注：1、除第九题外，其他各题每题10分，第九题20分。
2、所有试题的答案写在答题纸上。

一、判断下列叙述的对错。
(1) 线性表的逻辑顺序与物理顺序总是一致的。
(2) 线性表的顺序存储表示优于链式存储表示。
(3) 线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。
(4) 二维数组是其数组元素为线性表的线性表。
(5) 每种数据结构都应具备三种基本运算：插入、删除和搜索。

二、设单链表中结点的结构为
TYPEDEF STRUCT NODE { //链表结点定义
ELEMTYPE DATA; //数据
STRUCT NODE * LINK; //结点后继指针
} LISTNODE;
(1) 已知指针P所指结点不是尾结点，若在*P之后插入结点*S，则应执行下列哪一个操作？
A. S->LINK = P; P->LINK = S;
B. S->LINK = P->LINK; P->LINK = S;
C. S->LINK = P->LINK; P = S;
D. P->LINK = S; S->LINK = P;

(2) 非空的循环单链表FIRST的尾结点（由P所指向）满足：
A. P->LINK == NULL;
B. P == NULL;
C. P->LINK == FIRST;
D. P == FIRST;

三、设有一个顺序栈S，元素S1, S2, S3, S4, S5, S6依次进栈，如果6个元素的出栈顺序为S2, S3, S4, S6, S5, S1，则顺序栈的容量至少应为多少？

四、一棵具有N个结点的理想平衡二叉树（即除离根最远的最底层外其他各层都是满的，最底层有若干结点）有多少层？若设根结点在第0层，则树的高度H如何用N来表示（注意N可能为0）？

五、从供选择的答案中选择与下面有关图的叙述中各括号相匹配的词句，将其编号填入相应的括号内。
(1) 对于一个具有N个结点和E条边的无向图，若采用邻接表表示，则顶点表的大小为（ A ），所有边链表中边结点的总数为（ B ）。
(2) 采用邻接表存储的图的深度优先遍历算法类似于树的（ C ）。
(3) 采用邻接表存储的图的广度优先遍历算法类似于树的（ D ）。
(4) 判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（ E ）。
供选择的答案
A：① N ② N+1 ③ N-1 ④ N+E
B：① E/2 ② E ③ 2E ④ N+E
C~D：① 中根遍历 ② 先根遍历 ③ 后根遍历 ④ 按层次遍历
E：① 求关键路径的方法 ② 求最短路径的DIJKSTRA方法
③ 深度优先遍历算法 ④ 广度优先遍历算法

六、填空题
(1) 在用于表示有向图的邻接矩阵中, 对第I行的元素进行累加, 可得到第I 个顶点的（ ① ）度, 而对第J列的元素进行累加, 可得到第J个顶点的（ ② ）度。
(2) 一个连通图的生成树是该图的（ ③ ）连通子图。若这个连通图有N个顶点, 则它的生成树有（ ④ ）条边。
(3) 给定序列{100, 86, 48, 73, 35, 39, 42, 57, 66, 21}, 按堆结构的定义, 则它一定( ⑤ )堆。
(4) 在进行直接插入排序时, 其数据比较次数与数据的初始排列（ ⑥ ）关；而在进行直接选择排序时，其数据比较次数与数据的初始排列（ ⑦ ）关。
(5) 利用关键码分别为10, 20, 30, 40的四个结点，能构造出（ ⑧ ）种不同的二叉搜索树。

七、设带表头结点的双向链表的定义为
TYPEDEF INT ELEMTYPE;

TYPEDEF STRUCT DNODE { //双向链表结点定义
ELEMTYPE DATA; //数据
STRUCT DNODE * LLINK, * RLINK; //结点前驱与后继指针
} DBLNODE;

TYPEDEF DBLNODE * DBLLIST; //双向链表
试设计一个算法，改造一个带表头结点的双向链表，所有结点的原有次序保持在各个结点的右链域RLINK中，并利用左链域LLINK把所有结点按照其值从小到大的顺序连接起来。

八、设有一个关键码的输入序列 { 55, 31, 11, 37, 46, 73, 63, 02, 07 },
(1) 从空树开始构造平衡二叉搜索树, 画出每加入一个新结点时二叉树的形态。若发生不平衡, 指明需做的平衡旋转的类型及平衡旋转的结果。
(2) 计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度和查找不成功的平均查找长度。

九、下面是求连通网络的最小生成树的PRIM算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。
CONST INT MAXINT = INT_MAX; //INT_MAX的值在中
CONST INT N = 6; //图的顶点数, 应由用户定义
TYPEDEF INT ADJMATRIX[N>[N>; //用二维数组作为邻接矩阵表示
TYPEDEF STRUCT { //生成树的边结点
INT FROMVEX, TOVEX; //边的起点与终点
INT WEIGHT; //边上的权值
} TREEEDGENODE;
TYPEDEF TREEEDGENODE MST[N-1>; //最小生成树定义

VOID PRIMMST ( ADJMATRIX G, MST T, INT RT ) {
//从顶点RT出发构造图G的最小生成树T，RT成为树的根结点
TREEEDGENODE E; INT I, K = 0, MIN, MINPOS, V;
FOR ( I = 0; I < N; I++ ) //初始化最小生成树T
IF ( I != RT ) {
T[K>.FROMVEX = RT;
T[K>.TOVEX = I ;
T[K++>.WEIGHT = G[RT>;
}
FOR ( K = 0; K < N-1; K++ ) { //依次求MST的候选边
MIN = MAXINT ;
FOR ( I = K; I < N-1; I++ ) //遍历当前候选边集合
IF ( T.WEIGHT < MIN ) //选具有最小权值的候选边
{ MIN = T.WEIGHT; MINPOS = I ; }
IF ( MIN == MAXINT ) //图不连通, 出错处理
{ CERR << “GRAPH IS DISCONNECTED!” << ENDL; EXIT(1) ; }
E = T[MINPOS>; T[MINPOS> = T[K> ; T[K> = E;
V = T[K>.TOVEX;
FOR ( I = K+1; I < N-1; I++ ) //修改候选边集合
IF ( G[V>[T.TOVEX> < T.WEIGHT ) {
T.WEIGHT = G[V>[T.TOVEX>;
T.FROMVEX = V ;
}
}
}

参考答案

一、(1) 错 (2) 错 (3) 对 (4) 错 (5) 对

二、(1) B (2) C

三、3

四、H = éLOG2(N+1)ù -1

五、A. ① B. ③ C. ② D. ④ E. ③

六、① 出 ② 入 ③ 极小 ④ N-1
⑤ 是（最小） ⑥ 有 ⑦ 无 ⑧ 14

七、算法如下
VOID SORT ( DBLNODE * L ) {
DBLNODE * S = L->RLINK;
//指针S指向待插入结点, 初始时指向第一个结点
WHILE ( S != NULL ) { //处理所有结点
PRE = L; P = L->LLINK;
//指针P指向待比较的结点, PRE是P的前驱指针
WHILE ( P != NULL && S->DATA < P->DATA )
//循LLINK链寻找结点 *S的插入位置
{ PRE = P; P = P->LLINK; }
PRE->LLINK = S; S->LLINK = P; S = S->RLINK;
//结点 *S在LLINK方向插入到 *PRE与 *P之间
}
}

八、关键码的输入序列 { 55, 31, 11, 37, 46, 73, 63, 02, 07 }