Relax1000 数据结构 · 第5章树 · 题目¶

设有 n（n>1）个结点的二叉树采用三叉链表表示，其中每个结点包含三个指针，分别指向左孩子、右孩子及双亲（若不存在，则置为空），则下列说法正确的有（）。
I．树中空指针数量为 n+2
II．通过三叉链表，可以在 O（1）时间复杂度找到二叉树中任意结点前中后序遍历的直接前驱。
III．每个叶子结点只有一个指针指向它
IV．任意度为 2 的分支结点的三个指针非空

A．II、III、IV
B．I、III、IV
C．I、III
D．I、II、IV

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q18 原页片段

查看解析

Q19¶

如果一棵二叉树的先序序列是...a...b..，中序序列是...b...a...，则（）。

A．节点 a 和节点 b 分别在某节点的左子树和右子树中
B．节点 b 在节点 a 的右子树中
C．节点 b 在节点 a 的左子树中
D．节点 a 和节点 b 分别在某节点的两棵非空子树中

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q19 原页片段

查看解析

Q20¶

在下列关于二叉树遍历的说法中，正确的是（）。

A．若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点
B．若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点
C．若有一个叶结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点
D．若有一个叶结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q20 原页片段

查看解析

Q21¶

设 n,m 为一棵二叉树上的两个结点，在后序遍历时，n 在 m前的充分条件是（）。

A．n 在 m右方
B．n 是 m 祖先
C．n 在 m 左方
D．n 是 m子孙

查看解析

Q22¶

先序序列为 1,2,3,4 的不同二叉数有（）个。

A．13
B．14
C．15
D．16

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q22 原页片段

查看解析

Q23¶

4 个不同权值大小不同的元素组成的二叉排序树，有（）种不同的树型。

A．13
B．14
C．15
D．16

查看解析

Q24¶

设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（）。

A．A* B + C / (D * E) + (F - G)
B．(A* B + C) / (D * E) + (F - G)
C．(A* B+C) / (D * E+(F - G))
D．A* B+C / D * E + F - G

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q24 原页片段

查看解析

Q25¶

在二叉树中有两个结点 m 和 n，若 m是 n 的祖先，则使用（）可以找到从 m 到 n 的路径。

A．先序遍历
B．中序遍历
C．后序遍历
D．层次遍历

查看解析

Q26¶

下列关于树的说法错误的是（）。
Ⅰ．树的层序遍历一般使用栈
Ⅱ．图的深度优先遍历必须使用栈来实现
Ⅲ．图的广度优先遍历必须使用栈
Ⅳ．树的后序遍历非递归实现中，栈内的结点元素是当前遍历到的结点的祖先元素集合

A．Ⅰ、Ⅲ、Ⅳ
B．Ⅱ、Ⅳ
C．Ⅰ、Ⅱ
D．Ⅰ、Ⅲ

查看解析

Q27¶

一棵二叉树的前序遍历序列为 ABCDEFG，它的中序遍历序列可能是（）。

A．CABDEFG
B．ABCDEFG
C．DACEFBG
D．DBCEAFG

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q27 原页片段

查看解析

Q28¶

由 6 个节点组成的二叉树，若中序遍历序列为ABCDEF，则不可能的后序遍历序列是（）。

A．CBEADF
B．ADFECB
C．ABDECF
D．BADCFE

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q28 原页片段

查看解析

Q29¶

某二叉树的前序序列为 ABCDEFG，中序序列为 DCBAEFG 则该二叉树的深度（根结点在第 1层）为（）。

A．2
B．3
C．4
D．5

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q29 原页片段

查看解析

Q30¶

对于层序序列（ABDCEFGIH）和中序序列（BCAEDGHFI）所确定的二叉树，下列选项正确的是（）。

A．后序序列是 CBEGHIFDA
B．先序序列是 ABCDEFGIH
C．后序序列是 CBEIHGFDA
D．先序序列是 ABCDEFGHI

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q30 原页片段

查看解析

Q31¶

一棵二叉排序树后序遍历序列是 15,10,23,25,20,35,42,39,30，可能是前序遍历序列的是（）。

A．30,20,15,10,23,25,39,35,42
B．30,20,10,15,23,25,39,35,42
C．30,20,10,15,25,23,39,35,42
D．30,20,10,15,23,25,35,39,42

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q31 原页片段

