




下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
數(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.索引存?。籨.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的完全二叉樹至少有_2、_個(gè)結(jié)點(diǎn),至多有_2<1____個(gè)結(jié)點(diǎn),若按自上而下,
從左到右的次序給結(jié)點(diǎn)編號(hào)(從1開始),則編號(hào)最小的葉子結(jié)點(diǎn)的編號(hào)是_2卜」1_。
8、現(xiàn)有中序遍歷二叉樹的結(jié)果為羯則有種不同形態(tài)的二叉樹可以得到這一遍歷
結(jié)果。
9、有一個(gè)有序表為{1,3,9,12,32,41,45,62,75,77,82,95,100),當(dāng)二分查找
值為82的元素時(shí),需要經(jīng)過工次比較就找到。
10、在線索二叉樹中,結(jié)點(diǎn)P沒有左子樹的充要條件是-->蛔=1_。
11s數(shù)據(jù)集{4,5,6,730,1238}為結(jié)點(diǎn)權(quán)值構(gòu)造Hufftnan樹,請(qǐng)給出構(gòu)造所得的Huffman
樹,并求其帶權(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的樹中有m個(gè)度為1的結(jié)點(diǎn),m個(gè)度為2的結(jié)點(diǎn),…,眩個(gè)度為k的
結(jié)點(diǎn),問該樹中有多少個(gè)葉子結(jié)點(diǎn)?
解答:設(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è)一棵二叉樹的先序序列是EBADCFHGIKJ,中序序列是ABCDEFGHIJK。請(qǐng)畫出
該二叉樹。
和已知序列對(duì)應(yīng)的二叉樹是:
14、設(shè)線性表,試寫一按下列規(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、試完成二叉樹按層次(同一層自左至右)遍歷的算法。
解答:本題涉及的存儲(chǔ)結(jié)構(gòu)描述如下:
樹的二叉鏈表存儲(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(!
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 地產(chǎn)抵押合同二零二五年
- 簡(jiǎn)單個(gè)人租房的協(xié)議書
- 二零二五版餐廳承包協(xié)議書范文
- 初中班級(jí)管理工作計(jì)劃
- 2025年三年級(jí)上冊(cè)班主任培訓(xùn)與發(fā)展計(jì)劃
- 一年級(jí)下學(xué)期語文自主學(xué)習(xí)能力培養(yǎng)計(jì)劃
- 法律顧問服務(wù)協(xié)議
- 舞蹈教學(xué)工作坊活動(dòng)安排
- 建筑企業(yè)用工勞務(wù)合同二零二五年
- 房屋裝修合同樣本
- 2025年各地低空經(jīng)濟(jì)政策匯編
- 希沃白板5考題及答案
- 邢臺(tái)2025年河北邢臺(tái)市高層次人才引進(jìn)1025人筆試歷年參考題庫(kù)附帶答案詳解
- 第三單元 圓柱與圓錐 單元測(cè)試(含答案)2024-2025學(xué)年六年級(jí)下冊(cè)數(shù)學(xué)人教版
- XX鄉(xiāng)鎮(zhèn)履職事項(xiàng)清單表(1356項(xiàng))
- 地鐵保安服務(wù)投標(biāo)方案(技術(shù)方案)
- 《企業(yè)研發(fā)費(fèi)用稅前加計(jì)扣除政策解讀與應(yīng)用課件》
- 2025年湖北國(guó)土資源職業(yè)學(xué)院?jiǎn)握新殬I(yè)技能測(cè)試題庫(kù)及答案一套
- 七年級(jí)數(shù)學(xué)下冊(cè) 第8章 單元測(cè)試卷(蘇科版 2025年春)
- 2024年煤礦安全管理人員考試試題庫(kù)(含答案)
- 小學(xué)科學(xué)實(shí)驗(yàn)教學(xué)與現(xiàn)代教育技術(shù)融合研究
評(píng)論
0/150
提交評(píng)論