数据结构与算法-等级考试试题(程序员软考 2016年春栈的概念)

单项选择（2016年春程序员软考）

设有初始为空的栈S，对于入栈序列a、b、c、d，经由一个合法的进栈和出栈操作序列后(每个元素进栈、出栈各1次)，以c作为第一个出栈的元素时，不能得到的序列为【】。

A、cdba

B、cbda

C、cdab

D、cbad

答案解析

C

【解析】

栈的修改规则是后进先出。对于题目给出的元素序列，若要求c先出栈，此时a、b尚在栈中，因此这三个元素构成的出栈序列只能是cba，而元素d可在b出栈之前进栈，之后b只能在d出栈后再出栈，因此可以得到出栈系列cdba。同理，c可在a出栈之前进栈，从而得到出栈序列cbda。若e在a出栈后入栈、出栈，则得到出栈序列cbad。由于a不能在b出栈前出栈，因此不能得到cdab。

讨论

数据结构与算法

对于长度为n的线性表(即n个元素构成的序列)，若采用顺序存储结构(数组存储)，则在等概率下，删除一个元素平均需要移动的元素数为【】。

递归函数执行时，其调用和返回控制是利用【】来进行的。

与算术表达式3-(2+7)/4对应的二又树为【】。

在待排序的一组关键码序列k1，k2，…，kn中，若ki和kj相同，且在排序前ki领先于kj，那么排序后，如果ki和kj的相对次序保持不变，ki仍领先于kj，则称此类排序为稳定的。若在排序后的序列中有可能出现kj领先于ki的情形，则称此类排序为不稳定的。【】是稳定的排序方法。

若待排序记录按关键字基本有序，则宜采用的排序方法是【】。

【】不符合二叉排序树的定义。

某有向图G及其邻接矩阵如下所示。以下关于图的邻接矩阵存储的叙述中，错误的是【】。

最优二叉树(或哈夫曼树)是指权值为w1，w2，…，wn的n个叶结点的二叉树中带权路径长度最小的二叉树。【】是哈夫曼树(叶结点中的数字为其权值)。

三个互异的元素a、b、c依次经过一个初始为空的栈后，可以得到【】种出栈序列。

若栈采用链式存储且仅设头指针，则【】时入栈和出栈操作最方便。

栈的概念

中缀表达式 A-(B + c/d) * E的后缀形式是【】

设栈 S 和队列 Q 的初始状态为空，元素 a 、 b 、 c 、 d 、e、 f 依次通过栈 S ，一个元素出栈后即进入队列 Q 。若这 6 个元素出队列的顺序是 b 、 d 、 c 、f、 e 、 a ，则栈 S 的容量至少应该是__________。

算术表达式a+b-c*d的后缀式是【】(-、+、*表示算术的减、加、乘运算，运算符的优先级和结合性遵循惯例)。

如果入栈序列为ABCD，不可能出现的出栈序列是【】

设栈的输入序列为1,2,3,...,n，输出序列为a1,a2,a3,...,an，若存在1≤k≤n使得 ak=n，则当k≤i≤n时，ai 为【】

栈的输入序列为1,2,3,...,n，输出序列为a1,a2,a3,...,an，若ai=n(1≤i≤n)，则有 ak>ak+1>an。

设栈的输入序列是（1，2，3，4），则【】不可能是其出栈序列。

按照“后进先出”原则组织数据的数据结构是【】

支持子程序调用的数据结构是【】。

如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是【】。

栈

算术表达式(a+b)*(c-d/e)的后缀表达式为【】

一个栈的入栈序列是A，B，C，D，E，则栈的不可能的输出序列是【】

对于一个初始为空的栈，其入栈序列为abc时，其出栈序列可以有【】种。

算术表达式a*(b-c)+d的后缀式是【】(-、+、*表示算术的减、加、乘运算，运算符的优先级和结合性遵循惯例)。

对于一个初始为空的栈，其入栈序列为abc时，其出栈序列可以有【】种。

算术表达式a+(b-c)*d的后缀式是【】(-、+、*表示算术的减、加、乘运算，运算符的优先级和结合性遵循惯例)。

对于顺序栈和链栈，【】不是两者共有的运算特征。

若元素a、b、c、d、e、f依次进栈，允许进栈、出栈操作交替进行。但不允许连续三次进行出栈工作，则不可能得到的出栈序列是【】。

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

为支持函数调用及返回，常采用称为“【】”的数据结构。