2018年中国科学技术大学软件学院834软件工程基础[专业硕士]之数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 下列选项中，操作系统提供的给应用程序的接口是（ ）.
A. 系统调用
B. 中断
C. 库函数
D. 原语
【答案】A
【解析】操作系统提供给用户应用程序的接口只有两种:命令输入和系统调用. 其中，命令输入又有不同的形式，例如常规的命令行、图形化人机交互接口(GUI)、自然命令用户接口(NUI)等，而系统调用中除了常规的一些传统的系统调用(例如read （ ）) 以外，还有经过扩展的复杂调用(例如多种API) ，以及包含在Lib 库中的各种封装好的过程调用(最终都是通过系统调用陷入到操作系统中去的）等.
2． 下面关于B 和B+树的叙述中，不正确的是（ ）
A.B 树和B+树都是平衡的多叉树
B.B 树和B+树都可用于文件的索引结构
C.B 树和B+树都能有效地支持顺序检索
D.B 树和B+树都能有效地支持随机检索
【答案】C
【解析】B 树是一种平衡的多分树，通常我们说m 阶的B 树，它必须满足如下条件:①每个结点至多有m 个子结点；②除根结点和叶结点外，其它每个结点至少有个子结点；③若根结点不是叶子结点，则至少有两个子结点；④所有的叶结点在同一层；⑤有k 个子结点的非根结点恰好包含k －1个关键码。B+树是B 树的一种变形树，它与B 树的差异在于:有k 个子结点的结点必然有k 个关键码；非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。其中B 树适合与随即检索，不适合于顺序检索，所以C 项错误。
3． 某计算机主存容量为64KB ，其中ROM 区为4KB ，其余为RAM 区，按字节编址. 现要用2K ×8位的ROM 芯片和4K ×4位的RAM 芯片来设计该存储器，则需要上述规格的ROM 芯片数和RAM 芯片数分别是（ ）
A.1、15
B.2、15
C.1、30
D.2、30
【答案】D
【解析】主存储器包括RAM 和ROM 两部分，由于ROM 区为4KB ，则RAM 区为60KB. 存储容量的扩展方法有字扩展、位扩展、字和位同时扩展三种. 选用2Kx8位的ROM 芯片，只需采用2片芯片进行字扩展便可得到4KB 的ROM 区；选用4Kx4位的RAM 芯片，需采用(60)/4*2片芯片进行字和位同时扩展便可得60KB 的RAM 区.
4． 下列关于银行家算法的叙述中, 正确的是（ ）
A. 银行家算法可以预防死锁
B. 当系统处于安全状态时, 系统中一定无死锁进程
C. 当系统处于不安全状态时, 系统中一定会出现死锁进程
D. 银行家算法破坏了死锁必要条件中的“请求和保持”条件
【答案】B
【解析】银行家算法是避免死锁的方法。利用银行家算法, 系统处于安全状态时没有死锁进程, 故答案选B 。
5． 为提高散列(Hash)表的查找效率, 可以采用的正确措施是（ ）。
Ⅰ. 增大装填(载) 因子
Ⅱ. 设计冲突(碰撞) 少的散列函数
Ⅲ. 处理冲突(碰撞) 时避免产生聚集(堆积) 现象
A. 仅Ⅰ
B. 仅Ⅱ
C. 仅Ⅰ、Ⅱ
D. 仅Ⅱ、Ⅲ
【答案】D
【解析】散列表的查找效率(比较次数) 取决于:散列函数、处理冲突的方法和散列表的装填因子α。α标志着散列表的装满程度, 通常情况下, α越小, 发生冲突的可能性越小; 反之, α越大, 表示已填入的记录越多, 再填入记录时, 发生冲突的可能性越大。因此选项Ⅰ错误, 越是增大装填因子, 发生冲突的可能性就越大, 查找效率也越低。选项Ⅱ正确。选项Ⅲ正确。采用合适的处理冲突的方法避免产生聚集现象, 也将提高查找效率。例如, 用拉链法解决冲突时不存在聚集现象, 用线性探测法解决冲突时易引起聚集现象。
6． 下列程常段的时间复杂度是（ ）
A.O()
B.O(n) C.O() D.O()
【答案】C
【解析】外部循环的退出条件是k>n, 而对于k , 每次循环都执行
内部循环的退出条件是j>n, 对于j , 每次循环都执行
) , 即选C 。 段的时间复杂度为O(
7． 稀疏矩阵一般的压缩存储方法有两种，即（ ）。
A. 二维数组和三维数组
B. 三元组和散列
C. 三元组和十字链表
D. 散列和十字链表
【答案】C
【解析】稀疏矩阵一般的压缩方法为三元组表和十字链表。三元组表就是将非零元素及其对应的行和列构成一个三元组(行标，列标，值) 。十字链表相比三元组表而言，主要是对每个结点增加了两个链域。如果数组经常运算时，会产生大量数据元素的移动，此时，采用链表存储结构更为恰当。
8． 一棵3阶B-树中含有2047个关键字，包括叶结点层，该树的最大深度为（ ）。
A.11
B.12
C.13
D.14
【答案】B
9． 折半查找的时间复杂性为（ ）。 A.
B.O(n) C. D.
【答案】D
【解析】顺序查找的事件复杂度为, 因为折半查找是查找效率最髙的算法，它的事件复杂度为。
10．在有向图G 的拓扑序列中，若顶点在顶点之前，则下列情形不可能出现的是（ ）。
A.G 中有弧
B.G 中有一条从到的路径
, 所以循环次数为; , 所以每次循环次数为n 次。所以此程序