一、 单项选择题（共 15 题，每题 2 分，共计 30 分。每题有且仅有一个正确选项。）

1. 一棵二叉树一共有19个节点，其叶子节点不可能有（ ）个

A. 1 B. 9 C. 10 D. 11

2. 二叉树$T$，已知其前序遍历是1 2 4 3 5 7 6（数字为结点的编号，以下同），后序遍历是4 2 7 5 6 3 1，则该二叉树的中序遍历不可能是（ ）

A. 4 2 1 7 5 3 6 B. 4 2 1 7 5 6 3 C. 2 4 1 7 5 3 6 D. 2 4 1 5 7 3 6

3. 与十进制数$17.5625$ 对应的8进制数是（ ）

A. 21.5625 B. 21.44 C. 21.73 D. 21.731

4. 表达式$a*(b+c)-d$的后缀表达式是（ ）

A. abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd

5. 设一组初始记录关键字序列为$(50，40，95，20，15，70，60，45)$，则以增量$d=4$的一趟希尔排序结束后前4条记录关键字为（ ）

A. 40，50，20，95 B. 15，40，60，20 C. 15，20，40，45 D. 45，40，15，20

6. 设某哈夫曼树中有$199$个结点，则该哈夫曼树中有（ ）个叶子结点

A. 99 B. 100 C. 101 D. 102

7. 十进制下的无限循环小数（不包括循环节内的数字均为$0$或均为$9$的平凡情况），在二进制下有可能是（ ）。

