計(jì)算機(jī)軟件及應(yīng)用軟件設(shè)計(jì)師歷年試題算法

1、軟件設(shè)計(jì)師歷年試題算法1990年下午試題五閱讀以下說(shuō)明和流程圖。答復(fù)以下問(wèn)題 1 和 2。 有一個(gè)集合，集合中有n個(gè)元素，每個(gè)集合元素都是正整數(shù)，它們存放在一維數(shù)組A中，每個(gè)數(shù)組元素存放一個(gè)集合元素。對(duì)給定的整數(shù)total假定集合中每個(gè)元素的值均小于total，流程圖求出所有滿足以下條件的子集：子集中各元素之和等于 total。 此題在使用試探法找出全部解答的過(guò)程中，依次選取當(dāng)前的候選元素，嘗試組成一個(gè)小于total 的局部和，如果適宜，那么選取下一元素試探；假設(shè)不適宜，那么回溯取另一個(gè)候選元素嘗試，題中利用s棧存放候選元素的下標(biāo)，用它實(shí)現(xiàn)回溯。如果候選元素加上局部和等于total，那么表示找

2、到一個(gè)解答，然后通過(guò)回溯，再試探尋找其它的解答。問(wèn)題1流程圖中的 應(yīng)與AD中的哪一點(diǎn)相連，并填充圖中的，使之成為完整的流程圖。問(wèn)題2設(shè)total10，n6，數(shù)組A中各元素的值為(8，4，1，2，5，3)。假設(shè)圖中的(1)框改為sp：0，那么執(zhí)行該流程圖后輸出什么結(jié)果。1990年下午試題五問(wèn)題1 issp T+AsspT ssp+1 D問(wèn)題2J1時(shí)輸出的解為：824123415253J2時(shí)輸出的解為：4123415253J3時(shí)輸出的解為：253J4時(shí)輸出的解為：253J5，6時(shí)無(wú)解1993年下午試題七程序說(shuō)明對(duì)于正整數(shù)n，輸出其和等于n 且滿足以下限制條件的所有正整數(shù)的和式，即組成和式的數(shù)字自左

3、至右構(gòu)成一個(gè)非遞增的序列。如n=4，程序輸出為4 = 44 = 3 + 14 = 2 + 24 = 2 + 1 +14 = 1 + 1 + 1 + 1k深度分解將要分解出的和數(shù)ak應(yīng)該為k-1度分解所分解出的和數(shù)ak-1和其余數(shù)的較小者因?yàn)楹褪揭敌蚺帕?1993年下午試題七程序中給出了分別采用遞歸和非遞歸解法的兩個(gè)函數(shù)rd()和nd()。函數(shù)rd()采用遞歸解法，它有兩個(gè)參數(shù)n和k。其意義分別是被分解和式的數(shù)n，及當(dāng)前第k深度分解。算法思想是對(duì)n的所有合理的和式分解，將分解出的數(shù)(稱為和數(shù))存于數(shù)組a中。當(dāng)其中一個(gè)分解已不再需要進(jìn)一步分解時(shí)，即找到一個(gè)解，將存于數(shù)組a中的一個(gè)完整和式的和數(shù)輸

4、出。當(dāng)還需要進(jìn)一步分解時(shí)，以要進(jìn)一步分解的數(shù)及分解深度為參數(shù)，遞歸調(diào)用分解和式函數(shù)。1993年下午試題七函數(shù)nd()以要分解的數(shù)為參數(shù)，另開(kāi)設(shè)一個(gè)數(shù)組r，用于存貯當(dāng)前還未分解的余數(shù)。在求一個(gè)解的第k步時(shí)，ak為第k個(gè)和數(shù)，rk為相應(yīng)的余數(shù)。當(dāng)找到一個(gè)分解后(此步rk等于0)，輸出解，并作回溯處理，從當(dāng)前k退回到第一個(gè)不為1的和數(shù)，將其減1，并將其余數(shù)加1，準(zhǔn)備去找另一個(gè)解；否那么，生成下一步的分解和數(shù)與余數(shù)。#define MAXN 100int aMAXN，rMAXN；rd(int n，int k) /遞歸求解 int j，i； for (j=_;j=1;j-) /依次求解 ak=j； if

5、 (_) /判斷k深度分解是否為解printf(“%d=%d,a0,a1); /找到解for (i=2；i=k；i+)printf( “+d，ai )；printf( “n )； else _ /不是解，遞歸求k+1深度的分解 執(zhí)行過(guò)程rd(4,1);rd(3,2);rd(2,2);rd(2,3);rd(1,4);nak-1? n:ak-1n=ak 或n=jrd(n-j,k+1);重點(diǎn)：數(shù)組a的變化nd(int n) /回溯法求解 int i，k；k=0；r0=n； do if ( _ ) /和相同的判斷 printf( “d=d，a0，a1 )； for ( i=2；i0& _ )k-；/找

6、到解后回溯 if ( k0 ) ak-；rk+；else ak+1=_；/生成下一步分解的和數(shù)和余數(shù)rk+1=rk-ak+1；k +； while(k0)； rk=0ak=1akrk?ak:rk1993年下午試題七int test_data =3，4，5；main() int i； for (i=0;isizeof (test_data)/sizeof(int);i+) a0=test_datai； rd( test_datai，1 )； printf( “n_nn )； nd( test_datai )； printf( n_nn )；1995年下午試題七程序說(shuō)明本程序用回溯算法來(lái)產(chǎn)生由0或

7、1組成的2m個(gè)二進(jìn)位串，使該串滿足以下要求。視串為首尾相連的環(huán)，那么由m位二進(jìn)制數(shù)字組成的2m個(gè)子序列，每個(gè)可能的子序列都互不相同。例如，如果m=3，在串 11101000首尾相連構(gòu)成的環(huán)中，由3位二進(jìn)制數(shù)字組成的每個(gè)可能的子序列都在環(huán)中恰好出現(xiàn)一次，它們依次是111，110，101，010，100，000，001，011(見(jiàn)圖)。1995年下午試題七#define N l024#define M 10int bN+M-1int equal( int k，int j，int m)/判斷數(shù)組b中保存的串中是否有相等子串 int i； for ( i=0;im;i+ )if ( b k + i _

