數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2011年10月真題及答案解析（02142）

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2011年10月真題及答案（02142），該試卷為數(shù)據(jù)結(jié)構(gòu)導(dǎo)論自考?xì)v年真題試卷，包含答案及詳細(xì)解析。

一、單項(xiàng)選擇題(本大題共15小題。每小題2分。共30分)在每小題列出的四個備選項(xiàng)中只有一個是符合題目要求的。請將其代碼填寫在題后的括號內(nèi)。錯選、多選或未選均無分。

1.設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1，e2，e3，e4，e5和e6依次通過棧S，元素退棧后即進(jìn)人隊(duì)列Q，若6個元素的出隊(duì)序列是e2，e4，e3，e6，e5，e1，則棧S的容量至少為(　　)

A.2
B.3
C.4
D.6

2.設(shè)計(jì)一個判別表達(dá)式中左右括號是否配對出現(xiàn)的算法，采用的最佳數(shù)據(jù)結(jié)構(gòu)為(　　)

A.線性表的順序存儲結(jié)構(gòu)
B.隊(duì)列
C.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)
D.棧

3.下列程序段的時間復(fù)雜度為(　　)i=0; s=0;while(s<n){  i++;   s =s+i;}

A.

B.

C.O(n)

D.

4.設(shè)A是n×n的對稱矩陣，將A的對角線及對角線上方的元素Aij(1≤i，j≤n，i≤j)以列優(yōu)先順序存放在一維數(shù)組元素B[1]至B[n(n+1)/2]中，則元素Aij(i≤j)在B中的位置為(　　)

A.i(i-1)/2+j
B.j(j-1)/2+i
C.j(j-1)/2+i-1
D.i(i-1)/2+j-1

5.在有向圖G的拓?fù)湫蛄兄校繇旤c(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是(　　)

A.G中有弧

B.G中有一條從Vi到Vj的路徑

C.G中沒有弧

D.G中有一條從Vj到Vi的路徑

6.下列序列中，由第一趟快速排序可得到的序列(排序的關(guān)鍵字類型是字符串)是(　　)

A.[da，ax，eb，de，bb] ff [ha，gc]
B.[cd，eb，ax，da] ff [ha，gc，bb]
C.[gc，ax，eb，cd，bb] ff [da，ha]
D.[ax，bb，cd，da] ff [eb，gc，ha]

7.不穩(wěn)定的排序方法是(　　)

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

8.設(shè)散列表表長m=14，散列函數(shù)為h(k)=k%11，表中已有4個記錄，如果用二次探測法處理沖突，關(guān)鍵字為49的記錄的存儲位置是(　　)

A.3
B.5
C.8
D.9

9.若元素1，2，3依次進(jìn)棧，則退棧不可能出現(xiàn)的次序是(　　)

A.3，2，1
B.2，1，3
C.3，1，2
D.1，3，2

10.直接插入排序的時間復(fù)雜度是(　　)

A.

B.

C.O(n)

D.

11.稀疏矩陣是指(　　)

A.元素少的矩陣
B.有少量零元素的矩陣
C.有少量非零元素的矩陣
D.行數(shù)、列數(shù)很少的矩陣

12.深度為k(k≥1)的二叉樹，結(jié)點(diǎn)數(shù)最多有(　　)

A.2k

B.-1

C.

D.-1

13.由帶權(quán)為9，2，5，7的四個葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為(　　)

A.23
B.37
C.44
D.46

14.有n個頂點(diǎn)的有向完全圖的弧數(shù)為(　　)

A.

B.2n
C.n(n-1)
D.2n(n+1)

15.圖的深度優(yōu)先搜索類似于二叉樹的(　　)

A.先根遍歷
B.中根遍歷
C.后根遍歷
D.層次遍歷

二、填空題(本大題共13小題。每小題2分，共26分)請?jiān)诿啃☆}的空格中填上正確答案。錯填、不填均無分。

11.下列程序段的時間復(fù)雜度為________。for( i=1; i<-n; i++ )      for( j=1; j<=n; j++ )             x++;

12.數(shù)據(jù)結(jié)構(gòu)中結(jié)點(diǎn)按邏輯關(guān)系依次排列形成一條“鎖鏈”的結(jié)構(gòu)是________。

13.在表長為n的順序表上做刪除運(yùn)算，平均要移動的結(jié)點(diǎn)個數(shù)為________。

14.在帶有頭結(jié)點(diǎn)的單循環(huán)鏈表head中，指針P所指結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件是________。

15.隊(duì)列又稱為________的線性表。

16.順序棧被定義為結(jié)構(gòu)類型，含有兩個域：data和top，則對棧*sq進(jìn)行初始化的操作是________。

17.對于任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為‰，度為2的結(jié)點(diǎn)數(shù)為，則________。

18.一棵具有n個結(jié)點(diǎn)的二叉樹，采用二叉鏈表存儲，則二叉鏈表中指向孩子結(jié)點(diǎn)的指針有________個。

19.若連通圖G的頂點(diǎn)個數(shù)為n，則圖G的生成樹的邊數(shù)為________。

110.一個具有n個頂點(diǎn)的無向圖的邊數(shù)最多為________。

111.中根遍歷二叉排序樹所得到的結(jié)點(diǎn)訪問序列是鍵值的________序列。

112.冒泡排序的平均時間復(fù)雜度為________。

113.將序列(60，20，23，68，94，70，73)建成堆，則只需把20與________互相交換。

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

21.如題29圖所示，在棧的輸入端元素的輸入順序?yàn)锳，B，C，D，進(jìn)棧過程中可以退棧，寫出在棧的輸出端以A開頭和以B開頭的所有輸出序列。

22.一棵二叉樹如題30圖所示，寫出該二叉樹的先根遍歷序列、中根遍歷序列和后根遍歷序列。

23.將題31圖所示的一棵二叉樹轉(zhuǎn)換成森林。題31圖

24.對于有向無環(huán)圖：(1)敘述求拓?fù)渑判蛩惴ǖ幕静襟E;(2)對于題32圖，寫出它的4個不同的拓?fù)渑判蛐蛄小?img style="width: 258px; height: 205px;" src="https://status.shangxueba.com/exam/2019-03-20/92195168791112.png" width="355" height="316"/>

25.判別以下序列是否為堆。如果不是，則把它調(diào)整為堆。(1)(100，86，48，73，35，39，42，57，66，21);(2)(12，70，33，65，24，56，48，92，86，33)。

四、算法設(shè)計(jì)題(本大題共2小題。每小題7分。共14分)

31.n個結(jié)點(diǎn)的完全二叉樹按結(jié)點(diǎn)編號將值順序存放在一維數(shù)組元素A[1]至A[n]中，試編寫算法實(shí)現(xiàn)將順序存儲結(jié)構(gòu)轉(zhuǎn)換為二叉鏈表存儲結(jié)構(gòu)，其中根結(jié)點(diǎn)由tree指向。

32.試寫出冒泡排序算法。