A. 无限循环小数(不包括循环节内的数字均为0或均为9的平凡情况） B. 无限不循环小数 C. 有限小数 D. 整数

8. 设$X、Y、Z$分别代表三进制下的一位数字，若等式$XY + ZX = XYX$在三进制下成立，那么同样在三进制下，等式$XY * ZX = （ ）$也成立 。

A. YXZ B. ZXY C. XYZ D. XZY

9. 通过分治算法解决输入大小为 N 的问题，以下方法中，（ ）的效率是最差的。

A. 分成2个规模为N/3的子问题，并且完成其中的一个步骤需要$O(N)$的时间 B. 分成2个规模为N/3的子问题，并且完成其中的一个步骤需要$O(NlogN)$的时间 C. 分成3个规模为N/2的子问题，并且完成其中的一个步骤需要$O(N)$的时间 D. 分成3个规模为N/3的子问题，并且完成其中的一个步骤需要$O(NlogN)$的时间

10. 使用邻接表存储图，借助队列优化后，宽度优先搜索的时间复杂度和辅助空间复杂度为（）

A. $O(n+e)$ ，$O(e)$ B. $O(n+e)$ ，$O(n)$ C. $O(n^2)$ ， $O(e)$ D. $O(n!)$ ， $O(n)$

11. 一棵二叉树的前序遍历序列是$ABCDEFG$，后序遍历序列是$CBFEGDA$，则根结点的左子树的结点个数可能是（ ）

A. 2 B. 3 C. 4 D. 5

12. 现有一只青蛙，初始时在 $n$ 号荷叶上。当它某一时刻在 $k$ 号荷叶上时，下一时刻将等概率地随机跳到 $1, 2, …, k$ 号荷叶之一上，直至跳到 $1$ 号荷叶为止。当 $n = 2$ 时，平均一共 跳 $2$次；当 $n = 3$ 时，平均一共跳 $2.5$ 次。则当 $n = 5$ 时，平均一共跳（ ）次

A. 3.5 B. 37/12 C. 47/12 D. 1/4

13. 完全二叉树的结点个数为$4 * N + 3$，则它的叶结点个数为（ ）

A. $2 * N$ B. $2 * N - 1$ C. $2 * N + 1$ D. $2 * N + 2$

14. 设栈S的初始状态为空，元素$a, b, c, d, e, f, g$依次入栈，以下出栈序列不可能出现的有（ ）

A. a, b, c, e, d, f, g B. b, c, a, f, e, g, d C. a, e, c, b, d, f, g D. d, c, f, e, b, a, g

15. 设全集$I={a,b,c,d,e,f,g,h}$，集合$A={a,b,c,d,e,f}$，$B={c,d,e}$，$C={a,d}$，那么集合$A∩B∩ \sim C$为（ ）

A. {c,e} B. {d,e} C. {e} D. {c,d,e}

二、 阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 T，错误填F；除特殊说明外，判断题1.5分，选择题3分，共计40分）

1）

1.	#include<iostream>  
2.	#include<cstring>  
3.	using namespace std;  
4.	int main(){  
5.	    int i,n,jr,jw,jb;  
6.	    char ch1;  
7.	    char ch[22];  
8.	    scanf("%d",&n);  
9.	    scanf("%s",ch);  
10.	    jr=0;  
11.	    jw=n-1;  
12.	    jb=n-1;  
13.	    while(jr<=jw){  
14.	        if(ch[jw]=='R'){  
15.	            ch1=ch[jr];  
16.	            ch[jr]=ch[jw];  
17.	            ch[jw]=ch1;  
18.	            jr++;  
19.	        }else if(ch[jw]=='W'){  
20.	            jw--;  
21.	        }else{  
22.	            ch1=ch[jw];  
23.	            ch[jw]=ch[jb];  
24.	            ch[jb]=ch1;  
25.	            jw--;  
26.	            jb--;  
27.	        }  
28.	    }  
29.	    printf("%s\n",ch);  
30.	    return 0;  
31.	}  

判断题

16. 对于一个输入，字符串中字母的排列顺序不影响输出

A. 正确 B. 错误

17. 如果输入字符只有RWB三种，则最终输出的结果所有的R一定在最左边

A. 正确 B. 错误

18. 将13行的jw换成jb，与原输出结果区别在于是W和B的位置交换了

A. 正确 B. 错误

19. 如果输入不止RWB三种字符，则在结果中其他字符一定在最后

A. 正确 B. 错误

选择题

20. 输入8 RWBBBERW，则输出为（ ）

A. RRWWBBBE B. RRBBBEWW C. RRWWEBBB D. RREBBBWW

21. (本题4分) 将 while 循环中所有的 jw 换成 jb，jb 换成 jw，则20题的输出为（ ）

A. RRWWBBBE B. RRBBBEWW C. RRWWEBBB D. RREBBBWW

2）

1.	#include<iostream>  
2.	#include<cstring>  
3.	using namespace std;  
4.	int main(){  
5.	    int i,j,s,sp1;  
6.	    int p;  
7.	    int a[11];  
8.	    sp1=1;  
9.	    a[1]=2;  
10.	    j=2;  
11.	    while(sp1<10){  
12.	        j++;  
13.	        p=1;  
14.	        for(i=2;i<=j-1;i++)  
15.	            if(j%i==0)  
16.	                p=0;  
17.	        if(p){   
18.	            sp1++;  
19.	            a[sp1]=j;  
20.	        }  
21.	    }  
22.	    j=2;  
23.	    p=1;  
24.	    while(p){  
25.	        s=1;  
26.	        for(i=1;i<=j;i++)  
27.	            s*=a[i];  
28.	        s++;  
29.	        for(i=2;i<=s-1;i++)  
30.	            if(s%i==0)  
31.	                p=0;  
32.	        j++;  
33.	    }  
34.	    cout<<s<<endl;  
35.	    return 0;  
36.	}  

判断题

22. a数组中保存着前10个质数

A. 正确 B. 错误

23. 将14行的 i<=j-1 修改成 i<j-1 ，答案不会发生改变

A. 正确 B. 错误

24. 该程序24行的 while(p) 语句会执行六次

A. 正确 B. 错误

25. 将26行的 i<=j 修改成 i<j ，答案会发生改变

A. 正确 B. 错误

选择题

26. 最终的输出结果为（ ）

A. 30031 B. 2311 C. 510511 D. 211

27. 如果将 s++ 改为 s+=17 ，则最终输出结果为（ ）

A. 30047 B. 2327 C. 510527 D. 227

3）

1.	#include<iostream>  
2.	using namespace std;  
3.	int n;  
4.	int count(int n)  
5.	{  
6.	    if (n==1) return 0;  
7.	    else if (n%2==0)  
8.	        return count(n/2)+1;  
9.	    else  
10.	        return count(n*3+1)+1;  
11.	}  
12.	int main()  
13.	{  
14.	    cin>>n;  
15.	    cout<<count(n);  
16.	    return 0;  
17.	}  

判断题

28. 存在一个输入使得该程序不能终止

A. 正确 B. 错误

29. 对于所有的$i，j$如果有$i * 3 < j$，那么 count(i) 的递归次数一定比 count(j) 的递归次数要少

A. 正确 B. 错误

选择题

30. 如果输入为$8$，函数调用次数为（ ）

A. 1 B. 2 C. 3 D. 4

31. 如果输入为$11$，函数调用次数为（ ）

A. 9 B. 11 C. 13 D. 15

32. 如果输入为$123$，输出为（ ）

A. 44 B. 45 C. 46 D. 47

33. 如果将第7行改为 n%2==1 ，输入为14，输出为（ ）

A. 4 B. 8 C. 12 D. 16

三、完善程序（单选题，每小题3分，共计30分）

1）给定一个长度为$1,000,000$的无序正整数序列，以及另一个数$n(1<=n<=1000000)$，接下来以类似快速排序的方法找到序列中第$n$大的数（关于第$n$大的数：例如序列${1，2，3，4，5，6}$中第$3$大的数是$4$）。

1.	#include <stdlib.h>  
2.	#include <stdio.h>  
3.	  
4.	int a[1000001],n,ans = -1;  
5.	  
6.	void swap(int *a,int *b) {  
7.	    int c;  
8.	    c = *a;  
9.	    *a = *b;  
10.	    *b = c;  
11.	}  
12.	int FindKth(int left, int right, int n) {  
13.	    int tmp,value,i,j;  
14.	    if (left == right) return left;  
15.	    tmp = rand()% (right - left) + left;  
16.	    swap( &a[tmp], &a[left] );  
17.	    value = ① ; 
18.	    i = left;  
19.	    j = right;  
20.	    while (i < j) {  
21.	  
22.	        while (i < j && ② ) j --;  
23.	        if (i < j) {  
24.	            a[i] = a[j];  
25.	            i ++;  
26.	        } else break;  
27.	        while (i < j &&  ③ ) i ++;  
28.	        if (i < j) {  
29.	            a[j] = a[i];  
30.	            j - -;  
31.	        } else break;  
32.	    }  
33.	    a[i] = value;  
34.	    if (i < n) return  FindKth(  ④  );  
35.	    if (i > n) return FindKth(  ⑤  );  
36.	    return i;  
37.	}  
38.	  
39.	int main() {  
40.	    int i;  
41.	    int m = 1000000;  
42.	    for (i = 1; i <= m; i ++) scanf("%d", &a[i]);  
43.	    scanf("%d", &n);  
44.	    ans = FindKth(1,m,n);  
45.	    printf("%d\n", a[ans]);  
46.	    return 0;  
47.	}  

34.①处应填（ ）

A. a[tmp] B. a[left] C. a[right] D. a[1]

35.②处应填（ ）

A. a[j]<value B. a[j]>value C. a[i]<a[j] D. a[i]>a[j]

36.③处应填（ ）

A. a[i]<value B. a[i]>value C. a[i]<a[j] D. a[i]>a[j]

37.④处应填（ ）

A. left,i,n B. left,i-1,n C. i+1,right,n D. i,right,n

38.⑤处应填（ ）

A. left,i,n B. left,i-1,n C. i+1,right,n D. i,right,n

2. 有一些长度相等的等差数列（数列中每个数都为 $0 \sim 59$ 的整数）， 设长度均为$L$，将等差数列中的所有数打乱顺序放在一起。现在给你这些打乱后的数，问原先，$L$最大可能为多大？先读入一个数$n（1<=n<=60）$，再读入$n$个数，代表打乱后的数。输出等差数列最大可能长度$L$。

1.	#include <stdio.h>  
2.	int hash[60];  
3.	int n, x, ans, maxnum;  
4.	  
5.	int work(int now) {  
6.	    int first, second, delta, i;  
7.	    int ok;  
8.	    while (  ①  && !hash[now])  
9.	        ++now;  
10.	    if (now > maxnum)  
11.	        return 1;  
12.	    first = now;  
13.	    for (second = first; second <= maxnum; second++)  
14.	        if (hash[second]) {  
15.	            delta =  ②;  
16.	            if (first + delta * ③ > maxnum) break;  
17.	            if (delta == 0)  
18.	                ok = ( ④  );  
19.	            else {  
20.	                ok = 1;  
21.	                for (i = 0; i < ans; i++)  
22.	                    ok =  ok  && (hash[first+delta*i]);  
23.	            }  
24.	            if (ok) {  
25.	                for (i = 0; i < ans; i++)  
26.	                    hash[first+delta*i]--;  
27.	                if (work(first))  
28.	                    return 1;  
29.	                for (i = 0; i < ans; i++)  
30.	                    hash[first+delta*i]++;  
31.	            }  
32.	        }  
33.	    return 0;  
34.	}  
35.	  
36.	int main() {  
37.	  
38.	    int i;  
39.	  
40.	    memset(hash, 0, sizeof(hash));  
41.	    scanf("%d", &n);  
42.	    maxnum = 0;  
43.	    for (i = 0; i < n; i++) {  
44.	        scanf("%d", &x);  
45.	        hash[x]++;  
46.	        if (x > maxnum)  
47.	            maxnum = x;  
48.	    }  
49.	    for (ans = n; ans >= 1; ans--)  
50.	        if ( n%ans==0 && ⑤) {  
51.	            printf("%d\n", ans);  
52.	            break;  
53.	        }  
54.	    return 0;  
55.	}  

39.①处应填（ ）

A. now<maxnum B. now<=maxnum C. now>=maxnum D. now>maxnum

40.②处应填（ ）

A. first-second B. second+first C. second-first D. maxnum-second

41.③处应填（ ）

A. ans-1 B. ans C. ans+1 D. max(first,ans)

42.④处应填（ ）

A. hash[first]<ans B. hash[first]>=ans C. delta<ans D. delta>ans

43.⑤处应填（ ）

A. work(0) B. work(ans) C. work(n) D. work(n-ans)