发布时间 : 星期五 文章数据结构课后练习题汇总更新完毕开始阅读28ea12643169a4517623a301
六、 算法设计题
1、 对于二维数组A[m][n]，分别编写相应函数实现如下功能：（1）求数组 A靠边元素之和；（2）求
从A[0][0]开始的互不相邻的各元素之和；（3）当m=n时分别求两条对角线上的元素之和，否则打印出m≠n的信息。
2、 如果矩阵A中的一个元素A[i][j]满足下列条件：A[i][j]是第I行中最小的元素，又是第j列中值最
大的元素，则称之为该矩阵的一个马鞍点。编写函数计算m×n的矩阵A的所有马鞍点，并分析算法的时间复杂度。
28
第六章 树和二叉树
一、 选择题
1、 有一“遗传”关系，设x是y的父亲，则x可以把它的属性遗传给y，表示该遗传关系最适合的
数据结构是（ ）
A、向量 B、树 C、图 D、二叉树 2、树最适合用来表示（ ）
A、有序数据元素 B、元素之间具有分支层次关系的数据 C、无序数据元素 D、元素之间无联系的数据
3、树B的层号表示为1a,2b,3d,3e,2c，对应于下面选择的（ ） A、1a(2b(3d,3e),2c) B、a(b(D,e),c) C、a(b(d,e),c) D、a(b,d(e),c)
4、对二叉树的结点从1开始连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（ ）次序的遍历实现二叉树的结点编号。
A、先序 B、中序 C、后序 D、从根开始按层次遍历 5、按照二叉树的定义，具有3个结点的二叉树有（ ）种。 A、3 B、4 C、5 D、6
6、在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则数的最大高度为（n0+n1+n2 ），其叶结点数为（ n2+1 ）；树的最小高度为（[ log2n]+1 ），若采用链表存储结构，则有（n+1 ）个空链域。
A、n/2 B、[ log2n]+1 C、log2n D、n E、n0+n1+n2 F、n1+n2 G、n2+1 H、1 I、n+1 J、n1 K、n2 L、n1+1 7、对一棵满二叉树，m个树叶，n个结点，深度为h，则（ ） A、n=m+h B、h+m=2n C、m=h-1 D、n=2h-1
8、设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ），至多为（ ）。
A、2h B、2h-1 C、2h-1 D、2h-1
9、在一棵二叉树上第5层的结点数最多为（ ）（假设根结点的层数为1） A、8 B、16 C、15 D、32
10、深度为5的二叉树至多有（ ）个结点。 A、16 B、32 C、31 D、10
11、一棵有124个叶结点的完全二叉树，最多有（ ）个结点 A、247 B、248 C、249 D、250
12、含有129个叶子结点的完全二叉树，最少有（ ）个结点 A、254 B、255 C、256 D、257
29
13、假定有一棵二叉树，双分支结点数为15，单分支结点数为30，则叶子结点数为（ ）个。 A、15 B、16 C、17 D、47 n2+1=n0
16、用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若有左子树，则左子树是结点（ ）。
A、R[2i+1] B、R[2i] C、R[i/2] D、R[2i-1]
17、在一棵非空二叉树的中序遍历序列中，根结点的右边（ ）。
A、只有右子树上的所有结点 B、只有右子树上的部分结点 C、只有左子树上的所有结点 D、只有左子树上的部分结点
18、任何一棵二叉树的叶结点在先序、中序和后序遍历中的相对次序（ ）。 A、不发生改变 B、发生改变 C、不能确定 D、以上都不对
19、设n、m为一棵树上的两个结点，在中序遍历时，n在m前的条件是（ ）。 A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孙
20、一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在先序遍历中结点E的直接前驱为（ ），后序遍历中结点B的直接后继是（ ）。 A、B B、D C、A D、I E、F F、C
21、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（ ）。 A、acbed B、decab C、deabc D、cedba
22、若二叉树采用二叉链表作存储结构，要交换其所有分支结点左右子树的位置，利用（ ）遍历方法最合适。
A、前序 B、中序 C、后序 D、层次 23、线索二叉树是一种（ ）结构。
A、逻辑 B、逻辑和存储 C、物理 D、线性
24、如果T2是由有序树T转换而来的二叉树，那么T中结点的前序就是T2中结点的（ ）。 A、前序 B、中序 C、后序 D、层次序
25、设T是哈夫曼树，具有5个叶结点，树T的高度最高可以是（ ）。 A、1 B、2 C、3 D、4 E、5 F、6
26、由带权为8，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（ ）。 A、23 B、37 C、46 D、43
27、树的后根遍历序列等同于该树对应的二叉树的（ ）。 A、先序遍历 B、中序遍历 C、后序遍历 D、层次遍历 28、以下说法错误的是（ ）
A、树形结构的特点是一个结点可以有多个直接前趋 B、线性结构中的一个结点至多只有一个直接后继 C、二叉树与树是两种不同的数据结构
D、树(及一切树形结构)是一种“分支层次”结构
30
29、以下说法错误的是（ ）
A、二叉树可以是空集 B、二叉树的任一结点都有两棵子树
C、二叉树与树具有相同的树形结构 D、二叉树中任一结点的两棵子树有次序之分 30、以下说法错误的是（ ）
A、完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 B、在三叉链表上，二叉树的求双亲运算很容易实现 C、在二叉链表上，求根，求左、右孩子等很容易实现 D、在二叉链表上，求双亲运算的时间性能很好 31、以下说法错误的是（ ）
A、一般在哈夫曼树中，权值越大的叶子离根结点越近 B、哈夫曼树中没有度数为1的分支结点
C、若初始森林中共有n棵二叉树，最终求得的哈夫曼树共有2n-1个结点
D、若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树
32、将含有41个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺
序对结点编号，那么编号为21的双亲结点编号为（ ）
A 、10 B、 11 C、 41 D、 20
33、任何一棵二叉树的叶结点在其先根、中根、后根遍历序列中的相对位置（ ）
A、肯定发生变化 B、有时发生变化 C、肯定不发生变化 D、无法确定
34、下列说法正确的是（ ）
A、树的先根遍历序列与其对应的二叉树的前序遍历序列相同 B、树的先根遍历序列与其对应的二叉树的后序遍历序列相同 C、树的后根遍历序列与其对应的二叉树的前序遍历序列相同 D、树的后根遍历序列与其对应的二叉树的后序遍历序列相同
35、下列说法中正确的是（ ）
A、任何一棵二叉树中至少有一个结点的度为2 B、任何一棵二叉树中每个结点的度都为2 C、任何一棵二叉树中的每个结点的度肯定等于2 D、任何一棵二叉树中的每个结点的度都可以小于2
36、一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有
结点的值，而大于右子树上所有结点的值。现采用（ ）遍历方式就可以得到这棵二叉树所有结 点的递减序列。
A、前序 B、中序 C、后序 D、层次
37、对含有（ ）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。
A 、0 B、 1 C 、2 D、 不存在这样的二叉树
31