单项选择题（每题只有一个正确选项，每题2分，共30分）

1. 计算机存储数据的基本单位是{{ select(1) }}

• bit
• Byte
• GB
• KB

2. 十进制小数 $13.375$ 对应的二进制数是{{ select(2) }}

• $1101.011$
• $1011.011$
• $1101.101$
• $1010.01$

3. 要求以下程序的功能是计算：$s=1+1/2+1/3+...+1/10$。

#include <iostream>
using namespace std;
int main(){
    int n;
    float s;
    s = 1.0;
    for(n = 10; n > 1; n--)
        s = s + 1 / n;
    cout << s << endl;
    return 0;
}

程序运行后输出结果错误，导致错误结果的程序行是{{ select(3) }}。

• s = 1.0;
• for(n = 10; n > 1; n--);
• s = s + 1 / n;
• cout << s << endl;

4. 2017 年 10 月 1 日是星期日，1999 年 9 月 29 日是 {{ select(4) }}

• 星期三
• 星期日
• 星期五
• 星期二

5. 已知表头元素为c的单链表在内存中的存储状态如下表所示。现将f存放于 $1014H$ 处并插入单链表，若f在逻辑上位于a和e之间，则a,e,f的“链接地址”依次是

地址	元素	链接地址
1000H	a	1010H
1004H	b	100CH
1008H	c	1000H
100CH	d	NULL
1010H	e	1004H
1014H	f

{{ select(5) }}

• 1010H,1014H,1004H
• 1010H,1004H,1014H
• 1014H,1010H,1004H
• 1014H,1004H,1010H

6. 设二叉树有 $2n$ 个结点，且 $m<n$，则不可能存在 {{ select(6) }}

• $n$ 个度为 $0$ 的点
• $2m$ 个度为 $0$ 的点
• $2m$ 个度为 $1$ 的点
• $2m$ 个度为 $2$ 的点

7. 一家四口人，至少两个人生日属于同一月份的概率是 {{ select(7) }} （假定每个人生日属于每个月份的概率相同且不同人之间相互独立）。

• $1/12$
• $1/144$
• $41/96$
• $3/4$

8. 表达式a * (b + c) * d的后缀形式为 {{ select(8) }}

• a b c d * + *
• a b c + * d *
• a * b c + * d
• b + c * a * d

9. 求整数 $n(n\ge0)$ 的阶乘的算法如下，其时间复杂度是

int fact(int n){
    if(n <= 1) return 1;
    return n * fact(n - 1);
}

{{ select(9) }}

• $O(log_n)$
• $O(n)$
• $O(nlog_n)$
• $O(n^2)$

10. 将 7 个名额分给 4 个不同的班级，允许有的班级没有名额，有{{ select(10) }} 种不同的分配方案。

• $60$
• $84$
• $96$
• $120$

11. 若 f[0] = 0, f[1] = 1, f[n + 1] = (f[n] + f[n - 1]) / 2，则随着 i 的增大，f[i]将接近于{{ select(11) }}

• $1/2$
• $2/3$
• $(√5 - 1)/2$
• $1$

12. 设 a,b,c,d,e,f 以所给的次序进栈，若在进栈操作时，允许出栈操作，则下面得不到的序列为{{ select(12) }}

• fedcba
• bcafed
• dcefba
• cabdef

13. 若串 ”S=“copyright”，其子串的个数是（{{ select(13) }}

• 78
• 45
• 46
• 36

14. 下列哪个算法不是用来求最小生成树的：{{ select(14) }}

• Kruscal 算法
• Boruvka 算法
• Prim 算法
• Tarjan 算法

15. 甲、乙、丙三位同学选修课程，从 4 门课程中，甲选修 2 门，乙、丙各选修3门，则不同的选修方案共有{{ select(15) }}种。

• 36
• 48
• 96
• 192

程序阅读理解题（共3大题。程序输入不超过数组或字符串定义的范围，除特殊说明外，判断题1.5分，选择题3分，共计40分）

