2000上半年程序员考试真题及答案-下午卷.doc-资料库

第1页 / 共7页

第2页 / 共7页

第3页 / 共7页

第4页 / 共7页

第5页 / 共7页

第6页 / 共7页

第7页 / 共7页

2000 上半年程序员考试真题及答案-下午卷试题一(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 (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; for (i = 1; i <= u[0]; i++) /*将整数 1 至 b 顺序存于数组 d */ /*从 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; for (i = 1; i < = u[0]; i++) /*将 u 中各整数相乘，存于长整数 c */ /*长整数 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; 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; continue; /*运算符个数与运算分量个数不相容 */ /*运算分量比运算符多 1 个 */ } else { /*处理运算符或非法字符 */ for (i = 0; opchTb1[i].code != -1 && ___(4)___ ; i++) if (opchTb1[i].code == -1) return 3; op = &opchTbl[i]; type = opchTbl[i].code; c = *pos++; /*得到运算符的内部码 */ /*C 中存储下一个字符*/ /*非法字符 */ } if (type < 5) { /*如是运算符 */ if(m != 1) return 1; m = 0; /*运算符与运算分量一样多 */ /*运算符个数与运算分量个数不相容*/ } if (type == 5) n++; if (type == 6) { if (n-- == 0) return 2; /*运算符或括号进栈 */ if /*左括号计数增 1*/ ( ___(5)___ ) if (op->data == '(' ) push(op->code, 1, &optop); else push(op->data, op->code, op->pri, &optop); /*圆括号不匹配*/ else { while (optop != NULL && op->pri <= optop->pri) { pop( ___(6)___ ); if ( ___(7)___ ) { /* 运算符复制到工作数组*/ *numtop++ = ' '; *numtop++ = stop; } } if (op->data=='0') return (n!=0||(m!=1&&numtop>num))?4( *numtop='\0'); else if(op->data!=')') push (op->data, op->code, op->pri, &optop); } } } void main() { int d; printf("请输入表达式 !\n"); gets(expStr); if ((d = expr(expStr)) == 0) printf("后缀表达式为 %s\n",num); else printf("表达式句法错！错误类型为%d\n",d); } 试题四(21 分)

阅读下列程序说明和 C 代码，将应填入 ___(n)___ 处的字句写在答卷的对应栏内。 [程序 4 说明] 有一种单人玩的游戏：设有 n(2 <= n <= 200) 堆薄片，各堆顺序用 0 至 n-1 编号，极端情况，有的堆可能没有薄片。在游戏过程中，一次移动只能取某堆上的若干张薄片，移到该堆的相邻堆上。如指定 i 堆 k 张 k 移到 i-1(i>0) 堆，和将 k 张薄片移至 i+1(i<n-1) 堆。所以当有两个堆与 i 堆相邻时，i 堆原先至少有 2k 张薄片；只有一个堆与 i 堆相邻时，i 堆原先至少有 k 张薄片。游戏的目标是对给定的堆数，和各堆上的薄片数，按上述规则移动薄片，最终使各堆的薄片数相同。为了使移动次数较少些，移动哪一堆薄片，和移多少薄片先作以下估算：设 ci: i 堆的薄片数(0 <= i < n,0 <= ci <= 200); v：每堆的平均薄片数； ai: i 堆的相邻堆可以从 i 堆得到的薄片数。估算方法如下： v = c0+a1-a0 v = c1+a0+a2-2a1 a1 = v+a0-c0 a2 = v+2a1-a0-c1 …… …… V = ci+ai-1+ai+1-2ai ai+1 = v+2ai-ai-1-ci 这里并不希望准确地求出 A0 至 an-1，而是作以下处理：若令 a0 为 0，能按上述算式计算出 A1 至 an-1。程序找出 a 中的最小值，并让全部 a 值减去这最小值，使每堆移去的薄片数大于等于 0。实际操作采用以下贪心策略： (1)每次从第一堆出发顺序搜索每一堆，若发现可从 i 堆移走薄片，就完成一次移动。即，i 堆的相邻堆从 i 堆取走 ai 片薄片。可从 i 堆移薄片到相邻堆取于 i 堆薄片数：若 i 堆是处于两端位置( i = 0 i = n-1), 要求 ci >= ai ；若 i 堆是中间堆，则要求 ci >= 2ai。 (2)因在 ai>0 的所有堆中，薄片数最多的堆在平分过程中被它的相邻堆取走的薄片数也最多。在用策略 (1) 搜索移动时，当发生没有满足条件 (1) 的可移走薄片的堆时，采用本策略，让在 ai>0 的所有堆中，薄片数最多的堆被它的相邻堆取走它的全部薄片。 [程序 4] #include <stdio.h> #define N 200 #define M 200 #define struct { int id; int k; } way[Limit]; int mc = 0; int c[N], a[N], n int init( int *np, int *c, int *a ) { int i, n, d, min, v; long sum = OL; /*移动次数 */ Limit 2000 /*存储每次移动的位置和薄片张数 */ /* 输入初始数据，估算 ai */ printf ("输入 n:"); scanf ("%d",&n); printf ("输入各堆的薄片数(<%d)\n", M);

