普及组初赛模拟27

一、单选题

1. 计算机存储和处理数据的基本单位是（ ） {{ select(1) }}

• $Bit$
• $Byte$
• $KB$
• $GB$

2. 用两个字节最多能编出多少个不同的码（ ） {{ select(2) }}

• 256
• 65536
• 32768
• 2147483648

3. 具有18个元素的有序数组，其中第一个元素下标为1, 现进行二分查找, 则查找到下标为3的元素, 比较序列的下标依次为（ ） {{ select(3) }}

• 1, 2, 3
• 9, 5, 2, 3
• 9, 5, 3
• 9, 4, 2, 3

4. 设二叉树的后序序列为 $DBFEGCA$, 中序序列为 $DBAFEGG$, 则它的先序遍历为（ ） {{ select(4) }}

• $ABCDFEG$
• $ABDOFEG$
• $ABCDEFG$
• $ABDCEFG$

5. 设输入序列为1, 2, 3, 4, 5, 6, 则通过栈的作用后可以得到的输出序列为（ ） {{ select(5) }}

• 5, 3, 4, 6, 1, 2
• 3, 2, 5, 6, 4, 1
• 3, 1, 2, 5, 4, 6
• 1, 5, 4, 6, 2, 3

6. 权值为 $\{1, 2, 6, 8\}$ 的四个点构成的哈夫曼树的带权路径长度是（ ） {{ select(6) }}

• 18
• 28
• 19
• 29

7. 设有一组初始记录关键字序列为 $\{34, 76, 45, 18, 26, 54, 92\}$, 则由这组记录关键字生成的二叉排序树的深度为（ ） {{ select(7) }}

• 4
• 5
• 6
• 7

8. 在含有n个顶点和e条边的无向图的邻接矩阵中, 零元素的个数为（ ） {{ select(8) }}

• e
• 2e
• $n^2 - e$
• $n^2 - 2e$

9. 设带有头结点的单向循环链表的头指针为变量为 $head$, 则判断该循环链表为空的条件是（ ） {{ select(9) }}

• head == 0
• head -> next == 0
• head -> next == head
• head != 0

10. 现安排甲、乙、丙、丁、戊5名同学参加世博会志愿者服务活动，每人从事翻译、导游、礼仪、司机四项工作之一，每项工作至少有一人参加。甲乙不会开车但能从事其它三项工作，丙、丁、戊都能胜任四项工作，则不同安排工作的方案种数是（ ） {{ select(10) }}

• 152
• 126
• 90
• 54

11. 假设以行优先顺序存储三位数组 $R[6][9][6]$，其中元素 $R[0][0][0]$ 的地址为2100，每个元素占4个存储单元，则存储地址为2832的元素为（ ） {{ select(11) }}

• $R[3][3][2]$
• $R[3][3][3]$
• $R[4][3][4]$
• $R[4][3][3]$

12. 全局变量 cnt 初始值为0，则计算 $fibo(4)$ 后，cnt 的值为（ ）

int fibo(int n)
{
    cnt++;
    if(n == 1 || n == 2) return 1;
    else return fibo(n - 1) + fibo(n - 2);
}

{{ select(12) }}

• 4
• 5
• 6
• 7

13. 某台阶共有10级，每一步可以跨一级、两级或三级，那么恰好6步上完台阶的方法有多少（ ） {{ select(13) }}

• 120
• 90
• 78
• 144

14. 已知图的邻接矩阵如下，从顶点0出发按深度优先搜索遍历的结点序列为（ ） {{ select(14) }}

• 0 1 3 6 5 4 2
• 0 1 3 4 2 5 6
• 0 1 3 4 2 6 5
• 0 2 4 3 1 5 6

15. 由同一组关键字集合构成的各种二叉排序树，下列说法正确的是（ ） {{ select(15) }}

• 其形态不一定相同，但平均查找长度相同
• 其形态均相同，平均查找长度也相同
• 其形态均相同，但平均查找长度不相同
• 其形态不一定相同，平均查找长度也不一定相同

二、程序阅读

程序1

#include<bits/stdc++.h>
using namespace std;

