数据结构和程序设计.ppt

《数据结构和程序设计.ppt》由会员分享，可在线阅读，更多相关《数据结构和程序设计.ppt（170页珍藏版）》请在三一办公上搜索。

1、第一章：数据结构与算法,考核知识点：算法的基本概念数据结构的基本概念线性表的定义栈和队列线性链表树的基本概念查找技术排序技术,第一章：数据结构与算法,第一节：算法1、定义所谓算法是指解题方案的准确而完整的描述。2、算法的基本牲（1）可行性:同一个算法在不同的计算机上应得到相同的结果（2）确定性。是指算法中的每一步都必须是有明确的定义，不允许有模棱两可的解释，也不允许有多义性。（3）有穷性。是指必须能在执行有限步骤之后终止。（4）拥有足够的情报。一个算法执行的结果总是与输入的数据有关，不同的输入有不同的结果。当输入不足或输入错误时，算法可能就无法执行。当算法拥有足够多的情报时（考虑的输入可能性越

2、多），出错的可能越小。,3、算法的基本要素一个算法通常有二种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。（1）对数据对象的运算和操作 基本运算和操作有以下四类：算术运算、逻辑运算、关系运算和数据传输（赋值、输入、输出）。（2）算法的控制结构 算法的控制结构一般可分为顺序、选择、循环三种基本结构。,4、算法设计的基本方法计算机解题的过程实际上是实施某种算法，称计算机算法。（1）列举法 列举法是指根据提出的问题，列举所有可能的情况，然后，进行处理。（2）归纳法通过列举少量的特殊情况，经过分析，找出一般关系（3）递推从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果（4）递

3、归将一个复杂的问题归结为若干个较简单的问题，直到最简单的问题解决（5）减半递推技术（6）回溯法就是对问题分而治之。,5、算法复杂度算法复杂度主要包括时间和空间复杂度。（1）时间复杂度 是指算法基本运算的次数。（不是指运算的时间）（2）空间复杂度 执行这个算法所需要的内存空间。包括程序所占的空间、输入的初始数据所占的空间、运算时所需的空间。,算法的时间复杂度是指 A）执行算法程序所需要的时间 B）算法程序的长度 C）算法执行过程中所需要的基本运算次数 D）算法程序中的指令条数,算法的空间复杂度是指 A）算法程序的长度 B）算法程序中的指令条数 C）算法程序所占的存储空间 D）算法执行过程中所需要

4、的存储空间,第2节：数据结构的基本概念,大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。数据结构主要研究三个方面的问题：（1）数据的逻辑结构：数据集合众各数据元素间所固有的逻辑关系（2）数据的存储结构（物理结构）：各数据元素在计算机中的存储关系（3）对各种数据结构进行的运算。以上问题的主要目的是为了提高数据处理的效率。所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占的计算机存储空间。,1、什么是数据结构实例：无序表的顺序查找与有序表的对分查找,数据元素在表中的表列顺序对查找效率是有

5、很大的影响。,1、什么是数据结构数据结构是指反映数据元素之间关系的数据元素集合的表示。,成绩单,在上表中，查找给定学号的某学生的情况时很方便的。但要查找计算机成绩在75分以上的情况时，则需要从头到尾扫描。为了便于查找成绩，可以进行重新组织数据结构是指相互有关联的数据元素的集合,1、什么是数据结构（1）数据结构的逻辑结构 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。（2）数据的存储结构 数据的逻辑结构在计算机存储空间的存放形式称为数据的存储结构（也称数据的物理结构）,下列叙述中正确的是A）一个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻

6、辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率,数据的存储结构是指 A）存储在外存中的数据B）数据所占的存储空间量C）数据在计算机中的顺序存储方式D）数据的逻辑结构中计算机中的表示,2、数据结构的图形表示,父亲,儿子,女儿,d1,d2,d3,名词解释：（1）结点（2）前件结点（3）后件结点（4）根结点（5）终结点,在数据结构中，与所使用的计算机无关的数据结构是（）A 逻辑 B 存储C 逻辑和存储D 物理,2、数据结构的图形表示,父亲,儿子,女儿,d1,d2,d3,名词解释：（1）结点（2）前件结点（3）后

