2022 算法设计与分析(北京科技大学) 最新满分章节测试答案

文章目录[隐藏]

01 算法概述与算法分析基础算法概述与算法分析基础测试
02 算法设计基础算法设计基础测试
03 算法设计策略——迭代法算法设计策略——迭代法测试
include <algorithm>
include <stdlib.h>
include <cmath>
- 04 算法设计策略——分治算法设计策略——分治
include <iostream> using namespace std; #define N 64 void GameTable(int k,int a[][N]) { int n=2; a[1][1]=1;a[1][2]=2; a[2][1]=2;a[2][2]=1; int i,j,t; for (t=1;t<k;t++) { int temp=n; n*=2; for (i=temp+1;i<=n;i++) for (j=1;j<=temp;j++) a[i][j]=a[i-temp][j]+temp; for (i=1;i<=temp;i++) for (j=temp+1;j<=n;j++) ① for (i=temp+1;i<=n;i++) for (j=temp+1;j<=n;j++) a[i][j]=a[i-temp][j-temp]; } cout<<“运动员编号\t”; for (i=1;i<n;i++) { cout<<“第”<<i<<“天\t”; } cout<<endl; for (i=1;i<=n;i++) { cout<<i<<“号运动员:\t”; for (j=2;j<=n;j++) cout<<a[i][j]<<‘\t’; if (j==n) cout<<n; cout<<endl; } } void main() { int a[N][N]; int k; cout<<“输入选手个数的次数：”; cin>>k; GameTable(k,a); }
- 07 算法设计策略——动态规划(三) 算法设计策略——动态规划测试
include<stdio.h> #include<string.h> #define Num 101 int n; int s[Num][Num],m[Num][Num],p[Num]; void traceback(int i,int j) { if(i==j) return; traceback(i,s[i][j]); traceback(s[i][j]+1,j); printf(“%d-%d，%d-%d”,i,s[i][j],s[i][j]+1,j); } void set() { int i,j,k,r,t; for(i=1;i<=n;i++) { m[i][i]=0; } for(r=2;r<=n;r++) { for(i=1;i<=n-r+1;i++) { j=r+i-1; m[i][j]=99999; s[i][j]=i; for(k=i;k<j;k++){ ① if(t<m[i][j]) { m[i][j]=t; s[i][j]=k; } } } } } int main() { scanf(“%d”,&n); for(int i=0;i<=n;i++) { scanf(“%d”,&p[i]); } set(); printf(“%d”,m[1][n]); traceback(1,n); return 0; }
include<string.h>
include<math.h>
define N 100

本答案对应课程为:点我自动跳转查看
本课程起止时间为:2022-03-28到2022-06-20

01 算法概述与算法分析基础算法概述与算法分析基础测试

1、问题:下列关于算法说法错误的是__
选项：
A:算法具备输入、输出、有穷性、确定性和可行性等属性。
B:算法可以没有输入。
C:算法可以没有输出。
D:算法需要具有正确性、健壮性、可读性和高效性。
答案: 【算法可以没有输出。】

2、问题:T(n)表示输入规模为n时的算法效率，以下算法效率最优的是
选项：
A:
B:
C:
D:
答案: 【】

3、问题:当输入规模为n时，算法复杂度增长率最大的是
选项：
A:
B:
C:
D:
答案: 【】

4、问题:下面关于NP问题说法正确的是 _。
选项：
A:NP问题都是不可能解决的问题。
B:P类问题包含在NP类问题中。
C:NP类问题包含在P类问题中。
D:NP完全问题是P类问题的子集。
答案: 【P类问题包含在NP类问题中。】

5、问题:下面叙述正确的是。
选项：
A:算法就是程序。
B:算法的性能与数据存储结构无关。
C:在设计算法时只需要考虑结果的可靠性。
D:以上三种描述都不正确。
答案: 【以上三种描述都不正确。】

6、问题:对具有n个元素的序列执行堆排序，其最坏情况下的算法时间复杂度为__。
选项：
A:
B:
C:
D:
答案: 【】

7、问题:以下关于渐近记号性质表述正确的是。
选项：
A:O(f(n)) + O(g(n)) = O( max(f(n), g(n)) )
B:O(f(n)) + O(g(n)) = O( min(f(n), g(n)) )
C:O(f(n)) + O(g(n)) = O( f(n)×g(n)) )
D:以上三种描述都不正确。
答案: 【O(f(n)) + O(g(n)) = O( max(f(n), g(n)) )】

