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

单项选择（2014年秋程序员软考）

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

A、3

B、4

C、5

D、6

答案解析

C入栈序列为abc时，出栈序列可以为abc、acb、bac、bca、cba，以I表示入栈、O对应出栈，原则是：每个元素仅入栈、出栈各1次：;一次出栈操作的条件是栈不为空且只能让栈顶元素出栈。出栈序列为abc时，对应的操作序列为IOIOIO。出栈序列为acb时...

查看完整答案

讨论

数据结构与算法

含有n个元素的线性表采用顺序存储方式时，对其运算速度最快的操作是【】。

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

函数 Reverselist(LinkList headptr)的功能是将含有头结点的单链表就地逆置。处理思路是将链表中的指针逆转，即将原链表看成由两部分组成，已经完成逆置的部分和未完成逆置的部分，令s指向未逆置部分的第一个结点，并将该结点插入已完成部分的表头(头结点之后)，直到全部结点的指针域都修改完成为止。例如，某单链表如图所示，逆置过程中指针s的变化情况如图(a)(b)所示。链表结点类型定义如下：typedef struct Node{ int data， struct Node *next;}Node， *LinkList;void ReverseList (LinkList headptr){//含头结点的单链表就地逆置， headptr为头指针 LinkList p，s; if(__(1)__) return;//空链表(仅有头结点)时无需处理 p=__(2)__;//令p指向第一个元素结点 if (!p->next) return;//链表中仅有一个元素结点时无需处理 s= p->next;//s指向第二个元素结点 __(3)__=NULL;//设置第一个元素结点的指针域为空 while (s){ p=s;//令p指向未处理链表的第一个结点 s=__(4)__; p-> next= headptr-> next;//将p所指结点插入已完成部分的表头 headptr-> next=__(5)__; }}

对于下图，若采用邻接矩阵存储，则矩阵中的非0元素数目为【】。

对于下图，从顶点1进行深度优先遍历时，不可能得到的遍历序列是【】

在有13个元素构成的有序表data[1..13]中，用折半查找(即二分查找，计算时向下取整)方式查找值等于data[8]的元素时，先后与【】等元素进行了比较。

已知某二叉树的先序遍历序列为ABCD，后序遍历序列为CDBA，则该二叉树为【】。

在数据结构中，【】是与存储结构无关的术语。

设有字符串S='software'，其长度为3的子串数目为【】。

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

栈的概念

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

中缀表达式 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，则可能的出栈序列是【】。

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

如果入栈序列为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），则【】不可能是其出栈序列。

栈

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

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

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

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

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

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

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

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

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

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