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

考研大纲/试题:全国|北京交通大学
globalsino.com  



北方交通大学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


其他推荐阅读:

离婚后又陷三角恋 娱乐圈中可恨的三角恋
清华1996年硕士研究生入学考试生物化学试题 清华大学1995年计算机编译原理考研试题
同性恋的成因究竟是什么? 什么叫第一、第二反抗期?
饮食营养与心理健康 自我心理止痛法
人们为何迷恋给未来的自己写信 心理师教你控制购物欲
哮喘对女性性行为有何影响? 你是怎样看待工作的
原发性痛经的治疗 症状很严重的经常痛经如何治疗
北大1997年考研现当代试题 北大1997年考研法理学试题
女人聪明 男人拼命 情感故事:情人的爱跨不过一条内衣的沟
天大99年西方经济学考研试题 天大99硕士入学建筑施工技术及施工组织管理题
专家详解“兔唇”原因
糖尿病会遗传吗 爷爷有糖尿病,我是后备军吗?
女人的15个“行为秘密” 管理老公钱包的3大阶段
管理中绝对经典的18个故事 影响世界的100个管理定律
海外华人婚姻的最大威胁 “网络改变婚姻-网络是制造爱情的工厂
泰山《岱岳沧桑》 泰山《东岳谈兵》
告别头屑的健康全攻略
蚊子到底更爱叮谁? 夏季蚊虫战:宝典三四五!
茶疗验方七则 胖人最适合吃的蔬菜
闯荡社会的50条忠告! 人生最恐惧5件事
 
 
 
【无国界华人网】版权所有。Copyright (C) 2006 GlobalSino, All Rights Reserved