查看解析

Q32¶

下列关于二叉树的遍历的陈述中，正确的是（）。
Ⅰ．存在一棵二叉树的叶结点在先序、中序、后序遍历序列中相对位置可能不同
Ⅱ．要交换二叉树的所有分支结点的左右子树的位置，利用中序遍历框架解决最合适
Ⅲ．含有 4 个结点的二叉树最多有 14 种形态
Ⅳ．一棵非空的二叉树的前序序列和中序序列正好相反，则该二叉树一定只有一个叶结点

A．Ⅲ、Ⅳ
B．Ⅱ、Ⅲ、Ⅳ
C．Ⅱ、Ⅲ
D．Ⅳ

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q32 原页片段

查看解析

Q33¶

在二叉树的前序序列、中序序列和后序序列中，所有叶结点的先后顺序（）。

A．都不相同
B．完全相同
C．前序和中序相同，而与后序不同
D．中序和后序相同，而与前序不同

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q33 原页片段

查看解析

Q34¶

某二叉树的先序遍历序列和后序遍历序列正好相反，则关于该二叉树一定是（）。

A．空或只有一个结点
B．该二叉树转成森林，每棵树只有一个根节点
C．度为 1 的树
D．高度等于其结点数

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q34 原页片段

查看解析

Q35¶

某二叉树的中序遍历序列和后序遍历序列正好相同，则关于该二叉树一定是（）。

A．空树或任一结点没有左子树
B．空树或任一结点没有右子树
C．空树或每个结点的度为 1
D．空树或满二叉树

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q35 原页片段

查看解析

Q36¶

一棵完全二叉树的中序遍历序列为 1,2,3,4,5,6,7，那么其先序遍历为（）。

A．4,2,1,3,6,5,7
B．4,2,6,1,3,5,7
C．1,3,2,5,7,6,4
D．7,6,5,4,3,2,1

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q36 原页片段

查看解析

Q37¶

若一棵二叉树先序遍历序列为 a,e,b,d,c，后序遍历序列为 b,c,d,e,a，则下列说法错误的是（）。

A．根节点只有一个孩子
B．度为 2 的结点只有一个
C．b 一定是 e 的左孩子
D．c 一定是 d 的左孩子

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q37 原页片段

查看解析

Q38¶

下列关于二叉树遍历的综合判断，错误的是（）。

A．若一棵二叉树的前序序列和中序序列完全相同，则该树所有节点无左孩子
B．若一棵二叉树的后序序列和中序序列完全相同，则该树所有节点无右孩子
C．存在某棵二叉树，前序、中序、后序遍历序列完全相同
D．叶子节点在三种遍历中的相对先后位置一定会发生变化

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q38 原页片段

查看解析

Q39¶

设结点 x 和结点 y 是二叉树 T 中的任意两个结点，若在先序序列中 x 在 y 之前，而在后序序列中 x 在 y 之后，则 x 和 y 的关系是（）。

A．x 是 y 的左兄弟
B．x 是 y 的右兄弟
C．x 是 y 的祖先
D．x 是 y 的后代

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q39 原页片段

查看解析

Q40¶

队列常用于二叉树的层序遍历，下列二叉树的层序遍历中，队列空间的大小至少是（）。

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

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q40 原页片段

查看解析

Q41¶

在下列叙述中，正确的叙述是（）。

A．树的先序遍历和中序遍历可以得到树的后遍历
B．将一棵树转换成二叉树后，根结点没有右子树
C．采用二叉链表作存储结构，树的先序遍历和其相应的二叉树的先序遍历的结果不同
D．一棵树中的叶子结点数一定等于与其对应的二叉树的叶子结点数

查看解析

Q42¶

一棵具有 n 个非叶子结点完全二叉树的线索树，含有（）条线索。

A．2n+1 或 2n
B．2n+2 或 2n+1
C．2n+1 或 2n-1
D．2n+2 或 2n-2

查看解析

Q43¶

判断线索二叉树中 *p 结点有右孩子结点的条件是（）。

A．p != NULL
B．p->rchild!=NULL
C．p->rtag==0
D．p->rtag==1

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q43 原页片段

查看解析

