向顺序栈中压入新元素时,为什么先移动指针,再放入元素?

来源：蜘蛛抓取(WebSpider) 时间：2022-05-02 04:45 标签： 向顺序栈压入元素时

一步都应确切地、无二义性地定义；(3)可行性：每条指令可以执行且有正确的结果。

10、评价一个算法的好坏主要依据：1正确性2、可读性3、健壮性4、高效率

11、算法效率的衡量方法有：事后统计法和事前分析估算法；事前估算法主要

考虑：（1）算法选用的策略、（2）、问题的规模。

12、算法时间复杂度是算法中基本运算重复执行次数多少的量度。记作O(n)，

空间复杂度作为实现算法所需的辅助存储空间的大小，记作S(n)=O(f(n))。

1、线性表是具有相同特性的数据元素的一个有限序列。其特征有三：所有元素

类型相同、线性表是由有限个数据元素组织、线性表中的数据元素与位置有关的，这一点表明线性表不同于集合，线性表中的每一个元素都有一个对应的序号，线性表中元素可以重复出现。

2、线性结构特点：有“头”元素有“尾”元素，中间的元素有“前驱”元素和

3、线性表的顺序表示是指：用一组地址连续的存储单元依次存放线性表中的数

4、对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为O

（1），在表尾插入元素的时间复杂度为O（n）。

5、在下面的数组a中链接存储着一个线性表，表头指针为a[o].next，则该线性

4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表

更多“顺序栈中数据元素与栈顶指针的变化：非空栈中的栈顶指针top始终在的 （）下一个位置”相关的问题

阅读下列说明和c函数代码，将应填入 (n) 处的字句写在答题纸的对应栏内。

对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点，且每个结点仅访问一次的过程。函数InOrder。()借助栈实现二叉树的非递归中序遍历运算。

设二叉树采用二叉链表存储，结点类型定义如下：

在函数InOrder()中，用栈暂存二叉树中各个结点的指针，并将栈表示为不含头结点

的单向链表(简称链栈)，其结点类型定义如下：

BTree elem； ／*栈中的元素是指向二叉链表结点的指针*／

假设从栈顶到栈底的元素为en、en-1、…、e1，则不含头结点的链栈示意图如图5—5

StNode*q； ／*q暂存链栈中新创建或待删除的结点指针+／

visit(q)； ／*visit是访问结点的函数，其具体定义省略*／

free(q)； ／*释放原栈顶元素的结点空间*／

试题七（共 15 分）

阅读以下说明和C程序，将应填入 （n） 处的字句写在答题纸的对应栏内。

现有 n（n < 1000）节火车车厢，顺序编号为 1,2,3,...,n，按编号连续依次从 A方向的铁轨驶入，从 B 方向铁轨驶出，一旦车厢进入车站（Station）就不能再回到 A方向的铁轨上；一旦车厢驶入 B 方向铁轨就不能再回到车站，如图 7-1所示，其中 Station 为栈结构，初始为空且最多能停放 1000 节车厢。

下面的 C 程序判断能否从 B 方向驶出预先指定的车厢序列，程序中使用了栈类

STACK,关于栈基本操作的函数原型说明如下：

int Top(STACK s)：返回非空栈的栈顶元素值，栈中元素数目不变。

/*此处为栈类型及其基本操作的定义，省略*/

printf("请输入需要判断的车厢编号序列（以空格分隔） ： ");

阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。

函数print(BinTreeNode*t；DateType ＆x)的功能是在二叉树中查找值为x的结点，并打印该结点所有祖先结点。在此算法中，假设值为x的结点不多于一个。此算法采用后序的非递归遍历形式。因为退栈时需要区分右子树。函数中使用栈ST保存结点指针ptr以及标志tag，Top是栈顶指针。

设二叉树采用二叉链表作为存储结构。试用类Pascal语言实现按前序遍历顺序输出二又树中结点的非递归算法。要求定义所用结构。设栈已经定义：inits(S)，empty(S)，push(S，P)，pop(S)，top(S)分别为栈初始化，判栈空，入栈，出栈，看栈顶等操作。【北京工业大学1997二、1(10分)】

设将整数1、2、3、4依次进栈，只要出栈时栈非空，则可将出栈操作按任何次序夹人其中；请回答下述问题：

2．能否得到出栈序列1、4、2、3和1、4、3、2?答案为(27)。

3．请分析研究1、2、3、4的24种排列中，(28)序列是可以通过相应的入、出栈操作得到的。

●设将整数1、2、3、4依次进栈，只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：

2.能否得到出栈序列1、4、2、3和1、4、3、2？答案为 (27) 。

3.请分析研究1、2、3、4的24种排列中， (28) 序列是可以通过相应的入、出栈操作得到的。

一个栈(Stack)对象有三种状态：S1——栈空；S2——栈非空也非满；S3——栈满。则各个状态的条件如下：

S1：(t0)创建栈对象时初始化，这是系统做的

为简化问题，假设栈Stack的容量为2，栈元素的数据类型为整数。

根据题意，画出栈对象的状态迁移图；

以下关于栈和队列的叙述中，错误的是（ ）。

A.栈和队列都是线性的数据结构 B.栈和队列都不允许在非端口位置插入和删除元素 C.一个序列经过一个初始为空的栈后，元素的排列次序一定不变 D.一个序列经过一个初始为空的队列后，元素的排列次序不变

以下下关于栈和队列的叙述中，错误的是（ ）。

A.栈和队列都是线性的数据结构B.栈和队列都不允许在非端口位置插入和删除元素C.一个序列经过一个初始为空的栈后，元素的排列次序一定不变D.一个序列经过一个初始为空的队列后，元素的排列次序不变

已知Q是一个非空队列，S是一个空栈。仅用队列和栈的ADT函数和少量工作变量，使用 Pascal或C语言编写一个算法，将队列Q中的所有元素逆置。栈的ADT函数有： makeEmpty(S：stack)； ／／置空栈 push(S：stack；value：datatype)； ／／新元素value进栈 pop(S：stack)：datatype； ／／出栈，返回栈顶值

我要回帖

更多关于 向顺序栈压入元素时 的文章

 

随机推荐