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

【MOOC期末】《算法設(shè)計(jì)與分析》(北京科技大學(xué))期末中國大學(xué)慕課答案算法分析與設(shè)計(jì)期末考試卷1.單選題：下面程序的時(shí)間復(fù)雜度為()。for(i=1,s=0;i<=n;i++){t=1;?for(j=1;j<=i;j++)t=t*j;s=s+t;?}

選項(xiàng)：

A、

B、

C、

D、

答案：【】2.單選題：圖的BFS生成樹的樹高比DFS生成樹的樹高()。

選項(xiàng)：

A、大或相等

B、小

C、小或相等

D、大

答案：【小或相等】3.單選題：若一組記錄的關(guān)鍵碼為(46，79，56，38，40，84)，則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的第一趟結(jié)果為()。

選項(xiàng)：

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.單選題：設(shè)一維數(shù)組中有n個(gè)數(shù)組元素，則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為()。

選項(xiàng)：

A、O(1)

B、O(n)?

C、

D、

答案：【O(1)

】5.單選題：設(shè)輸入序列為1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為()。

選項(xiàng)：

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.單選題：設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑?度之和為()。

選項(xiàng)：

A、40

B、45

C、30

D、20

答案：【45】7.單選題：設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作為()。

選項(xiàng)：

A、top=top+1;?

B、top->next=top;

C、top=top->next;

D、top=top-1;

答案：【top=top->next;】8.單選題：設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點(diǎn)最多有()。

選項(xiàng)：

A、1024

B、256

C、20

D、512

答案：【512】9.單選題：下列說法不正確的是()。

選項(xiàng)：

A、圖的深度遍歷不適用于有向圖

B、圖的深度遍歷是一個(gè)遞歸過程

C、遍歷的基本方法有兩種:深度遍歷和廣度遍歷

D、圖的遍歷是從給定的源點(diǎn)出發(fā)每個(gè)頂點(diǎn)僅被訪問一次

答案：【圖的深度遍歷不適用于有向圖】10.單選題：下面程序段的時(shí)間復(fù)雜度為()。s=i=0;?do{i=i+1;s=s+i;?}while(i<=n);

選項(xiàng)：

A、

B、

C、

D、

答案：【】11.單選題：假設(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]);//每一個(gè)所需要的張數(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])】12.單選題：編寫程序輸出1~1000之間的素?cái)?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】13.單選題：哈弗曼編碼的貪心算法所需的計(jì)算時(shí)間為（）

選項(xiàng)：

A、O（n2）

B、O（nlogn）

C、O（2n）

D、O（n）

答案：【O（nlogn）】14.單選題：能采用貪心算法求最優(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ì)】15.單選題：有一個(gè)矩陣map，它每個(gè)格子有一個(gè)權(quán)值。從左上角的格子開始每次只能向右或者向下走，最后到達(dá)右下角的位置，路徑上所有的數(shù)字累加起來就是路徑和，返回所有的路徑中最小的路徑和。給定一個(gè)矩陣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】16.單選題：動(dòng)態(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]】17.單選題：下列算法中通常以自底向上的方式求解最優(yōu)解的是()

選項(xiàng)：

A、分治法

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

C、貪心法

D、回溯法

答案：【動(dòng)態(tài)規(guī)劃法】18.單選題：用動(dòng)態(tài)規(guī)劃算法解決最大字段和問題,其時(shí)間復(fù)雜性為()

選項(xiàng)：

A、logn

B、n

C、n2

D、nlogn

答案：【n】19.單選題：設(shè)輸入序列是1、2、3、...、n，經(jīng)過棧的作用后輸出序列的第一個(gè)元素是n，則輸出序列中第i個(gè)輸出元素是()。

選項(xiàng)：

A、n-1-i

B、不能確定

C、n-i

D、n+1-i

答案：【n+1-i

】20.單選題：設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則刪除表中第i個(gè)元素需向前移動(dòng)()個(gè)元素。

選項(xiàng)：

A、n-1-i

B、n-i

C、i?

D、n+1-i

答案：【n-i

】21.單選題：分支限界法與回溯法都是在問題的解空間樹T上搜索問題的解，二者（）。

選項(xiàng)：

A、求解目標(biāo)不同，搜索方式相同

B、求解目標(biāo)不同，搜索方式也不同

C、求解目標(biāo)相同，搜索方式不同

D、求解目標(biāo)相同，搜索方式也相同

答案：【求解目標(biāo)不同，搜索方式也不同】22.單選題：解決0/1背包問題可以使用動(dòng)態(tài)規(guī)劃、回溯法和分支限界法,其中不需要排序的是(),需要排序的是(),()。

選項(xiàng)：

A、分支界限法，回溯法，動(dòng)態(tài)規(guī)劃

B、回溯法，動(dòng)態(tài)規(guī)劃，分支限界法

C、動(dòng)態(tài)規(guī)劃，回溯法，分支限界法

D、分支界限法，動(dòng)態(tài)規(guī)劃，回溯法

答案：【動(dòng)態(tài)規(guī)劃，回溯法，分支限界法】23.單選題：使用回溯法求{1,2,3,4,5}的所有排列個(gè)數(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;】24.單選題：背包問題的回溯算法所需的計(jì)算時(shí)間為（）

選項(xiàng)：

A、O(n·2^n)

B、O(nlogn)

C、O(2^n)

D、O(n)

答案：【O(n·2^n)】25.單選題：打出所有的水仙花數(shù)。（水仙花數(shù)是指一個(gè)3位數(shù)，它的每個(gè)位上的數(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】26.單選題：背包問題設(shè)有一背包的容量為5kg，有三件物品的質(zhì)量和價(jià)值如下，問如何才能使裝入背包的物品價(jià)值最大。物品123重量325價(jià)值8512問裝入背包的物品的最大價(jià)值為多少：

選項(xiàng)：

A、8

B、12

C、13

D、25

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

選項(xiàng)：

A、5

B、6

C、7

D、8

答案：【7】28.單選題：選擇排序、插入排序和合并排序算法中，（）算法是分治算法。

選項(xiàng)：

A、選擇排序

B、插入排序

C、合并排序

D、以上全部

答案：【合并排序】29.單選題：機(jī)器人走方格有一個(gè)X*Y的網(wǎng)格，一個(gè)機(jī)器人只能走格點(diǎn)，且只能向右或向下走，要從左上角走到右下角。請?jiān)O(shè)計(jì)一個(gè)算法，計(jì)算機(jī)器人有多少種走法。給定兩個(gè)正整數(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]】30.單選題：生成楊輝三角#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];

】31.單選題：一次考試共考了語文、代數(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】32.單選題：1.警察局抓了a,b,c,d四名偷竊嫌疑犯，其中只有一人是小偷。審問中a說：“我不是小偷?！眀說：“c是小偷?！眂說：“小偷肯定是d?！眃說：“c在冤枉人?！爆F(xiàn)在已知：四個(gè)人中三人說的是真話，一人說的是假話，問到底誰是小偷？請選擇合適語句，完成代碼。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】33.單選題：如下算法的時(shí)間復(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、

答案：【】34.單選題：下列屬于P問題的是。

選項(xiàng)：

A、0-1背包問題

B、旅行商問題

C、最小生成樹

D、漢諾塔問題

答案：【最小生成樹】35.單選題：在下圖所給的有向圖G中，每一邊都有一個(gè)非負(fù)邊權(quán)。要求圖G的從源頂點(diǎn)s到目標(biāo)頂點(diǎn)t之間的最短路徑。問最短路徑的長度為？

選項(xiàng)：

A、8

B、9

C、14

D、7

答案：【8】36.單選題：Dijkstr