窗體頂端

數(shù)據(jù)結(jié)構(gòu)與算法

第17章：數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用

試題1(2017年下半年試題4)

閱讀下列說明和C代碼，回答問題1至問題2,將解答寫在答題紙的對(duì)應(yīng)欄內(nèi)。

【說明】

一個(gè)無向連通圖G點(diǎn)上的哈密爾頓(Hamiltion)回路是指從圖G上的某個(gè)頂點(diǎn)出發(fā)，經(jīng)過

圖上所有其他頂點(diǎn)一次且僅一次，最后回到該頂點(diǎn)的路勁。一種求解無向圖上哈密爾頓回路

算法的基礎(chǔ)私下如下：

假設(shè)圖G存在一個(gè)從頂點(diǎn)V0出發(fā)的哈密爾頓回路VI——V2——V3——...——Vn-1——V0,

算法從頂點(diǎn)V0出發(fā)，訪問該頂點(diǎn)的一個(gè)未被訪問的鄰接頂點(diǎn)VI,接著從頂點(diǎn)VI出發(fā)，訪

問VI一個(gè)未被訪問的鄰接頂點(diǎn)V2,；對(duì)頂點(diǎn)Vi,重復(fù)進(jìn)行以下操作：訪問Vi的一個(gè)未

被訪問的鄰接接點(diǎn)Vi+1；若Vi的所有鄰接頂點(diǎn)均已被訪問，則返回到頂點(diǎn)Vi-1,考慮Vi-1

的下一個(gè)未被訪問的鄰接頂點(diǎn)，仍記為Vi；知道找到一條哈密爾頓回路或者找不到哈密爾頓

回路，算法結(jié)束。

【C代碼】

下面是算法的C語言實(shí)現(xiàn)。

(1)常量和變量說明

n:圖G中的頂點(diǎn)數(shù)

c□口:圖G的鄰接矩陣

K:統(tǒng)計(jì)變量，當(dāng)期已經(jīng)訪問的定點(diǎn)數(shù)為k+1

x[k]:第k個(gè)訪問的頂點(diǎn)編號(hào)，從0開始

VisitedLx[k]]：第k個(gè)頂點(diǎn)的訪問標(biāo)志，0表示未訪問，1表示已訪問

(2)C程序

#include<stido.h>

include<stidb.h>

#defineMAX100

