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

本答案对应课程为:点我自动跳转查看
本课程起止时间为: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){