23.[2010统考真题]若元素 a,b,c,d,e,f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续3次进行退栈操作，不可能得到的出栈序列是(D)。
A.dcebfa B.cbdaef C.bcaefd D.afedcb
解析：
直接看D选项，a出栈之后就是f出栈，所以要让b,c,d,e,f依次进栈，而这时候需要连续退栈5次才能才能输出b，显然D错。
16.【2010统考真题】某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a,b,c,d,e依次入此队列后再进行出队操作，则不可能得到的出队序列是(D）。
A. b,a,c,d,e B. d,b,a,c,e C. d,b,c,a,e D. e,c,b,a,d
解析：
a第一个进入，a指定是在中间，其他元素接着左右两边往里添就完事了。
A:
接着
b往左进------ba
c往右进------bac
d往右进------bacd
e往右进------bacde, A正确。
B:
b往左进------ba
c往右进------bac
d往左进------dbac
e往右进------dbace, B正确
C:
a，b相连进去的队列，a和b应该挨着的。C不可能形成。
D：
b往左进------ba
c往左进------cba
d往右进------cbad
e往左进------ecbad, D正确
28.[2010 统考真题]下列线索二叉树中(用虚线表示线索),符合后序线索树定义的是(D)。
解析：
先写出这个二叉树的后序序列是：dbca
d没有前驱，d前面应该接个NULL，排除BC,答案在AD当中，再看一下d的后继是b，符合选项的只有D，选D。
18.【2010统考真题】在下图所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树，在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是(C）。
A.13,48 B.24,48 C.24,53 D.24,90
解析：
画出插入关键字48后的新二叉树：
,很显然左子树高度是1，右子树高度是3，高度相差2，这已经不是平衡二叉树了，我们要把它变成新的平衡二叉树，这里有官方做法和非官方两种做法。
非官方做法：
找到关键字中的中间值：37。将37作为根结点，24比37小作为左节点，53比37大作为右节点。13和90还是按照原来的位置放，13放在24的左子树上，90放在53的右子树上，再看48比37大，比53小，放在53的左子树上。
画出来的二叉树如下：
官方做法：
先判断是什么型的不平衡。48是在右子树的左子树上，所以是RL型。
第一步，把它变成RR型。给90施加一个向下的力，进行右旋。
右旋之后变成
，然后把48挂载上去
，再进行左旋再进行左旋
，得到答案C。
7.【2010统考真题】在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是(B）。
A.41 B.82 C.113 D.122
解析：设
是度为0的结点个数，也就是叶子结点。
度为4的结点个数+度为3的结点个数+度为2的结点个数+度为1的结点个数+根结点=所有结点个数。
20+10+1+10+1= 20*4+10*3+1*2+10*1+
算出
直接求解82
11.[2010 统考真题]n(n≥2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是(A)。
A.该树一定是一棵完全二叉树
B.树中一定没有度为 1 的结点
C.树中两个权值最小的结点一定是兄弟结点
D.树中任一非叶结点的权值一定不小于下一层任一结点的权值
解析:
A：哈夫曼树可以是这个样子的：
,但是完全二叉树是从左子树依次往右子树排的，不可能出现只有右子树没有左子树的情况。
因为哈夫曼树是每次找出两个最小的数，往上逐层塔上去的，结点的度要么是0要么是2，不难看出BCD是对的。
15.【2010统考真题】若无向图G=（V,E）中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是(B）。
A.6 B.15 C.16 D.21
解析：
有七个顶点，要想7个顶点都联通，我们只需要使6个顶点完全联通，然后接一条边连上最后一个顶点即可。
例如：要想A,B,C,D,E5个点都联通，只需要让A,B,C,D四个点都完全联通再接一条边与E联通即可。
结合上面的思想，我们来做这道题：
假设有：①②③④⑤⑥⑦这7个顶点。
把顶点⑦这个顶点拿出来放在一边，先算让①-⑥,6个顶点完全联通需要多少条边。顶点①与顶点②-⑥进行连接有5条边，
顶点②与顶点③-⑥进行连接有4条边，因为顶点②和顶点①已经联通了，所以从顶点③开始连接。
顶点③与顶点④-⑥进行连接有3条边。
顶点④与顶点⑤-⑥进行连接有2条边。
顶点⑤与顶点⑥进行连接有1条边。
5+4+3+2+1=
=15，使用多项式求和公式。
15+1=16,选B。
总结：要使n个顶点的无向图，在任何情况下都是联通的，则需要保证n-1个顶点完全联通，再加1条边。
17.【2010统考真题】对下图进行拓扑排序，可得不同拓扑序列的个数是(B）。
A.4 B.3 C.2 D.1
解析：拓扑排序是依次将入度为0的点输出出去，并把这个点相连的边去掉，再进入下一轮。
开始只有a的入度为0，从a开始。
①输出a，去掉与a相连的边。
拓扑序列：a
②这下入度为0的点是e和b了，这里有输出e和输出b两种选择，
假设走输出b这条路线：
拓扑序列：ab
③入度为0的点为e和c，这里同样有两种选择，
以输出c为例:
拓扑序列：abced
以输出e为例：
拓扑序列：abecd
前面提到步骤2有两种选择回到步骤②，假设这时输出的是e:
那很明显，拓扑序列就是aebcd
综上所述，有3种拓扑序列。选B.
18.[2010 统考真题]已知一个长度为 16 的顺序表 L，其元素按关键字有序排列，若采用折半查找法查找一个 L 中不存在的元素，则关键字的比较次数最多是(B)。
A.4 B.5 C.6 D.7
解析：
折半查找：指针low指向最小的元素，指针high指向最大的元素，指针mid指向下标等于[low+high]/2的元素，假如要查找的数是x，如果x比mid指向的数小，则指针high指向mid-1的元素，指针low不变。如果x比指针mid所指向的数大，则指针low指向mid+1的元素，指针high不变重新设置mid的指向，接着下一轮。。。
本题：题目要比较的次数最多就要一直查找一直折半，直到最后折半不了为止。
第一次比较：
mid = [0+15]/2 = 7,
7左边的数是7个，7右边的数是8个，要想比较次数最多，肯定走数多的一边，因为数越多折半能折半的次数越多，能比较的数也就越多。
第二次比较：
mid=[8+15]/2 = 11,
11左边的数（8-10）是3个，11右边的数（12-15）是4个，接走走右边。
第三次比较：
mid=[12+15]/2 = 13,
13左边的数（12）是1个，13右边的数（14-15）是2个，接走走右边。
第四次比较：
mid=[14+15]/2 = 14,
注意此时指针low也是14，还能再比较一次，接着走右边。
第五次比较：
low = high = 15 ;
mid =15,
那这是最后一个数了，比较失败。
一共5次。
其实我们可以用一种更直观的方式来看这个题：折半查找二叉树。
由题可知，这个树的结点的个数应该是16个。
假设这个树的高度是h，那它的h-1层一定是满的，h层可能满也可能不满。
根据这个结论，我们可以推出折半查找判定树的树高
，树高为5，第4层是满的。
，前四层的结点个数是：
个，所以插入最后一个。
这样来看树高是5，则最多比较5次，如图来看，从上到下一共可比较5次。
答案选B。
14.[2010 统考真题]采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是()。
A.递归次数与初始数据的排列次序无关
B.每次划分后，先处理较长的分区可以减少递归次数
C.每次划分后，先处理较短的分区可以减少递归次数
D.递归次数与每次划分后得到的分区的处理顺序无关
解析：
快速排序：任取一元素作为枢轴划分成两部分，左<=枢轴，右>=枢轴然后递归处理左右，直到空或只剩一个。
例如：
A.对于快速排序，当序列是一个有序序列的时候时间复杂度最高，同时递归次数也最多。
例：下图这个序列，每次递归只确定一个数的位置。递归次数只跟树高有关。
有序：
无序：
如图所示，无序时的树高比有序的树高矮，而树高和递归次数有关，所以递归次数和初始数据的排列次序无关是错误的。A错。
B.C.D：递归次数只跟树高有关，不管是先处理较长的分区，还是较短的分区，树高都是不边的。那么递归次数也不变,与划分分区的处理顺序无关。选D。
13.【2010统考真题】对一组数据（2,12,16,88,5,10）进行排序，若前3趟排序结果如下：
第一趟排序结果：2,12,16,5,10,88.
第二趟排序结果：2,12,5,10,16,88.
第三趟排序结果：2,5,10,12,16,88.
使用了什么排序(A)。
A.冒泡排序 B.希尔排序 C.归并排序 D.基数排序
解析：
A:记住冒泡排序的特点：每趟排序过后，数列中最小或者最大的数都会出现在序列的最左边或者最右边。
我们来看第一趟排序：88移到了最右边。
第二趟排序：16移到了最右边。
第三趟排序：12移到了最右边。
经过三趟排序，队列中最大的三个数都有序出现在了序列的最右边，显然符合冒泡排序的特点。A对。
B：顺序表长度为n，d1=n/2=3,2和88是一组的，并且有序不需要变动。显然不是希尔排序，B错。
C：归并排序是把两个或多个有序的序列合并成一个。C显然不对
D：显然不对。
