数据结构考研分类复习真题 第三章 栈和队列[22]

五 算法设计题

设有两个栈SS都采用顺序栈方式并且共享一个存储区[Omaxsize]为了尽量利用空间减少溢出的可能可采用栈顶相向迎面增长的存储方式试设计SS有关入栈和出栈的操作算法【哈尔滨工业大学 七 （分）】

设从键盘输入一整数的序列a a a…an试编写算法实现用栈结构存储输入的整数当ai≠时将ai进栈当ai=时输出栈顶整数并出栈算法应对异常情况（入栈满等）给出相应的信息【南京航空航天大学 六 （分）】

设表达式以字符形式已存入数组E[n]中#为表达式的结束符试写出判断表达式中括号（（和））是否配对的C语言描述算法EXYX(E); (注算法中可调用栈操作的基本算法)【北京科技大学 九 （分）】

从键盘上输入一个逆波兰表达式用伪码写出其求值程序规定逆波兰表达式的长度不超过一行以$符作为输入结束操作数之间用空格分隔操作符只可能有+*/四种运算例如 +*$【山东师范大学 七 （分）】

假设以I和O分别表示入栈和出栈操作栈的初态和终态均为空入栈和出栈的操作序列可表示为仅由I和O组成的序列称可以操作的序列为合法序列否则称为非法序列【武汉大学 五】

（）下面所示的序列中哪些是合法的？

A IOIIOIOO B IOOIOIIO C IIIOIOIO D IIIOOIOO

（）通过对（）的分析写出一个算法判定所给的操作序列是否合法若合法返回true否则返回false（假定被判定的操作序列已存入一维数组中）

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []