模拟卷02

一、单项选择题（共 25 题，每题 3 分，共计 75 分；每题有且仅有一个正确选项）

1. 根节点高度为 1，对于一棵有 118 个节点的二叉树，其树高至少为 ( )。 {{ select(1) }}

• 5
• 6
• 7
• 8

2. 某班有 6 名学生参加表演会。表演会上有 4 个不同的节目需要参演。每个学生恰好参演其中一个节目，且不允许一个节目有三个或三个以上的学生参加。安排学生参加表演会的不同方案共有 ( ) 种。 {{ select(2) }}

• 540
• 1080
• 960
• 1320

3. 对于入栈序列 {1, 2, 3, 4, 5}，下列哪一个不是可能的出栈序列 ( )。 {{ select(3) }}

• {1, 2, 3, 4, 5}
• {1, 3, 2, 5, 4}
• {5, 1, 2, 3, 4}
• {5, 4, 3, 2, 1}

4. 现在有 3 位男生和 3 位女生共 6 位同学站成一排，若男生甲不站两端，3 位女生中有且只有两位女生相邻，则排队方案有 ( ) 种。 {{ select(4) }}

• 360
• 288
• 216
• 96

5. 字符串 abbccacb 和字符串 abcacaab 之间的最长公共子串是 ( )。 {{ select(5) }}

• abcacb
• accab
• bcacb
• bccacb

6. 在平面直角坐标系中取 n 个整点（即横纵坐标均为整数的点）。当 n 至少为 ( ) 时，这 n 个点中必定会有两个点的中点为整点。 {{ select(6) }}

• 4
• 3
• 6
• 5

7. 在 C++ 程序中，表达式 130 | 10 的值为 ( ) 。 {{ select(7) }}

• 13
• 1
• 120
• 138

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

• 84
• 120
• 96
• 20

9. 对于任何一个无向连通图的最小生成树，下列说法正确的是？ {{ select(9) }}

• 有一棵或多棵
• 只有一棵
• 一定有多棵
• 可能不存在

10. 对于一棵满二叉树，共有 a 个结点和 b 个叶结点，高度为 h ，下列选项中说法正确的是？

{{ select(10) }}

• $a=2b-1$
• $b=2a-1$
• $a=2^h$
• $a=2h$

11. 马路上有编号为 1,2,3,4,5,6,7,8,9 的九盏路灯，现要关闭其中的 3 盏灯，但不能关掉相邻的 2 盏或 3 盏灯，也不能关掉两端的任意一盏灯，求满足条件的关灯方法有多少种？

{{ select(11) }}

• 10
• 15
• 20
• 25

12. 三名男生，四名女生中选三人，要求至少有一名男生和一名女生，求方案数。

{{ select(12) }}

• 12
• 35
• 30
• 15

13. 有 10 个运动员名额，分给 7 个班，每班至少一个，有 ( ) 种分配方案。

{{ select(13) }}

• 252
• 90
• 80
• 84

14. 以下关于变量的定义，命名的说法哪个是正确的？ {{ select(14) }}

• 变量名可以以数字开头，例如0a。
• 变量名只能由字母组成。
• 一个程序里可以定义多个int a;，只要这些变量的作用域不同即可。
• 变量的名字可以是系统中已经有的关键词。

15. 对n个元素的数组进行什么排序，其平均时间复杂度和最坏情况下的时间复杂度都是 $O(n \log n)$ ？ {{ select(15) }}

• 希尔排序
• 快速排序
• 堆排序
• 选择排序

16. 对于序列{2, 3, 1, 5, 4}进行冒泡排序使之变成{5, 4, 3, 2, 1}，需要进行（ ）次交换操作。 {{ select(16) }}

• 7
• 8
• 5
• 9

17. 无向图的邻接矩阵是一个？ {{ select(17) }}

• 对称矩阵
• 零矩阵
• 上三角矩阵
• 对角矩阵

18. 在一个有序数组中查找特定元素的最有效算法是？ {{ select(18) }}

• 二分查找
• 线性查找
• 插值查找
• 斐波那契查找

19. 下面的故事与（ ）算法有着异曲同工之妙。 从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚 在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事……’” {{ select(19) }}

• 枚举
• 递归
• 贪心
• 分治

20. 在一个含有 10 个元素的集合里，其非空子集的数量是 ( ) 。 {{ select(20) }}

• 1024
• 1025
• 1023
• 512

21. 按照二叉树的定义，具有3个节点的二叉树有 ( ) 种。 {{ select(21) }}

• 3
• 4
• 5
• 6

22. 在链表数据结构中，节点之间是通过什么方式进行连接的？ {{ select(22) }}

• 指针
• 变量
• 数组
• 常量

23. 用S表示进栈操作，用X表示出栈操作，若元素的进栈顺序是1,2,3,4，为了得到出栈顺序1,3,4,2，则相应的S和X的操作序列为？ {{ select(23) }}

• SXSXSSXX
• SSSXXSXX
• SXSSXXSX
• SXSSXSXX

24. 十六进制 $(8AF)_{16}$ 转化为十进制为？ {{ select(24) }}

• $(2333)_{10}$
• $(2233)_{10}$
• $(2223)_{10}$
• $(2222)_{10}$

25. 对一个具有6个点的无向完全图，其上的边共有 ( ) 条。 {{ select(25) }}

