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

单项选择（2009年3月二级考试）

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

A、栈

B、树

C、队列

D、二叉树

答案解析

A

【解析】

根据栈的定义，栈是一种限定在一端进行插入与删除的线性表。

在主函数调用子函数时，主函数会保持当前状态，然后转去执行子函数，把子函数的运行结果返回到主函数，主函数继续向下执行，这种过程符合栈的特点。

讨论

数据结构与算法

某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是【】。

一棵二叉树有10个度为1的结点，7个度为2的结点，则该二叉树共有结点个数为【】。

某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根结点在第1层）【】

深度为5的满二叉树有__________个叶子结点。

一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为 __________。

已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为【】

树是结点的集合，它的根结点数目是【】

对于正整数n ，输出其和等于n且满足以下限制条件的所有正整数的和式，组成和式的数字自左至右构成一个非递增的序列。如 n = 4 ，程序输出为：4 = 44 = 3 + 14 = 2 + 24 = 2 ＋ 1 ＋ 1 4 = 1 ＋ 1 ＋ 1 ＋ 1test 是实现该功能的 C 程序段，请将未完成的部分补足，使之完整。test 函数为一递归函数，参数 n 为被分解和式的数， k 为当前的分解深度。算法思想是对 n 的所有合理的和式分解，将分解出的数（称为和数）存于二数组 a[]中。当其中一个分解己不再需要进一步进行时，即找到一个解，将存于 a[] 中的一个完整和式的和数输出。当还需要进一部分解时，以要进一部分解的数及分解深度为参数，递归调用 test 函数。#define MAXN 100 int a[MAXN]; test(int n,int k){ int i,j; for (j=__________；j>=1；j--）{ a[k]=j; if (__________）{ printf ( "%d = %d" , a[0]，a[l]); for (i = 2 ; i < = k ; i + + ) printf ( " + % d " , a[i]); printf ( " n " ); }else test(__________，k + l ); } }

写出和下列递归过程等价的非递归过程。void test(int sum){ int a; scanf("%d",&a); if(a==0) sum=1; else{ test(sum); sum=sum*a; } pritf("%d",sum); }

一般情况下，将递归转换成等价的非递归算法应该设置【】

栈的概念

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

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

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

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

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

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

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

栈的输入序列为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的后缀式是【】(-、+、*表示算术的减、加、乘运算，运算符的优先级和结合性遵循惯例)。

栈

算术表达式(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，则合法的出栈序列为【】。