南京邮电大学2000年硕士研究生入学考试
数据结构试题
一、完成下列各题（每小题6分，共18分）
1.设n是偶数，试计算运行下列程序段后m的值并给出该程序段的时间复杂度。m:=0；
FOR i:=1 TO n DO
FOR  j:=2*i TO n DO
m：=m+1；
2.已知字符串‘cddcdececd ea’，过算每介字符的next和nextval函数的值.
3.给出冒泡排序和快速排序的最好情况，平均情况和最坏情况下的时间复杂度。
二、完成下列各题：（每小题8分，共24分）
1、设有下图所示的有向图，给出其邻接矩阵和强连通分量。
2、设有3阶B-树如下图所示，
（1)从该B-树上依次插入关键字33，97，画出两次插入后的B-树；
（2)从（1）得到的B-树上依次删除66，43，画出两次删除后的B-树；
（1）画出据此构造的败选择树
（2）画出输出一个记录后的败方树
三、阅读下列二叉树算法，每个结点三个域：lchild,element,rchild。(10分)
(1)X(p)对以p为根的二叉树执行什么功能?
(2)以下图所示的二叉树调用此算法，则X（p）的执行结果是什么?
(3)执行中，栈s中元素个数最多时为多少?给出该时栈中元素的情况。
void X(BinTree *t)
{struct Stack s;
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)；
else(*p)=Pop(s)
}
}
四、阅读下列要求每对顶点之间的最短路径的Floyd算法。(16分)
（1)若对下图所示的有向图执行此算法，写出对k为1到n的各步中，二维数组a和path的值。
（2）试设计一个算法，打印每对顶点<ij>（1<=i,j<=n）之间的最短路径长度(a[i,j]的值)及其对应的那条路径（路径上的顶点序列）。
CONST n={usersupplied integer}
TYPE graph=,1..n] OF real;
Pathtype=,1..n] OF integer;
PROCEDURE Floyd(cost:graph;VAR a:graph;VAR path:pathtype);
VAR 1,j,k,integer;
BEGIN
FOR i:=1 TO n DO
FOR j:=1 TO n DO
BEGIN
A[i,j]:=cost[i,j]；
IF(i<>j)and(a[i.j]<maxnum)
THEN path[i,j]:=i
ELSE path[i,j]:=0；
END
FOR k:=1 TO n DO
FOR i:=1 TO n DO
FOR j=1 TO n DO
IF a[i.j]:=a[i,k]+a[k,j]；
THEN BEGIN
a[i,j]:=a[i,k]+a[k,j]；
path[i,j]:=path[k,j]；
END
END
五、设计一个算法判断一个算数表达式中的括号是否配对。算数表达式保存在带表头结点的单循环链表中，每个结点有两个域：ch和link，其中ch域为字符类型。(16分）
六、试设计一个递归算法有一棵有n各结点的随机建立的二叉排序树上查第k (1<=k<=n)小元素，并返回指向该结点的指针。要求算法的平均时间复杂度为
o(log2n)2并说明你所设计的算法具有该时间复杂度的理由。二叉排序树的每个结点有四个域：1child,element,rchild,count。其中，count域中包存有以该结点为根的树（子树）上的结点数目。（16分）
南京邮电学院
2001年攻读硕士学位研究生入学
数据结构试题
一、完成下列各题(每小题6分，共18分)：
1.已知字符串P=‘abbabbac’，计算next（7)和mextva1(7)的值.
字符串是什么数据结构
2.给出下列排序软法的最坏情况时间复杂性，并指出哪些算法是稳定的？
(1）块速排序（2）简单选择排序（3）堆排序
3.设度为m的树采用多重链表存储。每个结点有m+1个域，其中有一个数据域，m个指向孩子的指针域。则空指针的数目是多少?说明这种存储方式的利弊。
二、完成下列各题：（每小题8分，共40分)
2.对于下列AOE网络，求出各活动可能的最早开始时间和允许的最晚完成时间。
3.设有13个初始游程。其长度分别为28，16，33，19，5，7,18，20，12，31，38,22,10。试画出4路合并的最佳合并树，并计算它的加权路径长度。
4.设散列表ht长度为11，散列函数,h1(key)=keymod11,h2(key)=keymod9+1。采用双重探查法解决冲突，请从空表开始，依次插入下列关键字值序列,70,25,80, 35,60,45,50,55，建立散列表。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。