第一章：数据结构与算法考核知识点：算法的基本概念数据结构的基本概念线性表的定义栈和队列线性链表树的基本概念排序技术1第一章：数据结构与算法第一节：算法1、定义所谓算法是指解题方案的准确而完整的描述算法是指解题方案的准确而完整的描述。2、算法的基本牲（1）可行性可行性:同一个算法在不同的计算机上应得到相同的结果同一个算法在不同的计算机上应得到相同的结果（2）确定性确定性。是指算法中的每一步都必须是有明确的定义，不允许有模棱两可的解释，也不允许有多义性。（3）有穷性有穷性。是指必须能在执行有限步骤之后终止。（4）拥有足够的情报拥有足够的情报。一个算法执行的结果总是与输入的数据有关，不同的输入有不同的结果。当输入不足或输入错误时，算法可能就无法执行。当算法拥有足够多的情报时（考虑的输入可能性越多），出错的可能越小。23、算法的基本要素一个算法通常有二种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。（1）对数据对象的运算和操作 基本运算和操作有以下四类： 算术运算、逻辑运算、关系运算和数据传输（赋值、输入、输出）。（2）算法的控制结构 算法的控制结构控制结构一般可分为顺序、选择、循环顺序、选择、循环三种基本结构。 34、算法设计的基本方法计算机解题的过程实际上是实施某种算法，称计算机算法。（1）列举法列举法 列举法是指根据提出的问题，列举所有可能的情况，然后，进行列举法是指根据提出的问题，列举所有可能的情况，然后，进行处理。处理。（2）归纳法归纳法通过列举少量的特殊情况，经过分析，找出一般关系通过列举少量的特殊情况，经过分析，找出一般关系（3）递推递推从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果（4）递归递归将一个复杂的问题归结为若干个较简单的问题，直到最简单的问题解决将一个复杂的问题归结为若干个较简单的问题，直到最简单的问题解决（5）减半递推技术减半递推技术 （6）回溯法）回溯法就是对问题分而治之。就是对问题分而治之。 45、算法复杂度算法复杂度主要包括时间和空间复杂度。（1）时间复杂度时间复杂度 是指算法基本运算的次数。（不是指运算的时间）（2）空间复杂度空间复杂度 执行这个算法所需要的内存空间。包括程序所占的空间、输入的初始数据所占的空间、运算时所需的空间。算法的时间复杂度是指 A） 执 行 算 法 程 序 所 需 要 的 时 间 B）算法程序的长度 C）算法执行过程中所需要的基本运算次数 D）算法程序中的指令条数 算法的空间复杂度是指 A）算法程序的长度 B）算法程序中的指令条数 C）算法程序所占的存储空间 D）算法执行过程中所需要的存储空间 5第2节：数据结构的基本概念大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。数据结构主要研究三个方面的问题：（1）数据的逻辑结构：数据集合众各数据元素间所固有的逻辑关系（2）数据的存储结构（物理结构）：各数据元素在计算机中的存储关系（3）对各种数据结构进行的运算。以上问题的主要目的是为了提高数据处理的效率。所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占的计算机存储空间。61、什么是数据结构实例：无序表的顺序查找与有序表的对分查找3516788543293321544616212933354346547885数据元素在表中的表列顺序对查找效率是有很大的影响。71、什么是数据结构数据结构是指反映数据元素之间关系的数据元素集合的表示。学号姓名性别计算机200501张三女80200503李四男70200513王五女50成绩单在上表中，查找给定学号的某学生的情况时很方便的。但要查找计算机成绩在75分以上的情况时，则需要从头到尾扫描。为了便于查找成绩，可以进行重新组织数据结构是指相互有关联的数据元素的集合81、什么是数据结构（1）数据结构的逻辑结构 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。（2）数据的存储结构 数据的逻辑结构在计算机存储空间的存放形式称为数据的存储结构（也称数据的物理结构）下列叙述中正确的是A）一个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率 数据的存储结构是指 A）存储在外存中的数据B）数据所占的存储空间量C）数据在计算机中的顺序存储方式D）数据的逻辑结构中计算机中的表示 92、数据结构的图形表示父亲儿子女儿d1d2d3名词解释：（1）结点（2）前件结点（3）后件结点（4）根结点（5）终结点在数据结构中，与所使用的计算机无关的数据结构是（ ）A 逻辑 B 存储C 逻辑和存储D 物理102、数据结构的图形表示父亲儿子女儿d1d2d3名词解释：（1）结点（2）前件结点（3）后件结点（4）根结点（5）终结点春夏秋冬113、线性结构和非线性结构 如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。根据数据元素之间前后件关系的复杂程度，将数据结构分为这两类什么是线性结构？线性必须满足以下二个条件：（1）有且只有一个根结点。（2）每个结点最多有一个前件，也最多一个后件。d1d2d3春夏秋冬在数据结构中，从逻辑上可以把数据结构分成（）A 动态结构和静态结构B 紧凑结构和非紧凑结构C 线性结构和非线性结构D 内部结构和外部结构12 第3节、线性表和顺序存储结构1、线性表的基本概念线性表由一组数据元素组成。线性表是一种线性结构。非空线性表有如下结构牲：（1）有且只有一个根结点（2）有且只有一个终结节点（3）除以上二结点外，每个结点有且只有一个前件，也有且只有一个后件。d1d2d3春夏秋冬姓名性别数学英语张三女7070李四男6590王五女6880132、线性表的顺序存储结构线性表顺序存储具有如下特点（1）线性表中所有元素所占的存储空间是连续的。（2）数据元素在存储空间中是按逻辑顺序依次存放的。姓名数学英语张三7070李四6590王五6880张三7070李四6590王五6880线性表的顺序存储结构是一种线性表的顺序存储结构是一种随机存取的存储结构随机存取的存储结构 。可随机。可随机访问任意一个结点访问任意一个结点143、线性表的插入运算14153、线性表的插入运算14163、线性表的插入运算14173、线性表的插入运算14183、线性表的插入运算结论：如果在线性表的末尾进行，即在第n个元素之后插入新元素，则只要增加一个元素即可，不需要移动元素如果要在线性表的第1个元素之前插入，则需要移动表中所有的元素。在一般情况下，如果在第i个元素之前进行，则第i个元素之后的所有元素都必须移动。在平均情况下，需要移动表中一半的在平均情况下，需要移动表中一半的元素。元素。因此算法的平均时间复杂度为因此算法的平均时间复杂度为O(n).194、线性表的删除运算204、线性表的删除运算214、线性表的删除运算224、线性表的删除运算234、线性表的删除运算注意：如果为线性表开辟的存储空间已经满了，不能再插入元素，否则会造成“上溢”错误如果删除第n个元素，则不需要移动表中的元素；如果删除第1个元素，则需要移动表中所有的元素。在一般情况下，若要删除第i个元素，则原来第i个元素之后的所有元素都必须依次往前移动一个位置。平均要移动表中一半的元素。算法的平均时间复杂度为算法的平均时间复杂度为O(n).24 总结：在线性表顺序存储的情况下，要插入或删除一个元素，其效率都是很低的，特别是在线性表比较大的情况下更为突出，由于数据元素的移动而消耗较多的处理时间。线性表的顺序存储结构对于小线性表或者元素不常变动的线性表来说是合适的，因为顺序存储结构比较简单。对线性表，在下列情况下应当采用链表表示的是（）A） 经常需要随机地存取元素B）经常需要进行插入和删除操作C）表中元素需要占据一片连续的存储空间D）表中元素的个数不变25 第4节：栈和队列1、栈及其运算 栈是限定在一端进行插入与删除的线性表。 入栈原则：先进后出，后进选出。栈顶栈底64261、栈及其运算 栈是限定在一端进行插入与删除的线性表栈顶栈底6271、栈及其运算 栈是限定在一端进行插入与删除的线性表栈顶栈底281、栈及其运算 栈是限定在一端进行插入与删除的线性表栈顶栈底291、栈及其运算 栈是限定在一端进行插入与删除的线性表栈顶栈底301、栈及其运算 栈是限定在一端进行插入与删除的线性表栈顶栈底311、栈及其运算 栈是限定在一端进行插入与删除的线性表栈顶栈底下列关于栈的描述正确的是A）在栈中只能插入元素而不能删除元素B）在栈中只能删除元素而不能插入元素C）栈是特殊的线性表，只能在一端插入或删除元素D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素 下列关于栈的描述中错误的是A）栈是先进后出的线性表B）栈只能顺序存储C）栈具有记忆作用D）对栈的插入与删除操作中，不需要改变栈底指针 32实例1： 栈底至栈顶依次存放元素A、B、C、D，E在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是_。A. ABCEDB. DBCEAC. CDABED. DCBEA33实例：若进栈序列为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）一定是2C）可能是1 D）不确定342、队列及其运算 什么是队列？ 是指允许在一端进行插入、而在另一端进行删除的线性表。 即“先进选出，后进后出”的原则frontrear352、队列及其运算 什么是队列？ 是指允许在一端进行插入、而在另一端进行删除的线性表。 即“先进选出，后进后出”的原则frontrear362、队列及其运算 什么是队列？ 是指允许在一端进行插入、而在另一端进行删除的线性表。 即“先进选出，后进后出”的原则frontrear372、队列及其运算 什么是队列？ 是指允许在一端进行插入、而在另一端进行删除的线性表。 即“先进选出，后进后出”的原则frontrear382、队列及其运算 什么是队列？ 是指允许在一端进行插入、而在另一端进行删除的线性表。 即“先进选出，后进后出”的原则frontrear392、队列及其运算 什么是队列？ 是指允许在一端进行插入、而在另一端进行删除的线性表。 即“先进选出，后进后出”的原则frontrear栈和队列的共同点是（ ） A）都是先进先出 B）都是后进先出 C）只允许在端点处插入和删除元素 D）没有共同点一个队列的入队序列是1，2，3，4，则队列的输出序列是A）4，3，2，1 B）1，2，3，4C）1，4，3，2 D）3，2，4，1402、队列及其运算 什么是队列？ 是指允许在一端进行插入、而在另一端进行删除的线性表。 即“先进选出，后进后出”的原则frontrear下列叙述中正确的是 A）线性表是线性结构 B）栈与队列是非线性结构 C）线性链表是非线性结构 D）二叉树是线性结构 下列关于队列的叙述中正确的是 A） 在 队 列 中 只 能 插 入 数 据 B）在队列中只能删除数据 C）队列是先进先出的线性表 D）队列是先进后出的线性表 41按照“后进先出”原则组织数据的数据结构是 A）队列 B）栈 C）双向链表 D）二叉树42 第5节：线性链表线性表的顺序结构的主要缺点（1）插入或删除时要移动大量的数据元素。（2）分配空间后，如果存储空间已满，会出现“上溢”错误。（3）多个线性表同时工作时，需要大量的连续空间。 假设每个数据结点对应一个存储单元，这种存储单元称为存储结点，简称结点。 在链式存储方式中，要求每个结点由两部组成：一部分用于存放数据元素值，称为数据区；另一部分用于存放指针，称为指针域。数据域指针域43 第5节：线性链表在链式存储结构中，存储数据结构的存储空间可以不连续。链式存储方式既可以用于线性结构，也可以用于非线性结构。在用于非线性结构时，其指针的个数要多一些。数据指针数据指针数据指针数据NULLHEAD0数据指针指针数据指针指针数据指针指针数据0单向链表示意图双向链表示意图44下列对于线性链表的描述中正确的是 AA）存储空间不一定是连续，且各元素的存储顺序是任意的B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面C）存储空间必须连续，且前件元素一定存储在后件元素的前面D）存储空间必须连续，且各元素的存储顺序是任意的 链表不具备的特点是A）可随机访问任意一个结点 B）插入和删除不需要移动任何元素C）不必事先估计存储空间 D）所需要空间与其长度成正比下列叙述中正确的是A 线性链表是线性表的链式存储结构B 栈和队列是非线性结构C 双向链表是非线性结构D 只有根结点的二叉树是线性结构45 第6节：树和二叉树1、树 树是一种非线性结构。南昌工程学院信息系水利系机电系软件应用网络应电供电通信46 第6节：树和二叉树 1、 关于树的基本术语：（1）根结点（没有前件的结点）（2）父结点（即前件）（3）子结点（即后件）（4）叶子结点（没有后件的结点）（5）一个结点有后件的个数叫该结点的度（6）树的最大层称为树的深度RKPQBENOWZ下列关于树的概念错误的是（）A）一棵树中只有一个无前驱的结点B）一棵树的度为树中各个结点的度数之和C）一棵树中，每个结点的度数之和等于结点总数减1D）一棵树中每个结点的度数之和与边的条数相等47 第6节：树和二叉树2、二叉树 二叉树具有以下两个特点（1）非空二叉树只有一个根结点。（2）每个结点最多有二个子树，且分别称左子树和右子树。二叉树的基本性质（1）第K层上最多有2 k-1个结点（2）深度为m的最多有2m-1个结点（3）在任意一个二叉树中，度为0的结点（即叶子结点）总比度为2的点多一个。（4）具有n个结点的二叉树，其深度至少为log2n+1,RKQBNOW48一棵二叉树第六层（根结点为第一层）的结点数最多为 【】 个 某二叉树中，度为2的结点有18个，则该二*树中有（）个叶子结点。设树T的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1。则T中的叶子结点为 A）8 B）7 C）6 D）5设一棵完全二叉树共有700个结点，则在该二叉树中有_个叶子结点 49 第6节：树和二叉树3、满二叉树和完全二叉树满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。 完全二叉树：是除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。RKBRKQBNRKQBNOWRKQBW在深度为5的满二叉树中，叶子结点的个数为 A）32 B）31 C）16 D）1550 第6节：树和二叉树4、二叉树的遍历 遍历是指不重复地访问二叉树中所有结点。遍历分三种：前序、中序和后序遍历。（1）前序遍历首先访问根结点，再前序左子树，最后前序右子树。如：FCADBEGHPFCAPHEDGB51 第6节：树和二叉树4、二叉树的遍历 遍历是指不重复地访问二叉树中所有结点。遍历分三种：前序、中序和后序遍历。（2）中序遍历首先中序遍历左子树，再访问根结点，最后中序右子树。如：ACBDFEHGPFCAPHEDGB52 第6节：树和二叉树4、二叉树的遍历 遍历是指不重复地访问二叉树中所有结点。遍历分三种：前序、中序和后序遍历。（3）后中序遍历首先后序遍历左子树，再后序右子树，最后访问根结点如：ABDCHPGEFFCAPHEDGB53 实例：已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是_。A. cedbaB. acbedC. decabD. deabcceadb54 实例：已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是_。A. cedbaB. acbedC. decabD. deabc由后序由以知道根节点是C；而C又在中序的最后，说明没有右子树。ceadb55 实例：已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是_。A. cedbaB. acbedC. decabD. deabcceadb设一棵二叉树的中序遍历结果为DBEAFC,前序遍历结果为ABDECF,则后序遍历结果为_。56如图所示的二叉树，其中序遍历的结果为（ ）A)abcdef B)abdefcC)dbefac D)defbcaabcefd下面关于线性表的叙述错误的是（）A）若用数组表示，表中诸元素的存储位置是连在一起的B）若用链表表示，便于插入和删除操作C）若用链表表示，不需要占用一片相邻的存储空间D）表的插入和删除操作仅允许在表的一端进行57 第7节：查找技术1、顺序查找 以下2种情况只能采用顺序查找 （1）无序表 （2）即使有序线性表，如果采用链式存储结构。2、二分法查找 只适用于顺序存储的有序表。 对长度为n的有序线性表，在最坏情况下，二分查找只需比较log2n次，而顺序查找要比较n次。在长度为n的有序线性表中进行二分查找，需要的比较次数为_。对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为 A）n+1 B）n C）(n+1)/2 D）n/2 58 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。517316959 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。517316960 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。157316961 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。157316962 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。157316963 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。153716964 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。153716965 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。153176966 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。153176967 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。153167968 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。153167969 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。153167970 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。153167971 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。153167972 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。151367973 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。151367974 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。115367975 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。115367976 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。115367977 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。115367978 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。113567979 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）冒泡排序法。1531679 设线性表的长度为线性表的长度为n,则最坏情况下，冒泡排序要经过n/2遍从前向后的扫描和n/2遍从后向前的扫描。需要比较的次数是n(n-1)/2次次。在最坏的情况下，冒泡排序的时间复杂度为O(n2)80对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为 。81 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序9173165在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=582 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=583 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=584 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=585 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=586 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=587 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=588 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=589 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=590 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=591 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=592 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=593 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=594 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。1、交换类排序法 借助元素之间的互相交换进行排序的一种方法。（1）快速排序1135769在第一个、中间、最后一个中，取出一个中间的值，放在T变量中，T=595 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 917316596 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序917316597 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序 198 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序 199 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序 1973165100 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序 1973165101 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序 7102 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序 7103 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序 1793165104 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序 1793165105 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序 3106 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序 3107 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序 1379165108 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序 1379165109 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序 1110 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序 1111 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序 1137965112 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序 1137965113 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序 6114 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序 6115 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序 1136795116 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序 1136795117 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序 5118 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序 5119 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （1）简单插入排序 1135679120 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。2、插入类排序法 （2）希尔排序法 希尔排序法属于插入类排序，它的思想是将整个无序的序列分割成若干小的子序列分别进行插入排序。121 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 9173165指向最小的数122 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 9173165指向最小的数123 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 9173165指向最小的数124 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 9173165指向最小的数125 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 9173165指向最小的数126 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 9173165指向最小的数127 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 9173165指向最小的数128 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1973165指向最小的数129 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1973165指向最小的数130 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1973165指向最小的数131 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1973165指向最小的数132 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1973165指向最小的数133 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1973165指向最小的数134 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1973165指向最小的数135 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1973165指向最小的数136 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1173965指向最小的数137 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1173965指向最小的数138 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1173965指向最小的数139 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1173965指向最小的数140 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1173965指向最小的数141 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1173965指向最小的数142 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1137965指向最小的数143 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1137965指向最小的数144 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1137965指向最小的数145 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1137965指向最小的数146 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1137965指向最小的数147 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1135967指向最小的数148 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1135967指向最小的数149 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1135967指向最小的数150 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1135967指向最小的数151 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1135697指向最小的数152 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1135697指向最小的数153 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1135697指向最小的数154 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1135679指向最小的数155 第8节：排序技术排序分：交换类排序法、插入类排序法和选择类排序法。3、选择类排序法 1135679指向最小的数156第二章：程序设计基础第二章：程序设计基础考核知识点：程序设计方法与风格结构化程序设计（原则、基本结构与特点 ）面向对象的程序设计方法、对象、属性及继承与多态性。（优点，基本概念）157第二章：程序设计基础第二章：程序设计基础2.1 程序设计方法与风格 要形成良好的程序设计风格，应考虑如下因素：1、源程序文档化 （1）符号名的命名应具有一定的实际含义。 （2）程序要有注释。 注释一般分为序言性注释和功能性注释。 序言性注释通常位于每个程序的开头部分，它给出程序的整体说明，主要描述：程序标题、程序的功能性说明 、主要算法、接口说明、程序位置、开发简历、程序设计者、复审者、复审日期、修改日期等 功能性注释的位置一般嵌在源程序体中，主要描述其后的语句或程序做什么 （3）视觉组织要好，可以利用空格、空行和缩进等技术。1582、数据说明的方法 在编写程序时，要注意数据说明的风格，以便使程序中的数据说明更易于理解和维护。数据说明应注意以下几点：（1）数据说明的次序规范化。（2）说明语句中变量安排要有顺序。（3）使用注解来说明复杂的数据结构。3、语句的结构（清晰第一，效率第二） 程序应该简单易懂，语句构造应简单直接，不应该为提高效率而把语句复杂化。1594、输入输出 输入输出方式和格式应尽可能方便用户的使用。对建立良好的程序设计风格，下面描述正确的是（）A）程序应力求简单、清晰、可读性好B）符号的命名只要合语法C）充分考虑程序的执行效率D）程序的注释可有可无1602.2 结构化程序设计2.2.1 结构化程序设计原则 结构化程序设计的原则概括为：自顶向下、逐步求精、模块化和限制使用goto语句。1、自顶向下 程序设计时，应先考虑总体，后考虑细节。2、逐步求精 对复杂问题，应设计一些子目标作过滤，逐步细化。3、模块化 把程序总目标分解成分目标，再进一步分解成具体的小目标，每个小目标称为一个模块。1612.2.2 结构化程序的基本结构和特点 采用结构化程序设计方法编写程序，可使程序结构良好、易读、易理解、易维护。 结构化程序有三种基本结构，即顺序、选择和重复结构。1、顺序结构AB结构化程序设计的3种基本结构是（）A）顺序、选择、重复B）递归、嵌套、调用C）过程、子过程、主程序D）顺序、转移、调用1622、选择结构AB真假1633、重复结构 重复结构又叫循环结构。 循环结构又分：当型循环结构和直到型循环结构。A真假当型循环结构A真假直到型循环结构1642.3 面向对象的程序设计2.3.1 关于面向对象方法 面向对象方法的本质，就是主张从客观世界固有的事物出发来构造系统，提倡用人类在现实生活中常用的思维方法来认识、理解和描述客观事物。 面向对象方法的主要优点如下：1、与人类习惯的思维方法一致。2、稳定性好 因为面向对象的软件系统的结构是根据问题领域的模型建立起来的，而不是基于对系统应完成的功能来分解的，所以，当对系统的功能需要变化时并不会引起软件结构的整体变化，往往仅需要作一些局部性的修改。165 由于现实世界中的实体是相对稳定的，因此，以对象为中心构造的软件系统也是比较稳定的。3、可重用性好 软件重用是指在不同的软件开发过程中重复使用相同或相似软件元素的过程。 在面向对象方法中所使用的对象，由于对象所固有的封装性，使得对象的内部实现与外界隔离，从而具有较强的独立性。对象提供了比较理想的模块化机制和比较理想的可重用的软件成分。166 有两种方法重复使用一个对象类： （1）创建该类的实例，从而直接使用它。 （2）从它派生出一个满足当前需要的新类。4、易于开发大型软件产品5、可维护性好面向对象的程序设计主要考虑的是提高软件的（）A）可靠性 B） 可重用性C）可移植性 D）可修改性对象是显示世界中一个实际存在的事物，它可以是有形的也可以是无形的，下面所列举的不是对象的是（）A）桌子 B）飞机D）狗 D）苹果的颜色对象是构成客观世界的一个独立单位，它具有自己的静态特征（属性）和动态特征（行为或功能）1672.3.2 面向对象方法的基本概念1、对象（object） 对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它是由一组表示其静态特征的属性和它可执行的一组操作封装而成的。2、类和实例 将属性、操作相似的对象归为类，也就是说，类是具有共同属性、共同方法的对象的集合。类是对象的抽象，对象是类的一个实例。下面对对象概念描述不正确的是A）任何对象都必须有继承性B）对象是属性和方法的封装体C）对象的通信靠消息传递D）操作是对象的动态属性类是一个支持继承的抽象数据类型，而对象是类的。1683、消息 面向对象的世界是通过对象与对象间彼此的相互合作来推动的，对象间的这种相互合作需要一个机制协助进行，这样的机制称为“消息”。发送对象接口 接受对象消息操作名、参数在面向对象方法中，信息隐蔽是通过对象的性来实现的在面向对象方法中，一个对象请求另一对象为其服务的方式是通过发送实现的。169 4、继承 继承是使用已有的类定义作为基础建立新类的定义技术。 可以部分继承、也可以全部继承。5、多态性 对象根据接受的消息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。 在面向对象的方法出现以前我们都是采用面向（C）的程序设计方法。A）用户 B）结构C）过程 D）以上都不对面向对象的开发方法中，类与对象的关系是（ ）A）具体与抽象 B）抽象与具体 C）整体与部分 D）部分与整体面向对象的 程序设计主要考虑的是提高软件的（ ）A）可靠性 B）可重用性 C）可移植性 D）可修改性170