2018年北京信息科技大学经济管理学院813数据结构和C语言程序设计之数据结构考研仿真模拟五套题
● 摘要
一、填空题
1． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，
请在算法空格处填上正确的语句。 设线索二叉树的结点数据结构为其中:
left 指向其左孩子，
【答案】
left 指向其前驱；，
right 指向其后继。
，
right 指向其右孩子，，
，
2． VSAM(虚拟存储存取方法) 文件的优点是:动态地_____，不需要文件进行_____，并能较快地_____进行查找。
【答案】分配和释放存储空间；重组；对插入的记录
3． 应用prim 算法求解连通网络的最小生成树问题。
(1)针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。(始顶点号，终顶点号，权值
)
(2)下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。
的值在
图的顶点数，应由用户定义
用二维数组作为邻接矩阵表示
生成树的边结点
边的起点与终点
边上的权值
最小生成树定义
从顶点rt 出发构造图G 的最小生成树T , rt 成为树的根结点
初始化最小生成树
T
依次求MST 的候选边
遍历当前候选边集合
选具有最小权值的候选边
图不连通，出错处理
修改候选边集合
【答案】(1)
(2)
【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设是N 上最小生成树边的集合。算法从属于
中
是连通图
，
，v ，
直到
，开始，重复执行下述操作:在所有u 属于
加入集合
，同时将并入
的边为止。
属于E 中找一条代价最小的边
4． 在哈希函数中，p 值最好取_____。
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
5． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。
【答案】O(1)；O(n)
【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。
二、单项选择题
6． 下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（ ）。
A. 直接插入排序 B. 起泡排序 C. 基数排序 D. 快速排序 【答案】C
【解析】C 项, 基数排序是采用分配和收集实现的, 不需要进行关键字的比较。ABD 三项都依赖关键字的比较, 不同的初始排列次序下元素移动的次数有很大变化, 最好情况元素正序, 则不用移动, 最坏情况元素反序, 则需要移动次(n为元素个数) 。
7． 当系统发生抖动(thrashing)时, 可以采取的有效措施是（ ）。
Ⅰ. 撤销部分进程 Ⅱ. 增加磁盘交换区的容量 Ⅲ. 提高用户进程的优先级 A. 仅Ⅰ B. 仅Ⅱ C. 仅Ⅲ D. 仅Ⅰ、Ⅱ 【答案】A
【解析】“抖动”现象是指刚刚被换出的页很快又要被访问, 为此, 又要换出其他页, 而该页又很快被访问, 必须换入, 如此频繁地置换页面, 以致操作系统的大部分时间都花在页面置换上, 引起系统性能下降甚至崩溃。引起系统抖动现象的原因是对换的信息量过大, 内存容量不足, 置换算法选择不当。所以解决的办法就是降低交换页面数量, 加大内存容量, 改变置换选择算法。但是降低交换页面数量和改变置换选择算法对于一个应用系统来讲是不可能的, 只能增加内存容量。增加内存容量可以是直接添加物理内存(大型计算机都可以在不关机的情况下增加物理内存条) , 或者, 降
相关内容
相关标签