CSP-J 初赛模拟卷11

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

1. 以下哪位科学家被称为“博弈论之父”，“现代计算机之父”? ()

{{ select(1) }}

• 冯 · 诺依曼
• 塔扬
• 图灵
• 比尔 · 盖茨

2. 下列属于网络模型的名称是 ( )。

{{ select(2) }}

• FTP
• SMTP
• TCP/IP
• LAN

3. 设有 $100$ 个顶点，利用二分法查找时，最大比较次数是( ) 。

{{ select(3) }}

• 25
• 10
• 7
• 50

4. 学号为 $1 \sim 30$ 的小朋友顺时针排成一圈，从 $1$ 号小朋友开始顺时针报数，从数字 $1$ 开始数下去，$1，2，3，...，28，29，30，31，32$，一圈又一圈，问当数到数字 $n$，所在的小朋友的学号为多少? ( )。

{{ select(4) }}

• $(n+1)\%30-1$
• $(n-1)\%30$
• $1+(n+1)\%30$
• $(n+1)\%30$

5. 十进制小数 $13.375$ 对应的二进制数是( )。

{{ select(5) }}

• 1101.101
• 1011.011
• 1010.01
• 1101.011

6. 计算机中的数有浮点与定点两种，其中用浮点表示的数，通常由( )这两部分组成。

{{ select(6) }}

• 尾数与小数
• 阶码与尾数
• 指数与基数
• 整数与小数

7. 表达式 (1 + 34) * 5 - 56 / 7 的后缀表达式为（）

{{ select(7) }}

• 1 34 + 5 * 56 7 / -
• 1 34 + 5 56 7 - * /
• - * + 1 34 5 / 56 7
• 1 34 5 * + 56 7 / -

8. $8$ 位二进制数中去掉符号位，最大能表示多少字符 ( )

{{ select(8) }}

• 128
• 127
• 255
• 256

9. 已知一棵二叉树前序遍历为 ABCDEFGI ,后序遍历为 CEDBIGFA ，则其中序遍历可能为 ( )

{{ select(9) }}

• CBDEAGFI
• ABCDEFGI
• CBEDAIFG
• CBEDAFIG

10. 在无向图中，所有顶点的度数之和是边数的 ( ) 倍。

{{ select(10) }}

• 0.5
• 1
• 2
• 4

11. $8$ 颗子弹，编号为 $1、2、3、4、5、6、7、8$，从编号 $1$ 开始按序嵌入弹夹，以下有哪个不是正常的打出子弹的次序 ( )

{{ select(11) }}

• 87654321
• 32154876
• 32164587
• 12345678

12. 有 A、B、C、D、E、F 六个绝顶聪明又势均力敌的盗墓贼，他们都排着队，他们每个人都想独吞财宝，最前面的 A 如果拿了财宝，那么体力下降，则其后面的 B 会杀掉 A，拿了财宝，当然 B 拿了财宝，体力也会下降，一样会被 C 杀掉，如果 B 不拿财宝，则 C 无法杀 B，请问 A、C、E 的最终想法是 ( )

{{ select(12) }}

• A不拿C不拿E不拿
• A拿C拿E不拿
• A不拿C拿E拿
• A不拿C不拿E拿

13. 完全二叉树共有 $2∗N−1$ 个结点，则它的叶节点数是（ ）。

{{ select(13) }}

• $N$
• $N-1$
• $2*N$
• $2*N-1$

14. 如果用一个字节来表示整数，最高位用作符号位，其他位表示数值。例如： 00000001 表示 $1$， 10000001 表示 $−1$ ，试问这样表示法的整数 $A$ 的范围应该是( )。

{{ select(14) }}

• $-128<A<128$
• $-128 \le A<128$
• $-128 \le A \le 127$
• $-128 \le A \le 128$

15. 给出 $3$ 种排序:插入排序、冒泡排序、选择排序。这 $3$ 种排序的时间代价分别是( )。

{{ select(15) }}

