2017年河北工业大学计算机科学与软件学院803数据结构与程序设计[专业学位]考研仿真模拟题
● 摘要
一、填空题
1． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。
【答案】2
【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。
2． 表达式的后缀表达式是_____。 【答案】
3． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
4． 建立索引文件的目的是_____。
【答案】提高查找速度
5． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。 【答案】
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。
6． 无用单元是指_____，例_____
【答案】用户不再使用而系统没有回收的结构和变量；
7． 在循环队列中，队列长度为n ，存储位置从0到，
【答案】 编号，以rear 指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是（ ）。
8． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关, 即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。
【答案】逻辑特性；在计算机内部如何表示和实现；数学特性
9． 二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
10．克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。
【答案】O （eloge ）; 边稀疏
11．在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。 【答案】
12．对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4; 2
二、选择题
13．组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为（ ）。 A. B. C. D.
【答案】B
【解析】因组与组之间已有序，故将个组分别排序即可，基于比较的排序方法每组的时
间下界为
0全部时间下界为
14．为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。
A. 栈
B. 队列
C. 树
D. 图
【答案】B
【解析】这类问题一般都先分析题目中的数据具有什么操作特性或是结构特性比如“先进后出”、“先进先出”等再判断其逻辑结构。栈和队列是操作受限的线性表，栈具有先进后出的特性而队列具有先进先出的特性。由于本题中先进入打印数据缓冲区的文件先被打印，因此打印数据缓冲区具有先进先出性，则它的逻辑结构应该是队列。
15．某计算机主存容量为64KB , 其中ROM 区为4KB , 其余为RAM 区，按字节编址。现要用2Kx8位的ROM 芯片和4Kx4位的RAM 芯片来设计该存储器，则需要上述规格的ROM 芯片数和RAM 芯片数分别是（ ）。
A.1、15
B.2、15
C.1、30
D.2、30
【答案】D
【解析】主存储器包括RAM 和ROM 两部分，由于ROM 区为4KB ，则RAM 区为60KB 。存储容量的扩展方法有字扩展、位扩展、字和位同时扩展三种。选用2Kx8位的ROM 芯片，只需
/4*2采用2片芯片进行字扩展便可得到4KB 的ROM 区；选用4Kx4位的RAM 芯片，需采用（60）
片芯片进行字和位同时扩展便可得60KB 的RAM 区。
16．假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入哈希表中，至少要进行多少次探测？（ ）
【答案】D
【解析】至少探测次数
17．，某基于动态分区存储管理的计算机，其主存容量为55MB （初始为空闲）采用最佳适配（Bestfit ）算法，分配和释放的顺序为：分配15MB 、分配30MB 、释放15MB 、分配8MB 、分配6MB , 此时主存中最大空闲分，区的大小是（ ）。
A.7MB
B.9MB
C.10MB
D.15MB
【答案】B
【解析】对于简单分区内存分配，需要将进程的所有代码和数据装入内存。故55MB 先分配15MB 余40MB , 再分配30MB 后余10MB , 释放15MB 后出现一个15MB 和一个10MB 的空闲空间，分配8MB 时按最佳适配（BestFit ）算法应该使用10MB 的空闲块，余2MB 的碎片，分配6MB
，因此最大空闲区为9MB 。 时占用15MB 的空间余9MB 的碎片（空闲空间）
18．将一个的三对角矩阵，按行优先存入一维数组中，A 中元素（即该元素下标
A.198
B.195
C.197
【答案】B 在B 数组中的位置K 为（ ）。
【解析】将对角矩阵存入
19．栈和队的共同点是（ ）。
A. 都是先进后出
B. 都是后进先出 三对角矩阵压缩地址计算公式如下：