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

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

　　 有递归算法如下 【北京邮电大学 一 （ 分）】

　　FUNCTION  sum (n:integer):intger;　　BEGIN　　IF n= THEN sum:= 　　ELSE BEGIN read(x) sum:=sum(n )+x END 　　END

　　设初值n= 读入 x=

　　问 ( ) 若x为局部变量时 该函数递归结束后返回调用程序的sum=? 并画出在递归过程中栈状态的变化过程

　　( ) 若x为全程变量递归结束时返回调用程序的sum=?

　　 画出对算术表达式A B*C/D E↑F求值时操作数栈和运算符栈的变化过程 【东南大学 一 （ 分）】

　　 计算算术表达式的值时 可用两个栈作辅助工具 对于给出的一个表达式 从左向右扫描它的字符 并将操作数放入栈S 中 运算符放入栈S 中 但每次扫描到运算符时 要把它同S 的栈顶运算符进行优先级比较 当扫描到的运算符的优先级不高于栈顶运算符的优先级时 取出栈S 的栈顶和次栈顶的两个元素 以及栈S 的栈顶运算符进行运算将结果放入栈S 中（得到的结果依次用T T 等表示） 为方便比较 假设栈S 的初始栈顶为?（?运算符的优先级低于加 减 乘 除中任何一种运算） 现假设要计算表达式 A B*C/D+E/F 写出栈S 和S 的变化过程 【山东科技大学 一 （ 分）】

　　 有字符串次序为 * y a/y^ 利用栈 给出将次序改为 y *ay ^/ 的操作步骤 （可用X代表扫描该字符串过程中顺序取一个字符进栈的操作 用S代表从栈中取出一个字符加入到新字符串尾的出栈操作 例如 ABC变为BCA的操作步骤为XXSXSS）【东北大学 一 ( 分)】

　　 内存中一片连续空间（不妨假设地址从 到m）提供给两个栈S 和S 使用 怎样分配这部分存储空间 使得对任一个栈 仅当这部分空间全满时才发生上溢 【东北大学 一 ( 分)】