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

軟考軟件設計師考試知識點填空檢測（4）內容如下：

第4章 數據結構

1 考點精講

1.1 線性結構

1、線性結構是一種基本的數據結構， 主要用于對客觀世界中具有____和____的數據關系進行描述。線性結構的特點是數據元素之間呈現一種線性關系， 即元素“一個接一個排列”。

2、線性表的存儲結構分為____和____。

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

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

1.2 樹

1、雙親、孩子和兄弟：結點的子樹的根稱為該結點的____;相應地，該結點稱為其子結點的____。具有相同雙親的結點互為____。

2、結點的度：一個結點的____記為該結點的度。

3、葉子結點：葉子結點也稱為____，指度為____的結點。

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

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

6、對于任何一棵二叉樹，若其終端結點數為n0,度為2的結點數為n2，則滿足等式____。

7、具有n個結點的完全二叉樹的深度為____。

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

9、前序遍歷：又稱為先序遍歷，按____的順序進行遍歷。

10、后序遍歷：按____的順序進行遍歷。

11、中序遍歷：按____的順序進行遍歷。

12、____：按層次順序進行遍歷。

1.3 圖

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

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

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

4、度：頂點v的度是指關聯(lián)于該頂點的____的數目。

5、圖的基本存儲結構有____表示法和____表示法兩種。

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

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

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

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

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

11、AOV網從源點到匯點的路徑中，長度最長的路徑稱為____。關鍵路徑上的所有活動均是關鍵活動。

1.4 查找

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

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

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

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

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

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

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

2 章節(jié)問答

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

答：