【正文】 軟件設(shè)計(jì)師歷年試題 算法 1990年下午試題五 ? 閱讀下列說(shuō)明和流程圖?；卮饐?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 的部分和，如果合適，則選取下一元素試探；若不合適，則回溯取另一個(gè)候選元素嘗試，題中利用 s棧存放候選元素的下標(biāo)，用它實(shí)現(xiàn)回溯。如果候選元素加上部分和等于 total，則表示找到一個(gè)解答，然后通過(guò)回溯，再試探尋找其它的解答。 ? [問(wèn)題 1]流程圖中的 ④應(yīng)與 A～ D中的哪一點(diǎn)相連，并填充圖中的①～③，使之成為完整的流程圖。 ? [問(wèn)題 2]設(shè) total＝ 10，n＝ 6，數(shù)組 A中各元素的值為 (8， 4， 1，2， 5， 3)。若圖中的(1)框改為 sp： 0，則執(zhí)行該流程圖后輸出什么結(jié)果。 1990年下午試題五 ? [問(wèn)題 1]① i→s[sp] ② T+A[s[sp]]→T ③ s[sp]+1 ④ D ? [問(wèn)題 2] J＝ 1時(shí)輸出的解為： 82 4123 415 253 J＝ 2時(shí)輸出的解為： 4123 415 253 J＝ 3時(shí)輸出的解為： 253 J＝ 4時(shí)輸出的解為： 253 J＝ 5， 6時(shí)無(wú)解 1993年下午試題七 ? [程序說(shuō)明 ]對(duì)于正整數(shù) n，輸出其和等于 n 且滿足以下限制條件的所有正整數(shù)的和式，即組成和式的數(shù)字自 左至右構(gòu)成一個(gè)非遞增的序列 。如 n=4，程序輸出為 4 = 4 4 = 3 + 1 4 = 2 + 2 4 = 2 + 1 +1 4 = 1 + 1 + 1 + 1 k深度分解將要分解出的和數(shù) a[k]應(yīng)該為 k1度分解所分解出的和數(shù) a[k1]和其余數(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ù)輸出。當(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í)， a[k]為第 k個(gè)和數(shù) ，r[k]為相應(yīng)的余數(shù) 。 當(dāng)找到一個(gè)分解后 (此步 r[k]等于 0)，輸出解，并作回溯處理，從當(dāng)前 k退回到第一個(gè)不為 1的和數(shù) ，將其減 1，并將其余數(shù)加 1，準(zhǔn)備去找另一個(gè)解；否則，生成下一步的分解和數(shù)與余數(shù)。 ? define MAXN 100 int a[MAXN]， r[MAXN]； ? rd(int n， int k) //遞歸求解 { int j， i； for (j=_① _。j=1。j) //依次求解 { a[k]=j； if (_② _) //判斷 k深度分解是否為解 {printf(“%d=%d”,a[0],a[1])。 //找到解 for (i=2； i=k； i++) printf( “+％ d”， a[i] )； printf( “\n” )； } else _③ _ //不是解，遞歸求 k+1深度的分解 } } 執(zhí)行過(guò)程 rd(4,1)。 rd(3,2)。 rd(2,2)。 rd(2,3)。 rd(1,4)。 na[k1]? n:a[k1] n==a[k] 或 n==j rd(nj,k+1)。 重點(diǎn) ：數(shù)組 a的變化 ? nd(int n) //回溯法求解 { int i， k； k=0； r[0]=n； do {if ( _④ _ ) //和②相同的判斷 { printf( “％ d=％ d”， a[0]， a[1] )； for ( i=2； i=ks i++ ) printf( “+％ d”，‘ a[i] )； print( “\n” )； while ( k0amp。amp。 _⑤ _ )k； //找到解后回溯 if ( k0 ){ a[k]； r[k]++； } } else { a[k+1]=_⑥ _； //生成下一步分解 的 和數(shù)和余數(shù) r[k+1]=r[k]a[k+1]； k ++； } } while(k0)； } r[k]==0 a[k]==1 a[k]r[k]?a[k]:r[k] 1993年下午試題七 ? int test_data[ ]={3， 4， 5}； main() { int i； for (i=0。isizeof (test_data)/sizeof(int)。i++) { a[0]=test_data[i]； rd( test_data[i]， 1 )； printf( “\n__________\n\n” )； nd( test_data[i] )； printf( \n_________\n\n )； } } 1995年下午試題七 ? [程序說(shuō)明 ]本程序用回溯算法來(lái)產(chǎn)生由 0或 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 10 int b[N+M1] ? int equal( int k， int j， int m) //判斷數(shù)組 b中保存的串中是否有相等子串 { int i； for ( i=0。im。i++ ) if ( b[ k + i] __(1)__ ) return 0。 return 1。 } b中 k開(kāi)始的 m個(gè)字符是否與 b中 j開(kāi)始的 m個(gè)字符相等，一旦有不同，則子串不等 !=b[j+i] 1995年下午試題七 ? int exchange ( int k, int m, int v) //將 b中新加入的從 k開(kāi)始的子串的最后一個(gè) 0或 1變成 1或 0 { while ( 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++) b[k] = v。 } k b[k+m1] 1995年下午試題七 ? main ( ) { int m,v,k,n,j。 printf (“Enter m(1m10),v(v=0,v=1)\n”)。 scanf (“%d%d ,amp。m,amp。v)。 //n賦值為 2m， m為所求串長(zhǎng)度，同時(shí)初始化 b n = 0x01 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{(%d\n,b[k])。 } ++k 1 1996年下午試題三 ? 閱讀以下說(shuō)明和 ER 圖，回答問(wèn)題，講解答寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。 【 說(shuō)明 】 設(shè)有下列關(guān)于運(yùn)動(dòng)會(huì)管理系統(tǒng)的 ER 圖。圖中矩形表示實(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 NULL, INO CHAR(6) NOT NULL, SCORRE CHAR(10))。 為了答題的方便，圖中的實(shí)體和屬性同時(shí)給出了中英文兩種名字，回答問(wèn)題時(shí)只需寫(xiě)出英文名即可。 1996年下午試題三 ? 【 ER圖 】 1996年下午試題三 ? 【 問(wèn)題 】 填充下列 SQL 程序 ～ 中的 ①～⑦，使它們分別完成相應(yīng)的功能： 程序 ：統(tǒng)計(jì)參加比賽時(shí)運(yùn)動(dòng)員人數(shù) SELECT __① __ FROM ATHLETE WHERE ASEX=39。M39。； 程序 ：查 100872號(hào)運(yùn)動(dòng)員參加的所有項(xiàng)目及其比賽時(shí)間和地點(diǎn) SELECT ITEM,INO,INAME,ITIME,IPLACE FROM GAMES,ITEM WHERE __② __ AND __③ __。 1996年下午試題三 ? 程序 ：查參加 100035 項(xiàng)目的所有運(yùn)動(dòng)員名單 SELSECT ANO,ANAME,ATEAM FROM ATHLETE WHERE __④ __ (SELECT __⑤ __ FROM GAMES WHERE = AND INO=‘10003539。)。 程序 ：建立運(yùn)動(dòng)員成績(jī)視圖 __⑥ __ ATHLETE_SCORE AS SELECT ,ANAME,ATEAM,INAME,SCORE FORM __⑦ __ WHERE = AND =。 1996年下午試題三 ? 1. COUNT(*) 2. = 3. =39。10087239。 注 : 2,3 可互換 4. EXISTS 5. * ? 4,5 也可為 4. ANO， IN 5. ANO 6. CREATE VIEW 7. ATHLETE, ITEM, GAMES(三項(xiàng)可交換 ) 1997年上午題第 5題 ? 從以下敘述中選出 5條最確切的敘述，把相應(yīng)編號(hào)依次寫(xiě)在答卷的 A～ E欄內(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ù)據(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ù)的查找、增添、刪除、修