數據結構導論2013年10月真題及答案解析（02142）

數據結構導論2013年10月真題及答案解析（02142），該試卷為數據結構導論自考歷年真題試卷，包含答案及詳細解析。

一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其選出并將“答題紙”的相應代碼涂黑。錯涂、多涂或未涂均無分。

1.下列幾種算法時間復雜度中，最大的是(　　)

A.O(1)
B.O(n)
C.O(log₂n)
D.O(n²)

2.數據結構中結點按邏輯關系依次排列形成一條“鏈”的結構是(　　)

A.集合
B.圖結構
C.樹形結構
D.線性結構

3.在表長為100的順序表中做插入運算，平均移動元素的次數為(　　)

A.25
B.33
C.50
D.100

4.已知尾指針的單向循環鏈表中，在第一個結點后面插入一個新結點，該算法的時間復雜度為(　　)

A.O(1)
B.O(log₂n)
C.O(n)
D.O(n²)

5.下列表述正確的是(　　)

A.棧空時出棧產生“上溢”，棧滿時進棧產生“下溢”
B.棧空時出棧產生“下溢”，棧滿時進棧產生“上溢”
C.棧空時出棧和棧滿時進棧均產生“上溢”
D.棧空時出棧和棧滿時進棧均產生“下溢”

6.隊列操作的原則是(　　)

A.先進先出
B.后進先出
C.先進后出
D.只進不出

7.一棵深度為6的滿二叉樹有(　　)

A.63個結點
B.64個結點
C.127個結點
D.128個結點

8.在一棵度為3的樹中，度為3的結點有4個，度為2的結點有2個，度為1的結點有3個，則度為0的結點有(　　)

A.8個
B.10個
C.11個
D.12個

9.一棵二叉樹T，度為2的結點數為20個，則葉子結點數為(　　)

A.19個
B.20個
C.21個
D.22個

10.有10個葉結點的哈夫曼樹中共有(　　)

A.10個結點
B.11個結點
C.19個結點
D.21個結點

11.求圖中兩個結點之間的最短路徑采用的算法是(　　)

A.廣度優先搜索(BFS)算法
B.克魯斯卡爾(Kruskal)算法
C.普里姆(Prim)算法
D.迪杰斯特拉(Dijkstra)算法

12.順序查找算法的平均查找長度為(　　)

A.log₂n
B.(n-1)/2
C.n/2
D.(n+1)/2

13.二叉排序樹中，根的(　　)

A.左子樹是二叉排序樹、右子樹不一定是二叉排序樹
B.左子樹是二叉排序樹、右子樹也是二叉排序樹
C.左子樹不一定是二叉排序樹、右子樹是二叉排序樹
D.左子樹不一定是二叉排序樹、右子樹也不一定是二叉排序樹

14.冒泡排序的時間復雜度為(　　)

A.O(n)
B.O(nlog₂n)
C.O(n²)
D.O(log₂n)

15.關于穩定性的表述，正確的是(　　)

A.穩定性是排序方法本身的特性，與數據無關
B.穩定性不是排序方法本身的特性，與數據有關
C.穩定性是排序方法本身的特性，與數據有關
D.穩定性不是排序方法本身的特性，與數據無關

二、填空題(本大題共13小題，每小題2分，共26分)

11.數據中不可分割的最小標識單位是__________。

12.雙向循環鏈表中，在p所指結點的后面插入一個新結點*t，需要修改四個指針，分別為：t->prior=p; __________; p->next->prior=t; p->next=t;。

13.在帶有頭結點的循環鏈表中，頭指針為head，判斷指針p所指結點為首結點的條件是__________。

14.元素的進棧次序為1，2，3，…，n，出棧的第一個元素是n，則第k個出棧的元素是__________。

15.在棧結構中，允許插入和刪除的一端稱為__________。

16.100個結點的二叉樹采用三叉鏈表存儲時，空指針域NULL有__________個。

17.某二叉樹的先序遍歷序列為ABKLMNO，中序遍歷序列為BLKANMO，則該二叉樹中結點A的右孩子為結點__________。

18.一個二叉樹的最少結點個數為__________。

19.圖中第一個頂點和最后一個頂點相同的路徑稱為回路。除第一個頂點和最后一個頂點相同外，其余頂點不重復的回路，稱為__________。

110.設查找表有n個數據元素，則二分查找算法的平均查找長度為__________。

111.用鍵值通過散列函數獲取存儲位置的這種存儲方式構造的存儲結構稱為__________。

112.若在線性表中采用二分查找法查找元素，則該線性表必須按值有序，并且采用__________存儲結構。

113.堆分為最小堆和最大堆，若鍵值序列{k₁, k₂, …, k_n}，滿足，則這n個鍵值序列{k₁, k₂,…, k_n}是__________。

三、應用題(本大題共5小題，每小題6分，共30分)

21.設一個鏈棧的輸入序列為X，Y，Z，試寫出出棧的所有可能的輸出序列及其操作步驟。

22.設二叉樹的先序遍歷序列為DCBAHEIFG，中序遍歷序列為ABCHDIEFG，試畫出該二叉樹并寫出后序遍歷序列。

23.已知連通帶權圖如題31圖所示，試利用普里姆(Prim)算法，從頂點A出發，構造它的最小生成樹，畫出構造過程。                      題31圖

24.給定表(28，15，55，3，71，75，10，22，56)，試按元素在表中的順序將它們依次插入一棵初始時為空的二叉排序樹，畫出插入完成后的二叉排序樹。

25.應用直接選擇排序算法，對初始關鍵字序列為48，35，61，98，82，18，29，48的記錄進行從小到大排序，寫出排序過程和結果。

四、算法設計題(本大題共2小題，每小題7分，共14分)

31.單鏈表的結點結構定義如下：typedef struct node{   int data;    struct node *next; }Node, *LinkList;試編寫在帶頭結點的單鏈表head中查找第1個元素值小于x的結點的實現算法Node *GetLinklist( LinkList head, int x)，若找到，則返回指向該結點的指針，否則返回NULL。

32.假設樹采用孩子兄弟鏈表表示法，其結構定義如下：typedef struct tnode{  DataType data;   struct tnode *son, *brother;}*Tree;試編寫算法void leveltree(Tree root)實現樹的按層次遍歷。