模拟卷01

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

1. 选出下列数字中公因数最大的一组（ ） {{ select(1) }}

• $133, 63$
• $104, 143$
• $195, 85$
• $69, 123$

2. 以下哪个编码不能表示数字 -0 ( )。 {{ select(2) }}

• $[00000000]_反$
• $[11111111]_反$
• $[10000000]_补$
• $[10000000]_原$

3. 二进制数00100100和00010101的和是( )。 {{ select(3) }}

• ${[57]_{10}}$
• $[00110001]_{2}$
• $[32]{16}$
• $[00110101]_{2}$

4. 下列关于位运算描述正确的是（ ） {{ select(4) }}

• 两个unsigned int类型的整数A和B进行按位或运算，得到的结果C不可能小于A也不可能小于B。
• 两个unsigned int类型的整数A和B进行按位异或运算，得到的结果C不可能既大于A又大于B。
• 一个unsigned int类型和一个unsigned long long类型的数字不能进行位运算。
• 两个unsigned int类型的整数A和B进行按位与运算得到结果C，按位或运算得到结果D，C和D一定不相等。

5. 如果 a 和 b 均为 int 类型的变量，下列表达式能正确判断“a 等于 0 并且 b 等于 0”的是（） {{ select(5) }}

• $(!a)$&&$(!b)$
• $(a==b==0)$
• $(a==0)$||$(b==0)$
• $(a==0)$-$(b==0)$$==0$

6. 对于序列$01011001$，选择其中一个子段进行翻转，（例如，选择第一个到第四个进行翻转，可以得到$10101001$），下列选项中哪个不可能由上述操作得到（ ） {{ select(6) }}

• 10011010
• 11101001
• 01110001
• 10011001

7. 两对夫妇各带一个小孩乘坐有6个座位的游览车，游览车每排只有1个座位。为安全起见，车的首尾两座一定要坐两位爸爸;两个小孩一定要在相邻位置。那么，这6人的排座方法有( )。 {{ select(7) }}

• 48
• 36
• 24
• 12

8. 现在有5个人A、B、C、D、E，要求你帮助他们围坐成一个圈。其中，A和B不想坐在相邻的位置，你有（ ）种不同的安排方案。

{{ select(8) }}

• 12
• 6
• 10
• 48

9. 在 10000 以内，不能被 3 整除也不能被 2 整除的数有（ ）个 {{ select(9) }}

• 6667
• 5000
• 3333
• 8334

10. 二叉树是一种树形数据结构，其中每个节点最多有两个子节点：一个左子节点和一个右子节点。满二叉树是每一层都完全填满，没有空缺的二叉树。一那么棵层数为 n 的满二叉树有（ ）个结点？ {{ select(10) }}

• $n$
• $2^{n-1}-1$
• $2^{n-1}$
• $2^n-1$

11. 12 个顶点的连通图的最大生成树，其边数为（）。 最大生成树的概念：保持一个图中点与点之间的联通性，删除若干条边后使图形成一棵树，使得树的两点间距离尽可能的远。 {{ select(11) }}

• 110
• 120
• 12
• 11

12. 把8个同样球放到5个不同的袋子里，允许有的袋子空着不放，问共有多少种不同的放置方法？ {{ select(12) }}

• 35
• 18
• 495
• 455

13. 已知袋中有3个相同的红球、3个相同的绿球、5个相同的黄球。每次取出一个不放回，全部取出。可能产生多少种序列( )

{{ select(13) }}

• 27720
• 55440
• 39916800‬
• 9240

14. 0,1,2,3,4,5这些数字组成一个三位数，请问在不使用重复数字的情况下，组成的数字能被5整除有多少

{{ select(14) }}

• 60
• 36
• 30
• 40

15. 六个小球，其中两个红色，两个黄色，两个蓝色，除了颜色之外完全一样。现在将它们放进一个盒子中，一次性摸出两个小球。两个小球颜色一样的概率为（ ） {{ select(15) }}

• 1/3。
• 1/5。
• 1/4。
• 2/5。

16. 小明想要统计能够被5的整除或者数位上包含5的数字，从1到2024这2024个数中，会统计多少数字（相同的数字只算依次）。 {{ select(16) }}

• 708
• 704
• 948
• 602

17. 使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少1个逆序对，因此序列 5，4，3，2，1需要执行（ ）次操作，才能完成冒泡排序。 {{ select(17) }}

• 0
• 5
• 10
• 15

18. 在方格中，每次可以往上下左右四个方向任意一个方向前进一步，那么从A到B最短路径数量是多少（）。 {{ select(18) }}

• 15
• 6
• 20
• 10

19. 二项展开式${(x+y)}^n$=$x^n$+n$x^{n-1}$y+$\frac{n(n-1)}{2}$$x^{n-2}$$y^2$+...+$y^n$的系数，正好满足杨辉三角的规律。当n=11时，二项式展开式中x$y^9$项的系数是（ ）

{{ select(19) }}

• 110
• 10
• 55
• 58

20. 矮人国是个非常奇妙的国家，其中流通的金币单位分别是1元、7元、23元。你现在要购买一个价值是100元的产品，最少你可以付出几个面值不同的金币来购买产品（ ）

{{ select(20) }}

• 12
• 9
• 3
• 6

21. 已知两个序列s1= {A,G,T,A,A,C,G,E,T,A} 、s2= {G,T,A,C,G,T,B,A,C} ，则它们的最长公共子序列是（ ）。

{{ select(21) }}

• {G,T,A,G,A}
• {A,G,T,A,C}
• {G,T,A,C,G,C,A}
• {G,T,A,C,G,T,A}

