15年408-数据结构
第一题
解析：
栈第一次应该存main的信息。
然后进入到main里面，要输出S(1)，将S(1)存入栈内，
进入到S(1)中，1>0,所以还要调用S(0)
S(0)进入栈中，此时栈内从下至上依次是main(),S(1),S(0)
答案选A
第二题：
解析：
先序序列个数为0时，二叉树个数是1：
先序序列个数为1时，二叉树个数是1：
先序序列个数为2时，二叉树个数是2：
先序序列个数为3时，二叉树个数是5：
先序序列个数为4时，二叉树个数是5+2+2+5=14：
第三题：
解析：
A：A错
B：B错
C：C错
答案选D
第四题：
解析：
该题给的是一棵平衡二叉树，平衡二叉树的定义是：根节点的左右两个子树的高度之差不大于1，当插入一个元素之后，可能会使平衡二叉树失衡，这时候需要判断失衡的类型，有RR，RL，LL，LR四种类型，为了使二叉树重新保存平衡，在经过左旋，右旋等操作后，插入的叶子结点可能到了根节点的位置。例如：
，C错，
题目说对其进行中序遍历之后能得到一个降序序列，中序遍历是左根右，也就是说该二叉树最大的结点一定是位于最左边的叶子结点，该结点没有左子树，D对
当二叉树的结点个数是2个时，根节点的度是1，A错。
第五题：
解析：
直接画图，就能看出答案了，答案是5个，选D
第六题：
解析：
卡鲁斯卡尔算法（选边）：选权值最小的边：权值为5
第一次选：（v1,v4）
第二次选：权值为8的点，(v1,v3),(v3,v4),(v2,v3)
普利姆算法（选点）：第一次选：v1,v4这两个点。
第二次的选择：选择与v1，v4这两个点相连的点，并且这条边权值要最小，由观察可得，权值最小的是8；也就是(v1,v3)和(v3,v4)这两条边。
（v2，v3）不是普利姆算法第二次选择的边，答案选（v2，v3）
第七题:
解析：
使用折半查找二叉树可以很直观的看待这个问题：
A：180出现在了200的右子树中，显然错误。
第八题：
解析：
abaaba
abaabc
第六个字符出现匹配失败，i=j=5，说明字符串下标是从0开始的。
因为是最后一个字符c和a匹配失败的，前面都能匹配的上，也就是说前面都是确定的字符，只有最后一个字符是匹配不上的，是未知的，ab是确认的，且模式串开头也是ab，因此下一轮匹配我们直接可以从ab开始后比较第三个元素，此时j在T[2],i在S[5],这个用文字不太好描述，王道课直接用这个题讲的课，可以看一下王道的KMP课。
答案选C
第九题：
解析：
A.直接插入排序：每次将待排序的记录中一个元素，按其关键字的大小插入到前面已经排好序的序列中，直到所有记录插入完毕。以1，2，3，4，5为例，进行升序排序，
因为本来就是有序的，所以不需要将元素进行任何交换。
而如果元素的序列是5，4，3，2，1，进行升序排序时，则每插入一个元素都要与前面的元素进行交换位置。显然A错
B：起泡排序也叫冒泡排序，是将一个序列，从左到右或者从右到左，两两进行比较，如果是逆序，则交换位置，直到序列比较完成。
还是以1，2，3，4，5为例，不需要移动元素，而5，4，3，2，1需要移动元素。B错
C：基数排序：是按照个位，十位，百位，依次排的，和次序无关。C对
D：快速排序很经典的问题，时间复杂度最差的情况是有序序列：
时间复杂度最好的情况是：
显然有序的时候不用交换次序，无序的时候要进行多次比较，然后需要交换元素次序。
第十题：
解析：
先将这个小根堆构建出来：
删除8后，将最后一个元素12放上去根的位置，接着下火海。
小根堆是根比左右两个子树要小，所以先从左右两个子树当中找出最小的一个，15和10进行比较，得出10比较小，然后10在和12比较一次，得出10最小，10和12交换位置。
接着要保证，12小于左右两个子树，因此12要和16进行一次比较，12比16小，不用交换位置，得到新的小根堆，题目完成。
一共要进行3次比较。
第十一题：
解析：
组内就两个元素在比较，使用直接插入排序就好了，不用那么复杂，答案选A。
