2018年南开大学计算机与控制工程学院816C语言与数据结构[专业硕士]考研强化五套模拟题
● 摘要
一、填空题
1． 文件可按其记录的类型不同而分成两类，即 _____和_____文件。
【答案】操作系统文件；数据库
2． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，
请在算法空格处填上正确的语句。 设线索二叉树的结点数据结构为其中:
left 指向其左孩子，
【答案】
left 指向其前驱；，
right 指向其后继。
，
right 指向其右孩子，，
，
3． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
4． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
a 中存放待排序的关键字
【答案】
【解析】快速排序(quick sort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
5． 循环队列的引入，目的是为了克服_____。
【答案】假溢出时大量移动数据元素
【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。
6． 外排序的基本操作过程是_____和_____。
【答案】生成有序归并段(顺串) ；归并
7． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关，即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。
【答案】逻辑特性；在计算机内部如何表示和实现；数学特性
8． 已知一循环队列的存储空间为则此循环队列判满的条件是_____
【答案】
9． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。
【答案】要加“虚结点”。
，其中n ＞m ，队头和队尾指针分别为front 和rear ，
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
设编号为i 和j 的结点在顺序存储中的下标为s 和t , 则结点i 和j 在同一层上的条件是
。
10．设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f(m，n) 为这种表示方式的数目。例f(5，3) ＝5, 有5种表示方式:3＋2, 3＋1＋1，2＋2＋1，2＋1＋1＋1，1＋1＋1＋1＋1。
①以下是该函数的程序段，请将未完成的部分填入，使之完整。
_____
_____；
}
_____；
}
，
_____)
②执行程序，f(6，4) ＝_____。 【答案】①1; 1; f(m, n ﹣1) ; n ②9
二、单项选择题
11．循环两列放在一维数组
中, end1指向队头元素, end2指向队尾元素的后一个位置。
假设队列两端均可进行入队和出队操作, 队列中最多能容纳M-1个元素。初始时为空, 下列判断队空和队满的条件中, 正确的是（ ）
A. 队空:endl==end2; 队满:endl==(end2+l)modM B. 队空Gendl==end2; 队满:Gend2==(endl+1)mod(M-1) C. 队空Gend2==(endl+1)modM; 队满:Gendl==(end2+l)modM D. 队空:【答案】A
【解析】在循环队列中, 在少用一个元素空间的前提下, 可约定入队前, 测试尾指针在循环意义下加1后是否等于头指针, 若相等, 则队满。而队空的条件还是首尾指针是否相等。
12．计算机开后, 操作系统最终被加载到（ ）
A.BIOS B.ROM C.EPROM D.RAM 【答案】D
【解析】系统开机后, 操作系统的程序会被自动加载到内存中的系统区, 这段区城是RAM , 故
队满: