资源描述：
《数据结构第三章习题课.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、1.一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（）。A.23415B.54132C.23145D.154322.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。A.不确定B.n-i+1C.iD.n-i3.若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i=1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。A.
2、top[2]-top[1]
3、=0B.top[1]+1=top[2]C.top[
4、1]+top[2]=mD.top[1]=top[2]4.栈在（）中应用。A.递归调用B.子程序调用C.表达式求值D.A，Ｂ，Ｃ5.执行完下列语句段后，i值为：（）intf(intx){return((x>0)?x*f(x-1):2);}inti;i=f(f(1));A．2B.4C.8D.无限递归6.表达式3*2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。A.3,2,4,1,1；(*^(+*-B.3,2,8；(*^-C.3,2,4,2,2；(*^(-D.3,2,8；(*^(-
5、7.用链接方式存储的队列，在进行删除运算时（）。A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改8.循环队列存储在数组A[0..m]中，则入队时的操作为（）。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)9.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的
6、容量至少应该是()。A．6B.4C.3D.210．表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是_______。答：23.12.3*2-4/34.5*7/++108.9/+（注：表达式中的点(.)表示将数隔开，如23.12.3是三个数）11.一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______。答：31212、链栈中为何不设置头结点?答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表
7、的头指针就可以了。1.【李春葆】向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。2.栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。3.队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。4.在具有n个单元的循环队列中，队满时共有n-1个元素。5.〖00年统考题〗带表头结点的空循环双向链表的长度等于0。L=head头结点R=headhead判断正误（判断下列概念的正
8、确性，并作出简要的说明。）（×）1.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。（×）2.在表结构中最常用的是线性表，栈和队列不太常用。错，不一定吧？调用子程序或函数常用，CPU中也用队列。（√）3.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（√）4.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略
9、有不同而已。（×）5.栈和链表是两种不同的数据结构。错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。（×）6.栈和队列是一种非线性数据结构。错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。（√）7.栈和队列的存储方式既可是顺序方式，也可是链接方式。（√）8.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（×）9.队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。错，后半句不对
10、。（×）10.一个栈的输入序列是12345，则栈的输出序列不可能是12345。错，有可能。单项选择题1.〖00年元月统考题〗栈中元素的进出原则是。Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出2.〖李春葆〗若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为。Ａ．iＢ．n=iＣ．n-i+1Ｄ
