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

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

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

结束

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

②部分稿件来源于网络，如有侵权，请联系我们沟通解决。