单元练习3_答案.doc

《单元练习3_答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

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

4、出栈操作以后，栈顶元素为B。（19）A+B/C-D*E的后缀表达式是：ABC/+DE*-。（20）四个元素按A、B、C、D顺序进S栈，执行两次Pop（S，x）运算后，x的值是C。三．选择题（1）插入和删除只能在一端进行的线性表，称为(C)。A．队列B．循环队列C．栈D．循环栈（2）设有编号为1，2，3，4的四辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为(D)A．1234B．1243C．1324D．1423（3）如果以链表作为栈的存储结构，则出栈操作时（B）A．必须判别栈是否满B．必须判别栈是否空C．必须判别栈元素类型D．队栈可不做任何判别（4）元素A,B,

5、C,D依次进栈以后，栈顶元素是（D）A．AB．BC．CD．D（5）顺序栈存储空间的实现使用（B）存储栈元素。A．链表B．数组C．循环链表D．变量（6）在C或C++语言中，一个顺序栈一旦被声明，其占用空间的大小（A）。A．已固定B．不固定C．可以改变D．动态变化（7）带头结点的链栈LS的示意图如下，栈顶元素是（A）LSHABCDΛA．AB．BC．CD．D（8）链栈与顺序栈相比，有一个比较明显的优点是（B）。A．插入操作更加方便B．通常不会出现栈满的情况。C．不会出现栈空的情况D．删除操作根加方便（9）从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执

6、行下列(D)命令。A．x=top;top=top->next;B．top=top->next;x=top->data;C．x=top->data;D．x=top->data;top=top->next;（10）在一个栈顶指针为HS的链栈中，将一个S指针所指的结点入栈，应执行下列(B)命令。A．HS->next=S;B．S->next=HS->next;HS->next=S;C．S->next=HS->next;HS=S;D．S->next=HS;HS=HS->next;（11）四个元素按A、B、C、D顺序进S栈，执行两次Pop（S，x）运算后，栈顶元素的值是（B）。

7、A．AB．BC．CD．D（12）元素A,B,C,D依次进栈以后，栈底元素是（A）。A．AB．BC．CD．D（13）经过下列栈的运算后，再执行ReadTop(s)的值是（A）。InitStack(s)（初始化栈）;Push(s,a);Push(s,b);Pop(s)A．aB．bC．1D．0（14）经过下列栈的运算后，x的值是（B）。InitStack(s)（初始化栈）;Push(s,a);Push(s,b);ReadTop(s);Pop(s,x);A．aB．bC．1D．0（15）经过下列栈的运算后，x的值是（B）。InitStack(s)（