程序员考试真题及答案试题一(15分)阅读下列函数说明和C代码，将应填入其中__(n)__处的字句写在答卷的对应栏内。【函数1.1说明】设链表结点的类型为typedefstructelem{intval;structelem*next;}intNode;函数merge(int*a,int*b)是将两个升序链表a和b合并成一个升序链表。【函数1.1】intNode*merge(intNode*a,intNode*b){intNode*h=a,*p,*q;while(b){for(p=h;p&&p->val<b->val;q=p,p=p->next);if(p==h)__(1)__;else__(2)__;q=b;b=b->next;__(3)__;}returnh;}【函数1.2说明】递归函数dec(inta[],intn)判断数组a[]的前n个元素是否是不递增的。不递增返回1，否则返回0。【函数1.2】intdec(inta[],intn){if(n<=1)__(4)__;if(a[0]
=10;p++){if(p>=a[0]__(1)__;a[p+1]+=a[p]/10;a[p]=__(2)__;}if(p>a[0])__(3)__;}【函数2.2说明】函数combine(a,b,c)是计算两个整数的组合数。由于计算结果超出longint的表示范围，故用本题【函数2.1说明】的方法存储计算结果。设整数a和b(a>=b)，它们的组合c(a,b)=a!/((a-b)!*b!)。计算a和b的组合可采用以下方法：a!/(a-b)!/b!=a*(a-1)*(a-2)*…*(a-b+1)/b!=u1*u2*…*ub/(d1*d2*…*db)其中u1=a，u2=a-1，…，ub=a-b+1；d1=1，d2=2，…，db=b。从而计算a和b的组合c(a,b)，可变成计算上述分式。为计算上述分式，先从u1，u2，…，ub中去掉所有d1*d2*…*db的因子，得到新的u1，u2，…，ub。然后再将它们相乘。以下函数中调用的外部函数gcd(a,b)是求两整数a和b最大公因子的函数；函数formal()就是本题中的函数2.1。【函数2.2】voidcombine(inta,intb,int*c){inti,j,x,k;intd[MAXN],u[MAXN];for(k=0,i=a;i>=a-b+1;i--)u[++k]=i;__(4)__;for(i=1;i<=b;i++)d[i]=i;/*将整数1至b顺序存于数组d*/for(i=1;i<=u[0];i++)/*从u的各元素中，去掉d中整数的所有因子*/if(u[i]!=1)for(j=1;j<=b;j++)if(__(5)__){x=gcd(u[i],d[j]);u[i]/=x;d[j]/=x;}c[0]=c[1]=1;/*长整数c初始化*/for(i=1;i<=u[0];i++)/*将u中各整数相乘，存于长整数c*/if(u[i]!=1){for(j=1;j<=c[0];j++)c[j]=__(6)__;formal(c);/*将存于c中的长整数规整*/}}试题三(21分)阅读下列函数说明和C代码，将应填入__(n)__处的字句写在答卷的对应栏内。【程序3说明】本程序中的函数expr()实现将中缀表达式转换成后缀表达式。设中缀表达式只有加(+)、减(-)、乘(*)和除(/)四则运算符(双目)，运算分量只能是变量，变量用英文字母开头英文字母和数字符组成的标识符命名。与平常四则运算的计算规则相一致，即先乘除，后加减，括号内的子表达式优先计算。例如，中缀表达式a*(c3-x2z/y)+u的后缀表达式为ac3x2zy/-*u+程序给每个运算符和括号设定一个优先级，并引入一个栈和一个存储后缀表达式的工作数组。函数expr()工作时，按自左至右逐个顺序扫描中缀表达式，如当前符号是变量名，就将该变量名直接复制到工作数组；如当前符号是运算符或括号，将当前符号的优先级和栈顶符号的优先级进行比较；若当前符号的优先级高，则当前符号进栈；反之，则进行出栈处理，并将从栈中退出的运算符依次复制到工作数组中，直到栈顶符号的优先级比当前符号的优先级低为止，然后将当前的运算符或左括号进栈。为使子表达式能优先处理，所以给左括号设定较高的优先级，但又为了能正确处理随后的子表达式，在左括号进栈时，它在栈中的优先级作了一定的改变。初始时，expr()函数预先在栈底设置一个符号'#'，其优先级比所有运算符和括号的优先级都低。...
