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

一、填空题

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

【答案】P ﹣＞next! ＝NULL

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

2． 有向图G=(V, E) ，其中，用三元组表示弧及弧上的权d 。E(G)为

，则从源点0到顶点3的最短路径长度是_____，经过的中间顶点是_____。

【答案】50；4 3． 假定查找有序表

【答案】

表

平均查找次数为

4． 文件由_____组成；记录由_____组成。

【答案】记录；数据项

5． 从平均时间性能而言，_____排序最佳。

【答案】快速

【解析】快速算法的平均时间复杂度为nlogn 。

6． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。

【答案】模式匹配；模式串

7． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。

【答案】

中每个元素的概率相等，则进行折半查找时的平均查找长度为_____。

【解析】折半查找时每个的次数如表所示:

。

；边稀疏

8． 以下是用类C 语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶指针为top ，P ，t 为辅助指针，head 为双向循环链表的头指针。试填充算法中的空格，使算法完整。

【答案】

9． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 _____和记录的_____。

【答案】比较；移动

10．阅读下列程序，指出其功能，并写出空格处应填上的语句。

【答案】

【解析】本题是在哈希表

中插入值为item 的元素，如该元素已在哈希表中，报告出错。

二、判断题

11．在初始数据表已经有序时，快速排序算法的时间复杂度为

【答案】×

。（ ）

【解析】当初始数据表有序，此时快速排序所需要比较的次数最多，快速排序算法的时间复杂度为。

12．基数分类只适用于以数字为关键字的情况，不适用于以字符串为关键字的情况。（ ）

【答案】×

【解析】如果用字符串为关键字，可以将其中的字符串的每一位用Ascn 码进行比较。

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

【答案】×

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

14．栈和队列都是限制存取点的线性结构。（ ）

【答案】 √

15．哈希函数越复杂越好，因为这样随机性好，冲突概率小。（ ）

【答案】×

【解析】随机性好和冲突概率小跟哈希函数的复杂程度无关，是根据具体情况而定的，跟实际的数据有很大关系。

16．二叉树中除叶结点外，任一结点X ，其左子树根结点的值小于该结点(X)的值；其右子树根结点的值大于等于该结点(X)的值，则此二叉树一定是二叉排序树。（ ）

【答案】×

【解析】二叉排序树按中序遍历的结点序列是从小到大的因为某结点的左子树根结点不一定是它的中序前驱，可能会出现某结点的左子树根结点的右子树上的值大于这个结点; 其右子树根结点也不一定是它的中序后继。可能会出现右子树根结点的左子树的值小于这个结点。

17．广义表(((a，b ，C) ，d ，e ，f)) 的长度是4。（ ）]

【答案】 ×

【解析】长度为1。因为只含一个元素即子表(((a，b ，C) ，d ，e ，f)) 。

18．一个广义表可以为其他广义表所共享。（ ）

【答案】 √

【解析】因为广义表中的元素还可能是表，所以对于一个广义表可以为其他广义表所共享。