数据结构复习题(4A)

8.从堆中删除一个元素的时间复杂度为（ ）。

A. O(1) B. O(n) C. O(Log2n) D. O(nLog2n) 标准答案：C

9.利用3、6、8、12为4个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最短带权路径长度为（ ）。

A. 18 B. 16 C. 12 D. 30 标准答案：A

10.向堆中插入一个元素的时间复杂度是（ ）。

A. O(1) B. O(Log2n) C. O(n) D. O(nLog2n) 标准答案：B

二、填空题（共有题目18题）

1.堆的存储结构适宜采用顺序存储，这样能够充分利用存储空间。

2.若有两棵树T 1和T 2均为小根堆，当以它们作为一棵树T的左、右子树，并用一个比这两棵子树的根都小的值作为整个树T的根结点，则树T是一个堆;小根堆。

3.在一棵非空的二叉搜索树中，以每个分支结点为根的子树都是一棵二叉搜索树。

4.有7个带权结点，其权值分别为3、7、8、2、6、10、14，若依它们为叶子结点构造一棵哈夫曼树，给出其广义表，并计算出其带权路径长度WPL＝134。 5.堆是一棵完全二叉树。

6.在一棵树中，结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的乘积。 7.在一棵二叉搜索树中，其左子树上结点的关键字值小于根结点的关键字值。 8.在一棵树中，两个结点之间如果有路径的话，路径的个数是唯一的。

9.在一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明查找成功；若元素的值小于根结点的值，则继续向左子树查找；若元素的值大于根结点的值，则继续向右子树查找。 10.当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。 11.当从一个小根堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整。 12.二叉搜索树又名二叉排序树。

13.在一个堆中，除编号为0的堆顶结点外，对于其他编号为i的结点，其双亲结点的编号为?(i?1)/2?。14.在一个堆的顺序存储结构中，堆中结点的编号是从0开始的，若一个元素的下标为i，则它的左孩子元素的下标是2i+1，右孩子元素的下标是2i+2。

15.在一个小根堆中，堆顶结点的值是所有结点中的最小值；在一个大根堆中，堆顶结点的值是所有结点中的最大值。

16.在任何一棵哈夫曼树中，单支结点的个数为0。

17.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个有序序列。

18.不管一棵哈夫曼树中有偶数或奇数个叶子结点，则树中总结点的个数必为奇数个。

第7章 图

一、单选题（共有题目18题）

1.对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为（ ）。

A. 0 B. 1 C. n D. n-1 标准答案：B

2.已知一个无向图的边集为{(0,1)3,(0,2)4,(0,3)8,(1,4)10,(2,3)2, (2,4)12,(3,4)8}，则利用普里姆算法从顶点0出发求其最小生成树的过程中，得到的第３条边是（ ）。

A. (0,1)3 B. (0,2)4 C. (2,3)2 D. (3,4)5 标准答案：C

3.在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为（ ）。

13

A. n B. e C. n*e D. 2e 标准答案：D

4.若要把n个顶点连接为一个连通图，则至少需要（ ）条边。

A. n B. n+1 C. n-1 D. 2n 标准答案：C

5.由一个具有n个顶点的连通图生成的最小生成树中，具有（ ）条边。

A. n B. n-1 C. n+1 D. 2n 标准答案：B

6.若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用（ ）次深度优先搜索遍历的算法。

A. 1 B. k-1 C. k D. k+1 标准答案：C

7.若一个图的边集为{（A,B）,（A,C）,（B,D）,（C,F）,（D,E）,（D,F）}，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为（ ）。

A. A，B，C，F，D，E B. A，C，F，D，E，B C. A，B，D，C，F，E D. A，B，D，F，E，C 标准答案：B

8.在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为（ ）。

A. n B. e C. n+e D. 2e 标准答案：D

9.若一个图的边集为{（A,B）,（A,C）,（B,D）,（C,F）,（D,E）,（D,F）}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为（ ）。

A. A，B，C，D，E，F B. A，B，D，E，F，C C. A，B，D，C，E，F D. A，C，B，F，D，E 标准答案：D

10.在一个具有n个顶点的有向完全图中，所含的边数为（ ）。

A. n B. n(n-1) C. n(n-1)/2 D. n(n+1)/2 标准答案：B

11.已知一个无向图的边集为{(0,1)3,(0,2)5,(0,3)6,(1,4) 10,(2,3)2,(2,4) 9,(3,4)8}，则该图的最小生成树的边集为（ ）。

A. {(0,1)3,(0,2)5,(0,3)6,(3,4)8} B. {(0,1)3,(0,2)5,(0,3)6,(2,3)2} C. {(2,3)2,(0,2)5,(3,4)8,(0,3)6} D. {(2,3)2,(0,2)5,(3,4)8,(0,1)3} 标准答案：D

12.在一个具有n个顶点的无向完全图中，所含的边数为（ ）。

A. n B. n(n-1) C. n(n-1)/2 D. n(n+1)/2 标准答案：C

13.在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素的个数为（ ）。

A. n B. e C. n*e D. 2e 标准答案：B

14.在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为（ ）。

A. s B. s-1 C. s+1 D. n 标准答案：A

15.已知一个无向图的边集为{(0,1)3,(0,2)4,(0,3)8,(1,4)10,(2,3)2, (2,4)12,(3,4)5}，则利用克鲁斯卡尔算法求其最小生成树的过程中，得到的第３条边是（ ）。

