发布时间 : 星期三 文章栈、队列练习题（答案）更新完毕开始阅读39b36b3d240c844768eaeec0
栈、队列练习题
一、选择题
1. 栈和队列的共同特点是( )。
A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2. 若让元素1、2、3、4依次入栈，则出栈次序不可能出现（ ） A．3 2 1 4 B．2 1 4 3 C．1 4 2 3 D．4 3 2 1 3. 栈的插入和删除操作在( )进行。 A. 栈顶 B. 栈底
C. 任意位置
D. 指定位置
4. 用单链表表示的链式队列的队头在链表的（ ）位置。
A. 链头 B. 链尾 C. 链中 D. 以上都不是
5. 在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是（ ）。 A． p->next=s; s->prior=p;
p->next->prior=s; s->next=p->next; B． s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; C． p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; D． s->prior=p; s->next=p->next; p->next->prior=s; p->next=s; 6. 设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列( )。 A．A, B, C, D, E B．B, C, D, E, A C．E, A, B, C, D D．E, D, C, B, A
7. 在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top
作为栈顶指针，当做出栈处理时，top变化为( )。 A．top不变
B．top=0
C．top--
D．top++
8. 向一个栈顶指针为hs的链栈中插入一个s结点时，应执行( )。 A．hs->next=s; B．s->next=hs; hs=s;
C．s->next=hs->next;hs->next=s; D．s->next=hs; hs=hs->next;
9. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队
尾指针，则判断队满的条件为( )。
A．rear％n= = front B．（front+l）％n= = rear C．rear％n -1= = front D．(rear+l)％n= = front
10.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队
尾指针，则判断队空的条件为( )。 A．rear％n= = front B．front+l= rear C．rear= = front
D．(rear+l)％n= front
11.在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操
作为( )。
A．front=front->next B．rear=rear->next C．rear=front->next D．front=rear->next
二、填空题
1. 队列的插入操作是在队列的__队尾___进行，删除操作是在队列的__队头__进行。 2. 数据的逻辑结构被分为__集合____、 __线性__ 、_树___和_图___四种。 3. 链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的___指针域的
值。
4. 栈可以进行插入、删除操作的那一端，叫做栈 栈顶 ，队列可以进行插入操作的那
一端叫做队 队尾 。
5. 设有一空栈，现有输入序列1，2，3，4经过push, push, pop, push, pop, push, pop, pop
后，输出序列是__2,3,4,1____。
6. 无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂
度均相同为 O(n) 。
三、判断题
1、 在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top
作为栈顶位置，当做出栈处理时，top变化为top++。 ( 0 )
2、 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和
队尾指针，则判断队空的条件为rear = = front。 ( 1 ) 3、 链式栈通常会选用链表的表尾一段作为栈顶。( 0 )
4、 链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。( 1 ) 5、 若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。( 0 ) 6、 在用单链表表示的链式队列Q中，队头指针为Q->front，队尾指针为Q->rear，则
队空条件为Q->front == Q->rear。( 1 ) 四、程序设计题
（1） 括号的匹配算法
void ExpIsCorrect(char exp[], int n)//判断有n个字符的字符串exp左右括号是否配对正确 { SeqStack myStack; //定义堆栈 int i; for(i = 0; i < n; i++) { if( exp[i]=='(') myStack.Push(exp[i]); if( exp[i]==')') if(myStack.NotEmpty()==0) break; else myStack.Pop(); } if(myStack.NotEmpty()==1||i