温故而知新，下笔如有神程序员考试专项练习题及答案试题一(15分)阅读下列函数说明和 C 代码，将应填入其中_(n)_处的字句写在答卷的对应栏内。【函数1.1说明】设链表结点的类型为typedef struct elem int val; struct elem *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)_; return h; 【函数1.2说明】递归函数 dec(int a,int n) 判断数组 a 的前 n 个元素是否是不递增的。不递增返回 1 ，否则返回 0 。【函数1.2】 int dec(int a,int n) if (n = 1) _(4)_; if (a0 a1) return 0; return _(5)_; 试题二(18分) 阅读下列函数说明和 C 代码，将应填入_(n)_处的字句写在答卷的对应栏内。【函数2.1说明】 设长正整数用数组存储，如有 k 位的长整数m用数组 a 存储： m = ak*10k-1ak-1*10K-2+a2*101+a1*100 并用a0存储长整数m的位数，即a0=k。 通常，存储长整数数组的每个元素只存储长整数的一位数字。长整数运算时，为了运算方便，产生的中间结果的某位数字可能会大于 9。这时，就应调用本函数将它规整，使数组的每个元素只存储长整数的一位数字。规整运算函数 formal(int *a) 就实现这个特殊要求。【函数2.1】 void formal(int *a) int p; for (p = 1; p = 10; p+) if (p = a0 _(1)_; ap+1+ = ap/10; ap = _(2)_; if (p a0) _(3)_; 【函数2.2说明】 函数 combine(a,b,c) 是计算两个整数的组合数。由于计算结果超出 long int 的表示范围，故用本题【函数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】 void combine (int a,int b,int *c) int i, j, x, k; int dMAXN,uMAXN; for (k = 0, i = a; i = a-b+1; i-) u+k = i; _(4)_; for (i = 1; i = b; i+) di = i; /*将整数 1 至 b顺序存于数组 d */ for (i = 1; i = u0; i+) /*从u的各元素中，去掉 d 中整数的所有因子*/ if (ui != 1) for (j = 1; j = b; j+) if (_(5)_) x = gcd(ui, dj); ui /= x; dj /= x; c0 = c1 = 1; /*长整数c初始化*/ for (i = 1; i = u0; i+) /*将 u 中各整数相乘，存于长整数 c */ if (ui! = 1) for (j = 1;j #include <ctype.h #include <stdlib.h typedef struct node /*符号、内部编号、优先级和后继栈元指针*/ char data; int code;int pri;strujct mode *link; NODE; struct Tb1 /*符号、内部编号、优先级*/ char data; int ckde ; int pri; opchTb1 = *, 1, 4, /, 2, 4, +, 3, 2, -, 4, 2, (, 5, 5, ), 6, 1,0, 7, 0, ,-1, 0; NODE *optop; /*栈顶指针*/ Char num200, *numtop; /*工作数组和存储指针*/ Char expStr200; /*存储中缀表达式的字符数组*/ Void push(char x, int c, int p, NODE *topt) /*链接存储栈的进栈函数*/ NODE *q = (NODE *)malloc(sizeof(NODE); q->data = x; q->code = c; q->pri = p; _(1)_ ; *toppt = q; int pop(char *op, int *cp, NODE *toppt) /*链接存储栈的出栈函数*/ NODE q = toppt; if (*toppt = NULL) return 1; /*空栈 */ *op = q->data; cp = q->code; _(2)_ ; free(q); return 0; int expr(char *pos) struct Tb1 *op; char sop; int type, code, n, m, i, c; optop = NULL; numtop = num; n = m = 0; c = ; push(#, 0, 0, &optop); /*预先在栈中置一个0优先级的符号 */ while (1) while (c= |c = t) c = *pos+; /*掠过空白符 */ if (isalpha(c) /*复制变量名到工作数组*/ *numtop+ = ; while (isalpha(c)|isdigit(c) _(3)_ ; c = *pos+; if (m) return 1; /*运算符个数与运算分量个数不相容 */ m = 1; /*运算分量比运算符多1 个 */ continue; else /*处理运算符或非法字符 */ for (i = 0; opchTb1i.code != -1 & _(4)_ ; i+) if (opchTb1i.code = -1) return 3; /*非法字符 */ op = &opchTbli; type = opchTbli.code; /*得到运算符的内部码 */