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

一、单项选择题

1．

对

（ ）。

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

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

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

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

【答案】A

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

2． 某计算机的Cache 共有16块，采用2路组相联映射方式(即每组2块). 每个主存块大小为32字节，按字节编址. 主存129号单元所在主存块应装入到的Cache 组号是（ ）.

A.0

B.2

C.4

D.6

【答案】C

【解析】首先根据主存地址计算所在的主存块号，然后根据组相联映射的映射关系K ＝ImodQ(K代表Cache 的组号，I 代表主存的块号，Q 代表Cache 的组数) 来计算Cache 的组号. 由于每个主存块大小为32字节，按字节编址，那么主存129号单元所在的主存块号是4，Cache 共有16块，采用2路组相联映射方式(即每组2块) ，故Cache 有8组，按照上面的公式可以计算得到Cache 的组号＝4mod8＝4.

3． 下面关于串的叙述中，不正确的是（ ）。

A. 串是字符的有限序列

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

B. 空串是由空格构成的串

C. 模式匹配是串的一种重要运算

D. 串既可以采用顺序存储，也可以采用链式存储

【答案】B

【解析】空格构成的串称空格串。空串用表示。零个字符的串称为空串，空格也是一个字符，因此B 项不正确。

4． 设无向图的顶点个数为m 则该图最多有（ ）条边。

A.n-1 B. C.

D.0E.n2

【答案】B

【解析】在数据结构中仅讨论简单图，在计算无向图的最多边时，不考虑顶点与顶点的边。因此边数最多时，构成的是无向完全图。此时的边数为。

5． 动态存储管理系统中，通常可有（ ）种不同的分配策略。

A.1

B.2

C.3

D.4

E.5

【答案】C

【解析】动态存储管理系统中有以下三种:首次拟合法、最佳拟合法、最差拟合法。①首次拟合法，从表头指针开始查找可利用空间表，将找到的第一个大小不小于n 的空闲块的一部分分配给用户。②最佳拟合法，将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给用户。则系统在分配前首先要对可利用空间表从头到尾扫视一遍，然后从中找出一块不小于n 且最接近n 的空闲块进行分配。③最差拟合法，将可利用空间表中不小于n 且是链表中最大的空闲块的一部分分配给用户。

6． 下列因素中, 不会影响信道数据传输速率的是（ ）

A. 信噪比

B. 频率宽带

C. 调制速率

D. 信号传播速度

【答案】D

【解析】信道数据传输速率与信噪比、频率宽度、调制速率都有关。

7． 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ）。

A. 直接插入排序

B. 起泡排序

C. 简单选择排序

D. 快速排序

【答案】A

【解析】当待排序列基本有序时，对冒泡排序来说，若最大关键字位于序列首部，则每趟排序仅能使其“下沉”一个位置，要使其下沉到底部仍需n －1趟排序，也即时间复杂度仍为0(n2)。而对简单选择排序来说，其比较次数与待排序列的初始状态无关；归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时间复杂度为；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，也

2即n －1趟，比较的时间复杂度由O(n) 降至O(n)。

8． 和顺序栈相比，链栈有一个比较明显的优势是（ ）。

A. 通常不会出现栈满的情况

B. 通常不会出现栈空的情况

C. 插入操作更容易实现

D. 删除操作更容易实现

【答案】A

9． 图的BFS 生成树的树高比DFS 生成树的树高（ ）。

A. 小或相等

B. 小

C. 大或相等

D. 大

【答案】A

【解析】BFS 称作广度优先搜索，DFS 称作深度优先搜索。广度优先搜索类似与二叉树的层序遍历算法，深度优先搜索类似于树的先序遍历。因为深度优先搜索算法遵循的策略是尽可能的“深”地搜索一个图。所以图的BFS 生成树的树髙比DFS 生成树的树高小或者相等。

10．如果本地域名服务无缓存，当采用递归方法解析另一网络某主机域名时，用户主机、本地域名服务器发送的域名请求消息数分别为（ ）.

A.1条，1条

B.1条，多条

C. 多条，1条

D. 多条，多条