CSP-J 初赛模拟卷08

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

1. 下列的符号常量定义中，正确的定义格式为 ( )。

{{ select(1) }}

• #define M1
• const int M2 20;
• #define M3 10
• const char mark;

2. 在因特网中IPV4的IP地址是由 ( ) 位二进制数组成的。

{{ select(2) }}

• 16
• 32
• 8
• 64

3. 有一个int类型的递增数组，后一个元素比前前一个元素大1，第一个元素的下标是1，元素值是1，该数组的长度是30，对该数组进行二分查找，则比较五次查找成功的结点数为? ( )

// 二分查找示例代码
int binary_search(int start, int end, int key)
{
    int ret = -1; // 未搜索到数据返回-1下标
    int mid;
    while (start <= end)
    {
        mid = start + ((end - start) >> 1); // 直接平均可能会溢出，所以用这个算法
        if (arr[mid] < key)
            start = mid + 1;
        else if (arr[mid] > key)
            end = mid - 1;
        else
        { // 最后检测相等是因为多数搜索情况不是大于就是小于
            ret = mid;
            break;
        }
    }
    return ret; // 单一出口
}

{{ select(3) }}

• 8
• 12
• 15
• 16

4. 分析以下递归算法程序段，输出结果为? ( )

int factorial1(int n) {
     if (n <= 1) return 1;
     else return factorial1(n - 1) * 2;
 }
 int factorial2(int n) {
     if (n <= 1) return 1;
     else return factorial2(n - 1) + factorial1(n) + n / 2;
 }
 int factorial3(int n) {
     if (n <= 1) return 1;
     else return factorial3(n - 1) + factorial2(n) + n;
 }
 int main() {
     printf("%d", factorial3(5));
     return 0;
 }

{{ select(4) }}

• 37
• 68
• 84
• 96

5. 在一个长度为n的单链表的第 i (0 <= i < n) 个元素后面插入一个元素，需要向后移动多少个元素( )。

{{ select(5) }}

• n - i
• n - i + 1
• n - i - 1
• 0

6. 某筑路队承担了修一条公路的任务。原计划每天修720米，实际每天比原计划多修80米，这样实际修的差1200米就能提前3天完成。这条公路全长( ) 米。

{{ select(6) }}

• 9600
• 14800
• 10800
• 12000

7. 后缀表达式A B - C D E + * F / + 对应的中缀表达式是 ( )

{{ select(7) }}

• ((A - B) + C * (D + E)) / F
• (A - B) + (C * D) + (E / F)
• (A - B) + (C * D + E) / F
• (A - B) + C * (D + E) / F

8. 以下描述，错误的是（ ）

{{ select(8) }}

• 对于给定的字符集及其出现频率，哈夫曼树的形态是唯一的
• 哈夫曼树中，权值最小的节点一定是叶子节点
• 哈夫曼树中，权值越大的节点一定离根节点越近
• 哈夫曼树是一棵带权路径长度最小的二叉树

9. 体育用品仓库里有许多足球、排球和篮球，某班50名同学来仓库拿球，规定 每个人至少拿1个球，至多拿2个球，问至少有几名同学的拿球方案是一致的？( )

{{ select(9) }}

• 5
• 6
• 7
• 9

10. 现在有6位同学需要分成2组，每组3人，组的顺序无关，问有多少种方法？（ ）

{{ select(10) }}

• 360
• 20
• 90
• 45

11. 已知有两个栈a和b，栈b用以接收a中全部出栈元素，a中无元素出栈后，b 中元素从栈顶到栈底依次出栈。有5 个元素e1~e5，这 5 个元素按照 e1,e3,e5,e2,e4 的顺序入栈a，则下列哪个序列不为栈b的合法出栈序列 ( )

{{ select(11) }}

• e5,e4,e3,e2,e1
• e1,e3,e5,e2,e4
• e4,e1,e3,e5,e2
• e1,e2,e4,e5,e3