VidoHamilton(intn,intx[MAXJntc[MAX][MAX]){

int;

intvisited[MAX];

intk;

/*初始化x數(shù)組賀visited數(shù)組*/

for(i=0:i<n;i++){

x[i]=0;

visited[i]=0;

)

/*訪問起始頂點(diǎn)*/

k=0

();

x[0]=0

K=k+1

/*訪問其他頂點(diǎn)*/

while(k>=0){

x[k]=x[k]+l;

while(x[k]xn){

if()&&c[x-[k-l]][x[k]=l){/*鄰接頂點(diǎn)x[k]未被訪問過*/

break；

}else(

x[k]=x[k]+1

)

)

if(x[k]<n-l&&(){/*找到一條哈密爾頓回路*/

for(k=0水<n;k++){

prinf(',%d-'',x[k]；/*輸出哈密爾頓回路*/

}

prinf(''%d-'',x[0];

return；

}elseifx[k]<n&&k<n-l){/*設(shè)置當(dāng)期頂點(diǎn)的訪問標(biāo)志，繼續(xù)下一個(gè)頂點(diǎn)*/

()

k=k+l;

}else{/*沒有未被訪問過的鄰接頂點(diǎn)，回退到上一個(gè)頂點(diǎn)*/

x[k]=0；

visitedx[k]=0；

();

}

)

)

【問題1】(10分)

根據(jù)題干說明。填充C代碼中的空(1)~(5).

【問題2】(5分)

根據(jù)題干說明和C代碼，算法采用的設(shè)計(jì)策略為(6),該方法在遍歷圖的頂點(diǎn)時(shí)，采用的

是(7)方法(深度優(yōu)先或廣度優(yōu)先)。

試題分析

哈密頓圖是一個(gè)無向圖，由天文學(xué)家哈密頓提出，由指定的起點(diǎn)前往指定的終點(diǎn)，途中經(jīng)過

所有其他節(jié)點(diǎn)且只經(jīng)過一次。在圖論中是指含有哈密頓回路的圖，閉合的哈密頓路徑稱作哈

密頓回路，含有圖中所有頂點(diǎn)的路徑稱作哈密頓路徑。

回溯法是一種選優(yōu)搜索法，又稱為試探法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到

某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再

走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為“回溯點(diǎn)”。在包含問題的所有解的

解空間樹中，按照深度優(yōu)先搜索的策略，從根結(jié)點(diǎn)出發(fā)深度探索解空間樹。當(dāng)探索到某一結(jié)

點(diǎn)時(shí)，要先判斷該結(jié)點(diǎn)是否包含問題的解，如果包含，就從該結(jié)點(diǎn)出發(fā)繼續(xù)探索下去，如果

該結(jié)點(diǎn)不包含問題的解，則逐層向其祖先結(jié)點(diǎn)回溯(其實(shí)回溯法就是對(duì)隱式圖的深度優(yōu)先搜

索算法)。若用回溯法求問題的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有可行的子樹都要

已被搜索遍才結(jié)束。而若使用回溯法求任一個(gè)解時(shí)，只要搜索到問題的一個(gè)解就可以結(jié)束。

算法題歷來都被認(rèn)為是比較難的題，一個(gè)程序開發(fā)人員都不喜歡看別人的代碼。但是要得分

也不是太難。

問題2比較容易得分，而且第二空就是個(gè)二選一的填空。只要了解到回溯法的相關(guān)原理，基

本可以得滿分。對(duì)于問題1就需要花一些心思，去讀懂題干和代碼，但是這里的第1空和第

5空也是比較容易發(fā)挖出來的空。第一空是初始化第一個(gè)結(jié)點(diǎn)，第五空是此路不通，得回走,

所以得退回。。

試題答案

(4)問題1：

1、visited[O]=1

2、visited[x[k]]==0

3、visited[x[k]]==1

4、visited[x[k]]=1

5、k=k-1

問題2：

6、回溯法

7、深度優(yōu)先

試題2(2017年上半年試題4)

閱讀下列說明和C代碼，回答問題1至問題3,將解答寫在答題紙的對(duì)應(yīng)欄內(nèi)。

【說明】

假幣問題：有n枚硬幣，其中有一枚是假幣，己知假幣的重量較輕?，F(xiàn)只有一個(gè)天平，要求

用盡量少的比較次數(shù)找出這枚假幣。

【分析問題】

將n枚硬幣分成相等的兩部分：

⑴當(dāng)n為偶數(shù)時(shí)，將前后兩部分，即l...n/2和n/2+l...O,放在天平的兩端，較輕的一端里

有假幣，繼續(xù)在較輕的這部分硬幣中用同樣的方法找出假幣：

(2)當(dāng)n為奇數(shù)時(shí)，將前后兩部分，即l..(n-l)/2和(n+l)/2+L..O,放在天平的兩端，較輕的一

端里有假幣，繼續(xù)在較輕的這部分硬幣中用同樣的方法找出假幣；若兩端重量相等，則中間

的硬幣，即第(n+l)/2枚硬幣是假幣。

【C代碼】

下面是算法的C語言實(shí)現(xiàn)，其中：

coins[]：硬幣數(shù)組

first,last：當(dāng)前考慮的硬幣數(shù)組中的第一個(gè)和最后一個(gè)下標(biāo)

#include<stdio.h>

intgetCounterfeitCoin(intcoins[],intfirst,intlast)

(

intfirstSum=0,lastSum=0;

int1;

lf(first==last-l){/*只剩兩枚硬幣*/

if(coins[first]<coins[last])

returnfirst;

returnlast;

)

if((last-first+1)%2==0){/*偶數(shù)枚硬幣*/

for(i=first;1<(1);i++){

firstSum+=coins[i];

)

for(i=first+(last-first)/2+l;i<last+l;i++){

lastSum+=coins[i];

}

if(2){

ReturngetCounterfeitCoin(coins,first,first+(last-first)/2;)

}else{

ReturngetCounterfeitCoin(coins,first+(last-first)/2+l,last;)

)

}

else{/*奇數(shù)枚硬幣*/

For(i=first;i<first+(last-first)/2;i++){

firstSum+=coins[i];

)

For(i=first+(last-first)/2+l;i<last+l;i++){

lastSum+=coins[i];

)

lf(firstSum<lastSum){

returngetCounterfeitCoin(coins,first,first+(last-first)/2-l);

}elseif(firstSum>lastSum){

returngetCounterfeitCoin(coins,first+(last-first)/2-l,last);

}else{

Return(3)

)

)

}

【問題一】

根據(jù)題干說明，填充C代碼中的空(1)-(3)

【問題二】

根據(jù)題干說明和C代碼，算法采用了()設(shè)計(jì)策略。

函數(shù)getCounterfeitCoin的時(shí)間復(fù)雜度為()(用。表示)。

【問題三】

若輸入的硬幣數(shù)為30,則最少的比較次數(shù)為()，最多的比較次數(shù)為()。

試題分析

若輸入30個(gè)硬幣，找假硬幣的比較過程為：

第1次：15比15,此時(shí)能發(fā)現(xiàn)假幣在15個(gè)的范圍內(nèi)。

第2次：7比7,此時(shí)，如果天平兩端重量相同，則中間的硬幣為假幣，此時(shí)可找到

假幣，這是最理想的狀態(tài)。

第3次：3比3,此時(shí)若平衡，則能找出假幣，不平衡，則能確定假幣為3個(gè)中的1個(gè)。

第4次：1比1,到這一步無論是否平衡都能找出假幣，此時(shí)為最多比較次數(shù)。

參考答案

試題答案

(4)問題1

(1)first+(last-first)/2或(first+last)/2

(2)firstSum<lastSum

(3)first+(last-first)/2或(first+last)/2

問題2

(4)分治法

(5)0(nlogn)

問題3

(6)2(7)4

試題3(2016年下半年試題4)

閱讀下列說明和C代碼，回答問題1至問題3,將解答寫在答題紙的對(duì)應(yīng)欄內(nèi)。

【說明】

模式匹配是指給定主串t和子串s,在主串t中尋找子串s的過程，其中s稱為模式。如

果匹配成功，返回s在t中的位置，否則返回-1。

KMP算法用next數(shù)組對(duì)匹配過程進(jìn)行了優(yōu)化。KMP算法的偽代碼描述如下：

1.在串t和串s中，分別設(shè)比較的起始下標(biāo)i=j=0。

2.如果串t和串S都還有字符，則循環(huán)執(zhí)行下列操作：

(1)如果j=-l或者t[i]=s[j],則將i和j分別加1,繼續(xù)比較t和s的下一個(gè)字符；

(2)否則，將j向右滑動(dòng)到next。]的位置，BPj=next[j]o

3.如果s中所有字符均已比較完畢，則返回匹配的起始位置(從1開始)；否則返回-1.

其中，next數(shù)組根據(jù)子串s求解。求解next數(shù)組的代碼已由get_next函數(shù)給出。

【C代碼】

(1)常量和變量說明

t,s：長度為憫粕Is的字符串

next:next數(shù)組，長度為Is

(2)C程序

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

/*求next口的值*/

voidget_next(int*nextzchar*s,intIs){

inti=0,j=-l;

next[0]=?1;/*初始化next[0]*/

while(i<還有字符*/

if(j二二二=s[j]){/*匹配*/

j++；

i++；

if(s[i]==sU])

next[i]=next[j];

else

Next[i]=j;

else

j=next[j];

)

)

intkmp(int*next,char*tzchar*s,intIt,intIs)

(

Inti=OJ=0;

while(i<It&&(1)){

if(j==-lII⑵){

i++；

j++；

}else

(3);

)

if(j>=Is)

return(4);

else

return-1;

}

【問題1】(8分)

根據(jù)題干說明，填充C代碼中的空(1)?(4).

【問題2】(2分)

根據(jù)題干說明和C代碼，分析出kmp算法的時(shí)間復(fù)雜度為(5)(主串和子串的長度分別為

It和Is,用。符號(hào)表示)。

【問題3】(5分)

根據(jù)C代碼，字符串“BBABBCAC”的next數(shù)組元素值為(6)(直接寫素值，之間用逗號(hào)

隔開)。若主串為"AABBCBBABBCACCD”，子串為“BBABBCAC"，則函數(shù)Kmp的返回值是

(7)?

試題分析

本題問題1根據(jù)KMP算法的偽代碼描述進(jìn)行推導(dǎo)。

根據(jù)偽代碼中第2步可以推導(dǎo)(1)是判斷字符串s是否還有字符，即j<ISoi表示字符串t

的下標(biāo)，j表示字符串s的下標(biāo)。

根據(jù)偽代碼第2.1步可以推導(dǎo)(2)是判斷字符串t和字符串s當(dāng)前位置的字符是否相同，即

t[i]==s[j]?

根據(jù)偽代碼第2.2步可以推導(dǎo)(3)是當(dāng)?shù)?.1步判斷條件不滿足時(shí)，改變j所指向的字符位

置。即調(diào)用函數(shù)get_next(next,s,is),_6.j=next[j]。

根據(jù)偽代碼第3步可以推導(dǎo)(4)是返回匹配的起始位置。由于當(dāng)前i所指向字符串中匹配

子串的最后一個(gè)字符的位置，且已知子串的長度為Is。(4)的代碼為i+1-ls。

本題問題2是計(jì)算KMP算法的復(fù)雜度。算法的復(fù)雜度一般考慮最壞情況，那么在子串讀到

Is及主串讀到It的時(shí)候是最壞情況。所以復(fù)雜度是O(lt+ls)

本題問題3中已知字符串“BBABBCAC”，則根據(jù)get_next()函數(shù)可以求得next數(shù)組的元素

值為[-1,-1,1,-1,-1,2,0,0]。并計(jì)算得到起始位置為6o

試題答案

(4)問題1：

(1)：j<ls;

(2)：t[i]==s[j]；

(3):get_next(next,s,Is);

j=next[j];

(4)：i+l-ls;

問題2：O(lt+ls)

問題3：(6)：[-1,-1,1,-1,-1,2,0,0],(7)6。

試題4(2016年上半年試題4)

試題四(共15分)

閱讀下列說明和C代碼，回答問題1至問題3,將解答寫在答題紙的對(duì)應(yīng)欄內(nèi)。

【說明】

在一塊電路板的上下兩端分別有n個(gè)接線柱。根據(jù)電路設(shè)計(jì)，用(i,"(i))表示將上端接線

柱i與下端接線柱”⑴相連，稱其為該電路板上的第i條連線。如圖4-1所示的n⑴排列為

{8,7,4,2,5,1,9,3,10,6}。對(duì)于任何lWi<jWn,第i條連線和第j條連線相交的充要條件是加(i)>

"0)。

圖4-1電路布線不意

在制作電路板時(shí)，要求將這n條連線分布到若干絕緣層上，在同一層上的連線不相交。

現(xiàn)在要確定將哪些連線安排在一層上，使得該層上有盡可能多的連線，即確定連線集Nets={(i,

"⑴)，lWi〈n}的最大不相交子集。

【分析問題】

記N(i,j)={t|(t,災(zāi)(t))GNets,tWi,n(t)Wj}。N(i,j)的最大不相交子集為MNS(iJ),

size(i,j)=|MNS(i,j)|?

經(jīng)分析，該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。對(duì)規(guī)模為n的電路布線問題，可以構(gòu)造如下遞歸

式：

⑴當(dāng)5—)寸篇況

/、、“a/、size(i-lj)j<欣i)

(2)當(dāng)i>l時(shí)，siz&Lj)=<9

maxisized-7,j),sizefi-1,Xz)-l)+1}其他情況

