高等教育自學考試 數(shù)據(jù)結(jié)構(gòu)試題2

2017年4月高等教育自學考試《數(shù)據(jù)結(jié)構(gòu)》試題

課程代碼：02331

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

1.下列敘述中，不正確的是

A.算法解決的只能是數(shù)值計算問題

B.同一問題可以有多種不同算法

C.算法的每一步操作都必須明確無歧義

D.算法必須在執(zhí)行有限步后結(jié)束

2.下列關(guān)于棧中邏輯上相鄰的兩個數(shù)據(jù)元素的敘述中，正確的是

A.順序存儲時不一定相鄰，鏈式存儲時一定相鄰

B.順序存儲時不一定相鄰，鏈式存儲時也不一定相鄰

C.順序存儲時一定相鄰，鏈式存儲時也一定相鄰

D.順序存儲時一定相鄰，鏈式存儲時不--定相鄰

3.對帶頭結(jié)點的單循環(huán)鏈表從頭結(jié)點開始遍歷(head為頭指針，p=head->next)。若指

針p指向當前被遍歷結(jié)點，則判定遍歷過程結(jié)束的條件是

A.p==NULLB.head==NULLC.p==headD.head!=p

4.設(shè)棧的入棧序列為123,4,5,經(jīng)過入、出棧操作后，，可能得到的出棧序列是

A.2,3,5,1,4B.421,3,5C.3,4,1,2,5D.34,2,1,5

5.數(shù)組A[2][3]按行優(yōu)先順序存放，A的首地址為10。若A中每個元素占用一個存儲單元，則元素

的存儲地址是

A.10B.12C.14D.15

6.廣義表((a,b),(c,d))的表尾是

A.bB.dC.(c,d)D.((c,d))

7.若完全二叉樹T包含20個終端結(jié)點，則T的結(jié)點數(shù)最多是

A.38B.39C.40D.41

8.對下面的二叉樹進行中序線索化后，結(jié)點f的右指針指向的結(jié)點是

A.aB.bC.cD.e

9.若圖G是一個含有n個頂點的強連通有向圖，則G的邊數(shù)至少是

A.n-lB.nC.n*(n+l)/2D.n*(n+l)

10.若從頂點a開始對下圖進行廣度優(yōu)先遍歷，則不可能得到的遍歷序列是

a

A.a,b>c,e,f,dB.a,c,b,e,f,d

C?a,c>e,b,d,tD.a,e,b,c,f,d

11.下列排序算法中，穩(wěn)定的是

A.堆排序B.直接選擇排序

C.冒泡排序D.希爾排序

12.下列排序算法中，比較操作的次數(shù)與待排序序列初始排列狀態(tài)無關(guān)的是

A.快速排序B.直接選擇排序

C.冒泡排序D.直接插入排序

13.若對二叉排序樹進行遍歷，則下列遍歷方式中，其遍歷結(jié)果為遞增有序的是

A.前序遍歷B.中序遍歷

C.后序遍歷D.按層遍歷

14.設(shè)一組記錄的關(guān)鍵字為｛12,22,10,20,88,27,54,11),散列函數(shù)為H(key尸key%11,

用拉鏈法解決沖突，則散列地址為0的鏈中結(jié)點數(shù)是

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

15.在下面3階B樹中插入關(guān)鍵字65后，其根結(jié)點內(nèi)的關(guān)鍵字是

A.5390B.53C.90D.65

二、填空題(本大題共10小題，每小題2分，共20分)

16.散列方法的基本思想是根據(jù)元素的關(guān)鍵字直接計算出該元素的。

17.一個需要頻繁增刪的線性表宜選擇存儲結(jié)構(gòu)。

18.若中綴表達式為9+(6-2)*8,則相應(yīng)的后綴表達式是。

19.對任何一棵二叉樹T,若其葉子結(jié)點數(shù)為〃°,度數(shù)為2的結(jié)點數(shù)為〃2,則〃2等于。

20.若某二叉樹T的前序遍歷序列是A,B,C,D,中序遍歷序列是B,A,D,C,則T的后序遍歷

序列是.

21.在給定n個葉子結(jié)點權(quán)值且不含度數(shù)為1的結(jié)點的所有二叉樹中，其最小的二叉樹稱為

哈夫曼樹。

22.用鄰接表存儲含n個頂點e條邊的有向無環(huán)圖G,對G進行拓撲排序，算法的時間復雜度

為。

23.連通圖G的一個子圖如果是一棵包含G的所有頂點的樹，則該子圖稱為G的樹。

24.二分查找的速度快效率高，但是它要求表按關(guān)鍵字有序并且。

25.除了問題的規(guī)模和分量個數(shù)之外，還有是影響基數(shù)排序時間復雜度的主要因素。

三、解答題(本大題共4小題，每小題5分，共20分)

26.對題26圖所示的帶權(quán)無向圖G,試回答以下問題。

(1)畫出G的最小生成樹；

(2)若用克魯斯卡爾(Kruskal)算法求最小生成樹，請按被選中的次序?qū)懗鲎钚∩蓸渖细鳁l邊的頂點和

