【MOOC】《算法設(shè)計(jì)與分析》(北京科技大學(xué))中國大學(xué)MOOC慕課答案

【MOOC】《算法設(shè)計(jì)與分析》(北京科技大學(xué))章節(jié)作業(yè)網(wǎng)課慕課答案01算法概述與算法分析基礎(chǔ)算法概述與算法分析基礎(chǔ)測試1.問題：如下算法的時間復(fù)雜度為________算法：loop2(n)s=0;for(i=1;i<=n;i++)for(j=1;j<=n*n;j++)s=s+i*j;

選項(xiàng)：

A、

B、

C、

D、

本題答案：【】2.問題：T(n)表示輸入規(guī)模為n時的算法效率，以下算法效率最優(yōu)的是

選項(xiàng)：

A、

B、

C、

D、

本題答案：【】3.問題：下列關(guān)于算法說法錯誤的是________

選項(xiàng)：

A、算法具備輸入、輸出、有窮性、確定性和可行性等屬性。

B、算法可以沒有輸入。

C、算法可以沒有輸出。

D、算法需要具有正確性、健壯性、可讀性和高效性。

本題答案：【算法可以沒有輸出?！?.問題：當(dāng)輸入規(guī)模為n時，算法復(fù)雜度增長率最大的是_______。

選項(xiàng)：

A、

B、

C、

D、

本題答案：【】5.問題：下列圖像與表達(dá)式對應(yīng)關(guān)系錯誤的是___________。

選項(xiàng)：

A、

B、

C、

D、

本題答案：【】6.問題：下列屬于P問題的是。

選項(xiàng)：

A、0-1背包問題

B、旅行商問題

C、最小生成樹

D、漢諾塔問題

本題答案：【最小生成樹】7.問題：以下關(guān)于漸近記號性質(zhì)表述正確的是。

選項(xiàng)：

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.問題：對具有n個元素的序列執(zhí)行堆排序，其最壞情況下的算法時間復(fù)雜度為________。

選項(xiàng)：

A、

B、

C、

D、

本題答案：【】9.問題：下面敘述正確的是。

選項(xiàng)：

A、算法就是程序。

B、算法的性能與數(shù)據(jù)存儲結(jié)構(gòu)無關(guān)。

C、在設(shè)計(jì)算法時只需要考慮結(jié)果的可靠性。

D、以上三種描述都不正確。

本題答案：【以上三種描述都不正確?！?0.問題：下面關(guān)于NP問題說法正確的是_______。

選項(xiàng)：

A、NP問題都是不可能解決的問題。

B、P類問題包含在NP類問題中。

C、NP類問題包含在P類問題中。

D、NP完全問題是P類問題的子集。

本題答案：【P類問題包含在NP類問題中?！?1.問題：當(dāng)輸入規(guī)模為n時，算法復(fù)雜度增長率最大的是

選項(xiàng)：

A、

B、

C、

D、

