14年数据结构
第一题
解析：
求时间复杂度就是看程序执行了多少次。
假设最外层执行了k次，我们看终止条件是k=n，则：
有
,
内层是一个j=1到j=n的循环，显然执行了n次。
总的时间复杂度是内层×外层=
答案选C。
第二题
解析：
一步一步来分析栈内元素的变化：
输出a
/存入栈中
此时栈：/
此时轮到+，+相对比/不够强，所以+不能直接进，需要先将/输出，然后+再进入。
此时栈：+
+存入栈中
然后是‘(’，‘(’够强，直接进入。
(存入栈中
此时栈：+ (
接着是c，c直接输出，然后是*,*够强直接存入栈中，d直接输出。
c输出
此时栈：+ ( *
然后是-号，-号不够强，需要*先输出，-再进入。
*输出
此时栈：+ ( -
然后是e，e直接输出，*够强存入栈中，f输出。
e输出
此时栈：+ ( - *
然后是)，)有着和(配对的特点，需要将()一起输出出来。
( - * )输出
此时栈：+
最后是/g，/够强直接存入栈中，g直接输出。
/存入栈
此时栈：+ /
题目问扫描到f时，栈的情况，直接看f。
答案选B
第三题
解析：
end1指向A[0]，end2指向队尾元素的后一个位置，如果end2指向A[1]，那就说明表内还有一个元素，肯定不对。
首先，队列为空时，对头指针和队尾指针中间肯定没有位置，也就是说这两个指针都指向同一个位置，end1=end2，直接排除C和D
这种题，画个图就很好解决了：
数组的大小不难看出是M个，但是题目说队列最多能容纳M-1个元素，那就代表队列种最后一个元素的序号是M-2,end2指向最后一个元素的后一个位置，end2=M-1，如图可知，（end2+1）mod M=end1
第四题
解析：
直接写出图示二叉树的中序遍历序列：左根右
d e b x a c
很显然x的左右是ba很显然选D
第五题
解析：
对付这种题直接画一个特殊的树就好了：树转二叉树：兄弟变成右子树，孩子变成左子树。
叶子结点没有孩子，我们说树转二叉树的过程中，孩子会变成左子树，左孩子指针为空也就是没有左字数，也就代表该结点没有孩子，没有孩子的结点就是叶子结点。
答案选C
第六题
解析：
对于一个前缀编码有一个特点叫前缀不是前缀：对于一个前缀编码里面的任何一个元素都不是其它元素的前缀。
我们看D选项：
110是1110的前缀，D错
答案选D。
第七题：
解析：一个一个分析选项；拓扑序列是每次找入度为0的结点，并删除与之相连的线。
A：24显然不对，2的入度不是0，56显然不对，5的入度不是0 A错
B：和A一样的问题：24
C：和A一样的问题：56
答案选D
第八题：
解析：
存储效率和装填因子反应的是，顺序表中已经存储或者说装填的元素个数/总个数，和堆不堆积没关系。A和C错。直接影响的应该是查找效率，在不堆积的情况下，查找效率高，通常能一次直接命中，如果发生了堆积，查找到当前位置发现不是该元素后，可能还要依次向后查找，以线性探测法为例。大大增大了查找长度。
答案选D
第九题
解析：
回顾一下B树的性质：
对于n阶B树的根节点，关键字的个数是[1,n-1]
对与n阶B树的非根结点，关键字的个数是【[n/2]向上取整-1，n-1】
回到这题：
题目要含关键字的结点个数最多，因为关键字的个数是有限的是15个，则要使每个结点的关键字最少。
我们可以算出，根节点最少是1个关键字，非根结点最少是4/2-1=1个关键字。
B树是一个完全二叉树。
因此直接画图：
正好是15个结点
选D。
第十题：
解析：
回顾一下希尔排序：设置一个间隔d，依次对i，i+d这两个元素进行排序。
也就是说经过一趟排序之后，间隔为d的两个元素，一定是有序的。
A.d=2,9-1是减序，1-13是升序，显然错。
B.d=3,B对
答案选B
第十一题：
解析：
快速排序每次都能确定一个元素的最终位置，且这个元素的左边都小于这个元素，这个元素的右边都大于这个元素。
经过两趟排序，至少能确定两个元素的最终位置。
我们直接写出排好序的最后的顺序是：2，3，4，5，6，7，9
A.23679的位置对了
B.29的位置对了
C.就一个9的位置是对的，我们说至少能确定两个元素的位置，C错
D.59的位置是对的。
