当前位置：问答库＞考研试题

一、填空题

1． 在单链表L 中，指针P 所指结点有后继结点的条件是_____

【答案】P ﹣＞next! ＝NULL

【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。

2． 中缀式(c-d)对应的前缀式为_____，若a=l，b=2, c=3, d=4, 则后缀式的运算结果为_____。 【答案】

【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。

3． 栈是_____的线性表，其运算遵循_____的原则。

【答案】操作受限(或限定仅在表尾进行插入和删除操作) ；后进先出

4． 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。 【答案】

【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺序查找效率一样为。

5． 阅读下列程序说明和程序，填充程序中的_____。

【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示。

本程序采用非递归的方法，设立一个堆栈stack 存放还没有转换过的结点，它的栈顶指针为tp 。交换左、右子树的算法为:

(1)把根结点放入堆栈。

(2)当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。

(3)重复(2)直到堆栈为空时为止。

第 2 页，共 79 页

【答案】

【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈是否为空，如果不为空，则取栈顶元素，交换取出结点的左右指针。并将左右指针分别进栈，重复这一操作。完成二叉树左右孩子的交换。

6． 模式串的next 函数值序列为_____。

【答案】01122312

7． —个有2001个结点的完全二叉树的高度是_____。

【答案】11

【解析】完全二叉树的高度

8． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。

【答案】顺序

【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。

9． 空格串是指_____，其长度等于_____。

【答案】由空格字符(ASCII值32) 所组成的字符串；空格个数

10．建立索引文件的目的是_____。

【答案】提高查找速度

二、单项选择题

11．进程P0和P1的共享变量定义及若进程P0和P1访问临界资源的类C 伪代码实现如下:

第 3 页，共 79 页

则并发执行进程P0和PI 时产生的情况是（ ）.

A. 不能保证进程互斥进入临界区，会出现“饥饿”现象

B. 不能保证进程互斥进入临界区，不会出现“饥饿”现象

C. 能保证进程互斥进入临界区，会出现“饥饿”现象

D. 能保证进程互斥进入临界区，不会出现“饥饿”现象

【答案】D

【解析】这是皮特森算法(Peterson’SAlgorithm)的实现，保证进入临界区的进程合理安全. 该算法为了防止两个进程为进入临界区而无限期等待，设置变量tum ，表示不允许进入临界区的编号，每个进程在先设置自己标志后再设置turn 标志，不允许另一个进程进入，这时，再同时检测另一个进程状态标志和不允许进入标志，这样可以保证当两个进程同时要求进入临界区时只允许一个进程进入临界区. 保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入. 先到先人，后到等待，从而完成临界区访问的要求.

12．在物理层接口特性中, 用于描述完成每种功能的事件发生顺序的是（ ）。

A. 机械特性

B. 功能特性

C. 过程特性

D. 电气特性

【答案】C 。

【解析】物理层的主要任务描述为确定与传输媒体接口的一些特性; 机械特性:主要定义物理连接的边界点, 即接插装置; 电气特性:规定传输二进制位时, 线路上信号的电压高低、阻抗匹配、传输速率和距离限制; 功能特性:主要定义各条物理线路的功能; 规程特性:主要定义各条物理线路的工作规程和时序关系。而从题干可以分析描述事件先后顺序的就是规程, 也就是过程特性, 答案是C 。

13．主机甲与主机乙之间已建立一个TCP 连接, 主机甲向主机乙发送了3个连续的TCP 段, 分别包含300字节、400字节和500字节的有效载荷, 第3个段的序号为900。若主机乙仅正确接收到第1和第3个段, 则主机乙发送给主机甲的确认序号是（ ）。

A.300

B.500

C.1200

第 4 页，共 79 页