2017年北京服装学院服装设计与工程917程序设计与算法考研强化模拟题
● 摘要
一、填空题
1． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
2． 设有两个算法在同一机器上运行，其执行时闻分别为_____。
【答案】15 【解析】当
3． 线性表
时，
而
，
时，
要使前者快于后者，n 至少为
用数组表示，假定删除表中任一元素的概率相同，则删除一个元素
平均需要移动元素的个数是_____。
【答案】（n －1）/2
【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为
4． 在有n 个顶点的有向图中，每个顶点的度最大可达。
【答案】2（n-l ）
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。
5． 模式串的next 函数值序列为_____。
【答案】01122312
6． 实现字符串拷贝的函数strcpy 为：
【答案】
7． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
8． 在二叉树中，指针p 所指结点为叶结点的条件是_____。
【答案】
【解析】叶子节点的左右孩子都不存在。
9． —棵有个结点的满二叉树有_____个度为1的结点、有_____个分支（非终端）结点和_____个叶子，该满二叉树的深度为_____。
【答案】
或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
10．文件可按其记录的类型不同而分成两类，即_____和_____文件。
【答案】操作系统文件；数据库
11．属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
12．以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
【答案】（1）链表未到尾就一直进行
（2）
将当前结点作为头结点后的第一元素结点插入
二、选择题
13．—个栈的入栈序列为的个数是（ ） A.n-3 B.n-2 C.n-1
D. 无法确定
【答案】C
【解析】除了3本身以外，其他的值均可以取到，因此可能取值的个数为n-1。
14．若某通信链路的数据传输速率为采用4相位调制，则该链路的波特率是（ ）。
A.600波特 B.1200波特 C.4800波特 D.9600波特 【答案】B
其出栈序列是若，则则可能取值
【解析】注意无噪声下的码元速率极限值B 与信道带宽H 的关系：B = 2xH （Baud ）, 而奈奎斯特公式一无噪信道传输能力公式是而可以得到波特率与数据传输速率的关系，即
N 为一个码元所取的离散值个数。从
在本题中数据传输速率C = 2400,
N=4，因此波特率是1200, 答案是B 。
15．若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ ）。
A.257 B.258 C.384 D.385 【答案】C
【解析】由
：_
则
和
_
_可知
，
即
显然
384, 所以二叉树的叶结点个数是384。还可以根据完全二叉树的另一个
性质：最后一个分支结点的序号为[768/2], 故非叶子结点数为384, 而叶子结点的个数为768-384=384。（[x]表示不大于x 的最大整数，比如[3.14] =3）。
16．
用户程序发出磁盘请求后，系统的处理系统的处理流程是：用户程序一系统调用处理程序一设备骆动程序一中断处理程序。其中，计算数据所在磁盘的柱面号、磁头号、扇区号的程序是（ ）
A. 用户程序 B. 系统调用处理程序 C. 设备驱动程序 D. 中断处理程序 【答案】C
【解析】计算磁盘号、磁头号和扇区号的工作是由设备驱动程序完成的，所以答案选C 。
17．中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是（ ）。
A. 程序计数器 B. 程序状态字寄存器 C. 通用数据寄存器 D. 通用地址寄存器 【答案】B 。
【解析】中断处理与子程序调用最大的区别是中断处理程序与正在运行的进程可能无关，而子程序调用与正在运行的进程有关。中断是要打断处理器的正常工作次序，并要求其去处理某一事件的一种常用手段。因此，除了要保护当前程序的地址，计数器（指针）和数据寄存器以外，还需要保存程序状态字。子程序调用是与当前进程有关，是正在运行的程序有意安排执行的，这一类调用发生的时间以及位置具有确定性，处于同一个进程内，因此不需要保存程序状态字。所