软件设计师历年试题-算法

《软件设计师历年试题-算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、到一个解答，然后通过回溯，再试探寻找其它的解答。[问题1]流程图中的④应与A～D中的哪一点相连，并填充图中的①～③，使之成为完整的流程图。[问题2]设total＝10，n＝6，数组A中各元素的值为(8，4，1，2，5，3)。若图中的(1)框改为sp：0，则执行该流程图后输出什么结果。1990年下午试题五[问题1]①i→s[sp]②T+A[s[sp]]→T③s[sp]+1④D[问题2]J＝1时输出的解为：824123415253J＝2时输出的解为：4123415253J＝3时输出的解为：253J＝4时输出的解为：253J＝5，6时无解1993年下午试题七[程序说明]对于正整

3、数n，输出其和等于n且满足以下限制条件的所有正整数的和式，即组成和式的数字自左至右构成一个非递增的序列。如n=4，程序输出为4=44=3+14=2+24=2+1+14=1+1+1+1k深度分解将要分解出的和数a[k]应该为k-1度分解所分解出的和数a[k-1]和其余数的较小者（因为和式要降序排列)1993年下午试题七程序中给出了分别采用递归和非递归解法的两个函数rd()和nd()。函数rd()采用递归解法，它有两个参数n和k。其意义分别是被分解和式的数n，及当前第k深度分解。算法思想是对n的所有合理的和式分解，将分解出的数(称为和数)存于数组a[]中。当其中一个分解已不

4、再需要进一步分解时，即找到一个解，将存于数组a[]中的一个完整和式的和数输出。当还需要进一步分解时，以要进一步分解的数及分解深度为参数，递归调用分解和式函数。1993年下午试题七函数nd()以要分解的数为参数，另开设一个数组r[]，用于存贮当前还未分解的余数。在求一个解的第k步时，a[k]为第k个和数，r[k]为相应的余数。当找到一个分解后(此步r[k]等于0)，输出解，并作回溯处理，从当前k退回到第一个不为1的和数，将其减1，并将其余数加1，准备去找另一个解；否则，生成下一步的分解和数与余数。#defineMAXN100inta[MAXN]，r[MAXN]；rd(int

5、n，intk)//递归求解{intj，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(“”)；}else_③_//不是解，递归求k+1深度的分解}}执行过程rd(4,1);rd(3,2);rd(2,2);rd(2,3);rd(1,4);n

6、/回溯法求解{inti，k；k=0；r[0]=n；do{if(_④_)//和②相同的判断{printf(“％d=％d”，a[0]，a[1])；for(i=2；i<=ksi++)printf(“+％d”，‘a[i])；print(“”)；while(k>0&&_⑤_)k--；//找到解后回溯if(k>0){a[k]--；r[k]++；}}else{a[k+1]=_⑥_；//生成下一步分解的和数和余数r[k+1]=r[k]-a[k+1]；k++；}}while(k>0)；}r[k]==0a[k]==1a[k]

7、_data[]={3，4，5}；main(){inti；for(i=0;i