?數據結構導論2014年4月真題（02142）

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

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

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

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

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

2.數據的存儲方式中除了順序存儲方式和鏈式存儲方式之外，還有(　　)

A.索引存儲方式和樹形存儲方式
B.線性存儲方式和散列存儲方式
C.線性存儲方式和索引存儲方式
D.索引存儲方式和散列存儲方式

3.表長為n的順序表中做刪除運算的平均時間復雜度為(　　)

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

4.順序表中定位算法(查找值為x的結點序號最小值)的平均時間復雜度為(　　)

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

5.元素的進棧次序為A，B，C，D，E，出棧的第一個元素為E，則第四個出棧的元素為(　　)

A.D
B.C
C.B
D.A

6.帶頭結點的鏈隊列中，隊列頭和隊列尾指針分別為front和rear，則判斷隊列空的條件為(　　)

A.front==rear
B.front!=NULL
C.rear!==NULL
D.front==NULL

7.深度為5的二叉樹，結點個數最多為(　　)

A.31個
B.32個
C.63個
D.64個

8.如果結點A有2個兄弟結點，結點B為A的雙親，則B的度為(　　)

A.1
B.3
C.4
D.5

9.將題9圖所示的一棵樹轉換為二叉樹，結點C是(　　)

A.A的左孩子
B.A的右孩子
C.B的右孩子
D.E的右孩子

10.n為圖的頂點個數，e為圖中弧的數目，則圖的拓撲排序算法的時間復雜度為(　　)

A.O(n)
B.O(e)
C.O(n-e)
D.O(n+e)

11.無向圖的鄰接矩陣是(　　)

A.對角矩陣
B.稀疏矩陣
C.上三角矩陣
D.對稱矩陣

12.在具有101個元素的順序表中查找值為x的元素結點時，平均比較元素的次數為(　　)

A.50
B.51
C.100
D.101

13.構造散列函數的方法很多，常用的構造方法有(　　)

A.數字分析法、除留余數法、平方取中法
B.線性探測法、二次探測法、除留余數法
C.線性探測法、除留余數法、鏈地址法
D.線性探測法、二次探測法、鏈地址法

14.就平均時間性能而言，快速排序方法最佳，其時間復雜度為(　　)

A.O(n)
B.O(nlog₂n)
C.O(n2)
D.O(1og₂n)

15.下述算法中，不穩定的排序算法是(　　)

A.直接插入排序
B.冒泡排序
C.堆排序
D.歸并排序

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

11.數據的基本單位是_________。

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

13.在帶有頭結點的循環鏈表中，尾指針為rear，判斷指針P所指結點為首結點的條件是_________。

14.若線性表中最常用的操作是求表長和讀表元素，則順序表和鏈表這兩種存儲方式中，較節省時間的是_________。

15.不含任何數據元素的棧稱為_________。

16.稀疏矩陣一般采用的壓縮存儲方法是_________。

17.100個結點的二叉樹采用二叉鏈表存儲時，用來指向左、右孩子結點的指針域有_________個。

18.已知完全二叉樹的第5層有5個結點，則整個完全二叉樹有_________個結點。

19.n個頂點的有向圖G用鄰接矩陣A[1..n，1..n]存儲，其第i列的所有元素之和等于頂點V_i的_________。

110.具有10個頂點的有向完全圖的弧數為_________。

111.要完全避免散列所產生的“堆積”現象，通常采用_________解決沖突。

112.在長度為n的帶有崗哨的順序表中進行順序查找，查找不成功時，與關鍵字的比較次數為_________。

113.歸并排序算法的時間復雜度是_________。

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

21.稀疏矩陣A如題29圖所示，寫出該稀疏矩陣A的三元組表示法。

22.設二叉樹的中序遍歷序列為BDCEAFHG，后序遍歷序列為DECBHGFA，試畫出該二叉樹。

23.寫出題31圖所示無向圖的鄰接矩陣，并寫出每個頂點的度。                      題31圖

24.已知散列表的地址空間為0至13，散列函數H(k)=k mod 11，(mod為求余運算)，待散列序列為(26，61，38，84，49)，用二次探測法解決沖突，構造該序列的散列表，要求寫出處理沖突的過程。

25.將一組鍵值(80，50，65，13，86，35，96，57，39，79，59，15)應用二路歸并排序算法從小到大排序，試寫出各趟的結果。

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

31.設單鏈表及鏈棧S的結構定義如下：typedef struct node{  Data Type data;   struct node *next;｝linkstack;編寫一個算法void ReverseList(1inkstack *head)，借助于棧S將帶頭結點單鏈表head中序號為奇數的結點逆置，序號為偶數的結點保持不變。(例如：單鏈表的邏輯結構為(a₁，a₂，a₃，a₄，a₅，a₆)，逆置后變為(a₅，a₂，a₃，a₄，a₁，a₆))。說明：棧的初始化運算用InitStack(S);進棧運算用Push(S, x);判棧空運算用EmptyStack(S);出棧運算用Pop(S);取棧頂元素運算用Gettop(S)。

32.以二叉鏈表作為存儲結構，試編寫遞歸算法實現求二叉樹中葉子結點個數。