22. 在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有4 个顶点、 6 条边的连通图。若要使它不再是连通图，至少要删去其中的（ ）条边。

{{ select(22) }}

• 1
• 2
• 3
• 4

23. 某系统自称使用了一种防窃听的方式验证用户密码。密码是 n 个数 s1, s2, ⋯ , sn，均为 0 或 1。该系统每次随机生成 n 个数 a1, a2, ⋯ , an，均为 0 或1，请用户回答 (s1a1 + s2a2 + ⋯+ snan) 除以 2 的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。 然而，事与愿违。例如，当n = 4 时，有人窃听了以下5 次问答：

就破解出了密码 s1 =___ ，s2 = ___，s3 =___ ，s4 =___。 {{ select(23) }}

• 0 1 1 0
• 0 1 0 0
• 0 1 1 1
• 1 0 0 0

24. 前缀表达式 $* + 3 4 - 5 6$ 的中缀表达式为（ ） {{ select(24) }}

• $3 * 4 + 5 - 6$
• $(3 + 4) * (-5 + 6)$
• $(3 - 4) * (5 + 6)$
• $(3 + 4) * (5 - 6)$

25. 如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S 和字母键D 的顺序循环按键，即CapsLock、A、S、D、CapsLock、A、S、D、……，屏幕上输出的第81 个字符是字母（ ）。 {{ select(25) }}

• A
• S
• D
• a

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

阅读下面的程序，完成第（26）到第（30）道小题，每道小题 2 分。

01 #include <iostream>
02 #include <string>
03 using namespace std;
04 int main()
05 {
06     string str1, str2;
07     cin >> str1 >> str2;
08     int len1 = str1.length(), len2 = str2.length();
09     int pos = 0;
10     int res = 0;
11     while (pos < len1 && pos < len2)
12     {
13         res = str1[pos] - str2[pos];
14         if (res != 0)
15             break;
16         pos++;
17     }
18     if (res > 0)
19         cout << str1;
20     else
21         cout << str2;
22     return 0;
23 }

判断题 （判断题正确答题卡填涂 A，错误答题卡填涂 B）

26. 如果将第18行中的 res > 0 改成 res >= 0，输出结果一定不会改变。 {{ select(26) }}

• 正确
• 错误

27. 如果将输入的两个字符串交换输入顺序，输出结果一定不会改变。 {{ select(27) }}

• 正确
• 错误

28. while 循环运行结束后，pos 一定小于等于 len1 和 len2。 {{ select(28) }}

• 正确
• 错误

选择题

29. 若输入为 aabbcc aabbbc，则程序运行结果为 {{ select(29) }}

• aabbcc
• aabbbc
• 6
• 无输出

30. 当输入的两个字符串交换输入顺序后，对于输出的结果说法正确的是（） {{ select(30) }}

• 输出的结果一定不会改变
• 当两个字符串长度相同时，输出的结果一定不会改变
• 当两个字符串长度不相同时，输出的结果一定会改变
• 只有当输入的两个字符串完全相同时，输出的结果才不会改变

阅读下面的程序，完成第（31）到第（34）道小题。

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 }

判断题（判断题正确答题卡填涂 A，错误答题卡填涂 B，每小题 1 分）

31. 若删除第 10 行，则程序运行结果一定不变。 {{ select(31) }}

• 正确
• 错误

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

• 正确
• 错误

33. 如果输入的所有 a 都相等，则就算没有 11-15 行的循环，程序运行结果也不会改变。 {{ select(33) }}

• 正确
• 错误

选择题（将正确答案填涂在答题卡上，本小题 2 分）

34. 若将输入数字个数为 n，每个数字 a 的大小为 m，则该程序的时间复杂度为 ?

    {{ select(34) }}

• $O(nm)$
• $O(n)$
• $O(nlogn)$
• $O(nlogm)$

三、程序完善（共 5 道小题，每小题 2 分，共计 10 分）

最长回文子串：给出一个长度为 n 的字符串，输出它最长的回文子串。

回文串的定义：正着读和反着读是一样的字符串。例如 aba，abba，a 等。 试补全程序。

01    #include <bits/stdc++.h>
02    using namespace std;
03    string s;
04    int check(int l, int r){
05        for(; ; l--, r++){
06            if(r >= s.size() || l < 0 || s[l] != s[r])
07                break;
08        }
09        return ①; // 返回最长回文子串的长度
10    }
11    int main(){
12        cin >> s;
13        int maxx = 0, l, r;// 用 l r 保存最终回文串的左右端点
14        for(int i = 0; i < s.size(); i++){
15            int len = max(check(i, i), check(i, i+1));
16            if(len > maxx){
17                maxx = len;
18                if(len % 2 == 1){
19                    ②; // 记录最长回文子串的左端点
20                    ③; // 记录最长回文子串的右端点
21                }else{
22                    l = i - len / 2 + 1;
23                    r = i + len / 2;
24                }
25            }
26        }
27        cout << ④ << endl; // 根据 l r 的位置输出最终的回文子串
28    }

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

• r - l
• r - l + 1
• r - l - 1
• r

36. ② 处应填

{{ select(36) }}

• l = i - len / 2
• l = i - len + 1
• l = i - len
• l = i - len / 2 + 1

37. ③ 处应填

{{ select(37) }}

• r = i + len / 2
• r = i + len - 1
• r = i + len
• r = i + len / 2 - 1

38. ④ 处应填

{{ select(38) }}

• s.substr(l)
• s.substr(l, r)
• s.substr(l, r - l + 1)
• s.substr(l, r-l)

39. 该代码的时间复杂度为

{{ select(39) }}

• $O(n)$
• $O(n^2)$
• $O(nlogn)$
• $O(n^3)$