数据结构与算法-考研试题(南京大学 2000年栈的概念)

填空题（2000年南京大学）

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

答案解析

3

讨论

数据结构与算法

顺序队列一般应该组织成为环状队列的形式，而且一般队列头或尾其中之一应该特殊处理。例如，队列为 listarray [ 0 ... n-1] ，队列头指针为front ，队列尾指针为 rear ，则 listarray[rear]表示下一个可以插入队列的位置。请解释其原因。

设一单项链表的头指针为head，链表的记录中包含整数类型的key域，试设计算法，将此链表的记录按照key递增的顺序进行就地排序。

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

用数组表示的循环队列的队首和队尾位置分别为1和 max_size，试给出判断队列为空和为满的边界条件。

若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后， rear和加front的值分别为多少？

在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应念是一个【】结构。

若用单链表来表示队列则应该选用【】

用单链表表示的链式队列的队头在链表的【】位置。

对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为__________。

在深度为7的满二叉树中，叶子结点的个数为【】

栈的概念

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

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

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

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

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

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

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

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

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

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

栈

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

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

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

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

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

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

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

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

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

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