程序员考试下午试题解答方法与技巧(1)

如果说程序员考试解上午题无技巧可言的话，那么解下午题就是70%的实力加30%的方法与技巧，若运用到极致的话，会是“四两拨千斤”。曾有很多网友问我，有没有“金玉良言”、“武功秘诀”等，我会先问他看书多少、做题多少;如果他既没看书又没做题，那就免谈了，因为神仙也难帮他;若看过书、做过题且总是在及格的边缘，那么就可以看看以下的方法与技巧了。

一、解题的步骤

1、把握题意。

根据问题的描述，确定问题的已知条件和隐含条件，并了解算法(程序)要达到的目的，窥测出题者的用意。这是至关重要的一步，是对题目的整体把握。准确的讲，这一步就要知道输入是什么，又得到什么样的输出结果。

2、快速确定算法。

每个题目的题干都有详细的描述，通过对描述的分析，要确定题目应该属于哪种类型的题，用到了哪一类数据结构以及相应的算法。有些题目可能不属于任何数据结构，则它可能与某类算法有关;但也有一些算法纯粹是数学方法。

3、带着问题阅读程序。

阅读、分析程序结构时，如果有很多子函数，首先弄清楚各函数之间的关系和各函数的作用;如果程序较长，则应该根据算法过程，把每个程序段与算法的每个过程对应起来，确定相应的程序段功能。在程序中，已经定义了某些变量，则在理解程序时，首先必须理解这些变量的含义。

找到算法思想的核心程序段及主函数，重点阅读。

4、根据具体的语言填空。

区分结构化程序设计语言和面向对象的程序设计语言的不同，由于C++与Java比较接近，有时容易搞混。要区分是语法填空还是算法填空。

二、解题的方法与技巧

1、心无旁鹜，勇往直前。

进入下午考试，也许有疲劳或不好的感觉，自信心就会下降;当看到题干很长，算法较复杂的题时，就有想回避或焦虑、急燥的情绪。这是典型的“两军未战，兵先屈”的败兴思绪。要知道两对手相遇勇者胜，勇者相遇智者胜。抛开所有不必要的想法，相信自己的实力，做到心无旁鹜，勇往直前。

2、审清题干(必需认真)。

题干包含了整个题目的条件和要求，但也有很多提示信息在程序的“注释”当中;若题干比较复杂，就要注意将题干“分段”来阅读，前后注意衔接，必要时在草稿纸上记载下关键数据。

有时候题干很长，看似很复杂，让很多人望而却步。其实，这种题更好解，因题干长了则提示信息也就多了。主要是考你有没有勇气和耐心。

3、正确阅读程序。

要从主函数开始，再到子函数(过程)，整体阅读两遍，找出各部分功能，对照题干的算法要求，然后再定位填空。

4、巧妙填空。

填空时要注意整体观念，因为有些空的答案在后面有提示。通常比较集中的填空，不容易填，往往这是题目的核心算法所在。比较分散的空通常是对语法的填空。

三、示例

【说明】

计算机在处理算术表达式时，首先将其转换为后缀表达式。例如，表达式“46+5*(120-37)”的后缀表达式形式为“46 5 120 37 - * +”。

计算后缀表达式时，从左至右扫描后缀表达式：若遇到运算对象，则压入栈中;遇到运算符，则从栈中弹出相关运算对象进行计算，并将运算结果压入栈中，重复以上过程，直到后缀表达式扫描结束。例如，后缀表达式“46 5 120 37 - * +”的计算过程为:

a. 依次将46、5、120、37压入栈中;

b. 遇到“-”，取出37、120，计算120–37，得83，将其压入栈中;

c. 遇到“*”，取出83、5，计算5*83，得415，将其压入栈中;

d. 遇到“+”，取出415、46，计算46+415，得461，将其压入栈中;

e. 表达式结束，则计算过程完成。

函数computing(char expr[],int *result)的功能是基于栈计算后缀形式的表达式(以串形式存入字符数组expr)的值，并通过参数result 返回该值。函数的返回值为-1/0分别表示表达式有/无错误。假设表达式中仅包含数字、空格和算术运算符号，其中所有项均以空格分隔，且运算符仅包含加(“+”)、减(“-”)、乘(“*”)、除(“”)。

