1、计算机专业基础综合历年真题试卷汇编 1及答案解析(总分：62.00，做题时间：90 分钟)一、单项选择题(总题数：27，分数：54.00)1.单项选择题 1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.先序序列为 a，b，c，d 的不同二叉树的个数是_。（分数：2.00）A.13B.14C.15D.163.假设栈初始为空，将中缀表达式 ab+(c*d-e*f)g 转换为等价的后缀表达式的过程中，当扫描到 f时，栈中的元素依次是_。（分数：2.00）A.+(*-B.+(-*C.+(*-*D.+-*4.在一棵度为 4的树 T中，若有 20个度为 4的
2、结点，10 个度为 3的结点，1 个度为 2的结点，10 个度为1的结点，则树 T的叶结点个数是_。（分数：2.00）A.41B.82C.113D.1225.已知一棵完全二叉树的第 6层(设根为第 1层)有 8个叶结点，则该完全二叉树的结点个数最多是_。（分数：2.00）A.39B.52C.111D.1196.若一棵完全二叉树有 768个结点，则该二叉树中叶结点的个数是_。（分数：2.00）A.257B.258C.384D.3857.给定二叉树如下图所示。设 N代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树。若遍历后的结点序列为 3，1，7，5，6，2，4，则其遍历方式是_。
3、（分数：2.00）A.LRNB.NRLC.RLND.KNL8.先序序列为 a，b，c，d 的不同二叉树的个数是_。（分数：2.00）A.13B.14C.15D.169.若一棵二叉树的前序遍历序列和后序遍历序列分别为 1，2，3，4 和 4，3，2，1，则该二叉树的中序遍历序列不会是_。（分数：2.00）A.1，2，3，4B.2，3，4，1C.3，2，4，1D.4，3，2，110.若一棵二叉树的前序遍历序列为 a，e，b，d，c，后序遍历序列为 b，c，d，e，a，则根结点的孩子结点_。（分数：2.00）A.只有 eB.有 e、bC.有 e、cD.无法确定11.对于下列关键字序列，不可能构成某二
4、叉排序树中一条查找路径的序列是_。（分数：2.00）A.95，22，91，24，94，71B.92，20，91，34，88，35C.21，89，77，29，36，38D.12，25，71，68，33，3412.在任意一棵非空二叉排序树 T 1 中，删除某结点 v之后形成二叉排序树 T 2 ，再将 v插入 T 2 形成二叉排序树 T 3 。下列关于 T 1 与 T 3 的叙述中，正确的是_。 若 v是 T 1 的叶结点，则 T 1 与 T 3 不同 若 v是 T 1 的叶结点，则 T 1 与 T 3 相同 若 v不是 T 1 的叶结点，则 T 1 与 T 3 不同 若 v不是 T 1 的叶结点，
5、则 T 1 与 T 3 相同（分数：2.00）A.仅、B.仅、C.仅、D.仅、13.下列二叉排序树中，满足平衡二叉树定义的是_。 （分数：2.00）A.B.C.D.14.在下图所示的平衡二叉树中，插入关键字 48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是_。 （分数：2.00）A.13，48B.24，48C.24，53D.24，9015.若平衡二叉树的高度为 6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结点总数为_。（分数：2.00）A.10B.20C.32D.3316.若将关键字 1，2，3，4，5，6，7 依次插入到初始为空的平
6、衡二叉树 T中，则 T中平衡因子为 0的分支结点的个数是_。（分数：2.00）A.0B.1C.2D.317.现有一棵无重复关键字的平衡二叉树(AVL 树)，对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是_。（分数：2.00）A.根结点的度一定为 2B.树中最小元素一定是叶结点C.最后插入的元素一定是叶结点D.树中最大元素一定是无左子树18.将森林转换为对应的二叉树，若在二叉树中，结点 u是结点 v的父结点的父结点，则在原来的森林中，u和 v可能具有的关系是_。父子关系兄弟关系u 的父结点与 v的父结点是兄弟关系（分数：2.00）A.只有B.和C.和D.、和19.己知
7、一棵有 2011个结点的树，其叶结点个数为 116，该树对应的二叉树中无右孩子的结点个数是_。（分数：2.00）A.115B.116C.1895D.189620.将森林 F转换为对应的二叉树 T，F 中叶结点的个数等于_。（分数：2.00）A.T中叶结点的个数B.T中度为 1的结点个数C.T中左孩子指针为空的结点个数D.T中右孩子指针为空的结点个数21.下列线索二叉树中(用虚线表示线索)，符合后序线索树定义的是_。 （分数：2.00）A.B.C.D.22.若 X是后序线索二叉树中的叶结点，且 X存在左兄弟结点 Y，则 X的右线索指向的是_。（分数：2.00）A.X的父结点B.以 Y为根的子树的
8、最左下结点C.X的左兄弟结点 YD.以 Y为根的子树的最右下结点23.若对如下的二叉树进行中序线索化，则结点 x的左、右线索指向的结点分别是_。（分数：2.00）A.e、cB.e、aC.d、cD.b、a24.对 n(n2)个权值均不相同的字符构造哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是_。（分数：2.00）A.该树一定是一棵完全二叉树B.树中一定没有度为 1的结点C.树中两个权值最小的结点一定是兄弟结点D.树中任一非叶结点的权值一定不小于下一层任一结点的权值25.5个字符有如下 4种编码方案，不是前缀编码的是_。（分数：2.00）A.01，0000，0001，001，1B.011，000
9、，001，010，1C.000，001，010，011，100D.0，100，110，1110，110026.下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是_。（分数：2.00）A.24，10，5 和 24，10，7B.24，10，5 和 24，12，7C.24，10，10 和 24，14，11D.24，10，5 和 24，14，627.下列关于无向连通图特性的叙述中，正确的是_。所有顶点的度之和为偶数边数大于顶点个数减 1至少有一个顶点的度为 1（分数：2.00）A.只有B.只有C.和D.和二、综合应用题(总题数：3，分数：8.00)28.综合应用题 41-
10、47小题。_29.已知有 6个顶点(顶点编号为 05)的有向带权图 G，其邻接矩阵 A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。 （分数：2.00）_二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树 T，采用二叉链表存储，结点结构为： （分数：6.00）(1).给出算法的基本设计思想；（分数：2.00）_(2).使用 C或 C+语言，给出二叉树结点的数据类型定义；（分数：2.00）_(3).根据设计思想，采用 C或 C+语言描述算法，关键之处给出注释。（分数：2.00）_计算机专业基础综合历年真题试卷汇编 1答案解析(总分：62.00，做题时
11、间：90 分钟)一、单项选择题(总题数：27，分数：54.00)1.单项选择题 1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_解析：2.先序序列为 a，b，c，d 的不同二叉树的个数是_。（分数：2.00）A.13B.14 C.15D.16解析：解析：根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。因为前序序列和中序序列可以唯一地确定一棵二叉树，所以题意相当于“以序列 a，b，c，d 为入栈次序，则出栈序列的个数为?”，对于 n个不同元素进栈，出栈序列的个数
12、为 3.假设栈初始为空，将中缀表达式 ab+(c*d-e*f)g 转换为等价的后缀表达式的过程中，当扫描到 f时，栈中的元素依次是_。（分数：2.00）A.+(*-B.+(-* C.+(*-*D.+-*解析：解析：将中缀表达式转换为后缀表达式的算法思想如下： 从左向右开始扫描中缀表达式； 遇到数字时，加入后缀表达式； 遇到运算符时： a若为(，入栈； b若为)，则依次把栈中的的运算符加入后缀表达式中，直到出现(，从栈中删除(； c若为除括号外的其他运算符，当其优先级高于除(以外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低
13、的或者遇到了一个左括号为止。 当扫描的中缀表达式结束时，栈中的所有运算符依次出栈加入后缀表达式。4.在一棵度为 4的树 T中，若有 20个度为 4的结点，10 个度为 3的结点，1 个度为 2的结点，10 个度为1的结点，则树 T的叶结点个数是_。（分数：2.00）A.41B.82 C.113D.122解析：解析：设树中度为 i(i=0，1，2，3，4)的结点数分别为 N i ，树中结点总数为 N，则树中各结点的度之和等于 N-1，即 N=1+N 1 +2N 2 +3N 3 +4N 4 =N 0 +N 1 +N 2 +N 3 +N 4 ，根据题设中的数据，即可得到 N 0 =82，即树 T的叶
14、结点的个数是 82。5.已知一棵完全二叉树的第 6层(设根为第 1层)有 8个叶结点，则该完全二叉树的结点个数最多是_。（分数：2.00）A.39B.52C.111 D.119解析：解析：完全二叉树比满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层有叶结点。第 6层有叶结点则完全二叉树的高度可能为 6或 7，显然树高为 7时结点更多。若第 6层上有 8个叶结点，则前六层为满二叉树，而第 7层缺失了 82=16个叶结点，故完全二叉树的结点个数最多为(2 7 -1)-16=111个结点。6.若一棵完全二叉树有 768个结点，则该二叉树中叶结点的个数是_。
15、（分数：2.00）A.257B.258C.384 D.385解析：解析：根据完全二叉树的性质，最后一个分支结点的序号为7.给定二叉树如下图所示。设 N代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树。若遍历后的结点序列为 3，1，7，5，6，2，4，则其遍历方式是_。 （分数：2.00）A.LRNB.NRLC.RLND.KNL 解析：解析：分析遍历后的结点序列，可以看出根结点是在中间访问，而右子树结点在左子树之前，即遍历的方式是 RNL。本题考查的遍历方法并不是二叉树的 3种基本遍历方法，对于考生而言，重要的是要掌握遍历的思想。8.先序序列为 a，b，c，d 的不同二叉树的个数是
16、_。（分数：2.00）A.13B.14 C.15D.16解析：解析：根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。因为前序序列和中序序列可以唯一地确定一棵二叉树，所以题意相当于“以序列 a，b，c，d 为入栈次序，则出栈序列的个数为?”，对于 n个不同元素进栈，出栈序列的个数为 9.若一棵二叉树的前序遍历序列和后序遍历序列分别为 1，2，3，4 和 4，3，2，1，则该二叉树的中序遍历序列不会是_。（分数：2.00）A.1，2，3，4B.2，3，4，1C.3，2，4，1 D.4，3，2，1解析：解析：
17、前序序列为 NLR，后序序列为 LRN，由于前序序列和后序序列刚好相反，故不可能存在一个结点同时存在左右孩子，即二叉树的高度为 4。1 为根结点，由于根结点只能有左孩子(或右孩子)，因此，在中序序列中，1 或在序列首或在序列尾，ABCD 皆满足要求。仅考虑以 1的孩子结点 2为根结点的子树，它也只能有左孩子(或右孩子)，因此，在中序序列中，2 或在序列首或序列尾，ABD 皆满足要求。10.若一棵二叉树的前序遍历序列为 a，e，b，d，c，后序遍历序列为 b，c，d，e，a，则根结点的孩子结点_。（分数：2.00）A.只有 e B.有 e、bC.有 e、cD.无法确定解析：解析：前序序列和后序序
18、列不能唯一确定一棵二叉树，但可以确定二叉树中结点的祖先关系：当两个结点的前序序列为 XY与后序序列为 YX时，则 X为 Y的祖先。考虑前序序列 a ，e，b，d，c、后序序列 b，c，d，e， a ，可知 a为根结点，e 为 a的孩子结点；此外，a 的孩子结点的前序序列 e ，b，d，c、后序序列 b，c，d， e ，可知 e是 bcd的祖先，故根结点的孩子结点只有 e。故选 A。11.对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是_。（分数：2.00）A.95，22，91，24，94，71 B.92，20，91，34，88，35C.21，89，77，29，36，38D.12
19、，25，71，68，33，34解析：解析：各选项对应的查找过如下图，BCD 对应的查找树都是二叉排序树，A 对应的查找树不是二叉排序树，因为在 91为根的左子树中出现了比 91大点的结点 94。12.在任意一棵非空二叉排序树 T 1 中，删除某结点 v之后形成二叉排序树 T 2 ，再将 v插入 T 2 形成二叉排序树 T 3 。下列关于 T 1 与 T 3 的叙述中，正确的是_。 若 v是 T 1 的叶结点，则 T 1 与 T 3 不同 若 v是 T 1 的叶结点，则 T 1 与 T 3 相同 若 v不是 T 1 的叶结点，则 T 1 与 T 3 不同 若 v不是 T 1 的叶结点，则 T 1
20、 与 T 3 相同（分数：2.00）A.仅、B.仅、C.仅、 D.仅、解析：解析：在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中，如果删除的结点是叶子结点，那么在插入结点后，后来的二叉排序树与删除结点之前相同。如果删除的结点不是叶子结点，那么再插入这个结点后，后来的二叉树会发生变化，不完全相同。13.下列二叉排序树中，满足平衡二叉树定义的是_。 （分数：2.00）A.B. C.D.解析：解析：根据平衡二叉树的定义有，任意结点的左、右子树高度差的绝对值不超过 1。而其余 3个选项均可以找到不符合该条件的结点。在做题的过程中，如果答案不太明显，可以把每个非叶结点的平衡因子都写出来再进
21、行判断。14.在下图所示的平衡二叉树中，插入关键字 48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是_。 （分数：2.00）A.13，48B.24，48C.24，53 D.24，90解析：解析：插入 48以后，该二叉树根结点的平衡因子由-1 变为-2，在最小不平衡子树根结点的右子树(R)的左子树(L)中插入新结点引起的不平衡属于 RL型平衡旋转，需要做两次旋转操作(先右旋后左旋)。15.若平衡二叉树的高度为 6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结点总数为_。（分数：2.00）A.10B.20 C.32D.33解析：解析：所有非
22、叶结点的平衡因子均为 1，即平衡二叉树满足平衡的最少结点情况，如下图所示。 16.若将关键字 1，2，3，4，5，6，7 依次插入到初始为空的平衡二叉树 T中，则 T中平衡因子为 0的分支结点的个数是_。（分数：2.00）A.0B.1C.2D.3 解析：解析：利用 7个关键字构建平衡二叉树 T，平衡因子为 O的分支结点个数为 3，构建的平衡二叉树如下图所示。构造及调整的过程如下：17.现有一棵无重复关键字的平衡二叉树(AVL 树)，对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是_。（分数：2.00）A.根结点的度一定为 2B.树中最小元素一定是叶结点C.最后插入的元
23、素一定是叶结点D.树中最大元素一定是无左子树 解析：解析：只有两个结点的平衡二叉树的根结点的度为 1，A 错误。中序遍历后可以得到一个降序序列，树中最小元素一定无左子树(可能有右子树)，因此不一定是叶结点，B 错误。最后插入的结点可能会导致平衡调整，而不一定是叶结点，C 错误。18.将森林转换为对应的二叉树，若在二叉树中，结点 u是结点 v的父结点的父结点，则在原来的森林中，u和 v可能具有的关系是_。父子关系兄弟关系u 的父结点与 v的父结点是兄弟关系（分数：2.00）A.只有B.和 C.和D.、和解析：解析：森林与二叉树的转换规则为“左孩子右兄弟”。在最后生成的二叉树中，父子关系在对应森林
24、关系中可能是兄弟关系或原本就是父子关系。 情形：若结点 v是结点 u的第二个孩子结点，在转换时，结点 v就变成结点 u第一个孩子的右孩子，符合要求。 情形结点 u和 v是兄弟结点的关系，但二者之中还有一个兄弟结点 k，则转换后，结点 v就变为结点 k的右孩子，而结点 k则是结点 u的右孩子，符合要求。 情形：若结点 u的父结点与 v的父结点是兄弟关系，则转换后，结点 u和 v分别在两者最左父结点的两棵子树中，不可能出现在同一条路径中。19.己知一棵有 2011个结点的树，其叶结点个数为 116，该树对应的二叉树中无右孩子的结点个数是_。（分数：2.00）A.115B.116C.1895D.18
25、96 解析：解析：树转换为二叉树时，树中每一个分支结点的所有子结点中的最右子结点无右孩子，根结点转换后也没有右孩子，因此，对应的二叉树中无右孩子的结点个数=分支结点数+1=2011-116+1=1896。通常本题应采用特殊法解，设题意中的树是如下图所示的结构，则对应的二叉树中仅有前 115个叶结点有右孩子，故无右孩子的结点个数=2011-115=1896。20.将森林 F转换为对应的二叉树 T，F 中叶结点的个数等于_。（分数：2.00）A.T中叶结点的个数B.T中度为 1的结点个数C.T中左孩子指针为空的结点个数 D.T中右孩子指针为空的结点个数解析：解析：将森林转化为二叉树即相当于用孩子兄
26、弟表示法表示森林。在变化过程中，原森林某结点的第一个孩子结点作为它的左子树，它的兄弟作为它的右子树。那么森林中的叶结点由于没有孩子结点，那么转化为二叉树时，该结点就没有左结点，所以 F中叶结点的个数就等于 T中左孩子指针为空的结点个数，选 C。此题还可以通过一些特例来排除 A、B、D 选项。21.下列线索二叉树中(用虚线表示线索)，符合后序线索树定义的是_。 （分数：2.00）A.B.C.D. 解析：解析：题中所给二叉树的后序序列为 d，b，c，a。结点 d无前驱和左子树，左链域空，无右子树，右链域指向其后继结点 b；结点 b无左子树，左链域指向其前驱结点 d；结点 c无左子树，左链域指向其前
27、驱结点 b，无右子树，右链域指向其后继结点 a。故选 D。22.若 X是后序线索二叉树中的叶结点，且 X存在左兄弟结点 Y，则 X的右线索指向的是_。（分数：2.00）A.X的父结点 B.以 Y为根的子树的最左下结点C.X的左兄弟结点 YD.以 Y为根的子树的最右下结点解析：解析：根据后序线索二叉树的定义，X 结点为叶子结点且有左兄弟，那么这个结点为右孩子结点，利用后序遍历的方式可知 X结点的后序后继是其父结点，即其右线索指向的是父结点。为了更加形象，在解题的过程中可以画出如下草图。23.若对如下的二叉树进行中序线索化，则结点 x的左、右线索指向的结点分别是_。（分数：2.00）A.e、cB.
28、e、aC.d、cD.b、a 解析：解析：线索二叉树的线索实际上指向的是相应遍历序列特定结点的前驱结点和后继结点，所以先写出二叉树的中序遍历序列：edbxac，中序遍历中在 x左边和右边的字符，就是它在中序线索化的左、右线索，即 b、a，选 D。24.对 n(n2)个权值均不相同的字符构造哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是_。（分数：2.00）A.该树一定是一棵完全二叉树 B.树中一定没有度为 1的结点C.树中两个权值最小的结点一定是兄弟结点D.树中任一非叶结点的权值一定不小于下一层任一结点的权值解析：解析：哈夫曼树为带权路径长度最小的二叉树，不一定是完全二叉树。哈夫曼树中没有度为
29、1的结点，B 正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左、右子树构造一棵新的二叉树，C 正确；哈夫曼树中任一非叶结点 P的权值为其左、右子树根结点权值之和，其权值不小于其左、右子树根结点的权值，在与结点 P的左、右子树根结点处于同层的结点中，若存在权值大于结点 P权值的结点 Q，那么结点 Q的兄弟结点中权值较小的一个应该与结点 P作为左、右子树构造新的二叉树。综上可知，哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。25.5个字符有如下 4种编码方案，不是前缀编码的是_。（分数：2.00）A.01，0000，0001，001，1B.011，000，001，010，1C.
30、000，001，010，011，100D.0，100，110，1110，1100 解析：解析：前缀编码的定义是在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。选项 D中编码 110是编码 1100的前缀，违反了前缀编码的规则，所以 D不是前缀编码。26.下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是_。（分数：2.00）A.24，10，5 和 24，10，7B.24，10，5 和 24，12，7C.24，10，10 和 24，14，11D.24，10，5 和 24，14，6 解析：解析：在哈夫曼树中，左右孩子权值之和为父结点权值。仅以分析选项 A
31、为例：若两个 10分别属于两棵不同的子树，根的权值不等于其孩子的权值和，不符：若两个 10属同棵子树，其权值不等于其两个孩子(叶结点)的权值和，不符。B、C 选项的排除方法一样。27.下列关于无向连通图特性的叙述中，正确的是_。所有顶点的度之和为偶数边数大于顶点个数减 1至少有一个顶点的度为 1（分数：2.00）A.只有 B.只有C.和D.和解析：解析：每条边都连接了两个结点，在计算顶点的度之和时每条边都被计算了两次(出度和入度)，故所有顶点的度之和为边数的两倍，正确。n 个顶点、n-1 条边可以构成无向连通图，比如树，错误。顶点数为 N(N1)的无向完全图中不存在度为 1的顶点，错误。二、综
32、合应用题(总题数：3，分数：8.00)28.综合应用题 41-47小题。_解析：29.已知有 6个顶点(顶点编号为 05)的有向带权图 G，其邻接矩阵 A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。 （分数：2.00）_正确答案：(正确答案：在上三角矩阵 A66中，第 1行至第 5行主对角线上方的元素个数分别为5、4、3、2、1，由此可以画出压缩存储数组中的元素所属行的情况，如下图所示。 采用“平移”的思想，分别将前 5、4、3、2、1 个元素，移动到矩阵对角线(“0”)右边的行上。 故，图 G的邻接矩阵A如下图所示。 )解析：解析：考查上三角矩阵的存储。二叉树的带权路径长度(W
33、PL)是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树 T，采用二叉链表存储，结点结构为： （分数：6.00）(1).给出算法的基本设计思想；（分数：2.00）_正确答案：(正确答案：算法的基本设计思想： 基于先序递归遍历的算法思想是用一个 static变量记录、wpl，把每个结点的深度作为递归函数的 一个参数传递，算法步骤如下： 若该结点是叶结点，那么变量 wpl加上该结点的深度与权值之积； 若该结点是非叶结点，那么若左子树不为空，对左子树调用递归算法：若右子树不为空，对右子树 调用递归算法，深度参数均为本结点的深度参数加 1； 最后返回计算出的 wpl即可。 基于层次遍历的算法思想是
34、使用队列进行层次遍历，并记录当前的层数， 当遍历到叶结点时，累计 wpl； 当遍历到非叶结点时，把该结点的子树加入队列； 当某结点为该层的最后一个结点时，层数自增 1； 队列空时遍历结束，返回 wpl。)解析：(2).使用 C或 C+语言，给出二叉树结点的数据类型定义；（分数：2.00）_正确答案：(正确答案：二叉树结点的数据类型定义如下： typedef struct BiTNode int weight； struct BiTNode *lchild，*rchild； BiTNode，*BiTree；)解析：(3).根据设计思想，采用 C或 C+语言描述算法，关键之处给出注释。（分数：2.
35、00）_正确答案：(正确答案：算法的代码如下： 基于先序遍历的算法： int WPL(BiTree root) return wpl_PreOrder(root，0)； int wpl PreOrder(BiTree root，int deep) static int wpl=0；定义一个 static变量存储 wpl if(root-lchild=NuLLroot-lchild=NULL)若为叶结点，累积wpl wpl+=deep*root-weight， if(root-ichiid!；NuLL)若左子树不空，对左子树递归遍历 wpl_PreOrder(root-ichild，deep+1
36、)， if(root-rchiidI=NULL)若右子树不空，对右于树递归遍历 wpl_PreOrder(root-rchild，deep+1)； return wpl； 基于层次遍历的算法： #define MaxSize 100设置队列的最大容量 int wpl LevelOrder(BiTree root) BiTree qMaxSize；声明队列，end1 为头指针，end2 为尾指针 int end1，end2，队列最多容纳 MaxSize-1个元素 end1=end2=0；头指针指向队头元素，尾指针指向队尾的后一个元素 int wpl=deep=0；初始化wpl和深度 BiTree
37、 lastNode；lastNode 用来记录当前层的最后一个结点 BiTree newlastNode；newlastNode 用来记录下一层的最后一个结点 lastNode=root；lastNode 初始化为根结点 newlastNode=NULL；newlastNode 初始化为空 qend2+=root；根结点入队 while(end1!=end2)f层次遍历，若队列不空则循环 BiTree t=qend1+；拿出队列中的头一个元素 if(t-ichild=NULL&t-lchild=NULL) wpl+=deep*t-weight； 若为叶结点，统计wpl if(t-ichild!
38、=NULL)若非叶结点把左结点入队 qend2+=t-ichild； newlastNode=t-ichiid； 并设下一层的最后一个结点为该结点的左结点 if(t-rchild!=NULL)处理叶结点 qend2+=t-rchild； newlastNode=t-rchild； if(t=lastNode)若该结点为本层最后一个结点，更新 lastNode lastNode=newlastNode； deep+=1；层数加 1 return wpl；返回 wpl )解析：解析：考查二叉树的带权路径长度，二叉树的带权路径长度为每个叶结点的深度与权值之积的总和，可以使用先序遍历或层次遍历解决问题。