權(quán)值。

27.己知散列表的長度為11,散列函數(shù)為H(key尸key%ll,散列表的當前狀態(tài)如下：

現(xiàn)要插入關(guān)鍵字38,回答下列問題。

關(guān)鍵字|||II|60口7|29|||一

(1)若用線性探查法解決沖突，則38所在位置的下標是什么？

(2)若用二次探查法解決沖突，則38所在位置的下標是什么？

(3)以上兩種方法中，各需要多少次探查次數(shù)？

28.試回答下列關(guān)于拓撲排序算法的問題。

(1)算法中利用一個棧保存入度為0的頂點，其目的是什么？

(2)若在算法中將隊列改為棧，相應(yīng)地將入、出棧及判?？詹僮鞲臑槿?、出隊列和判隊列空操作，其他

部分不變，是否依然能夠得到拓撲排序的正確結(jié)果？

29.考慮用快速排序、堆排序和歸并排序3種排序方法對數(shù)據(jù)序列進行排序，針對下列不同情況，宜分別

選擇哪種排序方法？

(I)使用盡量少的存儲空間；

(2)要求排序結(jié)果是穩(wěn)定的；

(3)快速找出數(shù)據(jù)序列中關(guān)鍵字值較大的若干項。

四、算法閱讀題(本大題共4小題，每小題5分，共20分)

30.設(shè)鏈表中結(jié)點類型定義如下，閱讀程序，回答下列問題。

typedefintDataType；

typcdcfstructnOdc

{DataTypedata；

structnOdc*next；

JRecType,LinkLiSt；

intf30(LinkList*head)

{if(head=NULL)retumO；

elSe

retummax(head->data,f30(head->next))；//max(a,b)返回a,b中的較大者

)

(1)若鏈表L：{2,12,16,88,5,10),寫出調(diào)用f30(L)的輸出結(jié)果:

(2)函數(shù)f30的功能是什么？

31.函數(shù)131的功能是逆序輸出鏈表中所有結(jié)點的數(shù)據(jù)域值。請在空白處填充適當?shù)膬?nèi)容，使其完成指定

功能。

voidf3l(LinkList*head)

(

if(head二二NULL)⑴；

else

{f31(head->next)；

printf(n%d”,[2])；

)

)

32.函數(shù)f32的功能是統(tǒng)計N個頂點的有向圖中邊的數(shù)量，有向圖用鄰接矩陣A表示。

閱讀程序，并在空白處填入適當內(nèi)容，使其完成指定功能。

intf32(intA[][N|)

(

inti,j；

intsum=0；

for(i=0；i<N；⑴)

for((2)；j<N；j++)

if()sumll++；

returnsum；

)

33.已知二叉樹的二叉鏈表類型定義如下：

typedefstructnode

{chardata；

structnode*lchild,*rchild；

JBiTNode；

typedefBiTNodeBiTree；

以下程序為求二叉樹深度的遞歸算法，請?zhí)羁胀晟浦?/p>

intdepth(BiTree*bt)/*bt為指向根結(jié)點的指針*/

{inthl：0,hr：0；

if(______LU_______)retum(0)；

hl：depth(bt->lchild)；

hr=depth(bt->rchild)；

if((2))return(hl4-1)；

else⑶：

)

五、算法設(shè)計題(本大題共1小題，每小題10分，共10分)

34.已知二叉樹的結(jié)點類型定義如下：

typcdcfstructnode

{intdata：

structnode*lchild,*rchild；

}BinTNode；