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

一、选择题

1． 用海明码对长度为8位的数据进行检/纠错时，若能纠正一位错，则校验位数至少为（ ）

A.2 B.3 C.4 D.5

【答案】C

【解析】设校验位的位数为k ，数据位的位数为n ，根据海明码编码k 和n

应满足下述关系。

当k=4时，

2．

对（ ）。

A. 该树一定是一棵完全二叉树 B. 树中一定没有度为1的结点

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

D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值 【答案】A

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

3． 一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是（ ）。

A. B. C. D.

字节

字节

字节

字节

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

符合要求，校验位至少是4位，故答案为C 。

【答案】C

【解析】段内位移的最大值就是最大段长。段号长度占了8位，剩下32-8=24位是段内位移空间，因此最大段长为

B 。

4． 对序

列

A.1 B.4 C.3 D.2

【答案】B

用希尔排序方法排序，经一趟后序列变

为

则该次采用的增量是（ ）。

【解析】由所给的序列知，本序列要进行递增排序，经过一趟后15的位置没有变化，而给的序列中只有20比15大，20的位置和15的位置相差4。所以该次采用的増量是4。

5． 设被排序的结点序列共有N 个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为（ ）。

【答案】C

【解析】因为该序列中的结点已经十分接近排序的情况，对于直接插入法，大部分结点只需要直接插入后面即可，因此时间复杂度为的时间复杂度为

对于采用归并法，它是一种稳定的排序方法，它

对于一般的快速排序法，序列越接近有序，所需要的比较次数越多，

此时的时间复杂度为

6． 下列选项中，会导致用户进程从态切换到内核的操作是（ ）

I. 整数除以零 II. Sin（ ）函数调用 III. read系统调用 A. 仅 I 、II B .仅 I 、III C. 仅II 、III D. I、II 和III 【答案】B

【解析】对于I ，系统发生异常，需要进入内核态由操作系统进行处理，而read 系统调用函数也是在内核态执行，sin （ ）就是普通的用户函数，在用户态执行，故答案为C 。

7． 假定一台计算机的显示存储器用DRAM 芯片实现，若要求显示分辨率为1600x1200, 颜色深度为24位，帧频为85Hz , 显存总带宽的50%用来刷新屏幕，则需要的显存总带宽至少约为（ ）。

A.245Mbps B.979Mbps

C.

D. 【答案】D

【解析】显存的容量=分辨率×色深，带宽=分辨率×色深×帧频，考虑到

的时间用来刷新

1600×1200×24×85×2＝7834Mbps 屏幕，故显存总带宽应加倍。所以需要的显存总带宽至少约为：

8． 已知三叉树T 中6个叶结点的权分别是2，3, 4, 5，6，7, T的带权（外部）路径长度最小是（ ）

A.27 B.46 C.54 D.56

【答案】B

【解析】利用三叉树的6个叶子结点的权构建最小带权生成树，

最小的带权路径长度为

9． 栈和队的共同点是（ ）。

A. 都是先进后出 B. 都是后进先出

C. 只允许在端点处插入和删除元素 D. 没有共同点 【答案】C

【解析】栈和队列的区别是栈是先进后出的数据结构，队列是先进先出的数据结构，栈和队列的共同点是都只能在端点处插入和删除元素。

10．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。

A. 插入 B. 选择 C. 希尔 D. 二路归并 【答案】A

【解析】解此题需要熟知各种排序方法的基本思想。插入排序的基本思想是：假设待排序的

记录存放在数组

中，排序过程的某一中间时刻，R

被划分成两个子区间

插入到有序区

和

其中：前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨

称其为无序区。将当前无序区的第1

个记录

11．

若

A.x+y B.-x+y C.x-y D.-x-y

【答案】C

中适当的位置上。使

变为新的有序区。这种方法通常称为增量法，因为它每次使有序区增加1个记录。

则下列表达式采用8位定点补码运算实现时，会发生溢出的是（ ）