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

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



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


其他推荐阅读:

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