第章栈与队列复习(ANSWER).docVIP

栈与队列复?习 1．设有一顺序?栈S，元素s1,s2,s3,s4,s5,s6 依次进栈，如果6个元?素出栈的顺?序是s2,s4,s3,s6,s5,s1，则栈的容量?至少应该是?（ ）。 A．2 B．3 C．4 D．5 2．向一个栈顶?指针为to?p的链栈中?插入一个s?所指的结点?时，其操作步骤?为（ ） A．top-next=s; B．s-next=top-next; top-next=s; C．s-next=top; top=s; D．s-next=top; top=top-next; 3．一个栈的入?栈序列是1?，2，3，4，5，则栈的不可?能输出序列?是（ ）。 A．3，5，4，2，1 B．3，2，4，5，1 C．1，2，3，4，5 D．5，4，3，1，2 4．表达式a*(b+c)-d的后缀表?达式是（ ） A．abcd*+- B．abc+*d- C．abc*+d- D．-+*abcd 5．一个队列的?入队序列是?1，3，5，7，9，则出队的输?出序列只能?是（ ） A．9，7，5，3，1 B．1，3，5，7，9 C．1，5，9，3，7 D．9，5，1，7，3 6．、设循环队列?中数组的下?标范围是1?～n，其头尾指针?分别为f和?r，则其元素个?数为（ ） A．r-f B. r-f+1 C. (r-f)% n+1 D. (r-f+n)% n 7．设数组da?ta[m]作为循环队?列SQ的存?储空间，front?为队头指针?，rear为?队尾指针，则执行入队?操作后其尾?指针rea?r值为（ ） A. rear=rear+1 B. rear=(rear-1)%m C. rear=(rear+1)%(m-1) D. rear=(rear+1)%m 8．两个栈共享?一片连续的?内存空间时?，为提高内存?利用率，减少溢出机?会，应把2个栈?的栈底分别?设在这片内?存空间的两?端。（对/错） 9、用链接方式?存储的队列?，在进行删除?运算时（ ）。 A. 仅修改头指?针 ????B. 仅修改尾指?针 C. 头、尾指针都要?修改 ? D. 头、尾指针可能?都要修改 解决“假溢出”的一种方法?，通常采用“牺牲一个存?储单元”或“作标记”的方法解决?“队满”和“队空”的判定问题?#inclu?deiostr?eam.h typed?ef int datat?ype; #defin?e MAXSI?ZE 100 //顺序队列 struc?t Seque?ue { datat?ype data[MAXSI?ZE]; int front?,rear; }; Seque?ue *init() { Seque?ue *sq=new Seque?ue; sq-front? =sq-rear =MAXSI?ZE-1; retur?n sq; } int empty?(Seque?ue *sq) { retur?n sq-front?==sq-rear; } int full(Seque?ue *sq) { retur?n sq-front?==(sq-rear+1)%MAXSI?ZE; } int inque?ue(Seque?ue *sq,datat?ype x) { if(full(sq))retur?n -1; sq-rear=(sq-rear+1)%MAXSI?ZE; sq-data [sq-rear ]=x; retur?n 1; } int outqu?eue(Seque?ue *sq,datat?ype *x) { if(empty?(sq))retur?n -1; sq-front?=(sq-front?+1)%MAXSI?ZE; *x=sq-data [sq-front? ]; retur?n 1; } void main() { Seque?ue* sq=init(); int i=1; datat?ype x; while?(!full(sq)) inque?ue(sq,i++); while?(!empty?(sq)) { outqu?eue(sq,x); coutx,; } } /*链队列 typed?ef struc?t node { datat?ype data; node *next; }Qnode?; typed?ef struc?t { Qnode? *front?,*rear; }LQueu?e; LQueu?e *init() { Qnode? *p=new Qnode?; LQueu?e *q=new LQueu?e; p-nex