南京邮电大学考研数据结构(811)00-09年真题和答案 .pdfVIP

南京邮电大学2000年硕士研究生入学考试

数据结构试题

一、完成下列各题（每小题6分，共18分）

1.设n是偶数，试计算运行下列程序段后m的值并给出该程序段的时间复杂度。

m:=0；

FORi:=1TOnDO

FORj:=2*iTOnDO

m：=m+1；

2.已知字符串‘cddcdececdea’,过算每介字符的next和nextval函数的值.

3.给出冒泡排序和快速排序的最好情况,平均情况和最坏情况下的时间复杂度。

二、完成下列各题：（每小题8分，共24分）

1、设有下图所示的有向图，给出其邻接矩阵和强连通分量。

621

53

4

2、设有3阶B-树如下图所示，

（1)从该B-树上依次插入关键字33，97，画出两次插入后的B-树；

（2)从（1）得到的B-树上依次删除66，43，画出两次删除后的B-树；

43

265560

16354148576668

1

现有8个初始游程，每个游程的第一、二个记录的关键字分别为：

旅程12345678

记录

一1182197124519

二1533251416184823

（1）画出据此构造的败选择树

（2）画出输出一个记录后的败方树

三、阅读下列二叉树算法,每个结点三个域：lchild,element,rchild。(10分)

(1)X(p)对以p为根的二叉树执行什么功能?

(2)以下图所示的二叉树调用此算法，则X（p）的执行结果是什么?

(3)执行中，栈s中元素个数最多时为多少?给出该时栈中元素的情况。

P

A

BE

CDFG

H

voidX(BinTree*t)

{structStacks;

BinTnode*q

Push(s,NUL1)

While(*p)

{q=(*p)-lchild

(*p)-1child=(*p)-rchild

(*p)-rchild=q

If((*p)-lchild)Push(s,(*p)-1child);

If((*p)-rchild)Push(s,(*p)-rchild)；

2

else(*p)=Pop(s)

}

}

四、阅读下列要求每对顶点之间的最短路径的Floyd算法。(16分)

（1)若对下图所示的有向图执行此算法，写出对k为1到n的各步中，二维数组

a和path的值。

（2）试设计一个算法,打印每对顶点ij（1=i,j=n）之间的最短路径长度

(a[i,j]的值)及其对应的那条路径（路径上的顶点序列）。

33

12

CONSTn={usersuppliedinteger}

TYPEgraph=ARRAY[1..n,1.