数据结构 | 每日一练(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)递归程序的入口语句和出口语句一般用条件判断语句来实现。递归程序由基本项和归纳项组成。基本项是递归程序出口,即不再递归即可求出结果的部分;归纳项是将原来问题化成简单的且与原来形式一样的问题,即向着“基本项”发展,最终“到达”基本项。

本文分享自微信公众号 - C语言入门到精通(yclzl960229)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券