北京交通大學(xué)1999年數(shù)據(jù)結(jié)構(gòu)考研試題

來(lái)源：時(shí)間：2007-06-06 13:36:17

北方交通大學(xué)
1999年碩士學(xué)位研究生入學(xué)考試試題
一．選擇題
1．棧的特點(diǎn)是_A_____,隊(duì)列的特點(diǎn)是_B______,棧和隊(duì)列都是___C_____;若進(jìn)棧序列為1,2,3,4 則__D___不可能是一個(gè)出棧序列（不可能全部進(jìn)棧后在出棧）。若進(jìn)隊(duì)列的序列為1,2,3,4 則___E__試一個(gè)進(jìn)隊(duì)列序列
A,B:①先進(jìn)先出 ②后進(jìn)先出 ③進(jìn)優(yōu)于出 ④出優(yōu)于進(jìn)
C: ①順序存儲(chǔ)的線性結(jié)構(gòu) ②鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu) ③限制存取點(diǎn)的線性結(jié)構(gòu)④限制存取點(diǎn)的非線性結(jié)構(gòu)
D,E: ①3,2,1,4 ②3,2,4,1 ③4,2,3,1
④4,3,2,1 ⑤1,2,3,4 ⑥1,3,2,4
2．要進(jìn)行順序查詢，則線性表___A___；要進(jìn)行折半查詢，則線性表__B____；若表中元素個(gè)數(shù)為n,則順序查找的平均比較次數(shù)為_(kāi)__C___；折半查找的平均比較次數(shù)為_(kāi)__D___。
A,B: ①必須以順序方式存儲(chǔ) ②必須以鏈?zhǔn)椒绞酱鎯?chǔ)；
③既可以以順序方式存儲(chǔ)，也可以鏈?zhǔn)椒绞酱鎯?chǔ)；
④必須以順序方式存儲(chǔ)，且數(shù)據(jù)以按遞增或遞減順序排好；
⑤必須以鏈?zhǔn)椒绞酱鎯?chǔ)，且數(shù)據(jù)以按遞增或遞減順序排好。
C,D: ①n ②n/2 ③n*n ④n*n/2 ⑤log2n ⑥n*log2n ⑦(n 1)/2 ⑧l(xiāng)og2(n 1)
3．序方法有許多種，___A___ 法從未排序的序列中依次取出元素，與以排序序列（初始化為空）中的元素作比較，將其放入以排序序列的正確位置；____B____法從未排序的序列中挑選元素，并將其依次放入以排序序列的一端；交換排序方法是對(duì)序列中的元素進(jìn)行一系列比較，當(dāng)被比較的兩元素逆序時(shí)，進(jìn)行交換；____C____和____D___是基于這類方法的兩種排序方法，而___D___是比___C____效率更高的方法； ____E___發(fā)是基于選擇排序的一種排序方法，是完全二叉樹(shù)結(jié)構(gòu)的一個(gè)重要應(yīng)用。
A,B,C,D,E: ①選擇排序 ②快速排序 ③插入排序 ④起泡排序
⑤歸并排序 ⑥shell排序 ⑦堆排序 ⑧基數(shù)排序
4．完成在雙循環(huán)鏈表結(jié)點(diǎn)P之后插入S的操作是_______；
①p^.next:=s ; s^.priou:=p; p^.next^.priou:=s ; s^.next:=p^.next;
②p^.next^.priou:=s; p^.next:=s; s^.priou:=p; s^.next:=p^.next;
③s^.priou:=p; s^.next:=p^.next; p^.next:=s; p^.next^.priou:=s ;
④s^.priou:=p; s^.next:=p^.next; p^.next^.priou:=s ; p^.next:=s;
5．若串s1=‘ABCDEFG’, S2=’9898 ’ ,S3=’###’,S4=’012345’,執(zhí)行concet(replace(substr(s1,length(s2),length(s3),)),s3),substr(s4,index(s2,’8’),length(s2)))其結(jié)果為_(kāi)_____
①ABC###G0123 ②ABCD###2345 ③ABC###G2345 ④ABC###2345
⑤ABC###G1234 ⑥ABCD###1234 ⑦ABC###01234
6．少用一個(gè)元素空間表示的循環(huán)隊(duì)列用數(shù)組 A[0..M]存其元素值，已知起頭為指針?lè)謩e為front和rear，則隊(duì)列中的元素個(gè)數(shù)可用______表示
①（front—rear） mod m ②（rear—front 1）mod m ③（rear—front）mod m-1
④（rear—front 1）mod m-1 ⑤（rear—front-1）mod m⑥（rear—front m）mod m⑦（front—rear-1） mod m⑧（front—rear 1） mod m-1
6．下列關(guān)于AOE網(wǎng)的敘述中，不正確的是：
①關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間
②任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成
③說(shuō)有的關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成
④某些關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程將會(huì)提前完成
二 .填空
1.起始地址為480,大小為8的塊,其伙伴的起始地址是_______;若塊大小為32,則其伙伴的起始地址是_______.
2.具有n個(gè)葉子結(jié)點(diǎn)的完全二叉樹(shù)的深度為_(kāi)____具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為_(kāi)____;具有n個(gè) 結(jié)點(diǎn)的折半查找的判定樹(shù)的深度為_(kāi)____;具有20個(gè)結(jié)點(diǎn)的平衡二叉樹(shù)的最大深度為_(kāi)____.
3.設(shè)二維樹(shù)組A[-20..30,-30..20], 每個(gè)元素占有4 個(gè)存儲(chǔ)單元, 存儲(chǔ)起始地址為200.如按行優(yōu)先順序存儲(chǔ),則元素 A[25,18]的存儲(chǔ)地址為_(kāi)___;如按列優(yōu)先順序存儲(chǔ),則元素A[-18,-25]的存儲(chǔ)地址為_(kāi)___.
4.已知如下程序段
for I:= n downto 1 do {語(yǔ)句1}
begin
x:=x 1； {語(yǔ)句2}
for j:=n downto I do {語(yǔ)句3}
y:=y 1; {語(yǔ)句4}
end.
語(yǔ)句1執(zhí)行的頻度為_(kāi)_____；語(yǔ)句2執(zhí)行的頻度為_(kāi)_____；語(yǔ)句3執(zhí)行的頻度為_(kāi)_____；語(yǔ)句4執(zhí)行的頻度為_(kāi)_____；
5．127階B-樹(shù)中每個(gè)結(jié)點(diǎn)最多有____個(gè)關(guān)鍵字；除根結(jié)點(diǎn)外所有非終端結(jié)點(diǎn)至少有____棵子樹(shù)；65階B 除根結(jié)點(diǎn)外所有結(jié)點(diǎn)至少有____個(gè)關(guān)鍵字；最多有____棵子樹(shù)；
6．無(wú)用單元是指_____,例____
三．下面的算法完成圖的深度優(yōu)先遍歷，請(qǐng)?zhí)羁?br> program graph_traver;
const nl=maxnode_number;
type
vtxptr=1..nl;
vtxptr0=0..nl;
arcptr=^acrnode;
arcnode =record
vexi ,vexj:vtxptr;
nexti,nextj:arcptr;
end;
vexnode =record
vexdata:char;
firstin:arcptr;
firstout:arcptr
end;
graph=array[vtxptr0] of vexnode ;
var
ga:graph
vistied:array[vtxptr] of bolean ;
n:integer;

