北京交通大学2000年数据结构考研试题

来源：时间：2007-06-06 13:36:22

北方交通大学2000年试题
一简述下列概念
1哈希树 2完全二叉树 3最有二叉树 4平衡二叉树
二选择题
1 以下与数据的存储结构无关的术语是----
a 循环队列 b 链表 c 哈希表 d 栈
2 比较次数与排序的初始状态无关的排序方法是----
a 直接插入排序 b起泡排序 c 快速排序 d 简单选择排序
3 稳定的排序方法是—
a 直接插入排序和快速排序b 折半插入排序和起泡排序
c简单选择排序和四路归并排序 d 树形选择排序和shell排序
4 既希望较快的查找又便于线性表动态变化的查找方法是
a 顺序查找 b 折半查找 c 索引顺序查找 d 哈希法查找
5 对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是—
a 每次区分后，先处理较短的部分 b每次区分后，先处理较长的部分
c 与算法每次分区后的处理顺序无关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）逆邻接表
六设民航公有一个自动预定飞机票的系统，该系统中有一张用双重链表示的乘客表，
表中结点按乘客姓氏的字母序相连。例如，下面是张某个时刻的乘客表。
试为该系统写出一个当任意乘客要订票时修改乘客表的课表的算法。
序号 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

结束

特别声明：①凡本网注明稿件来源为"原创"的，转载必须注明"稿件来源：育路网"，违者将依法追究责任；

②部分稿件来源于网络，如有侵权，请亚洲2019AV无码网站在线_波多野结衣免费一区视频_国产IGAO视频网在线观看_国产人妖乱国产精品人妖沟通解决。