数据结构复习题.pdfVIP

数据结构复习题：

一、判断题

1、（）采用循环链表作为存储结构的队列就是循环队列。

2、（）哈夫曼树一定是完全二叉树。

3、（）选择排序是一种稳定的排序方法。

4、（）在顺序存储结构的线性表中，取第i个元素操作的时间复杂度为O(1)。

5、（）有向图中第i个顶点的出度等于其邻接矩阵中第i行非0元素的个数。

6、（）在按值有序的线性链表中可以采用折半查找法进行查找。

7、（）只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。

8、（）在具有n个结点的完全二叉树中，无法确定其叶子结点的个数。

9、（）一棵树转换成二叉树后，该二叉树的根结点一定没有右子树。

10、（）对任意一个图，从它的某个顶点出发进行一次深度或广度优先有哪些信誉好的足球投注网站遍历时，均

可访问到该图的每个结点。

11、（）二叉树的存储结构必须采用二叉链表结构。

12、（）给定一组关键字序列，按顺序构造二叉排序树，其树的形态与关键字的排列顺

序无关。

13、（）当初始序列为逆序时，简单选择排序的比较次数达到最多。

14、（）在单链表表示的线性表中，取线性表第i个元素操作的时间复杂度为O(n)（n

为链表长度）。

15、（）具有n结点的二叉树，其最大深度为n。

16、（）在具有13个叶子结点的二叉树中，其度为2的结点个数一定为12。

17、（）具有n个顶点无向图，其生成树中一定存在n-1条边。

18、（）能采用折半查找法进行查找的查找表必须是有序并为顺序存储。

19、（）若一棵二叉树中不存在度为1的结点，则该二叉树一定是一棵完全二叉树。

20、（）快速排序是目前所有排序方法中效率最高的稳定排序。

二、选择填空

1、下列排序方法中，排序所花时间不受数据初始排列特性影响的算法是＿＿＿＿。

A）冒泡排序B）简单选择排序C）快速排序D）直接插入排序

2、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2

个，那么度为0的结点数为＿＿＿＿个。

A）4B）5C）6D）7

3、对于给定的8个元素：34，76，45，18，26，54，92，65，按给定顺序生成一棵二叉排序树，

该树的深度为＿＿＿＿。

A）4B）5C）6D）7

4、在具有n个结点的线索树中，线索的个数为＿＿＿＿。

A）n-1B）nC）n+1D）不确定

5、若对给定的关键字序列利用折半查找方法进行查找，则关键字序列需满足的条件是

_________。

A）顺序存储且有序B）顺序存储且升序

C）链式存储且有序D）有序

6、在一个单链表中，已知q指针所指结点为p指针所指结点的前驱，若在p、q之间插入s

所指结点，则主要操作为_________。

A）s-next=p-next;p-next=s;B）q-next=s;s-next=p;

C）p-next=s-next;s-next=p;D）p-next=s;s-next=q;

7、在具有n个顶点的无向图的邻接表中表结点总数最多为_________。

A）n*(n-1)B）n*nC）2*n*(n-1)D）n*(n-1)/2

8、设一个输入序列为1，2，3，4，5，6，则借助一个栈所得到的输出序列不可能是_________。

A）3，2，5，6，4，1B）4，5，3，6，2，1

C）2，4，3，5，1，6D）1，5，4，6，2，3

9、设循环队列存储空间的下标范围是0..n-1，当队列头尾指针分别为f和r时，队列长度为

_________。

A）r-fB）r–f+1C）