近几年程序员考试练习题及答案（专项习题训练）

温故而知新，下笔如有神程序员考试专项练习题及答案试题一(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-&gtval&ltb-&gtval; q = p, p = p-&gtnext); if (p = h) _(1)_; else _(2)_; q = b; b = b-&gtnext; _(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 < a0 | ap >= 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 <= c0; j+) cj = _(6)_; formal(c); /*将存于c中的长整数规整*/ 试题三(21分)阅读下列函数说明和 C 代码，将应填入_(n)_处的字句写在答卷的对应栏内。【程序3说明】 本程序中的函数 expr() 实现将中缀表达式转换成后缀表达式。设中缀表达式只有加(+)、减(-)、乘(*)和除(/)四则运算符(双目)，运算分量只能是变量，变量用英文字母开头英文字母和数字符组成的标识符命名。与平常四则运算的计算规则相一致，即先乘除，后加减，括号内的子表达式优先计算。例如，中缀表达式 a*(c3-x2z/y)+u 的后缀表达式为 ac3x2zy/-*u+ 程序给每个运算符和括号设定一个优先级，并引入一个栈和一个存储后缀表达式的工作数组。函数 expr() 工作时，按自左至右逐个顺序扫描中缀表达式，如当前符号是变量名，就将该变量名直接复制到工作数组；如当前符号是运算符或括号，将当前符号的优先级和栈顶符号的优先级进行比较；若当前符号的优先级高，则当前符号进栈；反之，则进行出栈处理，并将从栈中退出的运算符依次复制到工作数组中，直到栈顶符号的优先级比当前符号的优先级低为止，然后将当前的运算符或左括号进栈。为使子表达式能优先处理，所以给左括号设定较高的优先级，但又为了能正确处理随后的子表达式，在左括号进栈时，它在栈中的优先级作了一定的改变。 初始时，expr() 函数预先在栈底设置一个符号'#'，其优先级比所有运算符和括号的优先级都低。程序还检查输入表达式的运算符和运算分量的合理性，以及括号是否正确配对。【程序3】 #include &ltstdio.h> #include &ltctype.h> #include &ltstdlib.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-&gtdata = x; q-&gtcode = c; q-&gtpri = p; _(1)_ ; *toppt = q; int pop(char *op, int *cp, NODE *toppt) /*链接存储栈的出栈函数*/ NODE q = toppt; if (*toppt = NULL) return 1; /*空栈 */ *op = q-&gtdata; cp = q-&gtcode; _(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, &ampoptop); /*预先在栈中置一个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 = &ampopchTbli; type = opchTbli.code; /*得到运算符的内部码 */