中国铁道出版社数据结构(第二版)单元3练习参考答案

1、单元练习3判断题（下列各题，正确的请在前面的括号内打心错误的打X）（V）（1）栈是运算受限制的线性表。（V）（2）在栈空的情况下，不能作出栈操作，否则产生下溢出。（X）（3）栈一定是顺序存储的线性结构。（V）（4）栈的特点是“后进先出”。（X）（5）空栈就是所有元素都为0的栈。（X）（6）在C或C+语言中设顺序栈的长度为MAXLEN,则top=MAXLEN时表示队满。（V）（7）链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。（X）（8）一个栈的输入序列为：A,B,C,D,可以得到输出序列：C,A,B,D。（X）（9）递归定义就是循坏定义。（V）（10）将十进制数转换为二进制数是栈的典型

2、应用之一。填空题（1）在栈结构中，允许插入、删除的一端称为栈顶（2）在顺序栈中，当栈顶指针top=-l时，表示栈空。（3）在有n个元素的栈中，进栈操作的时间复杂度为0（1）。（4）在栈中，出栈操作的时间复杂度为：0（1）o（5）已知表达式，求它的后缀表达式是栈的典型应用。（6）在一个链栈中，若栈顶指针等于NULL,则表示栈空（7）向一个栈顶指针为top的链栈插入一个新结点*p时，应执行p-next=top：和top=p：操作。（8）顺序栈S存储在数组S-dataO.MAXLEN-l中，进栈操作时要执行的语句有：Stop+。（或二Stop+1）（9）链栈LS,指向栈顶元素的指针是LSTnext。

3、（10）从一个栈删除元素时，首先取出栈顶元素，然后再移动栈顶指针。（11）由于链栈的操作只在链表的头部进行，所以没有必要设置头结点。（12）已知顺序栈S,在对S进行进栈操作之前首先要判断栈是否满。（13）已知顺序栈S,在对S进行出栈操作之前首先要判断栈是否空。（14）若内存空间充足，链栈可以不定义栈满运算。（15）链栈LS是空的条件是LS-next二NULL（16）链栈LS的栈顶元素是链表的首元素。（17）同一栈的各元素的类型相同（18）若进栈的次序是A、B、C、D、E,执行三次出栈操作以后，栈顶元素为B。（19）A+B/C-D*E的后缀表达式是：ABC/+DE*-。（20）四个元素按A、B、

4、C、D顺序进S栈，执行两次Pop（S,x）运算后，x的值是C。选择题（1）插入和删除只能在一端进行的线性表，称为（C）。队列B.循环队列C.栈D.循坏栈（2）设有编号为1,2,3,4的四辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为（D）1234124313241423（3）如果以链表作为栈的存储结构，则出栈操作时（B）A.必须判别栈是否满C.必须判别栈元素类型（4）元素A,B,C,D依次进栈以后,AABB（5）顺序栈存储空间的实现使用A.链表B.数组必须判别栈是否空D.队栈可不做任何判别栈顶元素是（D）CCDD（B）存储栈元素。循环链表D.变量（6）在C或C+语言中，一个顺序栈一旦

5、被声明，其占用空间的大小（A）。A.已固定B.不固定C.可以改变D.动态变化（7）带头结点的链栈LS的示意图如下，栈顶元素是（A）DAAABBCCDD（8）链栈与顺序栈相比，有一个比较明显的优点是（B）。A.插入操作更加方便B.通常不会出现栈满的情况。C.不会出现栈空的情况D.删除操作根加方便（9）从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列（D）命令。Ax=top;top二topnext;Btop=topnext;x=topdata;Cx二top一data;Dx二top一data;top=topnext;（10）在一个栈顶指针为HS的链栈中，将一个S指针所指

6、的结点入栈，应执行下列（B）命令。AHSnext二S;BS-next=HS-next;HSnext=S;C.S-next=HS-next;HS=S;D.Snext=HS;HS=HS-next;（11）四个元素按A、B、C、D顺序进S栈，执行两次Pop（S,x）运算后，栈顶元素的值是（B）oAABBCCDD（12）元素A,B,C,D依次进栈以后，栈底元素是（A)oAABBCcDD（13）经过下列栈的运算后，再执行ReadTop（s）的值是（A）。InitStack(s)(初始化栈)；Push(s,a):Push(s,b);Pop(s)TOC o 1-5 h zAaBbC1D0经过下列栈的运算后，

