数据结构 | 每日一练（92）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1. 试证明：若借助栈由输入序列 1,2,…,n 得到输出序列为 P 1 ,P 2 ,…,P n （它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着 i<j<k,使 P j <P k <P i 。

2. 设一数列的输入顺序为 123456，若采用堆栈结构，并以 A 和 D 分别表示入栈和出栈操作，试问通过入出栈操作的合法序列。

（1） 能否得到输出顺序为 325641 的序列。

（2） 能否得到输出顺序为 154623 的序列。

3.

（1） 什么是递归程序？

（2） 递归程序的优、缺点是什么？

（3） 递归程序在执行时，应借助于什么来完成？

（4） 递归程序的入口语句、出口语句一般用什么语句实现？

正确答案

PS：||代表注释

1、如果i<j，则对于p i <p j 情况，说明p i 在p j 入栈前先出栈。而对于p i >p j 的情况，则说明要将p j 压到p i 之上，也就是在p j 出栈之后p i 才能出栈。这就说明，对于i<j<k，不可能出现p j <p k <p i 的输出序列。换句话说，对于输入序列1，2，3，不可能出现3，1，2的输出序列。

2、

（1）能得到325641。在123依次进栈后，3和2出栈，得部分输出序列32；然后4，5入栈，5出栈，得部分出栈序列325；6入栈并出栈，得部分输出序列3256；最后退栈，直到栈空。得输出序列325641。其操作序列为AAADDAADADDD。

（2）不能得到输出顺序为154623的序列。部分合法操作序列为ADAAAADDAD，得到部分输出序列1546后，栈中元素为23，3在栈顶，故不可能2先出栈，得不到输出序列154623。

3、

（1）一个函数在结束本函数之前，直接或间接调用函数自身，称为递归。例如，函数f在执行中，又调用函数f自身，这称为直接递归；若函数f在执行中，调用函数g，而g在执行中，又调用函数f，这称为间接递归。在实际应用中，多为直接递归，也常简称为递归。

（2）递归程序的优点是程序结构简单、清晰，易证明其正确性。缺点是执行中占内存空间较多，运行效率低。

（3）递归程序执行中需借助栈这种数据结构来实现。

（4）递归程序的入口语句和出口语句一般用条件判断语句来实现。递归程序由基本项和归纳项组成。基本项是递归程序出口，即不再递归即可求出结果的部分；归纳项是将原来问题化成简单的且与原来形式一样的问题，即向着“基本项”发展，最终“到达”基本项。