8、问题:下列属于P问题的是。
选项：
A:0-1背包问题
B:旅行商问题
C:最小生成树
D:汉诺塔问题
答案: 【最小生成树】

9、问题:下列图像与表达式对应关系错误的是_____。
选项：
A:
B:
C:
D:
答案: 【】

10、问题:当输入规模为n时，算法复杂度增长率最大的是_ 。
选项：
A:
B:
C:
D:
答案: 【】

11、问题:如下算法的时间复杂度为__算法： loop2(n) s=0; for(i=1;i<=n;i++) for(j=1;j<=nn;j++) s=s+ij;
选项：
A:
B:
C:
D:
答案: 【】

02 算法设计基础算法设计基础测试

1、问题:函数将字符串中的字符‘’移到串的前部分，前面的非‘’字符后移，但不能改变非‘’字符的先后顺序，函数返回串中字符‘’的数量。（例如原始串为abcde12，处理后应为*abcde12，函数返回值为5）.请选择合适语句，完成代码。1.int change(char str)
2.{
3.    int count = 0;
4.    for(int i=0,j=0;str[i];i++){
5.        if(str[i] == ‘‘){
6.            for(1;str[j]!=’‘ && j >=0;_2_)
7.                str[j+1]=str[j];
8.            str[j+1] = ‘*’;
9.            count++;
10.        }
11.    }
12.    return count;
13.} 1 和 2 处应分别填入：
选项：
A:j=i+1; j++
B:j=i-1; j–
C:j=i+1; j–
D:j=i-1; j++
答案: 【j=i-1; j–】

2、问题:打印具有下面规律的图形。15 28 6 310 9 7 4请选择合适语句，完成代码。1.main(){
2.    int i,j,a[100][100],n,k;
3.    input(n);
4.    k=1;
5.    for(i=0;i<n;i++)
6.        for(j=0;j<=n-1;j++)
7.        {
8.            1;
9.            k++;
10.        }
11.    for(i=0;i<n;i++)
12.    {
13.        print("");
14.        for(j=0;j<i;j++)
15.            print(a[i][j]);
16.    }
17.} 1 处应填入：
选项：
A:a[j-i][j] = k
B:a[i+j][i] = k
C:a[j-i][i] = k
D:a[i+j][j] = k
答案: 【a[i+j][j] = k】

3、问题:求一个字符串S的全排列。（例如，字符串ABC的全排列为ABC,ACB,BAC,BCA,CAB,CBA）。请选择合适语句，完成代码。1.swap(ref string s,int i,int j){
2.    char temp = s[i];
3.    char temp1 = s[j];
4.    s = s.Remove(i, 1).Insert(i,temp1.ToString());
5.    s = s.Remove(j, 1).Insert(j,temp.ToString());
6.}
7.
8.void permuterHelper(string s, int k)
9.{
10.    if(1_)
11.    {cout<<s<<endl;}
12.    else{
13.        for(int i=k;i<s.length();i++){
14.            swap(ref s, k, i);
15.            permuteHelper(s, k+1);
16.        }
17.    }
18.} 1 处应填入：
选项：
A:k>s.length()
B:k!=s.length()
C:k==s.length()
D:k>s.length()+1
答案: 【k==s.length()】

4、问题:一次考试共考了语文、代数和外语三科。某小组共有九人，考后各科及格名单如下表，请编写算法找出三科全及格的学生的名单（学号）。请选择合适语句，完成代码。1.main(){
2.    int a[10],i,xh;
3.    for(i=1;i<=1;i=i+1){
4.        input(xh);
5.        a[2] = a[3]+1;
6.    }
7.
8.    for(xh = 1;xh<=9;xh=xh+1)
9.    {
10.        if(a[xh]==3)
11.            print(xh);
12.    }
13.}    1 , 2 , 3 处分别应填入：
选项：
A:20 ; xh ; i
B:21 ; xh ; xh
C:21 ; i ; xh
D:20 ; xh ; xh
答案: 【21 ; xh ; xh】

5、问题:求X,使得X²为一个各位数字互不相同的九位数。请选择合适语句，完成代码。1.main(){
2.    long x,y1,y2;
3.    input p[10],i,t,k,num=0;
4.    for(x=10000;x<32000;x=x+1){
5.        for(i=0;i<=9;i=i+1){