• $O(n^2)、O(n)、O(n)$
• $O(\text{log }n)、O(n)、O(n^2)$
• $O(n^2)、O(n^2)、O(n^2)$
• $O(n)、O(n^2)、O(\text{log }n)$

二、阅读程序（程序输入不超过数组或字符串定义的范围;其中判断题1.5分，第5题分别为3,3,4分，第6题分别为4,4,4分，共计40分）

第一题

#include<iostream>
#include<cstdio>
using namespace std;
int i, j, n;
int x[101], y[101];
int main() {
    cin >> n;
    for (i = 1; i <= n; i++) cin >> x[i];
    for (i = 1; i < n; i++)
        for (j = i + 1; j <= n; j++)
            if (x[i] > x[j])
                y[j]++;
            else if (x[i] < x[j])
                y[i]++;
    for (i = 1; i <= n; i++)
        printf("%d ", y[i]);
    cout << endl;
    return 0;
}

1. 把第 12 行与第 14 行互换位置，结果不会改变。()

{{ select(16) }}

• 正确
• 错误

2. 第 13 行把 if(x[i] < x[j]) 删掉效果一样。()

{{ select(17) }}

• 正确
• 错误

3. 数组 y[i] 中存的是 x[i] 在数列中从大到小的次序。()

{{ select(18) }}

• 正确
• 错误

4. 第 10 行把 i + 1 改成 1 ，数组 y 每个元素的值增加 1 倍。()

{{ select(19) }}

• 正确
• 错误

5. 此程序如果 n 输入 4 ，然后输入 2 4 1 3 ，输出结果是( )。

{{ select(20) }}

• 4 3 2 1
• 1 2 3 4
• 2 0 3 1
• 1 3 0 2

6. 此程序的时间复杂度是( )

{{ select(21) }}

• $O(\text {log }n)$
• $O(n^2)$
• $O(n\text { log }n)$
• $O(n)$

第二题

#include<iostream>
#include<cstdio>
using namespace std;
int j, i, m;
int a[10];
int main() {
    for (i = 2; i <= 6; i++)
        a[i] = i + 1;
    do {
        m = 2;
        for (i = 3; i <= 6; i++)
            if (a[m] > a[i]) m = i;
                a[m] = a[m] + m;
        m = 1;
        for (i = 2; i <= 5; i++)
            for (j = i + 1; j <= 6; j++)
                if (a[i] < a[j]) m = 0;
    } while (m == 0);
    printf("%d", a[2]);
    return 0;
}

1. 程序结束时，a[2] 的值一定是数组 a 中的最大值。( )

{{ select(22) }}

• 正确
• 错误

2. 第 18 行 m==0 成立时，数组 $a[i](2≤i≤6)$ 从大到小排序: ( )

{{ select(23) }}

• 正确
• 错误

3. 程序输出时，a 数组满足:对任意的 $2≤i<6$ ，有 $a[i] > a[i+1]$ 。( )

{{ select(24) }}

• 正确
• 错误

4. 删除第 14 行代码 m=1 程序结果会发生改变。( )

{{ select(25) }}

• 正确
• 错误

5. 程序的输出结果为( )

{{ select(26) }}

• 58
• 61
• 59
• 60

6. 第 17 行 if (a[i] < a[j]) 执行了多少次( )。

{{ select(27) }}

• 800
• 360
• 10
• 30

第三题

#include<bits/stdc++.h>
using namespace std;
int a[6];
int change(int a) {
    a++;
}
int change1(int & a) {
    a++;
}
int main() {
    int c = 1;
    for (int i = 1; i <= 5; i++) a[i] = i * 3;
    int * b = & a[1];
    change( * b);
    cout << * b << endl;
    cout << a[1] << endl;
    * b++;
    cout << * b << endl;
    cout << a[1] << endl;
    change1( * b);
    cout << * b << endl;
    cout << a[1] << endl;
    * b = c;
    change(c);
    cout << * b << endl;
    cout << c << endl;
    change1(c);
    cout << * b << endl;
    cout << c << endl;
    return 0;
}

1. 将第 11 行中 int 换为 long long 后程序依然能通过编译。( )

