【MOOC期末】《算法设计与分析》(北京科技大学)期末中国大学慕课答案

【MOOC期末】《算法设计与分析》(北京科技大学)期末中国大学慕课答案算法分析与设计期末考试卷1.单选题：下面程序的时间复杂度为()。for(i=1,s=0;i<=n;i++){t=1;
for(j=1;j<=i;j++)t=t*j;s=s+t;
}

选项：

A、

B、

C、

D、

答案：【】2.单选题：图的BFS生成树的树高比DFS生成树的树高()。

选项：

A、大或相等

B、小

C、小或相等

D、大

答案：【小或相等】3.单选题：若一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的第一趟结果为()。

选项：

A、40，38，46，56，79，84

B、40，38，46，84，56，79


C、38，40，46，56，79，84

D、40，38，46，79，56，84


答案：【40，38，46，56，79，84】4.单选题：设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为()。

选项：

A、O(1)

B、O(n)


C、

D、

答案：【O(1)

】5.单选题：设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为()。

选项：

A、5，3，4，6，1，2

B、1，5，4，6，2，3

C、3，1，2，5，4，6

D、3，2，5，6，4，1

答案：【3，2，5，6，4，1】6.单选题：设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径⻓度之和为()。

选项：

A、40

B、45

C、30

D、20

答案：【45】7.单选题：设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作为()。

选项：

A、top=top+1;


B、top->next=top;

C、top=top->next;

D、top=top-1;

答案：【top=top->next;】8.单选题：设某棵二叉树的高度为10，则该二叉树上叶子结点最多有()。

选项：

A、1024

B、256

C、20

D、512

答案：【512】9.单选题：下列说法不正确的是()。

选项：

A、图的深度遍历不适用于有向图

B、图的深度遍历是一个递归过程

C、遍历的基本方法有两种:深度遍历和广度遍历

D、图的遍历是从给定的源点出发每个顶点仅被访问一次

答案：【图的深度遍历不适用于有向图】10.单选题：下面程序段的时间复杂度为()。s=i=0;
do{i=i+1;s=s+i;
}while(i<=n);

选项：

A、

B、

C、

D、

