第2章程序设计基本知识.ppt

《第2章程序设计基本知识.ppt》由会员分享，可在线阅读，更多相关《第2章程序设计基本知识.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,计算机的应用已不再局限于科学计算，而更多地用于控制、管理和数据处理等非数值计算的处理工作。为了编写一个“好”的程序，必须分析待处理的对象特性以及各处理对象之间存在的关系。,第二章 程序设计基本知识,第,1,节 程序基本常识,第,1,节 程序基本常识,1,算法,算法是对特定问题求解步骤的一种描述，它是指令（规则）的有限序列，其中每一条指令表示一个或多个操作。简单地说，算法就是解决问题的操作步骤。,一个算法必须满足以下五个重要的特征。,有穷性,对于任意一组合法的输入值，算法的操作每个操作步骤都能在有限的时间内完成。

2、这包括合理的执行时间的含义，如果一个算法执行耗费的时间太长，即使最终得出了结果，也是没有意义的。,确定性,算法中的每一步都必须是有明确的定义，不允许有歧义性和多义性。确定性使算法的执行者或者阅读者能够明确其含义及如何执行，并且在任何条件下，算法都只有一条执行路径。,输入,个算法应该有,0,个或多个输入,，以刻画运算对象的初始情况。所谓,0,个输入,是指有的算法表面上可以没有输入，实际上已被嵌入算法之中。,输出,一个算法应该有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；,可行性,一个算法必须遵循特定条件下的解题规则，算法描述的每一个操作都应该是特定的解题规则中允许使

3、用的、可执行的，并可以通过执行有限次来实现。,第,1,节 程序基本常识,2,算法的复杂度,同一个问题可用不同的算法来解决，而算法质量的优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适的算法和改进算法。算法评价主要从时间复杂度和空间复杂度来考虑。,时间复杂度,算法的时间复杂度（,Time Complexity,）是指算法所需要的计算工作量，用算法所执行的基本运算次数来度量。常见的时间复杂度有：常数阶,O(1),，对数阶,O(log,2,n),，线性阶,O(n),，线性对数阶,O(nlog,2,n),，平方阶,O(n,2,),，立方阶,O(n,3,),，,，指数阶,O(2,n,),。随着

4、问题规模,n,的不断增大，上述时间复杂度不断增大，算法的执行效率就越低。,空间复杂度,算法的空间复杂度（,Space Complexity,）是指执行这个算法所需要的内存空间。算法执行期间所需的存储空间主要包括三部分：输入数据所占的存储空间、程序本身所占的空间和算法执行过程中时所需的存储空间。,3,算法的基本结构,算法的结构不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。一般一个算法可以用顺序、选择和循环三种基本结构组合而成。,顺序结构。,顺序结构是最简单、最常用的算法结构，语句与语句之间，框与框之间按从上到下的顺序进行。,选择结构。,选择结构是先根据条件做出判

5、断，再决定执行哪一种操作的算法结构，它必须包含判断框。当条件,P,成立（或称为真）时执行,A,，否则执行,B,，不可能两者同时执行，但,A,或,B,两个框中可以有一个是空的，即不执行任何操作。,循环结构。,一些算法中经常出现从某处开始，按照一定条件，反复执行某一处理步骤的情况，这就是循环结构。反复执行的处理步骤为循环体，它可以细分为两类：当型循环结构和直到型循环结构。,第,1,节 程序基本常识,4,基础算法,高精度计算,利用计算机进行数值计算，有时会遇到这样的问题：有些计算要求精度高，希望计算的数的位数可达几十位甚至几百位，虽然计算机的计算精度不断提高了，但因受到硬件的限制，往往达不到实际问题

6、所要求的精度。我们可以利用程序设计的方法去实现这样的高精度计算。主要涉及高精度的加、减、乘、除运算。实现的时候采用逐位加、减、乘、除即可。,常见问题有“汉诺塔的步数”、“国王的米粒”等。,穷举算法,所谓穷举法，即枚举法，指的是从可能的解的集合中一一枚举各元素，用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立，即为其解。,有些问题可以用循环语句和条件语句直接求解，有些问题用循环求解时循环次数太多，无法编写程序，则需要用到回溯、递归、分治等方法。,常见问题有“百钱买百鸡”、“素数判断”等。,递推算法,递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计

7、算的一个重要算法。这种算法特点是：一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么，从问题出发逐步推到已知条件，此种方法叫逆推。无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。,常见问题有“斐波那契数列”、“过河卒”等。,

