數(shù)據(jù)結(jié)構(gòu)附部分答案

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

1、下面關(guān)于線性表的表達(dá)錯誤的是（C）。

A.線性表采用順序存儲必需占用一片連續(xù)的存儲空間B.線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間C.線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實現(xiàn)D.線性表采用順序存儲便于插入和刪除操作的實現(xiàn)

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

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所指結(jié)點的后續(xù)結(jié)點，則執(zhí)行（A）。A．p->next=p->next->nextB.p=p->next;p->next->nextC.p->next=p->nextD.p=p->next->next

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

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

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

6、設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有（D）條邊才能確保是一個連通圖。

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

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

有向圖G的一種拓?fù)渑判蛐蛄械氖牵ˋ）。

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

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

A.adbefcB.adcefbC.adcebfD.adefbc

b

a第1頁共11頁cefd

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

A.鏈?zhǔn)椒绞酱鎯?，元素?zé)o序B.鏈?zhǔn)酱鎯Ψ绞?，元素有序C.順序存儲方式，元素?zé)o序D.順序存儲方式，元素有序

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

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

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

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

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

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

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

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

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

kk-1

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

16、設(shè)某棵二叉樹的中序遍歷序列為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）進(jìn)行散列存儲時，若選用H（K）=K%9作為散列函數(shù)，則散列地址為1的元素有（D）個，

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

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

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

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

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

A．頑強性和可讀性B．并行性C．正確性D．時空繁雜度22.在帶有頭結(jié)點的單鏈表HL中，要向表頭插入一個由指針p指向的結(jié)點，則執(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.對線性表，在以下哪種狀況下應(yīng)當(dāng)采用鏈表表示？(B)

A.經(jīng)常需要隨機地存取元素B.經(jīng)常需要進(jìn)行插入和刪除操作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結(jié)點個數(shù)returni;}//CountX

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

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、設(shè)計兩個自小到大有序單鏈表ha，hb的合并排序算法，合并后的單鏈表頭指針為hc。

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

第11頁共11頁

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

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

4、統(tǒng)計出單鏈表HL中結(jié)點的值等于給定值X的結(jié)點數(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結(jié)點個數(shù)returni;}//CountX

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

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

if(bt1==0

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