数据结构-复习模拟.pdf

复习A

一、判断题

1．线性表的逻辑顺序总是与其物理顺序一致。（）

2．在单链表中插入和删除数据比在顺序表中要方便。（）

3．在一个有n个结点的链队列中出队一个结点的时间复杂度为O（1）。（）

4．链队列的入队操作总是需要修改头指针，出队操作总是要修改尾指针。（）

5．对二叉排序树进行中根遍历，可得到结点的有序排列。（）

6.边数很多的稠密图，适宜用邻接表表示。（）

7.进行折半查找的表必须是顺序存储的有序表。()

8．哈希查找法中解决冲突问题的常用方法是除留余数法。（）

9.在二叉排序树中插入新结点时，新结点总是作为叶子结点插入。（）

10.对一个连通图进行一次深度优先有哪些信誉好的足球投注网站可以遍访图中的所有顶点。()

二、单项选择题

1．评价一个算法时间性能的主要标准是（）

A.算法易于调试B.算法易于理解C.算法的稳定性和正确性D.算法的时间复杂度

2．可用带表头结点的链表来表示表，也可用不带表头结点的链表来表示表，前者的主要

好处是（）

A.可以加快对表的遍历B.使空表和非空表的处理统一

C.提高存取结点的速度D.节省存储空间

3．稀疏矩阵一般的压缩存储有两种，即（）。

A．一维数组和二维数组B．一维数组和三元组

C．二维数组和十字链表D．三元组和十字链表

4.若进栈序列为a,b,c,d,进栈过程中可以出栈,则（）不可能是一个出栈序列。

A．cbadB．bdcaC．cdbaD．adbc

5．将一棵有100个结点的完全二叉树从根的这一层开始，每一层从左到右依次对结点进

行编号，根结点编号为１，则编号为49的结点的左孩子的编号为（）

Ａ．98Ｂ．99Ｃ．50Ｄ．48

6．循环队列用数组A[M]存放元素，已知其头尾指针分别为front和rear，则当前队列中

的元素个数是（）。

A．rear-front+1B．rear-front-1

C．rear-frontD．(rear-front+M)%M

7．已知一棵二叉树的有35个叶子结点，则该二叉树至少有（）个结点。

A.69B.70C.71D.72

8．下列排序方法中，要求附加的内存容量最大的是（）。

A．冒泡排序B．快速排序C．堆排序D．归并排序

9．（）不是哈希查找中的冲突处理方法。

A．链地址法B．再哈希法C．除留余数法D．随机探测法

1

10.在一棵6阶的B-树中,除根结点外,每个结点中的至少有（）个关键字。

A)5B)4C)3D)2

三．填空题

1.在长度为n的顺序表中删除一个元素时,等概率情况下的平均移动元素的次数是【】。

2.仅允许在表的同一端进行插入和删除运算的线性表被称为【】．

3.大小为M的顺序存储的循环队列sq队满的条件为【】。

4.已知一棵二叉树的先根序列为ＡＢＤＦＣＥ，中根序列为ＤＦＢＡＣＥ，则后根序列为

【】．

5．在无向图G的邻接矩阵表示中，第j列中非零元的个数等于该顶点的【】。

6.克鲁斯卡尔算法适用于求【】的网的最小生成树。

7.初始有序的N个记录进行直接插入排序时，共进行【】次关键字比较。

8.在单链表中