初赛模拟题

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

第1题

在 C++ 中，下面哪个关键字用于声明一个局部变量，使其在整个程序运行期间都保持有效（ ）

A. unsigned B. const C. static D. mutable

第2题

十六进制数 3C4D 和 9876 的和为（ ）

A. D4C3 B. D3C4 C. D4C4 D. D3C3

第3题

以下不属于面向对象程序设计语言的是（ ） A. C++ B. Python C. Java D. C

第4题

阅读以下代码，说法正确的选项是（ ）

xxxxxxxxxx
31
1
#include <iostream>
2
using namespace std;
3
class ManyData{
4
    int * __data;
5
    int head, tail, capacity;
6
public:
7
    ManyData(int cap){
8
        capacity = cap;
9
        __data = new int[capacity];
10
        head = tail = 0;
11
    }
12
    void push(int val){
13
        __data[tail++]= val;
14
    }
15
    int pop(){
16
        return __data[--tail];
17
    }
18
    int size(){
19
        return tail - head;
20
    }
21
};
22
int main(){
23
    auto myData=ManyData(100);
24
    myData.push(1);
25
    myData.push(2);
26
    myData.push(3);
27
    myData.push(100);
28
    cout<< myData.size()<< endl;
29
    cout<< myData.pop()<< endl;
30
    return 0;
31
}

A.这段代码不能正常运行。 B. ManyData 类可⽤于构造队列（Queue）数据结构。 C.在上⾯代码环境，代码 cout<< myData.__data[0] << endl; 可以增加到代码 main 函数末尾（ return 0; 之前），且不会导致报错。 D.可以为 ManyData 类的 push() 、 pop() 函数增加异常处理代码，否则在使用 ManyData 类时可能导致运⾏时错误或逻辑错误（不⼀定局限于上述代码中的main 函数）。

第5题

某内容仅会出现 ABCDEFG ，其对应的出现概率为 0.40、0.30、0.15、0.05、0.04、0.03、0.03。按照哈夫曼编码规则，假设 B 的编码为 11 ，则 D 的编码为（ ） A. 10010 B. 10011 C. 10111 D. 10001

第6题

根节点高度为1的，拥有20个节点的二叉树，最多有多少叶子节点（ ）

A. 10 B. 12 C. 13 D. 15

第7题

N 个节点的双向循环链，在其中查找某个节点的平均时间复杂度是（ ） A. 0(1) B. 0(N) C. 0(log N) D. 0(N*N)

第8题

G 是⼀个⾮连通⽆向图，共有 28 条边，则该图⾄少有（ ）个顶点 A. 6 B. 7 C. 8 D. 9

第9题

某⼆叉树T的先序遍历序列为： {A B D F C E G H} ，中序遍历序列为： {B F D A G E H C} ，则下列 说法中正确的是（ ） A. T的度为1 B. T的⾼为4 C. T有4个叶节点 D. 以上说法都不对

第10题

图的⼴度优先搜索中既要维护⼀个标志数组标志已访问的图的结点，还需哪种结构存放结点以实现遍历（ ） A. 双向栈 B. 队列 C. 哈希表 D. 堆

第11题

给定⼀个简单有向图 G ，判断其中是否存在环路的下列说法哪个最准确 （ ） A. BFS更快 B. DFS更快 C. BFS和DFS⼀样快 D. 不确定

第12题

⼩杨要从A城到B城，⼜想顺路游览⼀番。他有两个选项：1、坐⾼铁路到C城游览，再坐⾼铁或飞机到B城； 2、坐船到D城游览，再坐船、⾼铁或飞机到B城。请问⼩杨从A城到B城共有⼏种交通⽅案可以选择 （ ） A. 2 B. 3 C. 5 D. 6

第13题

以下哪个函数声明是符合语法的，且在调⽤时可以将⼆维数组的名字作为实际参数传递给形式参数 a （ ） A. void QuickSort(int a[][10], int n); B. void QuickSort(int a[5][], int m); C. void QuickSort(int a[][], int n, int m); D. void QuickSort(int ** a, int n, int m);

第14题

以下关于⼆叉排序树的说法，正确的是 （ ） A. ⼆叉排序树的中序遍历序列⼀定是有序的。 B. 在含 n 个节点的⼆叉排序树中查找元素，最差情况的时间复杂度为 。 C. ⼆叉排序树⼀定是⼆叉平衡树。 D. 以上说法都不对。

第15题

下⾯有关C++类的说法，错误的是（ ） A. C++类对象销毁时，会执⾏析构函数。 B. C++类可以通过定义构造函数实现⾃动类型转换。 C. C++类可以通过重载 [] 运算符实现通过给定下标访问数组成员的元素。 D. C++类可以包含任意类型的成员变量

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

第16题

