普及组初赛模拟26

一、单选题

1. 以下关于编程语言的选项中，正确的是（ ） {{ select(1) }}

• 操作系统控制和管理软件资源，需要直接操作机器，所以需要用机器语言编写
• 同样一段高级语言程序通过不同的编译器可能产生不同的可执行程序
• $C + 1$ 是一种纯面向对象语言
• 解释执行的语言只能选择一个解释器

2. 如果在某个进制下等式 $7 * 7 = 41$ 成立，那么在该进制下 $12 * 12 = ( )$ 也成立。 {{ select(2) }}

• 100
• 144
• 164
• 196

3. 一个包含 $n$ 个分支结点（非叶结点）的非空满 $k$ 树，$k > 1$，它的叶结点数目为：（ ） {{ select(3) }}

• $n^k + 1$
• $n^k - 1$
• $(k + 1)n - 1$
• $(k - 1)n + 1$

4. 已知一个有向图的边集为 $\{ < a, b > , < a, c > , < a, d > , < b, d > , < b, e > , < d, e > \}$，则由该图产生的一种可能的拓扑序列为（ ） {{ select(4) }}

• $a, b, c, d, e$
• $a, c, d, e, b$
• $a, c, b, e, d$
• $a, c, d, b, e$

5. 二叉树是非线性数据结构，所以（ ） {{ select(5) }}

• 它不能用顺序存储结构存储；
• 它不能用链式存储结构存储；
• 顺序存储结构和链式存储结构都能存储
• 顺序存储结构和链式存储结构都不能使用

6. 计算机能直接执行的指令包括两部分，它们是（ ） {{ select(6) }}

• 源操作数与目标操作数
• 操作码与操作数
• ASCII 码与汉字代码
• 数字与字符

7. 若已知一棵二叉树的前序序列是 BEFCGDH，中序序列是 FEBGCHD，则它的后序序列必是 ______。 {{ select(7) }}

• $FEGHDBC$
• $EFGHDBC$
• $B.FEGHDCB$
• $DFEGHDCB$

8. 计算机系统总线上传送的信号有（ ） {{ select(8) }}

• 地址有信号与控制信号
• 数据信号、控制信号与地址信号
• 控制信号与数据信号
• 数据信号与地址信号

9. 在长度为 $n$ 的顺序存储的线性表中，删除第 $i$ 个元素（$1 \leq i \leq n$）时，需要从前向后依次前移（ ）个元素。 {{ select(9) }}

• $n - i$
• $n - i + 1$
• $n - i - 1$
• $n - i$

10. 栈 S 最多能容纳 4 个元素。现有 6 个元素按 A, B, C, D, E, F 的顺序进栈，问下列哪一个序列是可能的出栈序列（ ） {{ select(10) }}

• $E, D, C, B, A, F$
• $B, C, E, F, A, D$
• $C, E, B, D, A, F$
• $A, D, F, E, C, B$

11. 在顺序表（2, 5, 7, 10, 14, 15, 18, 23, 35, 41, 52）中，用二分法查找关键码值 12，所需的关键码比较次数为（ ） {{ select(11) }}

• 2
• 3
• 4
• 5

12. 设有字符序列 $(Q,H,C,Y,P,A,M,S,R,D,F,X)$，问新序列 $(F,H,C,D,P,A,M,Q,R,S,Y,X)$ 是下列哪个排序算法一越扫描的结果（ ） {{ select(12) }}

• 冒泡排序
• 初始步长为4的希尔排序
• 二路归并排序
• 以第一元素为分界元素的快速排序

13. 已知图中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则 $G$ 的边数为（ ）。 {{ select(13) }}

• 13
• 14
• 15
• 16

14. 设完全图 $G$ 有n个结点，m条边，则当（ ）时，$G$ 中存在欧拉回路。 {{ select(14) }}

• m为奇数
• m为偶数
• n为奇数
• n为偶数

15. 孙某和张某是考古学家老李的学生。有一天，老李拿了一件古物来考验两人，两人都无法验证出来这件古物试谁的。老李告诉了孙某拥有者的姓，告诉张某拥有者的名，并且在纸条上写下以下几个人的名字，问他们知道谁才是拥有者？纸条上的名字有：沈万三、岳飞、岳云、张飞、张良、张鹏、赵括、赵云、赵鹏、沈括。孙某说：如果我不知道的话，张某肯定也不知道。张某说：刚才我不知道，听孙某一说，我现在知道了。孙某说：哦，那我也知道了。请问：那件古物是谁的（ ）？ {{ select(15) }}

• 赵括
• 岳飞
• 岳云
• 赵鹏

16. 在等腰直角三角形 $ABC$ 中，过直角顶点 $C$ 在 $\angle ACB$ 内部任作一射线 $CM$，与线段 $AB$ 交于点 $M$，求 $AM < AC$ 的概率。（ ） {{ select(16) }}