Q44¶

知一棵二叉树的后序序列为 DABEC，中序序列为 DEBAC，则其对应的二叉树的先序线索二叉树中，右指针为线索的结点有（）个。

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

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q44 原页片段

查看解析

Q45¶

下列关于线索二叉树，说法不正确的是（）。

A．在中序线索二叉树中，若某结点有右孩子，那么其后继结点一定它右子树的最左下结点
B．在先序线索二叉树中，若某结点有左孩子，那么可能无法通过该结点的指针找到他的前驱结点
C．线索二叉树中，若总结点数为 n，那么表示线索的指针有 n+1 个
D．在后序线索二叉树中，若一个非根结点没有右孩子，那么它的右指针一定指向其父亲结点

查看解析

Q46¶

二叉树在线索化后，仍不能有效求解的问题是（）。

A．先序线索二叉树中求先序后继
B．中序线索二叉树中求中序后继
C．中序线索二叉树中求中序前驱
D．后序线索二叉树中求后序后继

查看解析

Q47¶

若对以下二叉树进行后序线索化，则结点 c 的左、右线索分别指向（）。

A．e,a
B．b,a
C．a,NULL
D．b, d

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q47 原页片段

查看解析

Q48¶

（）的遍历仍需要栈的支持。

A．前序线索树
B．中序线索树
C．后序线索树
D．所有线索树

查看解析

Q49¶

下列说法错误的是（）。

A．若一棵二叉排序树中一个结点有两个孩子，则它的中序后继结点没有左孩子，它的中序前驱结点没有右孩子
B．若二叉排序树中一个结点 x 的右子树为空，且 x 有一个中序后继 y，则 y 一定是 x 的祖先，且其左孩子也是 x 的祖先（结点本身也视为自己的一个祖先）
C．中序线索树中，从最左边的结点开始，不一定每次都能找到后继结点完成中序遍历
D．若 x 是二叉排序树的叶结点，y 是其父结点，那么 y 的数值要么是树中大于 x 的数值的最小关键字，要么是树中小于 x 的数值的最大关键字

查看解析

Q50¶

下列说法正确的是（）。

A．在二叉树中，具有两个孩子的双亲节点，在中序遍历序列中，它的后继节点（后继节点是指中序遍历序列中排在某节点之后的节点）中最多只能有一个孩子节点。
B．在二叉树中，具有一个孩子的双亲节点，在中序遍历序列中，它没有后继孩子节点
C．已知二叉树的先序遍历和后序遍历并不能唯一地确定这棵树，因为不知道树的根节点是哪一个
D．将一棵树转换成二叉树后，根节点没有左子树

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q50 原页片段

查看解析

Q51¶

设某树的孩子兄弟链表示中共有 6 个空的左指针域、7 个空的右指针域，包括 5 个结点的左、右指针域都为空，则该树中叶结点的个数是（）。

A．7
B．6
C．5
D．不能确定

查看解析

Q52¶

下列关于森林与二叉树的转换，说法错误的是（）。

A．二叉树中没有右孩子的结点个数为原森林中分支结点的个数+1
B．当且仅当森林只有一棵树时，二叉树的分支数和原森林的分支数相同
C．森林的中的叶子结点数量等于二叉树中空左指针数量。
D．二叉树中，某个结点的左右孩子在原森林中一定是叔侄关系。

查看解析

Q53¶

已知二叉树 T 的顺序存储为{1, 10, 6, 3, 2, 22, 4, -1, -1, -1, -1, -1, 5, -1, 8}（-1 代表空结点），那么二叉树 T 对应的森林 F 的先根遍历序列为（）。

A．3, 10, 1, 2, 22, 6, 5, 4, 8
B．1, 10, 3, 2, 6, 22, 5, 4, 8
C．1, 10, 2, 3, 6, 22, 5, 4, 8
D．1, 2, 10, 3, 6, 22, 5, 4, 8

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q53 原页片段

查看解析

Q54¶

一棵二叉排序树的层序遍历序列是 30,20,39,10,23,35,42,15,25。这棵二叉树转换成的树/森林的后根遍历为（）。

A．10,15,25,23,20,35,42,39,30
B．30,20,10,15,23,25,39,35,42
C．15,10,23,25,20,35,42,39,30
D．10,15,20,23,25,30,35,39,42

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q54 原页片段