8、(1)_ ) return 0; return 1;b中k開(kāi)始的m個(gè)字符是否與b中j開(kāi)始的m個(gè)字符相等，一旦有不同，那么子串不等!=bj+i1995年下午試題七int exchange ( int k, int m, int v)/將b中新參加的從k開(kāi)始的子串的最后一個(gè)0或1變成1或0while ( b k + m - 1 ) = v ) /需回溯 b k + m - 1= ! v; _(2)_; _(3)_=v; return k; /不回溯init ( int v) int k; for( k = 0 ; k = N + M - 1; k+) bk = v;k-bk+m-11995年下午試

9、題七main ( ) int m,v,k,n,j; printf (“Enter m(1m10),v(v=0,v=1)n); scanf (“%d%d ,&m,&v); /n賦值為2m，m為所求串長(zhǎng)度，同時(shí)初始化b n = 0 x01 m; init(!v); k=0; /k:子串起始下標(biāo) while( _(4)_n) /參加新子串，即k后移for (j=0;jk;j+)if (equal(k,j,m) k=exchange(k,m,v); j=_(5)_; for(k=0;kn;k+) print(%dn,bk); +k-11996年下午試題三閱讀以下說(shuō)明和 E-R 圖，答復(fù)以下問(wèn)題，講解答

10、寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。【說(shuō)明】設(shè)有以下關(guān)于運(yùn)動(dòng)會(huì)管理系統(tǒng)的 E-R 圖。圖中矩形表示實(shí)體，圓表示屬性，雙圓表示關(guān)鍵字屬性，菱形表示實(shí)體之間的關(guān)系。假定已通過(guò)以下 SQL 語(yǔ)言建立了根本表：CREATE TABLE ATHLETE(ANO CHAR(6) NOT NULL,ANAME CHAR(20),ASEX CHAR(1),ATEAM CHAR(20);CREATE TABLE ITEM(INO CHAR(6) NOT NULL,INAME CHAR(20),ITIME CHAR(10),IPLACE CHAR(20);CREATE TABLE GAMES(ANO CHAR(6) NOT NU

11、LL,INO CHAR(6) NOT NULL,SCORRE CHAR(10);為了答題的方便，圖中的實(shí)體和屬性同時(shí)給出了中英文兩種名字，答復(fù)以下問(wèn)題時(shí)只需寫(xiě)出英文名即可。1996年下午試題三【E-R圖】 1996年下午試題三【問(wèn)題】填充以下 SQL 程序 3.13.4 中的 ，使它們分別完成相應(yīng)的功能：程序 3.1：統(tǒng)計(jì)參加比賽時(shí)運(yùn)發(fā)動(dòng)人數(shù)SELECT _FROM ATHLETEWHERE ASEX=M；程序 3.2：查100872號(hào)運(yùn)發(fā)動(dòng)參加的所有工程及其比賽時(shí)間和地點(diǎn)SELECT ITEM,INO,INAME,ITIME,IPLACEFROM GAMES,ITEMWHERE _AND _

12、;1996年下午試題三程序 3.3：查參加 100035 工程的所有運(yùn)發(fā)動(dòng)名單SELSECT ANO,ANAME,ATEAMFROM ATHLETEWHERE _(SELECT _FROM GAMESWHERE GAMES.ANO=ATHLETE.ANOAND INO=100035);程序3.4：建立運(yùn)發(fā)動(dòng)成績(jī)視圖_ ATHLETE_SCOREAS SELECT ATHLETE.ANO,ANAME,ATEAM,INAME,SCOREFORM _WHERE ATHLETE.ANO=GAMES.ANOAND GAMES.INO=ITEM.INO;1996年下午試題三1. COUNT(*)2. GA

13、MES.INO=ITEM.INO3. GAMES.ANO=100872 注: 2,3 可互換4. EXISTS5. * 4,5 也可為 4. ANO，IN 5. ANO6. CREATE VIEW7. ATHLETE, ITEM, GAMES(三項(xiàng)可交換)1997年上午題第5題從以下表達(dá)中選出5條最確切的表達(dá)，把相應(yīng)編號(hào)依次寫(xiě)在答卷的AE欄內(nèi)。在數(shù)據(jù)庫(kù)系統(tǒng)中，數(shù)據(jù)獨(dú)立性指數(shù)據(jù)之間的相互獨(dú)立，互不依賴。SQL語(yǔ)言的視圖定義和視圖操作功能不支持邏輯數(shù)據(jù)的獨(dú)立性。SQL語(yǔ)言中不提供顯式地使用索引的功能，支持了物理數(shù)據(jù)的獨(dú)立性。用戶對(duì)“臟數(shù)據(jù)的讀出是由于數(shù)據(jù)庫(kù)完整性規(guī)那么受到了破壞。在數(shù)據(jù)庫(kù)系統(tǒng)中，數(shù)

14、據(jù)的平安性是指保護(hù)數(shù)據(jù)以防止未被授權(quán)用戶的蓄意或者無(wú)意使用。1997年上午題第5題實(shí)體完整性規(guī)那么指主關(guān)鍵字值的任何組成局部都不可以是空值；引用完整性規(guī)那么那么不允許引用不存在的實(shí)體即元組。在數(shù)據(jù)庫(kù)系統(tǒng)中，數(shù)據(jù)的完整性是指數(shù)據(jù)的正確性和有效性?！笆跈?quán)是數(shù)據(jù)庫(kù)系統(tǒng)中采用的完整性措施之一。事務(wù)處理(Transaction)是數(shù)據(jù)庫(kù)運(yùn)行的根本單位。如果一個(gè)事務(wù)處理成功，那么全部數(shù)據(jù)行到更新和提交；如果失敗，那么已做的全部更新被恢復(fù)成原狀，好象整個(gè)事務(wù)處理未進(jìn)行過(guò)一樣。這樣使數(shù)據(jù)庫(kù)保持了一致性。對(duì)數(shù)據(jù)庫(kù)的查找、增添、刪除、修改等操作都需由數(shù)據(jù)庫(kù)管理員進(jìn)行完整性定義和平安性授權(quán)，由數(shù)據(jù)庫(kù)系統(tǒng)具體執(zhí)行。

15、1997年上午題第5題答案:3 5 6 7 91997年下午試題八程序說(shuō)明一個(gè)相連的區(qū)域被不規(guī)那么地分割成 n 個(gè)不同的小區(qū)域；每個(gè)小區(qū)域與假設(shè)干其它小區(qū)域相鄰接?，F(xiàn)用 cn 種不同顏色為該區(qū)域著色，要求每個(gè)小區(qū)域著同一種顏色，相鄰小區(qū)域著不同顏色。設(shè)小區(qū)域被順序編號(hào)為 0，1，n-1。每個(gè)小區(qū)域與其它小區(qū)域的鄰接關(guān)系用兩維數(shù)組 bordering 表示，元素 borderingij 表示 i 號(hào)小區(qū)域與 j 號(hào)小區(qū)域之間的鄰接關(guān)系： 0： j 小區(qū)域與 i 小區(qū)域不鄰接1： j 小區(qū)域與 i 小區(qū)域相鄰接1997年下午試題八程序中，把計(jì)算結(jié)果存入于兩維數(shù)組 colored 中，顏色編號(hào)為 0

16、,1,cn-1,元素 coloredcolerj 的含義是:0：j 小區(qū)域不用顏色 color 著色 1：j 小區(qū)域用顏色 color 著色函數(shù) colorcountry(bordering,colored,n,cn) 根據(jù)所給的小區(qū)域鄰接關(guān)系數(shù)組 bordering、小區(qū)域個(gè)數(shù) n 、顏色數(shù) cn，將找到的著色方案記錄在數(shù)組 colored 中。函數(shù)采用試探法找解。首先從第一個(gè)小區(qū)域著第一種顏色開(kāi)始順序?yàn)楦餍^(qū)域找著色方案。對(duì)某個(gè)小區(qū)域，當(dāng)為它找到一種未被它的相鄰小區(qū)域著色的顏色時(shí)，就用該顏色對(duì)該小區(qū)域著色，并準(zhǔn)備處理下一個(gè)小區(qū)域。當(dāng)不能為某個(gè)小區(qū)域找到一個(gè)未被它的相鄰小區(qū)域著色的顏色時(shí)，就

17、回溯。如最終為全部小區(qū)域找到著色方案，函數(shù)返回 1；否那么，函數(shù)返回0。程序假定小區(qū)域個(gè)數(shù)不超過(guò) 20，顏色數(shù)為 4。#include #define n 20 #define CN 4int colorcountry(int borderingN, int coloredN, int n,int cn) int color,used,i,c; for(color = 0; color cn; color+) /設(shè)置所有區(qū)域均未著色for(i = 0;i n; i+) coloredcolori = 0; c = 0; /從第1個(gè)小區(qū)域開(kāi)始 color = 0; /從著第1種顏色開(kāi)始試探 wh

18、ile (c n) /還未對(duì)全部小區(qū)域著色時(shí)循環(huán)while(_(1)_)/順序?qū)γ糠N顏色作試探 /檢查當(dāng)前顏色是否已被某相鄰小區(qū)域著色 for (i = 0, used = 0; !used & ic; i+) if(_(2)_) used = 1; if (!used) break; /當(dāng)前顏色未被相鄰小區(qū)域著色 color+; if (!used) /找到一種可用顏色，用此色著色，并準(zhǔn)備處理下一個(gè)小區(qū)域_(3)_ = 1; color = 0; else /未找到一種可用顏色，回溯 c-; if (c 0) return 0; /發(fā)現(xiàn)沒(méi)有解的情況 for(color = 0; _(4)_;

19、 color+) _(5)_ = 0; return 1; print(int coloredN,int n,int cn) /輸出結(jié)果 char *colortbl = “RED,BLUE,GREEN,YELLOW; int color,i; for(color = 0; color cn; color+) printf(“n%s;n,colortb1color); for(i = 0;in; i+) if (coloredcolori) printf(“t%d,i); printf(“n); int coloredCNN,borderingNN; main() int c,i,j,n; p

20、rintf(“Enter number of areas.); scanf(“%d,&n); printf(“Enter bordering:n); for (i = 0;i n; i+) for (j = 0;j n; j+) borderingij = 0 for(i = 0;i n; i+) printf(“Enter areas to link %d area(= 0) if(i != j) borderingij = borderingji = 1; scanf(“%d,&j); if(colorcountry(bordering,colored,n,CN) print(colore

21、d,n,CN); else printf(“No Solution.n); 13分 color cn 答 color 4 給 3 分；答 color 0且=%d)n，i+1，total; scanf (“%d，&d); if( d total) printf(“出錯(cuò)，請(qǐng)重新輸入！n); continue； s += ai+ = d; sum(0，total，0,_(5)_，a，n); printf (nn); ssum (int i,int total,int sigma,int rear,int d,int t) int j; /考慮di被包含在新的局部元素序列中的可能性 if (sigma

22、 + di = total) flgi = 1; /di被考慮在被局部元素序列中 if(_(1)_ = total) / 輸出解 for (j = 0; flgj = 0; j+); printf(“%4d = %d，total，dj); for(j+; j = i; j+) if (flgj)printf(“+%d,dj); printf(“); else /考慮后面的元素有可能找到解答時(shí) if(i= total) sum(i+1,total,_(2)_,rear-di,d,n); _(3)_; sigma + disigma + diflgi=01998年下午試題七 /考慮元素di不被包含

23、在新的局部元素序列中的可能性 if (i= total) sum(i+1,total,_(4)_,rear-di,d,n); sigma1999年下午試題六【程序6說(shuō)明】本程序從n種不同重量、不同價(jià)值的物品中選取一局部物品。要求在不超過(guò)限定重量limw的前提下，使被選取的那些物品的總價(jià)值較大。這里約定limw不超過(guò)n種物品的重量總和，也沒(méi)有一種物品的重量超過(guò)limw，并且各物品的價(jià)值都大于0。程序中，n種物品被順序編號(hào)為0.n-1。1999年下午試題六#include #define N 100double limw;int optsN; /存儲(chǔ)臨時(shí)最正確的選擇方案struct elem do

24、uble weight;double value; aN; /物品的重量和價(jià)值信息int k, n;struct int flg; /物品的考慮狀態(tài)：0不選，1將被考慮，2曾被選中 double tw; / 已到達(dá)的總重量 double tv; / 期望的總價(jià)值twvN; / 當(dāng)前候選解中各物品的考慮狀態(tài)，以及候選解的狀態(tài)1999年下午試題六main() double maxv, find(); printf(Enter number of matter. ); scanf(%d, &n); printf(Enter limit of weight. ); scanf(%1f, &limw);

25、 printf(Enter weight & values of matters.); for (k = 0; k n; k+) scanf(%1f%1f, &ak.weight, &ak.value); maxv = find(a,n); for(k = 0; k n; k+) if(optsk) printf(%4d, k); printf(nTotal value = %1fn, maxv);1999年下午試題六next(int i , double tw, double tv) /考慮i號(hào)物品 twvi.flg = 1; twvi.tw = tw; twvi.tv = tv; look

26、(int i, int *f, double *tw, double *tv) /取i號(hào)物品在解中的狀態(tài)信息 *f = twvi.flg; *tw = twvi.tw; *tv = twvi.tv;double find (struct elem *a, int n ) int i, k, f; double maxv=0, tw, tv, totv= 0.0; for(k = 0; k = 0) look(i, &f, &tw, &tv); switch (f) case 1: twvi.flg+; /先考慮被選中if(_(2)_= limw) /選中可行嗎if(imaxv) /是更好的解嗎

27、 maxv = tv; for(k = 0; k n; k+) optsk = twvk.flg != 0;break;totv += ak.valuetw + ai.weighti+1,tw+ai.weight,tv case 0: i-; break; /不選，回退default: /f = 2，曾被選中 twvi.flg = 0; if (_(4)_) /不選i號(hào)物品可行嗎if(in-1) /后面還有物品嗎 next(_(5)_); i+;else maxv = tv ai.value; for(k = 0; k maxvi+1,tw,tv-ai.value2001年試題11-12遞歸算

28、法的執(zhí)行過(guò)程,一般來(lái)說(shuō),可先后分成_(11)_和_(12)_兩個(gè)階段。(11)A.試探 B.遞推 C.枚舉 D.分析(12)A.回溯 B.回歸 C.返回D.合成B B2001年試題13-14假設(shè)一個(gè)問(wèn)題的求解既可以用遞歸算法,也可以用遞推算法,那么往往用_(13)_算法,因?yàn)開(kāi)(14)_。 (13) A.先遞歸后遞推 B.先遞推后遞歸 C.遞歸 D.遞推(14) A.遞推的效率比遞歸高 B.遞歸宜于問(wèn)題分解 C.遞歸的效率比遞推高 D.遞推宜于問(wèn)題分解D A2001年試題15貪心算法是一種_的算法。A.不求最優(yōu),只求滿意B.只求最優(yōu) C.求取全部可行解 D.求取全部最優(yōu)解A。貪心算法一般可以快

29、速得到滿意的解，因?yàn)樗∪チ藶檎业阶顑?yōu)解而窮盡所有可能所消耗的大量時(shí)間。常以當(dāng)前情況為根底做最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪心算法不要回溯。2001年下午試題五程序5說(shuō)明著名的四色定理指出任何平面區(qū)域圖均可用四種顏色著色,使相鄰區(qū)域著不同的顏色。本程序?qū)o定的區(qū)域圖找出所有可能的不超過(guò)四種顏色的著色方案。程序中用14表示四種顏色。要著色的N個(gè)區(qū)域用0N-1編號(hào),區(qū)域相鄰關(guān)系用adj矩陣表示,矩陣的i行j列的元素為1,表示區(qū)域i與區(qū)域j相鄰；矩陣的i行j列的元素為0,表示區(qū)域i與區(qū)域j不相鄰。數(shù)組color用來(lái)存儲(chǔ)著色結(jié)果, colori的值為區(qū)域i所著顏色。2001年下午試題五#i

