数据结构经典习题--每章都有 下载本文

第六章

一.选择题

1.假定在一棵二叉树中,双分支结点数为15个,单分支结点数为32个,则叶子结点 数为 。

A. 15 B. 16 C. 17 D. 47 2.假定一棵二叉树的结点数为18个,则它的最小高度 。

A. 4 B. 5 C. 6 D. 18 3.在一棵二叉树中第五层上的结点数最多为 。

A. 8 B. 15 C. 16 D. 32 4.在一棵具有五层的满二叉树中,结点总数为 。

A. 31 B. 32 C. 33 D. 16

5.已知8个数据元素为(34、76、45、18、26、54、92、65),按照依次插入结点的方法生成一棵二叉排序树后,最后两层上的结点总数为 。

A. 1 B. 2 C. 3 D. 4

6.由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树,该树的带权路径长度为 。

A. 23 B. 37 C. 44 D. 46

7.在树中除根结点外,其余结点分成m (m≥0)个 的集合T1,T2,T3...Tm,每个集合又都是树,此时结点T称为Ti的父结点,Ti称为T的子结点(1≤i≤m)。 A. 互不相交 B. 可以相交 C. 叶结点可以相交 D. 树枝结点可以相交 8.下面答案 是查找二叉树(又称二叉排序树)。

A. 二叉树中的每个结点的两棵子树的高度差的绝对值不大于1 B. 二叉树中的每个结点的两棵子树的高度差等于1 C. 二叉树中的每个结点的两棵子树是有序的

D. 二叉树中的每个结点的关键字大于其左子树(如果存在)所有结点的关键字值,

且小于其右子树(如果存在)所有结点的关键字值。 9.如果结点A有三个兄弟,而且B是A的双亲,则B的出度是 。 A. 3 B. 4 C. 5 D. 1 10.一个深度为L的满K叉树有如下性质:第L层上的结点都是叶子结点,其余各层上每个结点都有K棵非空子树。如果按层次顺序从1开始对全部结点编号,编号为n的有右兄弟的条件是 。

A. (n-1) % k= =0 B. (n-1) % k!=0 C. n % k= =0 D. n % k!=0 11.在完全二叉树中,当i为奇数且不等于1时,结点i的左兄弟是结点 ,否则没有左兄弟。

A. 2i-1 B. i+1 C. 2i+1 D. i-1

12.某二叉树T有n个结点,设按某种遍历顺序对T中的每个结点进行编号,编号值为

1,2,...,n且有如下性质:T中任一结点V,其编号等于左子树上的最小编号减1,而V的右子树 的结点中,其最小编号等于V左子树上结点的最大编号加1。这时按 编号。

A. 中序遍历序列 B. 前序遍历序列 C. 后序遍历序列 D. 层次遍历序列

9

13.最小代价生成树 。

A. 是唯一的 B.不是唯一的 C.唯一性不确定 D.唯一性与原因的边的权数有关

二、填空

1.在树型结构中,树根结点没有 结点,其余每个结点有且仅有 ;树叶

结点没有 ,其余每个结点的 结点数不受限制。 2.对于一棵具有n个结点的树,则该树中所有结点的度之和为 。

3.在一棵二叉树中,度为0的结点的个数为n0 ,度为2的结点的个数为n2 ,则:

_______ 。 4.在二叉树的顺序存储中,对于下标为5的结点,它的双亲结点的下标为 , 若

它存在左孩子,则左孩子结点的下标为 ,若它存在右孩子,则右孩子结点的下标为 。

5.假定一棵二叉树的广义表表示为A(B(,D),C(E(G),F)),则该树的深度为 , 度

为0的结点数为 ,度为1的结点数为 ,度为2的结点数为 ;C结点是A 结点的 ______,E结点是C结点的 _____。

6.在一棵二叉排序树中,按 遍历得到的结点序列是一个有序序列。

7.由分别带权为3,9,6,2,5的共五个叶子结点构成一棵哈夫曼树,则带权路径长度 ┏━━┳━━┳━━━┓

