北京交通大學1999年數據結構考研試題

來源：時間：2007-06-06 13:36:17

北方交通大學
1999年碩士學位研究生入學考試試題
一．選擇題
1．棧的特點是_A_____,隊列的特點是_B______,棧和隊列都是___C_____;若進棧序列為1,2,3,4 則__D___不可能是一個出棧序列（不可能全部進棧后在出棧）。若進隊列的序列為1,2,3,4 則___E__試一個進隊列序列
A,B:①先進先出 ②后進先出 ③進優于出 ④出優于進
C: ①順序存儲的線性結構 ②鏈式存儲的線性結構 ③限制存取點的線性結構④限制存取點的非線性結構
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．要進行順序查詢，則線性表___A___；要進行折半查詢，則線性表__B____；若表中元素個數為n,則順序查找的平均比較次數為___C___；折半查找的平均比較次數為___D___。
A,B: ①必須以順序方式存儲 ②必須以鏈式方式存儲；
③既可以以順序方式存儲，也可以鏈式方式存儲；
④必須以順序方式存儲，且數據以按遞增或遞減順序排好；
⑤必須以鏈式方式存儲，且數據以按遞增或遞減順序排好。
C,D: ①n ②n/2 ③n*n ④n*n/2 ⑤log2n ⑥n*log2n ⑦(n 1)/2 ⑧log2(n 1)
3．序方法有許多種，___A___ 法從未排序的序列中依次取出元素，與以排序序列（初始化為空）中的元素作比較，將其放入以排序序列的正確位置；____B____法從未排序的序列中挑選元素，并將其依次放入以排序序列的一端；交換排序方法是對序列中的元素進行一系列比較，當被比較的兩元素逆序時，進行交換；____C____和____D___是基于這類方法的兩種排序方法，而___D___是比___C____效率更高的方法； ____E___發是基于選擇排序的一種排序方法，是完全二叉樹結構的一個重要應用。
A,B,C,D,E: ①選擇排序 ②快速排序 ③插入排序 ④起泡排序
⑤歸并排序 ⑥shell排序 ⑦堆排序 ⑧基數排序
4．完成在雙循環鏈表結點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’,執行concet(replace(substr(s1,length(s2),length(s3),)),s3),substr(s4,index(s2,’8’),length(s2)))其結果為______
①ABC###G0123 ②ABCD###2345 ③ABC###G2345 ④ABC###2345
⑤ABC###G1234 ⑥ABCD###1234 ⑦ABC###01234
6．少用一個元素空間表示的循環隊列用數組 A[0..M]存其元素值，已知起頭為指針分別為front和rear，則隊列中的元素個數可用______表示
①（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．下列關于AOE網的敘述中，不正確的是：
①關鍵活動不按期完成就會影響整個工程的完成時間
②任何一個關鍵活動提前完成，那么整個工程將會提前完成
③說有的關鍵活動提前完成，那么整個工程將會提前完成
④某些關鍵活動提前完成，那么整個工程將會提前完成
二 .填空
1.起始地址為480,大小為8的塊,其伙伴的起始地址是_______;若塊大小為32,則其伙伴的起始地址是_______.
2.具有n個葉子結點的完全二叉樹的深度為_____具有n個結點的完全二叉樹的深度為_____;具有n個結點的折半查找的判定樹的深度為_____;具有20個結點的平衡二叉樹的最大深度為_____.
3.設二維樹組A[-20..30,-30..20], 每個元素占有4 個存儲單元, 存儲起始地址為200.如按行優先順序存儲,則元素 A[25,18]的存儲地址為____;如按列優先順序存儲,則元素A[-18,-25]的存儲地址為____.
4.已知如下程序段
for I:= n downto 1 do {語句1}
begin
x:=x 1； {語句2}
for j:=n downto I do {語句3}
y:=y 1; {語句4}
end.
語句1執行的頻度為______；語句2執行的頻度為______；語句3執行的頻度為______；語句4執行的頻度為______；
5．127階B-樹中每個結點最多有____個關鍵字；除根結點外所有非終端結點至少有____棵子樹；65階B 除根結點外所有結點至少有____個關鍵字；最多有____棵子樹；
6．無用單元是指_____,例____
三．下面的算法完成圖的深度優先遍歷，請填空
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.
四對輸入文件（101，51，19，61，3，71，31，17，19，100，55，20，9，30，50，6，90）。當k=6時，使用置換-選擇算法，寫出建立的初始敗者及生成的歸并段；
五以孩子兄弟鏈表為存儲結構，請設計遞歸和非遞歸算法求樹的深度。{書寫算法請用類pascal語言}

結束

特別聲明：①凡本網注明稿件來源為"原創"的，轉載必須注明"稿件來源：育路網"，違者將依法追究責任；

②部分稿件來源于網絡，如有侵權，請聯系我們溝通解決。