数据结构单元练习3.docx
单元练习一.判断题(下列各题，正确的请在前面的括号内打V；错误的打X) (J )()栈是运算受限制的线性表。(V ) (2)在栈空的情况下，不能作出栈操作，否则产生下溢出。(X) (3)栈一定是顺序存储的线性结构。(J )()栈的特点是“后进先出”。(X) (5)空栈就是所有元素都为0的栈。(X) 在C或者C+ +语言中设顺序栈的长度为MAXLEN, 则top=MAXLEN时表示队满。(V ) (7)链栈与顺序栈相比，其特点之一是通常不会浮现栈满 的情况。(X) (J)一个栈的输入序列为：A, B, C, D,可以得到输出序列：C, A, B, Do(X)()递归定义就是循环定义。(7)()将十进制数转换为二进制数是栈的典型应用之一。二.填空题()对、栈结构中，允许插入、删除的一端称为 栈顶 。()在顺序栈中，当栈顶指针top 时，表示 栈空。()在有个元素的栈中，进栈操作的时间复杂度为一()O()在栈中，出栈操作的时间复杂度为：。()已知表达式，求它的后缀表达式是栈的典型应用。()在一个链栈中，若栈顶指针等于，则表示栈空。()向一个栈顶指针为top的链栈插入一个新结点P 时，应执行 p->next=top ；和top=p；操作。()顺序栈存储在数组中，进栈操作时要执行的语句有：top o(或者 top+1)()链栈，指向栈顶元素的指针是。(10)从一个栈删除元素时，首先取出 栈顶元素，然后再挪移栈 顶指针。(11)由于链栈的操作只在链表的头部进行，所以没有必要设置头幺吉点002)°已知顺序栈S,在对S进行进栈操作之前首先要判断 栈是否满 oL13)已知顺序栈S,在对S进行出栈操作之前首先要判断 栈是否试写出把十进数转换为链栈的存储结构和栈顶指针定义如下, 二进制数的程序。储结构定义栈的存定义栈顶的指栈的应用：针解：二一十进制转换占八、指针置栈取余数取新的商申请新结余数入栈转换后的二进制数值为:转换后的二进制数值为：出栈处理出栈一个余数，收回一个结-L- O(14)若内存空间充足，链栈可以不定义栈满运算。()链栈是空的条件是o()链栈 的栈顶元素是链表的首 元素。()同一栈的各元素的类型 相同 。(18)若进栈的次序是A、B、C、D、E,执行三次出栈操作以后，栈顶元素为 B o(19) A+B/C-D*E 的后缀表达式是：ABC/+DE*-。()四个元素按、 顺序进栈，执行两次 (，)运算后，的值是 o三.选择题()插入和删除只能在一端进行的线性表，称为。.队列.循环队列.栈.循环栈()设有编号为，的四辆列车，顺序进入一个栈结构的 站台，下列不可能的出站顺序为则出栈操作时().必须判别栈是否空.队栈可不做任何判别()女口果以链表作为.栈的存储结构,.必须判别栈是否满.必须判别栈元素类型()元素挨次进栈以后，栈顶元素是()顺序栈存储空间的实现使用()存储栈元素。.链表 .数组.循环链表 .变量()在 或者 语言中，一个顺序栈一旦被声明，其占用空间 的大小()O.已固定 .不固定.可以改变 .动态变化()带头结点的链栈 的示意图如下，栈顶元素是()()链栈与顺序栈相比，有一个比较明显的优点是(.插入操作更加方便.通常不会浮现栈满的情况。.不会浮现栈空的情况（）从一个栈顶指针为被删除的结点，应执行下列.删除操作根加方便的链栈中删除一个结点时，用 保存命令。（）在一个栈顶指针为 入栈，应执行下列的链栈中，将一个指针所指的结点 命令。（）四个元素按、 顺序进栈，执行两次（，）运算后，栈顶元素的值是（ ）o（）元素挨.进栈以后，栈焉元素是（）O（）经过下列栈的运算后，再执行 . 的值是（.）。 （初始化栈）（）经过下列栈的运算后， 的值是（.） 0.（初始化栈）（）经过下列栈的运算后，的值是（）0（初始化栈）（）经过下列栈的运算后，.的值是（）。.（初始化栈）（）向顺序栈中压入元素时，（）O. 先存入元素，后挪移栈顶指针.先挪移栈顶指针,后存入元素.谁先谁后无关紧要（）初始化一个空间大小为的顺序栈后，的值是（）o.再也不改变 .动态变化7）一个栈的入栈次序 ，则栈的不可能的输出序列是挨次进栈：如果六 则栈的容量至少应是（）设有一个顺序栈：元素 个元素出栈的顺序是，四.设有一个栈，元素进栈的次序为：，用表示 进栈操作，表示出栈操作，写出下列出栈的操作序列。（）,（）,解：（）（）五.求后缀表达式（）（）（）（）六.算法设计题.设用一维数组表示一个堆栈，若堆栈中每一个元素需占用个数组单元（）,（）试写出其入栈操作的算法。（）试写出其出栈操作的算法。.设计一个算法，要求判别一个算术表达式中的圆括号配对是否正确。1 .解：用一整型变量top表示栈顶指针，top为0时表示栈为空。栈 中元素从S1开始存放元素。(1)入栈算法：void push (char x)(if (top+M)>MAXLEN- 1)printf ("堆栈溢出! ”)；else(if (top= =0)(top+;S top=x;)else(top=top+M;S top=x;)(2)出栈算法:void pop (char x)(if (top= =0)printf ("堆栈为空栈！ ”)；else(if (top= =1)(X= top;top -;)else(X= top;top=top - M;)2 .解：设表达式在字符数组a口中，使用一堆栈S来匡助判断。int correct (char a)stack s;I nitStack (s);for (i=0; i <strlen(a);i+)if (ai='(')Push (s,'(');else if (ai=')')(if StackEmpty (s)return 0;栈elsePop(s);)if (StackEmpty (s)printf (“配对正确！”);并返回1/调用初始化栈函数/调用判栈空函数/若栈为空返回0；否则出/调用判栈空函数/若栈空，说明配对正确,elseprintf ("配对错误！ ”);/配对错误返回0摹拟考题求后缀表达式. 求下列表达式：A的后缀表达式。解： ABC A /DE* + AC*. 求下列表达式：的后缀表达式。解： AB/C DE*+F写出运行下列程序段的输出结果初始化答:程序填空下列程序是判别一个算术表达式（存在字符数组中）的圆括号配对是否正确？试填空完成下列程序。初始化栈若栈为空返回；否则出栈配对正确!配对正确！配对错误!配对错误!