查看解析

Q55¶

若 T'是由有序树 T 转换而来的二叉树，则 T 中结点的后根序列就是 T'中结点的（）序列。

A．先序
B．中序
C．后序
D．层序

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q55 原页片段

查看解析

Q56¶

如果用孩子兄弟链来表示一棵具有 n(n>1)个节点的树，则在该存储结构中（）。

A．至多有 n-1 个非空的右指针域
B．至少有两个空的右指针域
C．至少有两个非空的左指针域
D．至多有 n-1 个空的右指针域

查看解析

Q57¶

如果森林 F 采用“孩子-兄弟”表示法对应的二叉树是 16 个结点的完全二叉树，问：森林 F 中树的数目和最大树的结点个数分别为（）。

A．2 和 8
B．2 和 9
C．4 和 8
D．4 和 9

查看解析

Q58¶

设森林 F 中有 3 棵树，第一、第二、第三棵树的结点个数分别为〔公式/符号见原页版面片段〕1，〔公式/符号见原页版面片段〕2和〔公式/符号见原页版面片段〕3。将森林 F 转换成对应的二叉树 T，若以第一棵树的根结点作为 T 的根结点，则 T 的根结点的右子树上的结点个数是（）。

A．〔公式/符号见原页版面片段〕1
B．〔公式/符号见原页版面片段〕1 + 〔公式/符号见原页版面片段〕3
C．〔公式/符号见原页版面片段〕3
D．〔公式/符号见原页版面片段〕2 + 〔公式/符号见原页版面片段〕3

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q58 原页片段

查看解析

Q59¶

采用双亲表示法描述一棵树，则具有 n 个结点的树至少需要（）个指向双亲的指针。

A．n
B．n - 2
C．n - 1
D．2n

查看解析

Q60¶

若某个森林转换的二叉树是一棵高度为 h 的满二叉树，那么关于原森林说法错误的是（）。

A．有 h 棵树
B．分支结点有2ℎ−1 − 1
C．第 i 棵树的结点个数是2ℎ−〔公式/符号见原页版面片段〕
D．第 i 棵树的度为 h-i-1

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q60 原页片段

查看解析

Q61¶

若一棵树有 4 个结点，那么其所有可能的树型有（）种。

A．4
B．5
C．14
D．24

查看解析

Q62¶

已知森林 F 对应的二叉树为 T，且该二叉树是一棵 BST，其后序序列是 1,3,4,2,7,9,8,10,6,5，那么在森林 F 中说法错误的是（）。

A．有 3 棵树
B．第一棵树的后根遍历是升序序列
C．森林的度为 2
D．原森林的先根遍历是 5,2,1,3,4,6,10,8,7,9

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q62 原页片段

查看解析

Q63¶

某二叉树结点的中序序列为 BDAECF，后序序列为 DBEFCA，则该二叉树对应的森林包括（）棵树。

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

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q63 原页片段

查看解析

Q64¶

设 F 是由 T1、T2 和 T3 三棵树组成的森林，与 F 对应的二叉树为 B，T1、T2 和 T3 的结点数分别为 N1、N2 和 N3，则二叉树 B的根结点的左子树的结点数为（）。

A．N1-1
B．N2-1
C．N2+N3
D．N1+N3

查看解析

Q65¶

下列说法错误的是（）。

A．哈夫曼树是带权路径长度最短的树，路径上权值较大的节点离根较近。
B．在先序遍历二叉树的序列中，任何节点其子树的所有节点都是直接跟在该节点之后的。
C．存在这样的二叉树，对它采用任何次序的遍历，结果都相同。
D．若一个叶子节点是某二叉树先序遍历序列中的最后一个节点，则它必是该树中序遍历序列中的最后一个节点。

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q65 原页片段

查看解析

Q66¶

下列说法正确的是（）。
I．所有叶节点深度一致的二叉树，必为完全二叉树。
II．完全二叉树的子树，也一定是完全二叉树。
III．在 Huffman 算法过程中，权重小的内部节点必然早于权重大的内部节点被创建。
IV．由同一组互异关键码，按不同次序逐个插入而生成的 BST 必互异。V．在 AVL 树中删除节点之后若树高降低，则必然做过旋转调整