int main(){
    int ax1, ayl, ax2, ay2;
    int bx1, by1, bx2, by2;
    cin >> ax1 >> ayl >> ax2 >> ay2;
    cin >> bx1 >> by1 >> bx2 >> by2;
    int area1 = (ax2 - ax1) * (ay2 - ayl);
    int area2 = (bx2 - bx1) * (by2 - by1);
    int width = min(ax2, bx2) - max(ax1, bx1)
    width = width > 0 ? width : 0;
    int height = min(ay2, by2) - max(ay1, by1);
    height = height > 0 ? height : 0;
    cout << area1 + area2 - width * height;
    return 0;
}

1. 程序输出一定为大于0的正整数（ ） {{ select(16) }}

• 正确
• 错误

2. 若输入为"0 0 1 1 0 0 1 1"，输出为"1"（ ） {{ select(17) }}

• 正确
• 错误

3. 计算过程中不会超出int范围。（ ） {{ select(18) }}

• 正确
• 错误

4. 若输入为"-3 0 3 4 0 -1 9 2"，则输出为（ ） {{ select(19) }}

• 51
• 55
• 45
• 42

5. 对于该算法的描述，最准确的是（ ） {{ select(20) }}

• 计算两个矩形的面积
• 计算两个矩形的体积
• 计算两个矩形覆盖的面积
• 计算两个矩形相交的面积

6. 若输入为"-10 -20 100 200 0 10 20 30"，则输出为（ ） {{ select(21) }}

• 24200
• 25200
• 20600
• 22600

程序2

#include<bits/stdc++.h>
using namespace std;

const int values[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
const char* symbols[] = {"N", "CH", "D", "CD", "C", "XC", "L", "XL", "X", "DK", "V", "IV", "I"};

int main(){
    int num;
    cin >> num;
    string s = "";
    for(int i = 0;i < 13;i++){
        while(num >= values[i]){
            num -= values[i];
            s += symbols[i];
        }
        if(num == 0){
            break;
        }
    }
    cout << s;
}

1. 程序的输出一定为长度大于等于 1 的字符串（ ） {{ select(22) }}

• 正确
• 错误

2. 将第 11 行的 i < 13 改为 i < 3，程序输出的结果一定为错误结果。（ ） {{ select(23) }}

• 正确
• 错误

3. 当输入为"1900"时，输出为"MCM"。（ ） {{ select(24) }}

• 正确
• 错误

4. 该算法第 12 行的 $while$ 循环，在单次 $for$ 循环中最多循环（ ）次 {{ select(25) }}

• 2
• 3
• 4
• 5

5. 当输入为"2145"时,输出为（ ） {{ select(26) }}

• MMCLXL
• MMCXLV
• MMCXLVI
• MMXLV

6. 当输入为"3999"时,输出为（ ） {{ select(27) }}

• MMMCMLXXXIX
• MMMCMLXXX
• MMCMXCIX
• MMMCMXCIX

程序3

#include<bits/stdc++.h>
using namespace std;

int dis[10010];
int main(){
    int x,y;
    cin >> x >> y;
    for(int i = 0;i < 10010;i ++)
        dis[i] = INT_MAX;
    dis[x] = 0;
    queue<int> q;
    q.push(x);
    while(!q.empty()){
        int s = q.front();
        q.pop();
        if(s == y){
            cout << dis[y] << endl;
            break;
        }
        if(s+1 < 10010 && dis[s+1] == INT_MAX){
            dis[s+1] = dis[s] + 1;
            q.push(s+1);
        }
        if(s-1 >= 0 && dis[s-1] == INT_MAX){
            dis[s-1] = dis[s] + 1;
            q.push(s-1);
        }
        if(s*2 < 10010 && dis[s*2] == INT_MAX){
            dis[s*2] = dis[s] + 1;
            q.push(s*2);
        }
    }
    return 0;
}

1. 输出的数字同样为一个不超过10000的正整数。（） {{ select(28) }}

• 正确
• 错误

2. 当输入的数字为"1 5"时，队列 $q$ 中同时最多存在的数字为3个。（） {{ select(29) }}

• 正确
• 错误

3. 输出一定大于等于输入数字的差的绝对值（） {{ select(30) }}

• 正确
• 错误

4. 当两个输入的数字相等时，输出一定为0。（） {{ select(31) }}

• 正确
• 错误

5. 当输入的数字为"7 20"，输出为（） {{ select(32) }}

• 5
• 4
• 6
• 10

6. 当输入的数字为"1 100",输出为（ ） {{ select(33) }}

• 100
• 7
• 8
• 10

三、程序完善

程序1

（循环数判断）判断一个数字是否为循环数 循环数满足：从最高位开始，向右数"该数位"个数字（如果到了最右边就从最左边开始继续数），会停止在一个新的数位并且是一个新的数字，重复这样做，最后经过每个数字一次后能够回到起点。 如果你的数字经过每一个数字后没有回到起点（最高位数）则不是循环数 如果你的数字没有经过每一个数字就已经发生重复，则不是循环数 例如，对于数字3126，从最高位3开始，向右数3个数字到达6，从6开始向右数6个数字（此时会像一个圆环一样继续从3开始数），到达1，此时向右输一个数字到达2，此时向右数2个数字回到起点3。所以3126是一个循环数。

#include<bits/stdc++.h>
using namespace std;

int nums[200], nums_rev[200];
bool vis[200];

int main(){
    int x;
    cin >> x;
    int cnt = 0;
    while(x > 0){
        nums[(1)] = x % 10;
        x /= 10;
    }
    for(int i = 1; i <= cnt; ++i) nums_rev[i] = nums[cnt - i -1];
    bool flag = true;
    int pos = 1;
    for(int i = 1; i <= cnt; ++i){
        if((2)) || nums_rev[pos] == 0){
            flag = false;
            break;
        }
        (3);
        pos = (4);
        if(pos == 0) pos = cnt;
    }
    if((5)) flag = false;
    if(flag) cout << "YES";
    else cout << "NO";
    return 0;
}

