大连东软数据结构题库全3

3 .7 习题 3 .7 .1 知识点：栈的基本概念 一、选择题 1① 下列哪种数据结构常用于函数调用（ A ）。 Ａ．栈 Ｂ．队列 Ｃ．链表 Ｄ．数组 2① 编译器中通常以哪种数据结构处理递归程序调用（ C ） Ａ．队列 Ｂ．数组 C．栈 D．记录 3① 下列哪些数据结构可用来实现栈（ D ）。 （1）链表 （2）数组 （3）树 （4）图 Ａ．（2），（3） Ｂ．（2），（4） C．（1），（4） D．（1），（2） 4② 元素的入栈序列是 a,b,c,d，则栈的不可能的输出序列是（ C ）。 A．dcba B．abcd C．dcab D．cbad 5② 已知栈的最大容量为 4。若进栈序列为 1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ C ）。 A．5，4，3，2，1，6 B．2，3，5，6，1，4 C．3，2，5，4，1，6 D．1，4，6，5，2，3 6② 若以 S 和 X 分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（ D ）。 A．SXSSXXXX B ．SXXSXSSX C．SXSXXSSX D．SSSXXSXX 7① 对于栈操作数据的原则是（ B ）。【青岛大学 2001】 A． 先进先出 B．后进先出 C．后进后出 D．不分顺序 8① 栈在（ D ）中应用。【中山大学 1998】 A．递归调用 B．子程序调用 C．表达式求值 D．A，Ｂ，Ｃ 9② 一个栈的输入序列为 123… n，若输出序列的第一个元素是 n，输出第 i（1<=i<=n）个元素是（B ）。【中山大学 1999】 A．不确定 B．n-i+1 C．i D．n-i 10② 若一个栈的输入序列为 1,2,3,… ,n，输出序列的第一个元素是 i，则第 j 个输出元素是（D ）。【武汉大学 2000】 A．i-j-1 B．i-j C．j-i+1 D．不确定的 11② 有六个元素 6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ C ）【北方交通大学 2001】 A．5 4 3 6 1 2 B．4 5 3 1 2 6 C．3 4 6 5 2 1 D．2 3 4 1 5 6 12② 输入序列为 ABC，可以变为 CBA 时，经过的栈操作为（B ）【中山大学 1999】 A．push,pop,push,pop,push,pop B．push,push,push,pop,pop,pop C．push,push,pop,pop,push,pop D．push,pop,push,push,pop,pop 13② 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ D ）数据结构最佳。【西安电子科技大学 1996】 A．线性表的顺序存储结构 B．队列 C．线性表的链式存储结构 D．栈 二、填空题 1① 栈是一种特...