计算机软件及应用软件设计师历年试题算法

1、软件设计师历年试题算法1990年下午试题五阅读以下说明和流程图。答复以下问题 1 和 2。 有一个集合，集合中有n个元素，每个集合元素都是正整数，它们存放在一维数组A中，每个数组元素存放一个集合元素。对给定的整数total假定集合中每个元素的值均小于total，流程图求出所有满足以下条件的子集：子集中各元素之和等于 total。 此题在使用试探法找出全部解答的过程中，依次选取当前的候选元素，尝试组成一个小于total 的局部和，如果适宜，那么选取下一元素试探；假设不适宜，那么回溯取另一个候选元素尝试，题中利用s栈存放候选元素的下标，用它实现回溯。如果候选元素加上局部和等于total，那么表示找

2、到一个解答，然后通过回溯，再试探寻找其它的解答。问题1流程图中的 应与AD中的哪一点相连，并填充图中的，使之成为完整的流程图。问题2设total10，n6，数组A中各元素的值为(8，4，1，2，5，3)。假设图中的(1)框改为sp：0，那么执行该流程图后输出什么结果。1990年下午试题五问题1 issp T+AsspT ssp+1 D问题2J1时输出的解为：824123415253J2时输出的解为：4123415253J3时输出的解为：253J4时输出的解为：253J5，6时无解1993年下午试题七程序说明对于正整数n，输出其和等于n 且满足以下限制条件的所有正整数的和式，即组成和式的数字自左

3、至右构成一个非递增的序列。如n=4，程序输出为4 = 44 = 3 + 14 = 2 + 24 = 2 + 1 +14 = 1 + 1 + 1 + 1k深度分解将要分解出的和数ak应该为k-1度分解所分解出的和数ak-1和其余数的较小者因为和式要降序排列)1993年下午试题七程序中给出了分别采用递归和非递归解法的两个函数rd()和nd()。函数rd()采用递归解法，它有两个参数n和k。其意义分别是被分解和式的数n，及当前第k深度分解。算法思想是对n的所有合理的和式分解，将分解出的数(称为和数)存于数组a中。当其中一个分解已不再需要进一步分解时，即找到一个解，将存于数组a中的一个完整和式的和数输

4、出。当还需要进一步分解时，以要进一步分解的数及分解深度为参数，递归调用分解和式函数。1993年下午试题七函数nd()以要分解的数为参数，另开设一个数组r，用于存贮当前还未分解的余数。在求一个解的第k步时，ak为第k个和数，rk为相应的余数。当找到一个分解后(此步rk等于0)，输出解，并作回溯处理，从当前k退回到第一个不为1的和数，将其减1，并将其余数加1，准备去找另一个解；否那么，生成下一步的分解和数与余数。#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深度的分解 执行过程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);重点：数组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=_；/生成下一步分解的和数和余数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年下午试题七程序说明本程序用回溯算法来产生由0或

7、1组成的2m个二进位串，使该串满足以下要求。视串为首尾相连的环，那么由m位二进制数字组成的2m个子序列，每个可能的子序列都互不相同。例如，如果m=3，在串 11101000首尾相连构成的环中，由3位二进制数字组成的每个可能的子序列都在环中恰好出现一次，它们依次是111，110，101，010，100，000，001，011(见图)。1995年下午试题七#define N l024#define M 10int bN+M-1int equal( int k，int j，int m)/判断数组b中保存的串中是否有相等子串 int i； for ( i=0;im;i+ )if ( b k + i _

8、(1)_ ) return 0; return 1;b中k开始的m个字符是否与b中j开始的m个字符相等，一旦有不同，那么子串不等!=bj+i1995年下午试题七int exchange ( int k, int m, int v)/将b中新参加的从k开始的子串的最后一个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为所求串长度，同时初始化b n = 0 x01 m; init(!v); k=0; /k:子串起始下标 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年下午试题三阅读以下说明和 E-R 图，答复以下问题，讲解答

