18年408数据结构

第一题：

解析：这道题很简单，按部就班的做就可以了。

画出S1，S2两个栈的情况：
S1: S2:

        2 +

        3 -

        8 *

        5

从S1中依次弹出两个操作数2和3，从S2中弹出一个运算符+，执行3+2，将计算结果压入S1中。计算结果是5。

第二轮：

S1: S2:

5 -

8 *

        5

运算： 8-5=3.

第三轮：

S1: S2:

3

5 *

运算：5*3=15

答案选B

第二题：

解析：

队列是对头出队，队尾入队，栈是先进后出，先输出栈顶元素。

依次分析：
A.1出队并输出，2出队并输出，345存入栈中，5出栈并输出，6出队并输出，4出栈并输出，3出栈并输出，A正确。

B.1出队入栈，2出队并输出，3出队并输出，4出队并输出，5出队并输出，6出队并输出,1出栈并输出。B正确。

C.1出队入栈，2出队入栈，3,4,5,6出队并输出，接着栈内的栈顶元素是2，只能是2先输出，所以C错。

答案选C。

第三题：

解析：画个图分析一下就好了。

如图所示：因为只存上三角部分的元素（包含对角线元素），经分析可知第一层存12个元素，第二层存11个元素，第三层存10个元素，第四层存9个元素，第五层存8个元素，接着第6层只存m6,6，一共是12+11+10+9+8+1=51.

也就是说m6,6在N中是第51个元素，因此下标是50，答案选A

第四题：

解析：

方法一：对于一个n层的满二叉树，第n层的结点个数： $2^{n-1}$ ，结点总数： $2^{n}-1$ 。

经题目分析可知，该二叉树应该是一个满二叉树，设该二叉树有n层，则有 $2^{n-1}=k,n=\log 2(k) +1$

n层的满二叉树的结点个数：2^n-1，

$2^{\log 2(k)+1}-1=2k-1$

答案选A.

方法二：对于一个二叉树，我们说度为2的结点个数+1就是叶子结点的个数：

$n_{0}=n_{2}+1$ ，

题目说每个非叶子结点都有2个子结点，说明没有度为1的点，利用这条结论，我们可以推断出，结点总数=度为2的点+度为0的叶子结点，叶子结点个数告诉我们了：K，度为2的结点个数利用上面提到的结论可知： $n_{2}=k-1$ ,结点总数=k-1+k=2k-1。

答案选A。

第五题：

解析:
很显然要先构造一颗哈夫曼树：

a：00

b：1011

c：01

d：1010

e：11

f ：100

答案选A

第六题：

解析：比根结点大的是右子树，比根结点小的左子树。

其实不用那么麻烦，直接看就行，最左边的最小，最右边的最大。

从左到右依次是： $x_{1}<x_{3}<x_{5}<x_{4}<x_{2}$

答案选C

第七题：

解析：拓扑序列：依次找入度为0的点，并删除与它相关的连线。

一开始找入度为0的点：1和5。

从节点1开始：

1-5-2-3-6-4 A

1-5-2-6-3-4

从节点5开始：

5-1-2-3-6-4 C

5-1-2-6-3-4 B

D.节点5去掉之后2的入度不为0，D错。

答案选D。

第八题：

解析：

至少要每个节点的关键字个数最少，回顾一下B数的定义：

至少是3/2向上取整减一等于一个关键字，这就将问题转换成了高度为5的满二叉树有多少个结点的问题了： $2^{5}-1=31$

答案选B.

第九题：

解析：

H(22)=22%7=1 22存入1的位置

H0(43)=43%7=1

H1(43+1)=44%7=2 43存入2的位置

H0(15)=15%7=1

H1(15+1)=16%7=2

H1(16+1)=17%7=3 14存入3的位置

平均查找长度：所有关键字的查找次数 / 关键字个数=(1+2+3)/3 = 2

答案选C

第十题：

解析：

第一趟排序很明显：第一个数字原来是8现在变成1了，说明8和1进行了比较并交换了位置，d=5，同时我们可以得知是升序排序，第二趟是2和3交换了位置，很明显d=3，答案选D。

第十一题：

解析：考查堆排序

第一步：画出原始数组：

第二步：从最后一个结点的父节点开始排序。

7比5和4大，调整为根结点：

此时储存在数组中的序列是：6,1,7,9,8,4,5，排除BC

第三步：调整倒数第二个父节点，也就是1这个位置

找到根节点和孩子节点中最大的节点，这里很显然是9，将1和9交换一下位置。

此时储存在数组中的序列是：6,9,7,1,8,4,5，排除D

答案选A