全国计算机等级考试二级公共基础知识1

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,全国计算机等级考试二级公共基础知识1,1,4,算法与算法分析,算法与算法分析,一 算法的概念,算法是对特定问题求解步骤的一种描述,算法的基本特征：,1,）,可行性,：组成算法的操作必须能够在计算机上实现。,2,）,确定性,：算法的每一步操作必须清晰无二义性。,3,）,有穷性,：算法必须在有限步内结束；,4,）,有足够的情报,：,0,个或多个输入；,1,个或多个输出；,算法描述的方法很多，如自然语言、框图、类,C,等,例,:,求两个正整数,m,，,n,中的最大数,MAX,的算法,（,1,）,若,m n,则,max=m,（,2,）,若,m = n,则,max=n,程序,=,算法,+,数据结构,1,、,正确性,：,(1),没有语法错误； ,(2),对于几组输入数据能够得出满足要求的结果；,(3),对于精心选择的典型而苛刻的几组输入数据能够得到满足要求的结果。,(4),对于一切合法的输入数据都能产生满足要求的结果。,2,、,可读性：,便于阅读、理解、调试、修改；,3,、,健壮性：,对不合法的输入能作出正确的反映与处理；,4,、,高效性：,执行时间短（,时间复杂度,）、,需求存储空间省（,空间复杂度,）,评价算法标准,1,时间复杂度,T,（,n,）,以求解问题的基本操作的,执行次数,作为算法时间的度量。,算法与算法分析,O,（,n,3,）,称为矩阵相乘算法时间复杂度；,O,（,n,3,）表示矩阵相乘算法执行时间与,n,3,成正比,即,O,（,n,3,）与,n,3,同一数量级；,例：,n,阶矩阵相乘的算法,For ( i = 1; i=n; i+ ) For (j = 1; j=n; j+ ), c i j = 0 ; For (k = 1; k= n; k+ ) c i j += a i k * b k j ,乘法 加法,执行次数均为,n,3,矩阵相乘的基本运算：乘法 加法；,数据结构中常用的时间复杂度频率计数有,7,个：,O(1),常数型,O(n),线性型,O(n,2,),平方型,O(n,3,),立方型,O(2,n,),指数型,O(log,2,n),对数型,O(nlog,2,n),二维型,2,算法空间复杂度 用执行算法所需的,内存空间的大小,作为算法所需空间的度量。 设执行算法所需的内存空间是问题规模,n,的某个函数,g(n),则算法空间复杂度记作：,S,（,n,）,= O(g(n),表示算法内存空间的增长率,与,g(n),的增长率相同,例计算,解法,1,先计算,x,的幂,存于,power ,中,再分别乘以相应的系数,# define N 100,float evaluate (float coef , float x , int n ), float powerN, f; int i;,for (power 0=1, i = 1; i=n; i+ ) poweri=x*poweri-1; for (f = 0, i=0; ideta=a;,q-next=p- next;,p- next =q;,head,z,y,x,p,y,x,z,p,head,a,q,插入操作功能：在线性链表的第,i,个元素结点之前插入一个新元素结点,e,；,插入操作图示：,插入前,插入后,a,i-,1,a,i,a,2,a,1,a,i+,1,n,a,n,head,a,i-,1,a,i,a,2,a,1,a,i+,1,n,a,n,e,head,4,）,删除结点,q=p-next;,p- next =q- next;,free(q);,head,z,y,x,q,y,x,z,q,head,p,p,删除前,删除后,a,i-,1,a,i,a,2,a,1,a,i+,1,n,a,n,head,a,i-,1,ai,a,2,a,1,a,i+,1,n,a,n,head,p,p,q,q,线性链表小结,线性链表是线性表的一种链式存储结构,线性链表的特点,1,通过保存直接后继元素的存储位置来表示,数据元素之间的逻辑关系；,2,插入、删除操作通过修改结点的指针实现；,3,不能随机存取元素,；,1,循环链表的概念,循环链表的特点是将线性链表的最后一个结点的指针指向链表的第一个结点（首尾相连的单链表）,2,循环链表图示,循环链表,(a),非空表 （,b,）空表,head,head,a,1,a,n,循环链表,说明,在解决某些实际问题时循环链表可能要比线性链表方便些。如将一个链表链在另一个链表的后面；,对循环链表，有时不给出头指针，而是给出尾指针,a,a1,an,a-next,给出尾指针的循环链表,双向链表,循环单链表，虽然从任一结点出发沿着指针链能找到其前件，但时间耗费是,O(n),。如果希望从表中快速确定某一个结点的前件，另一个解决方法是在链表的每个结点里再增加一个指向其前件的指针域,prior,。 这样形成的链表中就有两条方向不同的链，称为双向链表。,线性表小结,线性表的顺序存储结构,顺序表，,链式存储结构,-,线性链表,循环链表,双向链表,.,不同的存储结构，线性表的同一操作的算法是不同的,:,在顺序存储结构下，线性表的插入、删除操作，通过移动元素实现,;,在线性链表存储结构下，线性表的插入、删除操作，通过修改指针实现。,2,栈,栈是限定仅能在表尾一端进行插入、删除操作的线性表,（,a,1, a,2, . , a,i -1, a,i, a,i+1, , a,n,）,插入,删除,栈的概念,一 什么是栈,?,将表中允许进行插入、删除操作的一端称为,栈顶,(Top),，,栈顶的当前位置是动态变化的，由一个栈顶指针指示其位置。,表的另一端称为栈底,(Bottom),。,当栈中没有元素时称为空栈。,栈的插入操作称为,进栈或入栈,，删除操作称为,出栈或退栈,。,栈,栈的示意图,出栈,进栈,栈的特点,后进先出,第一个进栈的元素在栈底，最后一个进栈的元素在栈顶，,第一个出栈的元素为栈顶元素，,最后一个出栈的元素为栈底元素,栈顶,栈底,a,n,a,2,a,1,小 结,1,栈是限定仅能在表尾一端进行插入、,删除操作的线性表；,2,栈的元素具有后进先出的特点；,3,栈顶元素的位置由一个称为栈顶指针的,变量指示，,进栈、出栈操作要修改栈顶指针；,2,栈,3,队列,3.1,队列的概念,一 什么是队列,队列是限定仅能在表头进行删除，表尾进行插入的线性表,（,a,1, a,2, . , a,i -1, a,i, a,i+1, , a,n,）,插入,删除,3,队列,a,1,a,2,a,3,a,n,入队列,队头,队尾,出队列,队 列 的 示 意 图,队列的特点,先进先出,第一个入队的元素在队头，最后一个入队的元素在队尾，,第一个出队的元素为队头元素，,最后一个出队的元素为队尾元素,rear,front,J1,rear,front,J2,（,a),空队列,(b)J1,J2,相继入队列,(c)J1,出队,(d)J3,J4, J5,和,J6,相继入队之后,J2,出队,rear,front,0,1,2,3,4,5,rear,front,J5,J4,J3,front,rear,为整数,又有,J7,入队,怎么办？,？,J2,J6,3 .,循环队列,front,rear,J6,J4,J5,3 1,2,4 0,5,rear,5,4 0,3 1,2,front,J6,J7,J8,J9,J4,J5,front,rear,5,4 0,3 1,2,(b),队空,(a),队满,J7,rear,判分队空、队满方法：,1,）另设一个标志,S,以区分队空、队满。,2,）,S=0,队空：,front=rear;,S=1,队满：,front=rear;,或少用一个空间,Real+1=front,为满,front,5,4 0,3 1,2,J6,J7,J8,J4,J5,（,c,）,rear,入队操作,：,将元素,x,插入队尾,front,rear,5,4 0,3 1,2,J1,J3,J2,x,front,rear,5,4 0,3 1,2,J1,J3,J2,元素,x,入队前,元素,x,入队后,出队操作,：删除队头,元素；,front,rear,5,4 0,3 1,2,J1,J3,J2,出队操作前,front,rear,5,4 0,3 1,2,J1,J3,J2,出队操作后,小 结,1,队列是限定仅能在表尾一端进行插入，表头一端删除 操作的线性表；,2,队列中的元素具有先进先出的特点；,3,队头、队尾元素的位置分别由称为队头指针和队尾指针的变量指示，,4,入队操作要修改队尾指针，出队操作要修改队头指针；,数据存储结构方面的考题,1,：数据的存储结构是指 （,）。,A),存储在外存中的数据,B),数据所占的存储空间量,C),数据在计算机中的顺序存储方式,D),数据的逻辑结构在计算机中的表示,2.,下列叙述中正确的是 （,）。,A,）栈是“先进先出”的线性表,B,）队列是“先进后出”的线性表,C,）循环队列是非线性结构,D,）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构,3.,数据结构分为线性结构和非线性结构，带链的队列属于（ ）。,4.,下列数据结构中，属于非线性结构的是（ ）。,A,）循环队列,B),带链队列,C),二叉树,D,）带链栈,答案：,D,。,答案：,D,。,答案：线性结构。,答案：,c,5.,下列叙述中正确的是（ ）。,A,）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的,B,）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构,C,）顺序存储结构能存储有序表，链式存储结构不能存储有序表,D,）链式存储结构比顺序存储结构节省存储空间,答案：,A,。,6.,下列关于栈的叙述正确的是,（,）,A,）栈按“先进先出”组织数据,B),栈按“先进后出”组织数据,C,）只能在栈底插入数据,D,）不能删除数据,答案：,B,。,7.,一个队列的初始状态为空。现将元素,A,，,B,，,C,，,D,，,E,，,F,，,5,，,4,，,3,，,2,，,1,依次入队，然后再依次退队，则元素退队的顺序为,【1】,。（,）,答案：,A，B，C，D，E，F，5，4，3，2，1,9.,设某循环队列的容量为,50,，如果头指针,front=45(,指向队头元素的前一位置,),，尾指针,rear=10(,指向队尾元素,),，则该循环队列中共有,【2】,个元素。,（,）,8.,假设用一个长度为,50,的数组（数组元索的下标从,0,到,49,）作为栈的存储空间，栈底指针,bottom,指间栈底元素，栈顶指针,top,指向栈顶元素，如果,bottom=49,，,top=30,（数组下标），则栈中具有,【 】,个元素。,（,2009,年,3,月）,答案：,19,答案：,15,4,树和二叉树,1,树的定义,树是,n,个结点的有限集合,T,，当,n=0,时，称为空树；当,n0,时，,T,满足如下条件：在任一棵非空树中：（,1,）有且仅有一个称为根的结点。（,2,）其余结点可分为,M,个互不相交的子集合，而且这些子集中的每一个本身又是一棵树，也称为根的子树。,J,I,A,C,B,D,H,G,F,E,K,L,M,2,树的实例树可表示具有分枝结构关系的对象,例,1,家族族谱,设某家庭有,13,个成员,A,、,B,、,C,、,D,、,E,、,F,、,G,、,H,、,I,、,J,、,K,、,L,、,M,，他们之间的关系可用树表示：,J,I,A,C,B,D,H,G,F,E,K,L,M,计算机中树是常用的数据组织形式,尽管有些应用中数据元素之间并不存在分支结构关系，但为了便于管理和使用数据，将它们用树的形式来组织。,例,2,计算机的文件系统 不论是,DOS,文件系统还是,window,文件系统，所有的文件都是用树的形式来组织的。,文件夹,1,文件夹,n,文件,1,文件,2,文件夹,11,文件夹,12,文件,11,文件,12,C,盘,3,、树的 基本术语,树的结点：包含一个数据元素及若干指,向子树的分支；,孩子结点：结点的子树的根称为该结点,的孩子，,B,、,C,是,A,的孩子；,双亲结点：,B,结点是,A,结点的孩子，则,A,结点是,B,结点的双亲；,兄弟结点：同一双亲的孩子结点，,H,、,I,、,J,互为兄弟；,堂兄结点,：,同一层上结点，,E,、,F,、,G,、,H,、,I,、,J,、,互为堂兄弟；,J,I,A,C,B,D,H,G,F,E,K,L,M,3,、树的 基本术语,结点的层次：根结点的层次定义为,1,；根的孩子为第二层，依此类推；,树的深度：,树中所有结点的层次的最大值,结点的度：,结点子树的个数,树的度：,树中结点度的最大值。,叶子结点,：度为,0,的结点；,分枝结点：,度不为,0,的结点；,J,I,A,C,B,D,H,G,F,E,K,L,M,一 二叉树的概念,1,二叉树的定义,二叉树： 或为空树，或由根及两颗互不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。,A,F,G,E,D,C,B,一 二叉树的概念,二叉树,说明,1,）二叉树中每个结点最多有两个子树；,既：二叉树每个结点度小于等于,2;,2,）左、右子树不能颠倒,有序树,;,3,）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念,;,(a),、,(b),是不同的二叉树，,(a),的左子树有四个结点,，,(b),的左子树有两个结点,(a),(b),G,E,D,C,B,A,F,G,E,D,C,B,F,A,2, 二叉树的基本形态,(a),空树,(b),只有根,(c),右子树空,(e),左子树空,(d),左、右子树非空,二、 二叉树的性质,性质,1:,在二叉树的第,i,层上至多有,2,i-1,个结点,(i1),。 ,性质,2:,深度为,k,的二叉树至多有,2,k,-1,个结点（,k1,）。,性质,3:,对任意一棵二叉树,T,，若叶结点数为,n,0,，而其度为,2,的结点数为,n,2,，则,n,0,=n,2,+1,。,两种特殊的二叉树,满二叉树：深度为,k,的二叉树，如有,2,k,-1,个结点则称为满二叉树；,A,G,F,E,D,C,B,A,C,B,K=3,的满二叉树,K=2,的满二叉树,满二叉树的顺序表示：,从二叉树的根开始， 从上到下， 从左到右，逐层进行编号（,1,，,2,，,，,n,）。例如图（,a,）所示的满二叉树的顺序表示为,:,(1,，,2,，,3,，,4,，,5,，,6,，,7,，,8,，,9,，,10,，,11,，,12,，,13,，,14,，,15),。,完全二叉树：,深度为,k,，结点数为,n,的二叉树，如果其结点,1n,的位置序号分别与满二叉树的结点,1n,的位置序号一一对应，则为完全二叉树， 如上图,(b),所示。,满二叉树必为完全二叉树， 而完全二叉树不一定是满二叉树。,性质,4,：具有,n,个结点的完全二叉树的深度为,log,2,n,+1,。,性质,5:,对于有,n,个结点的完全二叉树， 按照从上到下、从左到右的顺序对二叉树中的所有结点从,1,开始顺序编号， 则对于任意的序号为,i,的结点有：,（,1,） 如,i=1,，则序号为,i,的结点是根结点， 无双亲结点； 如,i1,， 则序号为,i,的结点的双亲结点序号为,i/2,（下取整）,（,2,） 如,2in,，则序号为,i,的结点无左孩子；如,2in,，则序号为,i,的结点的左孩子结点的序号为,2i,。 ,（,3,） 如,2i,1n,，则序号为,i,的结点无右孩子；如,2i,1n,， 则序号为,i,的结点的右孩子结点的序号为,2i,1,。,二叉树,存储结构,-,二叉链表,二叉链表中每个结点包含三个域：数据域、左指针域、右指针域,A,F,E,D,C,B,二叉链表图示,D,A,B ,C,E ,F ,若一个二叉树含有,n,个结点，则它的二叉链表中必含有,2n,个指针域， 其中必有,n+1,个空的指针域。,二、二叉树的遍历（必考）,遍历,：,按某种顺序访问二叉树的每个结点，而且每个结点仅被访问一次。,访问：,含义很广，可以是对结点的各种处理,，如修改结点数据、输出结点数据。,如何访问二叉树的每个结点，,而且每个结点仅被访问一次？,？,二叉树的遍历方法（必考）,二叉树由根、左子树、右子树三部分组成,二叉树的遍历,可以分解为：访问根，遍历,左子树,和,遍历,右子树,令,：,L,：,遍历左子树,T,：,访问根结点,R,：,遍历右子树,约定先左后右,有三种遍历方法：,T,L R,前序遍历、,L,T,R,中序遍历,、,L R,T,后序遍历。,A,F,G,E,D,C,B,先序遍历,（,T,L,R,）,若二叉树非空 （,1,）访问根结点；,（,2,）先序遍历左子树； （,3,）先序遍历右子树,；,先序遍历序列,：,A,B,D,E,G,C,F,例：先,序遍历右图所示的二叉树,（,1,）访问根结点,A,（,2,）先序遍历左子树：即按,T,L,R,的顺序遍历,左子树,（,3,）先序遍历右子树：即按,T,L,R,的顺序遍历,右子树,A,F,G,E,D,C,B,中序遍历（,L,T,R,）,若二叉树非空（,1,）中序遍历左子树（,2,）访问根结点,（,3,）中序遍历右子树,中序遍历序列,：,D,B,G,E,A,C,F,例：,中序遍历右图所示的二叉树,（,1,）中序遍历左子树：即按,L,T,R,的顺序遍历,左子树,（,2,）访问根结点,A,（,3,）中序遍历右子树：即按,L,T,R,的顺序遍历,右子树,A,F,G,E,D,C,B,后序遍历（,L,R,T,）,若二叉树非空（,1,）后序遍历左子树（,2,）后序遍历右子树,（,3,）访问根结点,后序遍历序列：,D,G,E,B,F,C,A,例：后,序遍历右图所示的二叉树,（,1,）后序遍历左子树：即按,L,R,T,的顺序遍历,左子树,（,2,）后序遍历右子树：即按,L,R,T,的顺序遍历,右子树,（,3,）访问根结点,A,A,F,G,E,D,C,B,后序遍历序列,：,a,b,c,d,-,*,+,e,f,/,-,中序遍历序列,：,a,+,b,*,c,-,d,-,e,/,f,例：,中序遍历、,后,序,遍历下图所示的二叉树,e,d,c,b,f,a,+,*,/,-,-,例,:,已知一棵二叉树前序遍历和中序遍历分别为,ABDEGCFH,和,DBGEACHF,，则该二叉树的后序遍历为,?,A) GEDHFBCAB) DGEBHFCAC) ABCDEFGHD) ACBFEDHG,B,二叉树,1,二叉树： 或为空树，或由根及两颗互不相交的左子树、右子树构成，并且左、右子树本身也是二叉树；,2,二叉树可以用链式结构存储；,遍历：按某种搜索路径访问二叉树的每个结点，每个结点仅被访问一次。,二叉树的遍历可以分解为：访问根，遍历,左子树和,遍历,右子树，常用的三种遍历算法：,先序遍历、中序遍历、后序遍历；,5,查找,5.1,查找的基本概念,查找（列）表：由同一类型的数据元素（或记录）构成的集合， 可利用任意数据结构实现。 ,关键字：,数据元素的某个（几个）数据项的值。如果一个数据项可以,唯一标识列表中的一个数据元素,， 则称其为关键字。,查找： 根据给定的关键字值，在特定的查找（列）表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。,若找到相应的数据元素， 称查找成功，否则称查找失败,5,2,线性表的查找,5.2.1,顺序查找,-,最简单的查找方法,顺序查找的基本思想,从表的一端开始，顺序扫描线性表，,依次将扫描到的结点关键字和待找的值相比较，若相等，则查找成功，若整个表扫描完毕，仍末找到关键字等于的元素，则查找失败。,顺序查找既适用于顺序表，也适用于链表。若用顺序表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描。另外，顺序查找的表中元素可以是无序的。,顺序查找算法的性能。,假设列表长度为,n,，那么查找第,i,个数据元素时需进行,n-i+1,次比较，即,C,i,=n-i+1,。又假设查找每个数据元素的概率相等，即,P,i,=1/n,， 则顺序查找算法的平均查找长度为：,顺序查找的特点,顺序查找的,优点是算法简单,，对查找表结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序或无序排，它都同样适用。,顺序查找的缺点是,查找效率低,，当,n,较大时，不宜采用顺序查找,。,二分,查找（折半查找）,1.,二分查找的基本思想,高效率的查找方法。要求表中元素按关键字有序,(,升序或降序,),。假设表中元素为升序排列。,二分查找的基本思想是：,首先将表,中间位置记录的关键字与查找关键字,比较，如果两者相等，则查找成功；,否则利用中间位置记录,将表分成前、后两个子表， 如果中间位置记录的关键字大于查找关键字，,则进一步查找前一子表，否则进一步查找后一子表。,重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。,例如，假设给定有序表中关键字为：,05,13,19,21,37,56,64,74,80,88,92,，查找,K=21,的情况：,0 1 2 3 4 5 6 7 8 9 10,0 1 2 3 4 5 6 7 8 9 10,0 1 2 3 4 5 6 7 8 9 10,0 1 2 3 4 5 6 7 8 9 10,3.,二分查找的性能分析,二分查找的过程可以用二叉树来描述。把当前查找区间的中点作为根结点，左子区间和右子区间分别作为根的左子树和右子树，左子区间和右子区间再按类似的方法，由此得到的二叉树称为二分查找的判定树。,例如，给定的关键字序列,05,13,19,21,37,56,64,74,80,88,92,，的判定树。,0 1 2 3 4 5 6 7 8 9 10,在长度为,n,的有序线性表中进行二分查找。最坏的情况下，需要的比较次数为,log,2,n,6,排序,6,1,基本概念,6.1.1,排序定义,排序就是把一组记录（元素）按照某个域的值的递增或递减的次序重新排列的过程。,(,按学号的递增,),表,7-1,学生档案表,学号,姓名,年龄,性别,99001,王晓佳,18,男,99002,林一鹏,19,男,99003,谢宁,17,女,99004,张丽娟,18,女,99005,周涛,20,男,99006,李小燕,16,女,为讨论方便，我们直接将排序码写成一个一维数组的形式，,并且在没有声明的情形下，所有排序都按排序码的值递增排列。,排序,插入排序（直插排序、希尔排序）,交换排序（冒泡排序、快速排序）,选择排序 （直选排序、堆排序）,归并排序（二路归并排序）,6,2,插入排序,直接插入排序,1,直接插入排序（,Straight Insertion Sorting,）,基本思想：把,n,个待排序的元素看成一个有序表和一个无序表，,开始时有序表中只包含一个元素，无序表中包含有,n-1,个元素，,排序过程中每次从无序表中取出第一个元素，把它的排序码,依次与有序表元素的排序码进行比较，将它插入到有序表中,的适当位置，使之成为新的有序表。,例如，,n=6,，数组,R,的六个排序码分别为：,17,，,3,，,25,，,14,，,20,，,9,。它的直接插入排序的执行过程如图,7-1,所示。,3,直接插入排序的效率分析,直接插入排序算法十分简单。,空间,:,只需要一个元素的辅助空间，用于元素的位置交换,。,时间,:,外层循环要进行,n-1,次插入，每次插入最少比较一次（正序），移动两次；最多比较,i,次，移动,i,2,次（逆序）（,i=1,，,2,，,，,n-1,）。,直接插入排序的时间复杂度为,O,（,n,2,）。,最坏情况比较,n(n-1)/2,希尔排序,希尔排序,(,缩小增量排序,):1959,年由提出来的。,基本思想：先将整个待排元素序列分割成若干个子序列（由 “增量”确定）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。,例如，,n=8,，数组,array ,的八个元素分别为：,91,，,67,，,35,，,62,，,29,，,72,，,46,，,57,。下面用图,7-2,给出希尔排序算法的执行过程。,希尔排序的效率分析,与增量有关，,最坏情况，希尔排序的时间复杂性在,O,（,nlog,2,n,）。,6,3,交换排序,6.3.1,冒泡排序,基本思想,:,对待排序序列从后向前（从下标较大的元素开始），依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部，就象水底下的气泡一样逐渐向上冒。,例如，,n=6,，数组,R,的六个排序码分别为：,17,，,3,，,25,，,14,，,20,，,9,。下面用图,7-3,给出冒泡排序算法的执行过程。,冒泡排序的效率分析,若待排序的元素为正序，则只需进行一趟排序，比较次数为（,n-1,）次，移动元素次数为,0,；,若待排序的元素为逆序，则需进行,n-1,趟排序，比较次数为,(n,2,-n)/2,，移动次数为,3(n,2,-n )/2,，,最坏情况比较,n(n-1)/2,因此冒泡排序算法的时间复杂度为,O,（,n,2,）。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。,6.3.2,快速排序,基本思想是：取待排序序列中的某个元素（一般第一个元素）作为基准，通过一趟排序，将待排元素分为左右两个子序列，,左子序列元素的排序码均小于或等于基准元素的排序码，,右子序列的排序码则大于基准元素的排序码，,然后分别对两个子序列继续进行,快速,排序，直至整个序列有序。,元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面，排序码较小的记录一次就能够交换到前面，记录每次移动的距离较远，因而总的比较和移动次数较少。,例如，给定排序码为：（,46,，,55,，,13,，,42,，,94,，,05,，,17,，,70,），具体划分如图,7-4,所示。,3,快速排序的效率分析,若快速排序出现最好的情形（左、右子区间的长度大致相等），则结点数,n,与二叉树深度,h,应满足,log,2,nhlog,2,n+1,，所以总的比较次数不会超过,(n+1) log,2,n,。因此，,快速排序的最好时间复杂度应为,O,（,nlog,2,n,）。,已经证明，快速排序的平均时间复杂度也为,O,（,nlog,2,n,）,。,若快速排序出现最坏的情形（每次能划分成两个子区间，但其中一个是空），则这时得到的二叉树是一棵单分枝树，总的比较次数为,n(n-1)/2,。因此，,快速排序的最坏时间复杂度为,O(n,2,),。,快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为,O,（,log,2,n,），最坏的空间复杂度为,O(n),。,快速排序是一种不稳定的排序方法。,6,4,选择排序,6 . 4.1,直接选择排序,基本思想,直接选择排序是一种简单的排序方法。基本思想是：第一次从,array0arrayn-1,中选取最小值，与,array0,交换，第二次从,array1arrayn-1,中选取最小值，与,array1,交换，第三次从,array2arrayn-1,中选取最小值，与,array2,交换，,，第,i,次从,arrayi-1arrayn-1,中选取最小值，与,arrayi-1,交换，,第,n-1,次从,arrayn-2arrayn-1,中选取最小值，与,arrayn-2,交换，总共通过,n-1,次，得到一个按排序码从小到大排列的有序序列,。,例如，给定,n=8,，数组,R,中的,8,个元素的排序码为：（,8,，,3,，,2,，,1,，,7,，,4,，,6,，,5,），则直接选择排序过程如图,7-5,所示。,直接选择排序的效率分析,在直接选择排序中，共需要进行,n-1,次选择和交换，每次选择需要进行,n-i,次比较（,1in-1,），而每次交换最,多需,3,次移动，因此，总的比较次数,C= =(n,2,-n)/2,，,总的移动次数,M= =3(n-1),。,直接选择排序的时间复杂度为,O(n,2,),数量级，所以当记录占用的字节数较多时，通常比直接插入排序的执行速度要快一些,。,最坏情况比较,n(n-1)/2,7,5,归并排序,1,、,基本思想：将两个有序子区间（有序表）合并成一个有序子区间，一次合并完成后，有序子区间的数目减少一半，而区间的长度增加一倍，当区间长度从,1,增加到,n,（元素个数）时，整个区间变为一个，即为有序序列,.,例如，给定排序码,46,，,55,，,13,，,42,，,94,，,05,，,17,，,70,，二路归并排序过程如图,7-10,所示。算法,P284,归并排序的效率分析,归并排序的时间复杂度为,O(nlog,2,n),。,归并排序时，需要利用与待排序数组相同的辅助数组作临时单元，故该排序方法的空间复杂度为,O(n),，比前面介绍的其它排序方法占用的空间大。,对于长度为,n,的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是,A),冒泡排序为,n/2,B),冒泡排序为,n,C),快速排序为,n,D),快速排序为,n(n-1)/2,D,第二部分 程序设计,程序设计基础,2.1,程序设计方法与风格,如何形成良好的程序设计风格，主要包含以下几个因素：,（,1,）源程序文档化。,（,2,）数据说明的方法。,（,3,）语句的结构。,（,4,）输入和输出。,（,5,）适当的注释,注,释分序言性注释和功能性注释。,2,程序设计基础,2.2,结构化程序设计,结构化程序设计方法的四条原则是,（必考）：,1.,自顶向下；,2.,逐步求精；,3.,模块化；,4.,限制使用,goto,语句。,结构化程序的基本结构和特点：,（,1,）顺序结构：一种简单的程序设计，最基本、最常用的结构；,（,2,）选择结构：又称分支结构，包括简单选择和多分支选择结构，可根据条件，判断应该选择哪一条分支来执行相应的语句序列；,（,3,）重复结构：又称循环结构，可根据给定条件，判断是否需要重复执行某一相同程序段。,2,程序设计基础,2.3,面向对象程序设计,1,、面向对象方法的,优点,：,（,1,）与人类习惯的思维方法一致。 （,2,）稳定性好。,（,3,）可重用性好。 （,4,）易于开发大型软件产品。,（,5,）可维护性好。,2,、面向对象方法的基本概念,（,1,）对象,-,对象是面向对象方法中最基本的概念，可以用来表示客观世界中的任何实体，对象是实体的抽象。,属性即对象所包含的信息，操作描述了对象执行的功能，操作也称为方法或服务。,2,程序设计基础,（,2,）类和实例,类是指具有共同属性、共同方法的对象的集合。所以类是对象的抽象，对象是对应类的一个实例。,（,3,）消息,消息是一个实例与另一个实例之间传递的信息。消息的组成包括,1,、接收消息的对象的名称；,2,、消息标识符，也称消息名；,3,、零个或多个参数。,（,4,）继承,继承是指能够直接获得已有的性质和特征，而不必重复定义他们。继承分单继承和多重继承。单继承指一个类只允许有一个父类，多重继承指一个类允许有多个父类。,（,5,）多态性,多态性是指同样的操作在接受不同消息时可导致完全不同的行动的现象。,比如汽车一个类，而具体到某辆汽车则是一个对象。图,21,中，机动车类是对机动车特征和功能的总体描述，机动车,A,是具体到某辆车的特征。,3,软件工程基础,3.1,软件工程基本概念,1,、软件定义及特点,2,、软件危机与软件工程,3,、软件工程过程和软件生命周期,软件生命周期三个阶段,:,软件定义、软件开发、运行维护，主要活动阶段是：,（,1,）可行性研究与计划制定；,（,2,）需求分析；,（,3,）软件设计；,（,4,）软件实现；,（,5,）软件测试；,（,6,）运行和维护。,3,软件工程基础,4,、软件工程的目标和与原则,目标：在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。,基本目标：付出较低的开发成本；达到要求的软件功能；取得较好的软件性能；开发软件易于移植；需要较低的费用；能按时完成开发，及时交付使用。,软件工程的理论和技术性研究的内容主要包括：软件开发技术和软件工程管理。,软件开发技术包括：软件开发方法学、开发过程、开发工具和软件工程环境。,软件工程管理包括：软件管理学、软件工程经济学、软件心理学等内容。,软件管理学包括人员组织、进度安排、质量保证、配置管理、项目计划等。,软件工程原则包括抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。,3,软件工程基础,3.2,结构化分析方法,1,、需求分析,指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望。,（,1,）结构化需求分析方法。（,2,）面向对象的分析的方法（,OOA,）。,2,、结构化分析方法,结构化分析方法的实质：着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。,步骤：,调查原系统（获得当前系统如何工作）,原系统逻辑模型,需求分析（得出新系统应如何工作）,新系统逻辑模型,结构化分析的常用工具：（,1,）数据流图、（,2,）数据字典（,D-D,）、（,3,）判定树、（,4,）判定表,3,软件工程基础,3,、软件需求规格说明书,作用：,（,1,）便于用户与开发人员进行交流。,（,2,）是软件开发工作的基础和依据。,（,3,）作为确认测试和验收的依据。,内容：,（,1,）概述（,2,）数据描述,（,3,）功能描述。（,4,）性能描述。,（,5,）参考目录。（,6,）附录。,特点：,（,1,）正确性；（,2,）无岐义性；,（,3,）完整性；（,4,）可验证性