A. (0,1)3 B. (0,2)4 C. (2,3)2 D. (3,4)5 标准答案：B

14

16.在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（）。

A. n B. e C. n*e D. 2e 标准答案：D

17.在一个无权图中，若两顶点之间的路径长度为k，则该路径上的顶点数为（ ）。

A. k B. k+1 C. k+2 D. 2k 标准答案：B

18.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为（ ）。

A. s B. s-1 C. s+1 D. 2s 标准答案：D

二、填空题（共有题目13题）

1.一个图的边集为{(a,c),(a,e),(b,e),(c,d),(d,e)},从顶点a出发进行深度优先搜索遍历得到的顶点序列为a c d e b（ a e b d c 或 a e d c b），从顶点a出发进行广度优先搜索遍历得到的顶点序列为a c e d b（a e c b d或a e c d b）。

2.已知一个连通图的边集为{(1,2)3,(1,3)6,(1,4)8,(2,3)4, (2,5)10,(3,5)12,(4,5)2}，若从顶点v1出发，按照普里姆算法生成的最小生成树的过程中，被选取的第3条边为(1,4)8。 3.对于具有n个顶点和e条边的连通图，普里姆算法和克鲁斯卡尔算法的时间复杂度分别为O(n2)和O(n2)。 4.一个连通图中存在着1个连通分量。

5.已知一个连通图的边集为{(1,2)3,(1,3)6,(1,4)8,(2,3)4,(2,5) 10,(3,5)12,(4,5)2}，则度为3的顶点个数有_4个。 6.若一个连通图中每个边上的权（权值）均不同，则得到的最小生成树是唯一的。 7.在一个图中，所有顶点的度数之和等于所有边数的2倍。

8.若一个图的顶点集为{a,b,c,d,e,f}，边集为{(a,b),(a,c),(b,c),(d,e)}，则该图含有3个连通分量。 9.在一个具有n个顶点的有向完全图中，包含有n(n-1)条边。

10.已知一个连通图的边集为{(1,2)3,(1,3)6,(1,4)8, (2,3)4,(2,5)10,(3,5)12,(4,5)2}，该图的最小生成树的权为17。

11.在一个具有n个顶点的无向完全图中，包含有n(n-1)/2条边。

12.对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为n和n-1。 13.在一个具有n个顶点的无向图中，要连通所有顶点则至少需要n-1条边。

第8章 查找

一、单选题（共有题目7题）

1.对于长度为n的顺序存储的有序表，若采用二分查找，则对所有元素的最长查找长度为（ ）的值的向下取整加1。

A. log 2 (n+1) B. log 2 n C. n/2 D. (n+1)/2 标准答案：B

2.对于长度为18的顺序存储的有序表，若采用二分查找，则查找第15个元素的查找长度为（ ）。

A. 3 B. 4 C. 5 D. 6 标准答案：B

3.对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找任一元素的平均查找长度为（ ）。

A. 5.5 B. 5 C. 39/8 D. 19/4 标准答案：C

4.对于长度为n的顺序存储的有序表，若采用二分查找，则对所有元素的最长查找长度为（ ）的值的向上取整。

A. log2 (n+1) B. log 2 n C. n/2 D. (n+1)/2 标准答案：A

15

5.对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用二分查找，则查找元素26的查找长度为（ ）。

A. 2 B. 3 C. 4 D. 5 标准答案：C

6.对于长度为9的顺序存储的有序表，若采用二分查找，在等概率情况下的平均查找长度为（ ）的值除以9。

A. 20 B. 18 C. 25 D. 22 标准答案：C

7.对长度为3的顺序表进行查找，若查找第1个元素的概率为1/2，查找第2个元素的概率为1/3，查找第3个元素的概率为1/6，则查找任一元素的平均查找长度为（ ）。 A. 5/3 B. 2 C. 7/3 D. 4/3 标准答案：A

二、填空题（共有题目3题）

1.以顺序查找方法从长度为n的顺序表中查找一个元素时，平均查找长度为(n+1)/2，时间复杂度为O( n )。 2.以二分查找方法从长度为12的有序表中查找一个元素时，平均查找长度为37/12。

3.对于二分查找所对应的判定树，它既是一棵二叉搜索树，又是一棵理想平衡二叉树（理想平衡树、理想二叉树）。

第9章 排序

一、单选题（共有题目3题） 1.若对n个元素进行直接插入排序，在进行第 i 趟（1≤i≤n-1）排序时，为寻找插入位置最多需要进行（ ）次元素的比较。

A. i+1 B. i-1 C. i D. 1 标准答案：C

2.若对n个元素进行直接插入排序，在进行任一趟排序的过程中，为寻找插入位置而需要的时间复杂度为（ ）。

A. O(1) B. O(n) C. O(n2) D. O(log2n) 标准答案：B

3.在对n个元素进行直接选择排序的过程中，需要进行（ ）趟选择和交换。

A. n+1 B. n C. n-1 D. n/2 标准答案：C

二、填空题（共有题目2题）

1.每次从无序表中取一个元素，把它插入到有序表中的适当位置，此种排序方法叫做插入排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做选择排序。 2.在直接选择排序中，记录比较次数的时间复杂度为O(n2)，记录移动次数的时间复杂度为O(n)。

16