為方便軟考考生對(duì)軟件設(shè)計(jì)師考試知識(shí)點(diǎn)的檢測(cè)，希賽軟考頻道為考生帶來(lái)軟考軟件設(shè)計(jì)師考試知識(shí)點(diǎn)填空檢測(cè)的內(nèi)容（完整版可在本文文首本文資料處或文末的資料下載欄目下載）。

軟考軟件設(shè)計(jì)師考試知識(shí)點(diǎn)填空檢測(cè)（4）內(nèi)容如下：

第4章 數(shù)據(jù)結(jié)構(gòu)

1 考點(diǎn)精講

1.1 線性結(jié)構(gòu)

1、線性結(jié)構(gòu)是一種基本的數(shù)據(jù)結(jié)構(gòu)， 主要用于對(duì)客觀世界中具有____和____的數(shù)據(jù)關(guān)系進(jìn)行描述。線性結(jié)構(gòu)的特點(diǎn)是數(shù)據(jù)元素之間呈現(xiàn)一種線性關(guān)系， 即元素“一個(gè)接一個(gè)排列”。

2、線性表的存儲(chǔ)結(jié)構(gòu)分為_(kāi)___和____。

3、棧和隊(duì)列是程序中常用的兩種數(shù)據(jù)結(jié)構(gòu),它們的邏輯結(jié)構(gòu)和線性表相同。其特點(diǎn)在于運(yùn)算有所限制。棧按____的規(guī)則進(jìn)行操作，隊(duì)列按____的規(guī)則進(jìn)行操作，故稱為運(yùn)算受限的線性表。

4、長(zhǎng)度為零的串稱為_(kāi)___，它不包含任何字符。

1.2 樹(shù)

1、雙親、孩子和兄弟：結(jié)點(diǎn)的子樹(shù)的根稱為該結(jié)點(diǎn)的____;相應(yīng)地，該結(jié)點(diǎn)稱為其子結(jié)點(diǎn)的____。具有相同雙親的結(jié)點(diǎn)互為_(kāi)___。

2、結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)的____記為該結(jié)點(diǎn)的度。

3、葉子結(jié)點(diǎn)：葉子結(jié)點(diǎn)也稱為_(kāi)___，指度為_(kāi)___的結(jié)點(diǎn)。

4、內(nèi)部結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，也稱為_(kāi)___或____。除根節(jié)點(diǎn)以外，分支結(jié)點(diǎn)也叫____。

5、樹(shù)的高度：一棵樹(shù)的最大層數(shù)記為樹(shù)的____。

6、對(duì)于任何一棵二叉樹(shù)，若其終端結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2，則滿足等式____。

7、具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為_(kāi)___。

8、最優(yōu)二叉樹(shù)又稱為_(kāi)___，它是一類帶權(quán)路徑長(zhǎng)度最短的樹(shù)。

9、前序遍歷：又稱為先序遍歷，按____的順序進(jìn)行遍歷。

10、后序遍歷：按____的順序進(jìn)行遍歷。

11、中序遍歷：按____的順序進(jìn)行遍歷。

12、____：按層次順序進(jìn)行遍歷。

1.3 圖

1、有向圖。若圖中每條邊都是____的，那么頂點(diǎn)之間的關(guān)系用<v，y>表示，它說(shuō)明從v到y(tǒng)有一條有向邊(也稱為弧)。v是有向邊的起點(diǎn)，稱為弧尾，y是有向邊的終點(diǎn)，稱為弧頭。所有邊都有方向的圖稱為_(kāi)___。

2、無(wú)向圖。若圖中的每條邊都是____的，頂點(diǎn)v和y之間的邊用(v，y)表示。因此,在有向圖中<v，y>與<y，v>分別表示兩條邊，而在無(wú)向圖中(v，y)與(y，v)表示的是____。

3、完全圖。若一個(gè)無(wú)向圖具有n個(gè)頂點(diǎn)，而每一個(gè)頂點(diǎn)與其他n -1個(gè)頂點(diǎn)之間都有邊，則稱之為_(kāi)___。顯然，含有n個(gè)頂點(diǎn)的無(wú)向完全圖共有____條邊。

4、度：頂點(diǎn)v的度是指關(guān)聯(lián)于該頂點(diǎn)的____的數(shù)目。

5、圖的基本存儲(chǔ)結(jié)構(gòu)有____表示法和____表示法兩種。

6、無(wú)向圖的鄰接矩陣是____的，有向圖的鄰接矩陣則不一定____。

7、____搜索和____搜索是兩種遍歷圖的基本方法。

8、對(duì)于連通網(wǎng)來(lái)說(shuō)，邊是帶權(quán)值的，生成樹(shù)的各邊也帶權(quán)值，因此把生成樹(shù)各邊的權(quán)值總和稱為生成樹(shù)的權(quán)，把權(quán)值最小的生成樹(shù)稱為_(kāi)___。

9、普里姆算法的時(shí)間復(fù)雜度為O(n^2),與圖中的邊數(shù)無(wú)關(guān)，因此該算法適合于求____的網(wǎng)的最小生成樹(shù)。

10、克魯斯卡爾算法的時(shí)間復(fù)雜度為O(eloge)，與圖中的頂點(diǎn)數(shù)無(wú)關(guān)，因此該算法適合于求____的網(wǎng)的最小生成樹(shù)。

11、AOV網(wǎng)從源點(diǎn)到匯點(diǎn)的路徑中，長(zhǎng)度最長(zhǎng)的路徑稱為_(kāi)___。關(guān)鍵路徑上的所有活動(dòng)均是關(guān)鍵活動(dòng)。

1.4 查找

1、順序查找的基本思想是:從表的一端開(kāi)始，逐個(gè)將記錄的____和給定值比較，若找到一個(gè)記錄的關(guān)鍵字與給定值相等,則查找成功;若整個(gè)表中的記錄均比較過(guò)，仍未找到關(guān)鍵字等于給定值的記錄，則查找失敗。

2、____:首先將待查元素的關(guān)鍵字(Key) 值與表中間位置上的關(guān)鍵字進(jìn)行比較，若相等，則查找成功;否則需重新在上、下部分的表查找。

3、二叉排序樹(shù)又稱____，它或者是一棵空樹(shù)，或者是具有以下性質(zhì)的二叉樹(shù)。

(1)若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均____根結(jié)點(diǎn)的值。

(2)若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均____根結(jié)點(diǎn)的值。

(3)左、右子樹(shù)本身是____。

4、____又稱為AVL樹(shù)，它或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)。它的左子樹(shù)和右子樹(shù)都是平衡二叉樹(shù)，且左子樹(shù)和右子樹(shù)的高度之差的絕對(duì)值不超過(guò)____。

2 章節(jié)問(wèn)答

1、強(qiáng)連通圖和有向完全圖的區(qū)別？

答：