《数据结构练习题》栈与队列.doc

栈和队列1　简述栈和线性表的区别。2　简述栈和队列这两种数据结构的相同点和不同点。3　如果进栈的元素序列为A，B，C，D，则可能得到的出栈序列有多少种？写出全部的可能序列。4　如果进栈的元素序列为1，2，3，4，5，6，能否得到4，3，5，6，1，2和1，3，5，4，2，6的出栈序列？并说明为什么不能得到或如何得到。5　写出下列程序段的运行结果（栈中的元素类型是char）：main(　){ SEQSTACK s,*p; char x, y; p = s; initstack(p); x = ′c′; y = ′k′; push(p,x); push(p,′a′); push(p,y); x = pop(p); push(p,′t′); push(p,x); x = pop(p); push(p,′s′); while(!empty(p)) { y = pop(p); printf(″%c″,y);} printf(″%c＼n″,x);}6　将一个非负十进制整数转换成二进制数，用非递归算法和递归算法来实现。7　写一算法将一顺序栈中的元素依次取出，并打印元素值。8　设单链表中存放着n个字符，试编一算法，判断该字符串是否有中心对称关系，例如xyzzyx，xyzyx都算是中心对称的字符串。9　写出下列程序段的运行结果（队列中的元素类型是char）：main(　){ SEQQUEUE a, *q; char x, y; q = a; x=′e′; y=′c′; initqueue(q); enqueue(q,′h′); enqueue(q,′r′); enqueue(q,y); x = dequeue(q); enqueue(q,x); x = dequeue(q); enqueue(q,′a′); while(!empty(q)) { y = dequeue(q); printf(″%c″,y);} printf(″%c＼n″,x);}10　写一算法将一链队列中的元素依次取出，并打印这些元素值。