12. 若根节点深度为1，存在某棵二叉树度为1的节点个数为a，度为2的节点个数为b，且该二叉树的先序序列刚好为后序序列的逆序，则该二叉树的深度为 ( )。

{{ select(12) }}

• a + 1
• b + 1
• a + b
• a - 1

13. 已知 n 个顶点的有向图，若该图是强连通的（从所有顶点都存在路径到达其 他顶点），则该图中最少有多少条有向边？（ ）

{{ select(13) }}

• n
• n - 1
• n + 1
• n × (n - 1)

14. 在16*16点阵的汉字字库中，一个汉字“繁”所占用的字节数减去一个汉字“一”所占用的字节数等于多少？( )

{{ select(14) }}

• 0
• 256
• 32
• 3840

15. 一个彩色图像的大小为1024x768像素，每个像素使用 24位来表示RGB颜色值 （红色、绿色、蓝色各 8 位），请问这个图像需要多少的存储空间？( )

{{ select(15) }}

• 3MB
• 18432KB
• 2304KB
• 2.3MB

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

（1）

1  #include <iostream>
2  using namespace std;
3  int main() {
4      int n, m, a[105], b[105];
5      int sum = 0;
6      int x, y, t;
7      cin >> n >> m;
8      for (int i = 0; i < n; i++) {
9          cin >> a[i];
10     }
11     for (int i = 0; i < m; i++) {
12         cin >> b[i];
13     }
14     x = n;
15     y = m;
16     while (y >= 0) {
17         t = a[x];
18         a[x] = b[y];
19         b[y] = t;
20         x--;
21         y--;
22     }
23     for (int i = 0; i < min(n, m); i++) {
24         if (a[i] - b[i] > 0) {
25             sum++;
26         }
27         if (a[i] - b[i] < 0) {
28             sum--;
29         }
30     }
31     cout << sum;
32     return 0;
33 }

判断题

16. 若输入的n的值小于m的值，那么会导致程序运行错误。（ ）

{{ select(16) }}

• 正确
• 错误

17. 若输入的n的值和m的值不相同，并且程序不会运行错误，那么执行程序输出的结果一定不为0。（ ）

{{ select(17) }}

• 正确
• 错误

18. (2分) 若输入的a数组从第一个数到最后一个数的值为1,2,3,4,5，b数组从第一个到最后一个数的值为1,2,3,4，那么执行程序输出的结果为0。（ ）

{{ select(18) }}

• 正确
• 错误

单选题

19. 若输入的n的值等于10000，m的值等于10，则结果最大可能为（ ）

{{ select(19) }}

• 10000
• 0
• 10
• 10010

20. 输入的n的值为5，m的值为3，a数组的值为6,13,7,15,2，b数组的值为7,15,2， 则输出的结果为（ ）

{{ select(20) }}

• 1
• -2
• 0
• -1

（2）

1  #include <bits/stdc++.h>
2  using namespace std;
3  string getResult(int x, int k, vector<int> arr);
4  string getPermutation(int n, int k) {
5      int x = 1;
6      int i = 1;
7      vector<int> arr;
8      while (i < n) {
9          arr.push_back(i);
10         x *= i;
11         i++;
12     }
13     arr.push_back(i);
14     cout << i << endl;
15     return getResult(x, k, arr);
16 }
17 string getResult(int x, int k, vector<int> arr) {
18     int l = arr.size();
19     if (l == 1) return to_string(arr[0]);
20     int i = (k - 1) / x;
21     int y = arr[i];
22     arr.erase(arr.begin() + i);
23     return to_string(y) + getResult(x / (l - 1), k - i * x, arr);
24 }
25 int n, k;
26 int main() {
27     cin >> n >> k;
28     cout << getPermutation(n, k);
29     return 0;
30 }

假设输入满足 $1≤n≤9,1≤k≤n!$，完成下面的判断题和单选题判断题：

判断题

21. 将第 3 行代码删除，程序依然可以得到正确的结果。( )