for (i = 0; i < n; i++) { scanf ( "%d",&d); c[i] = ( d >= 0 && d < M) ? d : 0; } for (i = 0; i < n; i++) sum += c[i]; if (sum % m) return 0; v = (int)(sum / n); a[0] = 0; a[1] = v - c[0]; for (i = 1; i <n-1; i++) a[i+1] = ___(1)___; for (min = 0, i = 1; i < n; i++) if (a[i] < min) min = a[i]; for (i = 0; i < n; i++) a[i] -= min; *np = n; return 1; } void move (int i, int k, int n, int *c, int *a) { if (i > 0) { c[i-1] += k; c[i] -= k; } if (i < n-1) a[i] -= k; way[mc].id = i; way[mc++].k = k; { c[i+1] += k; c[i] -= k;} } void search(int *c, int *a, int n) { int i, d, m, pov, moved; do { pov = moved = 0; for (i = 0; i < n; i++) /*搜索满足策略(1)的堆*/ if ( ___(2)___ ) { pov = 1; if (( ___(3)___ )?(c[i]>=a[i] : c[i] >= 2*a[i])) { move( ___(4)___ ) moved = 1; break; /*完成一次移动*/ } } if ( pov && !moved) { /*找薄片数最多的堆，且被相邻堆全部取走*/ for (m = 0, i = 0; i < n; i++) if ( ___(5)___ && ___(6)___ ) { k = i; m = c[i]; } if (k > 0 && d < n-1) ___(7)___ ; move (k, m, n, c, a); } } while (mc < limit && pov); } void main() { int i; if (init(&n, c, a) == 0 ) { printf("薄片总数不能被平分\n"); return; } search(c, a, n); printf(" 序号移动位置号各相邻位置得到薄片数\n"); for (i = 0; i < mc; i++) printf("%4d%10d%18d\n", i+1, way[i].id, way[i].k); printf("\n");} 试题一参考答案

(1) h = b (2) q->next = b (3) q->next = p (4) return 1 (5) dec(a+1,n-1) 试题二 (1) a[p+1] = 0 (2) a[p] % 10 (3) a[0] = p (4) u[0] = k (5) d[j] != 1 或 d[j] > 1 (6) c[j]*u[j] 试题三 (1) q->link = *toppt (2) *toppt = q->link (3) *numtop++ = c (4) opchTb1[i],data != c (5) op->pri > optop->pri (6) &sop, &code, &optop (7) code <= 4 && code >0 试题四 (1) v + 2*a[i-1] -c[i] (2) a[j] > 0 (3) i==0 || i=n-1 (4) i, a[i], n, c, a (5) a[j] > 0 (6) c[j] > m (7) m /= 2

资料库

2000上半年程序员考试真题及答案-下午卷.doc

相关推荐

程序员考试

热门标签

最新资料