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

软件设计师历年试题,算法,1990年下午试题五,阅读下列说明和流程图。回答问题 1 和 2。 有一个集合，集合中有n个元素，每个集合元素都是正整数，它们存放在一维数组A中，每个数组元素存放一个集合元素。对给定的整数total（假定集合中每个元素的值均小于total），流程图求出所有满足下列条件的子集：子集中各元素之和等于 total。 本题在使用试探法找出全部解答的过程中，依次选取当前的候选元素，尝试组成一个小于total 的部分和，如果合适，则选取下一元素试探；若不合适，则回溯取另一个候选元素尝试，题中利用s栈存放候选元素的下标，用它实现回溯。如果候选元素加上部分和等于total，则表示找到一个解答，然后通过回溯，再试探寻找其它的解答。,问题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 且满足以下限制条件的所有正整数的和式，即组成和式的数字自左至右构成一个非递增的序列。如n=4，程序输出为4 = 44 = 3 + 14 = 2 + 24 = 2 + 1 +14 = 1 + 1 + 1 + 1,k深度分解将要分解出的和数ak应该为k-1度分解所分解出的和数ak-1和其余数的较小者（因为和式要降序排列),1993年下午试题七,程序中给出了分别采用递归和非递归解法的两个函数rd()和nd()。函数rd()采用递归解法，它有两个参数n和k。其意义分别是被分解和式的数n，及当前第k深度分解。算法思想是对n的所有合理的和式分解，将分解出的数(称为和数)存于数组a中。当其中一个分解已不再需要进一步分解时，即找到一个解，将存于数组a中的一个完整和式的和数输出。当还需要进一步分解时，以要进一步分解的数及分解深度为参数，递归调用分解和式函数。,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 (_) /判断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);,n0 ) ak-；rk+；else ak+1=_；/生成下一步分解的和数和余数rk+1=rk-ak+1；k +； while(k0)；,rk=0,ak=1,akrk?ak:rk,1993年下午试题七,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或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 _(1)_ ) return 0; return 1;,b中k开始的m个字符是否与b中j开始的m个字符相等，一旦有不同，则子串不等,!=bj+i,1995年下午试题七,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-1,1995年下午试题七,main ( ) int m,v,k,n,j; printf (“Enter m(1m10),v(v=0,v=1)n”); scanf (“%d%d ,+k,-1,1996年下午试题三,阅读以下说明和 E-R 图，回答问题，讲解答写在答卷的对应栏内。【说明】设有下列关于运动会管理系统的 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 NULL,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 _;,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. GAMES.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语言中不提供显式地使用索引的功能，支持了物理数据的独立性。用户对“脏数据”的读出是由于数据库完整性规则受到了破坏。在数据库系统中，数据的安全性是指保护数据以防止未被授权用户的蓄意或者无意使用。,1997年上午题第5题,实体完整性规则指主关键字值的任何组成部分都不可以是空值；引用完整性规则则不允许引用不存在的实体（即元组）。在数据库系统中，数据的完整性是指数据的正确性和有效性。“授权”是数据库系统中采用的完整性措施之一。事务处理(Transaction)是数据库运行的基本单位。如果一个事务处理成功，则全部数据行到更新和提交；如果失败，则已做的全部更新被恢复成原状，好象整个事务处理未进行过一样。这样使数据库保持了一致性。对数据库的查找、增添、删除、修改等操作都需由数据库管理员进行完整性定义和安全性授权，由数据库系统具体执行。,1997年上午题第5题,答案:3 5 6 7 9,1997年下午试题八,程序说明一个相连的区域被不规则地分割成 n 个不同的小区域；每个小区域与若干其它小区域相邻接。现用 cn 种不同颜色为该区域着色，要求每个小区域着同一种颜色，相邻小区域着不同颜色。设小区域被顺序编号为 0，1，n-1。每个小区域与其它小区域的邻接关系用两维数组 bordering 表示，元素 borderingij 表示 i 号小区域与 j 号小区域之间的邻接关系： 0： j 小区域与 i 小区域不邻接1： j 小区域与 i 小区域相邻接,1997年下午试题八,程序中，把计算结果存入于两维数组 colored 中，颜色编号为 0,1,cn-1,元素 coloredcolerj 的含义是:0：j 小区域不用颜色 color 着色 1：j 小区域用颜色 color 着色函数 colorcountry(bordering,colored,n,cn) 根据所给的小区域邻接关系数组 bordering、小区域个数 n 、颜色数 cn，将找到的着色方案记录在数组 colored 中。函数采用试探法找解。首先从第一个小区域着第一种颜色开始顺序为各小区域找着色方案。对某个小区域，当为它找到一种未被它的相邻小区域着色的颜色时，就用该颜色对该小区域着色，并准备处理下一个小区域。当不能为某个小区域找到一个未被它的相邻小区域着色的颜色时，就回溯。如最终为全部小区域找到着色方案，函数返回 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种颜色开始试探,while (c n) /还未对全部小区域着色时循环while(_(1)_)/顺序对每种颜色作试探 /检查当前颜色是否已被某相邻小区域着色 for (i = 0, used = 0; !used ,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; printf(“Enter number of areas.”); scanf(“%d”, ,（1）（3分） color cn 答 color 4 给 3 分；答 color = cn 给 2 分。（2）（3分）borderingci & coloredcolori 答 borderingci = 1 & coloredcolori = 1 给 3 分。 答 borderingci * coloredcolor i = 1 给 3 分，而将其中相等运算符“=”写成赋值运算符“=”时，只给 1 分。其中 borderingci 可写成 borderingic。&左右只对一半给 2 分。（3）（3分）coloredcolorc+ 答 coloredcolorc 给 2 分。答 coloredcolor 给 1 分。答 c+ 给 1 分。（4）（3分）coloredcolorc = 0 或 ! coloredcolorc 或 coloredcolorc != 1（5）（3分）coloredcolor +c 答 coloredcolorc 给 2 分。答 coloredcolor 给 1 分。,1998年下午试题七,程序说明本程序的函数sum(int i,int total，int sigma，int rear，int d，int n)用来从已知数组d的前n个元素中找出所有部分元素序列之和等于total的元素序列，约定数组d的元素都是正整数，且都小于等于total。函数sum使用递归方法找出全部解答。参数i表示递归函数当前考虑元素di，参数sigma是调用前已选取的部分序列的元素和，参数rear是后面还未考虑的那部分元素的元素和。函数对元素di 有两种可能的选择方案：,1998年下午试题七,1考虑元素di被包含在新的部分元素序列中的可能性。如果在当前部分元素序列之后接上 di，新序列的元素和不超过total，则函数将 di包含在当前部分元素序列中。如果新的部分元素序列的元素和等于total时，新的部分元素序列就是一个解答，函数将其输出；否则，若继续考虑后面的元素还有可能找到解答时，函数就递归去考虑后面的元素，寻找解答。最后，函数应恢复原来部分元素序列中不包含di的状态。2考虑元素di不被包含在新的部分元素序列中的可能性。如果继续向di之后考虑还是有希望能得到和为total的部分元素序列时，函数将新序列不包含di也作为一种可能的选择，并递归去考虑后面的元素，寻找解答。,1998年下午试题七,include stdio.h define N 100 int aN;int flgN;,1998年下午试题七,main() int i，j，n，total，s，d; printf(“输入 total！/n”); scanf(“%d”, ,s,sum (int i,int total,int sigma,int rear,int d,int t) int j; /考虑di被包含在新的部分元素序列中的可能性 if (sigma + di = total) sum(i+1,total,_(2)_,rear-di,d,n); _(3)_; ,sigma + di,sigma + di,flgi=0,1998年下午试题七,/考虑元素di不被包含在新的部分元素序列中的可能性 if (i= total) sum(i+1,total,_(4)_,rear-di,d,n); ,sigma,1999年下午试题六,【程序6说明】本程序从n种不同重量、不同价值的物品中选取一部分物品。要求在不超过限定重量limw的前提下，使被选取的那些物品的总价值较大。这里约定limw不超过n种物品的重量总和，也没有一种物品的重量超过limw，并且各物品的价值都大于0。程序中，n种物品被顺序编号为0.n-1。,1999年下午试题六,#include #define N 100double limw;int optsN; /存储临时最佳的选择方案struct elem double 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, ,1999年下午试题六,next(int i , double tw, double tv) /考虑i号物品 twvi.flg = 1; twvi.tw = tw; twvi.tv = tv; look(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, ,totv += ak.value,tw + ai.weight,i+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 maxv,i+1,tw,tv-ai.value,2001年试题11-12,递归算法的执行过程,一般来说,可先后分成_(11)_和_(12)_两个阶段。(11)A.试探 B.递推 C.枚举 D.分析(12)A.回溯 B.回归 C.返回D.合成B B,2001年试题13-14,若一个问题的求解既可以用递归算法,也可以用递推算法,则往往用_(13)_算法,因为_(14)_。 (13) A.先递归后递推 B.先递推后递归 C.递归 D.递推(14) A.递推的效率比递归高 B.递归宜于问题分解 C.递归的效率比递推高 D.递推宜于问题分解D A,2001年试题15,贪心算法是一种_的算法。A.不求最优,只求满意B.只求最优 C.求取全部可行解 D.求取全部最优解A。贪心算法一般可以快速得到满意的解，因为它省去了为找到最优解而穷尽所有可能所耗费的大量时间。常以当前情况为基础做最优选择，而不考虑各种可能的整体情况，所以贪心算法不要回溯。,2001年下午试题五,程序5说明著名的四色定理指出任何平面区域图均可用四种颜色着色,使相邻区域着不同的颜色。本程序对给定的区域图找出所有可能的不超过四种颜色的着色方案。程序中用14表示四种颜色。要着色的N个区域用0N-1编号,区域相邻关系用adj矩阵表示,矩阵的i行j列的元素为1,表示区域i与区域j相邻；矩阵的i行j列的元素为0,表示区域i与区域j不相邻。数组color用来存储着色结果, colori的值为区域i所着颜色。,2001年下午试题五,#includestdio.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) color*ip,2001年下午试题五,/检查区域 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 = c,2001年下午试题五,/为区域i选一种可着的颜色int select( int i, int c, int adjN, int color ) int k ; for ( k = c ; k = 4 ; k+ )if ( colorOK( _(3)_ ) )return k ; return 0 ;,(3) i,k,adj,color,int 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( ,(4) select (i,c+1,adj,color),(5) colori=c,2001年下午试题五,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,1,1,0;printf( 共有%d组解.n,coloring( adj ) ) ;,2002年试题11,算法是对问题求解过程的一类精确描述，算法中描述的操作都是可以通过已经实现的基本操作在限定时间内执行有限次来实现的，这说明算法具有_11_特性。A. 正确性 B. 确定性C. 能行性D. 健壮性C,附：算法的性质,有穷性：一个算法必须保证在有限个操作步骤执行后终止。一般指操作步骤或完成操作的时间在合理的范围内确定性：算法中每个步骤含义明确，无二义性。可行性：算法中描述的操作都可通过有限次的基本运算来实现输入：一个算法应具有零个或多个输入。输出：一个算法应具有一个或多个输出。,2002年试题12,快速排序算法采用的设计方法是_。A. 动态规划法 (Dynamic Programming) B. 分治法 (Divide and Conquer)C. 回溯法 (Backtracking) D. 分枝定界法 (Branch and Bound) B,2002年试题13-14,在数据压缩编码的应用中，哈夫曼算法可以用来构造具有_的二叉树，这是一种采用了_的算法。A. 前缀码 B. 最优前缀码C. 后缀码 D. 最优后缀码 A. 贪心 B. 分治C. 递推 D. 回溯 B A,2002年试题17,下述函数中渐进时间最小的是_(17)_ 。 A. T1(n) = nlog2n + 100log2nB. T2(n) = 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,12,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：B,2002年下午试题五,程序说明：“背包问题”的基本描述是：有一个背包，能盛放的物品总重量为S，设有N件物品，其重量分别为w1，w2，.，wn，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于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 ( 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，7,int 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 ( !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 & !k,2002年下午试题五,main() if ( knap(S，N) ) printf( “OK!n” )； else printf( “NO!n” )； ,2003年试题9,将两个长度为n的递增有序表归并成一个长度为2n的递增有序表，最少需要进行关键字比较_(9)_次。A. i B. n-1C. n D. 2n C,2003年试题64,对n个元素进行快速排序时，最坏情况下的时间复杂度为_(64)_。AO(1og2n) BO(n) CO(nlog2n) DO(n2) D,2004年11月试题52,采用动态规划策略求解问题的显著特征是满足最优性原理，其含义是_(52)_。A.当前所出的决策不会影响后面的决策 B.原问题的最优解包含其子问题的最优解 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.健壮性 A,2004年11月试题55,拉斯维加斯（Las Vegas）算法是一种常用的_(55)_算法。A.确定性 B.近似 C.概率 D.加密C概率算法允许算法在执行过程中可随机地选择下一个计算步骤。在许多情况下，当算法在执行过程中面临一个选择时，随机性选择常比最优选择要省时，因此可在很大程度上降低算法的复杂度。还有是蒙特卡罗（Monta Carlo）算法。,2004年11月试题56,在分支-界限算法设计策略中，通常采用_(56)_搜索问题的解空间。A.深度优先B.广度优先 C.自底向上 D.拓扑排序B,2004年11月试题57-58,在下列算法设计方法中，_(57)_在求解问题的过程中并不从整体最优上加以考虑，而是做出在当前看来是最好的选择。利用该设计方法可以解决_(58)_问题。A.分治法B.贪心法 C.动态规划法 D.回溯法A.排序B.检索 C.背包 D.0/1背包 B C,2004年11月试题59-60,以关键字比较为基础的排序算法在最坏情况下的计算时间下界为O（nlogn）。下面的排序算法中，最坏情况下计算时间可以达到O（nlogn）的是_(59)_，该算法采用的设计方法是_(60)_。A.归并算法 B.插入算法 C.选择算法 D.冒泡算法A.分治法 B.贪心法 C.动态规划法 D.回溯法 A A,2005年5月试题53-54,为在状态空间树中_(53)_，可以利用LC-检索（Least Cost Search）快速找到一个答案结点。在进行LC-检索时，为避免算法过分偏向于做纵深检查，应该_(54)_。（53）A.找出任一个答案结点 B.找出所有的答案结点 C.找出最优的答案结点 D.进行遍历（54）A.使用精确的成本函数c(.)来作LC-检索B.使用广度优先检索 C.使用深度优先检索D.在成本估计函数(.)中考虑根结点到当前结点的成本(距离) C D,2005年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的最短路径长度），则求解该问题的递推关系式为_。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) D,2005年5月 下午试题四,说明假设需要将N个任务分配给N个工人同时去完成，每个人都能承担这N个任务，但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案，在该方案中，为每个人分配1个不同的任务。程序中，N个任务从0开始依次编号，N个工人也从0开始依次编号，主要的变量说明如下：cij：将任务i分配给工人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)_ ,k=N,cost+ckimincost,i,k+1,workeri=0,void main () int i,j; for(i = 0;i N;i +) /设置每个任务由不同工人承担时的费用及全局数组的初值 worker i = 0; task i = 0; temp i = 0; for ( j = 0 ; j N ; j +)scanf (“%d”,2005年11月试题53-54,求解某问题的递归算法如右：求解该算法的计算时间时,仅考虑算法Move所做的计算为主要计算,且Move为常数级算法。则算法F的计算时间T(n)的递推关系式为_；设算法Move的计算时间为k，当n=4时，算法F的计算时间为 _。A. T(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.17k,F(int n) if n=1 Move(1); else F(n-1); Move(n); F(n-1); ,C B,2005年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)。则依次求解f0(X)、f1(X)、.、fn(X)的过程中使用的递推关系式为 _（56）_ 。,2005年11月试题55-56,A. 优先选取重量最小的物品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 B,2006年5月试题57-58,对于求取两个长度为n的最长公共子序列问题，利用（57）策略可以有效地避免最长公共子序列重复计算，得到时间复杂度为O(n2)的正确算法，串和的最长公共子序列的长度为（58）。A分治法 B贪心法 C动态规划方法 D分支-限界A3 B4 C5 D6C D,2006年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+nlog2n,2006年11月试题57,求单源点最短路径的迪杰斯特拉（Dijkstra）算法是按 （57） 的顺序求源点到各顶点的最短路径的。A. 路径长度递减B. 路径长度递增C. 顶