數(shù)據(jù)結(jié)構(gòu)（本）模擬卷1

一、填空題（共10題海題1分，共10分）

1.圖的深度優(yōu)先遍歷類似于樹的遍歷。（1分）

★標(biāo)準(zhǔn)答案：1.先序；

2.有向盲G用鄰接矩’陣存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的o

（1分）

★標(biāo)準(zhǔn)答案：1.出度；

3.具有n個(gè)頂點(diǎn)的有向圖最多有條邊。（1分）

★標(biāo)準(zhǔn)答案：1.n（n-1）;

4.設(shè)一棵完全二叉樹具有1000個(gè)結(jié)點(diǎn)，則此完全二叉樹有個(gè)葉

子結(jié)點(diǎn)，有個(gè)度為2的結(jié)點(diǎn)，有個(gè)結(jié)點(diǎn)只有非空左

子樹，有個(gè)結(jié)點(diǎn)只有非空右子樹。（1分）

★標(biāo)準(zhǔn)答案：1.500;2.499;3.1;4.0;

5.圖的廣度優(yōu)先遍歷類似于樹的遍歷。（1分）

★標(biāo)準(zhǔn)答案：L層次；

6.有8個(gè)結(jié)點(diǎn)的無(wú)向圖最多有條邊。（1分）

★標(biāo)準(zhǔn)答案：1.28;

7.由樹轉(zhuǎn)換為二叉樹，其根節(jié)點(diǎn)的右子樹總是。（1分）

★標(biāo)準(zhǔn)答案：1.為空；

8.設(shè)有兩個(gè)串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱作

（1分）

★標(biāo)準(zhǔn)答案：1.子串定位；

9.已知二維數(shù)組A[20][10]采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占2個(gè)存儲(chǔ)單元，

并且A[10][5]的存儲(chǔ)地址是1000,則A[18][9]的存儲(chǔ)地址是。

（1分）

★標(biāo)準(zhǔn)答案：1.1168;

10.隊(duì)列是一種先進(jìn)先出的線性表，允許插入的一端稱為。（1分）

★標(biāo)準(zhǔn)答案：1.隊(duì)尾；

二、單選題（共10題海題2分，共20分）

1.判斷線索二叉樹中某結(jié)點(diǎn)p沒(méi)有左孩子的條件是（）。（2分）

A.p!=nullB.p->lchild!=null

C.p->ltag=0D.p->ltag=l

★標(biāo)準(zhǔn)答案：D

2.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少需要（）條邊。（2

分）

A.n

B.n-1

C.n/2

D.n+1

★標(biāo)準(zhǔn)答案：B

3.在長(zhǎng)度為n的順序表中的第i(iSign+l)個(gè)位置上插入一個(gè)元素，元素的移

動(dòng)次數(shù)為()。(2分)

A.n-i+1B.n-i

C.iD.i-1

★標(biāo)準(zhǔn)答案：A

4.在順序表(3,6,8,10,12,15,16,18,21,25,30)中,用折半法查找關(guān)鍵碼值11,

所需的關(guān)鍵碼比較次數(shù)為O次。(2分)

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

★標(biāo)準(zhǔn)答案：C

5,廣義表A=(()),則表尾GetTail(A)為()。(2分)

A.)B.(())C.空表D.(

★標(biāo)準(zhǔn)答案：C

6.已知二叉樹的中序序列為DBGEAFC,后序序歹U為DGEBFCA,則先序序列

為。。(2分)

A.BDEGACFB.ABDEGCFC.BDEAGCFD.ADBGEFC

★標(biāo)準(zhǔn)答案：B

7.設(shè)有1000個(gè)無(wú)序元素，希望用較快速度挑選出其中前10個(gè)最大元素，采用

()方法最好。(2分)

A.直接插入排序

B.堆排序

C.快速排序

D.歸并排序

★標(biāo)準(zhǔn)答案：B

8.已知一個(gè)圖共有n個(gè)頂點(diǎn)，e條邊，用鄰接矩陣表示，要?jiǎng)h除所有從第i個(gè)

結(jié)點(diǎn)出發(fā)的邊，在其時(shí)間復(fù)雜度為()。(2分)

A.O(n)

B.O(nA2)

C.O(n+e)

D.O(n*e)

★標(biāo)準(zhǔn)答案：B

9.如果二叉樹中某結(jié)點(diǎn)p->rtag=O,則在對(duì)該二叉樹按照某種次序進(jìn)行線索化時(shí),

