第二套

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

1. 已知十进制中的 $18$ 在 $X$ 进制中的表示为 $24$，则 $18_{10}=24_x$，则这个 $X$ 进制为进制。 {{ select(1) }}

• 6
• 7
• 8
• 9

2. 根据网址的域名：http://www.jiangsu.gov.cn/，可以判断出该网站是什么类型的网站。 {{ select(2) }}

• 商业
• 军事
• 组织机构
• 政府部门

3. 与计算机硬件关系最密切的软件是。 {{ select(3) }}

• 编译程序
• 数据库管理程序
• 游戏程序
• 操作系统

4. 下列程序执行后 $s$ 的值为。

int i=1,s=0;
	while(i++){
		if(!(i%3))break;
		else s+=1;
}

{{ select(4) }}

• $2$
• $3$
• $4$
• 以上都不是

5. 将 $19$ 分解成 $3$ 个不重复数字（$1\sim 9$）之和（不计顺序）的方法有几种？{{ select(5) }}

• $3$
• $4$
• $5$
• $6$

6. 甲、乙、丙三位同学选修课程，在四门课程中，甲选修两门，乙、丙各选修三门，则不同的选修方案有几种？{{ select(6) }}

• $36$
• $48$
• $96$
• $192$

7. 已知某二叉树的选序遍历序列是 ABDCE，中序遍历序列是BDAEC，则该二叉树的后续遍历为？{{ select(7) }}

• BDECA
• DBCEA
• DBECA
• BDCEA

8. 计算机启动时，可以通过存储在{{ select(8) }}中的引导程序引导操作系统。

• RAM
• ROM
• Cache
• CPU

9. 表达式 a+b*c-(d+e) 的前缀形式是。{{ select(9) }}

• -+a*bc+de
• -+*abc+de
• abc*+de+-
• abcde*++-

10. 小军在家玩开关灯游戏，小军家的灯有三种颜色，分别是白、黄、红。按 $1$ 下白灯亮，按 $2$ 下灯灭，按 $3$ 下黄灯亮，按 $4$ 下灯灭，按 $5$ 下红灯亮，按 $6$ 下灯灭，再按又是白灯亮，依次循环。当按到 $49$ 次和 $100$ 次的灯的状态是。{{ select(10) }}

• 灯灭，灯灭
• 白灯亮，灯灭
• 白灯亮，红灯亮
• 红灯亮，灯灭

11. $704$ 与 $2048$ 的最小公倍数是。{{ select(11) }}

• $45056$
• $90112$
• $180224$
• $22528$

12. 在{{ select(12) }}的情况下，函数 $A \lor B$ 运算的结果是 False。

• A 和 B 全部是 False
• A 和 B 任一是 False
• A 和 B 任一是 True
• A 和 B 全部是 True

13. 小明夫妇请了小刚夫妇和小伟夫妇来他们家玩扑克。这种扑克游戏有一种规则，夫妇两人不能一组，小明和小红一组，小刚的队友是小伟的妻子，琳达的丈夫和小丽一组。那么这三对夫妇分别为。 {{ select(13) }}

• 小明-小丽、小刚-琳达、小伟-小红
• 小明-小丽、小刚-小红、小伟-琳达
• 小明-琳达、小刚-小红、小伟-小丽
• 小明-小红、小刚-小丽、小伟-琳达

14. $4$ 人过桥，每人单独过桥分别需要用时 $1$ 分、$2$ 分、$5$ 分、$10$ 分，过桥需要灯（只有一盏），一次只能 $2$ 人一起过（意味着需要有人送灯回来），过桥时间以用时最多的人为准，则 $4$ 人全部过桥时间最少需要 {{ select(14) }}分。

• $15$
• $17$
• $19$
• $21$

15. $2000$ 年，华人学者姚期智因为在计算理论（包括伪随机数生成，密码学与通信复杂度）方面的突出成就而荣获 {{ select(15) }}。

• 奥斯卡奖
• 图灵奖
• 诺贝尔奖
• 普利策奖

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

1	#include <iostream>
2	using namespace std;
3	int main()
4	{
5		const int SIZE=10;
6		int height[SIZE],num[SIZE],n,ans;
7		cin>>n;
8		for(int i=0;i<n;i++){
9			cin>>height[i];
10			num[i] = 1;
11			for(int j=0;j<i;j++){
12				if((height[j]<height[i]) && (num[j]>=num[i]))
13					num[i] = num[j]+1;
14			}
15		}
16		ans = 0;
17		for(int i=0;i<n;i++){
18			if(num[i]>ans)ans = num[i];
19		}
20		cout<<ans<<endl;
21		return 0;
22	}

判断题

16. 如果 height 数组中的输入有负数，则程序会出错。{{ select(16) }}

• √
• ×

17. 程序输出的 ans 小于或等于 $n$。{{ select(17) }}

• √
• ×

