数据结构与算法-面试题试题(腾讯公司校园招聘 2016年栈的概念)

单项选择（2016年腾讯公司校园招聘）

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

A、EDCBA

B、DECBA

C、DCEAB

D、ABCDE

答案解析

C

讨论

数据结构与算法

下列哪两个数据结构，同时具有较高的查找和删除性能【】？

利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树以后，查找元素35要进行【】次元素间的比较。

在分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成__________块最好；若分成25块，其平均查找长度为__________。

分块查找要求将待查找的表均匀地分成若干块，块中诸记录的顺序可以是任意的，但块与块之间____________。

用二分法查找一个线性表时，该线性表必须具有的特点是____________。

在n个记录的有序顺序表中进行折半查找，最大的比较次数是__________。

有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。

在分块检索中，对256个元素的线性表分成__________块最好，每块的最佳长度是__________；若每块的长度为8，其平均检索长度为__________。

若在线性表中采用折半查找元素，该线性表应该【】。

用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。

栈的概念

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

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

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

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

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

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

如果入栈序列为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。

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

栈

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

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

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

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

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

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

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

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

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

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