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

一、填空题

1． 在哈希函数

中，P 值最好取_____。

【答案】小于等于表长的最大素数或不包含小于20的质因子的合数

【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。

2． 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。

【答案】

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

【答案】

4． 应用prim 算法求解连通网络的最小生成树问题。

（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。

〔始顶点号，终顶点号，权值）

（2）下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。

的值在〈limits •h>中

//图的顶点数，应由用户定义

//用二维数组作为邻接矩阵表示

//生成树的边结点

//边的起点与终点

//边上的权值

//最小生成树定义

//从顶点rt 出发构造图G 的最小生成树T ，rt 成为树的根结点

//初始化最小生成树

T

//依次求MST 的候选边

//遍历当前候选边集合

//选具有最小权值的候选边

//图不连通，出错处理

//修改候选边集合

【答案】（1）（0，3，1）; （3，5, 4）; （5，2，2）; （3，1, 5）; （1，4，3） （2）①T[k]; tovex=i②min=Maxint③mispos=i④exit （O ）⑤T[i]; fromvex=v

【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设N={V，E}是连通图

，是N

上最小生成树边的集合。算法从属于

为止。

5． 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_____和_____; 而又根据指针的连接方式，链表又可分成_____和_____。

【答案】单链表；双链表；（动态）链表；静态链表

【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。

6． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。

【答案】物理上相邻；指针

【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。

E T 开始，重复执行下述操作：在所有u 属于

加入集合

同时将

并入

v

直到

的边（u ，v ）属于E

中找一条代价最小的边

7． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：

【答案】

【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。

8． 无用单元是指_____，例_____

【答案】用户不再使用而系统没有回收的结构和变量；

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

【答案】克鲁斯卡尔

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

10．执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。

【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储

11．组成串的数据元素只能是_____。

【答案】字符

12．已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。

【答案】左子树；右子树 【解析】二叉排序树

或者是一棵空树，或者是具有下列性质的二叉树：①若它

的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。