1.一个从大到小的数组，按从小到大的顺序排序，哪种排序方法最快？（最坏情况）
（1）冒泡排序：1+2+...n-1=O(n^2);
（2）快速排序：每次partion都需要比较k-1次，才能将“第一个”数字移动到“末端”。需要进行n-1次partion才能完成排序。所以最坏情况下比较次数仍然是1+2+..+n-1=O(n^2)；
（3）插入排序：2+3+...+n=O(n^2)；
（4）堆排序：O(nlogn)。
补充：平均情况下，这几种排序算法的比较：
（1）快速排序：平均时间复杂度为O(nlogn)；最坏时间复杂度O(N^2)；快速排序需要一个栈作辅助空间，用来实现递归处理左、右子文件，在最坏情况下,递归深度为n，所需栈的空间大小为O(n)数量级；不稳定的排序方法。
（2）冒泡排序：最坏时间复杂度O(N^2)；最好时间复杂度为n-1;少量辅助空间O(1)；稳定的排序方法。
（3）插入排序：平均复杂度为O(N^2)；最坏情况=(n-1)(n+2)/2 (次)；少量中间变量，为常量级O(1)；稳定的排序方法。
（4）堆排序：平均复杂度及最坏情况的复杂度都是O(nlogn)；适用于大数据量的排序。
2.关于循环队列说法正确的是：D
A.循环队列不是线性结构；
B.仅用头指针就可以描述循环序列中元素的变化过程；
C.仅用尾指针就可以描述循环序列中元素的变化过程；
D.循环队列中元素的个数是有队头指针和队尾指针共同决定。
解析：队列长度=(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
Q.rear=Q.front时可能为空队列，也可能为满队列；解决办法：少用一个元素空间，以队列头指针在队列尾指针的下一位置（环状的下一位置）上作为满状态标志。
3.设一棵二叉树中有3个叶子节点，有8个度为1的节点，则该二叉树中总的节点数为？ 3+2+8=13
解析：度为1的结点数8+度为0的结点数2+度为2的结点数（3-1）=13；
4.在一个元素个数为N的数组里，找到升序排在N/5位置的元素的最优算法时间复杂度是 O(n)
解析：找到一个长度为n的数组中第k大的数的最优化时间复杂度为O(n)。
将长度为k的数组进行partition，要比较的次数为k。在长度为n的数组中查找第k大的数字，最坏情况下要进行n-k次partition，复杂度为n+n-1+n-2+...+n-k=kn+k(k+1)/2=O(n)。