23年阅读程序和完善程序截取 【满分90分】

(1)

#include <iostream>
#include <cmath>
using namespace std;

double f(double a, double b, double c) {
    double s = (a + b + c) / 2;
    return sqrt(s * (s - a) * (s - b) * (s - c));
}

int main() {
    cout.flags(ios::fixed);
    cout.precision(4);

    int a, b, c;
    cin >> a >> b >> c;
    cout << f(a, b, c) << endl;
    return 0;
}

1. （2分）当输入为“2 2 2”时，输出为“1.7321”（） {{ select(1) }}

• T
• F

2. （2分）将第 7 行中的“(s - b) * (s - c)”改为“(s - c) * (s - b)”不会影响程序运行的结果（） {{ select(2) }}

• T
• F

3. （2分）程序总是输出四位小数（） {{ select(3) }}

• T
• F

4. 当输入为“3 4 5”时，输出为（） {{ select(4) }}

• “6.0000”
• “12.0000”
• “24.0000”
• “30.0000”

5. 当输入为“5 12 13”时，输出为（） {{ select(5) }}

• “24.0000”
• “30.0000”
• “60.0000”
• “120.0000”

(2)

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int f(string x,string y){
    int m=x.size();
    int n=y.size();
    vector<vector<int>>v(m+1,vector<int>(n+1,0));
    for(int i=1;i<=m;i++){
       for(int j=1;j<=n;j++){
            if(x[i-1]==y[j-1]){
                v[i][j]=v[i-1][j-1]+1;
            }else{
                v[i][j]=max(v[i-1][j],v[i][j-1]);
            }
        }
    }
    return v[m][n];
}
bool g(string x,string y){
    if(x.size() != y.size()){
        return false;
    }
    return f(x+x,y)==y.size();
}
int main(){
    string x,y;
    cin>>x>>y;
    cout<<g(x,y)<<endl;
    return 0;
}

6. f 函数的返回值小于等于 min(n,m)。（） {{ select(6) }}

• T
• F

7. f 函数的返回值等于两个输入字符串的最长公共子串的长度。（） {{ select(7) }}

• T
• F

8. 当输入两个完全相同的字符串时，g 函数的返回值总是true。（） {{ select(8) }}

• T
• F

9. 将第 19 行中的“v[m][n]”替换为“v[n][m]”，那么该程序（） {{ select(9) }}

• 行为不变
• 只会改变输出
• 一定非正常退出
• 可能非正常退出

10. 当输入为“csp-j p-jcs”时，输出为（） {{ select(10) }}

• “0”
• “1”
• “T”
• “F”

11. 当输入为“csppsc spsccp”时，输出为（） {{ select(11) }}

• “T”
• “F”
• “0”
• “1”

(3)

#include <iostream>
#include <cmath>
using namespace std;

int solve1(int n) {
    return n * n;
}

int solve2(int n) {
    int sum = 0;
    for (int i = 1; i <= sqrt(n); i++) {
        if(n % i == 0) {
            if(n/i == i) {
                sum += i*i;
            } else {
               sum += i*i + (n/i)*(n/i);
            }
         }
    }
    return sum;
}

int main() {
    int n;
    cin >> n;
    cout << solve2(solve1(n)) << " " << solve1(solve2(n)) << endl;
    return 0;
}

假设输入的 n 是绝对值不超过 1000 的整数，完成下面的判断题和单选题：

12. 如果输入的 n 为正整数，solve2 函数的作用是计算 n 所有因子的平方和。（） {{ select(12) }}

• T
• F

13. 第 13-14 行的作用是避免 n 的平方根因子 i（或n/i）进入第 16 行而被计算两次。（） {{ select(13) }}

• T
• F

14. 如果输入的 n 为质数，solve2(n) 的返回值为n²+1。（） {{ select(14) }}

• T
• F

15. （4分）如果输入的 n 为质数 p 的平方，那么solve2（n）的返回值为（） {{ select(15) }}

• p²+p+1
• n²+n+1
• n²+1
• p⁴+2p²+1

16. 当输入为正整数时，第一项减去第二项的差值一定（） {{ select(16) }}

• 大于0
• 大于等于0且不一定大于0
• 小于0
• 小于等于0且不一定小于0

17. 当输入为“5”时，输出为（） {{ select(17) }}

• “651 625”
• “650 729”
• “651 676”
• “652 625”

三，完善程序（单选题，每小题 3 分）

(1) （寻找被移除的元素）问题：原有长度为 n+1，公差为 1 的等差升序数列，将数列输入到程序的数组时移除了一个元素，导致长度为 n 的升序数组可能不再连续，除非被移除的是第一个或者最后一个元素。需要在数组不连续时，找出被移除的元素。

试补全程序

#include <iostream>
#include <vector>

using namespace std;
int find_missing(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == mid + ①) {
            ②;
        } else {
           ③;
        }
     }
     return ④;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++)cin >> nums[i];
    int missing_number = find_missing(nums);
    if (missing_number == ⑤) {
        cout << "Sequence is consecutive" << endl;
    } else {
        cout << "Missing number is " << missing_number << endl;
    }
    return 0;
}

18. ①处应填（） {{ select(18) }}

• 1
• nums[0]
• right
• left

19. ②处应填（） {{ select(19) }}

• left = mid + 1
• right = mid - 1
• right = mid
• left = mid

20. ③处应填（） {{ select(20) }}

• left = mid + 1
• right = mid - 1
• right = mid
• left = mid

21. ④处应填（） {{ select(21) }}

• left + nums[0]
• right + nums[0]
• mid + nums[0]
• right + 1

22. ⑤处应填（） {{ select(22) }}

• nums[0]+n
• nums[0]+n-1
• nums[0]+n+1
• nums[n-1]

(2) (编辑距离)给定两个字符串，每次操作可以删除（Delete），插入（Insert），替换（Replace）一个字符，求将第一个字符串转换为第二个字符串所需要的最少操作次数。

试补全动态规划算法。

#include <iostream> 
#include <string> 
#include <vector> 
using namespace std; 

int min(int x, int y, int z) { 
    return min(min(x, y), z); 
} 

int edit_dist_dp(string str1, string str2) { 
    int m = str1.length(); 
    int n = str2.length(); 
    vector<vector<int>> dp(m + 1, vector<int>(n + 1)); 
    for (int i = 0; i <= m; i++) { 
        for (int j = 0; j <= n; j++) { 
            if (i == 0) 
                dp[i][j] = ①; 
            else if (j == 0) 
                dp[i][j] = ②; 
            else if (③) 
                dp[i][j] = ④; 
            else 
                dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], ⑤); 
         } 
     } 
    return dp[m][n]; 
} 

int main() { 
    string str1, str2; 
    cin >> str1 >> str2; 
    cout << "Mininum number of operation:" << edit_dist_dp(str1, str2) << endl; 
    return 0; 
}

23. ①处应填（） {{ select(23) }}

• j
• i
• m
• n

24. ②处应填（） {{ select(24) }}

• j
• i
• m
• n

25. ③处应填（） {{ select(25) }}

• str1[i - 1] == str2[j-1]
• str1[i] == str2[j]
• str1[i - 1] != str2[j - 1]
• str1[i] != str2[j]

26. ④处应填（） {{ select(26) }}

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

27. ⑤处应填（） {{ select(27) }}

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