【c代碼】

下面是算法的c語言實(shí)現(xiàn)。

(1)變量說明

size[i]U]：上下端分別有i個(gè)和j個(gè)接線柱的電路板的第一層最大不相交連接數(shù)

pi[i]：n(i),下標(biāo)從1開始

(2)C程序

include"stdlib.h"

^include<stdio.h>

#defineN10/*問題規(guī)模*/

intm=0；/*牢記錄最大連接集合中的接線柱*/

VoidmaxNum(intpi[],intsize[N+l][N+l],intn){/*求最大不相交連接數(shù)*/

inti,j;

for(j=0;j<pi[l];j++)size[l][j]=0;/*當(dāng)j<“⑴時(shí)*/

for(j=pi[l];j<=n;j++)(1);/*當(dāng)j>=n(1)時(shí)*/

for(i=2;i<n;i++){

for(j=0;j<pi[i];j++)(2);/*當(dāng)j<pi[i]時(shí)*/

for(j=pi[i];j<=n；j++){/*當(dāng)j>=c[i]時(shí)，考慮兩種情況*/

size[i][j]=size[i-l][j]>=size[i-l][pi[i]-l]+l?size[i-l][j]:size[i-l][pi[i]-l]+l;

}

)

/*最大連接數(shù)*/

size[n][n]=size[n-l][n]>=size[n-l][pi[n]-l]+l?size[n-l][n]：size[n-l][pi[n]-l]+l;

)

/*構(gòu)造最大不相交連接集合，net[i]表示最大不相交子集中第i條連線的上端接線柱的序

號(hào)*/

voidconstructSet(intpi[],intsize[N+l][N+l],intn,intnet[n]){

inti,j=n;

m=0；

for(i=n;i>l;i-){/*從后往前*/

if(size[i][j]!=size[i-l][j]){/*(i,pi[i】)是最大不相交子集的一條連線*/

(3);/*將i記錄到數(shù)組net中，連接線數(shù)自增1*/

j=pi[i]-l；/*更新擴(kuò)展連線柱區(qū)間*/

}

}

if(j>=pi[l])net[m++]=l;/*當(dāng)i=l時(shí)*/

【問題1】（6分）

根據(jù)以上說明和C代碼，填充C代碼中的空（1）?（3）。

【問題2】（6分）

據(jù)題干說明和以上C代碼，算法采用了（4）算法設(shè)計(jì)策略。

函數(shù)maxNum和constructSet的時(shí)間復(fù)雜度分別為（5）和（6）（用。表示）。

【問題3】（3分）

若連接排列為{8,7,4,2,5,1,9,3,10,6},即如圖4-1所示，則最大不相交連接數(shù)為（7）

包含的連線為（8）（用（i,n（i））的形式給出）。

試題分析

這個(gè)是動(dòng)態(tài)規(guī)劃問題，不想交的平行線，算法思路來才能完整。

設(shè)為上端接線柱i與下端接線柱j前的最大不相交子集，則：

若i與j不相連，貝Ii與j前的最大不想交子集等于i與j-1前或i-1與j前的最大不相交子

集的最大值，即a[i][j]=max(a[i][j-1],a[i-l][j])

若i與j相連,則i與j前的最大不想交子集等于i-1與j-1前的最大不想交子集加1,即a[i]U]