18. 将 $12$ 行 num[j] >= num[i] 改为 num[j] > num[i]，程序的输出结果不会改变{{ select(18) }}

• √
• ×

19. 将 $18$ 行 num[i] > ans 改为 num[i] >= ans，程序的输出结果不会改变。{{ select(19) }}

• √
• ×

选择题

20. 若输入的数据为

10
1 1 1 1 1 1 1 1 1 1

则程序的输出结果是 {{ select(20) }}。

• $1$
• $2$
• $3$
• $4$

21. 若输入的数据为

10
3 2 5 11 12 7 4 10 15 6

则程序的输出结果是 {{ select(21) }}。

• $2$
• $3$
• $4$
• $5$

1	#include <iostream>
2	using namespace std;
3	int n,m,i,j,p,k;
4	int a[100],b[100];
5	int main()
6	{
7		cin>>n>>m;
8		a[0]=n;i=0;p=0;k=1;
9		do{
10			for(int j=0;j<i;j++)
11				if(a[i]==a[j])
12				{
13					p=1;k=j;break;
14				}
15			if(p)break;
16			b[i]=a[i]/m;
17			a[i+1]=a[i]/m;
18			a[i+1]=a[i]%m*10;
19			i++;
20		}while(a[i]!=0);
21		cout<<b[0]<<".";
22		for(j=1;j<k;j++)cout<<b[j];
23		if(p)cout<<"(";
24		for(j=k;j<i;j++)cout<<b[j];
25		if(p)cout<<")";
26		cout<<endl;
27		return 0;
28	}

判断题

22. 程序输入的 $n$ 和 $m$ 不能相等。{{ select(22) }}

• √
• ×

23. 程序输入的 $m$ 不能为 $0$。{{ select(23) }}

• √
• ×

24. 第 $9\sim 19$ 行的 do while 循环一共有 $2$ 个出口。{{ select(24) }}

• √
• ×

25. 数组 $a$ 和 $b$ 中的数值都小于或等于 $n$。{{ select(25) }}

• √
• ×

选择题

26. 若输入数据为11 8，则输出结果为{{ select(26) }}。

• 0.(375)
• 1.(375)
• 0.375
• 1.375

27. 若输入数据为5 13，则输出结果为{{ select(27) }}。

• 0.384615
• 0.(384615)
• 0.386514
• 0.(386514)

1	#include <iostream>
2	using namespace std;
3	const int V=100;
4	int n,m,ans,e[V][V];
5	bool visited[V];
6	void dfs(int x,int len)
7	{
8		int i;
9		visited[x]=true;
10		if(len>ans)ans=len;
11		for(int i=1;i<=n;i++)
12			if((!visited[i]) && (e[x][i]!=-1))
13				dfs(i,len+e[x][i]);
14		visited[x] = false;
15	}
16	int main()
17	{
18		int i,j,a,b,c;
19		cin>>n>>m;
20		for(i=1;i<=n;i++)
21			for(j=1;j<=n;j++)
22				e[i][j]=-1;
23		for(i=1;i<=m;i++){
24			cin>>a>>b>>c;
25			e[a][b]=c;
26			e[b][a]=c;
27		}
28		for(i=1;i<=n;i++)
29			visited[i]=false;
30		ans=0;
31		for(i=1;i<=n;i++)
32			dfs(i,0);
33		cout<<ans<<endl;
34		return 0;
35	}

判断题

28. 第 $19$ 行的输入中，如果满足 $m=n*(n-1)/2$，则 $20\sim 22$ 行的初始化可以省略 {{ select(28) }}

• √
• ×

29. 将第 $31$ 行的代码换成for(i = n; i >= 1; i--),程序结果不受任何影响。 {{ select(29) }}

• √
• ×

选择题

30. 若输入数据为

4 2
1 2 1
3 4 1

则程序输出结果为。{{ select(30) }}

• $1$
• $2$
• $3$
• $4$

31. 若输入数据为

4 6
1 2 1
2 3 1
3 4 1
4 1 1
1 3 1
2 4 1

则程序输出结果为。{{ select(31) }}

• $1$
• $2$
• $3$
• $4$

32. 若输入数据为

4 3
1 2 10
2 3 20
3 1 30

则程序输出结果为。{{ select(32) }}

• $10$
• $20$
• $30$
• $50$

33. （$4$ 分）若输入数据为

4 6
1 2 10
2 3 20
3 4 30
4 1 40
1 3 50
2 4 60

则程序输出结果为。{{ select(33) }}

• $60$
• $80$
• $100$
• $150$

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

（高精度计算）由于计算机运算的数据范围表示有一定限制，如整形 int 表达范围是（$-2^{31}~2^{31}-1$），unsigned int（无符号整数）是（$0~2^{32}-1$），都约为几十亿，因此在计算位数超过十几位的数时，不能采用现有类型，只能自己编程计算。 高精度计算通用方法：高精度计算时一般采用一个数组存储一个数，数组的一个元素对应于数的一位，将数由低位到高位依次存储在数组下标对应的由低到高的位置上。另外，申请数组大小时，一般考虑了最大的情况，在很多情况下表示有富裕，即高位有很多 $0$，可能造成无效的运算和判断，因此一般利用一个整型数据存储该数的位数。下面的程序是一个高精度整数的加法运算，请补充完整程序。

