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

一、填空题

1． 在单链表中设置头结点的作用是_____。

【答案】方便运算

2． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。

【答案】

【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。

3． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。

【答案】出度为0

【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最 后一个顶点的出度必定为零。

4． 文件可按其记录的类型不同而分成两类，即_____和_____文件。

【答案】操作系统文件；数据库

5． 外排序的基本操作过程是_____和_____。

；归并 【答案】生成有序归并段（顺串）

6． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。

Prior （node , x ） { if（node !=null）

If （ （1） ） *x=node->right；else * x-node->left;

}

next （bt , node, x ）/*bt是二叉树的树根*/ { （2） ;

if （node->rflag）（3）; else {do t=*x；; while （*x==node ）; *x=t; }

第 2 页，共 47 页

}

【答案】nodc->rflag==O; *x=ht; *x=nodc->right; prior （t , X ）

7． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e

【答案】克鲁斯卡尔

【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。

8． 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有_____检索和_____检索。

【答案】关键字；记录号；记录号；顺序；直接

9．

给定一组数据

的值为_____。 【答案】5；96

【解析】每次找两个最小的权值构建哈夫曼树：

以它构造一棵哈夫曼树，则树高为_____，

带权路径长度

10．属于不稳定排序的有_____。

【答案】希尔排序、简单选择排序、快速排序、堆排序等

二、算法设计题

11．编写算法打印出由指针Hm 指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。注意：行、列及总表头结点的形式为：

它们已用

域链接成循环链表。非零元的结点形式也同上，每一行（列）的非零元由

域把它们链接成循环链表，该行（列）的表头结点即为该行（列）循环链表的表头。

【答案】算法如下：

第 3 页，共 47 页

12．（1）试分别找出满足下列条件的所有二叉树：（a ）前序序列和中序序列相同：（b ）前序序列和后序序列 相同；（c ）中序序列和后序序列相同。

，设计算法：从右向左依次将所有（2）已知非空二叉树的结点结构为（lchild , data , rchild ）叶子的数据值 放到向量（假定向量的空间大于叶子的总个数）中。

【答案】（1）满足条件的二叉树如下：

（a ）若前序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。 （b ）若前序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。

（c ）若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。 （2）算法如下：

//全局变量

//从右向左依次将二叉树bt 的所有叶子的数据值放到a 向量中

//中序遍历右子树

//叶结点

//中序遍历左子树

13．请用流程图或高级语言表示算法。已知有向图有n 个顶点，请写算法，根据用户输入的数对，对于每条这样建立该有向 图的邻接表。即接受用户输入的（以其中之一为0标志结束）的边，申请一个结点，并插 入到的单链表中，如此反复，直到将图中所有边处理完毕。

提示：先产生邻接表的n 个头结点（其结点数值域从1到n ）。 【答案】算法如下：

//建立有向图的邻接表存储结构

//输入顶点信息

第 4 页，共 47 页