func order (g:graph;v:char); txptr;
_______; i:=n;
while g[i].vexdata<>v do i:=i-1;
order:=i;
endf；

proc creat （g:graph);
readln(n,e);
for i:= 1 to n do
[ readln(g[i].vexdata);
g[i].firstin :=nil ; g[i].firstout:=nil;]
for k:= 1 to e do
[readln (vt,vh);
I:=order (g,vt); j:=order (g,vh); new (p); p^,vexi:=I ; p^.vexj:=j
P^.nextj:=____B____;___C____:=p;
P^.nexti:=____D____;___E____:=p;]
ENDP.
Func firstadj(g:fraph:v:char):vtxptr0;
I:=order(g,v);p:=g[I].firstout;
If p<>nil then firstadj:=______else firstadj:=0;
Endf;
Func nextadj(g:fraph;v:char:w:char):vtxptr0;
I:=order(g,v);j:=order(g,w);
P:=______;
While(p<>nil ) and(p^.vexj<>j)do _____;
If _____and_____then nextadj:=p^.nexti^.vexj else nextadj:=0;
Endf;
Proc dfs(g:graph;v0:char);
Write(v0:2);visited[order(g,v0)]:true;
W:=_____
While w<>0 do
[ if _____ then dfs(g,g[w].vexdata);
w:=______;]
endp;
proc traver(g:graph);
for I;=1 to n do visited[I]:=false;
for I:=1 to n do
if not visitec[I]then dfs(g,g[I].vexdata);
endp;
begin
creat(ga);
traver(ga);
end.
四對(duì) 輸入文件（101，51，19，61，3，71，31，17，19，100，55，20，9，30，50，6，90）。當(dāng)k=6時(shí)，使用置換-選擇算法，寫出建立的初始敗者及生成的歸并段；
五以孩子兄弟鏈表為存儲(chǔ)結(jié)構(gòu)，請(qǐng)?jiān)O(shè)計(jì)遞歸和非遞歸算法求樹(shù)的深度。{書(shū)寫算法請(qǐng)用類pascal語(yǔ)言}

結(jié)束

特別聲明：①凡本網(wǎng)注明稿件來(lái)源為"原創(chuàng)"的，轉(zhuǎn)載必須注明"稿件來(lái)源：育路網(wǎng)"，違者將依法追究責(zé)任；

②部分稿件來(lái)源于網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系我們溝通解決。