大學(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ù)值計(jì)算州翡設(shè)計(jì)I'碉中計(jì)算機(jī)的a以及他們之間的包和運(yùn)算的

刮

a操作對(duì)象；b.計(jì)算方法；c邏輯存儲(chǔ)；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.存儲(chǔ)；d關(guān)系

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

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

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

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

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

5、一個(gè)隊(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))))的長(zhǎng)度是3,深度是」________。

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

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

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

結(jié)果。

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

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

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

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

樹(shù)，并求其帶權(quán)路徑長(zhǎng)度。

解答：

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的樹(shù)中有m個(gè)度為1的結(jié)點(diǎn)，m個(gè)度為2的結(jié)點(diǎn)，…，眩個(gè)度為k的

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

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

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

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

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

結(jié)點(diǎn)中，除根外，每個(gè)結(jié)點(diǎn)都有一個(gè)分支進(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è)一棵二叉樹(shù)的先序序列是EBADCFHGIKJ,中序序列是ABCDEFGHIJK。請(qǐng)畫(huà)出

該二叉樹(shù)。

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

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

使得

當(dāng)時(shí);

或者當(dāng)時(shí)。

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

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

注意：?jiǎn)捂湵淼拈L(zhǎng)度值和均未顯示存儲(chǔ)。

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

單鏈表存儲(chǔ)結(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、試完成二叉樹(shù)按層次(同一層自左至右)遍歷的算法。

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

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

typedefstrcutbitreenode*bitree;

typedefstructbitreenode{

datatypedata;

bitreeIch,rch;

}bitreenode,*bitree;

隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(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(!