8、第,1,节 程序基本常识,数据排序,排序就是将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程。,排序的方法很多，下面根据初赛的要求，简单介绍各种常见排序算法在一些方面的的比较，尤其是时间复杂度和稳定性两个方面。稳定性，指在原序列中相同元素的相对位置与排好序的新序列中相同元素的相对位置是否相同。若相同，则该算法是稳定的，否则不稳定。,时间复杂性比较,插入排序、冒泡排序、选择排序的时间复杂性为,O(n2),；,其它非线形排序的时间复杂性为,O(nlogn),；,线形排序的时间复杂性为,O(n),。,稳定性比较,插入排序、冒泡排序、二叉树排序、归并排序及其他线形排序是稳定的；,选择排序、希

9、尔排序、快速排序、堆排序是不稳定的；,辅助空间的比较,线形排序、归并排序的辅助空间为,O(n),其它排序的辅助空间为,O(1),。,其它比较,（,1,）插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。反而在这种情况下，快速排序慢了,时间复杂度会达到其上限。当数据为随机数据时，快速排序远远快于插入、冒泡、选择排序，时间复杂度接近其下限。,（,2,）当,n,较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。,（,3,）若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。,（,4,）当,n,较大时，关键字元素比较随机，对

10、稳定性没要求宜用快速排序。,（,5,）当,n,较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下，宜用归并排序。,常见问题有“合并果子”、“逆序对问题”等。,第,1,节 程序基本常识,递归算法,递归程序设计是,C+,语言程序设计中的一种重要的方法，它使许多复杂的问题变得简单，容易解决了。递归特点是：函数或过程调用它自己本身。其中直接调用自己称为直接递归，而将,A,调用,B,，,B,以调用,A,的递归叫做间接递归。,常见问题有“汉诺塔问题”、“,Ackermann,函数”等。,搜索与回溯算法,搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可

11、以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。,如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进,如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。,常见问题有“八皇

12、后问题”、“骑士游历问题”等。,贪心算法,贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。,贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。,常见问题有“删数问题”、“排队打水问题”等。,第,1,节 程序基本常识,分治算法,分治就是指的分而治之，即将较大规模的问题分解成几个较小规模的问题，通过对较

13、小规模问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称之为二分法。,常见问题有“归并排序”、“比赛日程安排”等。,广度优先搜索,广度优先算法的核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点,，如此依次扩展，检查下去，直到发现目标节点为止。这种搜索的次序体现沿层次向横向扩展的趋势，所以称之为广度优先搜索。,常见问题有“分油问题”、“八数码问题”等。,动态规划,动态规划程序设计是解决

14、多阶段决策过程最优化问题的一种途径、一种方法，而不是一种特殊算法。由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。需要满足“最优子结构”和“无后效性”的两项基本条件。实现时主要分成几个步骤：划分阶段、确定状态和状态变量、确定决策并写出状态转移方程、寻找边界条件、程序设计实现。大致可以分为以下几类：线性、区间、背包型、树型等。,常见问题有“最长不下降序列”、“最长公共子序列”等。,第,1,节 程序基本常识,【,课堂练习,】,1,、,【NOIP1998,提高组,】,表达式（,4%,

15、（,-3,）与（,-4%3,）的值为（）。,A,-1,，,-1 B,1,，,-1 C,-1,，,1 D,1,，,1,【,答案,】B,【,分析,】,任何一个整数,n,都可以表示成,n=k*q+r,其中,0=|r|=120,。也就是说至少要,7,次比较。,或者：,5,个数,7,次排好，具体如下：,假设,5,个数分别编号,1,，,2,，,3,，,4,，,5,，,1v2,，,3v42,次，假设,12,，,34,；,1v3,，,1,次，假设,13,则,134,；,把,5,插入,1,，,3,，,4,中，需要,2,次，,结果有,4,种：,5134,，则把,2,插入,3,，,4,中，需,2,次,1534,，则

16、把,2,插入,5,，,3,，,4,中，需,2,次,1354,，同上,1345,，同上,这样一共,2+1+2+2=7,。,第,1,节 程序基本常识,12,、,【,NOIP2000,】,某数列有,1000,个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索,(binary search),，在最坏的情況下，需检视,(),个单元。,A,1,000 B,10 C,100 D,500,【,答案,】B,【,分析,】,由二分法定义得：,291000,非,与,或、异或 （,|,和,是同级的）,如果加入加减乘除，就是以下这样：,注意：同级的运算符不分高低，计算时按照从左到右运算。,第,2,节 逻辑运

