2015年04月自學(xué)考試02142《數(shù)據(jù)結(jié)構(gòu)概論》真題和答案

2015年4月高等教育自學(xué)考試全國統(tǒng)一命題考試

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試卷

(課程代碼02142)

本試卷共4頁，滿分100分，考試時(shí)間150分鐘。

考生答題注意事項(xiàng)：

1.本卷所有試題必須在答題卡上作答。答在試卷上無效，試卷空白處和背面均可作草稿紙。

2.第一部分為選擇題。必須對(duì)應(yīng)試卷上的題號(hào)使用2B鉛筆將“答題卡”的相應(yīng)代碼涂黑。

3.第二部分為非選擇題。必須注明大、小題號(hào)，使用0.5毫米黑色字跡簽字筆作答。

4.合理安排答題空間，超出答題區(qū)域無效。

第一部分選擇題

一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)

在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其選出并將“答題卡”

的相應(yīng)代碼涂黑。未涂、錯(cuò)涂或多涂均無分。

1.設(shè)某個(gè)算法的計(jì)算量是問題規(guī)模n的函數(shù)：T(n)=an'+blog2n+cn+d,則該算法的時(shí)問復(fù)度

可表示成

A.O(n)B.0(log2n)C.0(n)D.0(1)

2.將長(zhǎng)度為n的單鏈表鏈接在長(zhǎng)度為m的單鏈表之后的算法時(shí)間復(fù)雜度為

A.0(n)B.0(m)C.0(n+m)D.O(nXm)

3.為解決計(jì)算機(jī)與打印機(jī)之間速度不匹配的問題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將

要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯

結(jié)構(gòu)應(yīng)該是

A.棧B.隊(duì)列C.樹D.圖

4.對(duì)于n(n2O)個(gè)元素構(gòu)成的線性表L,適合采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的操作是

A.需要頻繁修改L中元素的值B.需要頻繁地對(duì)L進(jìn)行隨機(jī)查找

C.需要頻繁地對(duì)L進(jìn)行插入和刪除操作D.要求L存儲(chǔ)密度高

5.判斷一個(gè)帶有頭結(jié)點(diǎn)的鏈隊(duì)列為空隊(duì)列Q的條件是

A.Q.front=NULLB.Q.front==Q.rear

C.Q.front!=Q.rearD.Q.rear==NULL

6.在一個(gè)單鏈表中，已知指針q指向指針p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，則刪除*p結(jié)點(diǎn)的操作

語句是

A.q=p；B.q=p->next；

C.q—>next=pjD.q—>next==p—>nextj

7.把特殊矩陣A[10][10]的下三角矩陣壓縮存儲(chǔ)到一個(gè)一維數(shù)組M中，剛A中元素a[4][3]

在M中所對(duì)應(yīng)的下標(biāo)位置是

A.8B.12C.13D.55

8.若一棵具有n(n>0)個(gè)結(jié)點(diǎn)的二叉樹的先序序列與后序序列正好相反，則該二叉樹一定是

A.結(jié)點(diǎn)均無左孩子的二叉樹B.結(jié)點(diǎn)均無右孩子的二叉樹

C.存在度為2的結(jié)點(diǎn)的二叉樹D.高度為n的二叉樹

9.對(duì)關(guān)鍵字序列{0,2,4,8,16,32,64,128}進(jìn)行二分查找，則第一個(gè)被查找到的關(guān)鍵

字是

A.0B.8C.16D.128

10.已知一個(gè)圖如題10圖所示，若從頂點(diǎn)a出發(fā)進(jìn)行廣度優(yōu)先遍歷，則可能得到的廣度優(yōu)

先搜

索的結(jié)果序列為

A.acefbd

B.acbdfe

C.acbdef

D.acdbfe

11.若某二叉樹按后序遍歷得到的結(jié)果為c、b、a,則可以得到該結(jié)果的二叉樹有

A.1種B.2種C.3種D.5種

12.下列有關(guān)哈夫曼（Huffman）樹的描述，不正確的是

A.哈夫曼樹的樹形唯一，且其WPL值最小

B.哈夫曼樹的樹形不一定唯一，但其WPL值最小且相等

C.哈夫曼字符編碼不一定唯一，但總碼長(zhǎng)最短

D.哈夫曼樹沒有嚴(yán)格要求區(qū)別左右子樹權(quán)重次序