30、ncludestdio.h#define N 10void output(int color)/輸出一種著色方案 int i ; for ( i = 0 ; i N ; i+ ) printf( %4d , colori ) ; printf( n ) ;2001年下午試題五int back( int *ip, int color ) /回溯 int c = 4 ; while ( c = 4 )if ( *ip = 0 ) return 0 ; /已回溯到0號(hào)區(qū)域-(*ip) ;c =_(1)_ ;color*ip = -1 ; return c ;/返回該區(qū)域原來(lái)的著色方案(1) colo

31、r*ip2001年下午試題五/檢查區(qū)域 i 對(duì)顏色 c 的可用性int colorOK( int i , int c , intN , int color int j ; for ( j = 0 ; j i ; j+ if ( _(2)_ )return 0 ; return 1 ;(2) adjij = 1 & colorj = c2001年下午試題五/為區(qū)域i選一種可著的顏色int select( int i, int c, int adjN, int color ) int k ; for ( k = c ; k = 4 ; k+ )if ( colorOK( _(3)_ ) )retu

32、rn k ; return 0 ;(3) i,k,adj,colorint coloring( int adjN ) /尋找各種著色方案 int colorN , i , c , cnt ; for ( i = 0 ; i N ; i+ ) colori = -1 ; i = c = 0 ; cnt = 0 ; while ( 1 ) if ( ( c =_(4)_ ) = 0 )c = back( &i , color) ; if ( c = 0) return cnt ; else _(5)_ ; i+ ; if ( i = N ) output(color) ; +cnt; c = ba

33、ck( &i , color ) ; else c = 0 ; (4) select (i,c+1,adj,color)(5) colori=c2001年下午試題五void main() int adjNN = 0,1,0,1,1,1,1,1,1,1,1,0,1,1,0,1,1,1,1,0,0,1,0,1,0,1,1,0,1,1,1,1,1,0,1,1,0,0,1,1,1,0,0,1,0,1,0,0,0,0,1,1,1,1,1,0,1,0,0,1,1,1,1,0,0,1,0,0,1,0,1,1,0,0,0,0,0,0,1,1,1,1,1,1,0,0,1,1,0,1,1,0,1,1,0,1,0,

34、1,1,0;printf( 共有%d組解.n,coloring( adj ) ) ; 2002年試題11算法是對(duì)問(wèn)題求解過(guò)程的一類(lèi)精確描述，算法中描述的操作都是可以通過(guò)已經(jīng)實(shí)現(xiàn)的根本操作在限定時(shí)間內(nèi)執(zhí)行有限次來(lái)實(shí)現(xiàn)的，這說(shuō)明算法具有_11_特性。A. 正確性 B. 確定性C. 能行性D. 健壯性C附：算法的性質(zhì)有窮性：一個(gè)算法必須保證在有限個(gè)操作步驟執(zhí)行后終止。一般指操作步驟或完成操作的時(shí)間在合理的范圍內(nèi)確定性：算法中每個(gè)步驟含義明確，無(wú)二義性。可行性：算法中描述的操作都可通過(guò)有限次的根本運(yùn)算來(lái)實(shí)現(xiàn)輸入：一個(gè)算法應(yīng)具有零個(gè)或多個(gè)輸入。輸出：一個(gè)算法應(yīng)具有一個(gè)或多個(gè)輸出。2002年試題12快速排

35、序算法采用的設(shè)計(jì)方法是_。A. 動(dòng)態(tài)規(guī)劃法 (Dynamic Programming) B. 分治法 (Divide and Conquer)C. 回溯法 (Backtracking) D. 分枝定界法 (Branch and Bound) B2002年試題13-14在數(shù)據(jù)壓縮編碼的應(yīng)用中，哈夫曼算法可以用來(lái)構(gòu)造具有_的二叉樹(shù)，這是一種采用了_的算法。A. 前綴碼 B. 最優(yōu)前綴碼C. 后綴碼 D. 最優(yōu)后綴碼 A. 貪心 B. 分治C. 遞推 D. 回溯 B A2002年試題17下述函數(shù)中漸進(jìn)時(shí)間最小的是_(17)_ 。 A. T1(n) = nlog2n + 100log2nB. T2(n

36、) = 2nlog2n - 100log2n C. T3(n) = n2 - 100log2nD. T4(n) = 4nlog2n - 100log2n A 先考慮最高階，再考慮相同階的系數(shù)2002年試題19、21對(duì)于給定的一組關(guān)鍵字12，2，16，30，8，28，4，10，20，6，18，按照以下算法進(jìn)行遞增排序，寫(xiě)出每種算法第一趟排序后得到的結(jié)果：快速排序選第一個(gè)記錄為基準(zhǔn)元素得到_(19)_，二路歸并排序得到_(21)_，(19) A. 10,6,18,8,4,2,12,20,16,30,28 B. 4,2,6,10,8,12,28,30,20,16,18 C. 2,4,6,8,10,1

37、2,16,18,20,28,30 D. 6,10,8,28,20,18,2,4,12,30,16 (21) A. 2,12,16,8,28,30,4,6,10,18,20 B. 2,12,16,30,8,28,4,10,6,20,18 C. 12,2,16,8,28,30,4,6,10,28,18 D. 12,2.10,20,6,18,4,16,30,8,28 答案：19：B 21：B2002年下午試題五程序說(shuō)明：“背包問(wèn)題的根本描述是：有一個(gè)背包，能盛放的物品總重量為S，設(shè)有N件物品，其重量分別為w1，w2，.，wn，希望從N件物品中選擇假設(shè)干件物品，所選物品的重量之和恰能放入該背包，即所選

38、物品的重量之和等于S。 如下程序均能求得“背包問(wèn)題的一組解，其中程序5.1是“背包問(wèn)題的遞歸解法，而程序5.2是“背包問(wèn)題的非遞歸解法。2002年下午試題五#include #define N 7#define S 15int wN+1 = 0，1，4，3，4，5，2，7；typedef struct int s；/背包剩余容量 int n; /物品的下標(biāo) int job；/物品當(dāng)前狀態(tài) KNAPTP；程序中用棧來(lái)保存已考查過(guò)的物品。結(jié)構(gòu)KNAPTP表示經(jīng)過(guò)考查的物品2002年下午試題五int knap ( int s，int n) /遞歸算法 if ( s= 0) return 1； if

39、( s0 & n1 ) return 0； if (_(1)_ ) ) printf( “4d，wn )； return 1； return _(2)_ ； (1) knap(s-wn,n-1)(2) knap(s,n-1)wN+1 = 0，1，4，3，4，5，2，7int knap( int s，int n ) /非遞歸算法KNAPTP stack100，x；int top， k， rep； x.s = s； x.n = n； x.job = 0； top = 1； stacktop = x；k = 0； while ( _(3)_ ) x = stacktop；rep = 1； while

40、 ( !k & rep ) if( x.s=0 ) k = 1；/已求得一組解 else if ( x.s0 | x.n= 1 & rep) x = stacktop-；/不選該物品 if ( x.job=1) x.s += wx.n + 1；x.job = 2； stack+top = x； _(6)_ ；/結(jié)束循環(huán)考查下個(gè) if (k) /輸出一組解 while ( top = 1 ) x = stacktop-； if ( x.job = 1 ) printf ( “%dt，wx.n+1 )； return k；(6) rep = 0(3) top0 & !k2002年下午試題五main

41、() if ( knap(S，N) ) printf( “OK!n )； else printf( “NO!n )； 2003年試題9將兩個(gè)長(zhǎng)度為n的遞增有序表歸并成一個(gè)長(zhǎng)度為2n的遞增有序表，最少需要進(jìn)行關(guān)鍵字比較_(9)_次。A. i B. n-1C. n D. 2n C2003年試題64對(duì)n個(gè)元素進(jìn)行快速排序時(shí)，最壞情況下的時(shí)間復(fù)雜度為_(kāi)(64)_。AO(1og2n) BO(n) CO(nlog2n) DO(n2) D2004年11月試題52采用動(dòng)態(tài)規(guī)劃策略求解問(wèn)題的顯著特征是滿足最優(yōu)性原理，其含義是_(52)_。A.當(dāng)前所出的決策不會(huì)影響后面的決策 B.原問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)

