数据结构与算法-考研试题(暨南大学 2023年顺序栈)

单项选择（2023年暨南大学）

表达式a*(b+c)-d 的后缀表达式是【】

A、abcd+-

B、-+*abcd

C、abc+*d-

D、abc*+d-

答案解析

C

讨论

二叉树

将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为35的结点的左孩子编号为【】。

按照二叉树的定义，具有3个结点的二叉树有【】种。

在一棵二叉树中，中序遍历的第一个结点，是二叉树的最左下结点。

已知一颗二叉树的先序序列和后序序列，一定能构造出该树。

由树转化为二叉树，该二叉树的右子树不一定为空。

设二叉树中度为0的结点数为30，度为1的结点数为20，则该二叉树中总共有_____个结点数。

在N个结点的线索二叉树中线索的数目为______.

阅读下面的程序代码，写出此函数的功能。void F(Bitree T,Stack &S){ if(T){ Push(S,T->data); if(!T->Lchild && !T->Rchild)PrintStack(S); else{ F(T->Lchild,S); F(T->Rchild,S); } Pop(S); }}

假设表中关键字序列为(41，36，58，12，79，25)，将关键字依次插入一棵初始为空的二叉排序树，然后删除结点 41。(1) 画出二叉排序树的生成过程；(2)画出删除结点41后的二叉排序树。

假设二叉树采用二叉链表存储结构，试编写一个非递归算法，输出中序遍历序列中第k个结点的数据值。

顺序栈

不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。

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

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

若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是【】

循环链表的主要优点是【】

任何一个无向连通图的最小生成树【】

深度优先遍历类似于二叉树的【】

如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是【】

算法的时间复杂度不是O(nlogn)的算法是【】

用邻接表表示图进行广度优先遍历时，通常采用【】来实现算法。

栈

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

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

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

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

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

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

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

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

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

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