数据结构
设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A、线性表的顺序存储结构B、队列C、线性表的链式存储结构D、栈
题目
设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。
- A、线性表的顺序存储结构
- B、队列
- C、线性表的链式存储结构
- D、栈
相似问题和答案
第1题：
A、顺序表
B、链表
C、队列
D、栈
第2题：
判断一个表达式中左右括号是否匹配，采用(38)这一数据结构实现较为方便。
A．栈
B．队列
C．线性表的链式存储
D．线性表的顺序存储
解析：在高级语言的编译阶段，从头到尾来扫描语句，检验括号是否匹配的方法可用“期待的急迫程度”来描述，这需要一个栈来帮助实现。换言之，每读到一个括号，若是右括号，则使置于栈顶的最急迫的期待得以消解，或者是不合法的情况；若是左括号，则作为一个新的更急迫期待压入栈中，自然使原有的在栈中的所有未消解的期待的急迫性都降了一级。这是栈的一个典型应用。
第3题：
此题为判断题(对，错)。
第4题：
设计一个判别表达式左、右括号是否配对出现的算法，采用______数据结构最佳。
A．线性表的顺序存储结构
B． 栈
C． 队列
D． 线性表的链式存储结构
解析： 栈是一种具有记忆能力的线性表，存取规则是先进后出，判别时遇到一个左括号时就向栈插入左括号，遇到右括号就从栈中删除一个左括号，最后若栈中没有左括号就证明括号成对，所以采用栈最适合判断表达式中括号是否成对出现。
第5题：
阅读下列说明和算法，回答问题1和问题2。
【说明】
算法5-1用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号或者右括号，则给出相应的提示信息，如表5-1所示。
在算法5-1中，stack为一整数栈。算法中各函数的说明如表5-2所示。
【算法5-1】
将栈stack置空，置EOF为false
ch←nextch();
while(not EOF)
k←kind(ch);
ifk== (1) )
push( (2) ;push( (3) ;
else if(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
为了识别更多种类的括号，对算法5-1加以改进后得到算法5-2。算法5-2能够识别圆括号、方括号和花括号(不同类型的括号不能互相匹配)。改进后，函数kind(charch)的参数及其对应的返回值如表5-3所示。
【算法5-2】
将栈stack置空, 置EOF为false
ch←nextch();
while(not EOF)
k←kind(ch);
if(k＞0)
if(判断条件 1)
push( (5) ); push( (6) ); push( (7) );
else if(判断条件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
请将【算法5-1】和【算法5-2】中(1)至(7)处补充完整。
(1) 1 (2) col (3) row (4) 2 (5) col (6) row (7) k
第6题：
阅读以下算法说明和C程序，根据要求回答问题1和问题2。
【说明】
【算法4-1】的功能是用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号而没有对应的左括号或者右括号，则给出相应的提示信息，如图1-18所示。
在【算法4-1】中，slack为一整数栈。算法中各函数的说明如表1-11所示。
【算法4-1】
将栈stack置空，置EOF为false
Ch＜-nextch()；
while(not EOF)
k←kind(ch)；
if (k ==(1) ) {
push( (2) )；
push( (3) )；}
else if( k ==(4) )
if(not empty()){
pop()；
pop()；)
else{
显示错误信息(缺少对应左括号或右括号)：
显示行号row：显示列号col：)
End if
End if
Ch＜-nextch()；
end while
if(not empty())
显示错误信息(缺少对应左括号或右括号)：
While(not empty()){
row＜-pop()；
col＜-pop()：
显示行号row：显示列号col；)
End while
End if
为了识别更多种类的括号，对【算法4-1】加以改进后得到【算法4-2】。【算法4-2】能够识别圆括号、方括号和花括号(不同类型的括号不能互相匹配)。改进后，函数kind(charch)的参数及其对应的返回值如表1-12所示。
【算法4-2】
将栈stack置空，置EOF为false
Ch＜-nextch()；
while(not EOF){
k＜- kind(ch)；
if(k ＞ 0)
if(判断条件1){
push( (5) )；
push( (6) )；
push( (7) )；}
else if(判断条件2 and判断条件3){
pop()；
pop()；
pop()；}
else {
显示错误信息(缺少对应左括号或右括号)；
显示行号row；显示列号col；)
end if
end if
ch ＜- nextch()；)
end while
if(not empty()){
显示错误信息(缺少对应左括号或右括号)；
While(not empty()){
Pop()；
row ＜- pop()：
col ＜- pop()；
显示行号row；显示列号col；))
end while
end if
请将【算法4-1】和【算法4-2】中，(1)～(7)空缺处的内容补充完整。
(1)1 (2)col (3)row (4)2 (5)col (6)row (7)k
第7题：
阅读以下算法说明和C程序，根据要求回答问题1至问题2。
[说明]
[算法4-1]的功能是：用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号或者右括号，则给出相应的提示信息，如图4-18所示。
在[算法4-1]中，stack为一整数栈。算法中各函数的说明如表4-16所示。
[算法4-1] 将栈stack置空，置EOF为false
为了识别更多种类的括号，对[算法4-1]加以改进后得到[算法4-2]。[算法4-2]能够识别圆括号、方括号和花括号(不同类型的括号不能互相匹配)。改进后，函数kind(charch)的参数及其对应的返回值如表4-17所示。
[算法4-2]
[问题1]
请将[算法4-1]和[算法4-2]中，(1)～(7)空缺处的内容补充完整。
[问题2]
请从以下选项中选择相应的判断逻辑填补[算法4-2]中的“判断条件1”至“判断条件3”。注意，若“判断条件2”的逻辑判断结果为假，就无需对“判断条件3”进行判断。
判断条件1： (8)
判断条件2： (9)
判断条件3： (10)
[供选择的答案]
A．栈顶元素表示的是与当前字符匹配的左括号
B．栈顶元素表示的是与当前字符匹配的右括号
C．字符是左括号 D．字符是右括号 E．栈不空 F．栈空
G．字符是括号
这是一道要求读者用创建Thread类的子类的方法实现多线程的编程题。本题的解答思路如下。 通常把限定只能在一端进行插入和删除操作的线性表称为栈，所以栈又称为运算受限的线性表。把可以进行插入和删除操作的一端称为栈顶(习惯用top指针指示)，而另一端称之为栈底。当栈中不包含任何数据元素时，这个栈就为空栈。 由于栈具有“后进先出”的运算特点，因此在程序设计中应用十分广泛。例如，进制转换、括号匹配的检验、表达式求值以及迷宫求解等。 [算法4-1]的功能是检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号或者右括号，则给出图4-18所示的提示信息。从图4-18所给出的信息可知，程序不但要求检查出是否有括号匹配错误，而且还需给出具体错在哪个括号。通常，括号匹配的规则是把最近的左右括号配成一对，所以括号匹配最常用的方法是遇到左括号则入栈，遇到右括号就出栈。这样，出栈的左括号与当前的右括号是匹配的。 [算法4-1]分析： ①栈置空，置EOF为FALSE，并从文件中读取第一个字符到ch，然后进入循环。循环体执行一次处理一个ch。进入循环，利用kind函数算出ch的类型k。 ②虽然[算法4-1]中有(1)～(4)空缺处，但其基本结构却很明显，大致流程如下。 当k等于什么的时候把什么入栈； 当k等于什么的时候且栈不为空的时候，进行出栈操作。如果栈为空，则打印错误信息；如果都不是，则读文件的下一个字符再次进入循环。 根据以上所提及的算法可知，入栈操作应该发生在类型k为1(即ch为左括号)时，而出栈操作应该发生在类型k为2(即ch为右括号)时。因此(1)空缺处所填写的内容是“1”，(4)空缺处所填写的内容是“2”。 由于在(4)空缺处之后的出栈操作中，并没有用到栈的内容。因此可能有些读者理所当然地认为栈中的内容没有什么用，可以在(2)、(3)空缺处随便压个ch，即两个空缺处所填写“ch”。但换个角度思考，从逻辑上就可以推翻这种解答。如果(2)、(3)空缺处压的是同样的数据，又是在同一位置出栈，算法大可只用一个PUSH、POP就可以了。 由语句“row-pop()；col-pop()；”可知，(2)、(3)空缺处应该把row和col压入堆栈。由于是先弹出row后弹出col，且根据栈的“后进先出”操作规则可知，应先将col压入栈，再压入row。因此 (2)空缺处所填写的内容是“col”，(3)空缺处所填写的内容是“row"。 [算法4-2]分析： 同理，由[算法4-2]中的语句“row-pop()；col-pop()；”可知，(5)、(6)空缺处应该把row和col压入堆栈。由于是先弹出row后弹出col，因此应先将col压入栈，再压入row，即(5)空缺处所填写的内容是“col”，(6)空缺处所填写的内容是“row”。 由于判断条件1为真时，需要进行入栈操作，因此判断条件1应是判断字符是不是左括号，如果是就入栈，即(8)空缺处应选择选项C的“字符是左括号”。 判断条件2和判断条件3是相关联的，当两个判断条件都为真时，要进行出栈操作，因此要判断栈是否为空。由此可以得出在判断条件2和判断条件3中，至少有一个必定是用来判断栈是否为空的。可以用判断栈顶元素来确定当前括号是否和栈中压入括号是同一类型的，但前提是左括号类型入了栈，而且要在栈顶。如果(7)空缺处压入的是k，则正好符合这一条件。所以(7)空缺处所填写的内容是“k”。 同时，判断括号是否匹配的条件也就可以确定了，如果当前ch是右括号且当前栈顶的左括号(只有左括号入了栈)类型与ch匹配，则匹配成功。根据试题说明中的提示信息：若“判断条件2”的逻辑判断结果为假，就无需对“判断条件3”进行判断，所以应把“栈不空”作为判断条件2，“栈顶元素表示的是与当前字符匹配的左括号”作为判断条件3，即(9)空缺处应选择选项E的“栈不空”，(10)空缺处应选择选项A的“栈顶元素表示的是与当前字符匹配的左括号”。
第8题：
A.线性表的顺序存储结构
B、队列
D.线性表的链式存储结构
E.D.栈
解释：利用栈的后进先出原则。
第9题：
设计一个“判别在表达式中左、右括号是否配对出现”的算法，采用______数据结构最佳。
A．线性表的顺序存储结构
B．栈
C．队列
D．线性表的链式存储结构
第10题：
A、需要进行出栈操作但栈已空
B、需要进行入栈操作但栈已满
C、表达式处理已结束,但栈中仍留有字符“(”
D、表达式处理已结束,但栈中仍留有字符“)”