大學(xué)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題

數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題

1、數(shù)據(jù)結(jié)構(gòu)1-1,須知E數(shù)值計算州翡設(shè)計I'碉中計算機(jī)的a以及他們之間的包和運(yùn)算的

刮

a操作對象；b.計算方法；c邏輯存儲；d.數(shù)據(jù)映像

a結(jié)構(gòu)；b.關(guān)系；c.運(yùn)算；d算法

2、數(shù)據(jù)結(jié)構(gòu)被形式化地定義為(DR〉，其中D是_b的有限集合，R是D上包的有限集

4口。

a.算法；b.數(shù)據(jù)元素：c.數(shù)據(jù)操作；d.邏輯結(jié)構(gòu)

a.操作：b.映像；c.存儲；d關(guān)系

3、線性表的順序存儲結(jié)構(gòu)是一種_3_的存儲結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種」_的存

儲結(jié)構(gòu)。

a.隨機(jī)存儲；b順序存儲；c.索引存取；d.HASH存取

4、一個棧的入棧序列是4b,cde,則棧的不可能的輸出序列是J。

a.edcba:b.decba;c.dceab:d.abcde

5、一個隊(duì)列的入隊(duì)序列是1,2,3,4,則隊(duì)列的愉出序列是b。

a.4,32/；b.1,23,4;c.1,43,2；d.32,4,1

6、廣義表((a),((b),c),<?d))))的長度是3,深度是」________。

7、深度為k的完全二叉樹至少有_2、_個結(jié)點(diǎn)，至多有_2<1____個結(jié)點(diǎn)，若按自上而下,

從左到右的次序給結(jié)點(diǎn)編號(從1開始)，則編號最小的葉子結(jié)點(diǎn)的編號是_2卜」1_。

8、現(xiàn)有中序遍歷二叉樹的結(jié)果為羯則有種不同形態(tài)的二叉樹可以得到這一遍歷

結(jié)果。

9、有一個有序表為｛1,3,9,12,32,41,45,62,75,77,82,95,100),當(dāng)二分查找

值為82的元素時，需要經(jīng)過工次比較就找到。

10、在線索二叉樹中，結(jié)點(diǎn)P沒有左子樹的充要條件是-->蛔=1_。

11s數(shù)據(jù)集｛4,5,6,730,1238｝為結(jié)點(diǎn)權(quán)值構(gòu)造Hufftnan樹，請給出構(gòu)造所得的Huffman

樹，并求其帶權(quán)路徑長度。

解答：

WPL=4*4+5*4Y*3+7*3+10*3+12*2+18*2

=9*4+23*3+30*2

=3169+60

=165

12、已知一棵度為k的樹中有m個度為1的結(jié)點(diǎn)，m個度為2的結(jié)點(diǎn)，…，眩個度為k的

結(jié)點(diǎn)，問該樹中有多少個葉子結(jié)點(diǎn)？

解答：設(shè)該樹的總結(jié)點(diǎn)數(shù)是：〃；分支數(shù)目是：3。則有：

〃=%+"1+“2"!-----F+3

另外，每個非葉子結(jié)點(diǎn)都產(chǎn)生分支，度為1的每個結(jié)點(diǎn)產(chǎn)生一個分支，度為2的每個結(jié)點(diǎn)產(chǎn)

生2個分支，…，度為左的每個結(jié)點(diǎn)產(chǎn)生上個分支；每個分支都進(jìn)入某一結(jié)點(diǎn)，在〃個

結(jié)點(diǎn)中，除根外，每個結(jié)點(diǎn)都有一個分支進(jìn)入。因此，有：

5=%+2n2+3n3+（左一l）9_i+knk

〃=3+1③

k

由①、②和③得到：勿0=%+2內(nèi)+34+…（左一1）%+1=N（j-l）%+1

13、假設(shè)一棵二叉樹的先序序列是EBADCFHGIKJ,中序序列是ABCDEFGHIJK。請畫出

該二叉樹。

和已知序列對應(yīng)的二叉樹是:

14、設(shè)線性表，試寫一按下列規(guī)則和并為線性表的算法，即

使得

當(dāng)時;

或者當(dāng)時。

線性表和均以單鏈表作存儲結(jié)構(gòu)，且表利用表和表中的結(jié)

點(diǎn)空間構(gòu)成。

注意：單鏈表的長度值和均未顯示存儲。

本題涉及的存儲結(jié)構(gòu)描述如下：

單鏈表存儲結(jié)構(gòu):

typedefstructLnode*LinkList;

typedefstructLnode

(

DataTypedata;

LinkListnext;

}Lnode,*LinkList;

voidmergelinklist(LinkList&lc,LinkListla,LinkListlb)

(

lc=la;

pa=la->next;pb=lb->next;pc=lc;

lc->next=NULL;

while(pa&&pb)

(

pc->next=pa;

pc=pa;

pa=pa->next;

pc->next=pb;

pc=pb;

pb=pb->next;

)

if(pa)pc->next=pa;

delete(lb);

)

15、試完成二叉樹按層次(同一層自左至右)遍歷的算法。

解答：本題涉及的存儲結(jié)構(gòu)描述如下：

樹的二叉鏈表存儲結(jié)構(gòu)：

typedefstrcutbitreenode*bitree;

typedefstructbitreenode{

datatypedata;

bitreeIch,rch;

}bitreenode,*bitree;

隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)：

typedefstructlinkquenode*linkqueptr;

typedefstructlinkquenode{

bitreequelem;

linkqueptrnext;

}linkquenode,*linkqueptr;

typedefstructlinkque{

linkqueptrfront,rear;

}linkque;

voidlayertraverse(bitreebt)

(

cout<<endl〈v”按層次遍歷的結(jié)果如下：”《endl;

initqueue(Q);

if(bt)

(

enterqueueu(Q,bt);

while(!