42、解 C.問(wèn)題可以找到最優(yōu)解，但利用貪心法不能找到最優(yōu)解D.每次決策必須是當(dāng)前看來(lái)最優(yōu)決策才可以找到最優(yōu)解B 2004年11月試題53下面函數(shù)中漸進(jìn)時(shí)間最小的是_(53)_A.T1(n)=n+nlognB.T2(n)=2n+nlognC.T3(n)=n2-logn D.T4(n)=n+100lognD 2004年11月試題54下面的程序段違反了算法的_(54)_原那么。void sam() int n=2;while (!odd(n) n+=2;printf(n);A.有窮性 B.確定性 C.可行性 D.健壯性 A2004年11月試題55拉斯維加斯Las Vegas算法是一種常用的_(55)_算

43、法。A.確定性 B.近似 C.概率 D.加密C概率算法允許算法在執(zhí)行過(guò)程中可隨機(jī)地選擇下一個(gè)計(jì)算步驟。在許多情況下，當(dāng)算法在執(zhí)行過(guò)程中面臨一個(gè)選擇時(shí)，隨機(jī)性選擇常比最優(yōu)選擇要省時(shí)，因此可在很大程度上降低算法的復(fù)雜度。還有是蒙特卡羅Monta Carlo算法。2004年11月試題56在分支-界限算法設(shè)計(jì)策略中，通常采用_(56)_搜索問(wèn)題的解空間。A.深度優(yōu)先B.廣度優(yōu)先 C.自底向上 D.拓?fù)渑判駼 2004年11月試題57-58在以下算法設(shè)計(jì)方法中，_(57)_在求解問(wèn)題的過(guò)程中并不從整體最優(yōu)上加以考慮，而是做出在當(dāng)前看來(lái)是最好的選擇。利用該設(shè)計(jì)方法可以解決_(58)_問(wèn)題。A.分治法B.貪