7、件结点（4）根结点（5）终结点,春,夏,秋,冬,3、线性结构和非线性结构 如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。根据数据元素之间前后件关系的复杂程度，将数据结构分为这两类什么是线性结构？线性必须满足以下二个条件：（1）有且只有一个根结点。（2）每个结点最多有一个前件，也最多一个后件。,d1,d2,d3,春,夏,秋,冬,在数据结构中，从逻辑上可以把数据结构分成（）A 动态结构和静态结构B 紧凑结构和非紧凑结构C 线性结构和非线性结构D 内部结构和外部结构,第3节、线性表和顺序存储结构1、线性表的基本概念线性表由一组数据元素组成。线性表是一种线性结构。非空线性表有如

8、下结构牲：（1）有且只有一个根结点（2）有且只有一个终结节点（3）除以上二结点外，每个结点有且只有一个前件，也有且只有一个后件。,d1,d2,d3,春,夏,秋,冬,2、线性表的顺序存储结构线性表顺序存储具有如下特点（1）线性表中所有元素所占的存储空间是连续的。（2）数据元素在存储空间中是按逻辑顺序依次存放的。,张三7070,李四6590,王五6880,线性表的顺序存储结构是一种随机存取的存储结构。可随机访问任意一个结点,3、线性表的插入运算,14,3、线性表的插入运算,14,3、线性表的插入运算,14,3、线性表的插入运算,14,3、线性表的插入运算,结论：如果在线性表的末尾进行，即在第n个元

9、素之后插入新元素，则只要增加一个元素即可，不需要移动元素如果要在线性表的第1个元素之前插入，则需要移动表中所有的元素。在一般情况下，如果在第i个元素之前进行，则第i个元素之后的所有元素都必须移动。在平均情况下，需要移动表中一半的元素。因此算法的平均时间复杂度为O(n).,4、线性表的删除运算,4、线性表的删除运算,4、线性表的删除运算,4、线性表的删除运算,4、线性表的删除运算,注意：如果为线性表开辟的存储空间已经满了，不能再插入元素，否则会造成“上溢”错误,如果删除第n个元素，则不需要移动表中的元素；如果删除第1个元素，则需要移动表中所有的元素。在一般情况下，若要删除第i个元素，则原来第i个

10、元素之后的所有元素都必须依次往前移动一个位置。平均要移动表中一半的元素。算法的平均时间复杂度为O(n).,总结：在线性表顺序存储的情况下，要插入或删除一个元素，其效率都是很低的，特别是在线性表比较大的情况下更为突出，由于数据元素的移动而消耗较多的处理时间。线性表的顺序存储结构对于小线性表或者元素不常变动的线性表来说是合适的，因为顺序存储结构比较简单。,对线性表，在下列情况下应当采用链表表示的是（）A）经常需要随机地存取元素B）经常需要进行插入和删除操作C）表中元素需要占据一片连续的存储空间D）表中元素的个数不变,第4节：栈和队列1、栈及其运算 栈是限定在一端进行插入与删除的线性表。入栈原则：先

11、进后出，后进选出。,栈顶,栈底,64,1、栈及其运算 栈是限定在一端进行插入与删除的线性表,栈顶,栈底,6,1、栈及其运算 栈是限定在一端进行插入与删除的线性表,栈顶,栈底,1、栈及其运算 栈是限定在一端进行插入与删除的线性表,栈顶,栈底,1、栈及其运算 栈是限定在一端进行插入与删除的线性表,栈顶,栈底,1、栈及其运算 栈是限定在一端进行插入与删除的线性表,栈顶,栈底,1、栈及其运算 栈是限定在一端进行插入与删除的线性表,栈顶,栈底,下列关于栈的描述正确的是A）在栈中只能插入元素而不能删除元素B）在栈中只能删除元素而不能插入元素C）栈是特殊的线性表，只能在一端插入或删除元素D）栈是特殊的线性表