=a[i-l]U-l]+l

題目的意思就是要求出，沒有交叉的這種連線的數(shù)量達(dá)到最大的情況。此時(shí)，有4條這樣的

線不會(huì)交叉，所以是大不相交子集連接數(shù)為4。如果你能找到5條這樣不交叉的線，則是5。

就這個(gè)意思。

圖4-1電路布線示意

試題答案

(4)

【問題1】

(1)size[i][j]=l

(2)size[i][j]=size[i-l][j]

(3)net[m++]=i;

【問題2】

(4)動(dòng)態(tài)規(guī)劃算法

(5)0(n2)

(6)0(n)

【問題3】

(7)4

(8)(3,TI(3),(5,Jt(5)),(7,Jt(7)),(9,n(9))

或：(3,4)，(5,5)，(7,9),(9,10)

試題5(2015年下半年試題4)

閱讀下列說明和C代碼，回答問題1至問題3,將解答寫在答題紙的對(duì)應(yīng)欄內(nèi)。

【說明】

計(jì)算兩個(gè)字符串x和y的最長公共子串(LongestCommonSubstring)o

假設(shè)字符串x和字符串y的長度分別為m和n,用數(shù)組c的元素記錄x中前i個(gè)字

符和y中前j個(gè)字符的最長公共子串的長度。

滿足最優(yōu)子結(jié)構(gòu)，其遞歸定義為：

+1茬)。且j>-1]=y[/-l]

C[i][f]=

0其它

計(jì)算所有c[i][j](OWiWm,0WjWn)的值，值最大的即為字符串x和y的最長

公共子串的長度。根據(jù)該長度即i和j,確定一個(gè)最長公共子串。

【C代碼】

⑴常量和變量說明

x,y：長度分別為m和n的字符串

c[i]U]：記錄x中前i個(gè)字符和v中前j個(gè)字符的最長公共子串的長度

max：x和y的最長公共子串的長度

maxi,maXj：分別表示x和y的某個(gè)最長公共子串的最后一個(gè)字符在x和y中的位置(序

號(hào))

⑵C程序

#include<stdio.h>

ftinclude<string.h>

intc[50][50];

intmaxi;

intmaxj;

intlcs(char*x,intm,char*y,intn){

inti,j;

intmax=0;

maxi=0;

maxj=0;

for(i=0;i<=m;i++)c[i][0]=0;

for(i=1;i<=n;i++)c[0][i]=0;

for(i=1;i<=m;i++){

for(j=l;j<=n;j++){

if((1)){

c[i][j]=c[i-l][j-1]+1；

if(max<c[i][j]){

(2)；

maxi=i;

maxj=j;

)

}

else(3);

)

)

returnmax;

)

voidprintLCS(intmax,char*x){

inti=0;

if(max==0)return;

for((4);i<maxi;i++)

printf("%c"zx[i]);

)

voidmain(){

char*x="ABCADAB";

char*y="BDCABA";

intmax=0;

intm=strlen(x);

intn=strlen(y);

max=lcs(x,m,y/n);

printLCS(max,x);

}

【問題1】(8分)

根據(jù)以上說明和C代碼，填充C代碼中的空(1)?(4)。

【問題2】(4分)

根據(jù)題干說明和以上C代碼，算法采用了(5)設(shè)計(jì)策略。

分析時(shí)間復(fù)雜度為(6)(用。符號(hào)表示).

【問題3】(3分)

根據(jù)題干說明和以上C代碼,輸入字符串x="ABCADAB',，y="BDCABA",則輸出為(7)?

試題分析

首先對(duì)于C語言算法題,一般的解題思路是先解決除程序填空以外的問題，這些問題弄清楚,

有利于程序填空部分的分析。

第一步，分析程序所采用的算法，常見的算法包括：分治法、動(dòng)態(tài)規(guī)劃法、回溯法、貪心法。

本題中要求的是兩個(gè)串的最長公共子串，在程序中采用了數(shù)組來記錄子問題的中間結(jié)果，這

一特征與動(dòng)態(tài)規(guī)劃法的做法非常吻合，所以應(yīng)選動(dòng)態(tài)規(guī)劃法。

第二步，解決“輸入字符串x="ABCADAB',，y="BDCABA",則輸出為(7)”的問題，該問

題相對(duì)容易解決，因?yàn)轭}目已告知程序的作用是求最長公共子串，而且從程序的輸出函數(shù)可

以看出，要輸出的，只有子串，沒有其它信息，所以我們只需要手動(dòng)求兩個(gè)串的公共子串，

并寫出答案即可。兩個(gè)串第一個(gè)公共子串明顯是“AB”，所以輸出的結(jié)果為“AB”。

第三步，求時(shí)間復(fù)雜度，由于程序中最多雙重循環(huán)，其中外層循環(huán)的規(guī)模為m,而內(nèi)層循環(huán)

的規(guī)模為n,所以時(shí)間復(fù)雜度為0(m*n)。

第四步，也是最難的一步，是解決程序填空的問題。動(dòng)態(tài)規(guī)劃的問題，一般都會(huì)給出遞歸定

義式，這個(gè)式子，往往是多個(gè)空的關(guān)鍵點(diǎn)。以本題為例，前3空均與式子相關(guān)，式子中明確

說明了川時(shí)的值是多少，而其它情況均等于0,此時(shí)可以了解到前3空

的答案。而第4空是用于打印結(jié)果，由于maxi記錄了子串末尾+1的位置信息，子串長度為

max,所以用maxi-max定位至子串開始位置，以便打印子串。

試題答案

(4)【問題1】

⑴x[i-l]==y[j-l]

(2)max=c[i][j]

(3)c[i][j]=O

(4)i=maxi-max

【問題2】

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

(6)O(m*n)

【問題3】

(7)AB