10、写在答卷的对应栏内。【说明】设有以下关于运动会管理系统的 E-R 图。图中矩形表示实体，圆表示属性，双圆表示关键字属性，菱形表示实体之间的关系。假定已通过以下 SQL 语言建立了根本表：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);为了答题的方便，图中的实体和属性同时给出了中英文两种名字，答复以下问题时只需写出英文名即可。1996年下午试题三【E-R图】 1996年下午试题三【问题】填充以下 SQL 程序 3.13.4 中的 ，使它们分别完成相应的功能：程序 3.1：统计参加比赛时运发动人数SELECT _FROM ATHLETEWHERE ASEX=M；程序 3.2：查100872号运发动参加的所有工程及其比赛时间和地点SELECT ITEM,INO,INAME,ITIME,IPLACEFROM GAMES,ITEMWHERE _AND _

12、;1996年下午试题三程序 3.3：查参加 100035 工程的所有运发动名单SELSECT ANO,ANAME,ATEAMFROM ATHLETEWHERE _(SELECT _FROM GAMESWHERE GAMES.ANO=ATHLETE.ANOAND INO=100035);程序3.4：建立运发动成绩视图_ 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(三项可交换)1997年上午题第5题从以下表达中选出5条最确切的表达，把相应编号依次写在答卷的AE栏内。在数据库系统中，数据独立性指数据之间的相互独立，互不依赖。SQL语言的视图定义和视图操作功能不支持逻辑数据的独立性。SQL语言中不提供显式地使用索引的功能，支持了物理数据的独立性。用户对“脏数据的读出是由于数据库完整性规那么受到了破坏。在数据库系统中，数

14、据的平安性是指保护数据以防止未被授权用户的蓄意或者无意使用。1997年上午题第5题实体完整性规那么指主关键字值的任何组成局部都不可以是空值；引用完整性规那么那么不允许引用不存在的实体即元组。在数据库系统中，数据的完整性是指数据的正确性和有效性。“授权是数据库系统中采用的完整性措施之一。事务处理(Transaction)是数据库运行的根本单位。如果一个事务处理成功，那么全部数据行到更新和提交；如果失败，那么已做的全部更新被恢复成原状，好象整个事务处理未进行过一样。这样使数据库保持了一致性。对数据库的查找、增添、删除、修改等操作都需由数据库管理员进行完整性定义和平安性授权，由数据库系统具体执行。

15、1997年上午题第5题答案:3 5 6 7 91997年下午试题八程序说明一个相连的区域被不规那么地分割成 n 个不同的小区域；每个小区域与假设干其它小区域相邻接。现用 cn 种不同颜色为该区域着色，要求每个小区域着同一种颜色，相邻小区域着不同颜色。设小区域被顺序编号为 0，1，n-1。每个小区域与其它小区域的邻接关系用两维数组 bordering 表示，元素 borderingij 表示 i 号小区域与 j 号小区域之间的邻接关系： 0： j 小区域与 i 小区域不邻接1： j 小区域与 i 小区域相邻接1997年下午试题八程序中，把计算结果存入于两维数组 colored 中，颜色编号为 0

16、,1,cn-1,元素 coloredcolerj 的含义是:0：j 小区域不用颜色 color 着色 1：j 小区域用颜色 color 着色函数 colorcountry(bordering,colored,n,cn) 根据所给的小区域邻接关系数组 bordering、小区域个数 n 、颜色数 cn，将找到的着色方案记录在数组 colored 中。函数采用试探法找解。首先从第一个小区域着第一种颜色开始顺序为各小区域找着色方案。对某个小区域，当为它找到一种未被它的相邻小区域着色的颜色时，就用该颜色对该小区域着色，并准备处理下一个小区域。当不能为某个小区域找到一个未被它的相邻小区域着色的颜色时，就

17、回溯。如最终为全部小区域找到着色方案，函数返回 1；否那么，函数返回0。程序假定小区域个数不超过 20，颜色数为 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+) /设置所有区域均未着色for(i = 0;i n; i+) coloredcolori = 0; c = 0; /从第1个小区域开始 color = 0; /从着第1种颜色开始试探 wh

