（1）设表的长度为n。下列算法中，最坏情况下比较次数小于n的是:◎A)二分查找法◎B)堆排序◎C)快速排序D)顺序查找法[正确答案] A[解析]二分法查找只适用于顺序存储的有序表。二分查找的基本方法是:将被查元素x与线性表的中间项进行比较，若中间项的值等于x，则说明查到;若小于中间项的值则在线性表的前半部分;以相同的方法进行查找;若大于中间项的值，则在线性表的后半部分以相同的方法进行查找。在最坏情况下，二分查找需要比较1og2n次。所以选项A正确。

（2）下列叙述中错误的是:◎A)循环链表是循环队列的存储结构◎B)二叉链表是二叉树的存储结构C)栈是线性结构◎D)循环队列是队列的存储结构[正确答案] A[解析]循环队列属于逻辑结构，其实质还是顺序存储，只是使用指针进行首尾的联结，其实现的存储方式可分为:分散的链表和连续的线性表，与其逻 辑结构实现功能无关。所以选项A正确。

（3）设一棵树的度为4，其中度为4，3, 2，1的结点个数分别为2，3，3，0。则该棵树中的叶子结点数为:◎A)16◎B) 15◎C) 17◎D)不可能有这样的树[正确答案] A .[解析]因为任一棵树中, 结点总数=总分支数目+1，所以: n0+2+3+3+0= (n0*0 + 4*2 + 3*3 + 2*3+1*0) +1。计算得出n0=16。其中，n0表示叶子结点，所以选项A正确。

（4）循环队列的存储空间为Q(1:100)，初始状态为front=rear=100。 经过一系列正 常的入队与退队操作后，front=rear=99， 则循环队列中的元素个数为:◎A) 0或100◎B) 1◎C) 2◎D) 99[正确答案] A[解析]循环队列中，由于入队时尾指针rear向前追赶头指针front;出队时头指针front向前追赶尾指针rear,造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是“空”还是“满”。对于这个题目来说，经过一系列正常的入队与退队操作后，front=rear-99， 此时，要么队列为空(元素个数为0)，要么队列为满(元素个数为100)，因此选项A正确。