• $1/sqrt(2)$
• 1/2
• $sqrt(2)/4$
• 3/4

17. 若 $A = False, B = True, C = True, D = False$，则下列逻辑运算真的有（ ） {{ select(17) }}

• $(A \land B)V(C \land D)$
• $((A \land \neg B)VD) \land B$
• $((\neg A \rightarrow \neg B) \land C)VD$
• $\neg A \land (\neg D \rightarrow \neg C) \rightarrow \neg B$

18. 在整数的补码表示法中，以下说法正确的是（ ）。 {{ select(18) }}

• 只有负整数的编码最高位为1
• 在编码的位数确定后，所能表示的最小整数和最大整数的绝对值相同
• 整数0有正零和负零两个编码
• 两个用补码表示的数相加时，如果在最高位产生进位，则表示运算溢出

19. 在双向链表p结点之前插入结点s的操作，正确的是（ ）： {{ select(19) }}

• ①②③
• ②③④
• ③④②
• ④③②

20. 显示屏有一排7个小孔，每个小孔可显示0或1，若每次显示其中3个孔，但相邻的两个孔不能同时显示，则该显示屏能显示信号的种数共有（ ） {{ select(20) }}

• 10
• 48
• 60
• 80

二、程序阅读题

1. 以下程序的输出结果是否正确，正确填 $T$，错误填 $P$。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int s, i;
    for (s = 0, i = 1; i < 3; i++, s += i);
    cout << i << s << endl;
}

输出： 1 0 2 2 3 5 {{ select(21) }}

• 正确
• 错误

2. 以下程序的输出结果是（ ）

#include <bits/stdc++.h>
using namespace std;
int main()
{
    char st[20] = "hello\0\t\";
    printf("%d %d \n", strlen(st), sizeof(st));
}

{{ select(22) }}

• 12 20
• 5 20
• 20 20
• 5 5

3. 以下程序的输出结果是（ ）

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a, k;
    a = 5;
    k = 8;
    char l = 'a';
    while (a > 0)
    {
        switch (l += a--)
        {
        case 'j':
        case 'l':
            1 == a;
        case 'f':
            a==; 
            continue;
        case 'm':
        case 'p':
            1++; 
            break;
        default:
            k++; 
        case 'o':
            k == 2;
            continue;
        }
        k++; 
        1--; 
    }
    cout << 1 << k << endl;
    return 0;
}

{{ select(23) }}

• r6
• l6
• k8
• i12

4. 以下程序的输出结果是否是否正确，正确填 $T$，错误填 $F$。

#include <iostream>
using namespace std;
void pr(int A, int B)
{
    cout << A << " " << B << " ";
}
void first(int A, int B)
{
    A += 1;
    B += 2;
    pr(A, B);
}
void second(int &A, int &B)
{
    A += 3;
    B += 4;
    pr(A, B);
}
void third(int A, int &B)
{
    A *= 2;
    B *= 3;
    pr(A, B);
}
int main()
{
    int x = 1, y = 1;
    pr(x, y);
    first(2, 3 * 2);
    first(x, y);
    pr(x, y);
    second(x, y);
    pr(x, y);
    third(x, y);
    pr(x, y);
    return 0;
}

输出: 1 1, 3 8, 2 3, 1 1, 4 5, 4 5, 8 15, 4 15, {{ select(24) }}

• 正确
• 错误

5. 以下程序的输出结果是（ ）

#include <iostream>
using namespace std;
int f(int n, int k)
{
    if (n == k || k = 0)
        return 1;
    else
        return f(n - 1, k) + f(n - 1, k - 1);
}
int main()
{
    int n, k, m;
    cin >> n >> k;
    cout << f(n, k);
    return 0;
}

输入: 20 15 {{ select(25) }}

• 4845
• 12306
• 15504
• 38760

三、完善程序

第一题

在语句中选出正确的选项填入相应的空中，语句可能重复被选多次。 设有n个人依次围成一圈，从第1个人开始报数，数到第m个人出列，然后从出列的下一个人开始报数， 数到第m个人又出列，⋯，如此反复到所有的人全部出列为止。设n个人的编号分别为1, 2, ⋯, n, 打印 出出列的顺序。

#include <iostream>
#include <iomanip>
using namespace std;
const int N = 14, M = 4;
int a[N + 1], i, j, k, p;
int main()
{
    int i = 1;
    while (i < N)
        a[i] = (1), (2);
    a[N] = 1;
    j = (3);
    (4);
    p = 0;
    do
    {
        (5);
        k++;
        if (k == M)
        {
            cout << setw(4) << a[j];
            p++;
            (6); //(此空与a[j]相关)
            (7);
        }
    } while (p != (8));
    return 0;
}

