锦州医科大学医疗学院计算机考试期末
一、 单项选择题(总题数：27，分数：54.00)
1.单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）
__________________________________________________________________________________________
解析：
2.先序序列为a，b，c，d的不同二叉树的个数是_______。
（分数：2.00）
A.13
B.14 √
C.15
D.16
解析：解析：根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和中序
序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。因为前序序列和中序序列可以唯一地
确定一棵二叉树，所以题意相当于“以序列a，b，c，d为入栈次序，则出栈序列的个数为?”，对于n个n
不同元素进栈，出栈序列的个数为 C =14。2n
3.假设栈初始为空，将中缀表达式a／b+(c*d-e*f)／g转换为等价的后缀表达式的过程中，当扫描到f时，
栈中的元素依次是_______。（分数：2.00）
A.+(*-
B.+(-* √
C.／+(*-*
D.／+-*
解析：解析：将中缀表达式转换为后缀表达式的算法思想如下： 从左向右开始扫描中缀表达式； 遇到数
字时，加入后缀表达式； 遇到运算符时： a．若为‘(’，入栈； b．若为‘)’，则依次把栈中的的运算
符加入后缀表达式中，直到出现‘(’，从栈中删除‘(’； c．若为除括号外的其他运算符，当其优先级
高于除‘(’以外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级高和
优先级相等的运算符，直到一个比它优先级低的或者遇到了一个左括号为止。 当扫描的中缀
表达式结束时，
栈中的所有运算符依次出栈加入后缀表达式。
4.在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1
的结点，则树T的叶结点个数是_______。
（分数：2.00）
A.41
B.82 √
C.113
D.122
解析：解析：设树中度为i(i=0，1，2，3，4)的结点数分别为N ，树中结点总数为N，则树中
各结点的i
度之和等于N-1，即N=1+N +2N +3N +4N =N +N +N +N +N ，根据题设中的数据，即可得到
123401234
N =82，即树T的叶结点的个数是82。
0
5.已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点，则该完全二叉树的结点个数最多是_______。
（分数：2.00）
A.39
B.52
C.111 √
D.119
解析：解析：完全二叉树比满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满
二叉树，并且只有最后两层有叶结点。第6层有叶结点则完全二叉树的高度可能为6或7，显然树高为7
时结点更多。若第6层上有8个叶结点，则前六层为满二叉树，而第7层缺失了8×2=16个叶结点，故完
7
全二叉树的结点个数最多为(2 -1)-16=111个结点。
6.若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是_______。
（分数：2.00）
A.257
B.258
C.384 √
D.385
解析：解析：根据完全二叉树的性质，最后一个分支结点的序号为=384，故叶子结点的个数为
768-384=384。
7.给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历
后的结点序列为3，1，7，5，6，2，4，则其遍历方式是_______。
（分数：2.00）
A.LRN
B.NRL
C.RLN
D.KNL √
解析：解析：分析遍历后的结点序列，可以看出根结点是在中间访问，而右子树结点在左子树之前，即遍
二叉树公式历的方式是RNL。本题考查的遍历方法并不是二叉树的3种基本遍历方法，对于考生而言，重要的是要掌
握遍历的思想。
8.先序序列为a，b，c，d的不同二叉树的个数是_______。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。