西北工業(yè)大學(xué)考研真題-西工業(yè)北大學(xué)考研真題-西北工業(yè)大學(xué)1999年數(shù)據(jù)結(jié)構(gòu)試題

朽木易折，金石可鏤。千里之行，始于足下。第頁/共頁西北工業(yè)大學(xué)99年數(shù)據(jù)結(jié)構(gòu)試題

LBHIDDEN[0]LBHIDDEN西北工業(yè)大學(xué)99考研題一．（15分）請給出下列概念或術(shù)語的解釋。

1．廣義表

2．平衡因子

3．平均尋找長度（ASL）

4．伙伴空間

5．AOE-網(wǎng)的關(guān)鍵路徑

二．（8分）簡述直接插入排序，容易挑選排序，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ì)滿的判斷條件，并且分析一下該條件對隊(duì)列實(shí)際存儲(chǔ)空間大小的影響，倘若為了不損失存儲(chǔ)空間，你如何改進(jìn)循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿的判斷條件？

四．（10分）試比較順序文件，索引非順序文件，索引順序文件，散列文件的存儲(chǔ)代價(jià)，檢索，插入，刪除記錄時(shí)的優(yōu)點(diǎn)和缺點(diǎn)。

五．（10分）一個(gè)深度為L的滿K*樹有以下性質(zhì)：第L層的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上么個(gè)結(jié)點(diǎn)都有K棵非空子樹，倘若按層次順序從1開始對所有結(jié)點(diǎn)舉行編號，求：

1．各層的結(jié)點(diǎn)的數(shù)目是多少？

2．編號為n的結(jié)點(diǎn)的雙親結(jié)點(diǎn)（若存在）的編號是多少？

3．編號為n的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)（若存在）的編號是多少？

4．編號為n的結(jié)點(diǎn)有右兄弟的條件是什么？倘若有，其右兄弟的編號是多少？

請給出計(jì)算和推導(dǎo)過程。

六．（14分）閱讀下列算法的類PASCAL描述，按照算法的要求，對相應(yīng)的空格處寫出準(zhǔn)確合理的語句。

1．后序遍歷二*樹的非遞歸算法，bt是二*樹的根，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)先級別的函數(shù)，operate(opnd1,oper,opnd2)為兩操作數(shù)的運(yùn)算結(jié)果。（#表示運(yùn)算起始和終止符號）

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分）簡述無向圖和有向圖有哪幾種存儲(chǔ)結(jié)構(gòu)，并說明各種結(jié)構(gòu)在圖的不同操作（圖的遍歷，有向圖的拓?fù)渑判虻龋┲杏惺裁礃拥膬?yōu)越性？

八、（15分）遍歷一棵二*樹的中序序列和后序序列分離為，中序BFDGAEHC，后序FGDBHCA，寫出這棵二*樹的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，已知一棵二*樹的中序序列和后序序列分離由INO[1..n]和POST[1..n]數(shù)據(jù)存放，并且假定沒有數(shù)據(jù)域值相同的結(jié)點(diǎn)，證實(shí)可由此生成一棵唯一的二*樹，并寫出生成的算法。

九、（10分）考慮邊界標(biāo)志法的兩種策略（最佳適配和首次適配）：

1．?dāng)?shù)據(jù)結(jié)構(gòu)的主要區(qū)別是什么？

2．分配算法的主要區(qū)別是什么？

3．回收算法的主要區(qū)別是什么？

要求寫出相應(yīng)的結(jié)構(gòu)和核心算法。