习题三 栈和队列.doc

《习题三 栈和队列.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题3栈和队列3.1单项选择题1.一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是__C__。A.edcbaB.decbaC.dceabD.abcde2.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为__C__。A.iB.n=iC.n-i+1D.不确定3.栈结构通常采用的两种存储结构是__A__。A.顺序存储结构和链式存储结构B.散列方式和索引方式C.链表存储结构和数组D.线性存储结构和非线性存储结构4.判定一个顺序栈ST（最多元素为m0）为空的条件是_B___。A.top!

2、=0B.top==0C.top!=m0D.top==m0-15.判定一个顺序栈ST（最多元素为m0）为栈满的条件是_D___。A.top！=0B.top==0C.top！=m0D.top==m0-16.栈的特点是_B___，队列的特点是__A_。A.先进先出B.先进后出7.向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行__C__。(不带空的头结点)A.HS—＞next=s;B.s—＞next=HS—＞next;HS—＞next=s;C.s—＞next=HS;HS=s;D.s—＞next=HS;HS=HS—＞next;8.从一个栈顶指针

3、为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行_B___。(不带空的头结点)A.x=HS;HS=HS—＞next;B.x=HS—＞data;C.HS=HS—＞next;x=HS—＞data;D.x=HS—＞data;HS=HS—＞next;9.一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是___C_。A.4，3，2，1B.1，2，3，4C.1，4，3，2D.3，2，4，110.判定一个循环队列QU（最多元素为m0）为空的条件是_C___。A.rear-front==m0B.rear-front-1==m0C.fro

4、nt==rearD.front==rear+111.判定一个循环队列QU（最多元素为m0,m0==Maxsize-1）为满队列的条件是__A__。A.((rear-front)+Maxsize)%Maxsize==m0B.rear-front-1==m0C.front==rearD.front==rear+112.循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是_A___。A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-fro

5、nt13.栈和队列的共同点是_C___。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点3.2填空题（将正确的答案填在相应的空中）1.向量、栈和队列都是__线性__结构，可以在向量的__任何__位置插入和删除元素；对于栈只能在_栈顶___插入和删除元素；对于队列只能在_队尾___插入元素和__队首__删除元素。2.向一个长度为n的向量的第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动__n-i+1__个元素。3.向一个长度为n的向量中删除第i个元素（1≤i≤n）时，需向前移动__n-i__个元素。4.向栈

6、中压入元素的操作是_先移动栈顶指针，后存入元素___。5.对栈进行退栈时的操作是_先取出元素，后移动栈顶指针___。6.在一个循环队列中，队首指针指向队首元素的_前一个位置___。7.从循环队列中删除一个元素时，其操作是__先移动队首元素，后取出元素__。8.在具有n个单元的循环队列中，队满时共有_n-1___个元素。9.一个栈的输入序列是12345，则栈的输出序列43512是_不可能的___。10.一个栈的输入序列是12345，则栈的输出序列12345是__可能的__。3.3算法设计题:1.输入一个任意的非负十进制整数,输出与其等值的八进值数

7、。2.按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，并仿照教科书3.2节例3—1的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A-B*C/D+E↑F3.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。