17、算,【,课堂练习,】,1,、,【NOIP2002,提高组,】,已知,A=35H,，,A/05H/A/30H,的结果是（）。,A,30H B,05H C,35H D,53H,【,答案,】,C,【,分析,】,将上述十六进制数转化成二进制岁数，逐位进行逻辑运算，注意与运算比或运算的优先级高。,35H=0011 0101 B 05H=0000 0101 B 30H=0011 0000 B,A05H=0011 0101B0000 0101B=0000 0101B,A30H=0011 0101B0011 0000B=0011 0000B,A05HA30H=0000 0101B0011 0000B=0011

18、 0101B=35H,2,、,【NOIP2003】,假设,A=true,，,B=false,，,C=true,，,D=true,，逻辑运算表达式,ABCD,的值是（）。,A,true B,false C,0 D,1 E,NULL,【,答案,】A,【,分析,】,注意“与”运算比“或”运算的优先级高，所以,AB,和,CD,先运算，分别得到,false,和,true,，然后,falsetrue,得到,true,。,3,、,【NOIP2003,提高组,】,设全集,E=1,，,2,，,3,，,4,，,5,，集合,A=1,，,4,，,B=1,，,2,，,5,，,C=2,，,4,，则集合（,A B,）,C,

19、为（）。,A,空集,B,1 C,3,，,5 D,1,，,5 E,1,，,3,，,5,【,答案,】E,【,分析,】,集合运算的一元操作符优先级高于二元，求“补”的优先级比“交”和“并”高，交运算和并运算优先级相同。,AB,是交运算，结果是,1,，,C,的结果是,1,3,5,，最后进行的运算是,1,1,3,5,，最终结果为,1,3,5,。,4,、,【NOIP2004,提高组,】,设全集,I=a,b,c,d,e,f,g,，集合,A=a,b,c,，,B=b,d,e,，,C=e,f,g,，那么集合为（）。,A.a,b,c,d B.a,b,d,e C.b,d,e D.b,c,d,e E.d,f,g,【,答

20、案,】A,【,分析,】,考查集合知识。,第,2,节 逻辑运算,例题,2,计算,23+2|2&5*3-6 5=,（）。,题解：,数字也有逻辑运算，当然也可以混合加减乘除。,这里举例说明运算的操作：,2004,和,2005,都出现了,集合运算,，虽然后来没有再出现，但集合的运算还是需要掌握的。,并运算：；交运算：；差运算：；非运算：（区别于逻辑非运算：）,并运算：,比如,AB,，就是,A,集合和,B,集合里所有元素组成一个新集合，重复的元素只保留一份。,AB a,b,c,b,d,ea,b,c,d,e,。,交运算：,比如,AB,，就是同时在,A,集合和,B,集合的元素组成一个新集合。,AB b,。,

21、差运算：,比如,AB,，就是,A,集合删去,AB,里的元素后组成一个新集合。,AB a,c,。,非运算：,如是单目运算符，比如,A,。非运算有个特殊的要求：一定要说明全集。那么,A,就全集删去,A,集合中的元素，剩下的全集中的元素组成一个新集合。,A=d,e,f,g,。,第,2,节 逻辑运算,5,、,【,NOIP2005,普及组,】,设,A=true,，,B=false,，,C=false,，,D=true,，以下逻辑运算表达式值为真的是（）。,A.(AB)(CD)B.(AB)C)D C.A(BC)D),D.(A(BC)D E.(AB)(CD),【,答案,】D,【,分析,】,考查逻辑运算的知识

22、，相当于与,&,，相当于或,|,。,6,、,【,NOIP2005,提高组,】,设全集,I=a,b,c,d,e,f,g,h,，集合,B,A,=a,b,c,d,e,f,，,C,A,=c,d,e,，,B,A,=a,d,，那么集合,C,B,A,为（）。,A.c,e B.d,e C.e D.c,d,e E.d,f,【,答案,】A,【,分析,】,考查集合知识。,7,、,【,NOIP2006,普及组,】,设,A=B=D=true,，,C=false,，以下逻辑运算表达式值为真的有（）。,A.(AB)(CD)B.(ABD)C),C.A(BCD)D.(ABC)D,【,答案,】B,【,分析,】,相当于与,&,，相