• 36
• 15
• 30
• 25

二、程序阅读（共 2 题，第 1 道小题 5 分，第 2 道小题 10 分，共计 15 分）

阅读程序第一题(每小题1分)

01    #include <iostream>
02    using namespace std;
03    int main(){
04        int n = 5, now = 1, a;
05        for(int i = 1; i <= n; i++){
06            cin >> a; // a 为正整数
07            int y = now;
08            now *= a;
09            if(now != 1){
10                if(a < y)   swap(a, y);
11                while(y != 0){
12                    int temp = y;
13                    y = a % y;
14                    a = temp;
15                }
16                now = now / a;
17            }
18        } 
19        cout << now << endl;
20    }

判断题

26. 若删除第 10 行，则程序运行结果一定不变。

{{ select(26) }}

• 正确
• 错误

27. 若将第 16 行改为now /= a;， 则程序运行结果一定不变。

{{ select(27) }}

• 正确
• 错误

28. 若将第 9 行改为if(true){，则程序运行结果一定不变。

{{ select(28) }}

• 正确
• 错误

选择题

29. 若程序的输入为 1 1 3 6 7，则输出为 {{ select(29) }}

• 3
• 18
• 126
• 42

30. 若将输入数字个数为 n，每个数字 a 的大小为 m，则该程序的时间复杂度为 {{ select(30) }}

• $O(nm)$
• $O(n)$
• $O(n \log n)$
• $O(n \log m)$

阅读程序第二题(每小题2分)

01  #include <iostream>
02  #include <stack>
03  using namespace std;
04  int main(){
05    string s;
06    cin >> s;
07    stack<int>sta;
08    bool flag = true;
09    char a[] = {'{', '[', '(', '}', ']', ')'};
10    for(int i = 0; i < s.size(); i++){
11       for(int j = 0; j < 6; j++){
12          if(a[j] != s[i])  continue;
13          if(j <= 2)  sta.push(j);
14          else if(!sta.empty()){
15             int now = sta.top();
16             sta.pop();
17             if(now + 3 != j)  flag = false;
18          }else{
19             flag = false;
20          }  
21       }
22    }
23    cout << ((flag && sta.empty()) ? "YES" : "NO");
24  }

判断题

31. 若将第 9 行的char a[] 改为 char a[6]，程序运行结果一定不变。 {{ select(31) }}

• 正确
• 错误

32. 若将第 9 行改为char a[] = {"{[(}])"};，程序运行结果一定不变。 {{ select(32) }}

• 正确
• 错误

33. 若在第 20 行之后加上一句break;，程序运行结果一定不变。{{ select(33) }}

• 正确
• 错误

选择题

34. 如果输入的字符串长度为 100，则 sta 中元素的数量最多为 ( ) 。 {{ select(34) }}

• 50
• 100
• 6
• 3

35. 若程序的输出结果为YES，则输入的字符串可能为 ( ) 。 {{ select(35) }}

• $\{[(())(])\}$
• $\{\}[]((([)]))$
• $\{[]\}[\{\}]()$
• $\{()\}([)]()$

三、程序填空（每题 2 分，共 10 分）

1.（选择数对）有 n 个小朋友分别拿着一个数字，现在要求你将小朋友两两配对，要求每对小朋友手上的数字之差大于给定值 k。问最多可以从数组中选出多少对符合条件小朋友。（每个小朋友最多只能和另外一个小朋友配对，不能脚踏两条船） 输入格式：第一行给出 n，k 分别表示小朋友的个数，以及参数 k。$(1 \leq n, k \leq 10^5)$ ，接下来给出 n 个数字，表示每个小朋友手上的数字。

提示：二分最终的结果，对于二分的结果 mid，在 check 函数中 O(n) 判断能否选出 mid 对小朋友符合要求，最终保留二分的结果。

01  #include <iostream>
02  #include <algorithm>
03  using namespace std;
04  const int maxn = 1e5 + 5;
05  int a[maxn], n, k;
06  bool check(int mid){
07    bool flag = true;
08    for(int i = 1, ①; j <= n; j++, i++){
09       if(②)
10          flag = false;
11    }
12    return flag;
13  }
14  int main(){
15    cin >> n >> k;
16    for(int i = 1; i <= n; i++)
17       cin >> a[i];
18    int l = ③, r = n, ans;
19    sort(a+1, a+1+n);
20    while(l <= r){
21       int mid = (l + r) / 2;
22       if(check(mid)){
23          ④;
24          ans = mid;
25       }else{
26          ⑤;
27       }
28    }
29    cout << ans << endl;
30  }

36. 1 处应该填的代码是: {{ select(36) }}

• j = 1
• j = n - mid
• j = n - mid + 1
• j = mid

37. 2 处应该填的代码是: {{ select(37) }}

• a[i] - a[j] > k
• a[i] - a[j] <= k
• a[j] - a[i] > k
• a[j] - a[i] <= k

38. 3 处应该填的代码是: {{ select(38) }}

• 1
• 0
• n/2
• a[1]

39. 4 处应该填的代码是: {{ select(39) }}

• l = mid
• r = mid
• l = mid + 1
• r = mid - 1

40. 5 处应该填的代码是: {{ select(40) }}

• l = mid
• r = mid
• l = mid + 1
• r = mid - 1