44、心法 C.動(dòng)態(tài)規(guī)劃法 D.回溯法A.排序B.檢索 C.背包 D.0/1背包 B C2004年11月試題59-60以關(guān)鍵字比較為根底的排序算法在最壞情況下的計(jì)算時(shí)間下界為Onlogn。下面的排序算法中，最壞情況下計(jì)算時(shí)間可以到達(dá)Onlogn的是_(59)_，該算法采用的設(shè)計(jì)方法是_(60)_。A.歸并算法 B.插入算法 C.選擇算法 D.冒泡算法A.分治法 B.貪心法 C.動(dòng)態(tài)規(guī)劃法 D.回溯法 A A2005年5月試題53-54為在狀態(tài)空間樹(shù)中_(53)_，可以利用LC-檢索Least Cost Search快速找到一個(gè)答案結(jié)點(diǎn)。在進(jìn)行LC-檢索時(shí)，為防止算法過(guò)分偏向于做縱深檢查，應(yīng)該_(54

45、)_。53A.找出任一個(gè)答案結(jié)點(diǎn) B.找出所有的答案結(jié)點(diǎn) C.找出最優(yōu)的答案結(jié)點(diǎn) D.進(jìn)行遍歷54A.使用精確的本錢(qián)函數(shù)c(.)來(lái)作LC-檢索B.使用廣度優(yōu)先檢索 C.使用深度優(yōu)先檢索D.在本錢(qián)估計(jì)函數(shù)(.)中考慮根結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的本錢(qián)(距離) C D2005年5月試題56利用動(dòng)態(tài)規(guī)劃方法求解每對(duì)結(jié)點(diǎn)之間的最短路徑問(wèn)題(all pairs shortest path problem)時(shí)，設(shè)有向圖G=共有n個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)編號(hào)1n，設(shè)C是G的本錢(qián)鄰接矩陣，Dk(i，j)即為圖G中結(jié)點(diǎn)i到j(luò)并且不經(jīng)過(guò)編號(hào)比k還大的結(jié)點(diǎn)的最短路徑的長(zhǎng)度Dn(i，j)即為圖G中結(jié)點(diǎn)i到j(luò)的最短路徑長(zhǎng)度，那么求解該問(wèn)題的遞

