数据结构-第3章答案(已核)

数据结构-第3章答案(已核)数据结构-第3章答案(已核)全文共4页，当前为第1页。3.5数据结构-第3章答案(已核)全文共4页，当前为第1页。一、名词解释（1）栈栈是限制在表的一端进行插入和删除操作的线性表。允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。栈的顺序结构：利用顺序存储方式实现的栈称为顺序栈。栈的链式结构：用链式存储结构实现的栈称为链栈。（2）队队是一种“先进先出”(FIFO---FirstInFirstOut)的数据结构，即插入操作在表一端进行，而删除操作在表的另一端进行，这种数据结构称为队列。把允许插入的一端称为队尾(rear)，把允许删除的一端称为队头(front)。队的顺序结构：顺序存储的队称为顺序队。队的链式结构：采用链式存储结构的队称为链队。二、判断题（1）栈和队列都是特殊的线性表。(√)（2）栈和队列都将插入和删除操作限制在表的端点处进行。(√)（3）只允许在表的一端进行插入和删除操作的线性表称为栈。(√)（4）没有元素的栈称为空栈，空栈用不着栈顶指针。(×)（5）只要栈不空，就能任意删除栈的元素。(×)（6）栈允许删除的一端称为栈顶，而栈底元素是不能删除的。(×)（7）对采用链式存储结构的栈进行操作不必判断溢出。(√)（8）元素进出队列一定满足“先进先出”的规律。(√)（9）链队列不存在溢出问题。(√)（10）在链队列中删除一个元素是在链表的最前端进行的。(√)三、单项选择题（1）栈和队列的共同之处在于它们具有相同的(A)。A．逻辑特性B．物理特性C．运算方法D．元素类型数据结构-第3章答案(已核)全文共4页，当前为第2页。（2）栈和队列都是特殊的线性表，其特殊性在于(C数据结构-第3章答案(已核)全文共4页，当前为第2页。A．它们具有一般线性表所没有的逻辑特性B．它们的存储结构比较特殊C．对它们的使用方法做了限制D．它们比一般线性表更简单（3）若5个元素的出栈序列为1，2，3，4，5，则进栈序列可能是()。A．2，4，3，1，5B．2，3，1，5，4C．3，1，4，2，5D．3，1，2，5，4（4）某队列初始为空，若它的输入序列为a，b，c，d，它的输出序列应为()。A．a，b，c，dB．d，c，b，aC．a，c，b，dD．d，a，c，b（5）当3个元素的进栈序列给定以后，由这3个元素组成的可能的出栈序列应该有()。A．5种B．6种C．4种D．3种（6）若栈采用顺序存储结构，正常情况下，往堆栈中插入一个元素，栈顶指针top的变化是()。A．不变B．top=0C．--topD．top++（7）若栈采用顺序存储结构，正常情况下，删除栈中一个元素，栈顶指针top的变化是()。A．不变B．top=0C．top--D．top++（8）若队列采用顺序存储结构，元素的排列顺序(B)。A．与元素的值的大小有关B．由元素进入队列的先后顺序决定C．与队头指针和队尾指针的取值有关n与作为顺序存储结构的数组的大小有关（9）若非空栈采用含头结点的链式存储结构，栈顶指针为top，删除堆栈的一个元素的过程是依次执行：p=top，(B)，free(p)。A．top=p->nextB．top->next=p->nextC．p=topD．p=p->next数据结构-第3章答案(已核)全文共4页，当前为第3页。（10）数据结构-第3章答案(已核)全文共4页，当前为第3页。A．rear=pB．front=pC．rear->next=pD．front->next=p（11）若非空队列采用链式存储结构，队头元素指针与队尾元素指针分别为front和rear，删除队列的一个元素的过程是依次执行：p=front，()，free(p)。A．rear=pB．rear=p->nextC．rear=p->nextD．front=p->next（12）在循环队列中，若front与rear分别表示队头元素和队尾元素的位置，则判断循环队列队空的条件是(C)。A．front=rear+1B．rear=front+1C．front==rearD．rear=front-1四、填空题（1）栈和队列的逻辑结构都是__线性__结构。（2）栈的插入和删除操作都是在_栈顶_进行，而队列的插入操作在_队尾___进行，删除操作在__队头__进行。（3）对某栈执行删除操作时，只有在_栈中只有一个元素的___情况下，才会将栈底元素删除。（4）在具体的程序设计过程中，栈的顺序存储结构一般是利用一个_数组___描述的，同时还要定义一个整型变量来_给出栈顶元素的位置___。（5）若栈采用顺序存储结构，在不产生溢出的情况下往栈中插人一个新元素，首先_将栈顶指针后移一个位置___，然后__将被插入元素放在修改后的栈顶指针所指出的位置_。（6）若队列采用顺序存储结构，未溢出时插入一个元素首先__将队尾指针后移一个位置__，然后再__将被插入元素放在修改后的队尾指针所指出的位置__。（7）当栈的最大长度难以估计时，最好采用_链式___存储结构。数据结构-第3章答案(已核)全文共4页，当前为第4页。五数据结构-第3章答案(已核)全文共4页，当前为第4页。（1）已知栈采用链式存储结构，初始时为空，请画出a，b，c，d四个元素依次进栈以后该栈的状态，然后再画出此时的那个栈顶元素出栈后栈的状态。（2）若按从左到右的顺序依次读人已知序列{a，b，c，d，e，f，g}中的元素，然后结合栈操作，能得到下列序列中的哪些序列(每个元素进栈一次，下列序列表示出栈的次序)?A.{d，e，c，f，b，g，a}B.{f，e，g，d，a，c，b}C.{e，f，d，g，b，c，a}D.{c，d，b，e，f，a，g}

答：A、D满足出栈