《2000上半年程序员考试真题及答案-下午卷.doc》由会员分享，可在线阅读，更多相关《2000上半年程序员考试真题及答案-下午卷.doc（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、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-&g
2、tval; 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)_处的字句写在答卷的对应栏内。【函
3、数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)
4、_; 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
5、 =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)_;
6、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 <cty
7、pe.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, *num
8、top; /*工作数组和存储指针*/ 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 = NU
9、LL) 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
10、 (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 = o
11、pchTbli.code; /*得到运算符的内部码 */ c = *pos+; /*C 中存储下一个字符*/ if (type 5) /*如是运算符 */ if(m != 1) return 1; /*运算符个数与运算分量个数不相容*/ m = 0; /*运算符与运算分量一样多 */ if (type = 5) n+; /*左括号计数增1*/ if (type = 6) if (n- = 0) return 2; /*圆括号不匹配*/ if ( _(5)_ ) /*运算符或括号进栈 */ if (op->data = ( ) push(op->code, 1, &optop);
12、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->c
13、ode, op->pri, &optop); void main() int d; printf(请输入表达式 !n); gets(expStr); if (d = expr(expStr) = 0) printf(后缀表达式为 %sn,num); else printf(表达式句法错！错误类型为%dn,d); 试题四(21分) 阅读下列程序说明和C代码，将应填入 _(n)_ 处的字句写在答卷的对应栏内。程序4说明 有一种单人玩的游戏：设有 n(2 = n = 200) 堆薄片，各堆顺序用 0 至 n-1 编号，极端情况，有的堆可能没有薄片。在游戏过程中，一次移动只能取某堆上的若干张
14、薄片，移到该堆的相邻堆上。如指定 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 = ai ；若 i 堆是中间堆，则要求ci = 2ai。 (2)因在 ai>0 的所有堆中，薄片数最多的堆在平分过程中被
15、它的相邻堆取走的薄片数也最多。在用策略 (1) 搜索移动时，当发生没有满足条件 (1) 的可移走薄片的堆时，采用本策略，让在 ai>0 的所有堆中，薄片数最多的堆被它的相邻堆取走它的全部薄片。程序4 #include <stdio.h #define N 200 #define M 200 #define Limit 2000 struct int id; int k; wayLimit; /*存储每次移动的位置和薄片张数 */ int mc = 0; /*移动次数 */ int cN, aN, n int init( int *np, int *c, int *a ) /* 输入初始
16、数据，估算ai */ int i, n, d, min, v; long sum = OL; printf (输入n:); scanf (%d,&n); printf (输入各堆的薄片数(%d)n, M); for (i = 0; i = 0 & d M) ? d : 0; for (i = 0; i n; i+) sum += ci; if (sum % m) return 0; v = (int)(sum / n); a0 = 0; a1 = v - c0; for (i = 1; i <n-1; i+) ai+1 = _(1)_; for (min = 0, i = 1; i
17、n; i+) if (ai min) min = ai; for (i = 0; i 0) ci-1 += k; ci -= k; if (i n-1) ci+1 += k; ci -= k; ai -= k; waymc.id = i; waymc+.k = k; void search(int *c, int *a, int n) int i, d, m, pov, moved; do pov = moved = 0; for (i = 0; i =ai : ci = 2*ai) move( _(4)_ ) /*完成一次移动*/ moved = 1; break; if ( pov & !
18、moved) /*找薄片数最多的堆，且被相邻堆全部取走*/ for (m = 0, i = 0; i 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 next = b(3) q-next = p(4) return 1(5) dec(a+1,n-1)试题二(1) ap+1 = 0(2) ap % 10(3) a0 = p(4) u0 = k(5) dj != 1 或 dj 1(6) cj*uj试题三(1) q-link = *toppt(2) *toppt = q-link(3) *numtop+ = c(4) opchTb1i,data != c(5) op-pri optop-pri(6) &sop, &code, &optop(7) code 0试题四(1) v + 2*ai-1 -ci(2) aj 0(3) i=0 | i=n-1(4) i, ai, n, c, a(5) aj 0(6) cj m(7) m /= 2