12、，只能在一端插入元素，而在另一端删除元素,下列关于栈的描述中错误的是A）栈是先进后出的线性表B）栈只能顺序存储C）栈具有记忆作用D）对栈的插入与删除操作中，不需要改变栈底指针,实例1：栈底至栈顶依次存放元素A、B、C、D，E在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是_。A.ABCEDB.DBCEAC.CDABED.DCBEA,实例：若进栈序列为1，2，3，4，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）A）1，4，3，2 B）2，3，4，1 C）3，1，4，2 D）3，4，2，1若进栈序列是1，2，3，4，假定进栈和出栈可以穿插进行，则可能的出栈序列是（）A）2，4，1，

13、3 B）3，1，4，2 C）3，4，1，2 D）1，2，3，4以下不是栈的基本运算的是（）A）删除栈顶元素 B）删除栈底元素C）判断栈是否为空 D）将栈置为空栈若已知一个栈的进栈序列是1，2，3n，其输出序列是p1,p2,p3pn,若p1=3,则p2为（）A）可能是2 B）一定是2C）可能是1 D）不确定,2、队列及其运算 什么是队列？是指允许在一端进行插入、而在另一端进行删除的线性表。即“先进选出，后进后出”的原则,front,rear,2、队列及其运算 什么是队列？是指允许在一端进行插入、而在另一端进行删除的线性表。即“先进选出，后进后出”的原则,front,rear,2、队列及其运算 什

14、么是队列？是指允许在一端进行插入、而在另一端进行删除的线性表。即“先进选出，后进后出”的原则,front,rear,2、队列及其运算 什么是队列？是指允许在一端进行插入、而在另一端进行删除的线性表。即“先进选出，后进后出”的原则,front,rear,2、队列及其运算 什么是队列？是指允许在一端进行插入、而在另一端进行删除的线性表。即“先进选出，后进后出”的原则,front,rear,2、队列及其运算 什么是队列？是指允许在一端进行插入、而在另一端进行删除的线性表。即“先进选出，后进后出”的原则,front,rear,栈和队列的共同点是（）A）都是先进先出 B）都是后进先出 C）只允许在端点处

15、插入和删除元素 D）没有共同点,一个队列的入队序列是1，2，3，4，则队列的输出序列是A）4，3，2，1 B）1，2，3，4C）1，4，3，2 D）3，2，4，1,2、队列及其运算 什么是队列？是指允许在一端进行插入、而在另一端进行删除的线性表。即“先进选出，后进后出”的原则,front,rear,下列叙述中正确的是 A）线性表是线性结构 B）栈与队列是非线性结构 C）线性链表是非线性结构 D）二叉树是线性结构,下列关于队列的叙述中正确的是 A）在队列中只能插入数据 B）在队列中只能删除数据 C）队列是先进先出的线性表 D）队列是先进后出的线性表,按照“后进先出”原则组织数据的数据结构是 A）

16、队列 B）栈 C）双向链表 D）二叉树,第5节：线性链表线性表的顺序结构的主要缺点（1）插入或删除时要移动大量的数据元素。（2）分配空间后，如果存储空间已满，会出现“上溢”错误。（3）多个线性表同时工作时，需要大量的连续空间。假设每个数据结点对应一个存储单元，这种存储单元称为存储结点，简称结点。在链式存储方式中，要求每个结点由两部组成：一部分用于存放数据元素值，称为数据区；另一部分用于存放指针，称为指针域。,数据域,指针域,第5节：线性链表在链式存储结构中，存储数据结构的存储空间可以不连续。链式存储方式既可以用于线性结构，也可以用于非线性结构。在用于非线性结构时，其指针的个数要多一些。,HEA

