2026上半年软考中级软件设计师备考资料：第5章知识点分值分布及试题

2026上半年软考中级软件设计师第5章《算法基础》考试知识点分值分布及试题如下：

第5章 算法基础

一、分值分布

二、试题示例

1．算法效率--1分

试题【2020年下半年软件设计师考试基础知识真题】

根据渐进分析，表达式序列：n4, lgn, 2n, 1000n, n2/3, n!从低到高排序为（  ）。

A.lgn,1000n,n2/3,n4,n!,2n

B.n2/3,1000n,lgn,n4,n!,2n

C.lgn,1000n,n2/3,2n,n4,n!

D.lgn,n2/3,1000n,n4,2n,n!

答案：D

解析：

本题考查时间复杂度的相关知识。

根据选项来看，1000n的渐进表示就是O(n)。因此lgn规模是小于1000n的，所以B选项错误，n2/3小于n，因此D选项正确。

2．二分查找--3分

试题【2023年上半年软件设计师考试基础知识真题】

对某有序表进行折半查找（二分查找）时，进行比较的关键字序列不可能是（  ）。

A.42，61，90，85，77

B.42，90，85，61，77

C.90，85，61，77，42

D.90，85，77，61，42

答案：C

解析：

C选项中比完61后与77比，就说明要找的数比61大。

所以接下来不可能跟42比。所以选择C选项。

3．散列表（哈希）--3分

试题【2022年上半年软件设计师考试基础知识真题】

以下关于散列表（哈希表)，及其查找特点的叙述中，正确的是（ ）。

A.在散列表中进行查找时，只需要与待查找关键字及其同义词进行比较

B.只要散列表的装填因子不大于1/2，就能避免冲突

C.用线性探测法解决冲突容易产生聚集问题

D.用链地址法解决冲突可确保平均查找长度为1

答案：C

解析：

A选项错误，考查的是散列表查找时对应位置填写的可能是关键字、也可能是同义词、也可能是非同义词。在放置数据时，首次放置关键字本身或者同义词（计算结果一致的元素），但也有可能在前面的处理过程中因为冲突的原因，将某个非同义词放置到该位置了，在查找过程中，这3类都有可能出现在计算结果对应的位置，所以只需要与查找关键字及同义词比较的说法是错误的。

B选项错误，装填因子越大，表示装填的记录越满，发生冲突的可能性越大，反之发生冲突的可能性越小。并不会避免冲突发生。

C选项正确，线性探测法解决冲突空间利用率高，但容易发生聚集现象。

D选项错误，链地址解决冲突时，可能会出现多个同义词放在同一个链表，平均查找长度无法确保为1。

因此本题正确答案为C选项。