一、单项选择题：1~40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是符合题目要求的。
1. 下列程常段的时间复杂度是
count=0;
for(k=1;k<=n;k*=2)
for(j=1;j<=n;j+1)
count++;
A.O(log2n) B.O(n) C.O(nlog2n) D.O(n2)
2. 假设栈初始为空，将中缀表达式 转换为等价后缀表达式的过程中，当扫描到f时，栈中的元素依次是
A. B. C. D. 3. 循环两列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空，下列判断队空和队满的条件中，正确的是
A.队空：end1==end2; 队满：end1==(end2+1)modM
B.队空：end1==end2; 队满：end2==(end1+1)mod(M-1)
C.队空：end2==(end1+1)modM ; 队满：end1==(end2+1)modM
D.队空：end1==(end2+1)modM; 队满：end2==(end1+1)mod(M-1)
4. 若对如下的二叉树进行中序线索化，则结点x的左、右线索指向的结点分别是
5. 将森林F转换为对应的二叉树T，F中叶结点的个数等于
A.T中叶结点的个数 B.T中度为1的结点个数
C.T中左孩子指针为空的结点个数 D.T中右孩子指针为空的结点个数
6. 5个字符有如下4种编码方案，不是前缀编码的是
A.01,0000,0001,001,1 B.011,000,001,010,1
C.000,001,010,011,100 D.000,001,010,011,100
7. 对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是
A.3,1,2,4,5,6 B.3,1,2,4,6,5
C.3,1,4,2,5,6 D.3,1,4,2,6,5
8. 用哈希(散列)方法处理冲突(碰撞)时可能出现堆积(聚集)现象，下列选项中，会受堆积现象直接影响的是
A.存储效率 B.数列函数
C.装填(装载)因子 D.平均查找长度
9.在一棵具有15个关键字的4阶B树中，含关键字的结点数最多是
A.5 B.6 C.10 D.15
10. 用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9,1,4,13,7,8,20,23,15，则该趟排序采用的增量(间隔)可能是
A.2 B.3 C.4 D.5
11. 下列选项中，不可能是快速排序第2趟排序结果的是
A.2,3,5,4,6,7,9 B.2,7,5,6,4,3,9
C.3,2,5,4,7,6,9 D.4,2,3,5,7,6,9
