2026上半年軟考中級(jí)軟件設(shè)計(jì)師第5章《算法基礎(chǔ)》考試知識(shí)點(diǎn)分值分布及試題如下：

第5章 算法基礎(chǔ)

一、分值分布

二、試題示例

1．算法效率--1分

試題【2020年下半年軟件設(shè)計(jì)師考試基礎(chǔ)知識(shí)真題】

根據(jù)漸進(jìn)分析，表達(dá)式序列：n4, lgn, 2n, 1000n, n2/3, n!從低到高排序?yàn)椋?nbsp; ）。

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

解析：

本題考查時(shí)間復(fù)雜度的相關(guān)知識(shí)。

根據(jù)選項(xiàng)來(lái)看，1000n的漸進(jìn)表示就是O(n)。因此lgn規(guī)模是小于1000n的，所以B選項(xiàng)錯(cuò)誤，n2/3小于n，因此D選項(xiàng)正確。

2．二分查找--3分

試題【2023年上半年軟件設(shè)計(jì)師考試基礎(chǔ)知識(shí)真題】

對(duì)某有序表進(jìn)行折半查找（二分查找）時(shí)，進(jìn)行比較的關(guān)鍵字序列不可能是（  ）。

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選項(xiàng)中比完61后與77比，就說(shuō)明要找的數(shù)比61大。

所以接下來(lái)不可能跟42比。所以選擇C選項(xiàng)。

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

試題【2022年上半年軟件設(shè)計(jì)師考試基礎(chǔ)知識(shí)真題】

以下關(guān)于散列表（哈希表)，及其查找特點(diǎn)的敘述中，正確的是（ ）。

A.在散列表中進(jìn)行查找時(shí)，只需要與待查找關(guān)鍵字及其同義詞進(jìn)行比較

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

C.用線性探測(cè)法解決沖突容易產(chǎn)生聚集問(wèn)題

D.用鏈地址法解決沖突可確保平均查找長(zhǎng)度為1

答案：C

解析：

A選項(xiàng)錯(cuò)誤，考查的是散列表查找時(shí)對(duì)應(yīng)位置填寫的可能是關(guān)鍵字、也可能是同義詞、也可能是非同義詞。在放置數(shù)據(jù)時(shí)，首次放置關(guān)鍵字本身或者同義詞（計(jì)算結(jié)果一致的元素），但也有可能在前面的處理過(guò)程中因?yàn)闆_突的原因，將某個(gè)非同義詞放置到該位置了，在查找過(guò)程中，這3類都有可能出現(xiàn)在計(jì)算結(jié)果對(duì)應(yīng)的位置，所以只需要與查找關(guān)鍵字及同義詞比較的說(shuō)法是錯(cuò)誤的。

B選項(xiàng)錯(cuò)誤，裝填因子越大，表示裝填的記錄越滿，發(fā)生沖突的可能性越大，反之發(fā)生沖突的可能性越小。并不會(huì)避免沖突發(fā)生。

C選項(xiàng)正確，線性探測(cè)法解決沖突空間利用率高，但容易發(fā)生聚集現(xiàn)象。

D選項(xiàng)錯(cuò)誤，鏈地址解決沖突時(shí)，可能會(huì)出現(xiàn)多個(gè)同義詞放在同一個(gè)鏈表，平均查找長(zhǎng)度無(wú)法確保為1。

因此本題正確答案為C選項(xiàng)。