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

一、填空题

1． 在哈希函数中，p 值最好取_____。

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

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

2． 设有一个10阶对称矩阵A 采用压缩存储方式(以行为主序存储:a 11＝l) ， 则a 85的地址为_____。

【答案】33

【解析】设存储的元素的行标为i ，列标为j 。若i ＞＝j ，则

＝i(i﹣l)/2＋j 。若i ＜j 。则

3．

给定一组数据

WPL 的值为_____。

【答案】5；96

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

的地址为l ＋2＋... ＋i ﹣l ＋j 的地址为j(j﹣l)/2＋i 。将i ＝8，j ＝5代入得33。 以它构造一棵哈夫曼树，则树高为_____，带权路径长度

4． 在一个无向图的的邻接表中，若表结点的个数是m ，则图中边的条数是_____条。 【答案】

【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。

5． 在单链表L 中，指针P 所指结点有后继结点的条件是_____

【答案】P ﹣＞next! ＝NULL

【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。

6． 实现字符串拷贝的函数strcpv 为:

(_____)

【答案】s++＝*t++或(*s++＝*t++)!＝'\0’

7． 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。 【答案】

【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺序查找效率一样为。

8． 循环队列的引入，目的是为了克服_____。

【答案】假溢出时大量移动数据元素

【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。

9． 在循环队列中，队列长度为n ，存储位置从0到，n ﹣1编号，以rear 指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是_____。

【答案】

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

二、判断题

11．拓扑排序的有向图中，最多存在一条环路。（ ）

【答案】×

【解析】要进行拓扑排序，需要满足一个条件为:若顶点A 在序列中排在顶点B 的前面，则在图中不存在顶点B 到顶点A 的路径。如果是一个有环图，则不能满足这个条件，所以拓扑排序的有向图中不能存在环路。

12．在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。（ ）

【答案】√

【解析】最佳适配法:将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给用户；最先适配法:从表头指针开始查找可利用空间表，将找到的第一个大小不小于n 的空闲块的一部分分配给用户；从适配法选择上可以看出最佳适配法会增加闲置空间。

13．KMP 算法的特点是在模式匹配时指示主串的指针不会变小。（ ）

【答案】 √

【解析】KMP 算法是一种字符串匹配的算法，KMP 算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next （ ）函数，函数本身包含了模式串的局部匹配信息。

14．二元查找树的任何结点的左右子树都是二元查找树。（ ）

【答案】√

【解析】二元查找树也称作二元排序树。二元查找树的性质:①若左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若右子树不空，则右子树所有结点的值均大于它的根结点的值；③左右子树也分别为二元查找树。

15．排序算法中的比较次数与初始元素序列的排列无关。（ ）

【答案】×

【解析】这个要看是哪个排序算法，比如快速排序，初始序列为有序的情况比较的次数就相对于无序的多。

16．用希尔(Shell)方法排序时，若关键字的初始排序杂乱无序，则排序效率就低。（ ）

【答案】×

【解析】希尔排序的基本思想是:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

17．哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念（ ）

【答案】×

【解析】哈希文件是使用一个函数(算法) 来完成一种将关键字映射到存储器地址的映射，根据用户给出的关键字，经函数计算得到目标地址，再进行目标的检索。哈希表是根据关键码值而直接进行访问的数据结构。

18．在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（ ）

【答案】√

【解析】在进行分块查找时，首先查找元素在哪一块，然后在确定的块中查找元素，因此，在索引顺序表中，进行分块查找的平均查找长度不仅与表中元素的个数有关，而且与每块中的元素个数有关。

19．十字链表是无向图的一种存储结构。（ ）

【答案】×