二分查找 - 阅读程序（三）

题目描述

阅读以下程序，回答判断题（第 1-5 题，每题 10 分）和单选题（第 6-8 题，每题约 17 分）。

输入的只可能是小写字母。

#include<bits/stdc++.h>

using namespace std;

char last[101], ch;
int main(){
    int n, length = 0;
    scanf("%d", &n);
    for(int i = 0; i <= n; i++){
        cin >> ch;
        if(ch >= last[length]){
            last[++length] = ch;
        }else if(ch < last[1]){
            last[1] = ch;
        }else{
            int l = 1, r = length, mid;
            while(l < r - 1){
                mid = (l + r) / 2;
                if(last[mid] <= ch){
                    l = mid;
                }else r = mid;
            }
            last[r] = ch;
        }
    }
    printf("%d\n", length);
    return 0;
}

判断题

第 1 题 要使输出等于 n，输入的所有字符必须满足第 i 个字符 ASCII 整数值小于第 i+1 个字符的 ASCII 整数值（1 ≤ i ≤ n-1）。{{ select(1) }}

• 正确
• 错误

第 2 题 若输入字符个数超过 101 个，一定会发生数组下标溢出。{{ select(2) }}

• 正确
• 错误

第 3 题 若将第 18 行替换为 mid = l + ((r - l) >> 1)，程序运行结果不会改变。{{ select(3) }}

• 正确
• 错误

第 4 题 程序运行过程中，变量 r 的值可能会等于 n。{{ select(4) }}

• 正确
• 错误

第 5 题 如果第 11 行修改为 ch > last[length]，最终输出的结果可能会有 30。{{ select(5) }}

• 正确
• 错误

单选题

第 6 题 第 23 行 last[r] = ch 最多会运行（ ）次。{{ select(6) }}

• A. 1
• B. n-2
• C. n-1
• D. n

第 7 题 若输入 n = 100，且第 17 行的 while 循环运行了至少一次，那么输出结果不可能是（ ）{{ select(7) }}

• A. 2
• B. 3
• C. 98
• D. 100

第 8 题 若输入数据为 4 b c d a e，则输出是（ ）{{ select(8) }}

• A. 4
• B. 2
• C. 5
• D. 3