23、当于或,|,，,相当于非。,8,、,【,NOIP2007,普及组,】,设,A=B=true,，,C=D=false,，以下逻辑运算表达式值为假的有（）。,A.(AB)(CDA)B.(AB)C)D),C.A(BCD)D D.(A(DC)B,【,答案,】D,【,分析,】,考查逻辑运算的知识，相当于与,&,，相当于或,|,，,相当于非。,第,2,节 逻辑运算,9,、,【,NOIP2006,普及组,】,在,C+,中，表达式,212,的值是（）。,A.441 B.42 C.23 D.24,【,答案,】C,【,分析,】,异或操作。,21,转换为二进制,10101,2,转换为二进制,00010,，两数异或得

24、到结果,10111,，再将其转换为十进制数，得到结果,23,。,10,、,【,NOIP2006,】,在,C+,中，判断,a,不等于,0,且,b,不等于,0,的正确的条件表达式是（）。,A.!a=0|!b=0 B.!(a=0)&(b=0)C.!(a=0&b=0)D.a&b,【,答案,】,D,【,分析,】0,为假，非,0,为真。,11,、,【,NOIP2007,】,在,C+,程序中，表达式,23|25,的值是（）。,A.23 B.1 C.32 D.18,【,答案,】A,【,分析,】,为位运算异或，不同为,1,，相同为,0,，,23=10111(2),，,2=10(2),，,5=101(2),，位运

25、算优先级,&|,，,25=7,23|7=23,。,12,、,【,NOIP2007,】,在,C+,程序中，判断,a,等于,0,或,b,等于,0,或,c,等于,0,的正确的条件表达式是（）。,A.!(a!=0)|(b!=0)|(c!=0)B.!(a!=0)&(b!=0)&(c!=0),C.!(a=0&b=0)|(c!=0)D.(a=0)&(b=0)&(c=0),【,答案,】,B,【,分析,】DE,语法错误先排除，题目要求相当于,a=0|b=0|c=0,，,abc,只要有一个为真就成立，列个,23,的,01,真假值表，可以穷举验证一下。,第,3,节 栈,栈是只能在某一端插入和删除的特殊线性表。,用桶

26、堆积物品，先堆进来的压在底下，随后一件一件往上堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。,栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（,PUSH,），删除则称为退栈（,POP,）。栈也称为后进先出表（,LIFO,表）。,一个栈可以用定长为的数组来表示，用一个栈指针,TOP,指向栈顶。若,TOP,0,，表示栈空，,TOP=N,时栈满。进栈时,TOP,加。退栈时,TOP,减。当,TOPn;,coutd;,do,a+i=n%d;,n=n/d;,while(n!=0);,for(j=i;j=1;j-)coutaj;,re

27、turn 0;,例题,1,设输入元素为,1,、,2,、,3,、,P,和,A,，输入次序为,123PA,，如图所示。元素经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名？,123PA,输入次序输出次序,【,解答,】,高级语言变量名的定义规则：以字母开头，字母与数字的组合。,出站进站,由于必须以字母开头，所以，第一个可能出现的字母是,P,，那么必然要求,123,已经先后入栈，这样便可得到以,P,开头的、并且,123,按逆序排列的（即,321,）、同时,A,位于,P,后任一位置的变量名序列。此外，还需要考虑以,A,开头的可能情况，这只有一种情形：,AP321,。所

28、以,AP321,，,PA321,，,P3A21,，,P32A1,，,P321A,可以作为高级语言的变量名。,例题,2,火车站列车调度示意图如下，假设调度站两侧的轨道为单向行驶轨道。,如果进站的车厢序列为,123,，则可能的出站车厢序列是什么？,如果进站的车厢序列为,123456,，问能否得到,135426,和,435612,的出站序列。,123PA,输入次序,输出次序,出站,进站,【,课堂练习,】,1,、,【,NOIP2001,】,若已知一个栈的入栈顺序是,1,，,2,，,3,，,，,n,，其输出序列为,P1,，,P2,，,，,Pn,，若,P1,是,n,，则,Pi,是（）,A,i,B,n-1

29、C,n-i+1,D,不确定,【,答案,】C,【,分析,】,归纳总结,P1 n,P2 n-1,P3 n-2,Pn 1,总结：,Pi,对应,n-i+1,2,、,【,NOIP2001,提高组,】,以下哪一个不是栈的基本运算（）。,A,删除栈顶元素,B,删除栈底的元素,C,判断栈是否为空,D,将栈置为空栈,【,答案,】B,【,分析,】,堆栈删除和插入操作只能在栈顶进行。,3,、,【,NOIP2002,提高组,】,设栈,S,和队列,Q,的初始状态为空，元素,e1,，,e 2,，,e 3,，,e 4,，,e 5,，,e 6,依次通过栈,S,，一个元素出栈后即进入队列,Q,，若出队的顺序为,e2,，,e 4

30、,，,e 3,，,e 6,，,e 5,，,e 1,，则栈,S,的容量至少应该为,(),。,A,2 B,3 C,4 D,5,【,答案,】B,【,分析,】,因为依次入栈，所以一个元素入队时，比它标号小的元素要么已入队，要么还在栈中，对每个元素计算比它标号小的元素总数减去队列中比它标号小的元素个数据得尚在栈中的元素个数，找出最大值加,1(,其本身刚出栈,),，就是所要结果。例中,e6,入队时，队中有,e2,，,e4,，,e3,共,3,个元素，比,e6,标号小的有,5,个元素，,5-3+1=3,。,5,、,【,NOIP2006,】,某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该

31、车站状态为空，从 这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的 顺序为,1,，,2,，,3,，,，则车辆出站的顺序为（）。,A.1,2,3,4,5 B.1,2,4,5,7 C.1,4,3,7,6 D.1,4,3,7,2,【,答案,】C,【,分析,】,栈按先进后出顺序，元素上面有元素就不能出栈。,4,、,【,NOIP2003,提高组,】,已知元素（,8,，,25,，,14,，,87,，,51,，,90,，,6,，,19,，,20,），问这些元素以怎样的顺序进入栈，才能使出栈的顺序满足：,8,在,51,前面；,90,在,87,的后面；,20,在,14

32、,的后面；,25,在,6,的前面；,19,在,90,的后面,(),。,A,20,，,6,，,8,，,51,，,90,，,25,，,14,，,19,，,87 B,51,，,6,，,19,，,20,，,14,，,8,，,87,，,90,，,25,C,19,，,20,，,90,，,7,，,6,，,25,，,51,，,14,，,87 D,6,，,25,，,51,，,8,，,20,，,19,，,90,，,87,，,14,E,25,，,6,，,8,，,51,，,87,，,90,，,19,，,14,，,20,【,答案,】D,【,分析,】,根据堆栈先进后出的操作原则，出栈顺序和入栈顺序相反，将题中所给两数间的

33、前后关系颠倒过来：,18,在,51,的前面,8,在,51,的后面,290,在,87,的后面,90,在,87,的前面,320,在,14,的后面,20,在,14,的前面,425,在,6,的前面,25,在,6,的后面,519,在,90,的后面,19,在,90,的前面,其中：,A,不符合,1,；,B,不符合,2,；,C,不符合,1,；,E,不符合,1,。符合条件的只有,D,。,6,、,【,NOIP2006,】,设栈,S,的初始状态为空，元素,a,b,c,d,e,依次入栈，以下出栈序列不可能出现的有（）。,A.a,b,c,e,d B.b,c,a,e,d,C.a,e,c,b,d D.d,c,e,b,a,【

34、,答案,】,C,【,分析,】C,中,a,和,e,出栈后，从栈顶到栈底有,dcb,，,d,没有出栈,c,和,b,出不来。,7,、,【,NOIP2007,】,地面上有标号为,A,、,B,、,C,的,3,根细柱，在,A,柱上放有,10,个直径相同中间有孔的圆盘，从上到下依次编号为,1,，,2,，,3,，,，将,A,柱上的部分盘子经过,B,柱移入,C,柱，也可以在,B,柱上暂存。如果,B,柱上的操作记录为：“进，进，出，进，进，出，出，进，进，出，进，出，出”。那么，在,C,柱上，从下到上的盘子的编号为（）。,A.2 4 3 6 5 7 B.2 4 1 2 5 7 C.2 4 3 1 7 6 D.2

35、4 3 6 7 5,【,答案,】D,【,分析,】,本题就是一个栈，按照“进、出,”,的描述，进栈、出栈的顺序是固定的，不得调整的。这样一来，进、出栈的顺序就是：,1,进、,2,进、,2,出、,3,进、,4,进、,4,出、,3,出、,5,进、,6,进、,6,出、,7,进、,7,出、,5,出。,第,4,节 队列,队列是限定在一端进行插入，另一端进行删除特殊线性表。就像排队买东西，排在前面的人买完东西后离开队伍（删除），而后来的人总是排在队伍未尾（插入）。通常把队列的删除和插入分别称为出队和入队。允许出队的一端称为队头，允许入队的一端称为队尾。所有需要进队的数据项，只能从队尾进入，队列中的数据项只能

36、从队头离去。由于总是先入队的元素先出队,(,先排队的人先买完东西,),，这种表也称为先进先出,(FIFO),表。,队列可以用数组,Qm+1,来存储，数组的上界即是队列所容许的最大容量。在队列的运算中需设两个指针：,head,：队头指针，指向实际队头元素的前一个位置,tail,：队尾指针，指向实际队尾元素所在的位置,一般情况下，两个指针的初值设为，这时队列为空，没有元素。图,1(a),画出了一个由个元素构成的队列，数组定义,Q11,。,Qi i=3,4,5,6,7,8,头指针,head,2,，尾指针,tail,8,。,队列中拥有的元素个数为,:L=tail-head,现要让队头的元素出队，则需将

37、头指针加。即,head=head+1,这时头指针向上移动一个位置，指向,Q3,，表示,Q3,已出队。见图,1(b),。,如果想让一个新元素入队，则需尾指针向上移动一个位置。即,tail=tail+1,这时,Q9,入队，见图,1(c),。,当队尾已经处理在最上面时，即,tail=10,，见图,1(d),，如果还要执行入队操作，则要发生“上溢”，但实际上队列中还有三个空位置，所以这种溢出称为“假溢出”。,【,课堂练习,】,1,、,【,NOIP2000,普及组,】,设循环队列中数组的下标范围是,1n,，其头尾指针分别为,f,和,r,，则其元素个数为,(),。,A,r-f B,r-f+1 C,(r-f

38、)%n+1 D,(r-f+n)%n,【,答案,】,D,【,分析,】,循环队列中,f,和,r,不一定满足,fr,，如果满足,fr,，则元素个数为,r-f,；但有时也会,rf,，所以需要加,n,然后对,n,求余才能统一表示。,2,、,【,NOIP2003,】,已知队列,(13,，,2,，,11,，,34,，,41,，,77,，,5,，,7,，,18,，,26,，,15),，第一个进入队列的元素是,13,，则第五个出队列的元素是（）。,A,5 B,41 C,77 D,13 E,18,【,答案,】B,【,分析,】,根据队列先进先出的操作原则，第一个进入队列的是,13,，则第一个出队的也是,13,，向后

39、依次为,2,，,11,，,34,，,41,，,77,，,5,，,7,，,18,，,26,，,15,。其中第五个是,41,，因此答案为,B,。,3.,若用一个大小为,6,的数组来实现循环队列，且当,rear,和,front,的值分别为,0,和,3,。当从队列中删除一个元素，再加入两个元素后，,rear,和,front,的值分别为（）。,A.1,和,5 B.2,和,4 C.4,和,2 D.5,和,1,【,答案,】B,【,分析,】,删除一个元素，则,front,要前进一格，即,3+1=4,；加入两个元素，则,rear,要前进两格，即,0+2=2,；所以,rear,和,front,的值分别为,2,和,

40、4,。,4.,如图所示的循环队列中元素数目是（）。其中,tail=32,指向队尾元素，,head=15,指向队头元素的前一个空位置，队列空间,m=60.,A.42 B.16 C.17 D.41,【,答案,】C,【,分析,】,元素数目可以根据公式,(tail-head+60)%60,得到，,即,(32-15+60)%60=17,。,克服假溢出的方法有两种。一种是将队列中的所有元素均向低地址区移动，显然这种方法是很浪费时间的；另一种方法是将数组存储区看成是一个首尾相接的环形区域。当存放到,n,地址后，下一个地址就,翻转,为。在结构上采用这种技巧来存储的队列称为循环队列，见图,2,循环队的入队算法如下：,1,、,tail=tail+1,；,2,、若,tail=n+1,，则,tail=1,；,3,、若,head=tail,尾指针与头指针重合了，表示元素已装满队列，则作上溢出错处理；,4,、否则，,Qtail=x,，结束（,x,为新入出元素）。,A,A,A,A,A,A,A,