程序员考试真题及答案
试题一(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)__;
isalpha 函数 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 (a[0] < a[1]) return 0;
return __(5)__;
}
试题二(18分)
阅读下列函数说明和 C 代码，将应填入__(n)__处的字句写在答卷的对应栏内。
【函数2.1说明】
设长正整数用数组存储，如有 k 位的长整数m用数组 a[] 存储：
m = a[k]*10k-1a[k-1]*10K-2+……+a[2]*101+a[1]*100
并用a[0]存储长整数m的位数，即a[0]=k。
通常，存储长整数数组的每个元素只存储长整数的一位数字。长整数运算时，为了运算方便，
产生的中间结果的某位数字可能会大于 9。这时，就应调用本函数将它规整，使数组的每个元素
只存储长整数的一位数字。规整运算函数 formal(int *a) 就实现这个特殊要求。
【函数2.1】
void formal(int *a)
{ int p;
for (p = 1; p < a[0] || a[p] >= 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) 是计算两个整数的组合数。由于计算结果超出 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 d[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() 函数预先在栈底设置一个符号'#'，其优先级比所有运算符和括号的
优先级都低。程序还检查输入表达式的运算符和运算分量的合理性，以及括号是否正确配
对。
【程序3】
#include <stdio.h>
#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 num[200], *numtop; /*工作数组和存储指针*/
Char expStr[200]; /*存储中缀表达式的字符数组*/
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;
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论