1	#include <iostream>
2	#include <cstring>
3	using namespace std;
4	
5	struct HugeInt{
6		int len;
7		int num[100001];
8	};
9	HugeInt a,b,w;
10	char c[100001],d[100001];
11	void Scan_HugeInt() {
12		cin>>c;
13		cin>>d;
14		a.len = strlen(c);
15		b.len = strlen(d);
16		for(int i=0;i<a.len;i++)
17			①;
18		for(int i=0;i<b.len;i++)
19			②; 
20	}
21	void Plus() {
22		w.len=max(a.len,b.len);
23		for(int i=1;i<=w.len;i++){
24			w.num[i]+=③;
25			w.num[i+1]+=④;
26			w.num[i]%=10; 
27		}
28		if(⑤)
29			w.len++;
30	}
31	int main()
32	{
33		Scan_HugeInt();
34		Plus();
35		for(int i=2.len;i>=1;i--)
36			cout<<w.num[i];
37		cout<<endl;
38		return 0;
39	}

34. ① 处应填{{ select(34) }}

• a.num[i] = c[i]
• a.num[a.len - 1] = c[i]
• a.num[i] = c[i] - '0'
• a.num[a.len - i] = c[i] - '0'

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

• b.num[i] = d[i]
• b.num[b.len - i] = d[i]
• b.num[i] = d[i] - '0'
• b.num[b.len - i] = d[i] - '0'

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

• (a.num[i] + b.num[i])
• (a.num[i] + b.num[i]) % 10
• (a.num[i] % 10 + b.num[i] % 10)
• (a.num[i] + b.num[i] - 10)

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

• w.num[i]
• w.num[i] % 10
• w.num[i] / 10
• w.num[i] - 10

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

• w.num[w.len + 1] >= 0
• w.num[w.len + 1] == 0
• w.num[w.len + 1] > 1
• w.num[w.len + 1] != 0

（马走日）回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求条件时，就“回溯”返回，尝试其他路径。回溯法是一种选优搜索法，按选优条件向前搜索以达到目标。但当搜索到某一步时，若发现原先选择并不优或达不到目标，则退回一步重新选择，这种走不通就退回去再走的技术称为回溯法，而满足回溯条件的某个状态的点称为回溯点。 马在中国象棋中以日字的形式规则移动。请编写一段程序，给定r×c大小的棋盘以及马的初始位置（m,n）,要求不能重复经过棋盘上的同一个点，计算马有多少途径可以遍历棋盘上的所有点。

1	#include <iostream>
2	using namespace std;
3	int r,c;
4	int cnt,tot;
5	int wayr[8]={2,2,1,-1,-2,-2,1,-1};
6	int wayc[8]={1,-1,2,2,1,-1,-2,-2};
7	bool mark[1001][1001];
8	bool check(int x,int y)
9	{
10		if(①)return true;
11		return false;
12	}
13	void search(int x,int y)
14	{
15		for(int i=0;i<8;i++)
16			if(②&&③)
17			{
18				mark[x+wayr[i]][y+wayc[i]]=true;
19				tot++;
20				if(④)cnt++;
21				search(⑤);
22				tot--;
23				mark[x+wayr[i]][y+wayc[i]]=false;
24			}
25	}
26	int main()
27	{
28		cnt = 0;
29		int m,n;
30		cin>>r>>c>>m>>n;
31		if(!check(m,n))cout<<0<<endl;
32		else if(r==1 && c==1)cout<<1<<endl;
33		else
34		{
35			mark[m][n]=true;
36			search(m,n);
37			cout<<cnt<<endl; 
38		}
49	}

39. ① 处应填{{ select(39) }}

• x >= 0 && y >= 0 && x < r && y < c
• x >= 0 || y >= 0 || x < r || y < c
• x >= 0 || y >= 0 && x < r || y < c
• x >= 0 && y >= 0 || x < r || y < c

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

• check(x + wayr[i], y + wayc[i])
• check(wayr[i], wayc[i])
• !check(x + wayr[i], y + wayc[i])
• !check(wayr[i], wayc[i])

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

• mark[wayr[i]][wayc[i]]
• mark[x + wayr[i]][y + wayc[i]]
• !mark[wayr[i]][wayc[i]]
• !mark[x + wayr[i]][y + wayc[i]]

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

• tot == r * c - 1
• tot == r * c
• cnt == r * c - 1
• cnt == r * c

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

• wayr[i], wayc[i]
• x + wayr[i], y + wayc[i]
• x - wayr[i], y - wayc[i]
• x - wayr[i], y + wayc[i]