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

一、单项选择题

1． 将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和v 可能具有的关系是（ ）.

(1)父子关系

(2)兄弟关系

(3)U的父结点与V 的父结点是兄弟关系

A. 只有(1)

B.(1)和(2)

C.(1)和(3)

d.(1)、(2)和(3)

【答案】B

【解析】首先，在二叉树中，若结点U 是结点v 的父结点的父结点，那么u 和v 的关系有如下4种情况：

接下来，根据森林与二叉树的转换规则，将这4种情况还原成森林中结点的关系. 其中： 情况(1)，在原来的森林中u 是v 的父结点的父结点；

情况(2)，在森林中u 是v 的父结点；

情况(3)，在森林中u 是v 的父结点的兄弟；

情况(4)，在森林中u 与v 是兄弟关系.

由此可知，题目中的(1)、(2)是正确的.

2． 设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作（ ）。

A. 求子串

B. 判断是否相等

C. 模型匹配

D. 连接

【答案】C

【解析】常用的串的基本操作有七种，INDEX(s，t) 是其中的定位函数，这种运算就是所说的模式匹配。

3． 在一棵度为4的树T 中, 若有20个度为4的结点, 10个度为3的结点, 1个度为2的结点, 10个度为1的结点, 则树T 的叶结点个数是（ ）。

A.41

B.82

C.113

D.122

【答案】B

【解析】根据二叉树的性质3的推广公式:

式, 即

。

树T 的叶子结点的个数是82。

4． 先序序列为a , b , c , d 的不同二叉树的个数是（ ）。

A.13

B.14

C.15

D.16

【答案】B

【解析】二叉树的先序遍历定义为:若二叉树为空, 则空操作; 否则, 访问根节点, 然后先序遍历左子树, 最后先序遍历右子树。本题中, 结点a 为二叉树的根节点, 左右子树的先序遍历可能存在下面四种情况:

①左子树为空, bcd 为右子树; ②b 为左子树, cd 为右子树; ③bc 为左子树, d 为右子树; ④bcd 为左子树, 右子树为空。

然后将左右子树继续分解, 如第①种情况的右子树先序遍历(bcd)可能有:

A. 左子树为空, 右子树为cd ;

b. 左子树为c , 右子树为d ;

c. 左子树为cd , 右子树为空。

按照这种方法继续分解左右子树, 直到不能再分解为止, 可得第①和④种情况各包含5种不同情况, 第②和③种情况各包含2种情况, 因此总共有14种不同的二叉树。

5． 下列选项中, 属于多级页表优点的是（ ）

A. 加快地址变换速度

B. 减少缺页中断次数

C. 减少页表项所占字节数

D. 减少页表所占的连续内存空间

【答案】D

可直接在将数据带入公

【解析】多级页表避免了把所有的页表一直保存在内存中

6． 文件系统中，文件访问控制信息存储的合理位置是（ ）.

A. 文件控制块

B. 文件分配表

C. 用户口令表

D. 系统注册表

【答案】A

【解析】文件控制块是文件存在的标志，文件的相关信息(基本信息、存取控制信息以及使用信息) 都存储在文件控制块中，系统对文件的管理全是依靠文件控制块里的信息.

7． 假定下列指令已装入指令寄存器。则执行时不可能导致CPU 从用户态变为内核态(系统态) 的是（ ）。 A.

B. ; 产生软中断 C. ; 寄存器R0的内容取非 D.MOVRO , addr ; 把地址处的内存数据放入寄存器RO 中

【答案】C

【解析】A 项, 除法操作出现除数为零的情况时, 会产生内中断, CPU 切换为内核态进行中断处理; B 项, 直接产生中断, 会切换到内核态; D 项, addr 出现非法地址, 会出现中断, 进而切换到内核态。

8． 排序算法的稳定性是指（ ）。

A. 经过排序之后，能使值相同的数据保持原顺序中的相对位置不变

B. 经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变

C. 算法的排序性能与被排序元素的数量关系不大

D. 算法的排序性能与被排序元素的数量关系密切

【答案】A

【解析】假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=tj，且ri 在ij 之前，而在排序后的序列中，ri 仍在rj 之前，则称这种排序算法是稳定的；否则称为不稳定的。

9． 下列排序算法中，其中（ ）是稳定的。

A. 堆排序，起泡排序

B. 快速排序，堆排序

C. 直接选择排序，归并排序

D. 归并排序，起泡排序