A．I、II、III、IV
B．II、III、IV、V
C．II、III
D．II、III、V

查看解析

Q67¶

有 5 个字符，根据其使用频率设计对应的哈夫曼编码，以下哪个是不可能的哈夫曼编码（）。

A．000，001，010，011，1
B．0000，0001，001，01，1
C．000，001，01，10，11
D．00，100，101，110，111

查看解析

Q68¶

已知字符集{a, b, c, d, e, f}，若各字符出现的次数分别为 6, 3, 8, 2, 10, 4，则对应字符集中各字符的哈夫曼编码可能是（）。

A．00, 1011, 01, 1010, 11, 100
B．00, 100, 110, 000, 0010, 01
C．10, 1011, 11, 0011, 00, 010
D．0011, 10, 11, 0010, 01, 000

查看解析

Q69¶

下列关于哈夫曼树和哈夫曼编码的陈述中，正确的是（）。

A．一个数据文件由 8 位定长度的字符组成，字符集内所有的 256个字符出现的频率大致相同，最高的频率低于最低频率的 2 倍，那么此时哈夫曼编码比 8 位固定长度编码更有效
B．哈夫曼树中度为 1 的结点数等于度为 2 和度为 0 的结点数之差
C．哈夫曼树的结点总数不能是偶数
D．若从二叉树的任一结点出发，到根结点的路径上所经结点的序列按其关键字有序，则该二叉树一定不是一棵哈夫曼树

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q69 原页片段

查看解析

Q70¶

以下说法错误的是（）。

A．一般在哈夫曼树中，权值越大的叶子离根结点越近
B．哈夫曼树中没有度数为 1 的分支结点
C．若初始森林中共有 n 棵二叉树，最终求得的哈夫曼树共有 2n-1 个结点
D．若初始森林中共有 n 棵二叉树，进行 n 次合并后才能剩下一棵最终的哈夫曼树

查看解析

Q71¶

假设某段通信电文仅由 6 个字母 ABCDEF 组成，字母在电文中出现的频率分别为 2，3，7，15，4，6。根据这些频率作为权值构造哈夫曼编码，最终构造出的哈夫曼树带权路径长度与字母 B的哈夫曼编码分别为（这里假定左节点的值小于右节点的值）（）。

A．86，1011
B．70，1000
C．86，0001
D．70，0010

查看解析

Q72¶

下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是（）。

A．26，16，5 和 26，10，6
B．26，16，8 和 26，10，5
C．26，10，5 和 26，12，7
D．26，16，7 和 26，16，8

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q72 原页片段

查看解析

Q73¶

下列说法正确的是（）。

A．哈夫曼树是带权路径长度最小的二叉树
B．哈夫曼树是完全二叉树
C．二叉树是度为 2 的有序树
D．在任意一棵二叉排序树中删除一个分支节点，接着又将该结点插入到二叉排序树中，则所得到的二叉排序树和删除前的二叉排序树相同

查看解析

Q74¶

若度为 m的哈夫曼树中，叶结点个数为 n，则非叶结点的个数为（）。

A．n-1
B．〔公式/符号见原页版面片段〕 − 1
C．〔公式/符号见原页版面片段〕−1 〔公式/符号见原页版面片段〕−1
D．⌈〔公式/符号见原页版面片段〕−1 ⌉-1

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q74 原页片段

查看解析

Q75¶

并查集中最核心的两个操作是：①查找，查找两个元素是否属于同一个集合；②合并，若两个元素不属于同一个集合，且所在的两个集合互不相交，则合并这两个集合。假设初始长度为 10(0～9)的并查集，按 1-2、3-4、5-6、7-8、8-9、1-8、0-5、1-9 的顺序进行合并操作，最终并查集共有（）个集合。

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

查看解析

Q76¶

下列关于并查集的说法中，正确的是（）。

A．并查集不能检测图中是否存在环路的问题
B．通过路径优化后的并查集在最坏情况下的高度仍是 O(n)
C．Find 操作返回集合中元素个数的相反数，它用来作为某个集合的标志
D．并查集基于树的双亲表示法

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q76 原页片段

查看解析

Q77¶

下列关于并查集的叙述中，（）是错误的。

