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選項。