2018年甘肃省培养单位近代物理研究所866计算机原理之数据结构考研强化五套模拟题
● 摘要
一、填空题
1． 有向图G=(V, E) ，其中权d 。E(G)为
，则从源点0到顶点3的最短路径长度是_____，经过的中间顶点是_____。
【答案】50；4
2． 在有n 个顶点的有向图中，每个顶点的度最大可达_____。
【答案】2(n－1)
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n －1。
3． 模式串的next 函数值序列为_____。
【答案】01122312
4． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空:
(_____i)；
＝
_____.
_____
【答案】a ＋l ；n%10
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
，用
三元组表示弧
及弧上的
5． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n 个顶点
用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。
(1)若
是边，则
的值等于_____，若
不是边，则A(i, j) 的值是一个比任何
置
边的权_____，矩阵的对角线元素全为0。
(2)构造最小生成树过程中，若顶点已包括进生成树，就把相邻矩阵的对角线元素成_____，若
【答案】(1)
已包括进生成树，就把矩阵元素
置成_____。
(3)算法结束时，相邻矩阵中_____的元素指出最小生成树的_____。
边上的权值；都大的数；(2)1; 负值；(3)为负；边
6． 在单链表中设置头结点的作用是_____。
【答案】方便运算
7． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关，即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。
【答案】逻辑特性；在计算机内部如何表示和实现；数学特性
8． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
9． 空格串是指_____，其长度等于_____。
【答案】由空格字符(ASCII值32) 所组成的字符串；空格个数
10．完善算法:求KMP 算法.next 数组。
k :＝_____；next[1]:＝0；
k :＝_____；
END ；
【答案】0；next[k]
二、单项选择题
11．程序P 在机器M 上的执行时间是20秒, 编译优化后, P 执行的指令数减少到原来的70%而CPI 增加到原来的
A. B.
秒 秒
倍, 则P 在M 上的执行时间是（ ）
C.14秒 D.
秒 【答案】D
【解析】
12．下列说法不正确的是（ ）。
A. 图的遍历是从给定的源点出发每个顶点仅被访问一次 B. 遍历的基本方法有两种:深度遍历和广度遍历 C. 图的深度遍历不适用于有向图 D. 图的深度遍历是一个递归过程 【答案】C
【解析】图的遍历是指从图中的某一个顶点出发，按照某种搜索算法沿着图中的边对图中的所有顶点访问一次且仅访问一次。图的深度遍历类似于树的先序遍历，不仅适合无向图，也适合于有向图。
13．系统为某进程分配了4个页框, 该进程已访问的页号序列为2, 0, 2, 9, 3, 4, 2, 8, 2, 3, 8, 4, 5, 若进程要访问的下一页的页号为7, 依据LRU 算法, 应淘汰页的页号是（ ）。
A.2 B.3 C.4 D.8
【答案】B
【解析】LRU 置换算法是选择最近最久未使用的页面予以淘汰。进程有4个页框, 题中访问过程中页框的变化如下:
访问页号为7的页时, 内存中存在的页的页号是:3、8、4和5, 根据LRU 定义应淘汰的是3。
14．已知关键字序列5，8，12，19，28，20，15，22是小根堆(最小堆) ，插入关键字3，调整后的小根堆是（ ）.
A.3， 5， 12， 8， 28， 20， 15， 22， 19 B.3， 5， 12， 19， 20， 15， 22， 8， 28 C.3， 8， 12， 5， 20， 15， 22， 28， 19 D.3， 12， 5， 8， 28， 20， 15， 22， 19 【答案】A
【解析】在堆中插入或删除一个元素后，将不再满足堆的性质. 为了使其成为新堆，在输出堆
相关内容
相关标签