




下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
數(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(!
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 北京2025年北京市大興區(qū)第一批事業(yè)單位招聘153人筆試歷年參考題庫附帶答案詳解
- 麗江云南麗江市婦女兒童醫(yī)院第一批編外備案制人員招聘6人筆試歷年參考題庫附帶答案詳解
- 未出資股權(quán)轉(zhuǎn)讓協(xié)議范例二零二五年
- 樁基工程勞務(wù)承包合同參考二零二五年
- 采礦權(quán)抵押協(xié)議合同書范例
- 微信公眾號運(yùn)營合同范例
- 火鍋店合伙人協(xié)議書二零二五年
- 煤炭公司股權(quán)轉(zhuǎn)讓協(xié)議二零二五年
- 2025分成合同樣本:網(wǎng)絡(luò)課程推廣協(xié)議書(比例分成)、委托生產(chǎn)管理合同(利潤分?jǐn)偅?、利潤共享協(xié)議書
- 2025勞務(wù)派遣合同(合同范本)
- 2025年各地低空經(jīng)濟(jì)政策匯編
- 希沃白板5考題及答案
- 邢臺2025年河北邢臺市高層次人才引進(jìn)1025人筆試歷年參考題庫附帶答案詳解
- 第三單元 圓柱與圓錐 單元測試(含答案)2024-2025學(xué)年六年級下冊數(shù)學(xué)人教版
- XX鄉(xiāng)鎮(zhèn)履職事項(xiàng)清單表(1356項(xiàng))
- 2021年同等學(xué)力申碩《臨床醫(yī)學(xué)》試題真題及答案
- 地鐵保安服務(wù)投標(biāo)方案(技術(shù)方案)
- 《企業(yè)研發(fā)費(fèi)用稅前加計扣除政策解讀與應(yīng)用課件》
- 2025年湖北國土資源職業(yè)學(xué)院單招職業(yè)技能測試題庫及答案一套
- 七年級數(shù)學(xué)下冊 第8章 單元測試卷(蘇科版 2025年春)
- 2024年煤礦安全管理人員考試試題庫(含答案)
評論
0/150
提交評論