前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构 | 每日一练(92)

数据结构 | 每日一练(92)

作者头像
小林C语言
发布2019-06-18 19:34:53
8930
发布2019-06-18 19:34:53
举报
文章被收录于专栏:C语言入门到精通

数据结构

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

——老子

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

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-06-18,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 C语言入门到精通 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档