17、D,单向链表示意图,双向链表示意图,下列对于线性链表的描述中正确的是 AA）存储空间不一定是连续，且各元素的存储顺序是任意的B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面C）存储空间必须连续，且前件元素一定存储在后件元素的前面D）存储空间必须连续，且各元素的存储顺序是任意的 链表不具备的特点是A）可随机访问任意一个结点 B）插入和删除不需要移动任何元素C）不必事先估计存储空间 D）所需要空间与其长度成正比下列叙述中正确的是A 线性链表是线性表的链式存储结构B 栈和队列是非线性结构C 双向链表是非线性结构D 只有根结点的二叉树是线性结构,第6节：树和二叉树1、树 树是一种非线性结构

18、。,南昌工程学院,信息系,水利系,机电系,软件,应用,网络,应电,供电,通信,第6节：树和二叉树 1、关于树的基本术语：（1）根结点（没有前件的结点）（2）父结点（即前件）（3）子结点（即后件）（4）叶子结点（没有后件的结点）（5）一个结点有后件的个数叫该结点的度（6）树的最大层称为树的深度,R,K,P,Q,B,E,N,O,W,Z,下列关于树的概念错误的是（）A）一棵树中只有一个无前驱的结点B）一棵树的度为树中各个结点的度数之和C）一棵树中，每个结点的度数之和等于结点总数减1D）一棵树中每个结点的度数之和与边的条数相等,第6节：树和二叉树2、二叉树 二叉树具有以下两个特点（1）非空二叉树只有一

19、个根结点。（2）每个结点最多有二个子树，且分别称左子树和右子树。二叉树的基本性质（1）第K层上最多有2 k-1个结点（2）深度为m的最多有2m-1个结点（3）在任意一个二叉树中，度为0的结点（即叶子结点）总比度为2的点多一个。（4）具有n个结点的二叉树，其深度至少为log2n+1,R,K,Q,B,N,O,W,一棵二叉树第六层（根结点为第一层）的结点数最多为【】个 某二叉树中，度为2的结点有18个，则该二*树中有（）个叶子结点。设树T的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1。则T中的叶子结点为 A）8 B）7 C）6 D）5设一棵完全二叉树共有700个结点，则在该二叉树中有

20、_个叶子结点,第6节：树和二叉树3、满二叉树和完全二叉树满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。完全二叉树：是除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。,R,K,B,R,K,Q,B,N,R,K,Q,B,N,O,W,R,K,Q,B,W,在深度为5的满二叉树中，叶子结点的个数为 A）32 B）31 C）16 D）15,第6节：树和二叉树4、二叉树的遍历 遍历是指不重复地访问二叉树中所有结点。遍历分三种：前序、中序和后序遍历。（1）前序遍历首先访问根结点，再前序左子树，最后前序右子树。如：FCADBEGHP,F,C,A,P,H,E,D,G,B,第

21、6节：树和二叉树4、二叉树的遍历 遍历是指不重复地访问二叉树中所有结点。遍历分三种：前序、中序和后序遍历。（2）中序遍历首先中序遍历左子树，再访问根结点，最后中序右子树。如：ACBDFEHGP,F,C,A,P,H,E,D,G,B,第6节：树和二叉树4、二叉树的遍历 遍历是指不重复地访问二叉树中所有结点。遍历分三种：前序、中序和后序遍历。（3）后中序遍历首先后序遍历左子树，再后序右子树，最后访问根结点如：ABDCHPGEF,F,C,A,P,H,E,D,G,B,实例：已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是_。A.cedbaB.acbedC.decabD.d

22、eabc,c,e,a,d,b,实例：已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是_。A.cedbaB.acbedC.decabD.deabc由后序由以知道根节点是C；而C又在中序的最后，说明没有右子树。,c,e,a,d,b,实例：已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是_。A.cedbaB.acbedC.decabD.deabc,c,e,a,d,b,设一棵二叉树的中序遍历结果为DBEAFC,前序遍历结果为ABDECF,则后序遍历结果为_。,如图所示的二叉树，其中序遍历的结果为（）A)abcdef B)abdefcC)d

