數(shù)據(jù)結構附部分答案

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結構附部分答案一、選擇題

1、下面關于線性表的表達錯誤的是（C）。

A.線性表采用順序存儲必需占用一片連續(xù)的存儲空間B.線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間C.線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)D.線性表采用順序存儲便于插入和刪除操作的實現(xiàn)

2、棧是一種特別的線性表，具有（B）性質A．先進先出B.先進后出C.后進后出D.順序進出

3、順序循環(huán)隊列中（數(shù)組大小為n），隊頭指示front指向隊列的第一個元素，隊尾指示

rear指向隊列最終一個元素的后一個位置，則循環(huán)隊列中存放了n-1個元素，即循環(huán)隊列滿的條件是（B）。

A．(rear+1)%n=front-1B.(rear+1)%n=frontC.(rear)%n=frontD.rear+1=front

4、在一個單鏈表中，若刪除p所指結點的后續(xù)結點，則執(zhí)行（A）。A．p->next=p->next->nextB.p=p->next;p->next->nextC.p->next=p->nextD.p=p->next->next

5、設某二叉樹中度數(shù)為0的結點數(shù)為N0，度數(shù)為1的結點數(shù)為Nl，度數(shù)為2的結點數(shù)為N2，

則以下等式成立的是（A）。

A.N0=N2+1B.N0=Nl+N2C.N0=N1+1D.N0=2N1+l

6、設有6個結點的無向圖，該圖至少應有（D）條邊才能確保是一個連通圖。

A.8B.6C.7D.5

7、設有向無環(huán)圖G中的有向邊集合E={，，，}，則以下屬于該

有向圖G的一種拓撲排序序列的是（A）。

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

8、已知一個有向圖如下所示，則從頂點a出發(fā)進行深度優(yōu)先遍歷，不可能得到的DFS序列為（A）。

A.adbefcB.adcefbC.adcebfD.adefbc

b

a第1頁共11頁cefd

9、適用于折半查找的表的存儲方式及元素排列要求是（D）

A.鏈式方式存儲，元素無序B.鏈式存儲方式，元素有序C.順序存儲方式，元素無序D.順序存儲方式，元素有序

10、設一組初始記錄關鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進行

（C）趟的分派和回收才能使得初始關鍵字序列變成有序序列。A.5B.4C.3D.811、棧和隊列的共同特點是(A)。

A.只允許在端點處插入和刪除元素B.都是先進后出C.都是先進先出D.沒有共同點

12、用鏈接方式存儲的隊列，在進行插入運算時(D).A.僅修改頭指針B.頭、尾指針都要修改C.僅修改尾指針D.頭、尾指針可能都要修改

13、以下數(shù)據(jù)結構中哪一個是非線性結構？(D)

A.隊列B.棧C.線性表D.二叉樹

14、樹最適合用來表示(C)。

A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素

C.元素之間具有分支層次關系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)15、二叉樹的第k層的結點數(shù)最多為(D).

kk-1

A．2-1B.2K+1C.2K-1D.2

16、設某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（A）。(A)BADC(B)BCDA(C)CDAB(D)CBDA

前序遍歷先訪問根，所以C為根，在中序遍歷中先訪問左子樹，再訪問根，最終訪問右子樹，所以在中序序列中，C前面的為左子樹，其次個訪問的是左子樹的根A以此類推可得這樣的一棵二叉樹：

第2頁共11頁

17、以下四種排序中（D）的空間繁雜度最大。(A)插入排序(B)冒泡排序(C)堆排序(D)歸并排序

18、對于線性表（7，34，55，25，64，46，20，10）進行散列存儲時，若選用H（K）=K%9作為散列函數(shù)，則散列地址為1的元素有（D）個，

A．1B．2C．3D．4分別是：55，64，46，10.

H（K）=K%9，表示除以9的余數(shù)。由于地址重疊造成沖突，所以散列存儲時，尋常還要有解決沖突的方法，如線性探查法等等。

19、設有6個結點的無向圖，該圖至少應有(A)條邊才能確保是一個連通圖。A.5B.6C.7D.8

20、設哈夫曼樹中的葉子結點總數(shù)為m，若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有（B）個空指針域。(A)2m-1(B)2m(C)2m+1(D)4m

21.對一個算法的評價，不包括如下（B）方面的內容。

A．頑強性和可讀性B．并行性C．正確性D．時空繁雜度22.在帶有頭結點的單鏈表HL中，要向表頭插入一個由指針p指向的結點，則執(zhí)行(A)。

A.p->next=HL->next;HL->next=p;B.p->next=HL;HL=p;C.p->next=HL;p=HL;D.HL=p;p->next=HL;

23.對線性表，在以下哪種狀況下應當采用鏈表表示？(B)

A.經(jīng)常需要隨機地存取元素B.經(jīng)常需要進行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲空間D.表中元素的個數(shù)不變

24.一個棧的輸入序列為123，則以下序列中不可能是棧的輸出序列的是(C)

A.231B.321C.312D.12325.AOV網(wǎng)是一種（D）。

A．有向圖B．無向圖C．無向無環(huán)圖D．有向無環(huán)圖

26.下面程序的時間繁雜為（B）

for（i=1，s=0；idata==x)i++;p=p->next;

}//while,出循環(huán)時i中的值即為x結點個數(shù)returni;}//CountX

5、設計判斷兩個二叉樹是否一致的算法。

typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*bt1,bitree*bt2){

if(bt1==0

elseif(bt1==0||bt2==0||bt1->data!=bt2->data)return(0);

elsereturn(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));}

6、設計兩個自小到大有序單鏈表ha，hb的合并排序算法，合并后的單鏈表頭指針為hc。

7、實現(xiàn)對n個整數(shù)自小到大的直接插入排序。

第11頁共11頁

2、設計算法，實現(xiàn)二叉樹的遞歸先序遍歷。

3、設計算法，實現(xiàn)n個整數(shù)的快速排序。

4、統(tǒng)計出單鏈表HL中結點的值等于給定值X的結點數(shù)。intCountX(LNode*HL,ElemTypex){inti=0;LNode*p=HL;//i為計數(shù)器while(p!=NULL)

{if(P->data==x)i++;p=p->next;

}//while,出循環(huán)時i中的值即為x結點個數(shù)returni;}//CountX

5、設計判斷兩個二叉樹是否一致的算法。

typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*bt1,bitree*bt2){

if(bt1==0

elseif(bt1==0||bt2==0||bt1->data!=bt2->data)r