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

軟考軟件設(shè)計師考試知識點(diǎn)填空檢測（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)， 主要用于對客觀世界中具有____和____的數(shù)據(jù)關(guān)系進(jìn)行描述。線性結(jié)構(gòu)的特點(diǎn)是數(shù)據(jù)元素之間呈現(xiàn)一種線性關(guān)系， 即元素“一個接一個排列”。

2、線性表的存儲結(jié)構(gòu)分為____和____。

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

4、長度為零的串稱為____，它不包含任何字符。

1.2 樹

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

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

3、葉子結(jié)點(diǎn)：葉子結(jié)點(diǎn)也稱為____，指度為____的結(jié)點(diǎn)。

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

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

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

7、具有n個結(jié)點(diǎn)的完全二叉樹的深度為____。

8、最優(yōu)二叉樹又稱為____，它是一類帶權(quán)路徑長度最短的樹。

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

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

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

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

1.3 圖

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

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

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

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

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

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

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

8、對于連通網(wǎng)來說，邊是帶權(quán)值的，生成樹的各邊也帶權(quán)值，因此把生成樹各邊的權(quán)值總和稱為生成樹的權(quán)，把權(quán)值最小的生成樹稱為____。

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

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

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

1.4 查找

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

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

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

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

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

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

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

2 章節(jié)問答

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

答：