#include <bits/stdc++.h>
using namespace std;
int main(){
   int n, x;
   cin >> n;
   int a[10];
   for(int i=0;i<10;++i) a[i] = n;
   bool ok = true;
   for(x = 1; ok; ++x){
   	int y = x;
   	while(y > 0) {
   		if(--a[y % 10] < 0) {cout << x - 1 << endl; ok = false;}
   		y /= 10;
	   }
   }
   return 0;
}

判断题

16. 将第 7 行改为memset(a, n, sizeof(a));程序运行结果不变。{{ select(16) }}

• 对
• 错

17. 将第 12 行的ok=false改为break程序可能会进入死循环。{{ select(17) }}

• 对
• 错

18. 程序可能会输出多行。{{ select(18) }}

• 对
• 错

19. 将第 12 行--a[y%10]<0改为a[y%10]--<0程序运行结果不变。{{ select(19) }}

• 对
• 错

选择题

20. 程序输入 $3$ 时，输出{{ select(20) }}

• 2
• 3
• 10
• 11

21. 程序输入20时，输出{{ select(21) }}

• 20
• 99
• 100
• 101

#include <bits/stdc++.h>
using namespace std;
int p;
void fun(int &x, int &y);
void func(int &x, int &y){
	if(y > x) return;
	x--; y/= 2;
	fun(x,y);
}
void fun(int &x, int &y){
	if(x == 1) return;
	x /= 2; y += p;
	func(x,y);
}
int main(){
   int x, y;
   cin >> x >> y >> p;
   fun(x,y);
   cout << x << " " << y;
   return 0;
}

判断题

22. 将第 04 行的&去除掉后，程序仍能通过编译。{{ select(22) }}

• 对
• 错

23. 读入的 x，y，p 为 int 范围内任意值时程序均能完成运行。{{ select(23) }}

• 对
• 错

24. （3分）若 x=1 时，输出的 x，y 与输入的一致。{{ select(24) }}

• 对
• 错

25. （3分）输出的 x 必然小于等于输入的 x。{{ select(25) }}

• 对
• 错

选择题

26. 输入为 7 33 2 时，输出为{{ select(26) }}

• 4 31
• 4 35
• 3 31
• 3 35

27. （4分）输入为 33 7 2 时，输出为{{ select(27) }}

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

#include <bits/stdc++.h>
using namespace std;
vector<int> ans;
int n, g[65][65], d[65];
char str[5];
char tochar(int x){
	if(x >= 1 && x <= 26) return x - 1 + 'A';
	else return x - 27 + 'a';
}
int getnum(char ch){
	if(ch >= 'A' && ch <= 'Z') return ch - 'A' + 1;
	else return 27 + ch - 'a';
}
void dfs(int now){
	for(int i=1;i<=52;++i){
		if(g[now][i]){
			g[now][i] = g[i][now] = 0;
			dfs(i);
		}
	}
	ans.push_back(now);
}
int main()
{
   int cnt = 0, u1 = 1e9 + 7, u2 = 1e9 + 7;
   cin >> n;
   for(int i=1;i<=n;++i){
   	cin >> str;
   	int u = getnum(str[0]), v = getnum(str[1]);
   	g[u][v] = g[v][u] = 1;
   	d[u]++;
   	d[v]++;
   }
   for(int i=1;i<=52;++i){
   	if(d[i] & 1){
   		cnt++;
   		u1 = min(u1, i);
	   } else {
	   	if(d[i] != 0) u2 = min(u2, i);
	   }
   }
   if(cnt != 0 && cnt != 2){
   	cout << "No Solution" << endl;
   	return 0;
   }
   if(!cnt) dfs(u2);
   else dfs(u1);
   reverse(ans.begin(), ans.end());
   for(int i=0;i<ans.size();++i) cout << tochar(ans[i]);
   return 0;
}

（约定每次输入的str均由2个大写或小写字母拼接而成，如"aa", "Xt", "RE"）

判断题

