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

一、选择题

1． 用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为

趟排序采用的增量（间隔）可能是（ ）

A.2

B.3

C.4

D.5

【答案】B

【解析】对于A , 增量为2, 那么9, 4, 7, 20, 15是一组，而它们是无序的，所以A 错误

对于C , 增量为4, 那么9, 7，15是一组，而它们是无序的，所以C 错误

对于D , 增量为5, 那么9, 8是一组，降序，1，20是一组，而它们是升序，所以D 也错误。对于B ，分为3组：都是升序有序，所以B 正确

2． 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。

A. 单链表

B. 仅有头指针的单循环链表

C. 双链表

D. 仅有尾指针的单循环链表

【答案】D

【解析】仅有尾指针的单循环链表，在最后插入元素和删除第一个元素都会用到这个尾指针。

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

A.13

B.14

C.15

D.16

【答案】B

【解析】二叉树的先序遍历定义为：若二叉树为空，则空操作；否则，访问根节点，然后先序遍历左子树，最后先序遍历右子树。本题中，结点a 为二叉树的根节点，左右子树的先序遍历可能存在下面四种情况：①左子树为空，bed 为右子树；②b 为左子树，cd 为右子树；③be 为左子树，d 为右子树；④bed 为左子树，右子树为空。然后将左右子树继续分解，如第①种情况的右子树先序遍历（bed ）可能有：a. 左子树为空，右子树为cd ；b. 左子树为c ，右子树为d ；c. 左子树为cd ，右子树为空。按照这种方法继续分解左右子树，直到不能再分解为止，可得第①和④种情况各包含5种不同情况，第②和③种情况各包含2种情况，因此总共有14种不同的二 叉树。

则该

4． 主机甲通过1个路由器个路由器（存储转发方式）与主机乙互联，两段链路的数据传输速率均为10Mbps ，主机甲分别采用报文交换和组大小为10kb 的分组交换向主机乙发送1

个大小为

的报文。若忽略链路传播延迟、分组头开销和拆装时间，则两种交换方式完成该

报文传输所需的总时间分别为（ ）

A.800ms> 1600ms

B.801ms 、1600ms

C.1600ms 、800ms

D.1600ms 、801ms

【答案】D

【解析】不进行分组时，发送一个报文的时延是

的时延也是800ms 共计1600ms 。进行分组后发送一个报文的时延是在接收端接收此报文件接收一个报文的时延也是1ms ，但是在发送第二个报文时，第一个报文已经开始接收。共计有800个分组，总时间为801 ms。

5．

对个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是（ ）。

A. 该树一定是一棵完全二叉树

B. 树中一定没有度为1的结点

C. 树中两个权值最小的结点一定是兄弟结点

D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值

【答案】A

【解析】哈夫曼树为带权路径长度最小的二叉树，但不一定是完全二叉树，选项A 错误；哈夫曼树中没有度为1的结点，选项B 正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树，C 正确；哈夫曼树中任一非叶结点P 的权值为其左右子树根结点权值之和，其权值不小于其左右子树根结点的权值，在与结点P 的左右子树根结点处于同一层的结点中，若存在权值大于结点P 权值的结点Q ，那么结点Q 与其兄弟结点中权值较小的一个应该与结点P 作为左右子树构造新的二叉树，由此可知，哈夫曼树中任一非叶结 点的权值一定不小于下一层任一结点的权值。

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

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

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

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

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

【答案】A

【解析】假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这

些记录的相对次序保持不变，即在原序列中，

且在之前，而在排序后的序列中，仍在之前，则称这种排序算法是稳定的；否则称为不稳定的。

7． 假定主存地址为32位，按字节编址，主存和Cache 之间采用直接映射方式，主存块大小为4个字，每字32位，采用回写（WriteBack ）方式，则能存放4K 字数据的Cache 的总容量的位数至少是（ ）。

A.146k

B.147K

C.148K

D.158K

【答案】B

【解析】Cache 和主存直接映射方式的规则为：主存储器分为若干区，每个区与缓存容量相同；每个区分为若干数据块，每个块和缓存块容量相同；主存中某块只能映象到Cache 的一个特定的块中。本题中，Cache 总共存放4K 字数据，块大小为4个字，因此cache 被分为4K/4 = 1K 个块，由10位表示。块内共16字节，所以由4位表示，于是标记位为32-10-14= 18位。所以，Cache 的每一行需要包含所存的数据4个字，每个字32位，18位标记位和一个有效位，因此总容

=147K。 量为：

8． —个进程的读磁区操作完成后，操作系统针对该进程必做的是（ ）

A. 修改进程状态为就绪态

B. 降低进程优先级

C. 进程分配用户内存空间

D. 增加进程的时间片大小

【答案】A

【解析】进程等待的操作完成便会从等待状态转移到就绪状态。

9． 下列选项中，在总线的数据线上传输的信息包括（ ）。

I. 接口中的命令字

II. 接口中的状态字III. 中断类型号

A. 仅 I 、II

B. 仅 I 、III

C. 仅 II 、III

D.I 、II 、III

【答案】D 。

【解析】

在

总线的数据线上传输的信息包括接口中的命令字、状态字以及真正的数据，而中断类型号也是通过数据线传输的。

10．归并排序中，归并的趟数是（ ）。