本題答案：【】02算法設(shè)計(jì)基礎(chǔ)算法設(shè)計(jì)基礎(chǔ)測試1.問題：求一個字符串S的全排列。（例如，字符串ABC的全排列為ABC,ACB,BAC,BCA,CAB,CBA）。請選擇合適語句，完成代碼。1.swap(refstrings,inti,intj){2.chartemp=s[i];3.chartemp1=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.voidpermuterHelper(strings,intk)9.{10.if(___1____)11.{cout<<<1處應(yīng)填入：

選項(xiàng)：

A、k>s.length()

B、k!=s.length()

C、k==s.length()

D、k>s.length()+1

本題答案：【k==s.length()】2.問題：打印具有下面規(guī)律的圖形選擇合適語句，完成代碼。1.main(){2.inti,j,a[100][100],n,k;3.input(n);4.k=1;5.for(i=0;i1處應(yīng)填入：

選項(xiàng)：

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.問題：函數(shù)將字符串中的字符‘*’移到串的前部分，前面的非‘*’字符后移，但不能改變非‘*’字符的先后順序，函數(shù)返回串中字符‘*’的數(shù)量。（例如原始串為ab**cd**e*12，處理后應(yīng)為*****abcde12，函數(shù)返回值為5）.請選擇合適語句，完成代碼。1.intchange(char*str)2.{3.intcount=0;4.for(inti=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.returncount;13.}1和2處應(yīng)分別填入：

選項(xiàng)：

A、j=i+1;j++

B、j=i-1;j--

C、j=i+1;j--

D、j=i-1;j++

本題答案：【j=i-1;j--】4.問題：數(shù)組中有n個數(shù)據(jù)，要將它們順序循環(huán)向后移k位，即前面的元素向后移k位，后面的元素則循環(huán)向前移k位，例：1、2、3、4、5循環(huán)移3位后為：3、4、5、1、2。請選擇合適語句，完成代碼。1.main(){2.inta[100],b[100],i,n,k;3.input(n,k);4.for(i=0;i1處應(yīng)填入：

選項(xiàng)：

A、(k+1)%n

B、(k+1)/n

C、(k+i)/n

D、(k+i)%n

本題答案：【(k+i)%n】5.問題：1.警察局抓了a,b,c,d四名偷竊嫌疑犯，其中只有一人是小偷。審問中a說：“我不是小偷。”b說：“c是小偷?！眂說：“小偷肯定是d。”d說：“c在冤枉人?！爆F(xiàn)在已知：四個人中三人說的是真話，一人說的是假話，問到底誰是小偷？請選擇合適語句，完成代碼。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處應(yīng)填入：

選項(xiàng)：

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】6.問題：一個顧客買了價值x元的商品，并將y元的錢交給售貨員。售貨員希望用張數(shù)最少的錢幣找給顧客。請選擇合適語句，完成代碼。1.main(){2.inti,j,x,y,z,a,b[7]={0,50,20,10,5,2,1},s[7];3.input(x,y);4.z=y-x;5.for(i=1;i<=6;i=i+1){6.a=z/b[i];7.s[i]=s[i]+a;8.__1__;9.}10.print(y,"-",x,"=",z);11.for(i=1;i<=6;i=i+1)12.{13.if(s[i]<>0)14.print(b[i],"----",s[i]);15.}16.}1處應(yīng)填入：

選項(xiàng)：

A、z=z-a*b[i]

B、z=z+a*b[i]

C、z=z+a-b[i]

D、z=z-a+b[i]

本題答案：【z=z-a*b[i]】7.問題：求X,使得X2為一個各位數(shù)字互不相同的九位數(shù)。請選擇合適語句，完成代碼。1.main(){2.longx,y1,y2;3.inputp[10],i,t,k,num=0;4.for(x=10000;x<32000;x=x+1){5.for(i=0;i<=9;i=i+1){6.p[i]=1;7.}8.y1=x*x;y2=y1;k=0;9.for(i=1;i<=9;i=i+1){10.t=y2mod10;11.y2=y2/10;12.if(p[t]==1)13.{14.p[t]=0;__1__;15.}16.else17.break;18.}19.if(k==9){20.num=num+1;21.print("No.",num,":n=",x,"n2=",y1);22.}23.}24.}1處應(yīng)填入：

選項(xiàng)：

A、k=k-1

B、k=k+i

C、k=k+1

D、k=k-i

本題答案：【k=k+1】8.問題：一次考試共考了語文、代數(shù)和外語三科。某小組共有九人，考后各科及格名單如下表，請編寫算法找出三科全及格的學(xué)生的名單（學(xué)號）。請選擇合適語句，完成代碼。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處分別應(yīng)填入：

選項(xiàng)：

A、20;xh;i

B、21;xh;xh

C、21;i;xh

D、20;xh;xh

本題答案：【21;xh;xh】03算法設(shè)計(jì)策略——迭代法算法設(shè)計(jì)策略——迭代法測試1.問題：每年冬天，北大未名湖上都是滑冰的好地方。北大體育組準(zhǔn)備了許多冰鞋，可是人太多了，每天下午收工后，常常一雙冰鞋都不剩。每天早上，租鞋窗口都會排起長龍，假設(shè)有還鞋的m個，有需要租鞋的n個。現(xiàn)在的問題是，這些人有多少種排法，可以避免出現(xiàn)體育組沒有冰鞋可租的尷尬場面。（兩個同樣需求的人（比如都是租鞋或都是還鞋）交換位置是同一種排法）若輸入兩個整數(shù)m=6和n=5，則隊(duì)伍排法的方案數(shù)為？

選項(xiàng)：

A、130

B、131

C、132

D、133

本題答案：【132】2.問題：機(jī)器人走方格有一個X*Y的網(wǎng)格，一個機(jī)器人只能走格點(diǎn)，且只能向右或向下走，要從左上角走到右下角。請?jiān)O(shè)計(jì)一個算法，計(jì)算機(jī)器人有多少種走法。給定兩個正整數(shù)intx,inty,請返回機(jī)器人的走法數(shù)目。保證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處應(yīng)填入：

選項(xiàng)：

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]】3.問題：用迭代法求#include#includeusingnamespacestd;intmain(){inta;doublex1,x2;cout<<"Pleaseentera:";cin>>a;for(x1=1,__1__;fabs(x2-x1)>1e-5;x1=x2,x2=(x1+a/x1)/2);cout<<"Squareroot="<<<程序中1處應(yīng)填入：

選項(xiàng)：

A、x2=(x1+a/x1)/2

B、x2=(x1-a/x1)/2

C、x2=(x1+a/x1)%2

D、x2=(x1-a/x1)%2

本題答案：【x2=(x1+a/x1)/2】4.問題：用迭代法求斐波那契數(shù)列#include#includeintFib(intn){if(n<1){return-1;}if(n==1||n==2){return1;}else{inti,s1=1,s2=2;for(i=3;i程序中1、2處分別應(yīng)填入：

選項(xiàng)：

A、s2=s1+s2；s1=s2-s1

B、s1=s2-s1；s2=s1+s2

C、s2=s1-s2；s1=s2+s1

D、s1=s2+s1；s2=s1-s2

本題答案：【s2=s1+s2；s1=s2-s1】5.問題：一輛吉普車來到1000km寬的沙漠邊沿。吉普車的耗油量為1L／km，總裝油量為500L。顯然，吉普車必須用自身油箱中的油在沙漠中設(shè)幾個臨時加油點(diǎn)，否則是通不過沙漠的。假設(shè)在沙漠邊沿有充足的汽油可供使用，那么吉普車應(yīng)在哪些地方、建多大的臨的加油點(diǎn)，才能以最少的油耗穿過這塊沙漠?#includeusingnamespacestd;intmain(){intdis=500,oil=500;intk=1;do{printf("儲油點(diǎn)%d：距離出發(fā)點(diǎn)%5d,",k,1000-dis);printf("儲油量%5dL\n",oil);k=k+1;__1__oil=500*k;}while(dis<1000);oil=500*(k-1)+(1000-dis)*(2*k-1);printf("儲油點(diǎn)%d：距離出發(fā)點(diǎn)%5d,儲油量%5dL\n",k,0,oil);return0;}程序中1處應(yīng)填入：

選項(xiàng)：

A、dis=dis+500%(2*k-1);

B、dis=dis+500/(2*k-1);

C、dis=dis+500%(2*k+1);

D、dis=dis+500/(2*k+1);

本題答案：【dis=dis+500/(2*k-1);】6.問題：生成楊輝三角#includeusingnamespacestd;intmain(){inti,j,n=0,a[17]={1},b[17];while(n<1||n>16){printf("請輸入楊輝三角形的行數(shù):");scanf("%d",&n);}for(i=0;i程序中1處應(yīng)填入：

選項(xiàng)：

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];】7.問題：猴子第一天采摘了一些桃子，第二天吃了第一天的一半多一個，第三天吃了第二天的一半多一個...直到第十天就剩下一個。問：猴子第一天摘了多少桃子？#include#includeusingnamespacestd;intmain(){//猴子吃桃intf[11];f[10]=1;for(inti=10;i>1;i--){__1__;}cout<程序中1處應(yīng)填入：

選項(xiàng)：

A、f[i-1]=(f[i]+1)/2

B、f[i-1]=(f[i]-1)/2

C、f[i-1]=(f[i]+1)*2

D、f[i-1]=(f[i]-1)*2

本題答案：【f[i-1]=(f[i]+1)*2】04算法設(shè)計(jì)策略——分治算法設(shè)計(jì)策略——分治1.問題：在尋找n個元素中第k小元素問題中，若使用快速排序算法思想，運(yùn)用分治算法對n個元素進(jìn)行劃分，應(yīng)如何選擇劃分基準(zhǔn)？下面（）答案解釋最合理。

選項(xiàng)：

A、隨機(jī)選擇一個元素作為劃分基準(zhǔn)

B、取子序列的第一個元素作為劃分基準(zhǔn)

C、用中位數(shù)的中位數(shù)方法尋找劃分基準(zhǔn)

D、以上皆可行。但不同方法，算法復(fù)雜度上界可能不同

本題答案：【以上皆可行。但不同方法，算法復(fù)雜度上界可能不同】2.問題：使用分治法求解不需要滿足的條件是

選項(xiàng)：

A、子問題必須是一樣的

B、子問題不能夠重復(fù)

C、子問題的解可以合并

D、原問題和子問題使用相同的方法解

本題答案：【子問題必須是一樣的】3.問題：整數(shù)的劃分將一個整數(shù)n劃分為若干個數(shù)相加，有多少種劃分方法？輸入是兩個正整數(shù)，一個是待劃分的整數(shù)n，一個是最大加數(shù)。若輸入為：2525則返回值為？

選項(xiàng)：

A、1950

B、1952

C、1954

D、1958

本題答案：【1958】4.問題：集合的劃分F（n,m）表示把n個元素的集合分為m個子集，有多少種分法。問：F(4,2)=?

選項(xiàng)：

A、5

B、6

C、7

D、8

本題答案：【7】5.問題：設(shè)有n=2^k(k>=1)個選手參加網(wǎng)球循環(huán)賽，循環(huán)賽共進(jìn)行n-1天，每位選手要與其他n-1位選手比賽一場，且每位選手每天必須比賽一場，不能輪空。試按此要求為比賽安排日程。#includeusingnamespacestd;#defineN64voidGameTable(intk,inta[][N]){intn=2;a[1][1]=1;a[1][2]=2;a[2][1]=2;a[2][2]=1;inti,j,t;for(t=1;t>k;GameTable(k,a);}程序中①處應(yīng)填入：

選項(xiàng)：

A、a[i][j]=a[i+temp][(j-temp)%n];

B、a[i][j]=a[i+temp][(j+temp)%n];

C、a[i][j]=a[i+temp][(j+temp)/n];

D、a[i][j]=a[i+temp][(j-temp)/n];

本題答案：【a[i][j]=a[i+temp][(j+temp)%n];】6.問題：實(shí)現(xiàn)pow(x,n)，即計(jì)算x的n次冪函數(shù)。classSolution{public:doublemyPow(doublex,intn){if(n==0)return1;doubletmp=myPow(x,n/2);doubleres=tmp*tmp;if(n>0){if(①)return②;elsereturnres;}else{if(③)return④;elsereturnres;}}};①②③④處分別應(yīng)填入：

選項(xiàng)：

A、n%2;res*x;n%2;res/x

B、n/2;res*x;n/2;res/x

C、n%2;res/x;n%2;res*x

D、n/2;res/x;n/2;res*x

本題答案：【n%2;res*x;n%2;res/x】7.問題：選擇排序、插入排序和合并排序算法中，（）算法是分治算法。

選項(xiàng)：

A、選擇排序

B、插入排序

C、合并排序

D、以上全部

本題答案：【合并排序】8.問題：實(shí)現(xiàn)大整數(shù)的乘法是利用的算法()

選項(xiàng)：

A、貪心法

B、動態(tài)規(guī)劃法

C、分治策略

D、回溯法

本題答案：【分治策略】07算法設(shè)計(jì)策略——動態(tài)規(guī)劃(三)算法設(shè)計(jì)策略——動態(tài)規(guī)劃測試1.問題：一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。給定兩個序列X和Y，找出二者的最長公共子序列。#include#include#include#defineN100chara[N],b[N];inttemp[N][N];intmain(){inti,j,len_a,len_b;scanf("%s",a);scanf("%s",b);len_a=strlen(a);len_b=strlen(b);for(i=1;i<=len_a;i++){for(j=1;j<=len_b;j++){if(a[i-1]==b[j-1])temp[i][j]=temp[i-1][j-1]+1;else①}}printf("%d\n",temp[len_a][len_b]);return0;}程序中①處應(yīng)填入：

選項(xiàng)：

A、temp[i][j]=temp[i+1][j]>temp[i][j-1]?temp[i-1][j]:temp[i][j-1];

B、temp[i][j]=temp[i-1][j]>temp[i][j-1]?temp[i-1][j]:temp[i][j-1];

C、temp[i][j]=temp[i-1][j]>temp[i][j+1]?temp[i-1][j]:temp[i][j-1];

D、temp[i][j]=temp[i-1][j]>temp[i][j-1]?temp[i+1][j]:temp[i][j-1];

本題答案：【temp[i][j]=temp[i-1][j]>temp[i][j-1]?temp[i-1][j]:temp[i][j-1];】2.問題：下列算法中通常以自底向上的方式求解最優(yōu)解的是()

選項(xiàng)：

A、分治法

B、動態(tài)規(guī)劃法

C、貪心法

D、回溯法

本題答案：【動態(tài)規(guī)劃法】3.問題：矩陣連乘問題#include#include#defineNum101intn;ints[Num][Num],m[Num][Num],p[Num];voidtraceback(inti,intj){if(i==j)return;traceback(i,s[i][j]);traceback(s[i][j]+1,j);printf("%d-%d，%d-%d\n",i,s[i][j],s[i][j]+1,j);}voidset(){inti,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<span=""><>①if(t<span=""><>m[i][j]=t;s[i][j]=k;}}}}}intmain(){scanf("%d",&n);for(inti=0;i<=n;i++){scanf("%d",&p[i]);}set();printf("%d\n",m[1][n]);traceback(1,n);return0;}程序中①處應(yīng)填入：

選項(xiàng)：

A、t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];

B、t=m[i][k]+m[k-1][j]+p[i-1]*p[k]*p[j];

C、t=m[i][k]+m[k+1][j]+p[i+1]*p[k]*p[j];

D、t=m[j][k]+m[k+1][j]+p[i-1]*p[k]*p[j];

本題答案：【t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];】4.問題：有一個矩陣map，它每個格子有一個權(quán)值。從左上角的格子開始每次只能向右或者向下走，最后到達(dá)右下角的位置，路徑上所有的數(shù)字累加起來就是路徑和，返回所有的路徑中最小的路徑和。給定一個矩陣map及它的行數(shù)n和列數(shù)m，請返回最小路徑和。保證行列數(shù)均小于等于100.若輸入為：[[1,2,3],[1,1,1]],2,3則返回值為？

選項(xiàng)：

A、2

B、3

C、4

D、5

本題答案：【4】5.問題：用動態(tài)規(guī)劃算法解決最大子段和問題,其時間復(fù)雜性為()

選項(xiàng)：

A、logn

B、n

C、n2

D、nlogn

本題答案：【n】6.問題：找零錢問題有數(shù)組penny，penny中所有的值都為正數(shù)且不重復(fù)。每個值代表一種面值的貨幣，每種面值的貨幣可以使用任意張，再給定一個整數(shù)aim(小于等于1000)代表要找的錢數(shù)，求換錢有多少種方法。給定數(shù)組penny及它的大小(小于等于50)，同時給定一個整數(shù)aim，請返回有多少種方法可以湊成aim。若輸入為：[1,2,3],3,3問返回值為？

選項(xiàng)：

A、1

B、2

C、3

D、4

本題答案：【3】7.問題：動態(tài)規(guī)劃求解兩字符串的最長公共子序列的長度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];}

選項(xiàng)：

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]】8.多選題：動態(tài)規(guī)劃算法的兩個基本要素是____和____性質(zhì)