試題6(2015年上半年試題4)

閱讀下列說明和C代碼，回答問題1至問題3,將解答寫在答題紙的對(duì)應(yīng)欄內(nèi)。

【說明】

n-皇后問題是在n行n列的棋盤上放置n個(gè)皇后，使得皇后彼此之間不受攻擊，其規(guī)則

是任意兩個(gè)皇后不在同一行、同一列和相同的對(duì)角線上。

擬采用以下思路解決n-皇后問題：第i個(gè)皇后放在第i行。從第一個(gè)皇后開始，對(duì)每個(gè)皇

后，從其對(duì)應(yīng)行(第i個(gè)皇后對(duì)應(yīng)第i行)的第一列開始嘗試放置，若可以放置，確定該位

置，考慮下一個(gè)皇后；若與之前的皇后沖突，則考慮下一列；若超出最后一列，則重新確定

上一個(gè)皇后的位置。重復(fù)該過程，直到找到所有的放置方案。

【C代碼】

下面是算法的C語言實(shí)現(xiàn)。

⑴常量和變量說明

pos：一維數(shù)組，pos[i]表示第i個(gè)皇后放置在第i行的具體位置

count：統(tǒng)計(jì)放置方案數(shù)

i,j>k：變量

N：皇后數(shù)

(2)C程序

#include<stdio.h>

#include<math.h>

#defineN4

/*判斷第k個(gè)皇后目前放置位置是否與前面的皇后沖突*/

inisplace(intpos[],intk){

inti;

for(i=l;i<k;i++){

if((1)||fabs(i-k)—fabs(pos[i]-pos[k])){

return0;

)

)

return1;

intmain(){

intij,count=l;

intpos[N+l]；

〃初始化位置

for(i=l;i<=N;i++){

pos[i]=0;

)

(2)；

while(j>=l){

pos[j]=pos[j]+l；

/*嘗試擺放第i個(gè)皇后*/

while(pos[j]<=N&&(3)_){

pos[j]=pos[j]+l;

)

/*得到一個(gè)擺放方案*/

if(pos[j]<=N&&j------N){

printf("方案％d:，count++);

for(i=l;i<=N;i++){

printf("%d",pos[i]);

)

printf("\n");

}

/*考慮下一個(gè)皇后*/

if(pos[j]<=N&&(4)){

j=j+l；

}else{〃返回考慮上一個(gè)皇后

pos[j]=0;

(5);

)

}

return1;

)

【問題1】(10分)

根據(jù)以上說明和C代碼，填充C代碼中的空(1)?(5)。

【問題2】(2分)

根據(jù)以上說明和C代碼，算法采用了(6)設(shè)計(jì)策略。

【問題3】(3分)

上述C代碼的輸出為：

(7)。

試題分析

本題考查算法設(shè)計(jì)和C程序設(shè)計(jì)語言的相關(guān)知識(shí)。

此類題目要求考生認(rèn)真閱讀題目，理解算法思想，并思考將算法思想轉(zhuǎn)化為具體的程序設(shè)計(jì)

語言的代碼。

【問題1】

根據(jù)題干描述?？?1)所在的代碼行判斷皇后合法放置的約束條件，即不在同一行，這通

過把第i個(gè)皇后放在第i行實(shí)現(xiàn)，條件"fabs(i-k)=fabs(pos[i]-pos[k])"判斷的是當(dāng)前擺放的

皇后是否與之前擺放的皇后在同一對(duì)角線上。因此，空(1)判斷的是當(dāng)前擺放的皇后是否

和之前擺放的皇后在同一列上，即應(yīng)填入"pos[i]=pos[k]''。

根據(jù)算法思想和主函數(shù)上下文，空(2)處應(yīng)該考慮第1個(gè)皇后，即初始化j為1,空(2)

填寫空(3)所在的行是判斷放置第j個(gè)皇后的位置是否合適，"posU]<=N"表示在

該行的合法列上，但還需要進(jìn)一步判斷是否與前面的皇后有沖突，根據(jù)滿足條件后的語句，

嘗試放入下一列，因此空（3）處填入"!isplace（pos,j）?根據(jù)前面的注釋，空（4）所在的

行是考慮下一個(gè)皇后，其條件是，當(dāng)前皇后找到了合適的位置，而且還存在下一個(gè)皇后，因

此空（4）處應(yīng)填入"j<N"。根據(jù)下面的注釋，若當(dāng)前皇后沒有找到合適的位置，則應(yīng)回溯,

即再次考慮上一個(gè)皇后的位置，因此空（5）處填入

【問題2】

從上述題干的敘述和C代碼很容易看出，從第一個(gè)皇后開始，對(duì)每個(gè)皇后總是從第一個(gè)位

置開始嘗試，找到可以放置的合法位置：若某個(gè)皇后在對(duì)應(yīng)的行上沒有合法位置，則回溯到

上一個(gè)皇后，嘗試將上一個(gè)皇后放置另外的位置。這是典型的深度優(yōu)先的系統(tǒng)搜索方式，即

回溯法的思想。

【問題3】

四皇后問題的答案為：

方案1：2413

方案2：3142

如表4-1所示：

表4-1

方案1

方案2

試題答案

(4)

【問題1】

(1)pos[i]==pos[k]

(2)j=l

(3)isplace(posj)==0

(4)j<N

(5)j=j-l

【問題2】

(6)回溯法

【問題3】

(7)

方案1:2413

方案2：3142

試題7(2014年下半年試題4)

閱讀下列說明和C代碼，回答問題1至問題3,將解答寫在答題紙的對(duì)應(yīng)欄內(nèi)。

【說明】

計(jì)算一個(gè)整數(shù)數(shù)組a的最長遞增子序列長度的方法描述如下：

假設(shè)數(shù)組a的長度為n,用數(shù)組b的元素可口記錄以a[i](0<i<n)為結(jié)尾元素的最長遞增予

序列的長度，則數(shù)組a的最長遞增子序列的長度為黑伯口)；其中b[i]滿足最優(yōu)子結(jié)構(gòu)，

可遞歸定義為：

力[0]=1

<5口]=max{可幻}+1

區(qū)國

域

【C代碼】

下面是算法的C語言實(shí)現(xiàn)。

(1)常量和變量說明