1. (1) 处应当填写（） {{ select(34) }}

• cnt
• cnt++)
• ++ cnt
• cnt+1

2. (2) 处应当填写（） {{ select(35) }}

• vis[nums_rev[i]]
• vis[nums_rev[pos]]
• lvis[nums_rev[pos]]
• vis[nums[pos]]

3. (3) 处应当填写（） {{ select(36) }}

• vis[nums_rev[pos]] = true;
• vis[i];
• vis[nums_rev[i]] = true;
• vis[pos] = true;

4. (4) 处应当填写（） {{ select(37) }}

• (pos + nums_rev[i]) % cnt
• (pos + nums_rev[pos]) % cnt + 1
• (pos + nums[pos]) % cnt
• (pos + nums_rev[pos]) % cnt

5. (5) 处应当填写（） {{ select(38) }}

• lvis[1]
• pos != 1
• pos != n
• pos == 1

程序2

(石子合并) 一条直线上有 $N$ 堆石子，现要将石子有次序的合并成一堆，规定每次只能选相邻的 2 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。 思路：使用 $dp[i][j]$ 表示下标位置 i 到 j 所有元素合并能获得最大得分 考虑区间的拆分进行状态转移

#include<bits/stdc++.h>
using namespace std;

int a[1024], pre[1024];
int dp[1024][1024];
int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        (1);
    }
    
    int i, j, k, len;
    for((2)){
        for((3)){
            j = i + len - 1;
            for(k = i; k < j && k <= n; k++)
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + (4));
        }
    }
    cout << (5);
}

1. (1) 处应当填写（） {{ select(39) }}

• pre[i] = a[i]
• pre[i] = pre[i-1] + a[i]
• pre[i] += a[i]
• pre[i] = a[i-1] + a[i]

2. (2) 处应当填写（） {{ select(40) }}

• i = n; i >= 1; i--;
• i = 1; i <= n; i++
• len = 1; len <= n; len++
• len = n; len >= 1; len --

3. (3) 处应当填写（） {{ select(41) }}

• i = n; i >= 1; i--;
• i = 1; i <= n; i++
• len = 1; len <= n; len++
• len = n; len >= 1; len --

4. (4) 处应当填写（） {{ select(42) }}

• pre[j] - pre[i-1]
• a[k] + a[k+1]
• pre[k+1]
• pre[j] - pre[i]

5. (5) 处应当填写（） {{ select(43) }}

• dp[n][1]
• dp[n][n]
• dp[1][n]
• dp[1][1]