函数computing中所用栈的基本操作的函数原型说明如下：

void InitStack(STACK *s)：初始化栈。

void Push(STACK *s, int e): 将一个整数压栈，栈中元素数目增1。

void Pop(STACK *s)：栈顶元素出栈，栈中元素数目减1。

int Top(STACK s)：返回非空栈的栈顶元素值，栈中元素数目不变。

int IsEmpty(STACK s)：若s是空栈，则返回1否则返回0。

【C函数】

int computing(char expr[], int *result)
{
　STACK s; int tnum, a,b; char *ptr;
　InitStack(&s);
　ptr = expr; /*字符指针指向后缀表达式串的第一个字符*/
　while (*ptr!='') {
if (*ptr==' ') { /*当前字符是空格*/
__(1)__ ; /*字符指针指向下一字符*/
continue;
}
else
if (isdigit(*ptr)) {
/*当前字符是数字,则将该数字开始的数字串转换为数值*/
tnum =__ (2)__ ;
while (*ptr>=’0’ && *ptr <=’9’) {
tnum = tnum * 10 +__ (3)__ ;
ptr++;
}
Push(__ (4)__ );
}
else /*当前字符是运算符或其他符号*/
if (*ptr=='+'||*ptr=='-'||*ptr =='*'||*ptr =='/'){
if (!IsEmpty(s)) {
a = Top(s); Pop(&s); /*取运算符的第二个运算数*/
　if (!IsEmpty(s)) {
b = Top(s); Pop(&s); /*取运算符的第一个运算数*/
　}
　else return -1;
}
else return -1;
switch (*ptr) {
　case '+': Push(&s,b+a); break;
　case '-': Push(&s,b-a); break;
　case '*': Push(&s,b*a); break;
　case '/': Push(&s,b/a); break;
}
}
else
　return -1;
ptr++; /*字符指针指向下一字符*/
} /* while */
if (IsEmpty(s)) return -1;
else {
　__(5)__ = Top(s); Pop(&s); /*取运算结果*/
　if (!IsEmpty(s)) return -1;
　return 0;
}
}  

1.试题分析。

栈的主要特点是后进先出，即后进栈的元素先处理。本题的题干很长，且程序结构较为复杂，但算法简单。其实这类题的填空比较分散，相对来说看懂了题干的算法思想，是比较容易填写的。

函数computing()的功能是基于栈计算后缀形式的表达式(以串形式存入字符数组expr)的值，并通过参数result 返回该值。函数的返回值为-1/0分别表示表达式有/无错误。看看程序结构：

结合上面的程序结构图，程序中用ptr来指向后缀表达式，如果首先碰到的字符是空格，则字符指针ptr指向下一字符，所以第(1)空要填ptr++。在第②个if语句处，当前字符是数字，则将该数字开始的数字串转换为数值，程序中选用了一个中间变量tnum，要对它初始化，所以第(2)空要填0。

一个多位数(指数值大于9以上的数)在中缀表达式中是连续的，每两组多位数之间是空格，所以题中将一组多位数(字符串)用*ptr来表示，当碰到中间的空格时，认为这一组结束。第(3)空是如何将字符转成数值，常用的方法就是用这个字符的ASCII码减去字符“0”的ASCII码，所以要填*ptr-‘0’。当转变成数值以后，则把它压入栈push(&s,tnum)，则第(4)空填&s,tnum。在第⑤个if语句处，是对那些双目运算不合法(缺少或不匹配)进行检查，若不满足，则返回-1。若合法，则执行switch()语句。得到最后的运算结果值，题目中要求“并通过参数result 返回该值”，所以第(5)空要填*result。

2.试题参考答案。

(1)ptr++，或++ptr，或ptr=ptr+1
(2)0，或tnum = 0
(3)*ptr–’0’，或*ptr-48
(4)&s,tnum
(5)*result   

四、后记

常言道“熟能生巧”、“打铁还得本身硬”，再好的方法与技巧若没有基础，是发挥不了作用的;如若有了一定的功底，再差的招式也会产生很大的威力，就像金庸小说中杨过的那柄钝剑。程序员考试的难度较大，下午题要求对C语言、数据结构与算法、面向对象的程序设计语言(C++、Java、VB三选一)、流程图比较熟练;如果只看不练，不会有提高。