a：長度為n的整數(shù)數(shù)組，待求其最長遞增子序列

b：長度為n的數(shù)組，b葉記錄以a「](0Wi<n)為結(jié)尾元素的最長遞增子序列的長

度，其U10Wi<n

len：最長遞增子序列的長度

i,j：循環(huán)變量

temp：臨時(shí)變量

(2)C程序

#include<stdio.h>

intmaxL(int*b,intn){

inti,temp=0;

for(i=0;i<n;i++){

if(b[i]>temp)

temp=b[i];

)

returntemp;

)

intmain(){

intn,a[100],b[100],i,j,len;

scanf("%d",&n);

for(i=0;i<n;i++){

scanf("%d",&a[i]);

)

(1)；

for(i=l;i<n;i++){

for(j=0,len=0;(2);j++){

if((3)&&len<b[j])

len=b[j];

)

(4)

,,

Printf("len:%d\n/maxL(b,n));

printf("\n")；

【問題1】（8分）

根據(jù)說明和C代碼，填充C代碼中的空（1）?（4）,

【問題2】（4分）

根據(jù)說明和C代碼，算法采用了（5）設(shè)計(jì)策略，時(shí)間復(fù)雜度為（6）（用。符號(hào)表示）。

【問題3】（3分）

已知數(shù)組a={3,10,5,15,6,8},根據(jù)說明和C代碼，給出數(shù)組b的元素值。

試題分析

本題考察算法設(shè)計(jì)與分析技術(shù)以及算法的C語言實(shí)現(xiàn)，是比較傳統(tǒng)的題目，要求考生細(xì)心分

析題目中所描述的內(nèi)容。

（1）根據(jù)題中說明，b數(shù)組記錄最長遞增子序列的長，故應(yīng)初始化b[O]=l,這是第一問的

答案。兩重for循環(huán)中，第一重是從a數(shù)組的第二個(gè)元素開始，考慮每個(gè)子數(shù)組的最

長遞增子序列的長度，第二重是具體的計(jì)算過程。考慮子數(shù)組其最長遞增子序列的

長度應(yīng)該等于子數(shù)組中的比元素a[i）小的元素的最長遞增子序列的長度加1,當(dāng)然，

可能存在多個(gè)元素比元素a[i]小，那么存在多個(gè)最長遞增子序列的長度，此時(shí)，取最大者。

因此，空（2）填寫“j<i"，即考慮子數(shù)組a。.川第三問為a[j]<=a[i],第四問為則=len+l。

（2）算法將待求解問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到

原問題的解。使用的是動(dòng)態(tài)規(guī)劃的思想。時(shí)間復(fù)雜度計(jì)算最壞情況下的運(yùn)算次數(shù)，最壞情況

時(shí)i和j都從1跑到n,故運(yùn)算n的平方次。算法的時(shí)間復(fù)雜度為0（n2）o

（3）初始b⑼=1,a[0]=3,a[l]=10進(jìn)入時(shí)b[l]=2,a⑵=5進(jìn)入時(shí)有3、5的序列故b[2]=2,

a[3]=15進(jìn)入時(shí)有3、10、15,故子序列為3,a⑷=6時(shí)有子序列3、5、6,故為3,當(dāng)最后

一個(gè)元素8進(jìn)入時(shí)有3、5、6、8,故b⑸=4。所以b=[l,2,2,3,3,4]。

試題答案

（4）

【問題1】

（1）b[0]=l

（2）j<i

（3）a[j]<=a[i]

（4）b[i]=len+l

【問題2】

（5）動(dòng)態(tài)規(guī)劃法

（6）0（n2）

【問題3】

b={l,2,2,3,3,4}

試題8（2014年上半年試題4）

閱讀下列說明和C代碼，回答問題1至問題3,將解答寫在答題紙的對(duì)應(yīng)欄內(nèi)。

【說明】

采用歸并排序?qū)個(gè)元素進(jìn)行遞增排序時(shí)，首先將n個(gè)元素的數(shù)組分成各含n/2個(gè)元素

的兩個(gè)子數(shù)組，然后用歸并排序?qū)蓚€(gè)子數(shù)組進(jìn)行遞歸排序，最后合并兩個(gè)已經(jīng)排好序的子

數(shù)組得到排序結(jié)果。

下面的C代碼是對(duì)上述歸并算法的實(shí)現(xiàn)，其中的常量和變量說明如下：

arr：待排序數(shù)組

p,q,r：一個(gè)子數(shù)組的位置從p到q,另一個(gè)子數(shù)組的位置從q+l至h

begin,end：待排序數(shù)組的起止位置

left,right：臨時(shí)存放待合并的兩個(gè)子數(shù)組

nl,n2：兩個(gè)子數(shù)組的長度

i,j,k：循環(huán)變量

mid：臨時(shí)變量

【C代碼】

#inciude<stdio.h>

#inciude<stdlib.h>

#defineMAX65536

voidmerge(intarr[],intp,intqjntr){

int*left,*right;

intnl,n2,ijk;

nl=q-p+l;

n2=r-q;

if((left=(int*)malloc((nl+l)*sizeof(int)))=NULL){

perror(Hmallocerror");

exit(l);

}

if((right=(int*)malloc((n2+l)*sizeof(int)))=NULL){

perror(Hmallocerror");

exit(l);

)

for(i=0;i<nl;i++){

left[i]=arr[p+i]；

)

left[i]=MAX；

for(i=0;i<n2;i++){

right[i]=arr[q+i+l]

)

right[i]=MAX;

i=0;j=0;

for(k=p;(1);k++){

if(left[i]>right[j]){

(2);

j++；

}else{

arr[k]=left[i]；

i++;

)

)

voidmergeSort(intarr[]Jntbeginjntend){

intmid;

if((3)){

mid=(begin+end)/2;

mergeSortfarr,begin,mid);

(4);

merge(arr,begin,mid,end);

)

)

【問題1】

根據(jù)以上說明和C代碼，填充1-4?

【問題2】

根據(jù)題干說明和以上C代碼，算法采用了(5)算法設(shè)計(jì)策略。

分析時(shí)間復(fù)雜度時(shí)，列出其遞歸式位(6),解出漸進(jìn)時(shí)間復(fù)雜度為(7)(用。符號(hào)表

示)?？臻g復(fù)雜度為(8)(用。符號(hào)表示)。

【問題3】

兩個(gè)長度分別為nl和n2的已經(jīng)排好序的子數(shù)組進(jìn)行歸并，根據(jù)上述C代碼，則元素之

間比較次數(shù)為(9)。

試題分析

根據(jù)題目中的參數(shù)說明,voidmergefintarr[],intp,intq,intr)是將數(shù)組arr[p...q]和數(shù)組

arr[q+l...r]進(jìn)行合并成一個(gè)排序的數(shù)組，因此合并之后數(shù)組的長度為r-q+l,也就是k<=r；數(shù)

組arr存入子數(shù)組arr[p...q]、arr[q+l...r]當(dāng)前進(jìn)行比較的最小值，因此當(dāng)right。]時(shí)，數(shù)

組arr中存入right。],即arr[k]=right[j]；

是指將數(shù)組遞歸進(jìn)行劃分，直到分成多個(gè)由一個(gè)

voidmergeSort(intarr[],intbegin,intend)arr

元素組成的子數(shù)組時(shí)，停止劃分，此時(shí)也就是begin==end,因此(3)處為begin<end,也

就是只要begin!=end則繼續(xù)劃分。劃分的時(shí)候每次分成兩半，兩半再分別遞歸，因此

mergeSort(arr,begin,mid);mergeSort(arGmid+l,end);；

很明顯歸并排序使用的分治算法，每次講數(shù)組分割成兩個(gè)小的子數(shù)組。

假設(shè)對(duì)n個(gè)元素的數(shù)組進(jìn)行歸并排序時(shí)間復(fù)雜度為T(n),則分成兩個(gè)小的子數(shù)組后分別進(jìn)行

排序所需的時(shí)間為T(n/2),兩個(gè)子數(shù)組則時(shí)間復(fù)雜度為2T(n/2),再加上歸并的時(shí)間0(n),

即可得出答案。

試題答案

(4)

【問題1】(8分)

(1)k<=r

(2)arr[k]=right[j]

(3)begin<end

(4)mergeSort(arr,mid+l,end)

【問題2】(5分)

(5)分治

(6)T(n)=2T(n/2)+O(n)

(7)O(nlogn)

(8)0(n)

【問題3】(2分)

(9)nl+n2

試題9(2013年下半年試題4-7)

閱讀下列說明和C代碼，回答問題1至問題3,將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。

【說明】

某工程計(jì)算中要完成多個(gè)矩陣相乘(鏈乘)的計(jì)算任務(wù)。

兩個(gè)矩陣相乘要求第一個(gè)矩陣的列數(shù)等于第二個(gè)矩陣的行數(shù)，計(jì)算量主要由進(jìn)行乘法運(yùn)

算的次數(shù)決定。采用標(biāo)準(zhǔn)的矩陣相乘算法，計(jì)算AmXn*BnXp,需要m*n*p次乘法運(yùn)算。

矩陣相乘滿足結(jié)合律，多個(gè)矩陣相乘，不同的計(jì)算順序會(huì)產(chǎn)生不同的計(jì)算量。以矩陣A110

X100,A2100X5,A35X50三個(gè)矩陣相乘為例，若按(A1*A2)*A3計(jì)算，則需要進(jìn)行

10*100*5+10*5*50=7500次乘法運(yùn)算；若按Al*(A2*A3)計(jì)算，則需要進(jìn)行

100*5*50+10*100*50=75000次乘法運(yùn)算。可見不同的計(jì)算順序?qū)τ?jì)算量有很大的影響。

