锦州医科大学医疗学院计算机考试期末.pdfVIP

锦州医科大学医疗学院计算机考试期末

一、单项选择题(总题数：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。本题考查的遍历方法并