選項(xiàng)：

A、最優(yōu)子結(jié)構(gòu)

B、重疊子問題

C、構(gòu)造最優(yōu)解

D、定義最優(yōu)解

本題答案：【最優(yōu)子結(jié)構(gòu);重疊子問題】09算法設(shè)計(jì)策略——貪婪法(二)算法設(shè)計(jì)策略——貪婪法測試1.問題：假設(shè)你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個孩子最多只能給一塊餅干。對每個孩子i，都有一個胃口值gi，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干j，都有一個尺寸sj。如果sj>=gi，我們可以將這個餅干j分配給孩子i，這個孩子會得到滿足。你的目標(biāo)是盡可能滿足越多數(shù)量的孩子，并輸出這個最大數(shù)值voidquick_sort(ints[],intl,intr){if(l<r){inti=l,j=r,x=s[l];while(i<j){while(i<j&&s[j]>=x){j--;}if(i<j){s[i++]=s[j];}while(i<j&&s[i]<x){i++;}if(i<j){s[j--]=s[i];}}s[i]=x;quick_sort(s,l,i-1);quick_sort(s,i+1,r);}}intmain(){intgSize;//孩子個數(shù)intsSize;//餅干個數(shù)intg[100];//孩子胃容量ints[100];//餅干尺寸cin>>gSize>>sSize;intm;for(m=0;m<gSize;m++){cin>>g[m];}for(m=0;m<sSize;m++){cin>>s[m];}quick_sort(g,0,gSize-1);quick_sort(s,0,sSize-1);inti=0;intj=0;intnum=0;while(i<gSize&&j<sSize){if(①){num++;i++;}j++;}cout<<num<<endl;return0;}①中應(yīng)該填入（）

選項(xiàng)：

A、g[i]<=s[j]

B、g[i]==s[j]

C、g[i]>s[j]

D、g[i]>=s[j]

本題答案：【g[i]<=s[j]】2.問題：有一個容量為150的背包，背包可以裝入7種物品，物品可以分割成任意大小，七種物品的重量為35,30,60,50,40,10,25，對應(yīng)的價值為10,40,30,50,35,40,30，為了盡可能使背包中裝入的物品總價值最大，我們編寫程序求出裝入物品及其對應(yīng)的比例如下：intmain(){floatw[10]={35,30,60,50,40,10,25};//用來表示每個物品的重量floatv[10]={10,40,30,50,35,40,30};//用來表示每個物品的價值量floatx[10];//表示最后放入背包的比例intn=7;//物品數(shù)floatM=150;//背包最大容納重量//按照單位重量的價值量大小降序排列Sort(n,w,v);inti;for(i=0;i<n;i++)x[i]=0;//初始值，未裝入背包，x[i]=0floatc=M;//更新背包容納量for(i=0;i<n;i++){if(①)break;//不能完全裝下x[i]=1;c=c-w[i];}if(i<n)x[i]=c/w[i];//輸出for(inti=0;i<n;i++)cout<<"重量為"<<w[i]<<"價值量為"<<v[i]<<"的物品"<<"放入的比例為"<<x[i]<<endl;return0;}①中應(yīng)該填入（）

選項(xiàng)：

A、c<w[i]

B、c<=w[i]

C、c>w[i]

D、c>=w[i]

本題答案：【c<w[i]】3.問題：編寫程序輸出1~1000之間的同構(gòu)數(shù)。同構(gòu)數(shù)是會出現(xiàn)在它平方數(shù)個位上的數(shù)，如5×5=25，6×6=36。以下是程序片段，請選擇正確的語句填入()intmain()//求同構(gòu)數(shù){//求1000以內(nèi)的同構(gòu)數(shù)longresult;for(inti=1000;i>=1;i--){result=pow(i,2);if(i<10&&i==result%10)//處理10以下的數(shù)cout<<i<<"同構(gòu)數(shù)"<<result<<endl;elseif(①)//處理100以下的數(shù)cout<<i<<"同構(gòu)數(shù)"<<result<<endl;elseif(i>=100&&i==result%1000)//處理1000以下的數(shù)cout<<i<<"同構(gòu)數(shù)"<<result<<endl;elsecontinue;}cout<<"<--------------------------------------->"<<endl;return0;}①中應(yīng)該填入（）

選項(xiàng)：

A、i%j==0

B、i>=10&&i==result%100

C、i<10&&i==result%10

D、i>=100&&i==result%1000

本題答案：【i>=10&&i==result%100】4.問題：哈弗曼編碼的貪心算法所需的計(jì)算時間為（）

選項(xiàng)：

A、O（n2）

B、O（nlogn）

C、O（2n）

D、O（n）

本題答案：【O（nlogn）】5.問題：假設(shè)1元、2元、5元、10元、20元、50元、100元的紙幣各有若干張張，現(xiàn)在要使用這些錢來支付k元，至少要用多少張紙幣？編寫代碼求解如下：intsolve(intmoney,intValue[],intCount[],intN){intnum=0;for(inti=N-1;i>=0;i--){intc=min(money/Value[i],Count[i]);//每一個所需要的張數(shù)money=money-c*Value[i];num+=c;//總張數(shù)}if(money>0)num=-1;returnnum;}intmain(){inti;intN;cin>>N;intCount[100];//每一張紙幣的數(shù)量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;//找不開}①中應(yīng)該填入（）

選項(xiàng)：

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])】6.問題：編寫程序輸出三位數(shù)的是水仙花數(shù)。水仙花數(shù)是一種三位數(shù)，其各位數(shù)之立方和等于該數(shù)，例如：13+53+33=153。以下是程序片段，請選擇正確的語句填入()intmain(){inta=0;for(intx=1;x<10;x++){for(inty=0;y<10;y++){for(intz=0;z<10;z++){a=①;if(a==xxx+yyy+zzz){cout<<a<<"是水仙花數(shù)"<<endl;}}}}return0;}①中應(yīng)該填入（）

選項(xiàng)：

A、x*x*x+y*y*y+z*z*z

B、100*z+10*y+x

C、100*x+10*y+z

D、100*y+10*x+z

本題答案：【100*x+10*y+z】7.問題：能采用貪心算法求最優(yōu)解的問題，一般具有的重要性質(zhì)為：（）

選項(xiàng)：

A、最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)

B、重疊子問題性質(zhì)與貪心選擇性質(zhì)

C、最優(yōu)子結(jié)構(gòu)性質(zhì)與重疊子問題性質(zhì)

D、預(yù)排序與遞歸調(diào)用

本題答案：【最優(yōu)子結(jié)構(gòu)性質(zhì)與貪心選擇性質(zhì)】8.問題：編寫程序輸出1~1000之間的素數(shù)，以下是程序片段，請選擇正確的語句填入()intmain(){inti,j;for(i=2;i<=1000;i++){for(j=2;j<=i;j++){if(j>=i){cout<<i<<endl;}if(①)break;}}return0;}①中應(yīng)該填入（）

選項(xiàng)：

A、i%j==0

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

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

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

本題答案：【i%j==0】10算法設(shè)計(jì)策略——蠻力法算法設(shè)計(jì)策略——蠻力法1.問題：背包問題設(shè)有一背包的容量為5kg，有三件物品的質(zhì)量和價值如下，問如何才能使裝入背包的物品價值最大。物品123重量325價值8512問裝入背包的物品的最大價值為多少：

選項(xiàng)：

A、8

B、12

C、13

D、25

本題答案：【13】2.問題：今有雞兔同籠，上有三十五頭，下有九十四足，問雞兔各幾只？1./*2.輸入?yún)?shù)head是籠中頭的總數(shù)，foot是籠中腳的總數(shù)，chicken是雞的總數(shù),rabbit是兔的總數(shù)3.返回結(jié)果為0，表示沒有搜索到符合條件的結(jié)果；4.返回結(jié)果為1，表示搜索到了符合條件的結(jié)果5.*/6.intqiongju(inthead,intfoot,intchicken,intrabbit)7.{8.intre,i,j;9.re=0;10.for(i=0;i<=head,i++)//進(jìn)行循環(huán)11.{12.j=head-i;13.if(1)//進(jìn)行判斷14.{15.re=1;//找到答案16.*chicken=i;17.*rabbit=j;18.}19.}20.returnre;21.}1處應(yīng)填入

選項(xiàng)：

A、i*2+j*4==head

B、i*4+j*2==head

C、i*4+j*2==foot

D、i*2+j*4==foot

本題答案：【i*2+j*4==foot】3.問題：100元面值的人民幣換成用20元、10元、5元面值的人民幣，在每種面值至少存在一張的情況下，有多少種組合。1.voidfun()2.{3.intiNum_20=0;//20元面值的張數(shù)4.intiNum_10=0;//10元面值的張數(shù)5.intiNum_5=0;//5元面值的張數(shù)6.7.intiCount=0;//組合計(jì)數(shù)8.for(iNum_20=1;iNum_20<=4;iNum_20++)//窮舉20元面值的所有情況9.{10.for(iNum_10=1;1;iNum_10++)//窮舉10元面值的所有情況11.{12.for(iNum_5=1;iNum_5<=14;iNum_5++)//窮舉5元面值的所有情況13.{14.if(100==((iNum_2020)+(iNum_1010)+(iNum_5*5)))15.{16.++iCount;17.cout<<"第"<<iCount<<"種組合：20元面值"<<iNum_20<<"張-10元面值"<<iNum_10<<"張-5元面值"<<iNum_5<<"張"<<endl;18.}19.}20.}21.}22.}1處應(yīng)填入()可使窮舉次數(shù)最少且結(jié)果正確

選項(xiàng)：

A、iNum_10<=10

B、iNum_10<=9

C、iNum_10<=7

D、iNum_10<=6

本題答案：【iNum_10<=7】4.問題：對于長度為5位的一個01串，每一位都可能是0或1，一共有32種可能。它們的前幾個是：0000000001000100001100100請按從小到大的順序輸出這32種01串。1.voidd_to_b(inta,int*b)2.{3.for(inti;i<5;i++)4.{5.b[4-i]=①;6.②;7.}8.}9.intmain()10.{11.intn=0;12.intb[4];13.for(;n<32;n++)14.{15.d_to_b(n,b);16.for(intd=0;d<5;d++)17.{18.cout<<b[d];19.}20.cout<<endl;21.}22.23.system("pause");24.return0;25.}①,②中應(yīng)分別填入：

選項(xiàng)：

A、a%2,a=a/2

B、a/2,a=a%2

C、a%2,a=a%2

D、a/2,a=a/2

本題答案：【a%2,a=a/2】5.問題：1221是一個非常特殊的數(shù)，它從左邊讀和從右邊讀是一樣的，編程求所有這樣的四位十進(jìn)制數(shù)。1.intmain()2.{3.intn;4.inta,b,c,d;5.for(n=1000;n<10000;n++)6.{7.d=n%10;8.c=n/10;9.b=c/10;10.a=b/10;11.c%=10;12.b%=10;13.a%=10;14.15.if(1)16.cout<<n<<endl;17.}18.19.return0;20.}1處應(yīng)填入：

選項(xiàng)：

A、a==d||b==c

B、a==d&&b==c

C、a==c&&b==d

D、a==c||b==d

本題答案：【a==d&&b==c】6.問題：打出所有的水仙花數(shù)。（水仙花數(shù)是指一個3位數(shù)，它的每個位上的數(shù)字的3次冪之和等于它本身）//打出所有的水仙花數(shù)1.intmain()2.{3.inti;4.for(i=99;i<1000;i++)//水仙花數(shù)為三位數(shù)，從100開始遍歷，直到999.5.{6.if(pow(i/100,3)+pow((1),3)+pow(i%10,3)==i)7.{8.cout<<<1中應(yīng)該填入：

選項(xiàng)：

A、(i%100)/10

B、(i/100)%10

C、i%100

D、i/100

本題答案：【(i%100)/10】11算法設(shè)計(jì)策略——回溯法算法設(shè)計(jì)策略——回溯法1.問題：使用回溯法求{1,2,3,4,5}的所有排列個數(shù)，以下是程序片段，請選擇正確的語句填入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<<<①和②中分別應(yīng)該填入（）

選項(xiàng)：

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;】2.問題：下列算法中通常以深度優(yōu)先方式系統(tǒng)搜索問題解的是（）。

選項(xiàng)：

A、備忘錄法

B、動態(tài)規(guī)劃法

C、貪心法

D、回溯法

本題答案：【回溯法】3.問題：背包問題的回溯算法所需的計(jì)算時間為（）

選項(xiàng)：

A、O(n·2^n)

B、O(nlogn)

C、O(2^n)

D、O(n)

本題答案：【O(n·2^n)】4.問題：數(shù)字n代表生成括號的對數(shù)，函數(shù)bracket能夠生成所有可能的并且有效的括號組合。例如”(())“、”()()“均是n=2時有效的括號組合。以下是程序片段，請選擇正確的語句填入intn=3;voidbracket(strings,intleft,intright){if(left==0&&right==0){cout<<0){①}if(right>0){if(left>=right)return;②}}intmain(){stringresult="";bracket(result,n,n);return0;}<①和②中分別應(yīng)該填入（）

選項(xiàng)：

A、bracket(s+'(',left-1,right);bracket(s+')',left,right-1);

B、bracket(s+'(',left,right-1);bracket(s+')',left-1,right);

C、bracket(s+'(',left-1,right-1);bracket(s+')',left,right);

D、bracket(s+'(',left,right);bracket(s+')',left-1,right-1);

本題答案：【bracket(s+'(',left-1,right);bracket(s+')',left,right-1);】5.問題：給定兩個整數(shù)n和k，返回1…n中所有可能的k個數(shù)的組合。以下是程序片段，請選擇正確的語句填入intn=4;intk=2;vectorsolution;voidpermutation(intx,intt){if(t==0){for(inti=0;i<<<'';cout<<<<'';>①中應(yīng)該填入（）

選項(xiàng)：

A、(inti=0;i

B、(inti=1;i<=n;i++）

C、(inti=x;i<=n;i++)

D、(inti=x+