数据结构填空选择复习题(无敌超全版).pdfVIP

⑶一棵二叉树的第i（i≥1）层最多有（）个结点；一棵有n（n0）个结点的满二叉树共有（）个叶子

结点和（）个非终端结点。

⑷设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（），最

小值是（）。

⑹具有100个结点的完全二叉树的叶子结点数为（）。

【解答】50

⑺已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树中有（）

⑼在具有n个结点的二叉链表中，共有（）个指针域，其中（）个指针域用于指向其左右孩子，剩下的

（）个指针域则是空的。

⑽在有n个叶子的哈夫曼树中，叶子结点总数为（），分支结点总数为（）。

⑶二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。

A空或只有一个结点B高度等于其结点数

C任一结点无左孩子D任一结点无右孩子

⑺任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（）。

A肯定不发生改变B肯定发生改变C不能确定D有时发生变化

⑻如果T是由有序树T转换而来的二叉树，那么T中结点的前序序列就是T中结点的（）序列，T中

结点的后序序列就是T中结点的（）序列。

A前序B中序C后序D层序

⑴在线索二叉树中，任一结点均有指向其前趋和后继的线索。

7．已知二叉树的中序和后序序列分别为CBEDAFIGH和CEDBIFHGA，试构造该二叉树。

【解答】二叉树的构造过程如图5-12所示。

8．对给定的一组权值W＝（5，2，9，11，8，3，7），试构造相应的哈夫曼树，并计算它的带权路径长

度。

【解答】构造的哈夫曼树如图5-13所示。

树的带权路径长度为：

WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2

=120

9．已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次，

对该字符串用[0，1]进行前缀编码，问该字符串的编码至少有多少位。

【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图5-14所示。其带权路径长度

=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，该字符串的编码长度至少为98位。

9．对于一棵具有n个结点的树，其所有结点的度之和为（）。

10．在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是（）。

⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）

条边，至多有（）条边。

⑵任何连通图的连通分量只有一个，即是（）。

⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。

⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的

（）遍历，它所用到的数据结构是（）。

⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal

算法求最小生成树的时间复杂度为（）。

⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。

⑵n个顶点的强连通图至少有（）条边，其形状是（）。

AnBn+1Cn-1Dn×(n-1)

E无回路F有回路G环状H树状

⑶含n个顶点的连通图中的任意一条简单路径，其长度不可能超过（）。

A1Bn/2Cn-1Dn

⑸图的生成树（），n个顶点的生成树有（）条边。

A唯一B不唯一C唯一性不能确定

DnEn+1Fn-1

⑹设无向图G=(V,E)和G=(V,E)，如果G是G的生成树，则下面的说法中错误的是（）。

AG为G的子图BG为G的连通分量

CG为G的极小连通子图且V=VDG是G的一个无环子图

⑺G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。

A6B7C8D9

⑼判定一个有向图是否存在回路除了可以利用拓扑排序