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

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

北方交通大學2000年試題
一簡述下列概念
1哈希樹 2完全二叉樹 3最有二叉樹 4平衡二叉樹
二選擇題
1 以下與數據的存儲結構無關的術語是----
a 循環(huán)隊列 b 鏈表 c 哈希表 d 棧
2 比較次數與排序的初始狀態(tài)無關的排序方法是----
a 直接插入排序 b起泡排序 c 快速排序 d 簡單選擇排序
3 穩(wěn)定的排序方法是—
a 直接插入排序和快速排序b 折半插入排序和起泡排序
c簡單選擇排序和四路歸并排序 d 樹形選擇排序和shell排序
4 既希望較快的查找又便于線性表動態(tài)變化的查找方法是
a 順序查找 b 折半查找 c 索引順序查找 d 哈希法查找
5 對n個記錄的線性表進行快速排序為減少算法的遞歸深度，以下敘述正確的是—
a 每次區(qū)分后，先處理較短的部分 b每次區(qū)分后，先處理較長的部分
c 與算法每次分區(qū)后的處理順序無關d 以上三者都不對
三下面使用類pascal語言些的對二叉樹進行操作的算法，請仔細閱讀
type
pointer=^tnodetp;
tnodetp=Record
data:char;
llink,rlink:pointer
End;
Linkstack:=^linknodet;
Linknodet=record
Data:pointer’
Next;linkstack
End;
Proc unknown (var t:pointer);
Var
P,temp;poineter;
Begin
P:=t;
if p<> nil then
[ temp;=p↑.llink
p↑.llink:=p↑.rlinkp;
p^.rlink:=temp;
unknown(p^.llink);
unknown(p^.rlink);
]
end;
(1) 指出該算法完成了什么功能
(2）用棧將以上算法改為非遞歸算法unknown1,其中有若干語句或條件空缺請在空缺
處填寫上適當的語句或條件
proc inistack(var s:linkstack);
( );s^.next:=nil;
endp;
func empty (s:linkstack):boolean;
if ( )then empty:=true else empty:=false
endf;
func gettop(s:linkstack):pointer;
gerrop:=( )
endf;
func pop(var s:linkstack)：pointer;
var
p:linkstack;
pop:s^.next^.data;
p:=s^.next;(　　�。�；（　　　）
endf;
proc push (var s:linkstack;x:pointer);
var
p:linkstack;
new(p);
p^.data:=x;( );s^.next:=p;
endp;
proc unknown(var t:pointer);
var
p.temp:pointer;
finish:boolean;
begin
inistack(s);
finish:=false;
p:=t;
repeat
while p<> nil do
[temp:=p^.llink;
p^.llink:=p^.rlink;
p^.rlink:=temp;
( );
p;=p^,llink;
];
if ( ) then [p:=gettop(s);temp;=pop(s);]
else ( )
until ( )
end;
四以下程序的功能是利用對進行排序。請在空白處填上適當語句，是程序完整。
procedure sift(var r:arr;k,m:inerger);
var
i,j,x:integer; t:rec; finished:boolean;
begin
i:=k;( ); x:=r[i].key; ( );
t:=r[k];
while (j<=m) and not finished do
begin
if (j<=m) and ( ) then j:=j 1;
if x<=r[j].key then finished:=true
else begin ( ) ;( ); ( )end;
end;
( )
end;
procedure heapsort (var t:arr);
var
i;inyeger;x:rec;
begin
for i:=n div 2 downto 1 do ( );
for i;=n downto 2 do
begin
x:=r[i];( ); r[i]:=x;
( )
end;
end;
五設有向圖G=<V,E>,其中V={V1,V2,V3,V4},E={<V1,V2>,<V1,V4>,<V2,V1>,
<V2,V3>,<V3,V4>,<V4,V1>,<V4,V2>}試按下列要求畫出G的存儲結構圖。
（1）鄰接矩陣（2）鄰接表（3）逆鄰接表
六設民航公有一個自動預定飛機票的系統(tǒng)，該系統(tǒng)中有一張用雙重鏈表示的乘客表，
表中結點按乘客姓氏的字母序相連。例如，下面是張某個時刻的乘客表。
試為該系統(tǒng)寫出一個當任意乘客要訂票時修改乘客表的課表的算法。
序號 data Llink Rlink
1 liu 6 5
2 chan 4 9
3 wang 5 7
4 bao 0 2
5 mai 1 3
6 dong 8 1
7 xi 3 0
8 deng 9 6
9 zhang 2 8

結束

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

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