該指針域指向該結(jié)點(diǎn)的()。(2分)

A.左孩子B.右孩子

C.遍歷前驅(qū)D.遍歷后繼

★標(biāo)準(zhǔn)答案：B

10.GetTail[GetHead[GetTail[((a,b),(c,d))]]]===()(2分)

A.(d)B.dC.(a,b)D.(a)

★標(biāo)準(zhǔn)答案：A

三、問(wèn)答題(共4題，每題5分洪20分)

1.簡(jiǎn)述什么是樹的定義。(5分)

★標(biāo)準(zhǔn)答案：樹是結(jié)點(diǎn)的有限集合，它有。個(gè)或1個(gè)根結(jié)點(diǎn)，記為T。其余的

結(jié)點(diǎn)分成為m(m>0)個(gè)有0個(gè)或1個(gè)互不相交的集合Tl,T2,…，Tm,每

個(gè)集合又都是樹，此時(shí)結(jié)點(diǎn)T稱為Ti的父結(jié)點(diǎn)，Ti稱為T的子結(jié)點(diǎn)(IgiWm)。

一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)為該結(jié)點(diǎn)的度。

2.簡(jiǎn)述什么是深度。(5分)

★標(biāo)準(zhǔn)答案：樹中所有結(jié)點(diǎn)的度的最大值。

3.寫出下列程序段的輸出結(jié)果。

voidmain()

{QueueQ;InitQueue(Q);

Charx='e';y='c';

EnQueue(Q,'h')；EnQueue(Q,'r')；EnQueue(Q,y);

DeQueue(Q,x);EnQueue(Q,x);

DeQueue(Q,x);EnQueue(Q,'a')；

While(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);};

printf(x);

}(5分)

★標(biāo)準(zhǔn)答案：輸出為“char”。

4.在哈希表中，發(fā)生沖突的可能性與哪些因素有關(guān)？為什么？(5分)

★標(biāo)準(zhǔn)答案：主要與哈希函數(shù)、裝填因子a有關(guān)。如果用哈希函數(shù)計(jì)算的地址

分布均勻，則沖突的可能性較小。在哈希存儲(chǔ)中，裝填因子a的值越大，則發(fā)

生沖突的可能性就越大；a的值越小，則發(fā)生沖突的可能性就越小。

四、計(jì)算題(共3題，每題10分洪30分)

1.已知某通訊系統(tǒng)使用8種字符，其概率分布分別為：0.06,0.28,0.07,0.08,

0.14,0.22,0.03,0.12,試設(shè)計(jì)其哈夫曼編碼。(10分)

★標(biāo)準(zhǔn)答案：哈夫曼不唯一，其對(duì)應(yīng)編碼也不唯一，寫對(duì)即可得分。

2.設(shè)關(guān)鍵字的輸入順序?yàn)椋?6,20,62,17,40,100。請(qǐng)寫出生成的二叉排

序樹及其中序遍歷序列。(10分)

★標(biāo)準(zhǔn)答案:1740100,/中序遍歷序列:17,20,40,56,62,100.

如下圖所示:

(1)畫出該圖的鄰接表表示；

3.(2)寫出從頂點(diǎn)a出發(fā)的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列。(io分)

★標(biāo)準(zhǔn)答案：

五、算法設(shè)計(jì)題(共2題，每題10分洪20分)

1.設(shè)A、B是兩個(gè)單鏈表，其表中元素遞增有序，寫一算法將A、B歸并成一

個(gè)有序的單鏈表C,C也是遞增有序的。(10分)

★標(biāo)準(zhǔn)答案:voidmerge(LinklistA,LinklistB,LinklistC){Listnode*p,*q,*r;

C=A;p=A->next;q=B->next;r=C;while(p!=null&q!=null)〃尾插法創(chuàng)建C鏈表

if(p->data<=q->data){r->next=p;r=p;p=p->next;else{r->next=q;r=q;q=q->next;

while(p!=null){r->next=p;r=p;p=p->next;while(q!=null){r->next=q;r=q;

q=q->next;free(B);

2.設(shè)計(jì)一遞歸算法，將以二叉鏈表為存儲(chǔ)結(jié)構(gòu)的二叉樹中的葉子結(jié)點(diǎn)全部刪除。

二叉排序樹的存儲(chǔ)結(jié)構(gòu)如下：(10分)

★標(biāo)準(zhǔn)答案：voidcout_node(BSTreeT)/*T為