2017年贵州大学计算机科学与技术学院831程序设计与数据结构考研强化模拟题
● 摘要
一、选择题
1． 用邻接表存储图所用的空间大小（ ）。
A. 与图的顶点数和边数都有关 B. 只与图的边数有关 C. 只与图的顶点数有关 D. 与边数的平方有关 【答案】A
【解析】邻接表就是对图G 中的每个顶点Vi 建立一个单链表，第i 个单链表中的结点表示依附于顶点V i 的边，这个单链表就称为顶点Vi 的边表。因此邻接表既存储图的所有顶点，也存储顶点之间的边的信息。
2． 假设某计算机的存储系统由Cache 和主存组成。某程序执行过程中访存1000次，其中访问Cache 缺失（未命中）50次，则Cache 的命中率是（ ）。
A.5% B.9.5% C.50% D.95%
【答案】D
【解析】Cache 的命中率次数，程序总访存次数
，其中
为访问Cache 的次数，
为访存主存的所以根据公
, 程序访存次数减去失效次数就是访问Cache 的次数
式可得：H=（1000-50）/1000=95%。
3． 在一株高度为2的5阶B 树中，所含关键字的个数最少是（ ）
A.5 B.7 C.8 D.14
【答案】A
【解析】根据B 树的定义可知，跟结点最少含有
个关键字，高度为2的阶B
树最少有（5-1）+1=5个关键字，其中根节点含有个关键字，第2层结点含有1关键字。
4． 用海明码对长度为8位的数据进行检/纠错时，若能纠正一位错，则校验位数至少为（ ）
A.2 B.3 C.4 D.5
【答案】C
【解析】设校验位的位数为k ，数据位的位数为n ，根据海明码编码k 和n
应满足下述关系。
当k=4时，
5． 某计算机有五级中断的顺序为
A.11110 B.01101 C.00011 D.01010 【答案】D
【解析】由于
则
中断屏蔽字为
表示对
级中断进行
屏蔽。若中断响应优先级从高到低的顺序是
且要求中断处理优先级从高到低
符合要求，校验位至少是4位，故答案为C 。
的中断处理程序中设置的中断屏蔽字是（ ）。
B
排除掉。的中断处理优先级下降，屏蔽字中需要3个0, 所以可以将选项A 、
需要对开放，所以相应位应该为即为01010。
6． 下列关于无向连通图特性的叙述中，正确的是（ ）。
I. 所有的顶点的度之和为偶数 II. 边数大于顶点个数减1 III. 至少有一个顶点的度为1 A. 只有I B. 只有II C.I 和II D.I 和III 【答案】A
【解析】在图中，顶点的度TD 点数，
e 为总边数），因此，I 项正确。对于II 、III 项中的特性不是一般无向连通图的特性，可以轻松地举出反例。“至少有一个顶点的度为1”的反例如下图（1）所示，“边数大于顶点个数减1”的反例如下图（2）所示。
之和与边的数目满足关系式：
（n 为图的总结
图
7． 对一组数据（2, 12, 16, 88, 5，10）进行排序，若前三趟排序结果如下：
第一趟：2，12，16, 5，10，88
第二趟：2，12，5，10，16, 88 第三趟：2，5，10，12，16, 88 则采用的排序方法可能是（ ）。 A. 起泡排序 B. 希尔排序 C. 归并排序 D. 基数排序 【答案】A
【解析】题目中所给的三趟排序过程，显然是使用起泡排序方法，每趟排序时从前往后依次，待序列中的记录“基比较，使大值“沉底”。希尔排序的基本思想是：先对序列进行“宏观调整”本有序”时再进行直接插入排序。宏观调整的方法是：通过某种规则将大的待排序序列分割为若干小的待排序序列，再依次对这些小的序列直接插入排序。宏观调整可以多次，每次分割的序列数逐渐増多，而每个序列中所包含的元素数逐渐减少。归并排序的基本操作是将多个小的有序序，直至整个序列为有序为止。 基数排序是分配排列合并为一个大的有序序列，然后“逐趟归并”
序的一种，这类排序不是通过关键字比较，而是通过“分配”和“收集”过程来实现排序的。 本，显然使用的是起泡排序法。 题中，很容易看出大值逐渐“沉底” 8． 某字长为8位的计算机中，y 的机器数分别为已知整型变量x 、若整型变量
A.11000000 B.00100100 C.10101010 D. 溢出
【答案】A
y 右移一位， 【解析】将x 左移一位，两个数的补码相加的机器数为1 1000000, 故答案选择A 。
9． 设栈S 和队列Q 的初始状态为空，元素依次通过栈S ，一个元素出栈后即进队列Q ，若6个元素出队的序列是
A.6 B.4 C.3 D.2
【答案】C
10．对于栈操作数据的原则是（ ）。
A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 【答案】B
则z 的机器数为（ ）
则栈S 的容量至少应该是（ ）。