2018年江苏师范大学计算机科学与技术学院862管理信息系统与数据结构之数据结构考研基础五套测试题
● 摘要
一、填空题
1． 求最短路径的Dijkstra 算法的时间复杂度为_____。
【答案】
2． 一个算法具有5个特性: _____、_____、_____、有零个或多个输入、有一个或多个输出。
【答案】有穷性；确定性；可行性
3． 在单链表中设置头结点的作用是_____。
【答案】方便运算
4． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度____；深度优先遍历图的时间复杂度_____，两者不同之处在于_____，反映在数据结构上的差别是_____。
【答案】查找顶点的邻接点的过程；0(n+e)；0(n+e)；访问顶点的顺序不同；队列和栈 【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。
5． VSAM(虚拟存储存取方法) 文件的优点是:动态地_____，不需要文件进行_____，并能较快地_____进行查找。
【答案】分配和释放存储空间；重组；对插入的记录
6． 在一个具有n 个单元的顺序栈中，假定以地址高端(即下标为n 的单元) 作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top ＝_____。
【答案】top ﹣1
【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，所以top ﹣1。
7． 完善算法:求KMP 算法.next 数组。
k :＝_____；next[1]:＝0；
k :＝_____；
END ；
【答案】0；next[k]
8． 应用prim 算法求解连通网络的最小生成树问题。
(1)针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。(始顶点号，终顶点号，权值
)
(2)下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。
的值在
图的顶点数，应由用户定义
用二维数组作为邻接矩阵表示
生成树的边结点
边的起点与终点
边上的权值
最小生成树定义
从顶点rt 出发构造图G 的最小生成树T , rt 成为树的根结点
初始化最小生成树
T
依次求MST 的候选边
遍历当前候选边集合
选具有最小权值的候选边
图不连通，出错处理
修改候选边集合
中
【答案】(1)
(2)
【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设是N 上最小生成树边的集合。算法从属于
的边为止。
9． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度, 当它为一棵_____时，具有最大高度。
【答案】完全；只有一个叶结点的二叉树
10．如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。
【答案】69
【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。
，
属于E 中找一条代价最小的边
加入集合
是连通图
，
，v ，
直到
开始，重复执行下述操作:在所有u 属于
，同时将并入
二、单项选择题
11．一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是（ ）.
A.28字节 B.216字节 C.224字节 D.232字节 【答案】C
【解析】段内位移的最大值就是最大段长. 段号长度占了8位，剩下32﹣8＝24位是段内位移空间，因此最大段长为2B.
12．下列关于USB 总线特性的描述中, 错误的是（ ）。
24
A. 可实现外设的即插即用和热插拔 B. 可通过级联方式连接多台外设 C. 是一种通信总线, 可连接不同外设 D. 同时可传输2位数据, 数据传输率高 【答案】D 。
【解析】USB 总线即通用串行总线, 它的特点有:
(1)即插即用; (2)热插拔; (3)有很强的链接能力能将所有外设链接起来, 且不损失带宽; (4)有很好的可扩展性; (5)高速传输, 速度可达480Mbps 。