搜索
数据结构课后练习题第3章栈和队列1/5北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1第3章栈和队列一、选择题1.栈结构通常采用的两种存储结构是（A）。A、顺序存储结构和链表存储结构B、散列和索引方式C、链表存储结构和数组D、线性链表结构和非线性存储结构2.设栈ST用顺序存储结构表示，则栈ST为空的条件是（B）A、ST.top-ST.base0B、ST.top-ST.base==0C、ST.top-ST.basenD、ST.top-ST.base==n3.向一个栈顶指针为HS的链栈中插入一个s结点时，则执行（C）（注：当有头结点选B）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;4.从一个栈顶指针为HS的链栈中删除一个结点，用x保存被删除结点的值，则执行（C）（应无头结点）A、x=HS；HS=HS-next;B、HS=HS-next；x=HS-data;C、x=HS-data；HS=HS-next;D、s-next=Hs；Hs=HS-next;5.表达式a*(b+c)-d的后缀表达式为（B）A、abcdd+-B、abc+*d-C、abc*+d-D、-+*abcd6.中缀表达式A-（B+C/D）*E的后缀形式是（D）A、AB-C+D/E*B、ABC+D/E*C、ABCD/E*+-D、ABCD/+E*-7.一个队列的入列序列是1，2，3，4，则队列的输出序列是（C）A、4，3，2，1B、1，2，3，4C、1，4，3，2D、3，2，4，18.循环队列SQ采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front和rear，则判定此循环队列为空的条件是（C）A、Q.rear-Q.front==nB、Q.rear-Q.front-1==nC、Q.front==Q.rearD、Q.front==Q.rear+19.循环队列SQ采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front和rear，则判定此循环队列为满的条件是（C）A、Q.front==Q.rearB、Q.front!=Q.rearC、Q.front==(Q.rear+1)%nD、Q.front!=(Q.rear+1)%n10.若在一个大小为6的数组上实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（B）A、1，5B、2,4C、4，2D、5，111.用单链表表示的链式队列的队头在链表的（A）位置A、链头B、链尾C、链中12.判定一个链队列Q（最多元素为n个）为空的条件是（A）A、Q.front==Q.rearB、Q.front!=Q.rearC、Q.front==(Q.rear+1)%nD、Q.front!=(Q.rear+1)%n13.在链队列Q中，插入s所指结点需顺序执行的指令是（B）A、Q.front-next=s；f=s;B、Q.rear-next=s；Q.rear=s;C、s-next=Q.rear；Q.rear=s;D、s-next=Q.front；Q.front=s;14.在一个链队列Q中，删除一个结点需要执行的指令是（C）数据结构课后练习题第3章栈和队列2/5北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1A、Q.rear=Q.front-next;B、Q.rear-next=Q.rear-next-next;C、Q.front-next=Q.front-next-next;D、Q.front=Q.rear-next;15.用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（D）A、仅修改队头指针B、仅修改队尾指针C、队头尾指针都要修改D、队头尾指针都可能要修改。16.栈和队列的共同点是（C）A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点17.消除递归（B）需要使用栈。A、一定B、不一定18.设有一顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素出栈的顺序是s2，s3，s4，s6，s5，s1，则栈的容量至少应该是（B）A、2B、3C、5D、619.若一个栈的输入序列是a，b，c，则通过入、出栈操作可能得到a,b,c的不同排列个数为（B）A、4B、5C、6D、720.设有一顺序栈已经含有3个元素，如图3.1所示元素a4正等待进栈。下列不可能出现的出栈序列是（A）A、a3,a1,a4,a2B、a3,a2,a4,a1C、a3,a4,a2,a1D、a4,a3,a2,a1图3.121.链栈和顺序栈相比，有一个比较明显的优势是（A）A、通常不会出现栈满的情况B、通常不会出现栈空的情况C、插入操作更容易实现D、删除操作更加容易实现22.若一个栈的输入序列是1，2，3，4，…，n，输出序列的第一个元素是n，则第i个输出元素是（C）A、不确定B、n-iC、n-i+1D、n-i-123.以下说法正确的是(A)A、因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况B、因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况C、对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢”D、对于顺序栈而言在栈满状态下如果此时再作进栈运算，则会发生“下溢”。二、判断题1.在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。V2.链栈与顺序栈相比的一个优点是链栈插入和删除操作更加方便。X3.若一个栈的输入序列为1，2，3，…，n，其输出序列的第一个元素为n，则其输出序列的每个元素一定满足ai=i+1(i=1,2,…,n)。X4.在链队列中，即使不设置尾指针也能进行入队操作。V5.在对链队列（带头指针）做出队操作时，不会改变front指针的值。V6.循环队列中元素个数为rear-front。X数据结构课后练习题第3章栈和队列3/5北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-17.一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到4,3,1,2。X8.一个栈的输入序列是1,2,3,4，则在栈的输出序列中可以得到1,2,3,4。V9.若以链表作为栈的存储结构，则进栈需要判断栈是否满。X10.若以链表作为栈的存储结构，则出栈需要判断栈是否空。V三、填空题1.栈的特点是（后进先出），队列的特点是（先进先出）。2.线性表、栈、队列都是（线性）结构，可以在线性表的（任意）位置插入和删除元素；对于栈只能在（栈顶）插入和删除元素；对于队列只能在（队尾）插入元素和在（队首）位置删除元素。3.有程序如下，则此程序的输出结果（栈的元素类型是SelemType为char）是（Stact）。voidmain(){stacks;charx,y;initstack(s);x=’c’;y=’k’;push(s,x);push(s,’a’);push(s,y);pop(s,x);push(s,’t’);push(s,x);pop(s,x);push(s,’s’);while(!stackempty(s)){pop(s,y);printf(y);}printf(x);}4.在栈顶指针为HS的链栈中，判定栈空的条件是（HS==NULL）。5.向栈中压入元素的操作是先（存入元素）后（移动栈顶指针）。6.对栈进行退栈操作是先（移动栈顶指针）后（取出元素）。7.用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（O(1)）和（O(n)）；若只设尾指针，则出队和入队的时间复杂度分别是（O(1)）和（O(1)）。8.从循环队列中删除一个元素时，其操作是（先取出元素，再移动头指针）。9.在一个循环队列中，队首指针指向队首元素的（当前位置）。10.在具有n个单元的循环队列中，队满时共有（n-1）个元素。11.在HQ的链队列中，判断只有一个结点的条件是（HQ.front-next=HQ.rear）。12.设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b、d、c、f、e、a则栈S的容量至少应该是（3）。13.有程序如下，则此程序的输出结果（队列的元素类型是QSelemType为char）是（char）。voidmain(){数据结构课后练习题第3章栈和队列4/5北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1charx=’e’,y=’c’;enqueue(q,’h’);enqueue(q,’r’);enqueue(q,y);dequeue(q,x);enqueue(q,x);degueue(q,x);enqueue(q,’a’);while(!queueempty(q)){dequeue(q,y);printf(y);}printf(x);}14.有如下递归函数：intdunno(intm){intvalue;if(m==0)value=3;elsevalue=dunno(m-1)+5;return(value);}执行语句printf(“%d\n”,dunno(3));的结果是（18）。四、简答题1.对于堆栈，给出三个输入项A，B，C，如果输入项序列为ABC，试给出全部可能的输出序列，并写出每种序列对应的操作。例如：A进B进C进C出B出A出，产生的序列为CBA。答案：利用栈的“后进先出”的特点，共有如下5种情况：A进A出B进B出C进C出产生输出序列ABCA进A出B进C进C出B出产生输出序列ACBA进B进B出A出C进C出产生输出序列BACA进B进B出C进C出A出产生输出序列BCAA进B进C进C出B出A出产生输出序列CBA2.简述以下算法的功能（栈的元素类型是SelemType为int）。（1）statusalgo1(stacks){intI,n,a[255];n=0;while(!stackempty(s)){n++;pop(s,a[n]);}for(I=1;I=n;I++)push(s,a[I]);}利用数组a将栈s中的元素逆置。(2)statusalgo2(stacks,inte){stackt;intd;initstack(t);while(!stackempty(s)){pop(s,d);if(d!=e)push(t,d);}while(!stackempty(t)){pop(t,d);push(s,d);}}（2）利用栈t将栈s中的数据元素e删除。薃肀莂蒃袂肀肂虿袈聿芄薂螄肈莇螇蚀肇葿薀罿肆腿莃袅肅芁薈螁膄莃莁蚇膄肃薇薃膃芅荿羁膂莈蚅袇膁蒀蒈螃膀膀蚃虿腿节蒆羈芈莄蚁袄芈蒆蒄螀芇膆蚀蚆袃莈蒃蚂袂蒁螈羀袁膀薁袆袁芃螆螂袀莅蕿蚈衿蒇莂羇羈膇薇袃羇艿莀蝿羆蒂薆螅羅膁蒈蚁羅芄蚄罿羄莆蒇袅羃蒈蚂螁羂膈蒅蚇肁芀蚁薃肀莂蒃袂肀肂虿袈聿芄薂螄肈莇螇蚀肇葿薀罿肆腿莃袅肅芁薈螁膄莃莁蚇膄肃薇薃膃芅荿羁膂莈蚅袇膁蒀蒈螃膀膀蚃虿腿节蒆羈芈莄蚁袄芈蒆蒄螀芇膆蚀蚆袃莈蒃蚂袂蒁螈羀袁膀薁袆袁芃螆螂袀莅蕿蚈衿蒇莂羇羈膇薇袃羇艿莀蝿羆蒂薆螅羅膁蒈蚁羅芄蚄罿羄莆蒇袅羃蒈蚂螁羂膈蒅蚇肁芀蚁薃肀莂蒃袂肀肂虿袈聿芄薂螄肈莇螇蚀肇葿薀罿肆腿莃袅肅芁薈螁膄莃莁蚇膄肃薇薃膃芅荿螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇羅羇膁螃羄膀莇虿羃节芀薅羂羂蒅蒁羁肄芈螀羀膆蒃蚆肀芈芆薂聿羈蒂蒈肈肀芅袆肇芃薀螂肆莅莃蚈肅肅薈薄蚂膇莁蒀蚁艿薇蝿螀罿荿蚅蝿肁薅薁螈膄莈薇螈莆膀袆螇肆蒆螁螆膈艿蚇螅芀蒄薃螄羀芇葿袃肂蒃螈袂膄芅蚄袂芇蒁蚀袁肆芄薆袀腿蕿蒂衿芁莂螁袈羁薇蚇袇肃莀薃羆膅薆葿羆芈荿螇