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

一、填空题

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

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

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

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

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

3． G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。

【答案】9

【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。

4． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。

h 为附加头结点指针

(_____)

_____；

【答案】(1)p!＝NULL //链表未到尾就一直进行

(2)q //将当前结点作为头结点后的第一元素结点插入

5． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。

【答案】顺序

【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。

6． 设单链表的结点结构为(data，next) ，next 为指针域，已知指针px 指向单链表中data 为x 的结点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，则需要执行以下语句: _____；_____；

【答案】py ﹣＞next ＝px ﹣＞next ；px ﹣＞next ＝py

7．

＝_____

【答案】5

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

【答案】克鲁斯卡尔

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

9． 对n 个元素的序列进行起泡排序时，最少的比较次数是_____。

【答案】n －1

【解析】如果序列是正序，冒泡排序第一次只要进行n －1次比较，发现没有移动元素，说明序列有序。

10．中缀式

运算结果为_____。 【答案】

【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。

(c-d)对应的前缀式为_____，若a=l，b=2, c=3, d=4, 则后缀式的

二、判断题

11．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。（ ）

【答案】×

【解析】单链表不能使用折半查找方法。折半查找主要用于数据元素有序且存储方式为顺序存储的表。

12．m 阶B 树的任何一个结点的左右子树的高度都相等。（ ）

【答案】√

【解析】由B 树的性质得知，叶子结点都处于同一层。因此，m 阶B 树的任何一个结点的左右子树的高度都相等。

13．从逻辑结构上看，n 维数组的每个元素均属于n 个向量。（ ）

【答案】 √

【解析】对于每一维，都有一个向量共用这个元素，比如我们最常见的二维数组，对于每个

元素，在行和列都有一个向量共用这个元素。

14．对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（ ）

【答案】×

【解析】索引顺序存取方法插入操作比较麻烦，对于处理大量数据，会有大量的记录进入溢出区，而基本区中又浪费很多空间。

15．堆肯定是一棵平衡二叉树。（ ）

【答案】×

【解析】堆是n 个元素的序列，排序树，更不会是平衡二叉树。

可以看成是完全二叉树，但相对于根并无左小右大的要求，故其既不是二叉

16．两个长度不相同的串有可能相等。（ ）

【答案】 ×

【解析】两个字符串相等，只有当两个字符串的长度相等，并且各个对应位置的字符相等才相等。

17．二叉树中序线索化后，不存在空指针域。（ ）

【答案】×

【解析】非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。

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

【答案】√

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

19．通常使用队列来处理函数或过程的调用。（ ）

【答案】 ×

【解析】经常使用栈来处理函数或过程的调用。

20．如果数据元素保持有序，则查找时就可以采用折半查找方法。（ ）

【答案】×

【解析】采用折半查找的条件是数据元素有序且存储方式为顺序存储，对于常见的链式存储，在进行查找时主要依靠指针来操作。