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层的结点个数：
，结点总数：
。
经题目分析可知，该二叉树应该是一个满二叉树，设该二叉树有n层，则有
n层的满二叉树的结点个数：2^n-1，
答案选A.
方法二：对于一个二叉树，我们说度为2的结点个数+1就是叶子结点的个数：
，
题目说每个非叶子结点都有2个子结点，说明没有度为1的点，利用这条结论，我们可以推断出，结点总数=度为2的点+度为0的叶子结点，叶子结点个数告诉我们了：K，度为2的结点个数利用上面提到的结论可知：
,结点总数=k-1+k=2k-1。
答案选A。
第五题：
解析:
很显然要先构造一颗哈夫曼树：
a：00
b：1011
c：01
d：1010
e：11
f ：100
答案选A
第六题：
解析：比根结点大的是右子树，比根结点小的左子树。
其实不用那么麻烦，直接看就行，最左边的最小，最右边的最大。
从左到右依次是：
答案选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的满二叉树有多少个结点的问题了：
答案选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