A．并查集是用双亲表示法存储的树
B．并查集可用于实现克鲁斯卡尔算法
C．并查集可用于判断无向图的连通性
D．在长度为 n 的并查集中进行查找操作的时间复杂度为〔公式/符号见原页版面片段〕(〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕)

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q77 原页片段

查看解析

Q78¶

下列关于并查集的说法，错误的是（）。
I．并查集采用的是树的双亲表示法
II．一个集合中根结点的双亲域的绝对值表示集合中的结点个数
III．Find()操作返回的一定是负值
IV．改进的 Union()操作使其本身的时间复杂度降低了V．在 Union 改进后，进一步，Find()经过压缩路径优化后，可使集合树的深度为〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕

A．III、V
B．IV、V
C．II、III
D．III、IV、V

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q78 原页片段

查看解析

Q79¶

有个并查集，元素编号为 1 ～ 8。初始时，每个元素各自构成一个集合，每个元素的双亲都是自己，即 parent[i]=i。并查集操作规则如下：find(x)：查找元素 x 所在集合的根结点，并在查找过程中进行路径压缩。union(x, y)：先分别使用 find 查找 x 和 y 所在集合的根结点，记为 rx 和 ry。如果 rx 和 ry 不同，则将 y 所在集合的根结点 ry 挂到 x 所在集合的根结点 rx 下面。现执行如下操作序列：union(1, 2)，union(3, 4)，union(2, 4)，union(5, 6)，union(7, 8)，union(6, 8)，union(4, 8)，现对该并查集的说法正确的是（）。

A．parent[8]=1
B．parent[4]=3
C．find(8)=7
D．find(6)=1

原页版面片段（用于核对图表、公式、矩阵或代码）

第5章 Q79 原页片段

查看解析

Q80¶

将 n 个结点的森林 F 转化为对应的二叉树 BT，下列叙述正确的是（）。
I. 若 BT 根结点一直往右遍历可以得到 k 个结点（包括根节点本身），那么 F中有 n-k 条边
II. 若 F 中有 m 个分支结点，BT 中一定有 m+1 个右指针为空的结点
III. 若 BT 中有 p 个结点无左孩子，F 中一定有 p 个叶子结点
IV. 若 BT 是一棵高度为 h 的完全二叉树（根节点高度为 1），F 中一定有 h 棵树

A．II、III
B．I、II、III
C．II、III、IV
D．全对

查看解析

Q81¶

在由 4 个字符组成的字符集 S 中，各字符出现的频次分别为 6,5,3,4，为 S 构造的哈夫曼编码的加权平均长度为（）。

A．1
B．2
C．36
D．18

查看解析

Q82¶

将树转换为对应的二叉树，若在二叉树中，结点 u 是结点 v 的叔叔，那么在森林中，u、v的关系不可能是（）。

A．叔叔和侄子
B．有共同的爷爷
C．侄子和叔叔
D．兄弟

查看解析

Relax1000 数据结构 · 第5章 树 · 题目¶

第5章 树¶

Q1¶

Q2¶

Q3¶

Q4¶

Q5¶

Q6¶

Q7¶

Q8¶

Q9¶

Q10¶

Q11¶

Q12¶

Q13¶

Q14¶

Q15¶

Q16¶

Q17¶

Q18¶

Q19¶

Q20¶

Q21¶

Q22¶

Q23¶

Q24¶

Q25¶

Q26¶

Q27¶

Q28¶

Q29¶

Q30¶

Q31¶

Q32¶

Q33¶

Q34¶

Q35¶

Q36¶

Q37¶

Q38¶

Q39¶

Q40¶

Q41¶

Q42¶

Q43¶

Q44¶

Q45¶

Q46¶

Q47¶

Q48¶

Q49¶

Q50¶

Q51¶

Q52¶

Q53¶

Q54¶

Q55¶

Q56¶

Q57¶

Q58¶

Q59¶

Q60¶

Q61¶

Q62¶

Q63¶

Q64¶

Q65¶

Q66¶

Q67¶

Q68¶

Q69¶

Q70¶

Q71¶

Q72¶

Q73¶

Q74¶

Q75¶

Q76¶

Q77¶

Q78¶

Relax1000 数据结构 · 第5章树 · 题目¶

第5章树¶