栈、队列练习题(答案)

栈、队列练习题一、选择题1. 栈和队列的共同特点是( )。A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2. 若让元素1、2、3、4依次入栈，则出栈次序不可能出现（ ）A3 2 1 4 B2 1 4 3 C1 4 2 3 D4 3 2 13. 栈的插入和删除操作在( )进行。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,下列是不可能的出栈序列( )。AA, B, C, D, E BB, C, D, E, ACE, A, B, C, D DE, D, C, B, A 7. 在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为( )。Atop不变 Btop=0 Ctop- Dtop+8. 向一个栈顶指针为hs的链栈中插入一个s结点时，应执行( )。Ahs-next=s; Bs-next=hs; hs=s;Cs-next=hs-next;hs-next=s; Ds-next=hs; hs=hs-next;9. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为( )。Arearn= = front B（front+l）n= = rearCrearn -1= = front D(rear+l)n= = front10. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为( )。Arearn= = front Bfront+l= rearCrear= = front D(rear+l)n= front11. 在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为( )。Afront=front-next Brear=rear-nextCrear=front-next Dfront=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( expi=() myStack.Push(expi); if( expi=) if(myStack