2026上半年軟考中級(jí)數(shù)據(jù)庫(kù)系統(tǒng)工程師第6章《數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)》考試知識(shí)點(diǎn)分值分布及試題如下：

第6章 數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)

一、分值分布

二、試題示例

1.線性表

令序列X、Y、Z的每個(gè)元素都按順序進(jìn)棧，且每個(gè)元素進(jìn)棧和出棧僅一次。則不可能得到的出棧序列是（ ）。

A.X Y Z

B.X Z Y

C.Z X Y

D.Y Z X

答案：C

解析：棧的順序：先進(jìn)后出。如要Z先出，則至少需要X-Y-Z依次全部進(jìn)棧，此時(shí)棧內(nèi)容已確定，出棧順序只能為Z-Y-X，因此，得不到序列ZXY。

2.樹(shù)與二叉樹(shù)

二叉樹(shù)遍歷是按照某種策略訪問(wèn)樹(shù)中的每個(gè)結(jié)點(diǎn)，且僅訪問(wèn)一次。按照遍歷左子樹(shù)要在遍歷右子樹(shù)之前進(jìn)行的原則，根據(jù)訪問(wèn)（ ）位置的不同，可得到二叉樹(shù)的前序、中序和后序三種遍歷方法。

A.根節(jié)點(diǎn)

B.導(dǎo)航節(jié)點(diǎn)

C.葉子結(jié)點(diǎn)

D.兄弟節(jié)點(diǎn)

答案：A

解析：本題考查數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)。

遍歷運(yùn)算是二叉樹(shù)的基本運(yùn)算，主要有先序、中序、后序和層序遍歷。

先序遍歷的基本方法：對(duì)于非空二叉樹(shù)，先訪問(wèn)根結(jié)點(diǎn)，然后先序遍歷根的左子樹(shù)，最后先序遍歷根的右子樹(shù)。因此，若已知某二叉樹(shù)的先序遍歷序列，則可直接得到其樹(shù)的根結(jié)點(diǎn)。

中序遍歷的基本方法：對(duì)于非空二叉樹(shù)，先中序遍歷根的左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后中序遍歷根的右子樹(shù)。因此，若已知某二叉樹(shù)的根結(jié)點(diǎn)，則可根據(jù)中序遍歷序列將該二叉樹(shù)左右子樹(shù)上的結(jié)點(diǎn)劃分開(kāi)。

后序遍歷的基本方法：對(duì)于非空二叉樹(shù)，首先后序遍歷根的左子樹(shù)，接著后序遍歷根的右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。因此，若已知某二叉樹(shù)的后序遍歷序列，則可直接得到其樹(shù)根結(jié)點(diǎn)。

因此，按照遍歷左子樹(shù)要在遍歷右子樹(shù)之前進(jìn)行的原則，根據(jù)訪問(wèn)根結(jié)點(diǎn)位置的不同， 可得到二叉樹(shù)的前序、中序和后序三種遍歷方法。

3.排序與查找

用哈希表存儲(chǔ)元素時(shí)，需要進(jìn)行沖突（碰撞）處理，沖突是指（ ）。

A.關(guān)鍵字被依次映射到地址編號(hào)連續(xù)的存儲(chǔ)位置

B.關(guān)鍵字不同的元素被映射到相同的存儲(chǔ)位置

C.關(guān)鍵字相同的元素被映射到不同的存儲(chǔ)位置

D.關(guān)鍵字被映射到哈希表之外的位置

答案：B

解析：A選項(xiàng)為一種解決沖突的辦法。題干問(wèn)的是沖突是什么，自然是B選項(xiàng)的意思。