2015年04月自學考試02142《數據結構概論》真題和答案

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

數據結構導論試卷

(課程代碼02142)

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

考生答題注意事項：

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

2.第一部分為選擇題。必須對應試卷上的題號使用2B鉛筆將“答題卡”的相應代碼涂黑。

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

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

第一部分選擇題

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

在每小題列出的四個備選項中只有一個是符合題目要求的，請將其選出并將“答題卡”

的相應代碼涂黑。未涂、錯涂或多涂均無分。

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

可表示成

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

2.將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法時間復雜度為

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

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

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

結構應該是

A.棧B.隊列C.樹D.圖

4.對于n(n2O)個元素構成的線性表L,適合采用鏈式存儲結構的操作是

A.需要頻繁修改L中元素的值B.需要頻繁地對L進行隨機查找

C.需要頻繁地對L進行插入和刪除操作D.要求L存儲密度高

5.判斷一個帶有頭結點的鏈隊列為空隊列Q的條件是

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

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

6.在一個單鏈表中，已知指針q指向指針p所指結點的前驅結點，則刪除*p結點的操作

語句是

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

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

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

在M中所對應的下標位置是

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

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

A.結點均無左孩子的二叉樹B.結點均無右孩子的二叉樹

C.存在度為2的結點的二叉樹D.高度為n的二叉樹

9.對關鍵字序列{0,2,4,8,16,32,64,128}進行二分查找，則第一個被查找到的關鍵

字是

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

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

先搜

索的結果序列為

A.acefbd

B.acbdfe

C.acbdef

D.acdbfe

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

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

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

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

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

C.哈夫曼字符編碼不一定唯一，但總碼長最短

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

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

A.順序方式存儲，且元素按關鍵字有序B.鏈式方式存儲，且元素按關鍵字有序

C.順序方式存儲，且元素按關鍵字無序D.鏈式方式存儲，且元素按關鍵字無序

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

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

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

15.對于n個元素的關鍵字序列{ki,k,….，k?）,當且僅當滿足關系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分）

請在答題卡上作答。

16.數據結構研究的主要內容包括數據的邏輯結構、、以及對數據及其關

系的操作運算。

17.根據數據元素之間的關系，通常有四類基本的邏輯結構：集合、線性結構、樹形結構、

18.在表長為n的順序表中插入一個數據元素，平均需要移動約個數據元素。

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

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

20.棧的特點是先進后出或后進先出，隊列的特點是。

21.若一棵二叉樹中度為1和度為2的結點個數均是3,則該二叉樹葉子結點的個數是.

22.高度（深度）為h的完全二叉樹最少的結點個數是。

23.根據圖的定義，圖中頂點的最少數目是____。

24.高度為3、含有5個結點（編號1?5）的二叉樹，其順序存儲結構為

川2|3|0回4叵則編號為4的結點的雙親結點的編號為。

25.對如題25圖所示的含有3棵樹的森林進行先序遍歷，得到的結果序列是一

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

字有。

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

的初始排列次序無關的有和堆排序。

28.用冒泡排序算法對n個帶有鍵值的數據元素進行排序，排序結束后所可能歷經的最少趟

數為______。

三、應用題（本大題共5小題，每小題6分，共30分）

請在答題卡上作答。

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

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

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

BCAEDGHFK試構造出該二叉樹，并給出該二叉樹的后序遍歷結果序列。

31.帶權圖（權值非負，表示邊連接的兩頂點間的距離）的最短路徑問題是找出從初始頂點

到目標頂點之間的一條最短路徑。假定從初始頂點到目標頂點之間存在路徑，現有一

種解決該問題的方法：①設最短路徑初始時僅包含初始頂點，令當前頂點u為初始頂

點；②選擇離u最近且尚未在最短路徑中的一個頂點v,加入到最短路徑中，修改當前頂

點vv；③重復步驟②，直到u是目標頂點時為止。現問上述方法能否求得最短路徑？

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

32.將關鍵字序列｛7,8,30,11,18,9,14｝散列存儲到一個散列表中，設該散列表的存

儲空間是一個下標從0開始、大?。℉ashSize）為10的一維數組，散列函數為

Il（key）=（keyX3）MODHashSize,處理沖突采用線性探測法?，F要求：（1）畫出所構造的散列

表；（2）計算出等概率情況下查找成功的平均查找長度。

33.若采用冒泡排序方法對關鍵字序列｛265,301,751,129,937,863,742,694,076,

438｝進行升序排序，寫出其每趟排序結束后的關鍵字序列。

四、算法設計題（本大題共2小題，每小題7分，共14分）

請在答題卡上作答。

34.寫出一個將線性表的順序表存儲方式（數組a、表長為n）改成單鏈表存儲方式（其頭結點

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

n）

35.統(tǒng)計出一棵二叉樹中結點數據域的值不小于m的所有結點個數。設二叉樹的存儲結構

為：

typedefstructbtnodej

intdata；

structbtnode*Ichild,*rchild；

}BTNode,*BTree；

2r

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

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

數^^1導論試題答案及評分參承’

忑產（課程代碼02142）

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

1.A2.B3.B

6.D7.C8.D

u.r12.A13.A

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

16.（數據的）存儲結構17.圖續(xù)枷

,19.aLl]E0J受/后繇出

22.21

25.EBACDFHG.22725

28.1

三、應用題（本大題共5小邈，每小題6分，共30分）

29.共14個。

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

,adebo

30.門料層出的相應的二叉樹為：

（3分）

等3。圖

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

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

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

段;事實上其墩短路徑為A-AC。

答31圖

數據紜構導論試題答案及評分參考第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分)

笏學:[129253301742694076438375^863937

1129

哥向趟26530]694075438]742)^51163937

第五趟：「12926530107643s二6947&751863937

第六趟11292650763013438694-,742751863937

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

第八趟:[076129J2653,031433694742751863937

第九趟：076129265筵肥8694742751863937

（1分）

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

34.Node*CrcateLinkeclListCDataTypea[J.inin)

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

head—>next=NULL