注：1、除第九题外，其他各题每题10分，第九题20分。
2、所有试题的答案写在答题纸上。
一、判断下列叙述的对错。
线性表的逻辑顺序与物理顺序总是一致的。
线性表的顺序存储表示优于链式存储表示。
线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。
二维数组是其数组元素为线性表的线性表。
每种数据结构都应具备三种基本运算：插入、删除和搜索。
二、设单链表中结点的结构为
typedef struct nodeListNode;
已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？
A. s-link =p-link = s;
B. s-link = p-link; p-link = s;
C. s-link = p-link; p = s;
D. p-link = s; s-link =
非空的循环单链表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）？
五、从供选择的答案中选择与下面有关图的叙述中各括号相匹配的词句，将其编号填入相应的括号内。
对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为（ A ），所有边链表中边结点的总数为（ B ）。
采用邻接表存储的图的深度优先遍历算法类似于树的（ C ）。
采用邻接表存储的图的广度优先遍历算法类似于树的（ D ）。
判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（ E ）。
供选择的答案
A：① n ② n+1 ③ n-1 ④ n+e
B：① e/2 ② e ③ 2e ④ n+e
C．D：① 中根遍历 ② 先根遍历 ③ 后根遍历 ④ 按层次遍历
E：① 求关键路径的方法 ② 求最短路径的Dijkstra方法
③ 深度优先遍历算法 ④ 广度优先遍历算法
六、填空题
在用于表示有向图的邻接矩阵中， 对第i行的元素进行累加， 可得到第i 个顶点的（ ① ）度， 而对第j列的元素进行累加， 可得到第j个顶点的（ ② ）度。
一个连通图的生成树是该图的（ ③ ）连通子图。若这个连通图有n个顶点， 则它的生成树有（ ④ ）条边。
给定序列， 按堆结构的定义， 则它一定堆。
在进行直接插入排序时， 其数据比较次数与数据的初始排列（ ⑥ ）关；而在进行直接选择排序时，其数据比较次数与数据的初始排列（ ⑦ ）关。
利用关键码分别为10， 20， 30， 40的四个结点，能构造出（ ⑧ ）种不同的二叉搜索树。
七、设带表头结点的双向链表的定义为
typedef int ElemType;
typedef struct dnodeDblNode;
typedef DblNode * DblList; //双向链表
试设计一个算法，改造一个带表头结点的双向链表，所有结点的原有次序保持在各个结点的右链域rLink中，并利用左链域lLink把所有结点按照其值从小到大的顺序连接起来。
八、设有一个关键码的输入序列 ，
从空树开始构造平衡二叉搜索树， 画出每加入一个新结点时二叉树的形态。若发生不平衡， 指明需做的平衡旋转的类型及平衡旋转的结果。
计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度和查找不成功的平均查找长度。
九、下面是求连通网络的最小生成树的Prim算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。
const int MaxInt = INT_MAX; //INT_MAX的值在中
const int n = 6; //图的顶点数， 应由用户定义
typedef int AdjMatrix[n[n; //用二维数组作为邻接矩阵表示
typedef structTreeEdgeNode;
typedef TreeEdgeNode MST[n-1; //最小生成树定义void PrimMST
forif//图不连通， 出错处理
e = T[minpos; T[minpos = T[k ; T[k = e;v = T[k.toVex;
for//修改候选边集合if}
参考答案
一、 错错对错对
二、 BC
三、3
四、h = élog2ù -1
五、A. ① B. ③ C. ② D. ④ E. ③
六、① 出 ② 入 ③ 极小 ④ n-1
⑤ 是（最小） ⑥ 有 ⑦ 无 ⑧ 14
七、算法如下
void sort pre-lLink = s; s-lLink =s = s-rLink; //结点 *s在lLink方向插入到 *pre与 *p之间 }
八、关键码的输入序列
在等概率下查找成功的平均查找长度
在等概率下查找不成功的平均查找长度
九 ① T[k.toVex = i
② min = MaxInt
③ minpos = i
④ exit
⑤ T.fromVex = v
发布者：ws2012
来源：在职研究生网本页网址：http://zzy.china-b.com/gctwk/lj/20090629/194019_1.html
声明：我方为第三方信息服务平台提供者，本文来自于网络，登载出于传递更多信息之目的，并不意味着赞同其观点或证实其描述，文章内容仅供参考。如若我方内容涉嫌侵犯其合法权益，应该及时反馈，我方将会尽快移除被控侵权内容。
同等学力成绩
咨询热线：
