下載本文檔
版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
朽木易折,金石可鏤。千里之行,始于足下。第頁(yè)/共頁(yè)西北工業(yè)大學(xué)99年數(shù)據(jù)結(jié)構(gòu)試題
LBHIDDEN[0]LBHIDDEN西北工業(yè)大學(xué)99考研題一.(15分)請(qǐng)給出下列概念或術(shù)語(yǔ)的解釋。
1.廣義表
2.平衡因子
3.平均尋找長(zhǎng)度(ASL)
4.伙伴空間
5.AOE-網(wǎng)的關(guān)鍵路徑
二.(8分)簡(jiǎn)述直接插入排序,容易挑選排序,2-路歸并排序的基本思想以及在時(shí)光復(fù)雜度和排序穩(wěn)定性上的差別。
三.(8分)一個(gè)循環(huán)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)描述如下:
TYPEseuueuetp=RECORD
elem:ARRAY[1。。maxsize]OFelemtp;
Front,rear:0。。maxize;
END;
給出循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿(mǎn)的判斷條件,并且分析一下該條件對(duì)隊(duì)列實(shí)際存儲(chǔ)空間大小的影響,倘若為了不損失存儲(chǔ)空間,你如何改進(jìn)循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿(mǎn)的判斷條件?
四.(10分)試比較順序文件,索引非順序文件,索引順序文件,散列文件的存儲(chǔ)代價(jià),檢索,插入,刪除記錄時(shí)的優(yōu)點(diǎn)和缺點(diǎn)。
五.(10分)一個(gè)深度為L(zhǎng)的滿(mǎn)K*樹(shù)有以下性質(zhì):第L層的結(jié)點(diǎn)都是葉子結(jié)點(diǎn),其余各層上么個(gè)結(jié)點(diǎn)都有K棵非空子樹(shù),倘若按層次順序從1開(kāi)始對(duì)所有結(jié)點(diǎn)舉行編號(hào),求:
1.各層的結(jié)點(diǎn)的數(shù)目是多少?
2.編號(hào)為n的結(jié)點(diǎn)的雙親結(jié)點(diǎn)(若存在)的編號(hào)是多少?
3.編號(hào)為n的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)(若存在)的編號(hào)是多少?
4.編號(hào)為n的結(jié)點(diǎn)有右兄弟的條件是什么?倘若有,其右兄弟的編號(hào)是多少?
請(qǐng)給出計(jì)算和推導(dǎo)過(guò)程。
六.(14分)閱讀下列算法的類(lèi)PASCAL描述,按照算法的要求,對(duì)相應(yīng)的空格處寫(xiě)出準(zhǔn)確合理的語(yǔ)句。
1.后序遍歷二*樹(shù)的非遞歸算法,bt是二*樹(shù)的根,S是一個(gè)棧,maxsize是棧的最大容量。
TYPEbitreptr=^bnodetp;
bitreptr=RECORD
data:datatype;
lchild,rchild:bitreptr
END;
TYPEstacktyp=RECORD
data:ARRAY[1…maxsize]OFbitreptr;
top:0…maxsize;
END;
PROCEDUREposterorder(be:bitreptr);
BEGIN
S.Top:=0;p:=bt;
REPEAT
WHILEp<>NILDO
BEGIN
S.top:=s.top+1;
IFS.top>maxsizeTHENstackfull
ELSEBEGINS.data[S.top]:=p
(1)_____________________;
END
END;
IFS.data[top]^.rchild<>NILTHEN
(2)_________________
ELSEBEGIN
REPEAT
Write(S.data[top]^.data);
UNTILS.top=0orS.data[top]^.rchild<>S.data[S.top+1];
IFS.data[top]^.rchild<>S.data[S.top+1];
THEN(3)_________________;
UNTIL(4)______________________;
END
2.算術(shù)表達(dá)式求值的流程,其中OPTR為算術(shù)符棧,OPND2為操作數(shù)棧,precede(oper1,oper2)是比較運(yùn)算符優(yōu)先級(jí)別的函數(shù),operate(opnd1,oper,opnd2)為兩操作數(shù)的運(yùn)算結(jié)果。(#表示運(yùn)算起始和終止符號(hào))
FUNCTION
exp_reduced:operandtype;
INITSTACK(OPTR);PUsH(OPTR"#"INITSTACK(OPND);read(w)
WHILENOT((W='#")and(GETTOP(OPTR)='#'))DO
IFwNOTinopthenPUSH(OPND,w);
ELSECASEprecede(GETTOP(OPTR),w)of
'<':[(1)
;read(w0;);
'=':[(2)
;read(w);];
'>':[theta-POP(OPTR);b:=POP(OPND);a:=POP(OPND);(3)
;]
ENDC;
RETURN(GETTOP(OPND);
ENDF;
七、(10分)簡(jiǎn)述無(wú)向圖和有向圖有哪幾種存儲(chǔ)結(jié)構(gòu),并說(shuō)明各種結(jié)構(gòu)在圖的不同操作(圖的遍歷,有向圖的拓?fù)渑判虻龋┲杏惺裁礃拥膬?yōu)越性?
八、(15分)遍歷一棵二*樹(shù)的中序序列和后序序列分離為,中序BFDGAEHC,后序FGDBHCA,寫(xiě)出這棵二*樹(shù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu),已知一棵二*樹(shù)的中序序列和后序序列分離由INO[1..n]和POST[1..n]數(shù)據(jù)存放,并且假定沒(méi)有數(shù)據(jù)域值相同的結(jié)點(diǎn),證實(shí)可由此生成一棵唯一的二*樹(shù),并寫(xiě)出生成的算法。
九、(10分)考慮邊界標(biāo)志法的兩種策略(最佳適配和首次適配):
1.?dāng)?shù)據(jù)結(jié)構(gòu)的主要區(qū)別是什么?
2.分配算法的主要區(qū)別是什么?
3.回收算法的主要區(qū)別是什么?
要求寫(xiě)出相應(yīng)的結(jié)構(gòu)和核心算法。
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 《政府運(yùn)營(yíng)管理》課件
- HWREP刷適性改進(jìn)劑相關(guān)項(xiàng)目投資計(jì)劃書(shū)范本
- 酒水供應(yīng)合同三篇
- 《保險(xiǎn)監(jiān)督管理》課件
- 《認(rèn)識(shí)簡(jiǎn)單路線(xiàn)圖說(shuō)》課件
- 《敬畏自然》課件
- 《解讀食品安全法》課件
- 八年級(jí)物理阿基米德原理課件
- 行車(chē)整改報(bào)告范文樣板
- 山東選人報(bào)告范文
- 承插型盤(pán)扣式支架施工技術(shù)總結(jié)
- 震雄注塑機(jī)Ai_01操作說(shuō)明書(shū)(中文)
- 四年級(jí)上學(xué)期家長(zhǎng)會(huì)PPT課件.ppt
- 電話(huà)機(jī)和對(duì)講機(jī)裝配實(shí)習(xí)報(bào)告
- 廣州美術(shù)學(xué)院關(guān)于本科畢業(yè)論文、畢業(yè)創(chuàng)作(設(shè)計(jì))工作的若干規(guī)定
- 壓力管道元件產(chǎn)品合格證
- 1000以?xún)?nèi)自然數(shù)數(shù)數(shù)表
- 10KV變電站供電系統(tǒng)設(shè)計(jì)
- 起重機(jī)傳動(dòng)裝置的設(shè)計(jì)
- 15立方米的液氯儲(chǔ)罐課程設(shè)計(jì)說(shuō)明書(shū)
- 發(fā)現(xiàn)所授薪律師及律師助理管理辦法
評(píng)論
0/150
提交評(píng)論