{{ select(28) }}

• 正确
• 错误

2. change 与 change1 两个函数等价。( )

{{ select(29) }}

• 正确
• 错误

3. 将第 23 行换为 b = &c; 输出值不变。( )

{{ select(30) }}

• 正确
• 错误

4. 将第 13 行 int * b = & a[1]; 换为 int *b=a+1; 输出值不变。( )

{{ select(31) }}

• 正确
• 错误

5. 输出结果的最大值是。( )

{{ select(32) }}

• 6
• 4
• 7
• 5

6. 输出结果的乘积是。( )

{{ select(33) }}

• 13608
• 11520
• 5760
• 6804

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

第一题

小 C 到商店购物，她只带了 $SW$ 元钱。有 $n$ 件商品，第 $i$ 件商品的价格为 $w_i$ 元，小 C 对它的满意度为 $v_i$ 。小 C 想要知道，用自己仅有的 $SW$ 元钱，能买到的所有商品的满意度之和最大是多少。 数据保证 $1≤n,w_i,v_i≤100,1≤SW≤10000$

#include <iostream>
using namespace std;

const int INF = 0x3f3f3f3f;

int n, SW, W[105], V[105], Dp[___(1)___];

int main(){
    cin >> n >> SW;
    for (int i = 1; i <= n; i++)
    cin >> W[i] >> V[i];
    for (int i = 1; i <= SW; i++)
        Dp[i] = ___(2)___;
    for (int i = 1; i <= n; i++)
        for (___(3)___)
            Dp[j] = max(Dp[j], ___(4)___);
    int ans = 0;
    for (int i = 1; i <= SW; i++)
        ___(5)___;
    cout << ans << "\n";
    return 0;
}

1. (1) 处应填（）

{{ select(34) }}

• 100
• 105
• 10000
• 10005

2. (2) 处应填（）

{{ select(35) }}

• INF
• 0
• -1
• 1

3. (3) 处应填（）

{{ select(36) }}

• int j = SW; j >= W[i]; j--
• int j = W[i]; j <= SW; j++
• int j = 1; j <= n; j++
• int j = n; j >= 1; j--

4. (4) 处应填（）

{{ select(37) }}

• Dp[i - W[j]] + V[j]
• Dp[i - V[j]] + W[j]
• Dp[i - W[i]] + V[i]
• Dp[i - V[i]] + W[i]

5. (5) 处应填（）

{{ select(38) }}

• ans = max(ans, Dp[i])
• ans = min(ans, Dp[i])
• ans = ans + Dp[i]
• ans = ans - Dp[i]

第二题

（链表反转）单向链表反转是一道经典算法问题，比如有一个链表是这样的 $1−>2−>3−>4−>5$，反转后成为 $5−>4−>3−>2−>1$ 。现给定如下链表节点的定义：

struct LinkNode {
    int value;
    LinkNode* next;
};

非递归实现：

LinkNode* Reverse(LinkNode* header) {
    if (header == NULL || header->next == NULL) {
        return header;
    }
    LinkNode *pre = header, *cur = header->next;
    pre->next = NULL;
    while (cur != NULL) {
        LinkNode* next = ___(1)___;
        ___(2)___ = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

递归实现：

LinkNode* Reverse(LinkNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    LinkNode* newhead = ___(3)___;
    ___(4)___ = head;
    head->next = ___(5)___;
    return newhead;
}

1. (1) 中应填

{{ select(39) }}

• pre -> next
• cur -> next
• header -> next
• NULL

2. (2) 中应填

{{ select(40) }}

• pre -> next
• cur -> next
• header -> next
• NULL

3. (3) 中应填

{{ select(41) }}

• ReverseList(head)
• ReverseList(pre)
• ReverseList(cur)
• ReverseList(head -> next)

4. (4) 中应填

{{ select(42) }}

• pre -> next -> next
• cur -> next -> next
• head -> next -> next
• NULL

5. (5) 中应填

{{ select(43) }}

• pre -> next
• cur -> next
• head -> next
• NULL