矩陣鏈乘問題可描述為：給定n個(gè)矩陣<A1,A2,….An>,矩陣Ai的維數(shù)為pi-IXpi,其中

確定一種乘法順序，使得這個(gè)矩陣相乘時(shí)進(jìn)行乘法的運(yùn)算次數(shù)最少。

i=l,2,-.non

由于可能的計(jì)算順序數(shù)量非常龐大，對(duì)較大的n,用蠻力法確定計(jì)算順序是不實(shí)際的。

經(jīng)過對(duì)問題進(jìn)行分析，發(fā)現(xiàn)矩陣鏈乘問題具有最優(yōu)子結(jié)構(gòu)，即若Al*A2*-*An的一個(gè)最優(yōu)

計(jì)算順序從第k個(gè)矩陣處斷開,即分為Al*A2*-.Ak和Ak+l*Ak+2*…*An兩個(gè)子問題,則

該最優(yōu)解應(yīng)該包含A1*A2*…*Ak的一個(gè)最優(yōu)計(jì)算順序和Ak+l*Ak+2*--An的一個(gè)最優(yōu)計(jì)算順

序。據(jù)此構(gòu)造遞歸式，

「」「[J0近i=J

〔而叫皿.cos但㈤+cosf[A+1][j]+孫*%*p*ifi<j

其中，cost[i][j]表示Ai+l*Ai+2*...Aj+l的最優(yōu)計(jì)算的計(jì)算代價(jià)。最終需要求解cost[0][n-l]。

【C代碼】

算法實(shí)現(xiàn)采用自底向上的計(jì)算過程。首先計(jì)算兩個(gè)矩陣相乘的計(jì)算量，然后依次計(jì)算3

個(gè)矩陣、4個(gè)矩陣、…、n個(gè)矩陣相乘的最小計(jì)算量及最優(yōu)計(jì)算順序。下面是算法的C語言

實(shí)現(xiàn)。

(1)主要變量說明

n：矩陣數(shù)

seq[J：矩陣維數(shù)序列

cost口口：二維數(shù)組，長度為n*n,其中元素cost[i][j]表示Ai+l*Ai+2*-Aj+l的最優(yōu)計(jì)算的計(jì)

算代價(jià)

trace口口：二維數(shù)組，長度為n*n,其中元素trace皿j]表示Ai+l*Ai+2*Aj+l的最優(yōu)計(jì)算對(duì)應(yīng)的

劃分位置，即k

(2)函數(shù)cmm

^defineN100

intcost[N][N];

inttrace[N][N];

intcmm(intn,intseq[]){

inttempCost;

inttempTrace;

intij,k,p;

inttemp;

for（i=O;i<n;i++）｛cost[i][i]=0;｝

for（p=l;p<n;p++）｛

for（i=0;（1）;i++）｛

（2）;

tempCost=-1;

for（k=i;k<j;k++）｛

temp=（3）;

if（tempCost==-l11tempCost>temp）｛

tempCost=temp;

（4）;

｝

）

cost[i][j]=tempCost;

trace[i][j]=tempTrace;

）

｝

returncost[0][n-l];

）

【問題1】（8分）

根據(jù)以上說明和C代碼，填充C代碼中的空（1）~（4）。

【問題2】（4分）

根據(jù)以上說明和C代碼，該問題采用了（5）算法設(shè)計(jì)策略，時(shí)間復(fù)雜度（6）。（用

。符號(hào)表示）

【問題3】（3分）

考慮實(shí)例n=6,各個(gè)矩陣的維數(shù)：A1為5*10,A2為：10*3,A3為3*12,A4為：12*5,A5

為5*50,A6為50*6,即維數(shù)序列為5,10,3,12,5,50,6。則根據(jù)上述C代碼得到的一個(gè)最優(yōu)計(jì)

算順序?yàn)椋?）（用加括號(hào)方式表示計(jì)算順序），所需要的乘法運(yùn)算次數(shù)為（8）。

試題分析

在解答本題時(shí)，需要注意的第一個(gè)問題便是矩陣的乘法到底是怎么進(jìn)行的。

一個(gè)n行m列的矩陣可以乘以一個(gè)m行p列的矩陣，得到的結(jié)果是一個(gè)n行p列的矩

陣，其中的第i行第j列位置上的數(shù)等于前一個(gè)矩陣第i行上的m個(gè)數(shù)與后一個(gè)矩陣第j列

上的m個(gè)數(shù)對(duì)應(yīng)相乘后所有m個(gè)乘積的和。如：

<1231/135]