23、befac D)defbca,a,b,c,e,f,d,下面关于线性表的叙述错误的是（）A）若用数组表示，表中诸元素的存储位置是连在一起的B）若用链表表示，便于插入和删除操作C）若用链表表示，不需要占用一片相邻的存储空间D）表的插入和删除操作仅允许在表的一端进行,第7节：查找技术1、顺序查找 以下2种情况只能采用顺序查找（1）无序表（2）即使有序线性表，如果采用链式存储结构。2、二分法查找 只适用于顺序存储的有序表。对长度为n的有序线性表，在最坏情况下，二分查找只需比较log2n次，而顺序查找要比较n次。,在长度为n的有序线性表中进行二分查找，需要的比较次数为_。对长度为n的线性表进行顺序查找，

24、在最坏情况下所需要的比较次数为 A）n+1 B）n C）(n+1)/2 D）n/2,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排

25、序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之

26、间的互相交换进行排序的一种方法。（1）冒泡排序法。,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行

27、排序的一种方法。（1）冒泡排序法。,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。

28、（1）冒泡排序法。,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法

29、。,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。,设线性表的长度为n,则最坏情况下，冒泡排序要经过n/2遍从前向后的扫描和n/2遍从后向前的扫描。需要比较的次数是n(n-1)/2次。,在最坏的情况下，冒泡排序的时间复杂度为O(n2),对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为。,第8节：排序技术排序分：交换类排序法、插入类排序法和选择

30、类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序,在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=5,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序,在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=5,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序,在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=5,第8节：排序技术排序分：交

31、换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序,在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=5,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序,在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=5,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序,在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=

32、5,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序,在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=5,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序,在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=5,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序,在第一个、中间、最后一个中，取出一

33、个中间的值，放在T变量中，T=5,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序,在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=5,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序,在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=5,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序,在第

34、一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=5,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序,在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=5,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序,在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=5,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法,第8节：排序技术排序分：交换类排

35、序法、插入类排序法和选择类排序法。2、插入类排序法（1）简单插入排序,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法（1）简单插入排序,1,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法（1）简单插入排序,1,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法（1）简单插入排序,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法（1）简单插入排序,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法（1）简单插入排序,7,第8节：

36、排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法（1）简单插入排序,7,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法（1）简单插入排序,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法（1）简单插入排序,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法（1）简单插入排序,3,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法（1）简单插入排序,3,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法（1

37、）简单插入排序,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法（1）简单插入排序,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法（1）简单插入排序,1,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法（1）简单插入排序,1,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法（1）简单插入排序,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法（1）简单插入排序,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。

38、2、插入类排序法（1）简单插入排序,6,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法（1）简单插入排序,6,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法（1）简单插入排序,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法（1）简单插入排序,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法（1）简单插入排序,5,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法（1）简单插入排序,5,第8节：排序技术排序分：交换类排序法、

39、插入类排序法和选择类排序法。2、插入类排序法（1）简单插入排序,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法（2）希尔排序法 希尔排序法属于插入类排序，它的思想是将整个无序的序列分割成若干小的子序列分别进行插入排序。,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法

40、和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序

41、法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择

42、类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指

43、向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,

44、第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第8节：排序

45、技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法,指向最小的数,第二章：程序设计基础,考核知识点：程序设计方法与风格结构化程序设计（原则、基本结构与特点）面向对象的程序设计方法、对象、属性及继承与多态性。（优点，基本概念）,第二章：程序设计基础,2.1 程序设计方法与风格 要形成良好的程序设计风格，应考虑如下因素：1、源程序文档化（1）符号名的命名应具有一定的实际含义。（2）程序要有注释。注释一般分为序言性注释和功能性注释。序言性注释通常位于每个程序的开头部分，它给出程序的整体说明，主要描述：程序标题、程序的功能性说明、主要算法、接口说明、程序位置、开发简历、程序设计者、