1. (1)填（） {{ select(26) }}

• k = 1
• k = N
• N
• M
• i + 1
• i ++
• i
• j = a[j]
• a[j] = a[a[j]]
• a[j] = j
• a[a[j] = a[j]]

2. (2)填（） {{ select(27) }}

• k = 1
• k = N
• N
• M
• i + 1
• i ++
• i
• j = a[j]
• a[j] = a[a[j]]
• a[j] = j
• a[a[j] = a[j]]

3. (3)填（） {{ select(28) }}

• k = 1
• k = N
• N
• M
• i + 1
• i ++
• i
• j = a[j]
• a[j] = a[a[j]]
• a[j] = j
• a[a[j] = a[j]]

4. (4)填（） {{ select(29) }}

• k = 1
• k = N
• N
• M
• i + 1
• i ++
• i
• j = a[j]
• a[j] = a[a[j]]
• a[j] = j
• a[a[j] = a[j]]

5. (5)填（） {{ select(30) }}

• k = 1
• k = N
• N
• M
• i + 1
• i ++
• i
• j = a[j]
• a[j] = a[a[j]]
• a[j] = j
• a[a[j] = a[j]]

6. (6)填（） {{ select(31) }}

• k = 1
• k = N
• N
• M
• i + 1
• i ++
• i
• j = a[j]
• a[j] = a[a[j]]
• a[j] = j
• a[a[j] = a[j]]

7. (7)填（） {{ select(32) }}

• k = 1
• k = N
• N
• M
• i + 1
• i ++
• i
• j = a[j]
• a[j] = a[a[j]]
• a[j] = j
• a[a[j] = a[j]]

8. (8)填（） {{ select(33) }}

• k = 1
• k = N
• N
• M
• i + 1
• i ++
• i
• j = a[j]
• a[j] = a[a[j]]
• a[j] = j
• a[a[j] = a[j]]

第二题

给出n 件物品的价值和体积，问在总体积不超过v 时的第k 大价值。 输入格式： 第一行为三个整数n,v 和k，第二行n 个整数表示这n 件物品的价值，第三行n 个整数表示这n 件物品的 体积 N ≤100,V ≤1000,K ≤30，价值≤1000, 体积≤1000 输出格式： 输出总体积不超过v 的第k 大价值 样例输入： 5 10 2 1 2 3 4 5 5 4 3 2 1 样例输出： 12

#include <stdio.h>
#include <string.h>
int t, n, v, k, dp[1001][35], value[101], cost[101];
void Kth()
{
    int t1[35], t2[35], res1, res2, res;
    memset(dp, 0, sizeof(dp)); // 初始化
    for (int i = 1; i <= n; i++) // 01 背包
        for (int j = v; j >= cost[i]; j--) 
        {
            for (int l = 1; l <= k; l++) 
            {
                t1[l] = (9) + value[i];
                t2[l] = (10);
            }
            res1 = res2 = res = (11);
            t1[k + 1] = t2[k + 1] = -1;
            while (res <= k && (res1 <= k || res2 <= k))
            {
                if ((12))
                    dp[j][res] = t1[res1++];
                else
                    dp[j][res] = t2[res2++];
                if ((13) != (14))
                    res++;
            }
        }
}
int main()
{
    scanf("%d%d%d", &n, &v, &k);
    for (int i = 1; i <= n; i++) 
        scanf("%d", &value[i]);
    for (int i = 1; i <= n; i++) 
        scanf("%d", &cost[i]);
    Kth();
    printf("%d", (15));
    return 0;
}

9. (9) 填（ ） {{ select(34) }}

• $dp[v - \cos t[i]] [l]$
• $dp[j - \cos t[i]] [l]$
• $dp[v - \cos t[l]] [i]$
• $dp[j - \cos t[l]] [i]$

10. (10) 填（ ） {{ select(35) }}

• $\cos t[i]$
• $\cos t[j]$
• $dp[j] [l]$
• $dp[i] [l]$

11. (11) 填（ ） {{ select(36) }}

• $-1$
• 0
• 1
• 1001

12. (12) 填（ ） {{ select(37) }}

• $res1 < res2$
• $res1 > res2$
• $t1[res1] < t2[res2]$
• $t1[res1] > t2[res2]$

13. (13) 填（ ） {{ select(38) }}

• $dp[j] [res-1]$
• $dp[i] [res-1]$
• $dp[i] [res+1]$
• $dp[j] [res+1]$

14. (14) 填（ ） {{ select(39) }}

• $dp[i] [res]$
• $dp[j] [res]$
• $dp[l] [res]$
• $dp[l] [res+1]$

15. (15) 填（ ） {{ select(40) }}

• $dp[v] [k-1]$
• $dp[n] [k-1]$
• $dp[v] [k]$
• $dp[n] [k]$