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

一、填空题

1． n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。

注：（1）图的顶点号从0开始计；

（2）indegree 是有n 个分量的一维数组，放顶点的入度， （3）函数crein 用于记算顶点入度；

（4）有三个函数push （data ）, pop（ ）, check（ ）其含义为数据data 入浅，出栈和测试栈是否空（不空返回1, 否则0）。

）

.

【答案】0; j; i; 0; indegree[i]=0; [vex][i]; k==l; indegree[i]=0

【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程：首先将入度 为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的 入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。

2． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。

【答案】2

【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。

3． —个字符串中_____称为该串的子串。

【答案】任意个连续的字符组成的子序列

；

（“图有回路”）

4． 设有两个算法在同一机器上运行，其执行时闻分别为_____。

【答案】15

【解析】当时，而，

5． 实现字符串拷贝的函数strcpy 为：

时，

要使前者快于后者，n 至少为

【答案】

6． 设为哈夫曼树的叶结点数日，则该哈夫曼树共有_____个结点。

【答案】

【解析】哈夫曼树只有度为0和2的节点。 7． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度，当它为一棵_____ 时. 具有最大高度

【答案】完全；只有一个叶结点的二叉树

8． 已知一循环队列的存储空间为环队列判满的条件是（ ）

【答案】

编号，以rear 指示实际的队尾元素，现

9． 在循环队列中，队列长度为n ，存储位置从0到，

【答案】

其中

队头和队尾指针分别为front 和rear , 则此循

要在此队列中插入一个新元素，新元素的位置是（ ）。

10．数组的存储结构采用_____存储方式。

【答案】顺序存储结构

【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。

二、选择题

11．设有一棵3阶B 树，如题图所示。删除关键字78得到一棵新B 树，其最右叶结点所含的关键字是（ ）。

题图二叉树图

A.60 B.60, 62 C.62, 65 D.65 【答案】D 。

【解析】本题主要考查B 树删除操作。即被删关键字所在的结点中的关键字个数等于而与该结点相邻的右兄弟（或左兄弟）结点中的关键字数目大于

则需将其兄弟结点中最

小（或最大）的关键字上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠该上移关键字的关键字下移至被删关键字所在结点中。题目中删除关键字78得到一棵新B 树如下，其最右叶结点所含的关键字是65。

12．下列寄存器中，汇编语言程序员可见的是（ ）。

A. 存储器地址寄存器（MAR ） B. 程序计数器（PC ）

C. 存储器数据寄存器（MDR ） D. 指令寄存器（IR ） 【答案】B

【解析】CPU 有5个专用寄存器，它们是程序计数器（PC ）、指令寄存器OR ）、存储器地址，这些寄存器中有些寄存器（MAR ）、 存储器数据寄存器（MBR ）和状态标志寄存器（PSWR ）是CPU 的内部工作寄存器，对汇编语言程序员来说是透明的，在汇编语言程序设计中不会出现。但汇编语言程序员可以通过制定待执行指令的地址来设置PC 的值，所以程序计数器（PC ）对于汇编语言程序员可见的。

13．采用开址定址法解决冲突的哈希查找中，发生集聚的原因主要是（ ）。

A. 数据元素过多 B. 负载因子过大 C. 哈希函数选择不当 D. 解决冲突的算法选择不好 【答案】D

【解析】开放定址法就是从发生冲突的那个单元开始，按照一定的次序，从散列表中查找出一个空闲的存储单元，把发生冲突的待插入元素存入到该单元中的一类处理冲突的方法。

14．分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。