18、ile (c n) /还未对全部小区域着色时循环while(_(1)_)/顺序对每种颜色作试探 /检查当前颜色是否已被某相邻小区域着色 for (i = 0, used = 0; !used & ic; i+) if(_(2)_) used = 1; if (!used) break; /当前颜色未被相邻小区域着色 color+; if (!used) /找到一种可用颜色，用此色着色，并准备处理下一个小区域_(3)_ = 1; color = 0; else /未找到一种可用颜色，回溯 c-; if (c 0) return 0; /发现没有解的情况 for(color = 0; _(4)_;

19、 color+) _(5)_ = 0; return 1; print(int coloredN,int n,int cn) /输出结果 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(“出错，请重新输入！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 /考虑后面的元素有可能找到解答时 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说明】本程序从n种不同重量、不同价值的物品中选取一局部物品。要求在不超过限定重量limw的前提下，使被选取的那些物品的总价值较大。这里约定limw不超过n种物品的重量总和，也没有一种物品的重量超过limw，并且各物品的价值都大于0。程序中，n种物品被顺序编号为0.n-1。1999年下午试题六#include #define N 100double limw;int optsN; /存储临时最正确的选择方案struct elem do

24、uble weight;double value; aN; /物品的重量和价值信息int k, n;struct int flg; /物品的考虑状态：0不选，1将被考虑，2曾被选中 double tw; / 已到达的总重量 double tv; / 期望的总价值twvN; / 当前候选解中各物品的考虑状态，以及候选解的状态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号物品 twvi.flg = 1; twvi.tw = tw; twvi.tv = tv; look

26、(int i, int *f, double *tw, double *tv) /取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号物品可行吗if(in-1) /后面还有物品吗 next(_(5)_); i+;else maxv = tv ai.value; for(k = 0; k maxvi+1,tw,tv-ai.value2001年试题11-12递归算

28、法的执行过程,一般来说,可先后分成_(11)_和_(12)_两个阶段。(11)A.试探 B.递推 C.枚举 D.分析(12)A.回溯 B.回归 C.返回D.合成B B2001年试题13-14假设一个问题的求解既可以用递归算法,也可以用递推算法,那么往往用_(13)_算法,因为_(14)_。 (13) A.先递归后递推 B.先递推后递归 C.递归 D.递推(14) A.递推的效率比递归高 B.递归宜于问题分解 C.递归的效率比递推高 D.递推宜于问题分解D A2001年试题15贪心算法是一种_的算法。A.不求最优,只求满意B.只求最优 C.求取全部可行解 D.求取全部最优解A。贪心算法一般可以快

29、速得到满意的解，因为它省去了为找到最优解而穷尽所有可能所消耗的大量时间。常以当前情况为根底做最优选择，而不考虑各种可能的整体情况，所以贪心算法不要回溯。2001年下午试题五程序5说明著名的四色定理指出任何平面区域图均可用四种颜色着色,使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过四种颜色的着色方案。程序中用14表示四种颜色。要着色的N个区域用0N-1编号,区域相邻关系用adj矩阵表示,矩阵的i行j列的元素为1,表示区域i与区域j相邻；矩阵的i行j列的元素为0,表示区域i与区域j不相邻。数组color用来存储着色结果, colori的值为区域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号区域-(*ip) ;c =_(1)_ ;color*ip = -1 ; return c ;/返回该区域原来的着色方案(1) colo

31、r*ip2001年下午试题五/检查区域 i 对颜色 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年下午试题五/为区域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算法是对问题求解过程的一类精确描述，算法中描述的操作都是可以通过已经实现的根本操作在限定时间内执行有限次来实现的，这说明算法具有_11_特性。A. 正确性 B. 确定性C. 能行性D. 健壮性C附：算法的性质有穷性：一个算法必须保证在有限个操作步骤执行后终止。一般指操作步骤或完成操作的时间在合理的范围内确定性：算法中每个步骤含义明确，无二义性。可行性：算法中描述的操作都可通过有限次的根本运算来实现输入：一个算法应具有零个或多个输入。输出：一个算法应具有一个或多个输出。2002年试题12快速排

35、序算法采用的设计方法是_。A. 动态规划法 (Dynamic Programming) B. 分治法 (Divide and Conquer)C. 回溯法 (Backtracking) D. 分枝定界法 (Branch and Bound) B2002年试题13-14在数据压缩编码的应用中，哈夫曼算法可以用来构造具有_的二叉树，这是一种采用了_的算法。A. 前缀码 B. 最优前缀码C. 后缀码 D. 最优后缀码 A. 贪心 B. 分治C. 递推 D. 回溯 B A2002年试题17下述函数中渐进时间最小的是_(17)_ 。 A. T1(n) = nlog2n + 100log2nB. T2(n

36、) = 2nlog2n - 100log2n C. T3(n) = n2 - 100log2nD. T4(n) = 4nlog2n - 100log2n A 先考虑最高阶，再考虑相同阶的系数2002年试题19、21对于给定的一组关键字12，2，16，30，8，28，4，10，20，6，18，按照以下算法进行递增排序，写出每种算法第一趟排序后得到的结果：快速排序选第一个记录为基准元素得到_(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年下午试题五程序说明：“背包问题的根本描述是：有一个背包，能盛放的物品总重量为S，设有N件物品，其重量分别为w1，w2，.，wn，希望从N件物品中选择假设干件物品，所选物品的重量之和恰能放入该背包，即所选

38、物品的重量之和等于S。 如下程序均能求得“背包问题的一组解，其中程序5.1是“背包问题的递归解法，而程序5.2是“背包问题的非递归解法。2002年下午试题五#include #define N 7#define S 15int wN+1 = 0，1，4，3，4，5，2，7；typedef struct int s；/背包剩余容量 int n; /物品的下标 int job；/物品当前状态 KNAPTP；程序中用栈来保存已考查过的物品。结构KNAPTP表示经过考查的物品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)_ ；/结束循环考查下个 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将两个长度为n的递增有序表归并成一个长度为2n的递增有序表，最少需要进行关键字比较_(9)_次。A. i B. n-1C. n D. 2n C2003年试题64对n个元素进行快速排序时，最坏情况下的时间复杂度为_(64)_。AO(1og2n) BO(n) CO(nlog2n) DO(n2) D2004年11月试题52采用动态规划策略求解问题的显著特征是满足最优性原理，其含义是_(52)_。A.当前所出的决策不会影响后面的决策 B.原问题的最优解包含其子问题的最优

42、解 C.问题可以找到最优解，但利用贪心法不能找到最优解D.每次决策必须是当前看来最优决策才可以找到最优解B 2004年11月试题53下面函数中渐进时间最小的是_(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概率算法允许算法在执行过程中可随机地选择下一个计算步骤。在许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择要省时，因此可在很大程度上降低算法的复杂度。还有是蒙特卡罗Monta Carlo算法。2004年11月试题56在分支-界限算法设计策略中，通常采用_(56)_搜索问题的解空间。A.深度优先B.广度优先 C.自底向上 D.拓扑排序B 2004年11月试题57-58在以下算法设计方法中，_(57)_在求解问题的过程中并不从整体最优上加以考虑，而是做出在当前看来是最好的选择。利用该设计方法可以解决_(58)_问题。A.分治法B.贪

44、心法 C.动态规划法 D.回溯法A.排序B.检索 C.背包 D.0/1背包 B C2004年11月试题59-60以关键字比较为根底的排序算法在最坏情况下的计算时间下界为Onlogn。下面的排序算法中，最坏情况下计算时间可以到达Onlogn的是_(59)_，该算法采用的设计方法是_(60)_。A.归并算法 B.插入算法 C.选择算法 D.冒泡算法A.分治法 B.贪心法 C.动态规划法 D.回溯法 A A2005年5月试题53-54为在状态空间树中_(53)_，可以利用LC-检索Least Cost Search快速找到一个答案结点。在进行LC-检索时，为防止算法过分偏向于做纵深检查，应该_(54

45、)_。53A.找出任一个答案结点 B.找出所有的答案结点 C.找出最优的答案结点 D.进行遍历54A.使用精确的本钱函数c(.)来作LC-检索B.使用广度优先检索 C.使用深度优先检索D.在本钱估计函数(.)中考虑根结点到当前结点的本钱(距离) C D2005年5月试题56利用动态规划方法求解每对结点之间的最短路径问题(all pairs shortest path problem)时，设有向图G=共有n个结点，结点编号1n，设C是G的本钱邻接矩阵，Dk(i，j)即为图G中结点i到j并且不经过编号比k还大的结点的最短路径的长度Dn(i，j)即为图G中结点i到j的最短路径长度，那么求解该问题的递

46、推关系式为_。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月 下午试题四说明假设需要将N个任务分配给N个工人同时去完成，每个人都能承担这N个任务，但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案，在该方案中，为每个人分配1个不同的任务。程序中，N个任务从0开始依次编号，N个工人也从0开始依次编号，主要的变量说明如下：cij：将任务i分配给工

47、人j的费用；taski：值为0表示任务i未分配。值为j表示任务i分配给工人j；workerk：值为0表示工人k未分配任务，值为1表示工人k已分配任务；mincost：最小总费用。2005年5月下午试题四#include #define N 8 /N表示任务数和工人数int cNN;unsigned int mincost = 65535; /设置min的初始值，大于可能的总费用int taskN,tempN,workerN;void plan(int k,unsigned int cost) /k为任务号 int i; if (_(1)_& cost mincost) mincost = co

48、st; for (i=0;iN;i+) tempi=taski; else for ( i = 0 ; iN; i + ) /分配任务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 +) /设置每个任务由不同工人承担时的费用及全局数组的初值 worker i = 0; task i = 0; temp i = 0; for

49、 ( j = 0 ; j N ; j +)scanf (“%d,&c i j ); plan (0,0); /从任务0开始分配 printf(“n最小费用 = %dn,mincost); for (i = 0; i N; i +)printf (“Task%d is assigned to worker%dn,i,temp i );2005年11月试题53-54求解某问题的递归算法如右：求解该算法的计算时间时,仅考虑算法Move所做的计算为主要计算,且Move为常数级算法。那么算法F的计算时间T(n)的递推关系式为_；设算法Move的计算时间为k，当n=4时，算法F的计算时间为 _。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利用贪心法求解背包问题时，_55_能够确保获得最优解。用动态规划方法求解0/1背包问题时，将“用前i个物品来装容量是X的背包的0/1背包问题记为KNAP(1,i,X),设fi(X)是KNAP(1,i,X)最优解的效益值，第j个物品的重量和放入背包后取得效益值分别为wj和pj(j=1n

51、)。那么依次求解f0(X)、f1(X)、.、fn(X)的过程中使用的递推关系式为 _56_ 。2005年11月试题55-56A. 优先选取重量最小的物品B. 优先选取效益最大的物品 C. 优先选取单位重量效益最大的物品 D. 没有任何准那么 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对于求取两个长度为n的最长公共子序列问题，利用57策

52、略可以有效地防止最长公共子序列重复计算，得到时间复杂度为O(n2)的正确算法，串和的最长公共子序列的长度为58。A分治法 B贪心法 C动态规划方法 D分支-限界A3 B4 C5 D6C D2006年5月试题59设某算法的计算时间可用递推关系式 T(n)=2T(n/2)+n表示，那么该算法的时间复杂度为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 求单源点最短路径的迪杰斯特拉Dijkstra算法是按 57 的顺序求源点到各顶点的最短路径的。

53、A. 路径长度递减B. 路径长度递增C. 顶点编号递减D. 顶点编号递增 答案：B2006年11月试题58_算法策略与递归技术的联系最弱。A动态规划 B贪心 C回溯 D分治B2006年11月试题59,60对于有n个元素的一个数据序列，假设只需得到其中第k个元素之前的局部序列，最好采用_(59)_，使用分治(Divide and Conquer)策略的是_(60)_算法。(59)A. 希尔排序 B. 直接插入排序 C. 快速排序D. 堆排序(60)A. 冒泡排序 B. 插入排序 C. 快速排序 D. 堆排序D C2006年11月下午试题四阅读以下说明和图，填补流程图中的空缺，将解答填入答题纸的对

54、应栏内。说明某汽车制造工厂有两条装配线。汽车装配过程如图4-1所示，即汽车底盘进入装配线，零件在多个工位装配，结束时汽车自动完成下线工作。 2006年11月下午试题四(1) e0 和 e1 表示底盘分别进入装配线 0 和装配线 1 所需要的时间。(2) 每条装配线有 n 个工位，第一条装配线的工位为 S0,0, S0,1, , S0,n-1, 第二条装 配线的工位为 S1,0, S1,1, , S1,n-1。其中 S0,k 和 S1,k0kn-1完成相同的任务，但所需时间可能不同。(3) ai,j 表示在工位 Si,j 处的装配时间，其中 i 表示装配线i=0 或 i=1,j 表示工位号(0j

55、n-1)。(4) ti,j 表示从 Si,j 处装配完成后转移到另一条装配线下一个工位的时间。(5) x0 和 x1 表示装配结束后，汽车分别从装配线 0 和装配线 1 下线所需要的时间。(6) 在同一条装配线上，底盘从一个工位转移到其下一个工位的时间可以忽略不计。 2006年11月下午试题四图 4-2 所示的流程图描述了求最短装配时间的算法，该算法的输入为：n: 表示装配线上的工位数；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:最短的装配时间；li:获得最短装配时间的下线装配线号(0 或者 1)。算法中使用的 fij表示从开始点到 Si,j 处的最短装配时间。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设商店有 10 元、5 元、2 元和 1 元的零币，每种零币的数量充足。售货员给顾客找零钱

57、时，零币的数量越少越好。例如给顾客找零 29 元：先选 2 张 10 元币，然后选择 1张 5 元币，再选择两张 2 元币。以上的找零钱方法采用了62策略。A. 分治B. 贪心C. 动态规划D. 回溯B2007年5月试题64-652007年5月下午试题四说明在一条农村公路的一边稀疏地分布着房子，其分布如图4-1所示。某电信公司需要在某些位置放置蜂窝 基站，由于基站的覆盖范围是6公里，因此必须使得每栋房子到某个基站的直线距离不超过6公里。为简化问题，假设所有房子在同一直线上，并且基站沿该直线放置。现采用贪心策略实现用尽可能少的基站覆盖所有的房子。2007年5月下午试题四实现贪心算法的流程如图4-

58、2所示，请填空并计算该算法的时间复杂度，其中：1di(1iN)表示第i个房子到公路A端的距离，N表示房子的总数，按房子到公路A端的距离从小到大进行房子编号。2sk表示第kk1个基站到公路A端的距离，算法结束后k的值为基站的总数。分析：问题解的模型该算法的时间复杂度为(5)k=0j=Nk+di+6O(n)2007年11月试题63迪杰斯特拉Dijkstra)算法按照路径长度递增的方式求解单源点最短路径问题，该算法运用了 63 算法策略。A. 贪心 B. 分而治之C. 动态规划D. 试探回溯A2007年11月试题64关于算法与数据结构的关系， 64 是正确的。A. 算法的实现依赖于数据结构的设计 B

59、. 算法的效率与数据结构无关C. 数据结构越复杂，算法的效率越高D. 数据结构越简单，算法的效率越高A2007年11月试题65假设一个问题既可以用迭代方式也可以用递归方式求解，那么 65 方法具有更高的时空效率。A. 迭代 B. 递归C. 先递归后迭代D. 先迭代后递归A2007年11月下午试题四说明：某机器上需要处理n个作业job1, job2, , jobn，其中：每个作业jobi(1in)的编号为i，jobi有一个收益值pi和最后期限值di；机器在一个时刻只能处理一个作业，而且每个作业需要一个单位时间进行处理，一旦作业开始就不可中断，每个作业的最后期限值为单位时间的正整数倍；job1jo

60、bn的收益值呈非递增顺序排列，即p1p2pn；如果作业jobi在其期限之内完成，那么获得收益pi；如果在其期限之后完成，那么没有收益。2007年11月下午试题四为获得较高的收益，采用贪心策略求解在期限之内完成的作业序列。图4-1是基于贪心策略求解该问题的流程图。整型数组J有n个存储单元，变量k表示在期限之内完成的作业数，J1.k存储所有能够在期限内完成的作业编号，数组J1.k里的作业按其最后期限非递减排序，即dJ1 dJk。为了方便于在数组J中参加作业，增加一个虚拟作业job0，并令d0 = 0，J0 = 0。2007年11月下午试题四算法大致思想：先将作业job1的编号1放入J1，然后，依次