46、推關(guān)系式為_(kāi)。A.Dk(i，j)=Dk-1(i，j)+C(i，j)B.Dk(i，j)=minDk-1(i，j)，Dk-1(i，j)+C(i，j)C.Dk(i，j)=Dk-1(i，k)+Dk-1(k，j)D.Dk(i，j)=minDk-1(i，j)，Dk-1(i，k)+Dk-1(k，j) D2005年5月 下午試題四說(shuō)明假設(shè)需要將N個(gè)任務(wù)分配給N個(gè)工人同時(shí)去完成，每個(gè)人都能承擔(dān)這N個(gè)任務(wù)，但費(fèi)用不同。下面的程序用回溯法計(jì)算總費(fèi)用最小的一種工作分配方案，在該方案中，為每個(gè)人分配1個(gè)不同的任務(wù)。程序中，N個(gè)任務(wù)從0開(kāi)始依次編號(hào)，N個(gè)工人也從0開(kāi)始依次編號(hào)，主要的變量說(shuō)明如下：cij：將任務(wù)i分配給工

47、人j的費(fèi)用；taski：值為0表示任務(wù)i未分配。值為j表示任務(wù)i分配給工人j；workerk：值為0表示工人k未分配任務(wù)，值為1表示工人k已分配任務(wù)；mincost：最小總費(fèi)用。2005年5月下午試題四#include #define N 8 /N表示任務(wù)數(shù)和工人數(shù)int cNN;unsigned int mincost = 65535; /設(shè)置min的初始值，大于可能的總費(fèi)用int taskN,tempN,workerN;void plan(int k,unsigned int cost) /k為任務(wù)號(hào) int i; if (_(1)_& cost mincost) mincost = co