8.假定在二叉树的链接存储中,每个结点的结构为 ┃left┃data┃right ┃,其中 ┗━━┻━━┻━━━┛

data为值域,left和right分别为链接左、右孩子结点的指针域,请在下面中序 遍历算法 中画有横线的地方填写合适的语句。

void inorder(bt); { if bt!=nil {

(1) ; (2) ; (3) ;}

} 三、判断题

1.后序遍历树和中序遍历与该树对应的二叉树,其结果不同( )。

2.若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点,则它必是该子 树

的前序遍历序列中的最后一个结点( )。 3.若一个树叶是某子树的中序遍历序列中的最后一个结点,则它必是该子树的前序 遍历序列中的最后一个结点( )。 4.已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树,因为不知道树 的根结点是哪一个( )

5.在哈夫曼编码中,当两个字符出现的频率相同时,其编码也相同,对于这种情况应作特殊处理( )。

6.中序遍历二叉排序树的结点就可以得到排好序的结点序列( )。

7.在二叉排序树上插入新的结点时,不必移动其它结点,仅需改动某个结点的指针, 由空变为非空即可( )。

四、综合题

1.分别写出对二叉树进行中根遍历和先根遍历的非递归算法(不允许使用转向语句)。

10

2. 对于二叉排序树,当所有结点的权都相等的情况下,最佳二叉排序树有何特点。 3. 试证明已知一棵二叉树的前序序列和中序序列,则可唯一地确定一棵二叉树。

第七章

一、 选择题

1.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的 倍。

A. 1/2 B. 1 C. 2 D. 4 2.对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为 。

A. n B. n+1 C. n-1 D. n+e

3.具有n个顶点的无向完全图,边的总数为 条。

A. n-1 B. n C. n+1 D. n*(n-1)/2 4.设图G有n个顶点和e条边,当G是非孤立顶点的连通图时有2e>=n,故可推得深度优先搜索的时间复杂度为 。

A. O(e) B. O(n) C. O(ne) D. O(n+e) 5.在无向图G的邻接矩阵A中,若A[i,j]等于1,则A[j,i]等于 。 A. i+j B. i-j C. 1 D. 0

6.图的深度优先或广度优先遍历的空间复杂性均为 。(访问标志位数组空间) A. O(n) B. O(e) C. O(n-e) D. O(n+e)

二、 填空

1.在图G的邻接表表示中,每个顶点邻接表中所含的结点数,对于无向图来说等于该 顶点的 ,对于有向图来说等于该顶点的 。

2.假定一个图具有n个顶点和e条边,则采用邻接矩阵表示的空间复杂性为 , 采用邻接表表示的空间复杂性为 。 3.已知一个无向图的邻接矩阵如下所示,则从顶点A出发按深度优先搜索遍历得到的 顶点序列为 ,按广度优先搜索遍历得到的顶点序列为 A B C D E F ┏0 1 1 0 1 0┓A ┃1 0 1 0 1 1┃B ┃1 1 0 1 0 0┃C ┃0 0 1 0 0 1┃D ┃1 1 0 0 0 1┃E

┗0 1 0 1 1 0┛F

4.已知一个图如下所示,在该图的最小生成树中,各边的权值之和为 。 10

① ② 15 5 2 8 ⑤ 12

11

③ 3 ④

三、 判断题

1.有回路的图不能进行拓扑排序( )。 2.有回路的图不能进行拓扑排序( )。 3.连通分量是无向图中的极小连通子图( ) 四、综合题

1.证明n个顶点的无向完全图的边数的n(n-1)/2。

2.证明一个有n个顶点,e条边的无向图G,必有∑dj =2e其中dj 为顶点j的度。 3.证明若无向图G的顶点度数的最小值大于或等于2,则G有一条回路。 4. 设无向图G如下图:

B E

A D G

C F 试给出

(1)该图的邻接矩阵;

(2)该图的邻接表;

(3)从A出发的“深度优先”遍历序列; (4)从A出发的“广度优先”遍历序列。

12