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

來源：時(shí)間：2007-06-06 13:36:22

北方交通大學(xué)2000年試題
一簡(jiǎn)述下列概念
1哈希樹 2完全二叉樹 3最有二叉樹 4平衡二叉樹
二選擇題
1 以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)的術(shù)語(yǔ)是----
a 循環(huán)隊(duì)列 b 鏈表 c 哈希表 d 棧
2 比較次數(shù)與排序的初始狀態(tài)無關(guān)的排序方法是----
a 直接插入排序 b起泡排序 c 快速排序 d 簡(jiǎn)單選擇排序
3 穩(wěn)定的排序方法是—
a 直接插入排序和快速排序b 折半插入排序和起泡排序
c簡(jiǎn)單選擇排序和四路歸并排序 d 樹形選擇排序和shell排序
4 既希望較快的查找又便于線性表動(dòng)態(tài)變化的查找方法是
a 順序查找 b 折半查找 c 索引順序查找 d 哈希法查找
5 對(duì)n個(gè)記錄的線性表進(jìn)行快速排序?yàn)闇p少算法的遞歸深度，以下敘述正確的是—
a 每次區(qū)分后，先處理較短的部分 b每次區(qū)分后，先處理較長(zhǎng)的部分
c 與算法每次分區(qū)后的處理順序無關(guān)d 以上三者都不對(duì)
三下面使用類pascal語(yǔ)言些的對(duì)二叉樹進(jìn)行操作的算法，請(qǐng)仔細(xì)閱讀
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,其中有若干語(yǔ)句或條件空缺請(qǐng)?jiān)诳杖?br>處填寫上適當(dāng)?shù)恼Z(yǔ)句或條件
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;
四以下程序的功能是利用對(duì)進(jìn)行排序。請(qǐng)?jiān)诳瞻滋幪钌线m當(dāng)語(yǔ)句，是程序完整。
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;
五設(shè)有向圖G=<V,E>,其中V={V1,V2,V3,V4},E={<V1,V2>,<V1,V4>,<V2,V1>,
<V2,V3>,<V3,V4>,<V4,V1>,<V4,V2>}試按下列要求畫出G的存儲(chǔ)結(jié)構(gòu)圖。
（1）鄰接矩陣（2）鄰接表（3）逆鄰接表
六設(shè)民航公有一個(gè)自動(dòng)預(yù)定飛機(jī)票的系統(tǒng)，該系統(tǒng)中有一張用雙重鏈表示的乘客表，
表中結(jié)點(diǎn)按乘客姓氏的字母序相連。例如，下面是張某個(gè)時(shí)刻的乘客表。
試為該系統(tǒng)寫出一個(gè)當(dāng)任意乘客要訂票時(shí)修改乘客表的課表的算法。
序號(hào) 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

結(jié)束

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

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