7、x的值是(B)。InitStack(s)(初始化栈);Push(s,a):Push(s,b);ReadTop(s):Pop(s,x);AaBbC1D0经过下列栈的运算后，x的值是(B)。InitStack(s)(初始化栈);Push(s,a);Pop(s,x);Push(s,b);Pop(s,x);AaBbC1D0经过下列栈的运算后，SEmpty(s)的值是(C)。InitStack(s)(初始化栈)；Push(s,a);Push(s,b);Pop(s,x);Pop(s,x);A.aBbC1D0（17）向顺序栈中压入元素时，（B）。A.先存入元素，后移动栈顶指针B.先移动栈顶指针，后存入元素C

8、.谁先谁后无关紧要D.同时进行（18）初始化一个空间大小为5的顺序栈S后，S-top的值是（B）。A.0B.-1C.不再改变D.动态变化（19）一个栈的入栈次序ABCDE,则栈的不可能的输出序列是（C）oA.EDCBAB.DECBAC.DCEABD.ABCDE（20）设有一个顺序栈S,元素A,B,C,D,E,F,依次进栈，如果六个元素出栈的顺序是B,D,C,F,E,A,则栈的容量至少应是（A）。A3B4C5D6设有一个栈，元素进栈的次序为：A,示出栈操作，写出下列出栈的操作序列。（1）C,B,A,D,E（2）A,C,B,E,D解：（1）III000I0I0（2）I0II00II00B,C,D,

9、E,用I表示进栈操作，0表求后缀表达式(1)ABC/D(2)-A+B+C+D/E(3)A*(B+C)*D-E(4)(A+B)*C-E/(F+G/H)-D(5)8/(5+2)-6解：AB0A(3)ABC+*D*E-(4)AB+C*EFGH/卜/-D(5)852+/6_六.算法设计题设用一维数组stackEn表示一个堆栈，若堆栈中每个元素需占用M个数组单元(M1),试写出其入栈操作的算法。试写出其出栈操作的算法。设计一个算法，要求判别一个算术表达式中的圆括号配对是否正确。解：用一整型变量top表示栈顶指针，top为0时表示栈为空。栈中元素从Sl开始存放元素。入栈算法：voidpush(charx)

10、if(top+M)MAXLEN-l)pnntf(“堆栈溢出！”)；elseif(top=0)top卄；Stop=x;elsetop=top+M;Stop=x;出栈算法：voidpop(charx)if(top=0)piintf(堆栈为空栈！”)；elseif(top=1)x=Stop;top-elsex=Stop;top=top_M;2.解：设表达式在字符数组a中，使用一堆栈S来帮助判断。intcorrect(chara)stacks;IiutStack(s);for(i=0;istiien(a);i+)if(ai=)OPush(s,();elseif(ai=丁)ifStackEmpty(s)

11、return0;else/调用初始化栈函数/调用判栈空函数/若栈为空返回5否则出栈Pop；if(StackEmpty(s)pnmf(“配对正确！”);elsepnntf(“配对错误！”);/调用判栈空函数若栈空，说明配对正确，并返回1/配对借误返回0模拟考题求后缀表达式求卞列表达式：a/bac+d*e-a*c的后缀表达式。解：AECA/DE*+AC*-求下列表达式：A/B-C+D*E-F的后缀表达式。解：AE/C-DEUF-写出运行下列程序段的输出结果voidmainOStackS;charx,y;InitStack(S);/初始化栈x=-cH;y=”k”；Push(S,x);Push(S,Ha”);Push(S,y);Pop(S,x);Push(S,壮”);Push(S,x);Pop(S,x);Push(S,fsn);While(JSEmpty(S)Pop(S,y);couty;coutx;答:stack11程序填空1.下列程序是判别一个算术表达式（存在字符数组a中）的圆扌舌号配对是否正确？试填空完成下列程序。intcorrect（chara）stacks;InitStack(s);for(i=0;inext二stop;s.top二p;s.topdata二x;w