答案：【】11.单选题：假设1元、2元、5元、10元、20元、50元、100元的纸币各有若干张张，现在要使用这些钱来支付k元，至少要用多少张纸币？编写代码求解如下：intsolve(intmoney,intValue[],intCount[],intN){intnum=0;for(inti=N-1;i>=0;i--){intc=min(money/Value[i],Count[i]);//每一个所需要的张数money=money-c*Value[i];num+=c;//总张数}if(money>0)num=-1;returnnum;}intmain(){inti;intN;cin>>N;intCount[100];//每一张纸币的数量intValue[100];//每一张的面额for(i=0;i<N;i++){cin>>Count[i];}for(i=0;i<N;i++){cin>>Value[i];}intmoney;cin>>money;intres=solve(money,Value,Count,N);if(res!=-1)cout<<res<<endl;elsecout<<"NO"<<endl;//找不开}①中应该填入（）

选项：

A、Count[i]

B、money/Value[i]

C、max(money/Value[i],Count[i])

D、min(money/Value[i],Count[i])

答案：【min(money/Value[i],Count[i])】12.单选题：编写程序输出1~1000之间的素数，以下是程序片段，请选择正确的语句填入()intmain(){inti,j;for(i=2;i<=1000;i++){for(j=2;j<=i;j++){if(j>=i){cout<<i<<endl;}if(①)break;}}return0;}①中应该填入（）

选项：

A、i%j==0

B、(i-1)%j==1

C、(i++)%j==0

D、i%(j-1)==1

答案：【

i%j==0】13.单选题：哈弗曼编码的贪心算法所需的计算时间为（）

选项：

A、O（n²）

B、O（nlogn）

C、O（2n）

D、O（n）

答案：【O（nlogn）】14.单选题：能采用贪心算法求最优解的问题，一般具有的重要性质为：（）

选项：

A、最优子结构性质与贪心选择性质

B、重叠子问题性质与贪心选择性质

C、最优子结构性质与重叠子问题性质

D、预排序与递归调用

答案：【最优子结构性质与贪心选择性质】15.单选题：有一个矩阵map，它每个格子有一个权值。从左上角的格子开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，返回所有的路径中最小的路径和。给定一个矩阵map及它的行数n和列数m，请返回最小路径和。保证行列数均小于等于100.若输入为：[[1,2,3],[1,1,1]],2,3则返回值为？

选项：

A、2

B、3

C、4

D、5

答案：【4】16.单选题：动态规划求解两字符串的最长公共子序列的长度charx[MAXN],y[MAXN];//两字符串intm,n;//两字符串的长度intc[MAXN][MAXN];//c[i][j]:长度为i的串与长度为j的串的最长公共子序列的长度intLCSLength(){inti,j;for(i=0;i<=m;i++)c[i][0]=0;for(j=1;j<=n;j++)c[0][j]=0;for(i=1;i<=m;i++){for(j=1;j<=n;j++){if(x[i-1]==y[j-1]){____;}elseif(c[i-1][j]>=c[i][j-1]){____;}else{____;}}}returnc[m][n];}

选项：

A、c[i][j]=c[i-1][j]；c[i][j]=c[i][j-1]；c[i][j]=c[i-1][j-1]+1

B、c[i][j]=c[i-1][j-1]+1；c[i][j]=c[i-1][j]；c[i][j]=c[i][j-1]

C、c[i][j]=c[i][j-1]；c[i][j]=c[i-1][j]；c[i][j]=c[i-1][j-1]+1

D、c[i][j]=c[i-1][j-1]+1；c[i][j]=c[i][j-1]；c[i][j]=c[i-1][j]

答案：【c[i][j]=c[i-1][j-1]+1；c[i][j]=c[i-1][j]；c[i][j]=c[i][j-1]】17.单选题：下列算法中通常以自底向上的方式求解最优解的是()

选项：

A、分治法

B、动态规划法

C、贪心法

D、回溯法

答案：【动态规划法】18.单选题：用动态规划算法解决最大字段和问题,其时间复杂性为()

选项：

A、logn

B、n

C、n²

D、nlogn

答案：【n】19.单选题：设输入序列是1、2、3、...、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是()。

选项：

A、n-1-i

B、不能确定

C、n-i

D、n+1-i

答案：【n+1-i

】20.单选题：设顺序线性表中有n个数据元素，则删除表中第i个元素需向前移动()个元素。

选项：

A、n-1-i

B、n-i

C、i


D、n+1-i

答案：【n-i

】21.单选题：分支限界法与回溯法都是在问题的解空间树T上搜索问题的解，二者（）。

选项：

A、求解目标不同，搜索方式相同

B、求解目标不同，搜索方式也不同

C、求解目标相同，搜索方式不同

D、求解目标相同，搜索方式也相同

答案：【求解目标不同，搜索方式也不同】22.单选题：解决0/1背包问题可以使用动态规划、回溯法和分支限界法,其中不需要排序的是(),需要排序的是(),()。

选项：

A、分支界限法，回溯法，动态规划

B、回溯法，动态规划，分支限界法

C、动态规划，回溯法，分支限界法

D、分支界限法，动态规划，回溯法

答案：【动态规划，回溯法，分支限界法】23.单选题：使用回溯法求{1,2,3,4,5}的所有排列个数，以下是程序片段，请选择正确的语句填入intamount=0;booluse[5]={false};voidpermutation(intn){if(n==5){amount++;return;}for(inti=1;i<=5;i++){if(!use[i]){①permutation(n+1);②}}}intmain(){permutation(0);cout<<<①和②中分别应该填入（）

选项：

A、use[i]=true;use[i]=true;

B、use[i]=true;use[i]=false;

C、use[i]=false;use[i]=true;

D、use[i]=false;use[i]=false;

答案：【use[i]=true;use[i]=false;】24.单选题：背包问题的回溯算法所需的计算时间为（）

选项：

A、O(n·2^n)

B、O(nlogn)

C、O(2^n)

D、O(n)

答案：【O(n·2^n)】25.单选题：打出所有的水仙花数。（水仙花数是指一个3位数，它的每个位上的数字的3次幂之和等于它本身）//打出所有的水仙花数1.intmain()2.{3.inti;4.for(i=99;i<1000;i++)//水仙花数为三位数，从100开始遍历，直到999.5.{6.if(pow(i/100,3)+pow((1),3)+pow(i%10,3)==i)7.{8.cout<<<1中应该填入：

选项：

A、(i%100)/10

B、(i%100)%10

C、i%100

D、i/100

答案：【(i%100)/10】26.单选题：背包问题设有一背包的容量为5kg，有三件物品的质量和价值如下，问如何才能使装入背包的物品价值最大。物品123重量325价值8512问装入背包的物品的最大价值为多少：

选项：

A、8

B、12

C、13

D、25

答案：【8】27.单选题：集合的划分F（n,m）表示把n个元素的集合分为m个子集，有多少种分法。问：F(4,2)=?

选项：

A、5

B、6

C、7

D、8

答案：【7】28.单选题：选择排序、插入排序和合并排序算法中，（）算法是分治算法。

选项：

A、选择排序

B、插入排序

C、合并排序

D、以上全部

答案：【合并排序】29.单选题：机器人走方格有一个X*Y的网格，一个机器人只能走格点，且只能向右或向下走，要从左上角走到右下角。请设计一个算法，计算机器人有多少种走法。给定两个正整数intx,inty,请返回机器人的走法数目。保证x+y小于等于12。publicintsolution2(intX,intY){int[][]state=newint[X][Y];if(X<0||Y<0){return0;}for(inti=0;i<X;i++){state[i][0]=1;}for(inti=0;i<Y;i++){state[0][i]=1;}for(inti=1;i<X;i++){for(intj=1;j<Y;j++){__1__;}}returnstate[X-1][Y-1];}程序中1处应填入：

选项：

A、state[i][j]=state[i+1][j]+state[i][j+1]

B、state[i][j]=state[i-1][j]+state[i][j+1]

C、state[i][j]=state[i+1][j]+state[i][j-1]

D、state[i][j]=state[i-1][j]+state[i][j-1]

答案：【state[i][j]=state[i-1][j]+state[i][j-1]】30.单选题：生成杨辉三角#includeusingnamespacestd;intmain(){inti,j,n=0,a[17]={1},b[17];while(n<1||n>16){printf("请输入杨辉三角形的行数:");scanf("%d",&n);}for(i=0;i程序中1处应填入：

选项：

A、b[j]=a[j+1]+a[j];

B、b[j]=a[i]+a[j-1];

C、b[j]=a[j-1]+a[i-1];

D、b[j]=a[j-1]+a[j];

答案：【b[j]=a[j-1]+a[j];

】31.单选题：一次考试共考了语文、代数和外语三科。某小组共有九人，考后各科及格名单如下表，请编写算法找出三科全及格的学生的名单（学号）。请选择合适语句，完成代码。1.main(){2.inta[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】32.单选题：1.警察局抓了a,b,c,d四名偷窃嫌疑犯，其中只有一人是小偷。审问中a说：“我不是小偷。”b说：“c是小偷。”c说：“小偷肯定是d。”d说：“c在冤枉人。”现在已知：四个人中三人说的是真话，一人说的是假话，问到底谁是小偷？请选择合适语句，完成代码。1.main()2.{3.intx;4.for(x=1;x<4;x++)5.{6.if(__1__)7.print(chr(64+x),"isathief.");8.}9.}1处应填入：

选项：

A、(x<>1)+(x==3)+(x==4)+(x==3)==3

B、(x<>1)+(x==3)+(x==4)+(x<>4)==4

C、(x==1)+(x==3)+(x==4)+(x<>4)==4

D、(x<>1)+(x==3)+(x==4)+(x<>4)==3

答案：【(x<>1)+(x==3)+(x==4)+(x<>4)==3】33.单选题：如下算法的时间复杂度为________算法：loop2(n)s=0;for(i=1;i<=n;i++)for(j=1;j<=n*n;j++)s=s+i*j;

选项：

A、

B、

C、

D、

答案：【】34.单选题：下列属于P问题的是。

选项：

A、0-1背包问题

B、旅行商问题

C、最小生成树

D、汉诺塔问题

答案：【最小生成树】35.单选题：在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目标顶点t之间的最短路径。问最短路径的长度为？

选项：

A、8

B、9

C、14

D、7

答案：【8】36.单选题：Dijkstr