1. xxxxxxxxxx
   65
   1
   #include <iostream>
   2
   #include <vector>
   3
   #include <cmath>
   4
   using namespace std;
   5
   
   6
   bool isPrime(int n) {
   7
       if (n <= 1) return false;
   8
       if (n <= 3) return true;
   9
       if (n % 2 == 0 || n % 3 == 0) return false;
   10
       for (int i = 5; i * i <= n; i += 6) {
   11
           if (n % i == 0 || n % (i + 2) == 0) return false;
   12
       }
   13
       return true;
   14
   }
   15
   
   16
   int sumOfDivisors(int n) {
   17
       int sum = 1 + n; 
   18
       for (int i = 2; i <= sqrt(n); i++) {
   19
           if (n % i == 0) {
   20
               sum += i;
   21
               sum += n / i;
   22
           }
   23
       }
   24
       return sum;
   25
   }
   26
   
   27
   pair<int, int> findPrimeProduct(int n) {
   28
       for (int i = 2; i <= sqrt(n); i++) {
   29
           if (n % i == 0 && isPrime(i) && isPrime(n / i)) {
   30
               return make_pair(i, n / i);
   31
           }
   32
       }
   33
       return make_pair(-1, -1);
   34
   }
   35
   
   36
   int main() {
   37
       int n;
   38
       cin >> n;
   39
   
   40
       int divisorSum = sumOfDivisors(n);
   41
       pair<int, int> primeProduct = findPrimeProduct(n);
   42
   
   43
       cout << divisorSum << " ";
   44
   
   45
       if (primeProduct.first != -1) {
   46
           cout << primeProduct.first * primeProduct.second << endl;
   47
       } else {
   48
           cout << 0 << " ";
   49
       }
   50
       return 0;
   51
   }
   52
   
   53
   1. 当输入60时，输出43行输出168。（）
   54
   2. 第9行的false应该改成true。（）
   55
   3. findPrimeProduct函数可以用来分辨一个数字是否能拆分成两个质数的乘积的形式。（）
   56
   4. 输入75时，输出什么？（）
   57
       A. 124 0
   58
       B. 124 3 25
   59
       C. 124 75
   60
       D. 无法确定
   61
   5. 输入36时，输出什么？（）
   62
       A. 91 0
   63
       B. 97 36
   64
       C. 97 0
   65
       D. 91 4 9
   

第17题

1. xxxxxxxxxx
   44
   1
   #include <iostream>
   2
   using namespace std;
   3
   int cnt1 = 0, cnt2 = 0;
   4
   int gcdEuclid(int a, int b) {
   5
       while (b != 0) {
   6
           int temp = b;
   7
           b = a % b;
   8
           a = temp;
   9
           cnt1++;
   10
       }
   11
       return a;
   12
   }
   13
   int gcdSubtraction(int a, int b) {
   14
       while (a != b) {
   15
           if (a > b) a -= b;
   16
           else b -= a;
   17
           cnt2++;
   18
       }
   19
       return a;
   20
   }
   21
   int main() {
   22
       int a, b;
   23
       cin >> a >> b;
   24
       int num1 = gcdEuclid(a,b);
   25
       int num2 = gcdSubtraction(a,b);
   26
       if(num1 == num2) cout<<num1<<endl;
   27
       else cout<<num1<<" "<<num2<<endl;
   28
       return 0;
   29
   }
   30
   1. gcdEuclid 与 gcdSubtraction 的返回值都代表最大公约数。（）
   31
   2. 任何情况下，cnt1 大于 cnt2。（）
   32
   3. 任何情况下，cnt1 大于等于 cnt2。（）
   33
   4. 输入 0 50 时，输出 0 。（）
   34
   5. 输入 5 13 时，cnt1 与 cnt2 相等。（）
   35
   6. 输入 200 300 时，输出内容为。（）
   36
       A.0 100
   37
       B.100 0
   38
       C.100
   39
       D.0 0
   40
   7. 输入 131 11 时，cnt1和cnt2的值为。（）
   41
       A.11
   42
       B.12
   43
       C.131 11
   44
       D.3 21
   

第18题

1. xxxxxxxxxx
   64
   1
   #include <iostream>
   2
   #include <vector>
   3
   #include <set>
   4
   using namespace std;
   5
   
   6
   vector<int> primeFactors(int n) {
   7
       vector<int> factors;
   8
       set<int> uniqueFactors;
   9
       for (int i = 2; i <= n; i++) {
   10
           while (n % i == 0) {
   11
               uniqueFactors.insert(i);
   12
               n /= i;
   13
           }
   14
       }
   15
       for (int factor : uniqueFactors) {
   16
           factors.push_back(factor);
   17
       }
   18
       return factors;
   19
   }
   20
   
   21
   int productOfUniquePrimeFactors(const vector<int>& factors) {
   22
       int product = 0;
   23
       for (int factor : factors) {
   24
           product *= factor;
   25
       }
   26
       return product;
   27
   }
   28
   
   29
   int main() {
   30
       int n;
   31
       cin >> n;
   32
   
   33
       vector<int> factors = primeFactors(n);
   34
   
   35
       for (int factor : factors) {
   36
           cout << factor ;
   37
       }
   38
       
   39
       cout << productOfUniquePrimeFactors(factors) << endl;
   40
   
   41
       return 0;
   42
   }
   43
   1. 本题2分，输入 120 ，输出 120 。（）
   44
   2. 本题2分，输入 120 ，输出 0 。（）
   45
   3. 将22行初始化0改为1后，productOfUniquePrimeFactors( 90 ) 的结果为。（）
   46
       A. 90
   47
       B. 0
   48
       C. 60 
   49
       D. 30
   50
   4. primeFactors( 99 ) 的返回值为。（）
   51
       A.3 11
   52
       B.3 3 11
   53
       C.1 3 11 99
   54
       D.9 11
   55
   5. 输入 131 ，输出。（）
   56
       A.131
   57
       B.0
   58
       C.1310
   59
       D.0131
   60
   6. 将23行改为：product += factor;输入 131 ，输出。（）
   61
       A.131
   62
       B.131131
   63
       C.13131
   64
       D.0
   

    

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