48、st; for (i=0;iN;i+) tempi=taski; else for ( i = 0 ; iN; i + ) /分配任務(wù)k if ( workeri=0 & _(2)_)workeri=1; taskk=_(3)_;plan(_(4)_,cost + c k i );_(5)_; task k = 0; k=Ncost+ckimincostik+1workeri=0void main () int i,j; for(i = 0;i N;i +) /設(shè)置每個(gè)任務(wù)由不同工人承擔(dān)時(shí)的費(fèi)用及全局?jǐn)?shù)組的初值 worker i = 0; task i = 0; temp i = 0; for

49、 ( j = 0 ; j N ; j +)scanf (“%d,&c i j ); plan (0,0); /從任務(wù)0開(kāi)始分配 printf(“n最小費(fèi)用 = %dn,mincost); for (i = 0; i N; i +)printf (“Task%d is assigned to worker%dn,i,temp i );2005年11月試題53-54求解某問(wèn)題的遞歸算法如右：求解該算法的計(jì)算時(shí)間時(shí),僅考慮算法Move所做的計(jì)算為主要計(jì)算,且Move為常數(shù)級(jí)算法。那么算法F的計(jì)算時(shí)間T(n)的遞推關(guān)系式為_(kāi)；設(shè)算法Move的計(jì)算時(shí)間為k，當(dāng)n=4時(shí)，算法F的計(jì)算時(shí)間為 _。A. T(

50、n)=T(n-1)+1B. T(n)=2T(n-1) C. T(n)=2T(n-1)+1D. T(n)=2T(n+1)+1 A.14k B.15k C.16k D.17kF(int n) if n=1 Move(1); else F(n-1); Move(n); F(n-1); C B2005年11月試題55-56利用貪心法求解背包問(wèn)題時(shí)，_55_能夠確保獲得最優(yōu)解。用動(dòng)態(tài)規(guī)劃方法求解0/1背包問(wèn)題時(shí)，將“用前i個(gè)物品來(lái)裝容量是X的背包的0/1背包問(wèn)題記為KNAP(1,i,X),設(shè)fi(X)是KNAP(1,i,X)最優(yōu)解的效益值，第j個(gè)物品的重量和放入背包后取得效益值分別為wj和pj(j=1n

51、)。那么依次求解f0(X)、f1(X)、.、fn(X)的過(guò)程中使用的遞推關(guān)系式為 _56_ 。2005年11月試題55-56A. 優(yōu)先選取重量最小的物品B. 優(yōu)先選取效益最大的物品 C. 優(yōu)先選取單位重量效益最大的物品 D. 沒(méi)有任何準(zhǔn)那么 A. fi(X)=minfi-1(X),fi-1(X)+pi B .fi(X)=maxfi-1(X),fi-1(X-Wi)+pi C. fi(X)=minfi-1(X-Wi),fi-1(X-Wi)+pi D. fi(X)=maxfi-1(X-Wi),fi-1(X)+pi C B2006年5月試題57-58對(duì)于求取兩個(gè)長(zhǎng)度為n的最長(zhǎng)公共子序列問(wèn)題，利用57策

52、略可以有效地防止最長(zhǎng)公共子序列重復(fù)計(jì)算，得到時(shí)間復(fù)雜度為O(n2)的正確算法，串和的最長(zhǎng)公共子序列的長(zhǎng)度為58。A分治法 B貪心法 C動(dòng)態(tài)規(guī)劃方法 D分支-限界A3 B4 C5 D6C D2006年5月試題59設(shè)某算法的計(jì)算時(shí)間可用遞推關(guān)系式 T(n)=2T(n/2)+n表示，那么該算法的時(shí)間復(fù)雜度為59。AO(lgn) BO(nlgn)CO(n) DO(n2)T(n)=2T(n/2)+n =4T(n/4)+n+n = =2kT(1)+kn (n=2k) =cn+nlog2n2006年11月試題57 求單源點(diǎn)最短路徑的迪杰斯特拉Dijkstra算法是按 57 的順序求源點(diǎn)到各頂點(diǎn)的最短路徑的。

53、A. 路徑長(zhǎng)度遞減B. 路徑長(zhǎng)度遞增C. 頂點(diǎn)編號(hào)遞減D. 頂點(diǎn)編號(hào)遞增 答案：B2006年11月試題58_算法策略與遞歸技術(shù)的聯(lián)系最弱。A動(dòng)態(tài)規(guī)劃 B貪心 C回溯 D分治B2006年11月試題59,60對(duì)于有n個(gè)元素的一個(gè)數(shù)據(jù)序列，假設(shè)只需得到其中第k個(gè)元素之前的局部序列，最好采用_(59)_，使用分治(Divide and Conquer)策略的是_(60)_算法。(59)A. 希爾排序 B. 直接插入排序 C. 快速排序D. 堆排序(60)A. 冒泡排序 B. 插入排序 C. 快速排序 D. 堆排序D C2006年11月下午試題四閱讀以下說(shuō)明和圖，填補(bǔ)流程圖中的空缺，將解答填入答題紙的對(duì)