28. 若n=1，则输出结果和输入的str 相同。{{ select(28) }}

• 对
• 错

29. 若每次输入的str 均为"aa" ，则输出结果为n+1 个'a' 拼接而成的字符串。{{ select(29) }}

• 对
• 错

30. 若n>1，且每次输入的str 共2n 个字符两两不同，则输出"No Solution"。{{ select(30) }}

• 对
• 错

31. 若n=26，且输入的str依次为"ab", "bc", "cd", ..., "za"，则输出结果为"abcd...za"。{{ select(31) }}

• 对
• 错

选择题

32. 在所有str 中，出现奇数次的字母个数为几时，程序不会输出"No Solution"。{{ select(32) }}

• 1
• 2
• 3
• 4

33. 当输入为"9 ab cd hh od ob bb ba bh ha" 时，输出字符串的长度为{{ select(33) }}

• 2
• 8
• 9
• 10

程序完善题（共2大题，每个选择题3分，共计30分）

（坐标统计）输入n个点的坐标，输出每个点左下方的点的个数，并且输出哪个点的"左下角的点的个数"最多（若有并列，则输出编号最大的那个）

注：左下角的点指的是x和y的坐标都更小的点。

试补全程序。

#include<iostream>
using namespace std;
const int N=110;
int x[N],y[N];
int num[N];
int n;
int i,j;
int cnt,ans;
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)cin>>x[i]>>y[i];
    cnt=0;
    for(i=1;i<=n;i++)
    {
        num[i]=[__ ①__];
        for(j=1;j<=n;j++)
        {
            if(x[j]<x[i]&&[___②_])
            [___③___];
        }
        if([___④___])
        {
            cnt=num[i];
            [____⑤____]; 
        }
    }
    for(i=1;i<=n;i++) cout<<num[i]<<endl;
    cout<<ans<<endl;
    return 0;
}

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

• 0
• 1
• i
• 0x3f

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

• y[j]<=y[i]
• y[j]<y[i]
• y[j]>y[i]
• y[j]>=y[i]

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

• ans=i
• num[i]++
• num[i]--
• ans++

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

• （num[i]>cnt）
• （num[i]>=cnt）
• （num[i]<cnt）
• （num[i]<=cnt）

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

• ans++
• ans+=cnt
• ans=i
• ans=cnt

（n选m排列）1~n中选m个数，输出这m个数的全排列，但由于这m个数并不确定，所以需要你输出所有可能的序列。

输出要求按照字典序从小到大输出。

题目保证 $1<n<20,1<m<n$

输入	输出
3 2	1 21 32 12 33 13 2

试补全程序。

#include <iostream>
#include <cstring>
using namespace std;
const int N=25;
bool vis[N];
int a[N];
int n,m；
int i,j,k;
bool flag;
int main() 
{
    cin>>n>>m;
    memset(vis,false,sizeof(vis));
    for(i=1; i<=m; i++) 
    {
        a[i]=i;
        vis[i]=true;
    }
    flag=true;
    while(flag)
    {
        for(i=1; i<=m-1; i++)
            cout<<a[i]<<" ";
            cout<<a[m]<<endl;
        flag=[ ① ];
        for(i=m; i>=1; i--) 
        {
            [ ② ];
            for(j=a[i]+1; j<=n; j++)
                if(!vis[j]) 
                {
                    vis[j]=true;
                    a[i]=[ ③ ];
                    flag=true;
                    break;
                }
                if(flag) 
                {
                    for(k=i+1; k<=m; k++)
                    for(j=1; j<=[ ④ ]; j++)
                        if(!vis[j]) 
                        {
                            a[k]=j;
                            vis[j]=true;
                            break;
                        }
                    [ ⑤ ];
                }
        }
    }
    return 0;
}

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

• false
• true
• 2
• -1

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

• vis[i]=true
• a[i]=i
• vis[a[i]]=true
• vis[a[i]]=false

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

• j
• i
• true
• false

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

• n
• m
• i
• j

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

• return 0
• exit
• continue
• break