扫码加入训练营

牢记核心词

学习得礼盒

计算机考研:数据结构常用算法精析(3)

2013-12-10 15:46:58来源:新东方在线编辑

  双端队列:

  两端都可以插入和删除,但实际应用中通常是输出受限的双端对列和输入受限的双端队列

  输入受限的双端队列指的是:一端可以输入输出另一端只能输出不能输入

  输出受限的双端队列指的是:一端可以输入输出另一端只能输入不能输出

  求从迷宫入口到出口的一条最短路径

  要用到队列,因为队列可以用在广度优先中,队列中的元素表示离中心点依次越来越远。

  所以第一次找到出口肯定是半径最短的。

  链式栈:

  a0

  ^

  a1

  top ……

  An

  链式队列:

  front

  rear

  q

  头

  a0

  an-1

  ^

  N个结点的不同二叉树有: 等于不同的进出栈总数

  有n个数顺序(依次)进栈,出栈序列有Cn种,Cn=[1/(n+1)]*(2n)!/[(n!)*(n!)]。=

  尾递归和单向递归的消除不需要借用栈

  单向递归和尾递归可直接用迭代实现其非递归过程

  其他情形必须借助栈实现非递归过程。

  证明:若借助栈由输入序列1,2,…,n得到输出序列为P1,P2,…,Pn(它是输入序列的一个排列),则在输出序列中不可能出现这样的情形:存在着i

  i

  若Pi>Pj 说明大的数先于小的数出栈,那么在Pi出栈前Pj一定在栈中

  证明:1)j

  2)iPk 说明Pi出栈前,Pk在栈中

  3)iPj 说明Pi出栈前Pj在栈中

考研公开课小程序

本文关键字: 计算机 考研 数据结构

考研英语核心词汇营

背词+听课+练习+督学,学习得礼盒

更多资料
更多>>
更多内容

关注新东方在线考研服务号

获得21考研真题及答案解析

1. 打开手机微信【扫一扫】,识别上方二维码;
2.点击【关注公众号】,获取资料大礼包。

考研资料大礼包
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料