?數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2012年1月真題（02142）

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

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

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

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

A.集合
B.線性結(jié)構(gòu)
C.樹(shù)形結(jié)構(gòu)
D.圖狀結(jié)構(gòu)

2.下面算法程序段的時(shí)間復(fù)雜度為(　　)for ( int i=0; i<m; i++)       for ( int j=0; j<n; j++)               a[i][j]=i*j;

A.

B.

3.線性結(jié)構(gòu)是(　　)

A.具有n(n≥0)個(gè)表元素的有窮序列
B.具有n(n≥0)個(gè)字符的有窮序列
C.具有n(n≥0)個(gè)結(jié)點(diǎn)的有窮序列
D.具有n(n≥0)個(gè)數(shù)據(jù)項(xiàng)的有窮序列

4.單鏈表中刪除由某個(gè)指針變量指向的結(jié)點(diǎn)的直接后繼，該算法的時(shí)間復(fù)雜度是(　　)

A.O(1)

B.

C.O(log₂n)

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

A.串是含有一個(gè)或多個(gè)字符的有窮序列
B.空串是只含有空格字符的串
C.空串是含有零個(gè)字符或含有空格字符的串
D.串是含有零個(gè)或多個(gè)字符的有窮序列

6.棧的輸入序列依次為1，2，3，4，則不可能的出棧序列是(　　)

A.1243
B.1432
C.2134
D.4312

7.隊(duì)列是(　　)

A.先進(jìn)先出的線性表
B.先進(jìn)后出的線性表
C.后進(jìn)先出的線性表
D.隨意進(jìn)出的線性表

8.10階上三角矩陣壓縮存儲(chǔ)時(shí)需存儲(chǔ)的元素個(gè)數(shù)為(　　)

A.11
B.56
C.100
D.101

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

A.2k 個(gè)
B.(2^k -1)個(gè)
C.2^k-1個(gè)
D.(2^k+1)個(gè)

10.具有12個(gè)結(jié)點(diǎn)的二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)中，空鏈域NULL的個(gè)數(shù)為(　　)

A.11
B.13
C.23
D.25

11.具有n個(gè)頂點(diǎn)的無(wú)向圖的邊數(shù)最多為(　　)

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

12.三個(gè)頂點(diǎn)v1，v2，v3的圖的鄰接矩陣為，該圖中頂點(diǎn)v3的入度為(　　)

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

13.順序存儲(chǔ)的表格中有60000個(gè)元素，已按關(guān)鍵字值升序排列，假定對(duì)每個(gè)元素進(jìn)行查找的概率是相同的，且每個(gè)元素的關(guān)鍵字值不相同。用順序查找法查找時(shí)，平均比較次數(shù)約為(　　)

A.20000
B.30000
C.40000
D.60000

14.外存儲(chǔ)器的主要特點(diǎn)是(　　)

A.容量小和存取速度低
B.容量大和存取速度低
C.容量大和存取速度高
D.容量小和存取速度高

15.在待排數(shù)據(jù)基本有序的前提下，效率最高的排序算法是(　　)

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

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

11.數(shù)據(jù)的不可分割的最小標(biāo)識(shí)單位是________，它通常不具有完整確定的實(shí)際意義，或不被當(dāng)作一個(gè)整體對(duì)待。

12.運(yùn)算分為加工型運(yùn)算和引用型運(yùn)算，讀取操作是________運(yùn)算。

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

14.在雙鏈表中，前趨指針和后繼指針?lè)謩e為prior和next。若使指針p往后移動(dòng)兩個(gè)結(jié)點(diǎn)，則需執(zhí)行語(yǔ)句________。

15.元素s₁，s₂，s₃，s₄，s₅，s₆依次進(jìn)入順序棧S，如果6個(gè)元素的退棧順序?yàn)閟₂，s₃，s₄，s₆，s₅，s₁，則順序棧的容量至少為_(kāi)_______。

16. 稀疏矩陣一般采用的壓縮存儲(chǔ)方法是________。

17. 在一棵樹(shù)中，________結(jié)點(diǎn)沒(méi)有雙親。

18.一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中，從樹(shù)根起，自上而下、自左至右給所有結(jié)點(diǎn)編號(hào)。設(shè)根結(jié)點(diǎn)編號(hào)為1，若編號(hào)為i的結(jié)點(diǎn)有父結(jié)點(diǎn)，那么其父結(jié)點(diǎn)的編號(hào)為_(kāi)_______。

19.二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)中判斷指針p所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是________。

110.邊稀疏的無(wú)向圖采用________存儲(chǔ)較省空間。

111.除第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同外，其余頂點(diǎn)不重復(fù)的回路，稱為_(kāi)_______。

112.二分查找算法的時(shí)間復(fù)雜度是________。

113.要將序列{51，18，23，68，94，70，73}建成堆，則只需把18與________相互交換。

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

21.將題29圖所示的一棵二叉樹(shù)轉(zhuǎn)換成對(duì)應(yīng)的森林。題29圖

22.給定權(quán)值{3，9，13，5，7｝，構(gòu)造相應(yīng)的哈夫曼(Huffman)樹(shù)，并計(jì)算其帶權(quán)路徑長(zhǎng)度。

23.寫出題31圖的鄰接矩陣和每個(gè)頂點(diǎn)的入度與出度。題31圖

24.二叉排序樹(shù)的各結(jié)點(diǎn)的值依次為20~28，請(qǐng)?jiān)陬}32圖中標(biāo)出各結(jié)點(diǎn)的值。                              題32圖

25.用冒泡排序法對(duì)數(shù)據(jù)序列(55，38，65，97，76，138，27，49)進(jìn)行排序，寫出排序過(guò)程中的各趟結(jié)果。

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

31.設(shè)線性表A =(a1，a2，…，am)，B=(b1，b2，…，bn)，試寫一個(gè)按下列規(guī)則合并A，B為線性表C的算法，使得        C=(a1，b1，…，am，bm，bm+1，…，bn) 當(dāng)m≤n時(shí);或者 C=(a1，b1，…，an，bn，an+1，…，am) 當(dāng)m>n時(shí)。線性表A，B和C均以帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)，且C表利用A表和B表中的結(jié)點(diǎn)空間構(gòu)成。(注意：?jiǎn)捂湵淼拈L(zhǎng)度值m和n均未顯式存儲(chǔ)。)

32.二叉樹(shù)的二叉鏈表類型定義如下：typedef struct btnode {        datatype data;        struct btnode *lchild, *rchild;} bitreptr;寫出后根遍歷根指針為t的二叉樹(shù)的遞歸算法( void postorder( bitreptr *t ))。