南 京 理 工 大 学97考研题
考试科目：数据结构 实用专业：计算机科学与应用
一 选择(28分，四个可选的答案中只有一个是正确的，选出正确的一个)
1. 双向链表中有两个指针域,LLINK和RLINK分别指向前趋和后继，设P指向链表中的一个结点，
现在要求删去P所指结点，则正确的删是——(链表结点数大于2，P不是第一个结点)
A. p^.link^.rlink:=p^llink;p^.llink^.rlink:-p^.rlnk;dispose(p);
B. dispose(p);p^.llink^.rlink:=p^.llink;p^.llink^,rlink:=p^.rlink;
C. p^.llink^.rlink:=p^.llink;dispose(p);p^.llink^.rlink:=p^.rlink;
D. 以上A，B，C都不对。
2.对一组数据(84，47，25，15，21)排序，数据的排列次序在排序的过程中的变化为
(1)84 47 25 15 21
(2)15 47 25 84 21
(3)15 21 25 84 47
(4)15 21 25 47 84
则采用的排序是 ——
A. 选择 B。冒泡 C。快速 D。插入
3.栈和队列都是——
A.顺序存储的线性结构 B。链式存储的非线性结构
C.限制存取点的线性结构 D。限制存取点的非线性结构
4.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法
构造散列表，散列函数为H(key)=key MOD 13,，散列地址为1的链中有——个记录。
A.1 B。2 C。3 D。4
5.设有三个元素X，Y，Z的顺序进栈(进的过程中允许出线)，下列得不到的出栈排列是
A.XYZ B。YZX C。ZXY D。ZYX
6.适用于折半查找的表的存储方式及元素排列要求为——
A. 链接方式存储，元素无序
B. 链接方式存储，元素有序
C. 顺序方式存储，元素无序
D. 顺序方式存储，元素有序
7.当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也棵用顺序查找，
但前者比后者的查找速度——
A.必定快 B。不一定 C。在大部分情况下要快 D。取决于表递增还是递减
8.设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，
数组从内容首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储
首地址为——
A.BA+141 B。BA+180 C。BA+222 D。BA+225
9.下列关于m阶B-树的说法错误的是——
A.根节点至多有m棵子树
B.所有叶子都同一层次上
C.非叶结点至少有m/2 m为偶数)或m/2+1(m为奇数)棵子树
D.根结点中的数据是有序的
10.某内排序方法的稳定性是指——
A. 该排序算法不允许有相同的关键字记录
B. 该排序算法允许有相同的 关键字记录
C. 平均时间0(n log n)的排序方法
D. 以上都不对
11-14
下面是求连通网的最小生成树的prim算法：
集合VT，ET分别放顶点和边，初始为(11)，下面步骤重复n-1次:a，(12) ,b,(13)最后，(14)
11.A.VT，ET为空 B。VT为所有顶点，ET为空
C.VT为网中任意一点，ET为空 D。VT为空，ET为网中所有边
12.A.选I属于VT，j不属于VT，且(I，j)上的权最小
B.选I属于VT，j不属于VT，且(I，j)上的权最大
C.选I不属于VT，j不属于VT，且(I，j)上的权最小
D.选I不属于VT，j不属于VT，且(I，j)上的权最大
13.A.顶点I加入VT，(I,j)加入ET
B.顶点j加入VT，(I,j)加入ET
C. 顶点j加入VT，(I,j)从ET中删去
D.顶点I，j加入VT，(I,j)加入ET
14.A.ET 中为最小生成树
B.不在ET中的边构成最小生成树
C.ET中有N-1条边时为声成树，否则无解
D.ET中无回路时，为生成树，否则无解
二.对下列说法正确的打对号，错误的画叉
1. 求最短路径的迪杰斯拉算法弧的权大于0。
2. 内排序要求数据一定要以顺序方式存储
3. 在平衡二叉树中，向某个平衡因子不为零的结点的书中插入一新接点，必引起平衡旋转
4. 在待排数据基本有序的情况下，快速排序效果最好
5. 散列函数月复杂越好，因为这样随机性好，冲突概率小
6. 二叉树只能用二叉链表表示
7. 一个堆是一个完整二叉树，反之依然
8. 二叉树的遍历结果不是唯一的
9. 取线性表的第I个元素的时间同I的大小有关
10. 求关键路径时，路径上的权可正可负
11. 一棵有N个接点的二叉树，从上到下，从左到右用自然数依次给予编号，则编号为I左儿子的编号为2I，(2I〈N 〉右儿子是2I+1
(2I+1〈N〉
三.填空
1.当两个栈共享一个存储区时，栈用一维数组STACK(1，N)表示，两栈顶指针为TOP[1]与TOP[2]，则当栈一空时，TOP[1]为—--------，栈二空时 ，TOP [2]为-------，栈满时为-------
2.一个有2001个结点的完全二叉树的高度为-----------
3.若一个无向图有E条边，则他的临接表中有-----个数据点
4.给定一组数据{6，2，7，10，3，12}以他构造一棵哈夫曼树，则树高为-------，带权路径长度WPL的值为-----。
5.设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长(也称增量序列)依次是4，2，1则排序需-------趟，写出第一趟结束后，数组中数据的排列次序--------------
6.一无向图G(V，E)，其中V(G)={1，2，3，4，5，6，7}，E(G)={(1，2)，(1，3)，(2，4)，(2，5)，(3，6)，(3，7)，(6，)(5，1)},对该图从顶点3开始进行遍历，去掉遍历中未走过得边，得一生成树G‘(V，E’)，V(G‘)=V(G)，E(G’)={(1，3)，(3，6)，(7，3)，(1，2)，(1，5)，(2，4)}，则采用的遍历方法是---------
7.设Y指向二叉线索书的一叶子，X指向一带插入点，现X作为Y的左孩子插入，树中标志域为ltag和rtag，并规定标志为1是线索，则下面的一段算法将x插入并修改相应的线索，试补充完整：(lchild,rchild分别代表左，右孩子)
x^.ltag:=------; x^.lchild:=----------;
y^.ltag:=------; y^.lchild:=----------;
x^.rtag:=------; x^.rchild:=---------;
IF(x^.lchild<>NIL)AND(x^lchild^.rtag=1)
THEN x^.lchild.rchild:=--------;
8.下面是求二叉树高度的类PASCAL及类C写的递归算法试补充完整
[说明]
(1) 考生可根据自己的情况任选一个做(都做不给分)
(2) 二叉树的两指针域为lchild与rchild, 算法中p为二叉树的根，lh和rh分别为以p为根的二叉树的左子树和右子树的高，hi为以p为根的二叉树的高，hi最后返回。
[类pascal]
procedure height(p);
begin
if -------then
if p^.lchild=nil
then lh:=--------
else lh:=---------;
if p^.rchild=nil
then rh:=-------
else rh:=--------;
if lh>rh
then hi:=-------
else hi:=-------;
else hi:=-----;
return hi;
end;
[类C]
height(p)
{
if (--------)
{
if(p->lchild=null)
lh=-----;
else rh=--------;
if (lh>rh)
hi=------
else hi=-------;
}
else hi=------;
return hi;
}
四.用类pascal或C,类-C写出算法(25分)
注:单考考生做1与2,其他考生做2,3.
1.(15分)(此题仅单考生做)
(1) 设有一组数据为{-2,9,-9,87,23,1,0},试按给定次序从空排序二叉树开始,逐步建立排序二叉树,画出最后的排序二叉树.
(2) 写出一个算法,PROCEDURE ex(tree);
其中tree为一个指向二叉排序树的根的指针,算法将二叉排序树的数据从大到小拍在头指针为head的无头链表中,二叉排序树的结点有数据域data,左,右指针域lchild 和rchild ,链表的域为数据域data,链域next,head 的初值为空.
2.(10分)设有向图用链接表表示,图有n个顶点,表示为1至n,试写一个算法求顶点k的入度(1
PROCEDURE COUNT(adj,k);
其中adj为邻接表,k为指定的顶点.
3.(15分,此题单考生不做)
设有两个无头结点的单链表,头指针分别为ha,hb,链表中有数据域data,链域 next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha 中,hb的链表在算法中不允许被破坏.
PROCEDURE merge(ha,hb); | 
