数据结构与算法-等级考试试题(二级考试 2007年4月栈的概念)

单项选择（2007年4月二级考试）

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

A、e3，e1，e4，e2

B、e2，e4，e3，e1

C、e3，e4，e1，e2

D、任意顺序

答案解析

B由栈“后进先出”的特点可知，其出栈顺序不能任意；题中，若e3先出，则中e1不可能比e2先出；e2，e4，e3，e1是可行的出栈顺序，其执行顺序是：e1进栈→e2进栈→e2出栈→e3进栈→e4进栈→e...

查看完整答案

讨论

数据结构与算法

如果G是一个具有n个顶点的连通无向图，那么G最多有__________条边，最少有__________条边。

n个顶点的连通图用邻接矩阵表示时，该矩阵至少有__________个非零元素。

一个具有n个结点的弱连通图至少有__________条边。

对于一个具有n个结点的连通无向图，如果它有且只有一个简单回路，那么此图有__________条边。

在一个有n个顶点的无向网中，有O(n1.5*log2n)条边，则应该选用【】算法来求这个网的最小生成树，从而使计算时间较少。

在下列两种求图的最小生成树的算法中，【】算法适合于求边稀疏的网的最小生成树。

Kruskal算法的时间复杂度为__________，它对__________图比较合适。

试列中下列图中全部可能的拓扑排序序列。

若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存在。

对于一个有向图，不用拓扑排序，如何判断图中是否存在环？

栈的概念

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

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

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

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

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

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

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

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

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

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

栈

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

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

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

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

设元素a、b、c、d依次进入一个初始为空的栈，则不可能通过合法的栈操作序列得到【】。

表达式可采用后缀形式表示。例如，“a+b”的后缀式为“ab+”。那么，表达式“a*(b-c)+d”的后缀表示为【】

对于一个初始为空的栈，其入栈序列为 1,2,3,...,n(n>3)，若出栈序列的第一个元素是1则出栈序列的第n个元素【】

递归函数执行时，需要【】来提供支持。

对于初始为空的栈S，入栈序列为a、b、c、d，且每个元素进栈、出栈各1次。若出栈序列的第一个元素为d，则合法的出栈序列为【】。

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