数据结构和程序设计.ppt

第一章：数据结构与算法 考核知识点： 算法的基本概念 数据结构的基本概念 线性表的定义 栈和队列 线性链表 树的基本概念 查找技术 排序技术 第一章：数据结构与算法 第一节：算法 1、定义 所谓算法是指解题方案的准确而完整的描述。 2、算法的基本牲 （1）可行性:同一个算法在不同的计算机上应得到相同的结果 （2）确定性。是指算法中的每一步都必须是有明确的定义， 不允许有模棱两可的解释，也不允许有多义性。 （3）有穷性。是指必须能在执行有限步骤之后终止。 （4）拥有足够的情报。一个算法执行的结果总是与输入的数 据有关，不同的输入有不同的结果。当输入不足或输入错误 时，算法可能就无法执行。当算法拥有足够多的情报时（考 虑的输入可能性越多），出错的可能越小。 3、算法的基本要素 一个算法通常有二种基本要素组成：一是对数据对象的 运算和操作，二是算法的控制结构。 （1）对数据对象的运算和操作 基本运算和操作有以下四类： 算术运算、逻辑运算、关系运算和数据传输（赋值 、输入、输出）。 （2）算法的控制结构 算法的控制结构一般可分为顺序、选择、循环三种 基本结构。 4、算法设计的基本方法 计算机解题的过程实际上是实施某种算法，称计算机算法。 （1）列举法 列举法是指根据提出的问题，列举所有可能的情况，然后，进行 处理。 （2）归纳法 通过列举少量的特殊情况，经过分析，找出一般关系 （3）递推 从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果 （4）递归 将一个复杂的问题归结为若干个较简单的问题，直到最简单的问题解决 （5）减半递推技术 （6）回溯法 就是对问题分而治之。 5、算法复杂度 算法复杂度主要包括时间和空间复杂度。 （1）时间复杂度 是指算法基本运算的次数。（不是指运算的时间） （2）空间复杂度 执行这个算法所需要的内存空间。包括程序所占的空间 、输入的初始数据所占的空间、运算时所需的空间。 算法的时间复杂度是指 A）执行算法程序所需要的时间 B）算法程序的长度 C）算法执行过程中所需要的基 本运算次数 D）算法程序中的指令条数 算法的空间复杂度是指 A）算法程序的长度 B）算法程序中的指令条数 C）算法程序所占的存储空间 D）算法执行过程中所需要的 存储空间 第2节：数据结构的基本概念 大量的数据元素在计算机中如何组织，以便提高数据处理的 效率，并且节省计算机的存储空间，这是进行数据处理的关 键问题。 数据结构主要研究三个方面的问题： （1）数据的逻辑结构：数据集合众各数据元素间所固有的逻辑关 系 （2）数据的存储结构（物理结构）：各数据元素在计算机中的 存储关系 （3）对各种数据结构进行的运算。 以上问题的主要目的是为了提高数据处理的效率。所谓提高 数据处理的效率，主要包括两个方面：一是提高数据处理的 速度，二是尽量节省在数据处理过程中所占的计算机存储空 间。 1、什么是数据结构 实例：无序表的顺序查找与有序表的对分查找 35 16 78 85 43 29 33 21 54 46 16 21 29 33 35 43 46 54 78 85 数据元素在表中的表列 顺序对查找效率是有很 大的影响。 1、什么是数据结构 数据结构是指反映数据元素之间关系的数据元素集合的表示 。 学号姓名性别计算机 200501张三女80 200503李四男70 200513王五女50 成绩单 在上表中，查找给定学号的某学生的情况 时很方便的。但要查找计算机成绩在75分 以上的情况时，则需要从头到尾扫描。为 了便于查找成绩，可以进行重新组织 数据结构是指相互有关联的数据元素的集 合 1、什么是数据结构 （1）数据结构的逻辑结构 数据的逻辑结构是指反映数据元素之间逻辑关系的数 据结构。 （2）数据的存储结构 数据的逻辑结构在计算机存储空间的存放形式称为数据 的存储结构（也称数据的物理结构） 下列叙述中正确的是 A）一个逻辑数据结构只能有一种存储 结构 B）数据的逻辑结构属于线性结构，存 储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储 结构，且各种存储结构不影响数据处理的 效率 D）一个逻辑数据结构可以有多种存储 结构，且各种存储结构影响数据处理的效 率 数据的存储结构是指 A）存储在外存中的数据 B）数据所占的存储空间量 C）数据在计算机中的顺序存储 方式 D）数据的逻辑结构中计算机中 的表示 2、数据结构的图形表示 父亲 儿子女儿 d1 d2d3 名词解释： （1）结点 （2）前件结点 （3）后件结点 （4）根结点 （5）终结点 在数据结构中，与所使用 的计算机无关的数据结构 是（ ） A 逻辑 B 存储 C 逻辑和存储 D 物理 2、数据结构的图形表示 父亲 儿子女儿 d1 d2d3 名词解释： （1）结点 （2）前件结点 （3）后件结点 （4）根结点 （5）终结点 春夏秋冬 3、线性结构和非线性结构 如果在一个数据结构中一个数据元素都没有，则称该数 据结构为空的数据结构。 根据数据元素之间前后件关系的 复杂程度，将数据结构分为这两类 什么是线性结构？ 线性必须满足以下二个条件： （1）有且只有一个根结点。 （2）每个结点最多有一个前件，也最多一个后件。 d1 d2d3 春夏秋冬 在数据结构中，从逻辑上可以把数 据结构分成（） A 动态结构和静态结构 B 紧凑结构和非紧凑结构 C 线性结构和非线性结构 D 内部结构和外部结构 第3节、线性表和顺序存储结构 1、线性表的基本概念 线性表由一组数据元素组成。 线性表是一种线性结构。 非空线性表有如下结构牲： （1）有且只有一个根结点 （2）有且只有一个终结节点 （3）除以上二结点外，每个结点有 且只有一个前件，也有且只有一个后件。 d1 d2d3 春夏秋冬 姓名性别数学英语 张三女7070 李四男6590 王五女6880 2、线性表的顺序存储结构 线性表顺序存储具有如下特点 （1）线性表中所有元素所占的存储空间 是连续的。 （2）数据元素在存储空间中是按逻辑顺 序依次存放的。 姓名数学英语 张三7070 李四6590 王五6880 张三 70 70 李四 65 90 王五 68 80 线性表的顺序存储结构是一种 随机存取的存储结构 。可随机 访问任意一个结点 3、线性表的插入运算 2 5 9 7 14 3、线性表的插入运算 2 5 9 7 14 3、线性表的插入运算 2 5 9 7 14 3、线性表的插入运算 2 5 9 7 14 3、线性表的插入运算 2 14 5 9 7 结论：如果在线性表的末尾进行，即 在第n个元素之后插入新元素，则只 要增加一个元素即可，不需要移动元 素 如果要在线性表的第1个元素之前插 入，则需要移动表中所有的元素。 在一般情况下，如果在第i个元素之 前进行，则第i个元素之后的所有元 素都必须移动。 在平均情况下，需要移动表中一半的 元素。 因此算法的平均时间复杂度为O(n). 4、线性表的删除运算 2 14 5 9 7 4、线性表的删除运算 2 5 9 7 4、线性表的删除运算 2 5 9 7 4、线性表的删除运算 2 5 9 7 4、线性表的删除运算 2 5 9 7 注意：如果为线性表开辟的存储空间 已经满了，不能再插入元素，否则会 造成“上溢”错误 如果删除第n个元素，则不需要移动 表中的元素；如果删除第1个元素， 则需要移动表中所有的元素。在一般 情况下，若要删除第i个元素，则原来 第i个元素之后的所有元素都必须依次 往前移动一个位置。 平均要移动表中一半的元素。 算法的平均时间复杂度为O(n). 总结：在线性表顺序存储的情况下，要插入或 删除一个元素，其效率都是很低的，特别是在 线性表比较大的情况下更为突出，由于数据元 素的移动而消耗较多的处理时间。 线性表的顺序存储结构对于小线性表或者元素 不常变动的线性表来说是合适的，因为顺序存 储结构比较简单。 对线性表，在下列情况下应当采用链表表示的是（） A） 经常需要随机地存取元素 B）经常需要进行插入和删除操作 C）表中元素需要占据一片连续的存储空间 D）表中元素的个数不变 第4节：栈和队列 1、栈及其运算 栈是限定在一端进行插入与删除的线性表。 入栈原则：先进后出，后进选出。 5 9 7 栈顶 栈底 6 4 1、栈及其运算 栈是限定在一端进行插入与删除的线性表 4 5 9 7 栈顶 栈底 6 1、栈及其运算 栈是限定在一端进行插入与删除的线性表 6 4 5 9 7 栈顶 栈底 1、栈及其运算 栈是限定在一端进行插入与删除的线性表 6 4 5 9 7 栈顶 栈底 1、栈及其运算 栈是限定在一端进行插入与删除的线性表 4 5 9 7 栈顶 栈底 1、栈及其运算 栈是限定在一端进行插入与删除的线性表 5 9 7 栈顶 栈底 1、栈及其运算 栈是限定在一端进行插入与删除的线性表 5 9 7 栈顶 栈底 下列关于栈的描述正确的是 A）在栈中只能插入元素而不能删除元素 B）在栈中只能删除元素而不能插入元素 C）栈是特殊的线性表，只能在一端插入或删除元素 D）栈是特殊的线性表，只能在一端插入元素，而在另 一端删除元素 下列关于栈的描述中错误的 是 A）栈是先进后出的线性表 B）栈只能顺序存储 C）栈具有记忆作用 D）对栈的插入与删除操作 中，不需要改变栈底指针 实例1： 栈底至栈顶依次存放元素A、B、C、D， E在第五个元素E入栈前，栈中元素可以出栈，则 出栈序列可能是_。 A. ABCED B. DBCEA C. CDABE D. DCBEA D C B A 实例：若进栈序列为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，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）一定是2 C）可能是1 D）不确定 2、队列及其运算 什么是队列？ 是指允许在一端进行插入、而在另一端进行删除的线性表 。 即“先进选出，后进后出”的原则 DCBA frontrear 2、队列及其运算 什么是队列？ 是指允许在一端进行插入、而在另一端进行删除的线性表 。 即“先进选出，后进后出”的原则 EDCBA front rear 2、队列及其运算 什么是队列？ 是指允许在一端进行插入、而在另一端进行删除的线性表 。 即“先进选出，后进后出”的原则 FEDCB A front rear 2、队列及其运算 什么是队列？ 是指允许在一端进行插入、而在另一端进行删除的线性表 。 即“先进选出，后进后出”的原则 FEDCB front rear 2、队列及其运算 什么是队列？ 是指允许在一端进行插入、而在另一端进行删除的线性表 。 即“先进选出，后进后出”的原则 FEDC front rear 2、队列及其运算 什么是队列？ 是指允许在一端进行插入、而在另一端进行删除的线性表 。 即“先进选出，后进后出”的原则 FEDC front rear 栈和队列的共同点是（ ） A）都是先进先出 B）都是后进先出 C）只允许在端点处插入和删除元素 D）没有共同点 一个队列的入队序列是1，2，3，4， 则队列的输出序列是 A）4，3，2，1 B）1，2，3，4 C）1，4，3，2 D）3，2，4，1 2、队列及其运算 什么是队列？ 是指允许在一端进行插入、而在另一端进行删除的线性表 。 即“先进选出，后进后出”的原则 FED front rear 下列叙述中正确的是 A）线性表是线性结构 B）栈与队列是非线性结构 C）线性链表是非线性结构 D）二叉树是线性结构 下列关于队列的叙述中正确的是 A）在队列中只能插入数据 B）在队列中只能删除数据 C）队列是先进先出的线性表 D）队列是先进后出的线性表 按照“后进先出”原则组织数据的数据结构是 A）队列 B）栈 C）双向链表 D）二叉树 第5节：线性链表 线性表的顺序结构的主要缺点 （1）插入或删除时要移动大量的数据元素。 （2）分配空间后，如果存储空间已满，会出现“上溢”错误。 （3）多个线性表同时工作时，需要大量的连续空间。 假设每个数据结点对应一个存储单元，这种存储单元称为 存储结点，简称结点。 在链式存储方式中，要求每个结点由两部组成：一部分用 于存放数据元素值，称为数据区；另一部分用于存放指针，称 为指针域。 数据域指针域 第5节：线性链表 在链式存储结构中，存储数据结构的存储空间可以不连续。 链式存储方式既可以用于线性结构，也可以用于非线性结构。 在用于非线性结构时，其指针的个数要多一些。 数据指针数据指针数据指针 数据NULL HEAD 0数 据 指 针 指 针 数 据 指 针 指 针 数 据 指 针 指 针 数 据 0 单向链表示意图 双向链表示意图 下列对于线性链表的描述中正确的是 A A）存储空间不一定是连续，且各元素的存储顺序是任意的 B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面 C）存储空间必须连续，且前件元素一定存储在后件元素的前面 D）存储空间必须连续，且各元素的存储顺序是任意的 链表不具备的特点是 A）可随机访问任意一个结点 B）插入和删除不需要移动任何元素 C）不必事先估计存储空间 D）所需要空间与其长度成正比 下列叙述中正确的是 A 线性链表是线性表的链式存储结构 B 栈和队列是非线性结构 C 双向链表是非线性结构 D 只有根结点的二叉树是线性结构 第6节：树和二叉树 1、树 树是一种非线性结构。 南昌工程学院 信息系水利系机电系 软件应用网络 应电供电通信 第6节：树和二叉树 1、 关于树的基本术语： （1）根结点（没有前件的结点） （2）父结点（即前件） （3）子结点（即后件） （4）叶子结点（没有后件的结点） （5）一个结点有后件的个数叫该结点的度 （6）树的最大层称为树的深度 R KP Q BEN OWZ 下列关于树的概念错误的是（） A）一棵树中只有一个无前驱的结点 B）一棵树的度为树中各个结点的度数之和 C）一棵树中，每个结点的度数之和等于结 点总数减1 D）一棵树中每个结点的度数之和与边的条 数相等 第6节：树和二叉树 2、二叉树 二叉树具有以下两个特点 （1）非空二叉树只有一个根结点。 （2）每个结点最多有二个子树，且 分别称左子树和右子树。 二叉树的基本性质 （1）第K层上最多有2 k-1个结点 （2）深度为m的最多有2m-1个结点 （3）在任意一个二叉树中，度为0的结点（即叶子 结点）总比度为2的点多一个。 （4）具有n个结点的二叉树，其深度至少为 log2n+1, R KQ BNOW 一棵二叉树第六层（根结点为第一层）的结点数最多为 【】 个 某二叉树中，度为2的结点有18个，则该二*树中有（）个叶子结点 。 设树T的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1 。则T中的叶子结点为 A）8 B）7 C）6 D）5 设一棵完全二叉树共有700个结点，则在该二叉树中有_个叶 子结点 第6节：树和二叉树 3、满二叉树和完全二叉树 满二叉树：除最后一层外，每一层上 的所有结点都有两个子结点。 完全二叉树：是除最后一层外，每一 层上的结点数均达到最大值；在最后 一层上只缺少右边的若干结点。 R K B R KQ BN R KQ BNOW R KQ BW 在深度为5的满二叉树中， 叶子结点的个数为 A）32 B）31 C）16 D）15 第6节：树和二叉树 4、二叉树的遍历 遍历是指不重复地访问二叉树中所 有结点。 遍历分三种：前序、中序和后序遍历 。 （1）前序遍历 首先访问根结点，再前序左子树，最 后前序右子树。 如：FCADBEGHP F C A PH E DG B 第6节：树和二叉树 4、二叉树的遍历 遍历是指不重复地访问二叉树中所 有结点。 遍历分三种：前序、中序和后序遍历 。 （2）中序遍历 首先中序遍历左子树，再访问根结点 ，最后中序右子树。 如：ACBDFEHGP F C A PH E DG B 第6节：树和二叉树 4、二叉树的遍历 遍历是指不重复地访问二叉树中所 有结点。 遍历分三种：前序、中序和后序遍历 。 （3）后中序遍历 首先后序遍历左子树，再后序右子树 ，最后访问根结点 如：ABDCHPGEF F C A PH E DG B 实例：已知二叉树后序遍历序列是 dabec，中序遍历序列是debac，它的 前序遍历序列是_。 A. cedba B. acbed C. decab D. deabc c e a db 实例：已知二叉树后序遍历序列是 dabec，中序遍历序列是debac，它的 前序遍历序列是_。 A. cedba B. acbed C. decab D. deabc 由后序由以知道根节点是C； 而C又在中序的最后，说明 没有右子树。 c e a d b 实例：已知二叉树后序遍历序列是 dabec，中序遍历序列是debac，它的 前序遍历序列是_。 A. cedba B. acbed C. decab D. deabc c e a d b 设一棵二叉树的中序遍历结果 为DBEAFC,前序遍历结果为 ABDECF,则后序遍历结果为 _。 如图所示的二叉树，其中序遍历的结果 为（ ） A)abcdef B)abdefc C)dbefac D)defbca a bc e f d 下面关于线性表的叙述错误的是（） A）若用数组表示，表中诸元素的存储位置 是连在一起的 B）若用链表表示，便于插入和删除操作 C）若用链表表示，不需要占用一片相邻的 存储空间 D）表的插入和删除操作仅允许在表的一端 进行 第7节：查找技术 1、顺序查找 以下2种情况只能采用顺序查找 （1）无序表 （2）即使有序线性表，如果采用链式存储结构。 2、二分法查找 只适用于顺序存储的有序表。 对长度为n的有序线性表，在最坏情况下，二分查找只需 比较log2n次，而顺序查找要比较n次。 在长度为n的有序线性表中进行二分查找，需要的比较次数为_。 对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为 A）n+1 B）n C）(n+1)/2 D）n/2 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）冒泡排序法。 5173169 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）冒泡排序法。 5173169 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）冒泡排序法。 1573169 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）冒泡排序法。 1573169 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）冒泡排序法。 1573169 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）冒泡排序法。 1537169 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）冒泡排序法。 1537169 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）冒泡排序法。 1531769 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）冒泡排序法。 1531769 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）冒泡排序法。 1531679 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）冒泡排序法。 1531679 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）冒泡排序法。 1531679 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）冒泡排序法。 1531679 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）冒泡排序法。 1531679 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）冒泡排序法。 1513679 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）冒泡排序法。 1513679 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）冒泡排序法。 1153679 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）冒泡排序法。 1153679 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）冒泡排序法。 1153679 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）冒泡排序法。 1153679 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）冒泡排序法。 1135679 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）冒泡排序法。 1531679 设线性表的长度为n,则最坏情况下，冒泡排序要经过n/2 遍从前向后的扫描和n/2遍从后向前的扫描。需要比较的次 数是n(n-1)/2次。 在最坏的情况下，冒泡排序的时间复杂度为O(n2) 对长度为10的线性表进行冒泡排序，最坏情况下需要 比较的次数为 。 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）快速排序 9173165 在第一个、中间、最后一个中，取出一个中间的值 ，放在T变量中，T=5 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）快速排序 917316 在第一个、中间、最后一个中，取出一个中间的值 ，放在T变量中，T=5 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）快速排序 173169 在第一个、中间、最后一个中，取出一个中间的值 ，放在T变量中，T=5 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）快速排序 173169 在第一个、中间、最后一个中，取出一个中间的值 ，放在T变量中，T=5 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）快速排序 173169 在第一个、中间、最后一个中，取出一个中间的值 ，放在T变量中，T=5 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）快速排序 173169 在第一个、中间、最后一个中，取出一个中间的值 ，放在T变量中，T=5 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）快速排序 117369 在第一个、中间、最后一个中，取出一个中间的值 ，放在T变量中，T=5 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）快速排序 117369 在第一个、中间、最后一个中，取出一个中间的值 ，放在T变量中，T=5 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）快速排序 117369 在第一个、中间、最后一个中，取出一个中间的值 ，放在T变量中，T=5 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）快速排序 113769 在第一个、中间、最后一个中，取出一个中间的值 ，放在T变量中，T=5 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）快速排序 113769 在第一个、中间、最后一个中，取出一个中间的值 ，放在T变量中，T=5 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）快速排序 113769 在第一个、中间、最后一个中，取出一个中间的值 ，放在T变量中，T=5 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）快速排序 113769 在第一个、中间、最后一个中，取出一个中间的值 ，放在T变量中，T=5 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。 （1）快速排序 1135769 在第一个、中间、最后一个中，取出一个中间的值 ，放在T变量中，T=5 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 9173165 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 9173165 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 973165 1 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 973165 1 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 1973165 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 1973165 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 193165 7 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 193165 7 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 1793165 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 1793165 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 179165 3 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 179165 3 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 1379165 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 1379165 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 137965 1 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 137965 1 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 1137965 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 1137965 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 113795 6 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 113795 6 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 1136795 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 1136795 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 113679 5 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 113679 5 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （1）简单插入排序 1135679 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 2、插入类排序法 （2）希尔排序法 希尔排序法属于插入类排序，它的思想是将整个无 序的序列分割成若干小的子序列分别进行插入排序。 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 9173165 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 9173165 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 9173165 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 9173165 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 9173165 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 9173165 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 9173165 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1973165 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1973165 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1973165 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1973165 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1973165 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1973165 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1973165 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1973165 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1173965 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1173965 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1173965 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1173965 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1173965 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1173965 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1137965 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1137965 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1137965 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1137965 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1137965 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1135967 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1135967 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1135967 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1135967 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1135697 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1135697 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1135697 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1135679 指向最小的数 第8节：排序技术 排序分：交换类排序法、插入类排序法和选择类排序法。 3、选择类排序法 1135679 指向最小的数 第二章：程序设计基础 考核知识点： 程序设计方法与风格 结构化程序设计（原则、基本结构与特点 ） 面向对象的程序设计方法、对象、属性及继承 与多态性。（优点，基本概念） 第二章：程序设计基础 2.1 程序设计方法与风格 要形成良好的程序设计风格，应考虑如下因素： 1、源程序文档化 （1）符号名的命名应具有一定的实际含义。 （2）程序要有注释。 注释一般分为序言性注释和功能性注释。 序言性注释通常位于每个程序的开头部分，它给出程序的整体说明，主要描 述：程序标题、程序的功能性说明 、主要算法、接口说明、程序位置、开发简历 、程序设计者、复审者、复审日期、修改日期等 功能性注释的位置一般嵌在源程序体中，主要描述其后的语句或程序做什么 （3）视觉组织要好，可以利用空格、空行和缩进等技术。 2、数据说明的方法 在编写程序时，要注意数据说明的风格，以便使程序中的 数据说明更易于理解和维护。数据说明应注意以下几点： （1）数据说明的次序规范化。 （2）说明语句中变量安排要有顺序。 （3）使用注解来说明复杂的数据结构。 3、语句的结构（清晰第一，效率第二） 程序应该简单易懂，语句构造应简单直接，不应该为提 高效率而把语句复杂化。 4、输入输出 输入输出方式和格式应尽可能方便用户的使用。 对建立良好的程序设计风格，下面描述正确的是（） A）程序应力求简单、清晰、可读性好 B）符号的命名只要合语法 C）充分考虑程序的执行效率 D）程序的注释可有可无 2.2 结构化程序设计