2010年软件水平考试软件设计师练习试题(下午题)

　　试题二

　　阅读下列说明和算法，回答问题 1 和问题2，将解答填入答题纸的对应栏内。

　　[说明]

　　算法2-1 是用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号或者右括号，则给出相应的提示信息，如下所示：文件 提示信息

　　(1+2)

　　abc) 缺少对应左括号：第2 行，第4 列

　　((def)gx)) 缺少对应左括号：第3 行，第10 列

　　(((h)

　　ij)(k

　　(1ml)

　　缺少对应右括号：第5 行，第4 列; 第4

　　行，第1 列

　　在算法2-1 中，stack 为一整数栈。算法中各函数的说明如下表所示：

　　函数名 函数功能

　　push(int i) 将整数i 压入栈stack 中。

　　pop() stack 的栈顶元素出栈。

　　empty() 判断stack 栈是否为空.若为空，函数返回1，否则函数返回0。

　　nextch()

　　读取文本文件中的下一个字符，并返回该字符的ASCII 值，将字符所在的行号以及字 符在行中的位置分别存储到变量row 和col中，若遇到文件结束符，则将变量EOF 置为true;kind(charch)判断字符ch 是左括号还是右括号，若是左括号，函数返回1，若是右括号，函数返回2， 若两者都不是，函数返回0。

　　[算法2-1]

　　将栈stack 置空，置EOF 为false

　　ch←nextch();

　　while(not EOF)

　　k←kind(ch);

　　if (k ==__(1)__)

　　push(__(2)__); push(__(3)__);

　　elseif( k ==__(4)__)

　　if(not empty())

　　pop();pop()：

　　else

　　显示错误信息(缺少对应左括号或右括号);显示行号row;显示列号col;

　　endif

　　endif

　　ch←nextch();

　　endwhile

　　if(not empty())

　　显示错误信息(缺少对应左括号或右括号);

　　while(not empty())

　　row←pop(); col←pop();

　　显示行号row;显示列号col;

　　endwhile

　　endif

　　为了识别更多种类的括号，对算法2-1 加以改进后得到算法2-2。算法2-2 能够识别圆括号，方括号和花括号(不同类型的括号不能互相匹配)。改进后，函数kind(charch)的参数及其对应的返回值如下表所示：

　　ch ( ) { } [ ] 其它

　　返回值 1 2 3 4 5 6 0

　　[算法2-2]

　　将栈stack 置空，置EOF 为false

　　ch←nextch();

　　while(not EOF)

　　k←kind(ch);

　　if(k > 0)

　　if(判断条件1)

　　push(__(5)__)：push(__(6)__);push(__(7)__)：

　　elseif( 判断条件2 and 判断条件3 )

　　pop(); pop(); pop();

　　else

　　显示错误信息(缺少对应左括号或右括号);显示行号row;显示列号col;

　　endif

　　endif

　　ch←nextch();

　　endwhile

　　if(not empty())

　　显示错误信息(缺少对应左括号或右括号);

　　while(not empty())

　　pop();row←pop();col←pop();

　　显示行号row;显示列号col;

　　endwhile

　　endif

　　[问题1]

　　请将[算法2-1]和[算法2-2]中(1)至(7)处补充完整。

　　[问题2]

　　请从下面的选项中选择相应的判断逻辑填补[算法2-2]中的“判断条件广至“判断条件3”。注意，若“判断条件2”的逻辑判断结果为假，就无需对“判断条件3”进行判断。

　　(a)字符是括号 (b)字符是左括号 (c)字符是右括号 (d)栈空 (e)栈不空

　　(f)栈顶元素表示的是与当前字符匹配的左括号

　　(g)栈顶元素表示的是与当前字符匹配的右括号