2014年考研数据结构辅导(16)
专业课
时间: 2019-03-09 12:17:12
作者: 匿名
尾递归和单向递归的消除不需要借用栈
单向递归和尾递归可直接用迭代实现其非递归过程
其他情形必须借助栈实现非递归过程。
证明:若借助栈由输入序列1,2,…,n得到输出序列为P1,P2,…,Pn(它是输入序列的一个排列),则在输出序列中不可能出现这样的情形:存在着i i 若Pi>Pj 说明大的数先于小的数出栈,那么在Pi出栈前Pj一定在栈中 证明:1)j 2)i 3)i 而Pi是最先出栈的那么在Pi为栈顶的时候,Pj和Pk一定都同时被压入栈中,那么就与1矛盾了,1要求Pj要在Pk入栈前出栈,而此时Pk Pj都在栈中所以假设不成立。
猜你喜欢
-
- 03-092017年考研《西方经济学》复习讲义:资源配置和经济制度
- 03-082018年考研专业课复有重点的复习就OK
- 03-092013年法律硕士(非法学)大纲变化综述
- 03-092016考研世界古代史知识点:原始的宗教和早期的文化
- 03-092015年考研教育学冲刺计划(全文)
- 03-092016年考研计算机专业辅导:TCP的慢启动
- 03-09法硕考研基础知识点:法与社会的一般关系
- 03-092013联考逻辑之重点题型:性质判断
- 03-09备考2018管理类考研需要注意这些事
- 03-082017年考研心理学大纲详解:心理学导论