●二分查找是查找算法中效率非常高的算法，当用递归算法实现n个不同元素构成的有序序列的二分查找，使用的递归工作栈的最小容量应为(55)。
(55)A.Inn
B.[n/2]
C.[log2n]
D.[log2(n+1)]
答案：(55)D
解析：将该有序序列做成一棵完全的二叉查找树，树的高度即为查找失败时进行递归调用次数最多的情况，
即log2(n+1)的整数部分值。
●函数的渐进时间是考虑当问题规模趋于无穷时，函数岁时间变化的趋势，下述函数中渐进时间最小的是(56)。
(56)A.T1(n)=3nlog2n-100log2n
B.T2(n)=2nlog2n-100log2n
C.T3(n)=n2—100log2n
D.T4(n)=nlog2n+100log2n
答案：(56)D
解析：对函数的渐进时间影响最大的是最高数量级，若相同则必须进一步考虑渐进表达式中的常数因子，通过比较不难得出T4(n)=nlog2n+100log2n渐进时间最小。
●写出每种算法第一趟排序后得到的结果：快速排序(选第一个记录为基准元素)得到(57)，希尔排序(增量为5)得到(58)，堆排序得到(59)，二路归并排序得到(60)，链式基数(基数为10)排序得到(61)：关键字(12，2，16，30，8，28，4，10，20，6，18)，递增排序。
(57)A.10，6，18，8，4，2，12，20，16，30，28
B.6，2，10，4，8，12，28，30，20，16，18
C.2，4，6，8，10，12，16，18，20，28，30
D.6，10，8，28，20，18，2，4，12，30，16
(58)A.2，4，6，8，10，12，16，18，20，28，30
B.6，2，10，4，8，12，28，30，20，16，18
C.12，2，10，20，6，18，4，16，30，8，28
D.30，10，20，12，2，4，16，6，8，28，18
(59)A.30，28，20，12，18，16，4，10，2，6，8
B.20，30，28，12，18，4，16，10，2，8，6
C.2，6，4，10，8，28，16，30，20，12，18
D.2，4，10，6，12，28，16，20，8，30，18
(60)A.2，12，16，8，28，30，4，6，10，18，20
B.2，12，16，30，8，28，4，10，6，20，18
C.12，2，l6，8，28，30，4，6，10，28，18
D.12，2，10，20，6，18，4，16，30，8，28
(61)A.10，6，18，8，4，2，12，20，16，30，28
B.12，2，10，20，6，18，4，16，30，8，28
C.2，4，6，8，10，12，16，18，20，28，30
D.30，10，20，12，2，4，16，6，8，28，18
答案：(57)B(58)C(59)C(60)B(61)D
解析：希尔排序的基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序。序列分割方法：将相隔某个增量h的元素构成一个个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就完成。
堆排序的基本思想：对一组待排序记录，首先把它们按堆的定义排成一个序列(即建立初始小或大堆)，输出顶端最小或者最大元素，然后将剩余的关键字再调整成新堆。便得到次小或者次大的关键字。如此重复进行，直至全部关键字排成有序序列。
二路归并排序的基本思想：将两个有序文件合并成一个新的有序文件。它是把一个有n个记录的无序文件看成是由n个长度为l的有序文件组成的文件，然后进行两两归并。得到(n/2)个长度为2或1的有序文件。再两两归并，如此重复，直至全部有序。
基数排序的基本思想是：首先按最低有效位的值把n个关键宇分配到r个队列中，然后从小到大将各队列中关键字再依次收集起来;接着再按次低有效位的值把刚刚收集起来的关键字分配到r个队列中。重复上述过程，直至最高有效位，这样便得到一个从小到大的有序序列。队列采用链式存储分配时。称为链式基数排序。
●AOE(Activity On Edge)网中的关键路径是指(62)。
(62)A.最长的回路
B.最短的回路
C.从源点到汇点(结束顶点)的最短路径
D.从源点到汇点(结束顶点)的最长路径
答案：(62)D
解析：AOE(Activity On Edge)网是边表示活动的网。它是一个带权的有向无环图，顶点表示事件。弧表示活动，权表示活动持续的时间。通常AOE网用来估算工程完成的时间。完成工程的最短时间是从开始点到完成点的最长路径长度(关键路径)，即路径上各活动持续时间之和。
●以下关键字序列中不符合堆定义的是(63)。
(63)A.(202，187，200，179，182，162，184，142，122，112，168)
B.(202，200，187，184，182，179，168，162，142，122，112)
C.(202，187，142，179，182，162，168，200，184，112，122)
D.(112，122，142，162，168，179，182，l84，187，200，202)
答案：(63)D
解析：堆的定义如下：具有n个元素的序列(h1,h2…，hn)，当且仅当满足(hi>=h2i。hi>=2i+1)或(hi<=h2i，hi<=2i+1)(i=1，2…，n/2)时称之为堆，前者称为最大堆，后者称为最小堆。根据此定义判断。C不是堆。
●一个具有167个结点的完全二叉树，其叶子结点个数为(64)。
(64)A.83
B.84
C.85
D.86
答案：(64)B
解析：完全二叉树中只有度为0和度为2的结点。设为n0和n2，于是总结点数为no+n2。度为2的结点衍生出2个子结点。度为0的结点没有子结点;根结点不是任何点的子结点，所以结点总数还可以表示为2n2+1。于是得到等式nO+n2=2n2+1，推出nO=n2+1。总结点数=2n0-1。本题中。总结点数为167，得nO=84，即叶子结点个数为84。
●若一个森林(非连通无向图)具有n个结点、k条边(n>k)，则该森林中必有(65)棵树。(65)A.k
B.n
C.n-k
D.n+k
答案：(65)C
解析：设该森林共有m棵树，每棵树有ni个结点，根据树的性质可得：
1.n=n1+n2+r13…+nm
2.k=(n1-1)+(n2-1)+(n3-1)……+(nm-1)
上面两式相减得n-k=1+1+1+1……=m。而m是树的个数。
●若G是一个具有28条边的非连通无向图(不含自回路和多重边)，则图G至少有(66)个顶点。
(66)A.11
B.10
C.9
D.8
答案：(66)C
解析：G是一个非连通无向图，则G至少有2个连通分量。顶点数目最少时，即顶点容纳的边最多，则连通分量比是完全图。8个顶点形成的完全图可容纳36条边，再加一个自成一个连通分量的顶点，所以该图至少有9个点。