13.能夠使用二分查找算法進(jìn)行查找的條件是必須以

A.順序方式存儲(chǔ)，且元素按關(guān)鍵字有序B.鏈?zhǔn)椒绞酱鎯?chǔ)，且元素按關(guān)鍵字有序

C.順序方式存儲(chǔ)，且元素按關(guān)鍵字無序D.鏈?zhǔn)椒绞酱鎯?chǔ)，且元素按關(guān)鍵字無序

14.下列排序方法中不穩(wěn)定的是

A.直接插入排序B.堆排序

C.冒泡排序D.二路歸并排序

15.對(duì)于n個(gè)元素的關(guān)鍵字序列{ki,k,….，k?）,當(dāng)且僅當(dāng)滿足關(guān)系kiWkz,且kiWk2H（2iWn,

2i+lWn）稱其為最小堆，反之則為最大堆。以下序列中不符合最小堆或最大堆定義的是

A.{4,10,15,72,39,23,18}B.{58,27,36,12,8,23,9）

C.{4,10,18,72,39,23,15}D.{58,36,27,12,8,23,9}

第二部分非選擇題

二、填空題（本大題共13小題，每小題2分。共26分）

請(qǐng)?jiān)诖痤}卡上作答。

16.數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容包括數(shù)據(jù)的邏輯結(jié)構(gòu)、、以及對(duì)數(shù)據(jù)及其關(guān)

系的操作運(yùn)算。

17.根據(jù)數(shù)據(jù)元素之間的關(guān)系，通常有四類基本的邏輯結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、

18.在表長(zhǎng)為n的順序表中插入一個(gè)數(shù)據(jù)元素，平均需要移動(dòng)約個(gè)數(shù)據(jù)元素。

19.設(shè)有二維數(shù)組A[8][10],按行序優(yōu)先存儲(chǔ)，且每個(gè)元素占用2個(gè)存儲(chǔ)單元，若第一個(gè)

元素的存儲(chǔ)起始位置為b,則存儲(chǔ)位置為b+20處的元素為。

20.棧的特點(diǎn)是先進(jìn)后出或后進(jìn)先出，隊(duì)列的特點(diǎn)是。

21.若一棵二叉樹中度為1和度為2的結(jié)點(diǎn)個(gè)數(shù)均是3,則該二叉樹葉子結(jié)點(diǎn)的個(gè)數(shù)是.

22.高度（深度）為h的完全二叉樹最少的結(jié)點(diǎn)個(gè)數(shù)是。

23.根據(jù)圖的定義，圖中頂點(diǎn)的最少數(shù)目是____。

24.高度為3、含有5個(gè)結(jié)點(diǎn)（編號(hào)1?5）的二叉樹，其順序存儲(chǔ)結(jié)構(gòu)為

川2|3|0回4叵則編號(hào)為4的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為。

25.對(duì)如題25圖所示的含有3棵樹的森林進(jìn)行先序遍歷，得到的結(jié)果序列是一

26.按關(guān)鍵字的輸入序列｛30,22,42,7,25｝所生成的二又排序樹中，其左子樹上的關(guān)鍵

字有。

27.插入、選擇、冒泡及堆等四種排序方法在各自排序過程中其鍵值比較的次數(shù)與數(shù)據(jù)元素

的初始排列次序無關(guān)的有和堆排序。

28.用冒泡排序算法對(duì)n個(gè)帶有鍵值的數(shù)據(jù)元素進(jìn)行排序，排序結(jié)束后所可能歷經(jīng)的最少趟

數(shù)為______。

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

請(qǐng)?jiān)诖痤}卡上作答。

29.字符a.b、c、d依次通過一個(gè)棧，按出棧的先后次序組成字符串，至多可以組成多少

個(gè)不同的字符串？并分別寫出它們。

30.已知某棵二叉樹的先序遍歷和中序遍歷的結(jié)果序列分別為ABCDEFGHI和

BCAEDGHFK試構(gòu)造出該二叉樹，并給出該二叉樹的后序遍歷結(jié)果序列。

31.帶權(quán)圖（權(quán)值非負(fù)，表示邊連接的兩頂點(diǎn)間的距離）的最短路徑問題是找出從初始頂點(diǎn)

到目標(biāo)頂點(diǎn)之間的一條最短路徑。假定從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間存在路徑，現(xiàn)有一

