2017年福建师范大学软件学院841计算机专业基础综合之数据结构考研强化模拟题
● 摘要
目录
2017年福建师范大学软件学院841计算机专业基础综合之数据结构考研强化模拟题（一）.... 2 2017年福建师范大学软件学院841计算机专业基础综合之数据结构考研强化模拟题（二）.. 13 2017年福建师范大学软件学院841计算机专业基础综合之数据结构考研强化模拟题（三）.. 23 2017年福建师范大学软件学院841计算机专业基础综合之数据结构考研强化模拟题（四）.. 35 2017年福建师范大学软件学院841计算机专业基础综合之数据结构考研强化模拟题（五）.. 46
一、填空题
1． 无用单元是指_____，例_____
【答案】用户不再使用而系统没有回收的结构和变量；
2． 顺序栈用
【答案】
存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。
3． 应用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
上最小生成树边的集合。算法从属于
为止。
4． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
5． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。
【答案】
6． 在哈希函数
中，P 值最好取_____。
E T 开始，重复执行下述操作：在所有u
属于
加入集合
同时将
并入
v
直到
的边（u ，v ）属于E
中找一条代价最小的边
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
7． 求最短路径的Dijkstra 算法的时间复杂度为_____。
【答案】
8． 完善算法：求KMP 算法.next 数组。
END ； 【答案】
9． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：
【答案】
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
10．已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。
【答案】左子树；右子树 【解析】二叉排序树
或者是一棵空树，或者是具有下列性质的二叉树：①若它
的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。
11．设有两个算法在同一机器上运行，其执行时闻分别为要使前者快于后者，n 至少为_____。
【答案】15
【解析】当时，而
，
12．实现字符串拷贝的函数strcpy 为：
时，
【答案】
二、选择题
相关内容
相关标签