{{ select(21) }}

• 正确
• 错误

22. 第 14 行代码输出的值一定跟 n 相同。( )

{{ select(22) }}

• 正确
• 错误

23. (2分) 将第 8 行代码 i < n 替换成 i <= n，并且将第 13 行代码删除，程序依然可以得到正确的结果。( )

{{ select(23) }}

• 正确
• 错误

单选题

24. 当输入 4 9 时，程序第28行的输出结果是 ( )

{{ select(24) }}

• 2143
• 2314
• 2341
• 2413

25. 当输入 9 360 时，getResult函数的执行次数是 ( )

{{ select(25) }}

• 8!
• 9!
• 8
• 9

26. (4分) 当输入 9 202423 时，程序第28行的输出结果是 ( )。

{{ select(26) }}

• 613294578
• 731295864
• 731295468
• 613295478

（3）

1  #include <bits/stdc++.h>
2  using namespace std;
3  vector<int> sumEvenAfterQueries(vector<int>& nums,
4                           vector<vector<int>>& queries) {
5      vector<int> res;
6      int sum = 0;
7      for (int i = 0; i < nums.size(); i++)
8          if (nums[i] % 2 == 0) sum += nums[i];
9      for (int i = 0; i < queries.size(); i++) {
10         int val = queries[i][0];
11         int index = queries[i][1];
12         if ((nums[index] & 1) == 1) {
13             if ((val & 1) == 1) {
14                 sum += (nums[index] + val);
15             }
16         } else {
17             if ((val & 1) == 0) {
18                 sum += val;
19             } else {
20                 sum -= nums[index];
21             }
22         }
23         nums[index] += val;
24         res.push_back(sum);
25     }
26     return res;
27 }
28 int main() {
29     int num, number, row, column;
30     cin >> num;
31     vector<int> vec(num, 0);
32     for (int i = 0; i < num; i++) {
33         cin >> vec[i];
34     }
35     cin >> row >> column;
36     vector<vector<int>> queries(row, vector<int>(column, 0));
37     for (int i = 0; i < row; i++) {
38         for (int j = 0; j < column; j++) {
39             cin >> queries[i][j];
40         }
41     }
42     vector<int> v = sumEvenAfterQueries(vec, queries);
43     for (int i = 0; i < v.size(); i++) {
44         cout << v[i] << " ";
45     }
46     cout << endl;
47     for (int i = 0; i < v.size(); i++) {
48         v[i] |= (1 << i) & ~(1 << i) ^ (1 << i);
49         cout << v[i] << " ";
50     }
51     return 0;
52 }

判断题

27. 该程序实现的功能是多次查询并更新数组元素，根据每次查询结果，计算每次查询后数组中所有奇数元素之和。( )

{{ select(27) }}

• 正确
• 错误

28. 当输入 3 3 2 1 3 2 3 1 4 2 5 3，程序能够输出正确结果。( )

{{ select(28) }}

• 正确
• 错误

29. (2分) 将 8 行代码的 if 判断条件修改为 nums[i] ^ 1 == nums[i] + 1，不影响程序的运行结果。 ( )

{{ select(29) }}

• 正确
• 错误

单选题

30. 当输入 4 1 2 3 4 4 2 1 0 3 1 -4 1 3 2 时，程序的 43~45 行产生的输出结果为 ( )

{{ select(30) }}

• 8 6 6 12
• 8 8 6 12
• 8 6 8 12
• 6 6 8 12

31. 下列选项中，该程序最准确的时间复杂度分析结果为 ( )

{{ select(31) }}

• $O(1)$
• $O(num)$
• $O(num+row)$
• $O(num+row*column)$

32. 当输入5 1 2 3 4 5 2 2 1 0 1 0，程序的 47~52 行产生的输出结果是 ( )。

{{ select(32) }}

• 6 9
• 9 8
• 8 6
• 9 6

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

（1）

