2017年首都师范大学信息工程学院908计算机学科综合考研强化模拟题
● 摘要
一、填空题
1． 求最短路径的Dijkstra 算法的时间复杂度为_____。
【答案】
2． 当广义表中的每个元素都是原子时，广义表便成了_____。
【答案】线性表
【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。
3． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。
【答案】
【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测的次数最小。总次数为
4． 文件由_____组成；记录由_____组成。
【答案】记录；数据项
5． 应用prim 算法求解连通网络的最小生成树问题。
（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。
〔始顶点号，终顶点号，权值）
（2）下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。
的值在〈limits •h>中
//图的顶点数，应由用户定义
//用二维数组作为邻接矩阵表示
//生成树的边结点
//边的起点与终点
//边上的权值
//最小生成树定义
//从顶点rt 出发构造图G 的最小生成树T ，rt 成为树的根结点
//初始化最小生成树
T
//依次求MST 的候选边
//遍历当前候选边集合
//选具有最小权值的候选边
//图不连通，出错处理
//修改候选边集合
【答案】（1）（0，3，1）; （3，5, 4）; （5，2，2）; （3，1, 5）; （1，4，3） （2）①T[k]; tovex=i②min=Maxint③mispos=i④exit （O ）⑤T[i]; fromvex=v
【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设N={V，E}是连通图
，是N
上最小生成树边的集合。算法从属于
为止。
6． 表达式
【答案】
的后缀表达式是_____。
E T 开始，重复执行下述操作：在所有u
属于
加入集合
同时将
并入
v
直到
的边（u ，v ）属于E
中找一条代价最小的边
7． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_____和记录的_____，
【答案】比较；移动 8
．
求REPLACE （S ，V , m ）=_____。
【答案】
已
知
9． 从平均时间性能而言，_____排序最佳。
【答案】快速
【解析】快速算法的平均时间复杂度为nlogn 。 10．=_____
【答案】5
11．高度为4的3阶B-树中，最多有_____个关键字。
【答案】26
【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。
12．在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。
【答案】m/2
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
二、选择题
13．—个多道批处理系统中仅有P1和P2两个作业，P2比P1晚5ms 到达。它们的计算和P1:计算60ms ，作顺序如下：
计算
计算
计算
虑调度和切换时间，则完成两个作业需要的时间最少是（ ）。
A.240ms B.260ms C.340ms D.360ms
【答案】B 。
【解析】考查处理系统的性能计算，由于P2比PI 晚5ms 到达，PI 先占用CPU ，根据PI 和P2的执行过程，作业运行的甘特图如下所示，故答案为B 。
操若不考
相关内容
相关标签