第19题

1. 给定一个已旋转的有序数组 nums，请找到数组中的最小元素。数组中的元素原本是递增排序的，但在某个未知的节点上被旋转了若干次。

xxxxxxxxxx
35
1
#include <iostream>
2
#include <vector>
3
using namespace std;
4

5
int findMin(vector<int>& nums) {
6
    int left = 0;
7
    int right = 【①】;
8
    
9
    while (left < right) {
10
        int mid = left + (right - left) / 2;
11
        
12
        if (nums[mid] > nums[right]) { 
13
            【②】;
14
        } else if (nums[mid] < nums[right]) { 
15
            【③】;
16
        } else if (【④】) {
17
            【⑤】; 
18
        }
19
    }
20
    
21
    return 【⑥】; 
22
}
23

24
int main() {
25
    vector<int> nums;
26
    int n;
27
    cin >> n;
28
    nums.resize(n);
29
    for (int i = 0; i < n; ++i) {
30
        cin >> nums[i];
31
    }
32
    
33
    cout << "Minimum element: " << findMin(nums) << endl;
34
    return 0;
35
}

xxxxxxxxxx
36
1
1.
2
    ① 处应填（ ）
3
    A. nums.size() - 1
4
    B. nums.size() + 1
5
    C. nums.size()
6
    D. nums.max_size()
7
2.
8
    ② 处应填（ ）
9
    A. left = mid + 1
10
    B. right = mid - 1
11
    C. left = mid
12
    D. right = mid
13
3.
14
    ③ 处应填（ ）
15
    A. left = mid + 1
16
    B. right = mid - 1
17
    C. left = mid
18
    D. right = mid
19
4.
20
   ④ 处应填（ ）
21
    A. nums[left] == nums[mid] 
22
    B. nums[right] == nums[mid]
23
    C. left == mid
24
    D. right == mid
25
5.
26
    ⑤ 处应填（ ）
27
    A. left = mid + 1
28
    B. right = mid - 1
29
    C. left++
30
    D. right--
31
6.
32
    ⑥ 处应填（ ）
33
    A. nums[left]
34
    B. nums[right]
35
    C. nums[mid]
36
    D. nums[0]

第20题

2. （最长公共子序列）给定两个字符串 str1 和 str2，求这两个字符串的最长公共子序列的长度。

xxxxxxxxxx
29
1
#include <iostream>
2
#include <string>
3
#include <vector>
4
using namespace std;
5

6
int lcs_dp(string str1, string str2) {
7
    int m = str1.length();
8
    int n = str2.length();
9
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
10

11
    for (int i = 0; i <= m; i++) {
12
        for (int j = 0; j <= n; j++) {
13
            if (i == 0 || j == 0)
14
                dp[i][j] = 【①】;
15
            else if (【②】)
16
                dp[i][j] = 【③】;
17
            else
18
                dp[i][j] = max(dp[i - 1][j], 【④】);
19
        }
20
    }
21
    return dp[m][n];
22
}
23

24
int main() {
25
    string str1, str2;
26
    cin >> str1 >> str2;
27
    cout << "Length of Longest Common Subsequence: " << lcs_dp(str1, str2) << endl;
28
    return 0;
29
}

xxxxxxxxxx
24
1
1.
2
    ① 处应填（ ）
3
    A. 0
4
    B. 1
5
    C. i
6
    D. j
7
2.
8
    ② 处应填（ ）
9
    A. str1[i] == str2[j]
10
    B. str1[i-1] == str2[j-1]
11
    C. str1[i] != str2[j]
12
    D. str1[i-1] != str2[j-1]
13
3.
14
    ③ 处应填（ ）
15
    A. dp[i-1][j-1]
16
    B. dp[i-1][j-1] + 1
17
    C. dp[i-1][j]
18
    D. dp[i][j-1]
19
4.
20
    ④ 处应填（ ）
21
    A. dp[i-1][j-1]
22
    B. dp[i-1][j-1] + 1
23
    C. dp[i-1][j]
24
    D. dp[i][j-1]