用两个栈实现队列 我们要实现一个类似于C++标准库里的std::queue的类型Queue。试补全程序。

#include<bits/stdc++.h>
using namespace std;
struct Queue {
	stack<int> stk1, stk2;
	int t;
	void push(int x) {
		stk1.push(x);
		t = x;
	}
	void check() {
		if(①) {
			while(②) {
				③;
				④;
			}
		}
	}
	void pop() {
		check();
		stk2.pop();
	}
	int front() {
		check();
		return ⑤;
	}
	int back() {
		return t;
	}
	bool empty() {
		return stk1.empty() && stk2.empty();
	}
	int size() {
		return stk1.size() + stk2.size();
	}
};

33. ①处应填（ ）

{{ select(33) }}

• stk1.empty()
• stk2.empty()
• !stk1.empty()
• !stk2.empty()

34. ②处应填（ ）

{{ select(34) }}

• stk1.empty()
• stk2.empty()
• !stk1.empty()
• !stk2.empty()

35. ③处应填（ ）

{{ select(35) }}

• stk1.push(stk2.top())
• stk2.push(stk1.top())
• stk1.push(t)
• stk2.push(t)

36. ④处应填（ ）

{{ select(36) }}

• stk1.pop()
• stk2.pop()
• stk1.push(t)
• stk2.push(t)

37. ⑤处应填（ ）

{{ select(37) }}

• stk1.pop()
• stk2.pop()
• t + 1
• t - 1

（2）

现在有两个n*n的字母方阵，希望你输出通过下列什么操作能将第一个原始方 阵转换成第二个目标方阵。如果多种操作都可以完成，请输出序号最小的一个。

操作1：将方阵顺时针旋转90度。

操作2：将方阵顺时针旋转180度。

操作3：将方阵逆时针旋转90度。

操作4：将方阵水平翻转（A∣B−>B∣A）。

操作5：执行操作4后，再执行操作1-3中的一个。

操作6：不改变方阵。

操作7：无法通过上述操作将原始方阵转换成目标方阵。

#include <iostream>
using namespace std;
int n;
string a[15], b[15], c[15];
void f() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            __①__;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = c[i][j];
        }
    }
}
void k() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            __②__;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = c[i][j];
        }
    }
}
int h() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (__③__) {
                return 0;
            }
        }
    }
    return 1;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> b[i][j];
        }
    }
    f();
    if (h() == 1) {
        cout << 1;
        return 0;
    }
    f();
    if (h() == 1) {
        cout << 2;
        return 0;
    }
    f();
    if (h() == 1) {
        cout << 3;
        return 0;
    }
    __④__;
    k();
    if (h() == 1) {
        cout << 4;
        return 0;
    }
    f();
    if (h() == 1) {
        cout << 5;
        return 0;
    }
    f();
    if (__⑤__) {
        cout << 5;
        return 0;
    }
    f();
    if (h() == 1) {
        cout << 5;
        return 0;
    }
    f();
    k();
    if (h() == 1) {
        cout << 6;
        return 0;
    }
    cout << 7;
    return 0;
}

38. ①处应填（ ）

{{ select(38) }}

• c[i][j]=a[n-j+1][i]
• c[i][j]=a[n-j][i]
• c[i][j]=a[i][n-j]
• c[i][j]=a[i][n-j+1]

39. ②处应填（ ）

{{ select(39) }}

• c[i][j]=a[i][n-j+1]
• c[i][j]=a[i][n-j]
• c[i][j]=a[n-j+1][i]
• c[i][j]=a[n-j][i]

40. ③处应填（ ）

{{ select(40) }}

• a[i][j]==b[i][j]
• a[i][j]>b[i][j]
• a[i][j]!=b[i][j]
• a[i][j]<b[i][j]

41. ④处应填（ ）

{{ select(41) }}

• k()
• f()
• h()
• int t = h()

42. ⑤处应填（ ）

{{ select(42) }}

• h() > 1
• h() < 1
• h() != 1
• h() == 1