種解決該問題的方法：①設(shè)最短路徑初始時(shí)僅包含初始頂點(diǎn)，令當(dāng)前頂點(diǎn)u為初始頂

點(diǎn)；②選擇離u最近且尚未在最短路徑中的一個(gè)頂點(diǎn)v,加入到最短路徑中，修改當(dāng)前頂

點(diǎn)vv；③重復(fù)步驟②，直到u是目標(biāo)頂點(diǎn)時(shí)為止。現(xiàn)問上述方法能否求得最短路徑？

若該方法可行，試證明之；否則，舉例說明。

32.將關(guān)鍵字序列｛7,8,30,11,18,9,14｝散列存儲(chǔ)到一個(gè)散列表中，設(shè)該散列表的存

儲(chǔ)空間是一個(gè)下標(biāo)從0開始、大?。℉ashSize）為10的一維數(shù)組，散列函數(shù)為

Il（key）=（keyX3）MODHashSize,處理沖突采用線性探測(cè)法?，F(xiàn)要求：（1）畫出所構(gòu)造的散列

表；（2）計(jì)算出等概率情況下查找成功的平均查找長(zhǎng)度。

33.若采用冒泡排序方法對(duì)關(guān)鍵字序列｛265,301,751,129,937,863,742,694,076,

438｝進(jìn)行升序排序，寫出其每趟排序結(jié)束后的關(guān)鍵字序列。

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

請(qǐng)?jiān)诖痤}卡上作答。

34.寫出一個(gè)將線性表的順序表存儲(chǔ)方式（數(shù)組a、表長(zhǎng)為n）改成單鏈表存儲(chǔ)方式（其頭結(jié)點(diǎn)

由頭指針head指向）的算法。設(shè)函數(shù)頭為：Node*CreateLinkedList（DataTypea[],int

n）

35.統(tǒng)計(jì)出一棵二叉樹中結(jié)點(diǎn)數(shù)據(jù)域的值不小于m的所有結(jié)點(diǎn)個(gè)數(shù)。設(shè)二叉樹的存儲(chǔ)結(jié)構(gòu)

為：

typedefstructbtnodej

intdata；

structbtnode*Ichild,*rchild；

}BTNode,*BTree；

2r

續(xù)承變★啟用前二啰禧二

2015年4月高等教育自學(xué)考試全國統(tǒng)一命題雪盒

數(shù)^^1導(dǎo)論試題答案及評(píng)分參承’

忑產(chǎn)（課程代碼02142）

一、單筆選擇題（木大是共15小惹，每小三：.公,

1.A2.B3.B

6.D7.C8.D

u.r12.A13.A

二、填空題（本大題共13小題,每小屋2分泮36分）

16.（數(shù)據(jù)的）存儲(chǔ)結(jié)構(gòu)17.圖續(xù)枷

,19.aLl]E0J受/后繇出

22.21

25.EBACDFHG.22725

28.1

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

29.共14個(gè)。

分別是：dcba,cbad,cbda,cdba,baud,bacic,bead,beda,bdca,abed,abac,aebd,aedb.

,adebo

30.門料層出的相應(yīng)的二叉樹為：

（3分）

等3。圖

其后序遍歷序列是:CBEHGIFDA。（3分）

32.該方謬得的方徑不一定是段短翳涇,<3分）

例溝產(chǎn)件答31圖所示的帝權(quán)圖，如果按熱屈于洛方法，從A男C忖球短卑徑為八:河’

段;事實(shí)上其墩短路徑為A-AC。

答31圖

數(shù)據(jù)紜構(gòu)導(dǎo)論試題答案及評(píng)分參考第1頁（頁）

32.(D答322

（3分）

(1廣1+”1丁2+1+3/7-8/7（3分）

33.初始態(tài):1299378637426940764381

751863742694076438J93（1分）

第二趟：[2651293017：；17-1269407643比863937C分)

笏學(xué):[129253301742694076438375^863937

1129

哥向趟26530]694075438]742)^51163937

第五趟：「12926530107643s二6947&751863937

第六趟11292650763013438694-,742751863937

第七趟：[129076265]301修弧742751863937（1分）

第八趟:[076129J2653,031433694742751863937

第九趟：076129265筵肥8694742751863937

（1分）

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

34.Node*CrcateLinkeclListCDataTypea[J.inin)

head~Olode*)malloc(sizeof(Node))；（1分）

head—>next=NULL