文档介绍：计算机软件及应用软件设计师历试题(shìtí)算法
第一页，共162页。
[问题1]流程图中的 ④应与A～D中的哪一点相连，并填充图中的①～③，使之成为完整的流程图。
[问题2]设total＝10，n＝6，数组A中各元素的值为(8，4，1，2，5，3)。若图中的(1)框改为(ɡǎi wéi)sp：0，则执行该流程图后输出什么结果。
第1页/共161页
第二页，共162页。
1990年下午(xiàwǔ)试题五
[问题(wèntí)1]① i→s[sp] ② T+A[s[sp]]→T ③ s[sp]+1 ④ D
[问题(wèntí)2] J＝1时输出的解为： 82 4123 415 253 J＝2时输出的解为： 4123 415 253 J＝3时输出的解为： 253 J＝4时输出的解为： 253 J＝5，6时无解
第2页/共161页
第三页，共162页。
1993年下午(xiàwǔ)试题七
[程序说明]对于正整数n，输出其和等于n 且满足以下限制条件(tiáojiàn)的所有正整数的和式，即组成和式的数字自左至右构成一个非递增的序列。如n=4，程序输出为 4 = 4 4 = 3 + 1 4 = 2 + 2 4 = 2 + 1 +1 4 = 1 + 1 + 1 + 1
k深度(shēndù)分解将要分解出的和数a[k]应该为k-1度分解所分解出的和数a[k-1]和其余数的较小者（因为和式要降序排列)
第3页/共161页
第四页，共162页。
1993年下午(xiàwǔ)试题七
程序中给出了分别采用递归和非递归解法的两个函数rd()和nd()。
函数rd()采用递归解法，它有两个参数n和k。其意义(yìyì)分别是被分解和式的数n，及当前第k深度分解。算法思想是对n的所有合理的和式分解，将分解出的数(称为和数)存于数组a[]中。当其中一个分解已不再需要进一步分解时，即找到一个解，将存于数组a[]中的一个完整和式的和数输出。当还需要进一步分解时，以要进一步分解的数及分解深度为参数，递归调用分解和式函数。
第4页/共161页
第五页，共162页。
1993年下午(xiàwǔ)试题七
函数nd()以要分解的数为参数，另开设一个数组r[]，用于存贮当前还未分解的余数。在求一个解的第k步时，a[k]为第k个和数，r[k]为相应的余数。当找到一个分解后(此步r[k]等于0)，输出解，并作回溯处理，从当前k退回(tuìhuí)到第一个不为1的和数，将其减1，并将其余数加1，准备去找另一个解；否则，生成下一步的分解和数与余数。
第5页/共161页
第六页，共162页。
#define MAXN 100 int a[MAXN]，r[MAXN]；
rd(int n，int k) //递归求解(qiú jiě) { int j，i； for (j=_①_;j>=1;j--) //依次求解(qiú jiě) { 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íxíng)过程 rd(4,1); rd(3,2); rd(2,2); rd(2,3); rd(1,4);
n<a[k-1]? n:a[k-1]
n==a[k] 或n==j
rd(n-j,k+1);
重点(zhòngdiǎn)：数组a的变化
第6页/共161页
第七页，共162页。
nd(int n) //回溯法求解 { int i，k；k=0；r[0]=n； do {if ( _④_ ) //和②相同的判断(pànduàn) { printf( “％d=％d”，a[0]，a[1] )； for ( i=2；i<=ks i++ ) printf( “+％d”，‘a[i] )； print( “\n” )； while ( k>0&& _⑤_ )k--；//找到解后回溯 if ( k>0 ){ a[k]--；r[k]++；} } else { a[k+1]=_⑥_；//生成下一步分解的和数和余数