a公共基础—ACCESS培训讲义课件

大家好大家好12014.3全国计算机等级考试全国计算机等级考试二级二级ACCESS培训讲义培训讲义2数据结构与算法数据结构与算法程序设计基础程序设计基础软件工程基础软件工程基础数据库设计基础数据库设计基础考试主要内容3公共基础知识公共基础知识（四个部分（四个部分（四个部分（四个部分30%30%）记忆为主，理解推导为辅记忆为主，理解推导为辅4一、基本数据结构与算法一、基本数据结构与算法5本部分主要内容本部分主要内容v算法算法 v数据结构数据结构 数据结构研究的主要内容数据结构研究的主要内容 基本概念和术语基本概念和术语 数据结构类型数据结构类型 线性结构和非线性结构线性结构和非线性结构 顺序存储与链式存储顺序存储与链式存储 线性表线性表 栈和队列栈和队列 线性链表线性链表 树与二叉树树与二叉树 查找和排序查找和排序 图图 61.1 1.1 算法算法v算法的基本概念算法的基本概念算法的基本概念算法的基本概念 （重点）（重点）（重点）（重点）算法：解题方案的准确而完整的描述算法：解题方案的准确而完整的描述。算法的基本特征：算法的基本特征：是一组严谨地定义运算顺序的规则，是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。下终止。算法不等于程序，程序不可能优于算法算法不等于程序，程序不可能优于算法。基本特性基本特性 可行性：可行性：根据实际问题设计的算法，执行得到满意结果根据实际问题设计的算法，执行得到满意结果 确定性：确定性：每一步骤必须有明确定义，不允许有多义性。每一步骤必须有明确定义，不允许有多义性。有穷性：有穷性：算法必须能在有限的时间内做完。算法必须能在有限的时间内做完。拥有足够的情报拥有足够的情报:输入和输出必须拥有足够的情报，方可输入和输出必须拥有足够的情报，方可执行。执行。71.1 1.1 算法算法v算法的基本要素算法的基本要素（了解）（了解）1.1.对数据对象的运算和操作对数据对象的运算和操作 算术运算：、算术运算：、等等 逻辑运算：逻辑运算：、=、=1k1，则则该该结结点点的的父父结结点点的编号为的编号为INT(k/2)INT(k/2)。若若2kn2kn，则则结结点点k k的的左左子子结结点点编编号号为为2k2k；否否则则该该结结点点无无左左子子结结点点（显显然然也没有右子结点）。也没有右子结点）。若若2k+1n2k+1n，则结点，则结点k k的右子结点编号为的右子结点编号为2k+12k+1；否则该结点无右子结点。；否则该结点无右子结点。该性质注意以特殊推导一般该性质注意以特殊推导一般42 3 16 78910 11 12 13 14 15 51.3.6 树与二叉树树与二叉树例如结点例如结点6 6，其父结点为，其父结点为3 3，左，左子结点为子结点为1212，左子结点为，左子结点为1313(了解了解)82一般情况下一般情况下(规律规律)：1 1、任意二叉树总结点数：、任意二叉树总结点数：n=n0+n1+n2n=n0+n1+n22 2、任意二叉树中总有：、任意二叉树中总有：n0=n2+1n0=n2+13 3、任意完全二叉树中总有：、任意完全二叉树中总有：n1=0n1=0或或n1=1n1=1831.3.6 树与二叉树树与二叉树v二叉树的存储结构二叉树的存储结构 (了解了解)A AB BC CD DE EF FG GH HI I123456789A AB BC CGGE EI ID DHHF FT0T0一一般不用般不用一、顺序存储结构一、顺序存储结构按二叉树的结点按二叉树的结点“自上而自上而下、从左至右下、从左至右”编号，用编号，用一组连续的存储单元存储。一组连续的存储单元存储。84讨论：讨论：不是完全二叉树怎么办？不是完全二叉树怎么办？答：答：一律转为完全二叉树！一律转为完全二叉树！方法很简单，将各层空缺处统统补上方法很简单，将各层空缺处统统补上“虚结点虚结点”，其内容为空。，其内容为空。A AB B C C D D E E123456789.16ABECD缺点：缺点：浪费空间；浪费空间；插入、删除不便插入、删除不便 85链式存储结构链式存储结构datalChildrChild二叉链表lChild data rChild含两个指针域的结点结构含两个指针域的结点结构v结点包含数据域和左、右结点包含数据域和左、右孩子结点的指针域孩子结点的指针域Note:含有含有n个结点的个结点的二叉链表中有二叉链表中有n+1个空个空链域。链域。86rootABCDFE二叉树 ABCDFEroot二叉链表87遍历定义遍历定义指按某条搜索路线遍访每个结点且不重复指按某条搜索路线遍访每个结点且不重复（又称周游）。（又称周游）。遍历用途遍历用途它是树结构插入、删除、修改、查找和排序它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和运算的前提，是二叉树一切运算的基础和核心。核心。遍历方法遍历方法牢记一种约定，对每个结点的查看都是牢记一种约定，对每个结点的查看都是“先先左后右左后右”。二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历 1.3.6 树与二叉树树与二叉树(重点重点)88二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历 遍遍历历是是指指按按某某条条搜搜索索路路线线寻寻访访树树中中每每个个结结点点，且且每每个个结结点点只只被访问一次。被访问一次。按先左后右的原则，一般使用三种遍历：按先左后右的原则，一般使用三种遍历：先序遍历先序遍历(D L R):(D L R):访问根结点，按先序遍历左子树，按先序遍历右子树。访问根结点，按先序遍历左子树，按先序遍历右子树。中序遍历中序遍历(L D R):(L D R):按中序遍历左子树，访问根结点，按中序遍历右子树。按中序遍历左子树，访问根结点，按中序遍历右子树。后序遍历后序遍历(L R D):(L R D):按后序遍历左子树，按后序遍历右子树，访问根结点。按后序遍历左子树，按后序遍历右子树，访问根结点。二叉树为空时，执行空操作，即空二叉树已遍历完。二叉树为空时，执行空操作，即空二叉树已遍历完。891.3.6 树与二叉树树与二叉树(重点重点)ABCDEFGH000000000beginend先序遍历顺序先序遍历顺序:A B D F G C E HABDFGCEH先序遍历演示先序遍历演示DLRDLR先序遍历，即先根再左再右先序遍历，即先根再左再右90ABCDEFGH000000000beginend中序遍历顺序中序遍历顺序:ABDFGC E HBFDGACEH中序遍历演示中序遍历演示LDRLDR中序遍历，即先左再根再右中序遍历，即先左再根再右91ABCDEFGH000000000beginend后序遍历顺序后序遍历顺序:F G D B H E C AABDFGCEH后序遍历演示后序遍历演示LRDLRD后序遍历，即先左再右再根后序遍历，即先左再右再根92前序序列前序序列:A,B,D,E,J,C,F,I,G中序序列中序序列:D,B,J,E,A,F,I,C,G后序序列后序序列:D,J,E,B,I,F,G,C,A前序序列前序序列:A,B,D,E,J,C,F,I,G中序序列中序序列:D,B,J,E,A,F,I,C,GABCDEFGIJ由遍历序列恢复二叉树由遍历序列恢复二叉树93前序序列前序序列:A,B,D,E,J,C,F,I,G中序序列中序序列:D,B,J,E,A,F,I,C,GAD,B,J,EF,I,C,G前序序列前序序列:A,B,D,E,J,C,F,I,G中序序列中序序列:D,B,J,E,A,F,I,C,GAF,I,C,GBJ,ED前序序列前序序列:A,B,D,E,J,C,F,I,G中序序列中序序列:D,B,J,E,A,F,I,C,GAF,I,C,GBDEJ94后序序列后序序列:D,J,E,B,I,F,G,C,A 规律规律(前前,中中):):在前序序列中找根在前序序列中找根;到中序序列中分左右。到中序序列中分左右。规律规律(中中,后后):):在后序序列中找根在后序序列中找根;到中序序列中分左右到中序序列中分左右。ABCDEFGIJ95961 1、已知一棵二叉树前序遍历和中序遍历分别为、已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFHABDEGCFH和和DBGEACHFDBGEACHF，则该二叉树的后序遍历为（，则该二叉树的后序遍历为（）A)GEDHFBCA A)GEDHFBCA B)DGEBHFCA B)DGEBHFCA C)ABCDEFGH C)ABCDEFGH D)ACBFEDHG D)ACBFEDHG 2 2、树是结点的集合，它的根结点数目是（、树是结点的集合，它的根结点数目是（）A)A)有且只有有且只有1 B)11 B)1或多于或多于1 C)01 C)0或或1 1D)D)至少至少2 2 3 3、在深度为、在深度为5 5的满二叉树中，叶子结点的个数为（的满二叉树中，叶子结点的个数为（）A)32A)32 B)31 C)16 B)31 C)16 D)15 D)15 4 4、下列叙述中正确的是（、下列叙述中正确的是（）A)A)线性表是线性结构线性表是线性结构B)B)栈与队列是非线性结构栈与队列是非线性结构 C)C)线性链表是非线性结构线性链表是非线性结构D)D)二叉树是线性结构二叉树是线性结构 过关练习过关练习BCCA975 5、具有、具有3 3个结点的二叉树有（个结点的二叉树有（）A)2A)2种形态种形态 B)4B)4种形态种形态 C)7C)7种形态种形态 D)5D)5种形态种形态 6 6、设有下列二叉树、设有下列二叉树,其前序遍历的结果为（其前序遍历的结果为（）A)ZBTTCPXA B)ATBZXCTP C)ZBTACTXP D)ATBZXCPT A)ZBTTCPXA B)ATBZXCTP C)ZBTACTXP D)ATBZXCPT 7 7、一棵二叉树中，共有、一棵二叉树中，共有7070个叶子结点与个叶子结点与8080个度为个度为1 1的结点，则的结点，则其总结点为（其总结点为（）。）。A)219 A)219 B)221 C)229 D)231 B)221 C)229 D)231DBA988 8、设一棵二叉树中有、设一棵二叉树中有3 3个叶子结点，有个叶子结点，有8 8个度为个度为1 1的结点，则该的结点，则该二叉树中总的结点数为（二叉树中总的结点数为（）A)12 A)12 B)13 C)14 D)15 B)13 C)14 D)15 9 9、设有下列二叉树，中序遍历的结果为（、设有下列二叉树，中序遍历的结果为（）A)ABCDEF B)DBEAFC C)ABDECF D)DEBFCAA)ABCDEF B)DBEAFC C)ABDECF D)DEBFCABB99v查找：查找：在一个给定的数据结构中，根据给定的条件找在一个给定的数据结构中，根据给定的条件找到满足条件的结点。不同的数据结构采用不同的查找方到满足条件的结点。不同的数据结构采用不同的查找方法。查找的效率直接影响数据处理的效率。法。查找的效率直接影响数据处理的效率。v平均查找长度：平均查找长度：查找过程中比较的次数查找过程中比较的次数 v查找的结果查找的结果 查找成功：查找成功：找到满足条件的结点找到满足条件的结点 查找失败：查找失败：找不到满足条件的结点。找不到满足条件的结点。1.3.7 查找和排序查找和排序100v顺序查找（线性查找）顺序查找（线性查找）对给定的一关键字对给定的一关键字K K，从线性表的一端开始，逐个进行记录，从线性表的一端开始，逐个进行记录的关键字和的关键字和K K的比较，直到找到关键字等于的比较，直到找到关键字等于K K的记录或到达表的另的记录或到达表的另一端。一端。可以采用从前向后查，也可采用从后向前查的方法。可以采用从前向后查，也可采用从后向前查的方法。在平均情况下，大约要与表中一半以上元素进行比较，效在平均情况下，大约要与表中一半以上元素进行比较，效率较低。最坏情况下需要比较率较低。最坏情况下需要比较n n次。次。时间复杂度时间复杂度O(n)O(n)或或 n n在下面两种情况下只能采取顺序查找：在下面两种情况下只能采取顺序查找：线性表为无序表（元素排列是无序的）；线性表为无序表（元素排列是无序的）；即使是有序线性表，但采用的是链式存储结构。即使是有序线性表，但采用的是链式存储结构。1.3.7 查找和排序查找和排序(重点重点)101折半查找（二分法查找）折半查找（二分法查找）v思想：思想：先确定待查找记录所在的范围，然后逐步缩小范围，先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。直到找到或确认找不到该记录为止。v前提：前提：必须在具有顺序存储结构的必须在具有顺序存储结构的有序表中进行有序表中进行。v分三种情况：分三种情况：中间项中间项mid=(low+high)/2mid=(low+high)/2不进位取整不进位取整若中间项的值等于若中间项的值等于x,x,则说明已查到。则说明已查到。若若x x小于中间项的值，则在线性表的前半部分查找；小于中间项的值，则在线性表的前半部分查找；若若x x大于中间项的值，则在线性表的后半部分查找。大于中间项的值，则在线性表的后半部分查找。v特点：特点：比顺序查找方法效率高。最坏的情况下，需要比较比顺序查找方法效率高。最坏的情况下，需要比较 loglog2 2n n次次。1.3.7 查找和排序查找和排序(重点重点)102折半查找（二分法查找）算法折半查找（二分法查找）算法 假设查找表存放在数组假设查找表存放在数组a a的的a1a1anan中，且升序，查找关中，且升序，查找关键字值为键字值为k k。折半查找的主要步骤为：。折半查找的主要步骤为：（1 1）置初始查找范围：）置初始查找范围：low=1low=1，high=n;high=n;（2 2）求查找范围中间项：）求查找范围中间项：mid=(low+high)/2 mid=(low+high)/2（3 3）将指定的关键字值）将指定的关键字值k k与中间项与中间项amid.keyamid.key比较。比较。若相等，查找成功，找到的数据元素为此时若相等，查找成功，找到的数据元素为此时mid mid 指向的位置；指向的位置；若小于，查找范围的低端数据元素指针若小于，查找范围的低端数据元素指针lowlow不变，高端数据元素指针不变，高端数据元素指针highhigh更新为更新为mid-1;mid-1;若大于，查找范围的高端数据元素指针若大于，查找范围的高端数据元素指针highhigh不变，低端数据元素指针不变，低端数据元素指针lowlow更新为更新为mid+1;mid+1;（4 4）重复步骤（）重复步骤（2 2）、（）、（3 3）直到查找成功或查找范围空（）直到查找成功或查找范围空（lowhighlowhigh），即查），即查找失败为止。找失败为止。（5 5）如果查找成功，返回找到元素的存放位置，即当前的中间项位置指针）如果查找成功，返回找到元素的存放位置，即当前的中间项位置指针midmid；否则返回查找失败标志；否则返回查找失败标志。103查找查找2323的过程如下图的过程如下图:mid=(low+high)/2不进位取整不进位取整(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)lowhighmid(08,14,23,37,46,55,68,79,91)lowhigh=mid-1mid(08,14,23,37,46,55,68,79,91)low=mid+1highmid折半查找（二分法查找）算法折半查找（二分法查找）算法(重点重点)104 排序的功能：排序的功能：将一个数据元素（或记录）的任将一个数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列。意序列，重新排成一个按关键字有序的序列。排序过程的组成步骤排序过程的组成步骤 1 1、首先比较两个关键字的大小；、首先比较两个关键字的大小；2 2、然后将记录从一个位置移动到另一个位置。、然后将记录从一个位置移动到另一个位置。1.3.7 查找和排序查找和排序堆排序堆排序起泡排序起泡排序排序方法排序方法插入排序插入排序选择排序选择排序交换排序交换排序归并排序归并排序直接、折半插入排序直接、折半插入排序希尔排序希尔排序简单选择排序简单选择排序快速排序快速排序(重点重点)105插入排序插入排序 1 1、直接插入排序、直接插入排序:基本思想：从数组的第基本思想：从数组的第2 2号元素开始，顺序从数组中取出号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位元素，并将该元素插入到其左端已排好序的数组的适当位置上。置上。需要需要n(n-1)/2n(n-1)/2次比较次比较【例例】打扑克牌时的抓牌就是插入排序一个很好的例子，每打扑克牌时的抓牌就是插入排序一个很好的例子，每抓一张牌，插入到合适位置，直到抓完牌为止，即可得到一抓一张牌，插入到合适位置，直到抓完牌为止，即可得到一个有序序列。个有序序列。106该该算算法法适适合合于于n 较较小小的的情情况况，时时间间复复杂度为杂度为O(n2).待排元素序列：待排元素序列：53 27 36 15 69 42第一次排序：第一次排序：27 53 36 15 69 42第二次排序：第二次排序：27 36 53 15 69 42第三次排序：第三次排序：15 27 36 53 69 42第四次排序：第四次排序：15 27 36 53 69 42第五次排序：第五次排序：15 27 36 42 53 69 直接插入排序示例直接插入排序示例对于有对于有n个数个数据元素的待排据元素的待排序列，插入操序列，插入操作要进行作要进行n-1次次107 交换排序的特点在于交换，有冒泡和快速排序两种交换排序的特点在于交换，有冒泡和快速排序两种。冒泡排序（起泡排序）冒泡排序（起泡排序）思想思想：小的浮起，大的沉底。从左端开始比较。小的浮起，大的沉底。从左端开始比较。第第一一趟趟：第第1 1个个与与第第2 2个个比比较较，大大则则交交换换；第第2 2个个与与第第3 3个个比比较，大则交换，较，大则交换，关键字最大的记录交换到最后一个位置上；关键字最大的记录交换到最后一个位置上；则第一趟需比较交换的元素对有则第一趟需比较交换的元素对有n-1n-1组组 第第二二趟趟：对对前前n-1n-1个个记记录录进进行行同同样样的的操操作作，关关键键字字次次大大的的记记录交换到第录交换到第n-1n-1个位置上；个位置上；依次类推，则完成排序。依次类推，则完成排序。1.3.7 交换排序交换排序(重点重点)108第第六六趟趟排排序序后后第第五五趟趟排排序序后后第第四四趟趟排排序序后后第第三三趟趟排排序序后后第第二二趟趟排排序序后后第第一一趟趟排排序序后后初初始始关关键键字字思思想想：小小的的浮浮起起，大大的的沉底。沉底。4936416511783665364156364165413641561178363641491156492525251149495611111125252525109快速排序快速排序 (对冒泡排序的改进）对冒泡排序的改进）思思想想：通通过过一一趟趟排排序序将将待待排排序序列列分分成成两两部部分分，使使其其中中一一部部分分记记录录的的关关键键字字均均比比另另一一部部分分小小，再再分分别别对对这这两两部部分分排排序序，以以达到整个序列有序。达到整个序列有序。关键字通常取关键字通常取第一个记录的值第一个记录的值为基准值。为基准值。110具体做法具体做法 附设两个指针附设两个指针lowlow和和highhigh，初值分别指向第一个记录和，初值分别指向第一个记录和最后一个记录，设枢轴为最后一个记录，设枢轴为 keykey；(1)(1)从从high high 所指位置起向前搜索，找到第一个不大于基所指位置起向前搜索，找到第一个不大于基准值的记录与枢轴记录相互交换；准值的记录与枢轴记录相互交换；(2)(2)从从low low 所指位置起向后搜索，找到第一个不小于基所指位置起向后搜索，找到第一个不小于基准值的记录与枢轴记录相互交换。准值的记录与枢轴记录相互交换。(3)(3)重复这两步直至重复这两步直至low=highlow=high为止。为止。1112121（21 03 37 13 91 09 21 03 37 13 91 09）lowlowhighhigh枢轴枢轴2121（09 03 1309 03 13 21 21 91 3791 37 ）2121（09 03 09 03 13 13 91 3791 37 ）lowlowhighhigh枢轴枢轴 2121highhigh枢轴枢轴（21 21 03 37 13 91 09 03 37 13 91 09）lowlow09092121（0909 0303 37 13 37 13 9191 ）lowlow枢轴枢轴highhigh 3737 lowlowhighhighlowlow1313112 堆是具有特定条件的顺序存储的完全二叉树。堆是具有特定条件的顺序存储的完全二叉树。其其特特定定条条件件是是：任任何何一一个个非非叶叶子子结结点点的的关关键键字字大大于于等等于于（或小于等于）子女的关键字的值。（或小于等于）子女的关键字的值。(1)(1)堆的示例堆的示例(a):堆顶元素取最大值堆顶元素取最大值(b):堆顶元素取最小值堆顶元素取最小值堆排序也是一种选择排序。堆排序也是一种选择排序。堆排序的时间复杂度为堆排序的时间复杂度为O(nlogO(nlog2 2n)n)113堆排序的一般步骤堆排序的一般步骤（以结果为非递减序列为例）以结果为非递减序列为例）将待排序序列将待排序序列Rl.nRl.n看成是一棵完全二叉树的顺序存储看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，创建对应的完全二叉树；在关系，创建对应的完全二叉树；将第将第步创建的完全二叉树调整为小根堆；步创建的完全二叉树调整为小根堆；利用小根堆的特性，从堆中提取最小值并删除根；利用小根堆的特性，从堆中提取最小值并删除根；重新调整删除根的堆为新堆，重复第重新调整删除根的堆为新堆，重复第步直到堆的长度步直到堆的长度为零；为零；将每次提取的根依次排列即为有序序列。将每次提取的根依次排列即为有序序列。114【例例】用堆排序将序列用堆排序将序列 20,60,26,30,36,10 调整调整为递增序列。为递增序列。构建小根堆；构建小根堆；提取堆顶并调整删除堆顶后的元素为新堆；提取堆顶并调整删除堆顶后的元素为新堆；重复第重复第2步，直至堆空。步，直至堆空。每次提取的堆顶依次排列即为递增序列。每次提取的堆顶依次排列即为递增序列。115将序列将序列 20,60,26,30,36,10 构建小根堆；构建小根堆；202660103630201060263630201030263660102030263660116102030263660输出输出 102620303660202630366020263036603626306026363060输出输出 20102030263660小根堆的递增输出序列小根堆的递增输出序列117303660输出输出 3036603660输出输出 36输出输出 6060递增输出序列为：递增输出序列为：10 20 26 30 36 6026363060603630303660输出输出 26118各种排序法比较各种排序法比较(重点重点)1191 1、假设线性表的长度为、假设线性表的长度为n n，则在最坏情况下，冒泡排序需要的，则在最坏情况下，冒泡排序需要的比较次数为（比较次数为（）A)logA)log2 2n n B)n B)n2 2 C)O(n1.5)C)O(n1.5)D)n(n-1)/2 D)n(n-1)/2 2 2、最简单的交换排序方法是（、最简单的交换排序方法是（）A)A)快速排序快速排序 B)B)选择排序选择排序 C)C)堆排序堆排序 D)D)冒泡排序冒泡排序 3 3、对长度为、对长度为n n的线性表进行顺序查找，在最坏的情况下所需要的线性表进行顺序查找，在最坏的情况下所需要的比较次数为（的比较次数为（）)n+1 B)n C)(n+1)/2 D)n/2)n+1 B)n C)(n+1)/2 D)n/2 过关练习过关练习DDB1204 4、下列数据结构中，能用二分法进行查找的是（、下列数据结构中，能用二分法进行查找的是（）A)A)顺序存储的有序线性表顺序存储的有序线性表 B)B)线性链表线性链表 C)C)二叉链表二叉链表 D)D)有序线性链表有序线性链表 5 5、在对、在对n n个元素进行冒泡排序的过程中，第一趟至多需要进行个元素进行冒泡排序的过程中，第一趟至多需要进行（）对相邻元素之间的比较。）对相邻元素之间的比较。A)n/2A)n/2 B)n-1 C)n B)n-1 C)n D)n+1D)n+1 过关练习过关练习AB1211.3.8 图图v图的基本概念图的基本概念图的基本概念图的基本概念 图：节点图：节点(图中称顶点图中称顶点)间的连接是任意的。间的连接是任意的。图的分类：图的分类：有向图、无向图有向图、无向图n n个顶点的连通图中边的条数至少为个顶点的连通图中边的条数至少为n n条条(重点重点)v2v1v3v4e1e2e3e4e5v2v1v3v4a1a2a3a4a5122v算法的四个基本特征（可行性、确定性、有穷性、有足够情报）算法的四个基本特征（可行性、确定性、有穷性、有足够情报）v算法的复杂度（时间复杂度、空间复杂度），衡量的标准是什么？算法的复杂度（时间复杂度、空间复杂度），衡量的标准是什么？v数据结构研究的三个方面（数据逻辑结构、存储结构、基本运算）数据结构研究的三个方面（数据逻辑结构、存储结构、基本运算）v数据结构逻辑分类（线性、非线性）、存储结构分类（顺序存储、链式存数据结构逻辑分类（线性、非线性）、存储结构分类（顺序存储、链式存储）储）v线性结构：栈、队列、循环队列的基本结构，操作方式，特点线性结构：栈、队列、循环队列的基本结构，操作方式，特点 v链式存储：单链、双向链、循环链表的结构，基本操作链式存储：单链、双向链、循环链表的结构，基本操作 v二叉树：定义，满二叉树与完全二叉树的定义与对比二叉树：定义，满二叉树与完全二叉树的定义与对比 v二叉树的三种遍历算法：先序、中序、后序二叉树的三种遍历算法：先序、中序、后序 v查找技术：二分查找法的基本运算过程，时间复杂度多少？查找技术：二分查找法的基本运算过程，时间复杂度多少？v排序技术：交换、插入排序的基本算法，时间复杂度多少？排序技术：交换、插入排序的基本算法，时间复杂度多少？本章重难点分析本章重难点分析1232 2、程序设计基础、程序设计基础124本部分主要内容本部分主要内容v程序设计方法和风格程序设计方法和风格 v结构化程序设计结构化程序设计 v面向对象程序设计面向对象程序设计 125v什么是程序什么是程序 指令的集合。（解释指令）指令的集合。（解释指令）通过硬件控制系统自动完成某一功能。通过硬件控制系统自动完成某一功能。通过一系列代码实现。通过一系列代码实现。v程序设计的风格程序设计的风格l 总体而言，应该强调简单和清晰，程序必须是可以理总体而言，应该强调简单和清晰，程序必须是可以理解的。解的。l 著名的著名的“清晰第一，效率第二清晰第一，效率第二”的论点成为当今主导的论点成为当今主导的程序设计风格的程序设计风格2.1 2.1 程序设计方法和风格程序设计方法和风格126软件设计及软件工程基础软件设计及软件工程基础v程序设计风格程序设计风格 编写程序时所表现出来的特点、习惯和逻辑思路。一般从编写程序时所表现出来的特点、习惯和逻辑思路。一般从以下四部分加以规范：以下四部分加以规范：源程序文档化：源程序文档化：选择有含义的符号名字、注释（序言性和选择有含义的符号名字、注释（序言性和功能性注释）、程序的视觉组织。功能性注释）、程序的视觉组织。数据说明：数据说明：显式地说明一切变量、数据说明的次序应该规显式地说明一切变量、数据说明的次序应该规范化、便于查找变量（按顺序排列）、对复杂数据结构应范化、便于查找变量（按顺序排列）、对复杂数据结构应注释说明注释说明 语句的结构：语句的结构：每条语句简单明了、尽量不用或少用每条语句简单明了、尽量不用或少用GOTOGOTO语语句、尽量只采用句、尽量只采用3 3种基本控制结构编程种基本控制结构编程 输入和输出：输入和输出：对所有输入数据进行校验和合理性检查、输对所有输入数据进行校验和合理性检查、输入输出格式保持一致、设计良好的输出报表入输出格式保持一致、设计良好的输出报表2.1 2.1 程序设计方法和风格程序设计方法和风格位于源程序位于源程序模块内部模块内部一般位于模块的一般位于模块的首部，用于说明首部，用于说明模块的相关信息模块的相关信息127v基本思想基本思想 结构化程序设计的主要思想是功能分解并逐步求精。当结构化程序设计的主要思想是功能分解并逐步求精。当一些任务十分复杂不易描述时，可以将它拆分为一系列较小的一些任务十分复杂不易描述时，可以将它拆分为一系列较小的功能部件，直到这些子任务小到易于理解和实现的程度。功能部件，直到这些子任务小到易于理解和实现的程度。结构化程序的特点：程序结构仅由顺序、选择和循环结构化程序的特点：程序结构仅由顺序、选择和循环3 3种结种结构复合而成。构复合而成。v设计原则设计原则 自顶向下自顶向下 逐步求精逐步求精 模块化模块化 限制使用限制使用gotogoto语句语句2.2 2.2 结构化程序设计结构化程序设计128S1NS流程图流程图输入输入100个数存入个数存入X1，x2,x100打印打印x1.x100中中不等于不等于0的数的数让让x1，x2,x100中的非素变为中的非素变为0S3S2输入输入xi当当i=100i=i+1i=1S1细化细化xi0当当i=100i=i+1i=1YN打印打印xiS3细化细化例：给例：给100100个整数，打印输出其中的素数个整数，打印输出其中的素数129S1NS流程图流程图输入输入100个数存入个数存入X1，x2,x100打印打印x1.x100中中不等于不等于0的数的数让让x1，x100中的中的非素变为非素变为0S3S2S2细化细化判断判断xi是否是素数，是否是素数，若不是则将若不是则将xi=0当当i=100i=i+1i=1S21r=0rxi/2S21细化细化130输入输入100个数存入个数存入X1，x2,x100打印打印x1.x100中中不等于不等于0的数的数让让x1，x100中中的非素变为的非素变为0细化后的流程图细化后的流程图输入输入xi当当i=100i=i+1i=1当当ixi/2i=i+1xi0当当i=100i=1YN打印打印xii=i+1131v基本结构：顺序、选择、循环基本结构：顺序、选择、循环 2.2 2.2 结构化程序设计结构化程序设计1322.3 2.3 面向对象程序设计面向对象程序设计v基本思想基本思想 客观世界中任何一个事物都可以被看成是一个对象，面向客观世界中任何一个事物都可以被看成是一个对象，面向对象方法的本质就是主张从客观世界固有的事物出发来构造系对象方法的本质就是主张从客观世界固有的事物出发来构造系统，系统中的对象及对象之间的关系能够如实地反映问题域中统，系统中的对象及对象之间的关系能够如实地反映问题域中固有的事物及其关系。固有的事物及其关系。面向对象的程序设计（面向对象的程序设计（Object-Oriented ProgrammingObject-Oriented Programming，OOOO是一种把面向对象的思想应用于软件开发过程中，指导开发是一种把面向对象的思想应用于软件开发过程中，指导开发活动的系统方法，简称活动的系统方法，简称OOOO方法，它是建立在对象概念（对象、方法，它是建立在对象概念（对象、类和继承）基础上的方法。类和继承）基础上的方法。133v主要优点主要优点主要优点主要优点 与人类习惯的思维方法一致与人类习惯的思维方法一致 稳定性好稳定性好 可重用性好可重用性好 易于开发大型软件产品易于开发大型软件产品 可维护性好可维护性好2.3 2.3 面向对象程序设计面向对象程序设计面向对象程序设计主要考虑的是面向对象程序设计主要考虑的是提高软件的可重用性！提高软件的可重用性！1342.3 2.3 面向对象程序设计面向对象程序设计v几个术语：几个术语：对象：对象：在现实世界中，每个实体都是对象，例如，大学生、汽在现实世界中，每个实体都是对象，例如，大学生、汽车、电视机、空调等都是现实世界中的对象车、电视机、空调等都是现实世界中的对象属性：属性：通常是一些数据，有时它也可以是另一个对象通常是一些数据，有时它也可以是另一个对象事件：事件：是由对象识别的一个动作，用户可以编写相应代码对此是由对象识别的一个动作，用户可以编写相应代码对此动作进行响应动作进行响应方法方法：对象中的属性只能通过该对象所提供的操作来存取或修对象中的属性只能通过该对象所提供的操作来存取或修改改1352.3 2.3 面向对象程序设计面向对象程序设计类类：类是一组具有相同属性和相同操作的对象的集合。类是一组具有相同属性和相同操作的对象的集合。基类基类：用来生成新类的类。用来生成新类的类。派生类派生类：由已存在的类派生出来的新类，也叫子类。由已存在的类派生出来的新类，也叫子类。继承继承:是指能够直接获得已有的性质和特征，而不必重复定义他是指能够直接获得已有的性质和特征，而不必重复定义他们。继承分单继承和多重继承。们。继承分单继承和多重继承。单继承单继承指一个类只允许有一个父指一个类只允许有一个父类，类，多重继承多重继承指一个类允许有多个父类指一个类允许有多个父类多态性多态性:是指同样的消息被不同的对象接受时可导致完全不同的是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。行动的现象。136137封装封装(Encapsulation)(Encapsulation)将数据和操作数据的函数衔接在一起，构成一个具有类将数据和操作数据的函数衔接在一起，构成一个具有类类型的对象的描述。类型的对象的描述。对象的内部实现受保护，外界不能访问对象的内部实现受保护，外界不能访问 封装简化了程序员对对象的使用封装简化了程序员对对象的使用 2.3 2.3 面向对象程序设计（面向对象程序设计（应该注意的概念应该注意的概念应该注意的概念应该注意的概念）类类(Class)(Class)一个类定义了一组大体上相似的对象。一个类定义了一组大体上相似的对象。一个类所包含的方法和数据描述一组对象的共同行为和一个类所包含的方法和数据描述一组对象的共同行为和属性。属性。类是在对象之上的抽象，对象是类的具体化，是类的实类是在对象之上的抽象，对象是类的具体化，是类的实例例 138消息消息(Message)(Message)对象之间进行通信的一种数据构造。对象之间进行通信的一种数据构造。消息是一个实例与另一个实例之间传递的信息消息是一个实例与另一个实例之间传递的信息2.3 2.3 面向对象程序设计（面向对象程序设计（应该注意的概念）应该注意的概念）应该注意的概念）应该注意的概念）对象对象(Object)(Object)对象是基本的运行时的实体，它既包括数据（属性），对象是基本的运行时的实体，它既包括数据（属性），也包括作用于数据的操作（行为）。也包括作用于数据的操作（行为）。一个对象把属性和行为封装为一个整体一个对象把属性和行为封装为一个整体 一个对象通常可由对象名、属性和操作一个对象通常可由对象名、属性和操作3 3部分组成部分组成 139继承继承(Inheritance)(Inheritance)继承是父类和子类之间共享数据的方法的机制继承是父类和子类之间共享数据的方法的机制 一个子类可以继承它的父类（或祖先类）中的属性和操一个子类可以继承它的父类（或祖先类）中的属性和操作作 子类中可以定义自己的属性和操作子类中可以定义自己的属性和操作 单重继承、多重继承单重继承、多重继承 ；且继承具有传递性；且继承具有传递性 水上交通工具水上交通工具陆上交通工具陆上交通工具水陆两用交通工具水陆两用交通工具 多多 重重 继继 承承 图图 2.3 2.3 面向对象程序设计（面向对象程序设计（应该注意的概念应该注意的概念应该注意的概念应该注意的概念）1401 1、结构化程序设计的结构化程序设计的3 3种结构是（种结构是（）A)A)顺序结构、选择结构、转移结构顺序结构、选择结构、转移结构 B)B)分支结构、等价结构、循环结构分支结构、等价结构、循环结构 C)C)多分支结构、赋值结构、等价结构多分支结构、赋值结构、等价结构 D)D)顺序结构、选择结构、循环结构顺序结构、选择结构、循环结构2 2、在设计程序时，应采纳的原则之一是（在设计程序时，应采纳的原则之一是（）A)A)不限制不限制gotogoto语句的使用语句的使用 B)B)减少或取消注解行减少或取消注解行 C)C)程序越短越好程序越短越好 D)D)程序结构应有助于读者理解程序结构应有助于读者理解3 3、结构化程序设计方法的结构化程序设计方法的3 3种基本控制结构中不包括种基本控制结构中不包括()。A A）循环结构）循环结构B B）递归结构）递归结构C C）顺序结构）顺序结构D D）选择结构）选择结构过关练习过关练习选择题选择题DDB1414 4、结构化程序设计主要强调的是（、结构化程序设计主要强调的是（）A)A)程序的规模程序的规模B)B)程序的效率程序的效率 C)C)程序设计语言的先进性程序设计语言的先进性 D)D)程序易读性程序易读性5 5、以下不属于对象的基本特点的是（、以下不属于对象的基本特点的是（）A)A)分类性分类性 B)B)多态性多态性 C)C)继承性继承性D)D)封装性封装性6 6、下面关于对象概念的描述中，错误的是下面关于对象概念的描述中，错误的是()。A A）对象就是）对象就是C C语言中的结构体变量语言中的结构体变量B B）对象代表着正在创建的系统中的一个实体）对象代表着正在创建的系统中的一个实体C C）对象是一个状态和操作）对象是一个状态和操作(或方法或方法)的封装体的封装体D D）对象之间的信息传递是通过消息进行的）对象之间的信息传递是通过消息进行的 过关练习过关练习选择题选择题DCA1427 7、对建立良好的程序设计风格，下面描述正确的是（、对建立良好的程序设计风格，下面描述正确的是（）A)A)程序应简单、清晰、可读性好程序应简单、清晰、可读性好 B)B)符号名的命名只要符合语法符号名的命名只要符合语法 C)C)充分考虑程序的执行效率充分考虑程序的执行效率 D)D)程序的注释可有可无程序的注释可有可无8 8、在结构化程序设计思想提出之前，在程序设计中曾强调程序的效率，现在，、在结构化程序设计思想提出之前，在程序设计中曾强调程序的效率，现在，与程序的效率相比，人们更重视程序的（与程序的效率相比，人们更重视程序的（）A)A)安全性安全性 B)B)一致性一致性 C)C)可理解性可理解性D)D)合理性合理性9 9、以下不是面向对象思想中的主要特征的是以下不是面向对象思想中的主要特征的是()。A A）多态）多态B B）继承）继承C C）封装）封装D D）类比性）类比性过关练习过关练习选择题选择题ACD1431010、下列叙述中，不属于结构化程序设计方法的主要原则的是（、下列叙述中，不属于结构化程序设计方法的主要原则的是（）A)A)自顶向下自顶向下 B)B)由底向上由底向上 C)C)模块化模块化D)D)限制使用限制使用gotogoto语句语句1111、对象实现了数据和操作的结合，是指对数据和数据的操作进行（对象实现了数据和操作的结合，是指对数据和数据的操作进行（）A)A)结合结合 B)B)隐藏隐藏 C)C)封装封装 D)D)抽象抽象1212、在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送、在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送（）A A）调用语句）调用语句 B B）命令）命令 C C）口令）口令 D D）消息）消息1313、以下叙述中，不属于面向对象方法的优点的是以下叙述中，不属于面向对象方法的优点的是()A A）可重用性好）可重用性好B B）与人类习惯的思维方法一致）与人类习惯的思维方法一致C C）可维护性好）可维护性好D D）有助于实现自顶向下、逐步求精）有助于实现自顶向下、逐步求精过关练习过关练习选择题选择题BCDD1441414、信息屏蔽的概念与下述哪一种概念直接相关（、信息屏蔽的概念与下述哪一种概念直接相关（）A A）软件结构定义）软件结构定义 B B）模块独立性）模块独立性C C）模块类型划分）模块类型划分 D D）模块偶合度）模块偶合度1515、下列对对象概念描述错误的是（、下列对对象概念描述错误的是（）A A）任何对象都必须有继承性）任何对象都必须有继承性B B）对象是属性和方法的封装体）对象是属性和方法的封装体C C）对象间的通讯靠消息传递）对象间的通讯靠消息传递D D）操作是对象的动态属性）操作是对象的动态属性1616、结构化程序设计主要强调的是结构化程序设计主要强调的是()。A A）程序的规模）程序的规模 B B）程序的效率）程序的效率C C）程序设计语言的先进性）程序设计语言的先进性D D）程序易读性）程序易读性过关练习过关练习选择题选择题BAD1451717、面向对象的设计方法与传统的面向过程的方法有本质的不同、面向对象的设计方法与传统的面向过程的方法有本质的不同,它的基本原理它的基本原理是（是（）A)A)模拟现实世界中不同事物之间的联系模拟现实世界中不同事物之间的联系 B)B)强调模拟现实世界中的算法而不强调概念强调模拟现实世界中的算法而不强调概念 C)C)使用现实世界的概念抽象地思考问题从而自然地解决问题使用现实世界的概念抽象地思考问题从而自然地解决问题 D)D)鼓励开发者在软件开发的绝大部分中都用实际领域的概念去思考鼓励开发者在软件开发的绝大部分中都用实际领域的概念去思考1818、下列叙述中正确的是下列叙述中正确的是()。A A）在面向对象的程序设计中，各个对象之间具有密切的联系）在面向对象的程序设计中，各个对象之间具有密切的联系B B）在面向对象的程序设计中，各个对象都是公用的）在面向对象的程序设计中，各个对象都是公用的C C）在面向对象的程序设计中，各个对象之间相对独立，相互依赖性小）在面向对象的程序设计中，各个对象之间相对独立，相互依赖性小D D）上述三种说法都不对）上述三种说法都不对 CC1461919、在面向对象方法中，一个对象请求另一对象为其服务的方式是通过在面向对象方法中，一个对象请求另一对象为其服务的方式是通过发送发送()。A A）调用语句）调用语句B B）命令）命令C C）口令）口令D D）消息）消息2020、面向对象程序设计中程序运行的最基本实体是面向对象程序设计中程序运行的最基本实体是()。A A）对象）对象B B）类）类C C）方法）方法D D）函数）函数2121、下列选项中不属于结构化程序设计方法的是下列选项中不属于结构化程序设计方法的是()。A A）自顶向下）自顶向下B B）逐步求精）逐步求精C C）模块化）模块化D D）可复用）可复用2222、在设计程序时，应采纳的原则之一是在设计程序时，应采纳的原则之一是()。A A）不限制）不限制gotogoto语句的使用语句的使用 B B）减少或取消注解行）减少或取消注解行C C）程序越短越好）程序越短越好 D D）程序结构应有助于读者理解）程序结构应有助于读者理解DADD1473 3 软件工程基本软件工程基本148v软件的定义软件的定义软件的定义软件的定义 软件软件(software)(software)是计算机系统中与硬件是计算机系统中与硬件(hardware)(hardware)相互依相互依存的另一部分。软件包括三个部分：程序存的另一部分。软件包括三个部分：程序(program)(program)、相关数、相关数据据(data)(data)、说明文档、说明文档(document)(document)。v软件的特点软件的特点软件的特点软件的特点 软件是一种逻辑实体，不是物理实体，具有抽象性。软件是一种逻辑实体，不是物理实体，具有抽象性。软件没有明显的制造过程。软件没有明显的制造过程。软件在使用过程中，没有磨损、老化问题软件在使用过程中，没有磨损、老化问题 软件依赖与硬件和环境，导致了移植问题软件依赖与硬件和环境，导致了移植问题 软件是复杂的，而且以后会更复杂软件是复杂的，而且以后会更复杂 软件的成本相当昂贵软件的成本相当昂贵 软件工作牵涉到很多社会因素软件工作牵涉到很多社会因素3.1 3.1 软件工程基本概念软件工程基本概念149v软件危机软件危机软件危机软件危机 早期的软件主要指程序，采用个体工作方式，缺少相关文早期的软件主要指程序，采用个体工作方式，缺少相关文档，质量低，维护困难，这些问题称为档，质量低，维护困难，这些问题称为“软件危机软件危机”，软件工，软件工程概念的出现源自于软件危机。程概念的出现源自于软件危机。v软件工程软件工程软件工程软件工程 软件工程是指应用计算机科学、数学及管理科学等原理，软件工程是指应用计算机科学、数学及管理科学等原理，以工程化的原则和方法来解决软件问题的工程。其目的是提高以工程化的原则和方法来解决软件问题的工程。其目的是提高软件生产率、提高软件质量、降低软件成本。软件生产率、提高软件质量、降低软件成本。3.1 3.1 软件工程基本概念软件工程基本概念150v软件工程基本目标软件工程基本目标软件工程基本目标软件工程基本目标 在给定成本、进度的前提下，开发出具有有效性、可靠性、在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品。踪性和可互操作性且满足用户需求的产品。v软件工程三要素软件工程三要素软件工程三要素软件工程三要素 方法：完成软件工程项目的技术手段方法：完成软件工程项目的技术手段方法：完成软件工程项目的技术手段方法：完成软件工程项目的技术手段 工具：支持软件的开发、管理、文档生成工具：支持软件的开发、管理、文档生成工具：支持软件的开发、管理、文档生成工具：支持软件的开发、管理、文档生成 过程：支持软件开发的各个环节的控制、管理过程：支持软件开发的各个环节的控制、管理过程：支持软件开发的各个环节的控制、管理过程：支持软件开发的各个环节的控制、管理 3.1 3.1 软件工程基本概念软件工程基本概念151v软件生命周期软件生命周期软件生命周期软件生命周期 软件产品从提出、实现、使用维护到停止使用退役的过程称软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。为软件生命周期。维护是持续时间最长，花费代价最大的一个时期，软件工程维护是持续时间最长，花费代价最大的一个时期，软件工程学的一个目的就是提高软件的可维护性，降低维护代价。学的一个目的就是提高软件的可维护性，降低维护代价。分为软件定义、软件开发及软件运行维护分为软件定义、软件开发及软件运行维护3 3个阶段。个阶段。1 1）软件定义阶段：）软件定义阶段：包括制定计划和需求分析。包括制定计划和需求分析。制定计划：确定总目标；可行性研究；探讨解决方案；制定计划：确定总目标；可行性研究；探讨解决方案；制定开发计划。制定开发计划。需求分析：对待开发软件提出的需求进行分析并给出详需求分析：对待开发软件提出的需求进行分析并给出详细的定义。细的定义。1522 2）软件开发阶段：）软件开发阶段：软件设计：分为概要设计和详细设计两个部分。软件设计：分为概要设计和详细设计两个部分。软件实现：把软件设计转换成计算机可以接受的程序软件实现：把软件设计转换成计算机可