[20；>112J~VO46；

在本題中，題干部分提到“發(fā)現(xiàn)矩陣鏈乘問題具有最優(yōu)子結(jié)構(gòu)”，這是利用動(dòng)態(tài)規(guī)劃法

求解最優(yōu)解問題的典型特征。所以（5）應(yīng)填動(dòng)態(tài)規(guī)劃法。

接下來分析（1）-（4）空，這幾個(gè)空中，最容易回答的是（3）和（4）。（3）空可通過

題目給出的遞歸式分析得到，其中cost數(shù)組部分與公式完全一致，而P數(shù)組在程序中是seq,

所以回答時(shí)修正即可,（3）填:cost[i][k]+cost[k+l][j]+seq[i]*seq[k+l]*seq[j+l]o第（4）空

的上一句為：tempCost=temp,即保存當(dāng)前狀態(tài)最優(yōu)解，由于在保存最優(yōu)解時(shí)，不僅涉及

cost的記錄，還涉及其位置k的記錄，所以需要在此進(jìn)行tempTrace=k的操作。

（1）與（2）相對(duì)復(fù)雜，其中（1）是對(duì)i值范圍的確定，而（2）是對(duì)j的賦值操作（由

于后面用到了j,但程序中沒有對(duì)j的賦值，從而斷定該空是對(duì)j的賦值)。兩者一并起到一

個(gè)效果，對(duì)cost數(shù)組操作時(shí)的操作范圍與順序。由于在進(jìn)行矩陣鏈乘操作時(shí)，分析解空間

所用到的是cost右上角的三角矩陣，而操作時(shí)，是對(duì)這個(gè)三角矩陣從左至右，呈斜線的訪

問(如圖所示)。所以(1)和(2)分別填i<n-p和j=i+p。

123456

該程序由于涉及3重循環(huán)，所以時(shí)間復(fù)雜度為：053)。通過手動(dòng)運(yùn)行程序的方式可知

最優(yōu)解為：

(A1A2)((A3A4)(A5A6))。

總計(jì)算次數(shù)為2010o

試題答案

(4)

【問題1】

(1)i<n-p

(2)j=i+p

(3)cost[i][k]+cost[k+l][j]+seq[i]*seq[k+l]*seq[j+l]

(4)tempTrace=k

【問題2】

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

(6)0(n3)

【問題3】

(7)((A1A2)((A3A4)(A5A6)))

(8)2010

試題10(2013年上半年試題4-6)

設(shè)有m臺(tái)完全相同的機(jī)器運(yùn)行n個(gè)獨(dú)立的任務(wù)，運(yùn)行任務(wù)i所需的時(shí)間為ti,要求確定一個(gè)

調(diào)度方案，使得完成所有任務(wù)所需要的時(shí)間最短。

假設(shè)任務(wù)已經(jīng)按照其運(yùn)行時(shí)間從大到小排序，算法基于最長運(yùn)行時(shí)間作業(yè)優(yōu)先的策略，按順

序先把每個(gè)任務(wù)分配到一臺(tái)機(jī)器上，然后將剩余的任務(wù)一次放入最先空閑的機(jī)器。

【C代碼】

下面是算法的C語言實(shí)現(xiàn)。

1.常量和變量說明

m：機(jī)器數(shù)

n：任務(wù)數(shù)

t[]：輸入數(shù)組，長度為n,下標(biāo)從0開始，其中每個(gè)元素表示任務(wù)的運(yùn)行時(shí)間，下標(biāo)從0開

始。

s[][]：二位數(shù)組，長度為m*n,下標(biāo)從0開始，其中元素表示機(jī)器i運(yùn)行的任務(wù)j的編

號(hào)。

d口：數(shù)組，長度為m其中元素d[i]表示機(jī)器i的運(yùn)行時(shí)間，下標(biāo)從0開始。

count[]：數(shù)組，長度為m,下標(biāo)從。開始，其中元素count。]表示機(jī)器i運(yùn)行的任務(wù)數(shù)。

i:循環(huán)變量。

j:循環(huán)變量。

k：臨時(shí)變量。

max：完成所有任務(wù)的時(shí)間。

min：臨時(shí)變量。

2.函數(shù)schedule

voidschedule(){

inti,j,k,max=0;

for(i=0;i<m;i++){

d[i]=0;

for(j=0;j<n;j++){

s[i]U]=O；

}

}

for(i=0;i<m;i++){〃分配前m個(gè)任務(wù)

s[i][0]=i;

(1)；

count[i]=l;

}

for((2);i<n;i++){〃分配后n~m個(gè)任務(wù)

intmin=d[0];

k