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

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

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

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

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

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

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

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

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

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

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

A.O(1)

B.

C.O(n)

D.

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

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

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

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

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

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

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

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

C.

D.

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

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

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

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

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

C.插入排序平均需要時(shí)間

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

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

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

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

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.替換是串的一種重要運(yùn)算
D.串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)

15.對稱矩陣A[N][N]，A[1][1]為首元素，將下三角(包括對角線)元素以行優(yōu)先順序存儲(chǔ)到一維數(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分)請?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。

11.下列程序段的時(shí)間復(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)中，各個(gè)結(jié)點(diǎn)按邏輯關(guān)系互相纏繞，任意兩個(gè)結(jié)點(diǎn)可以鄰接的結(jié)構(gòu)稱為________。

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

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

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

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

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

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

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

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

111.在圖中，第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為________。

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

113.堆排序需________個(gè)記錄大小的輔助存儲(chǔ)空間。

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

21.有一字符串的次序?yàn)?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é)點(diǎn)的值為32～40，標(biāo)出各結(jié)點(diǎn)的值。              題31圖

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

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

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

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

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