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

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

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

1.下述文件中適合于磁帶存儲的是(　　)

A.順序文件
B.索引文件
C.散列文件
D.多關(guān)鍵字文件

2.某二叉樹的后根遍歷序列為dabec，中根遍歷序列為debac，則先根遍歷序列為(　　)

A.acbed
B.becab
C.deabc
D.cedba

3.含有n個結(jié)點的二叉樹用二叉鏈表表示時，空指針域個數(shù)為(　　)

A.n-1
B.n
C.n+1
D.n+2

4.在一個圖中，所有頂點的度數(shù)之和與圖的邊數(shù)的比是(　　)

A.1∶2
B.1∶1
C.2∶1
D.4∶1

5.長度為n的鏈隊列用單循環(huán)鏈表表示，若只設(shè)頭指針，則出隊操作的時間復(fù)雜度為(　　)

A.O(1)

B.

C.O(n)

D.

6.下述幾種排序方法中，要求內(nèi)存量最大的是(　　)

A.插入排序
B.快速排序
C.歸并排序
D.選擇排序

7.對n個不同值進(jìn)行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)為(　　)

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

8.對線性表進(jìn)行二分查找時，要求線性表必須(　　)

A.以順序方式存儲
B.以鏈?zhǔn)椒绞酱鎯?br/>C.以順序方式存儲，且結(jié)點按關(guān)鍵字有序排列
D.以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排列

9.在表長為n的順序表上做刪除運算，其平均時間復(fù)雜度為(　　)

A.O(1)
B.O(n)

C.

D.

10.當(dāng)利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最大容量為(　　)

A.n-2
B.n-1
C.n
D.n+1

11.有關(guān)插入排序的敘述，錯誤的是(　　)

A.插入排序在最壞情況下需要時間

B.插入排序在最佳情況可在O(n)時間內(nèi)完成

C.插入排序平均需要時間

D.插入排序的空間復(fù)雜度為O(1)

12.有關(guān)樹的敘述正確的是(　　)

A.每一個內(nèi)部結(jié)點至少有一個兄弟
B.每一個葉結(jié)點均有父結(jié)點
C.有的樹沒有子樹
D.每個樹至少有一個根結(jié)點與一個葉結(jié)點。

13.循環(huán)隊列存儲在數(shù)組元素A[0]至A[m]中，則入隊時的操作為(　　)

A.rear=rear+1
B.rear=(rear+1)%(m-1)
C.rear=(rear+1)%m
D.rear=(rear+1)%(m+1)

14.關(guān)于串的的敘述，不正確的是(　　)

A.串是字符的有限序列
B.空串是由空格構(gòu)成的串
C.替換是串的一種重要運算
D.串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?/p>

15.對稱矩陣A[N][N]，A[1][1]為首元素，將下三角(包括對角線)元素以行優(yōu)先順序存儲到一維數(shù)組元素T[1]至T[N(N+1)/2]中，則任一上三角元素A[i][j]存于T[k]中，下標(biāo)k為(　　)

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

二、填空題(本大題共13小題，每小題2分，共26分)請在每小題的空格中填上正確答案。錯填、不填均無分。

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

12.在數(shù)據(jù)結(jié)構(gòu)中，各個結(jié)點按邏輯關(guān)系互相纏繞，任意兩個結(jié)點可以鄰接的結(jié)構(gòu)稱為________。

13.在單鏈表中，存儲每個結(jié)點有兩個域，一個是數(shù)據(jù)域，另一個是指針域，指針域指向該結(jié)點________的。

14.在棧結(jié)構(gòu)中，允許插入的一端稱為________。

15.從一個長度為n的順序表中刪除第i個元素(1≤i≤n)時，需向前移動________個元素。

16.一個棧的輸入序列是1，2，3，…，n，輸出序列的第一個元素是n，則第i個輸出元素為________。

17.循環(huán)隊列被定義為結(jié)構(gòu)類型，含有三個域：data、front和rear，則循環(huán)隊列sq為空的條件是________。

18.一個10階對稱矩陣A，采用行優(yōu)先順序壓縮存儲上三角元素，為第一個元素，其存儲地址為0，每個元素占有1個存儲地址空間，則的地址為________。

19.對于一棵滿二叉樹，若有m個葉子，則樹中結(jié)點數(shù)為________。

110.含有n個頂點和n-1條邊的連通圖G采用________存儲結(jié)構(gòu)較省空間。

111.在圖中，第一個頂點和最后一個頂點相同的路徑稱為________。

112.動態(tài)查找中兩個元素X，Y存入同一個散列表時，X、Y鍵值相同，則這種情況稱為________。

113.堆排序需________個記錄大小的輔助存儲空間。

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

21.有一字符串的次序為-3*y+a/y!2，試?yán)脳⑤敵龃涡蚋淖優(yōu)?y*-ay!2/+，試寫出進(jìn)棧和退棧的操作步驟。(用push(x)表示x進(jìn)棧，pop(x)表示x退棧)

22.已知一棵二叉樹的先根遍歷序列為ABCDEGHF，中根遍歷序列為CBEDAGFH，畫出該二叉樹。

23.題31圖中二叉排序樹的各結(jié)點的值為32～40，標(biāo)出各結(jié)點的值。              題31圖

24.下述矩陣表示一個無向網(wǎng)，畫出該無向網(wǎng)，并構(gòu)造出其最小生成樹。

25.什么是堆?寫出對應(yīng)于序列(10，20，7，75，41，67，3，9，30，45)的初始堆(堆頂元素取最小值)。

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

31.二叉樹按二叉鏈表形式存儲，編寫一個算法判別給定的二叉樹是否為完全二叉樹。

32.試寫出直接插入排序算法。