46、复审者、复审日期、修改日期等 功能性注释的位置一般嵌在源程序体中，主要描述其后的语句或程序做什么（3）视觉组织要好，可以利用空格、空行和缩进等技术。,2、数据说明的方法 在编写程序时，要注意数据说明的风格，以便使程序中的数据说明更易于理解和维护。数据说明应注意以下几点：（1）数据说明的次序规范化。（2）说明语句中变量安排要有顺序。（3）使用注解来说明复杂的数据结构。3、语句的结构（清晰第一，效率第二）程序应该简单易懂，语句构造应简单直接，不应该为提高效率而把语句复杂化。,4、输入输出 输入输出方式和格式应尽可能方便用户的使用。,对建立良好的程序设计风格，下面描述正确的是（）A）程序应力求简单、

47、清晰、可读性好B）符号的命名只要合语法C）充分考虑程序的执行效率D）程序的注释可有可无,2.2 结构化程序设计2.2.1 结构化程序设计原则 结构化程序设计的原则概括为：自顶向下、逐步求精、模块化和限制使用goto语句。1、自顶向下 程序设计时，应先考虑总体，后考虑细节。2、逐步求精 对复杂问题，应设计一些子目标作过滤，逐步细化。3、模块化 把程序总目标分解成分目标，再进一步分解成具体的小目标，每个小目标称为一个模块。,2.2.2 结构化程序的基本结构和特点 采用结构化程序设计方法编写程序，可使程序结构良好、易读、易理解、易维护。结构化程序有三种基本结构，即顺序、选择和重复结构。1、顺序结构,

48、A,B,结构化程序设计的3种基本结构是（）A）顺序、选择、重复B）递归、嵌套、调用C）过程、子过程、主程序D）顺序、转移、调用,2、选择结构,A,B,真,假,3、重复结构 重复结构又叫循环结构。循环结构又分：当型循环结构和直到型循环结构。,A,真,假,当型循环结构,A,真,假,直到型循环结构,2.3 面向对象的程序设计2.3.1 关于面向对象方法 面向对象方法的本质，就是主张从客观世界固有的事物出发来构造系统，提倡用人类在现实生活中常用的思维方法来认识、理解和描述客观事物。面向对象方法的主要优点如下：1、与人类习惯的思维方法一致。2、稳定性好 因为面向对象的软件系统的结构是根据问题领域的模型建

49、立起来的，而不是基于对系统应完成的功能来分解的，所以，当对系统的功能需要变化时并不会引起软件结构的整体变化，往往仅需要作一些局部性的修改。,由于现实世界中的实体是相对稳定的，因此，以对象为中心构造的软件系统也是比较稳定的。3、可重用性好 软件重用是指在不同的软件开发过程中重复使用相同或相似软件元素的过程。在面向对象方法中所使用的对象，由于对象所固有的封装性，使得对象的内部实现与外界隔离，从而具有较强的独立性。对象提供了比较理想的模块化机制和比较理想的可重用的软件成分。,有两种方法重复使用一个对象类：（1）创建该类的实例，从而直接使用它。（2）从它派生出一个满足当前需要的新类。4、易于开发大型软

50、件产品5、可维护性好,面向对象的程序设计主要考虑的是提高软件的（）A）可靠性 B）可重用性C）可移植性 D）可修改性,对象是显示世界中一个实际存在的事物，它可以是有形的也可以是无形的，下面所列举的不是对象的是（）A）桌子 B）飞机D）狗 D）苹果的颜色对象是构成客观世界的一个独立单位，它具有自己的静态特征（属性）和动态特征（行为或功能）,2.3.2 面向对象方法的基本概念1、对象（object）对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它是由一组表示其静态特征的属性和它可执行的一组操作封装而成的。2、类和实例 将属性、操作相似的对象归为类，也就是说，类是具有共同属性、共