发布时间 : 星期日 文章计算机软件技术基础所有题目答案-自学更新完毕开始阅读
9 10 11 12 13 14 15 16 17 18 #+ #+( #+( #+(+ #+(+ #+ #+/ #+/ #+ # 1 1 18 18 181 19 19 193 13 4 ( 8 + 1 ) / 3 #
5．链栈中为何不设置头结点?
答：因为链栈只在链表头插入和删除结点，不可能在链表中间插入或删除结点，算法实现很简单，所以一般不设置头结点。
第五节 树
(树根结点的高度为1)
一、选择题
1．以下说法错误的是( )。
*A．树形结构的特点是一个结点可以有多个直接前驱 B．线性结构中的一个结点至多只有一个直接后继 C．二叉树与树是两种不同的数据结构 D．树(及一切树形结构)是一种“分支层次’结构
2．以下说法错误的是( )。
A．二叉树可以是空集 B．二叉树的任一结点都有两棵子树 *C．二叉树与树具有相同的树形结构 D、二叉树中任一结点的两棵子树有次序之分 3．以下说法错误的是( )。
A．完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 B．在三叉链表上，二叉树的求双亲操作很容易实现 C．在二叉链表上，求根以及求左、右孩子等操作很容易实现 *D．在二叉链表上，求双亲操作的时间性能很好 4．以下说法错误的是( )。
A．一般在哈夫曼树中，权值越大的叶子离根结点越近 B．哈夫曼树中没有度数为1的分支结点 C．若初始森林中共有n棵二叉树，最终求得的哈夫曼树共有2n-1个结点 *D．若初始森林中共有n棵二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树 5．深度为6的二叉树最多有( )个结点。 A．64 *B．63 C．32 D．31
6．将含有41个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为21的双亲结点编号为( )。 *A．10 B．11 C．41 D．20
7．任何一棵二叉树的叶结点在其前序、中序、后序遍历序列中的相对位置( )。 A．肯定发生变化 B．有时发生变化 *C．肯定不发生变化 D．无法确定 8．设二叉树有n个结点，则其深度为( )。 A．n-1 B．n C．└log2n┘+1 *D．无法确定
9．设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少( )个。
A．k+l B．2k *C．2k-1 D．2k+1 10．下列说法正确的是( )。
17
*A．树的前序遍历序列与其对应的二叉树的前序遍历序列相同 B．树的前序遍历序列与其对
应的二叉树的后序遍历序列相同 C．树的后序遍历序列与其对应的二叉树的前序遍历序列相同 D．树的后序遍历序列与其对应的二叉树的后序遍历序列相同 11．下列说法中正确的是( )。
A．任何一棵二叉树中至少有一个结点的度为2 B．任何一棵二叉树中每个结点的度都为2 C．任何一棵二叉树中的每个结点的度肯定等于2 *D．任何一棵二叉树中的每个结点的度都可以小于2
12．一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用( )遍历方式就可以得到这棵二叉树所有结点的递减序列。
A．前序 *B．中序 C．后序 D．层次
13．设森林T中有4棵树，结点个数分别是n1、n2、n3、n4，当把森林T转换成一棵二叉树后，根结点的右子树上有( )个结点。
A．n1-1 B．n1 C．n1+n2+n3 *D． n2+n3+n4
14．对含有( )个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。 A．0 *B．1 C．2 D．不存在这样的二叉树 15．如图6-1所示的二叉树的中序遍历序列是( )。
A．abcdgef *B．dfebagc C．dbaefcg D．defbagc
16．已知某二叉树的后序遍历序列是deacb，中序遍历序列是deabc，它的前序遍历序列是( )。 A．acbed *B．baedc C．dceab D．cedba
17．如果T1是由有序树转化而来的二叉树，那么T中结点的前序就是T1中结点的( )。 *A．前序 B．中序 C．后序 D．层次序
18．某二叉树的前序遍历的结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是( )。
A．bdgcefha B．gdbecfha C．bdgechfa *D．gdbehfca 19．在图6-2中的二叉树中，( )不是完全二叉树。（*C）
20．树最适合用来表示( )。
A．有序数据元素 B．无序数据元素 *C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据
21．在计算递归函数时，如不使用递归过程，则一般情况下必须借助于( )数据结构。 *A．栈 B．树 C．双向队列 D．顺序表
22．设二叉树根结点的层次为0，一棵高度为h的满二叉树中的结点个数是( )。
18
A．2h B．2h-1 C．2h-1 *D．2h+1-1 23．以下说法错误的是( )。
A．存在这样的二叉树，对它采用任何次序的遍历，其结点访问序列均相同 *B．二叉树是树的特殊情形 C．由树转换成二叉树，其根结点的右子树总是空的 D．在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树
24．已知一个算式的中缀表达式为a+(b-c)/d，则其后缀表达式是( )。 A．a+(b-c)/d *B．abc-d/+ C．bc-d/a+ D．a+bc-d/
25．按照二叉树的定义，具有4个结点所能构造的不同的二叉树的个数是( )。 A．4 B．8 C．12 *D．14
26．在一棵度为3的树中，度为3的结点的个数为2，度为2的结点的个数为1，则度为0的结点的个数为( )。
A．4 B．5 *C．6 D．7
27．3个结点可构成( )棵不同形态的二叉树。 A．2 B．3 C．4 *D．5 28．哈夫曼树的带权路径长度是( )。
A．所有结点权值之和 *B．所有叶结点带权路径长度之和 C．带权结点的值 D．除根以外所有结点权值之和
29．设有一棵22个结点的完全二叉树，那么整棵二叉树有( )个度为0的结点。 A．6 *B．7 C．8 D．11
30．已知完全二叉树有26个结点，则整棵二叉树有( )个度为1的结点。 A．0 B．1 C．2 *D．13
31．在树的孩子兄弟表示法中，( )操作花时间最多。
A. 求某结点的兄弟 *B．求某结点的第i个孩子 C．求某结点的父结点 D．求树的根结点 32． 已知如图6-3所示的哈夫曼树，那么电文CDAA的编码是( )。 A．110100 B．11011100 *C．010110111 D．11111100
33．在n个结点的完全二叉树中，对任一结点i(1≤i≤n)，i的左孩子可能是( )。 A．i/2 *B．2i+1 C．2i D．都不是
34．已给出图6-3所示的二叉树，A，B，C，D的权值分别为7，5，2，4，则该树的带权路径长度为( )。
A．46 *B．36 C．35 D．都不是 35．下列叙述中正确的是( )。
A．二叉树是度为2的有序树 B．二叉树中结点只有一个孩子时无左右之分 *C．二叉树中必有度为2的结点 D．二叉树中结点最多有两棵子树，并且有左右之分 36．图6-4所示的几种结构中属于树形结构的是( )。（*C）
二、判断题
╳1．二叉树是树的特殊形式。
19
√2．树和二叉树之间最主要的差别是：二叉树的结点的子树要区分为左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。
√3．一棵有n个结点的d度树，若用多重链表表示，树中每个结点都有d个链域，则在树的n*d个链域中，有n*(d-1)+1个是空链域，只有n-1个是非空的。 √4．前序遍历树和前序遍历与该树对应的二叉树，其结果相同。 ╳5．中序遍历树和中序遍历与该树对应的二叉树，其结果不同。 √6．前序遍历森林和前序遍历与该森林对应的二叉树，其结果相同。 ╳7．中序遍历森林和中序遍历与该森林对应的二叉树，其结果不同。
√8．若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必须是该子树的前序遍历序列中的最后一个结点。
√9．二叉树具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女。 ╳10．在二叉树中，具有一个子女的父结点，在中序遍历中，它没有后继的子女结点。 ╳11．在二叉树中插入结点，该二叉树便不再是二叉树。
╳12．用一维数组存储二叉树时，总是以前序遍历存储结点。
√13．已知二叉树的前序遍历和后序遍历序列不能惟一地确定这棵树。 √14．不使用递归，也可以实现二叉树的前序、中序、后序遍历。
√15．在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点之后。 ╳16．有n个结点的不同二叉树有n!棵。
╳17．在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应做特殊处理。 三、填空题
1．树(及一切树形结构)是一种__层次__结构。在树中，__根_结点没有直接前驱。对树上任一结点x来说，x是它的任一子树的根结点惟一的_双亲_。
2．一棵树上的任何结点(不包括根本身)称为根的__子孙__。若B是A的子孙，则称A是B的__祖先__。
3．二叉树第i(i>0)层上至多有__2i-1__个结点。 4．深度为k(k>0)的二叉树至多有__2k-1__个结点。
5．对任何二叉树，若度为2的节点数为n2，则叶子数n0=__n2+1__。
6．满二叉树上各层的节点数已达到了二叉树可以容纳的__最大值_。满二叉树也是__完全__二叉树，但反之不然。
7．具有n个结点的完全二叉树的深度为___│log2n│+1___。
8．在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是__ │log2i│ =│ log2j│ ____。
9．如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(0
2i>n，则结点x无__左孩子__且无__右孩子__；否则，X的左孩子LCHILD(X)的编号为__2i __。(3)若2i+1>n，则结点X无__右孩子__；否则，X的右孩子RCHILD(X)的编号为__2i+1__。 10．二叉树通常有___顺序____存储结构和___链式__存储结构两类存储结构。
11．每个二叉链表还必须有一个指向__根__结点的指针，该指针具有标识二叉链表的作用。 12．对二叉链表的访问只能从___根__指针开始。
13．具有n个结点的二叉树中，一共有__2n__个指针域，其中只有__n-1_个用来指向结点的左右孩子，其余的__n+1__个指针域为NULL。
14．已知二叉树中叶子数为40，仅有一个孩子的结点数为20，则总结点数为__99___。 15．二叉树有不同的链式存储结构，其中最常用的是_二叉链表___与__三叉链表__。 16．可通过在非完全二叉树的“残缺”位置上增设__空指针___将其转化为完全二叉树。 17．具有100个结点的完全二叉树的深度是__7___。
18．深度为90的满二叉树上，第10层有___512___个结点。
19．在__前序__遍历二叉树的序列中，任何结点的子树上的所有结点都是直接跟在该结点之后。
20