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-082016年考研法律硕士(非法学)备考指导
- 03-082016考研管综大纲解析之中文写作考点精要
- 03-082016、2015年考研法律硕士(非法学)大纲变化对照表
- 03-082016考研管综大纲解析之中文写作100日备考纲要
- 03-082016、2015年考研农学大纲变化对照表
- 03-082016考研中医综合大纲发布高分秘笈必看
- 03-082016、2015年考研西医综合大纲变化对照表
- 03-082016年考研农学门类联考考试大纲
- 03-082016年考研法硕(非法学)大纲微调
- 03-082016年考研西医综合考试大纲