数据结构 第3章答案

1、3.5习题一、名词解释栈栈是限制在表的一端进行插入和删除操作的线性表。允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。栈的顺序结构：利用顺序存储方式实现的栈称为顺序栈。栈的链式结构：用链式存储结构实现的栈称为链栈。队队是一种“先进先出” (FIFO-First In First Out)的数据结构，即插入操 作在表一端进行，而删除操作在表的另一端进行，这种数据结构称为队列。 把允许插入的一端称为队尾(rear)，把允许删除的一端称为队头(front)。队的顺序结构：顺序存储的队称为顺序队。队的链式结构：采用链式存储结构的队称为链队。二、判断题栈和队列都是特殊的线性表。 (V )栈和队列都

2、将插入和删除操作限制在表的端点处进行。(V )只允许在表的一端进行插入和删除操作的线性表称为栈。(V)没有元素的栈称为空栈，空栈用不着栈顶指针。(X ) TOC o 1-5 h z 只要栈不空，就能任意删除栈的元素。(X )栈允许删除的一端称为栈顶，而栈底元素是不能删除的。(X )对采用链式存储结构的栈进行操作不必判断溢出。(V )元素进出队列一定满足“先进先出”的规律。(V )链队列不存在溢出问题。 (V )在链队列中删除一个元素是在链表的最前端进行的。(V )三、单项选择题栈和队列的共同之处在于它们具有相同的(A )。逻辑特性B.物理特性C.运算方法 D.元素类型栈和队列都是特殊的线性表，

3、其特殊性在于(C )。它们具有一般线性表所没有的逻辑特性它们的存储结构比较特殊对它们的使用方法做了限制它们比一般线性表更简单若5个元素的出栈序列为1, 2, 3, 4, 5,则进栈序列可能是()。2, 4, 3, 1, 5 B. 2, 3, 1, 5, 4C.3,1,4,2,5D.3,1,2,5,4某队列初始为空，若它的输入序列为a, b,c,d,它的输出序列应为()。A. a, b, c, dB. d, c, b, aC. a, c, b, dD. d, a, c, b当3个元素的进栈序列给定以后，由这3个元素组成的可能的出栈序列应该有()。A. 5种 B. 6种 C. 4种 D. 3种若栈

4、采用顺序存储结构，正常情况下，往堆栈中插入一个元素，栈顶 指针top的变化是()。A.不变 B. top=0 C. -topD. top+若栈采用顺序存储结构，正常情况下，删除栈中一个元素，栈顶指 针top的变化是()。A.不变 B. top=0 C. top-D. top+若队列采用顺序存储结构，元素的排列顺序(B )。与元素的值的大小有关由元素进入队列的先后顺序决定与队头指针和队尾指针的取值有关n与作为顺序存储结构的数组的大小有关若非空栈采用含头结点的链式存储结构，栈顶指针为top,删除堆栈的 一个元素的过程是依次执行：p=top，( B ), free(p)。A. top=p-nextC

5、.p=toptop-next =p-nextp=p- next若队列采用链式存储结构，队头元素指针与队尾元素指针分别为 front和rear，向队列中插入一个由p所指的新结点的过程是依次执行：(), rear二p。A. rear=pB. front=prear-next=pD. front-next=p若非空队列采用链式存储结构，队头元素指针与队尾元素指针分别为front和rear，删除队列的一个元素的过程是依次执行：p=front,(),free(p)。A.rear=pB.rear=p-nextC.rear=p-nextD.front=p-next在循环队列中，若front与rear分别表示

6、队头元素和队尾元素的位 置，则判断循环队列队空的条件是(C )。A. front=rear+1B. rear=front+1C.front=rear D.rear=front-1四、填空题栈和队列的逻辑结构都是一线性 结构。栈的插入和删除操作都是在 栈顶 进行，而队列的插入操作在 队尾 进行，删除操作在队头进行。对某栈执行删除操作时，只有在栈中只有一个元素的情况下，才 会将栈底元素删除。在具体的程序设计过程中，栈的顺序存储结构一般是利用一个数组 描述的，同时还要定义一个整型变量来给出栈顶元素的位置。若栈采用顺序存储结构，在不产生溢出的情况下 往 栈中插人一 个新元素，首先将栈顶指针后移一个位置

7、 ，然后 将被插入元素放在修改后 的栈顶指针所指出的位置若队列采用顺序存储结构，未溢出时插入一个元素首先一将队尾指针 后移一个位置，然后再 将被插入元素放在修改后的队尾指针所指出的位置当栈的最大长度难以估计时，最好采用链式存储结构。五、综合应用题（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，bC.e，f，d，g，b，c，a D.c，d，b，e，f，a，g答：A、D满足出栈序列。满足A出栈次序的具体操作序列为：a,b,c,d进