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

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

• 1
• 9
• 10
• 11

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

• 4 2 1 7 5 3 6
• 4 2 1 7 5 6 3
• 2 4 1 7 5 3 6
• 2 4 1 5 7 3 6

3. 与十进制数$17.5625$ 对应的8进制数是（ ） {{ select(3) }}

• 21.5625
• 21.44
• 21.73
• 21.731

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

• abcd*+-
• abc+*d-
• abc*+d-
• -+*abcd

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

• 40，50，20，95
• 15，40，60，20
• 15，20，40，45
• 45，40，15，20

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

• 99
• 100
• 101
• 102

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

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

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

• YXZ
• ZXY
• XYZ
• XZY

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

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

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

• $O(n+e)$ ，$O(e)$
• $O(n+e)$ ，$O(n)$
• $O(n^2)$ ， $O(e)$
• $O(n!)$ ， $O(n)$

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

• 2
• 3
• 4
• 5

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

• 3.5
• 37/12
• 47/12
• 1/4

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

• $2 * N$
• $2 * N - 1$
• $2 * N + 1$
• $2 * N + 2$

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

• a, b, c, e, d, f, g
• b, c, a, f, e, g, d
• a, e, c, b, d, f, g
• 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$为（ ） {{ select(15) }}

• {c,e}
• {d,e}
• {e}
• {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. 对于一个输入，字符串中字母的排列顺序不影响输出 {{ select(16) }}

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

选择题

20. 输入8 RWBBBERW，则输出为（ ） {{ select(20) }}

• RRWWBBBE
• RRBBBEWW
• RRWWEBBB
• RREBBBWW

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

• RRWWBBBE
• RRBBBEWW
• RRWWEBBB
• 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个质数 {{ select(22) }}

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

选择题

26. 最终的输出结果为（ ） {{ select(26) }}

• 30031
• 2311
• 510511
• 211

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

• 30047
• 2327
• 510527
• 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. 存在一个输入使得该程序不能终止 {{ select(28) }}

• 正确
• 错误

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

• 正确
• 错误

选择题

30. 如果输入为$8$，函数调用次数为（ ） {{ select(30) }}

• 1
• 2
• 3
• 4

31. 如果输入为$11$，函数调用次数为（ ） {{ select(31) }}

• 9
• 11
• 13
• 15

32. 如果输入为$123$，输出为（ ） {{ select(32) }}

• 44
• 45
• 46
• 47

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

• 4
• 8
• 12
• 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.①处应填（ ） {{ select(34) }}

• a[tmp]
• a[left]
• a[right]
• a[1]

35.②处应填（ ） {{ select(35) }}

• a[j]<value
• a[j]>value
• a[i]<a[j]
• a[i]>a[j]

36.③处应填（ ） {{ select(36) }}

• a[i]<value
• a[i]>value
• a[i]<a[j]
• a[i]>a[j]

37.④处应填（ ） {{ select(37) }}

• left,i,n
• left,i-1,n
• i+1,right,n
• i,right,n

38.⑤处应填（ ） {{ select(38) }}

• left,i,n
• left,i-1,n
• i+1,right,n
• 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.①处应填（ ） {{ select(39) }}

• now<maxnum
• now<=maxnum
• now>=maxnum
• now>maxnum

40.②处应填（ ） {{ select(40) }}

• first-second
• second+first
• second-first
• maxnum-second

41.③处应填（ ） {{ select(41) }}

• ans-1
• ans
• ans+1
• max(first,ans)

42.④处应填（ ） {{ select(42) }}

• hash[first]<ans
• hash[first]>=ans
• delta<ans
• delta>ans

43.⑤处应填（ ） {{ select(43) }}

• work(0)
• work(ans)
• work(n)
• work(n-ans)