辅导栈和队列数组课件

1、数据结构指导(2011 )，邱保志，1，学习交流PPT，大纲要求，2，堆栈，队列和排列(1)堆栈和队列的基本概念(2)堆栈和队列的顺序记忆结构(3)堆栈和队列的链记忆结构(4)堆栈和队列的应用(5)特殊矩阵第三章堆栈和提示点：堆栈和队列的定义，特性是解决实际问题堆栈的顺序表示，链表示和相应操作的实现队列顺序表示，链表表示和相应操作的实现循环队列满/空间的判断条件评价分，是以不同的存储结构进行的。 是判断队列顶端指针和队列端指针的操作，特别是循环队列满和空间的两种判断方法。 堆栈和队列顺序和链的存储结构，这里常见的本章中可能的一大问题是，利用堆栈和队列的特性，在基于这些的数据结构中支持实际问题解

2、决算法的设计，例如，在堆栈中解决递归问题， 解决特殊矩阵的压缩存储，例如在队列中解决图的扫描问题，该试验点复习的重点可以放在二维矩阵和一维矩阵的相互变换上，下标的计算方法，例如在平行于对角线的某些行上数据非零矩阵存储到一维矩阵中，然后计算对应于各数据点的下标。 3、学习交流PPT，一、出入堆栈顺序，堆栈已满。 已知，一个堆栈的输入堆栈序列为1，2，n，其输出序列为p1，p2，pn，如果p1=n，则pi=。 在具有2n个单元格的序列堆栈中，把地址的上位作为堆栈的底，把top作为堆栈的底部的指针，向堆栈中压入要素的话，该指针top的变化如下。 假设3个堆栈的输入序列为1234n，输出序列为a1a2

3、an，在1=k=n时ak=n，在k=i=n的情况下，ai不确定A n-i 1 B n-(i-k) C中4个堆栈的输入序列为1234，其输出堆栈序列a 1243 b 2134 c 1432 d 4312 也许设输入要素为1、2、3、p、a，输入顺序为123pa，设定了要素通过堆栈后到达输出序列，哪个输出序列为高级语言的变量名。ap321bpa321cpp3a21dp3a21ep321a、4、交流PPT、知识结构图、5、交流PPT、矩阵的知识结构图、6、学习交流PPT，1 .依次堆叠堆栈s、要素s1、s2、s3、s4、s5、S6，6要素的堆如果是s1，则堆栈的容量至少有() A. 2 B. 3 C

4、. 5 D. 6 2如果两个堆栈的输入序列是a、b、c，则通过输入堆栈、输出堆栈操作来输入a、b， c的不同的排列个数是() A. 4 B. 5 C. 6 D. 7 3 .和顺序堆栈可以进行比较的链堆栈中，() a .通常堆栈不满的情况b .通常堆栈不空闲的情况c .插入操作d .删除操作更容易实现4 .堆栈如果是n，输出序列的第一个要素是第n i个输出要素是() a .不确定b.n-ic.n-i1d.n-i-i-1， 7、学习通信PPT，5 .以下说法是正确的() a .因为链堆栈本身没有容量限制，所以在用户的内存空间范围内堆栈不会装满b .因为序列堆栈本身没有容量限制。 对于在用户存储空间

5、的范围内堆栈不会装满的c .链式堆栈，在堆栈装满的状态下再次进行堆栈操作时会发生溢出 d . sq.datasq.rear=x； B. sq.datasq.rear=x； sq.rear=sq.rear 1； C. sq.rear=(sq.rear 1)%maxsize； sq.datasq.rear=x； D. sq.datasq.rear=x； sq.rear=(sq.rear 1)%maxsize； 7 .循环队列的排队操作可以包括： sq.datasq.rear=x； B. sq.datasq.rear=x； sq.rear=sq.rear 1； C. sq.rear=(sq.rear

6、 1)%maxsize； sq.datasq.rear=x； D. sq.datasq.rear=x； sq.rear=(sq.rear 1)%maxsize； 8、学习交流PPT，8 .顺序队列的出场操作，() A. sq.front=(sq.front 1)%maxsize； B. sq，front=sq.front 1； C. sq.rear=(sq.rear 1)%maxsize； D. sq.rear=sq.rear 1； 9 .循环队列出队操作是： () A. sq.front=(sq.front 1)%maxsize； B. sq，front=sq.front 1； C. sq.