54、應(yīng)欄內(nèi)。說(shuō)明某汽車(chē)制造工廠有兩條裝配線。汽車(chē)裝配過(guò)程如圖4-1所示，即汽車(chē)底盤(pán)進(jìn)入裝配線，零件在多個(gè)工位裝配，結(jié)束時(shí)汽車(chē)自動(dòng)完成下線工作。 2006年11月下午試題四(1) e0 和 e1 表示底盤(pán)分別進(jìn)入裝配線 0 和裝配線 1 所需要的時(shí)間。(2) 每條裝配線有 n 個(gè)工位，第一條裝配線的工位為 S0,0, S0,1, , S0,n-1, 第二條裝 配線的工位為 S1,0, S1,1, , S1,n-1。其中 S0,k 和 S1,k0kn-1完成相同的任務(wù)，但所需時(shí)間可能不同。(3) ai,j 表示在工位 Si,j 處的裝配時(shí)間，其中 i 表示裝配線i=0 或 i=1,j 表示工位號(hào)(0j

55、n-1)。(4) ti,j 表示從 Si,j 處裝配完成后轉(zhuǎn)移到另一條裝配線下一個(gè)工位的時(shí)間。(5) x0 和 x1 表示裝配結(jié)束后，汽車(chē)分別從裝配線 0 和裝配線 1 下線所需要的時(shí)間。(6) 在同一條裝配線上，底盤(pán)從一個(gè)工位轉(zhuǎn)移到其下一個(gè)工位的時(shí)間可以忽略不計(jì)。 2006年11月下午試題四圖 4-2 所示的流程圖描述了求最短裝配時(shí)間的算法，該算法的輸入為：n: 表示裝配線上的工位數(shù)；ei: 表示 e1 和 e2，i 取值為 0 或 1；aij:表示 ai,j，i 的取值為 0 或 1，j 的取值范圍為 0n-1；tij:表示 ti,j, i 的取值為 0 或 1，j 的取值范圍為 0n-1

56、；xi: 表示 x0 和 x1，i 取值為 0 或 1。算法的輸出為：fi:最短的裝配時(shí)間；li:獲得最短裝配時(shí)間的下線裝配線號(hào)(0 或者 1)。算法中使用的 fij表示從開(kāi)始點(diǎn)到 Si,j 處的最短裝配時(shí)間。2006年11月下午試題四(1) f00 = e0 + a00 f10 = e1 + a10(2) f0j-1+a0j (3) f1j-1+a1j f0j-1+t0j-1+a1j (4) fi = f0n-1+x0 li = 0 (5) fi = f1n-1+x1 li = 12007年5月試題62設(shè)商店有 10 元、5 元、2 元和 1 元的零幣，每種零幣的數(shù)量充足。售貨員給顧客找零錢(qián)

57、時(shí)，零幣的數(shù)量越少越好。例如給顧客找零 29 元：先選 2 張 10 元幣，然后選擇 1張 5 元幣，再選擇兩張 2 元幣。以上的找零錢(qián)方法采用了62策略。A. 分治B. 貪心C. 動(dòng)態(tài)規(guī)劃D. 回溯B2007年5月試題64-652007年5月下午試題四說(shuō)明在一條農(nóng)村公路的一邊稀疏地分布著房子，其分布如圖4-1所示。某電信公司需要在某些位置放置蜂窩 基站，由于基站的覆蓋范圍是6公里，因此必須使得每棟房子到某個(gè)基站的直線距離不超過(guò)6公里。為簡(jiǎn)化問(wèn)題，假設(shè)所有房子在同一直線上，并且基站沿該直線放置?，F(xiàn)采用貪心策略實(shí)現(xiàn)用盡可能少的基站覆蓋所有的房子。2007年5月下午試題四實(shí)現(xiàn)貪心算法的流程如圖4-

58、2所示，請(qǐng)?zhí)羁詹⒂?jì)算該算法的時(shí)間復(fù)雜度，其中：1di(1iN)表示第i個(gè)房子到公路A端的距離，N表示房子的總數(shù)，按房子到公路A端的距離從小到大進(jìn)行房子編號(hào)。2sk表示第kk1個(gè)基站到公路A端的距離，算法結(jié)束后k的值為基站的總數(shù)。分析：?jiǎn)栴}解的模型該算法的時(shí)間復(fù)雜度為(5)k=0j=Nk+di+6O(n)2007年11月試題63迪杰斯特拉Dijkstra)算法按照路徑長(zhǎng)度遞增的方式求解單源點(diǎn)最短路徑問(wèn)題，該算法運(yùn)用了 63 算法策略。A. 貪心 B. 分而治之C. 動(dòng)態(tài)規(guī)劃D. 試探回溯A2007年11月試題64關(guān)于算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系， 64 是正確的。A. 算法的實(shí)現(xiàn)依賴于數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì) B

59、. 算法的效率與數(shù)據(jù)結(jié)構(gòu)無(wú)關(guān)C. 數(shù)據(jù)結(jié)構(gòu)越復(fù)雜，算法的效率越高D. 數(shù)據(jù)結(jié)構(gòu)越簡(jiǎn)單，算法的效率越高A2007年11月試題65假設(shè)一個(gè)問(wèn)題既可以用迭代方式也可以用遞歸方式求解，那么 65 方法具有更高的時(shí)空效率。A. 迭代 B. 遞歸C. 先遞歸后迭代D. 先迭代后遞歸A2007年11月下午試題四說(shuō)明：某機(jī)器上需要處理n個(gè)作業(yè)job1, job2, , jobn，其中：每個(gè)作業(yè)jobi(1in)的編號(hào)為i，jobi有一個(gè)收益值pi和最后期限值di；機(jī)器在一個(gè)時(shí)刻只能處理一個(gè)作業(yè)，而且每個(gè)作業(yè)需要一個(gè)單位時(shí)間進(jìn)行處理，一旦作業(yè)開(kāi)始就不可中斷，每個(gè)作業(yè)的最后期限值為單位時(shí)間的正整數(shù)倍；job1jo

60、bn的收益值呈非遞增順序排列，即p1p2pn；如果作業(yè)jobi在其期限之內(nèi)完成，那么獲得收益pi；如果在其期限之后完成，那么沒(méi)有收益。2007年11月下午試題四為獲得較高的收益，采用貪心策略求解在期限之內(nèi)完成的作業(yè)序列。圖4-1是基于貪心策略求解該問(wèn)題的流程圖。整型數(shù)組J有n個(gè)存儲(chǔ)單元，變量k表示在期限之內(nèi)完成的作業(yè)數(shù)，J1.k存儲(chǔ)所有能夠在期限內(nèi)完成的作業(yè)編號(hào)，數(shù)組J1.k里的作業(yè)按其最后期限非遞減排序，即dJ1 dJk。為了方便于在數(shù)組J中參加作業(yè)，增加一個(gè)虛擬作業(yè)job0，并令d0 = 0，J0 = 0。2007年11月下午試題四算法大致思想：先將作業(yè)job1的編號(hào)1放入J1，然后，依次