7、rear=(sq.rear 1)%maxsize； D. sq.rear=sq.rear 1； 10 .循环队列的队列满条件是() a.(sq.rear1) % maxsize=(sq.front1) % maxsizeb.(sq.rear1) % maxsize=sq.front 1； c.(sq.rear1) % maxsize=sq.frontd.sq.rear=sq.front 11 .循环队列的队列空条件是() a.(sq.rear1) % maxsize=(sq.front1) % maxsizeb.(sq.re c.(sq.rear1) % maxsize=sq.frontd.s

8、q.rear=sq.front，9、通信PPT， 12 .如果链表是堆栈的存储结构，则在操作堆栈时() a .堆栈是b .堆栈元素的类型c .必须判别堆栈是否为空.什么也不判别堆栈13 .堆栈顶部指针在Top的链接堆栈上以s指示的节点B. s-next=top-next； 顶层下一个=s； C. s-next=top； top=s； D. s-next=top； 顶部=顶部-下一个； 14 .从堆栈顶部指针为Top的链堆栈中删除一个节点，并将被删除的节点的值存储在x中。 操作步骤为() A. x=top-data； 顶部=顶部-下一个； b .顶端=顶端-下一个； x=顶部数据； C. x=t

9、op； 顶部=顶部-下一个； d.x=顶部数据； 学习交流PPT，15.1个链中，f、r分别是开头、末尾的指针的话，插入s所指节点的操作是() A. f-next=s； f=s； B. r-next=s； r=s； C. s-next=r； r=s； D. s-next=f； f=s； 16 .如果一个堆栈的输入堆栈序列为abcde，则堆栈的不可输出序列为() A. edcba B. decba C. dceab D. abcde 17 .如果一个队列的队列序列为1234，则队列的可能输出序列为() A. 4321 B.1234 C. 1432 D. 3241 18 .公式中，设计了一种算法来

10、判断左右括号是否成对，()数据结构是最佳的。如果将a .线性表的顺序结构b .堆栈c .队列d .线性表的链存储结构19.1234设为两端队列的输入序列，则无论是输入限制两端队列还是输出限制两端队列都不能得到的输出序列，可以使用() a.1234b.4132c.4231d.4213， 11、交流PPT、第3章堆栈和队列标题1循环队列用排列A0.m-1存储其要素值，在知道其头尾指针分别为front、rear的情况下，当前队列的要素数为。 2以大小为6的阵列实现循环队列，当前rear=0、front=3，如果从队列中删除一个元素并将两个元素入队，则rear=、front=。 12、学习通信PPT，

11、以3向量表示的循环队列的容量为MAXSIZE，队列的开头和末尾的位置分别为1和max_size，队列为空的条件，队列满的条件。 如果四个堆叠的s和队列q的初始状态为空，并且元素a、b、c、d、e和f顺序通过s并且当一个元素被堆叠时进入队列q，并且这六个元素队列的顺序为b、d、c、f、e和a，则s的容量至少为s。 用5 (中国科学技术大学1998 )的循环链表表示的队列的长度为n，如果只设置开头的指针，队和入队的时间复杂度分别为和，而如果只设置末尾的指针，队和入队的时间复杂度分别为和。 第二，为了解决队列应用2.1计算机主机与打印机之间的速度不一致问题，打印机设置打印数据缓冲器，在该缓冲器中顺序

12、地写入主机输出的数据，并且打印机从该缓冲器中取出数据来进行打印。 这个缓冲器是一个。 学习a堆栈b队列c阵列d线性表，13，交流PPT，知道2.2为非空队列，s是空的堆栈，用c语言制作算法，队列和堆栈的基本操作和少量的工作变量就能把队列q的要素反过来。 void Reverse_Queue(SqQueue Q，SqStack s) while (！ 队列执行(q ) )数据=队列推式(s，数据)/while while (！ 学习交流PPT，北京邮电大学1997年int s(int n) if(n=0) s(n)=0； 电子扫描(% d，x) s(n)=s(n-1) x； void main(

13、) printf(%d，s(4) )； 在n=4的情况下，读取x=4，9，6，2，并且在x是局部变量的情况下，该函数递归地结束，并且调用方的值为。 如果x是全局变量，则此函数递归结束，调用的值为： 15、学习通信PPT，并且对于循环队列，通过Q.front=Q.rear无法确定循环队列是否已满，并且尝试了多种处理方法以确定循环队列是否已空。 (设置区分队列的完整和空间的布尔变量，在队列中不使用一个单元，设置一个寄存器)将堆栈s和队列q的初始状态设置为空，元素a、b、c、d、e、f依次进入堆栈s，一个元素堆叠后立即进入队列q (3)因为很难估计堆栈在使用过程中所需的最大空间的大小，所以合理的方法

14、是给堆栈分配尽可能大的容量。 因为堆栈满了的话，堆栈就不能使用了。 (正误)，16，学习通信PPT，两端队列限定在表的两端进行的线性表，如果两端队列从某个端点插入元素只能从该端点删除，则该两端队列成为两个堆栈底部相邻的堆栈。 描述向依次分配的环队列Q0QM0-1插入节点的函数enqueue和从该队列中取出节点的dequeue函数(其中，M0 100是常数)。 用一个循环链表表示队列(称为循环队列)，在该队列中只有一个队列指针rear，并且不设置队列头部指针，在循环链表中插入元素x的节点算法，以及从循环链表中删除节点的算法17、学习通信PPT，使用m个空间阵列s (即s1sm )用于堆栈和队列，

15、虽然不知道堆栈和队列实际占用的空间，但随时要求存储在它们中的数据量不超过m (1) 如何配置堆栈和队列最大限度地利用空间，写入堆栈底bottom、堆栈顶top、队列头front、队列尾rear的初始值。(2)创建插入算法，满足参数i=1时，将x插入堆栈的参数i=2时，将x插入队列。 解： (1)初始条件： bottom=top=0 rear=front=m 1注：满足的条件： top (front-rear)=m、void overflow-false () for (I=front-1、i=rear； i-) sm i-front 1=si； rear=m-(前部) 1； 前端=m 1； v

16、oid insert (阵列类型s； PS； elementtypex if (rear=top1 ) overflow-false ()； if (I=1)顶=顶1； 停止=x； else if (i=2) rear=rear-1； srear=x； 学习交流PPT，方法2:将堆栈和队列分别放在数组的两端，推入堆栈： stop=e top； 进行列： srear=e rear中空间初始值： bottom=top=1 rear=front=m注：满足的条件： toprear或top=rear1void overflow-false () for (I=front； irear； i-) sm-

17、front i=si； rear=rear m-front； 前端=m； void insert (阵列类型s； PS； elementtypex if (top=rear1) overflow-false ()； PS (I=1)停止=x； 顶部=顶部1； else if (i=2)srear=x； rear=rear-1； 19、学习通信PPT，判定一个循环队列q (最大m个要素)已满的条件如下。 如果循环队列以数组A0.m-1存储元素，并且已知它的开头和末尾的指针分别为front和rear，则当前队列中的元素的数目为。 存储器具有连续的存储空间(设定1到m小区)，应如何将该空间分配给两个堆栈S1和