公共基础知识ppt课件

1、全国计算机等级考试二级二级公共公共根底根底知识知识考试大纲考试大纲根本要求根本要求1、掌握算法的根本概念。、掌握算法的根本概念。2、掌握根本数据构造及其操作。、掌握根本数据构造及其操作。3、掌握根本排序和查找算法。、掌握根本排序和查找算法。4、掌握逐渐求精的构造化程序设计方法。、掌握逐渐求精的构造化程序设计方法。5、掌握软件工程的根本方法，具有初步、掌握软件工程的根本方法，具有初步运用相关技术进展软件开发的才干。运用相关技术进展软件开发的才干。6、掌握数据库的根本知识，了解关系数、掌握数据库的根本知识，了解关系数据库的设计。据库的设计。考试大纲考试大纲考试内容考试内容一、根本数据构造与算法一、

2、根本数据构造与算法1、算法的根本概念；算法复杂度的概念和意、算法的根本概念；算法复杂度的概念和意义义(空间复杂度与时间复杂度空间复杂度与时间复杂度)。2、数据构造的定义；数据的逻辑构造和存储、数据构造的定义；数据的逻辑构造和存储构造；数据构造的图形表示；线性构造与非线构造；数据构造的图形表示；线性构造与非线性构造的概念。性构造的概念。3、线性表的定义；线性表的顺序存储构造及、线性表的定义；线性表的顺序存储构造及其插入删除运算。其插入删除运算。4、栈和队列的定义；栈和队列的顺序存储构、栈和队列的定义；栈和队列的顺序存储构造及其根本运算。造及其根本运算。5、线性单链表，双向链表与循环链表的构造、线

3、性单链表，双向链表与循环链表的构造及其根本运算。及其根本运算。6、树的根本概念；二叉树的定义及其存储构、树的根本概念；二叉树的定义及其存储构造；二叉树的前序、中序和后序遍历。造；二叉树的前序、中序和后序遍历。7、顺序查找与二分查找算法；根本排序算法、顺序查找与二分查找算法；根本排序算法(交换类排序、选择类排序、插入类排序交换类排序、选择类排序、插入类排序)。考试大纲考试大纲考试内容考试内容二、程序设计根底二、程序设计根底1、程序设计方法与风格。、程序设计方法与风格。2、构造化程序设计。、构造化程序设计。3、面向对象的程序设计方法，对象，方法，、面向对象的程序设计方法，对象，方法，属性及承继与多

4、态性。属性及承继与多态性。考试大纲考试大纲考试内容考试内容三、软件工程根底三、软件工程根底1、软件工程的根本概念；软件生命周期概念；、软件工程的根本概念；软件生命周期概念；软件工具与软件开发环境。软件工具与软件开发环境。2、构造化分析方法；数据流图，数据字典，、构造化分析方法；数据流图，数据字典，软件需求规格阐明书。软件需求规格阐明书。3、构造化设计方法；、构造化设计方法； 总体设计，详细设计。总体设计，详细设计。4、软件测试的方法；白盒测试，黑盒测试，、软件测试的方法；白盒测试，黑盒测试，测试用例设计；软件测试的实施；单元测试，测试用例设计；软件测试的实施；单元测试，集成测试，系统测试。集成

5、测试，系统测试。5、程序的调试，静态调试与动态调试。、程序的调试，静态调试与动态调试。考试大纲考试大纲考试内容考试内容四、数据库设计根底四、数据库设计根底1、数据库的根本概念；数据库，数据库管理、数据库的根本概念；数据库，数据库管理系统，数据库系统。系统，数据库系统。2、数据模型；实体联络模型及、数据模型；实体联络模型及E-R图，从图，从E-R图导出关系数据模型。图导出关系数据模型。3、关系代数运算，包括集合运算及选择、投、关系代数运算，包括集合运算及选择、投影、衔接运算；数据库规范化实际。影、衔接运算；数据库规范化实际。4、数据库设计方法和步骤；需求分析、概念、数据库设计方法和步骤；需求分析

6、、概念设计、逻辑设计和物理设计的相关战略。设计、逻辑设计和物理设计的相关战略。考试大纲考试大纲考试题型考试题型选择题选择题10 题题每题每题 2 分分共共 20 分分填空题填空题5 题题每题每题 2 分分共共 10 分分合计合计30 分分数据构造与算法数据构造与算法关键考点关键考点算法根本概念及算法复杂度算法根本概念及算法复杂度数据的存储构造数据的存储构造栈和队列栈和队列线性链表线性链表二叉树根本概念及其特性二叉树根本概念及其特性查找技术查找技术数据构造与算法数据构造与算法算法的根本概念算法的根本概念1、算法、算法算法是指解题方案的准确而完好的描画。算法是指解题方案的准确而完好的描画。留意：算

7、法与数学上的计算方法不是同一个留意：算法与数学上的计算方法不是同一个概念。算法要思索计算机的特点，要思索计概念。算法要思索计算机的特点，要思索计算方法的可行性。算方法的可行性。算法也不等于程序。算法不思索详细的机算法也不等于程序。算法不思索详细的机器及编程言语。处理问题时，总是先设计算器及编程言语。处理问题时，总是先设计算法，然后进展编程。法，然后进展编程。2、算法的根本特征、算法的根本特征可行性可行性确定性确定性有穷性有穷性拥有足够的情报拥有足够的情报算法是一个动态概念，强调实践的执行过算法是一个动态概念，强调实践的执行过程。程。数学上的计算方法是一个静态概念，注重数学上的计算方法是一个静态

8、概念，注重实际上的正确性。实际上的正确性。数学上的计算方法是设计算法的根底。数学上的计算方法是设计算法的根底。数据构造与算法数据构造与算法算法的根本概念算法的根本概念3、算法的根本要素、算法的根本要素算法中对数据的运算和操作算法中对数据的运算和操作根本的运算和操作有：算术运算、逻辑运算、根本的运算和操作有：算术运算、逻辑运算、关系运算、数据传输。关系运算、数据传输。算法的控制构造算法的控制构造控制构造决议操作的执行顺序。要求符合构控制构造决议操作的执行顺序。要求符合构造化原那么，强调易读性。造化原那么，强调易读性。4、算法设计根本方法、算法设计根本方法列举法列举法 列举一切能够情况，检测其中符

9、合条列举一切能够情况，检测其中符合条件的结果。件的结果。归纳法归纳法 列举假设干特殊情况，分析归纳出普列举假设干特殊情况，分析归纳出普通规律。通规律。递推递推 从知初始条件出发，逐渐推导出中从知初始条件出发，逐渐推导出中间及最后结果。间及最后结果。递归递归 将复杂问题归结为简单问题，在归将复杂问题归结为简单问题，在归结为更简单问题，结为更简单问题， 。减半递推技术减半递推技术 将问题规模将问题规模“减半，并反复减半，并反复该该“减半减半 的过程。的过程。回溯法回溯法 分析问题，找出某些线索，沿线索分析问题，找出某些线索，沿线索逐渐试探。假设试探胜利，那么继续，假设逐渐试探。假设试探胜利，那么继

10、续，假设试探失败，那么回退。直至问题处理。试探失败，那么回退。直至问题处理。数据构造与算法数据构造与算法算法的根本概念算法的根本概念5、算法的时间复杂度、算法的时间复杂度指执行算法所需求的计算任务量指执行算法所需求的计算任务量算法任务量的度量应与计算机、编程言语、算法任务量的度量应与计算机、编程言语、编程细节等无关。编程细节等无关。算法的任务量用算法所执行的根本运算次数算法的任务量用算法所执行的根本运算次数衡量。衡量。算法任务量是问题规模的函数：算法的任务算法任务量是问题规模的函数：算法的任务量量= f (n)度量方法有：度量方法有：平均性态分析平均性态分析 计算其加计算其加权平均值权平均值最

11、坏情况分析最坏情况分析 计算其根本运算的最计算其根本运算的最大次数大次数6、算法的空间复杂度、算法的空间复杂度指执行算法所需求的存储空间指执行算法所需求的存储空间包括：算法程序所占据的存储空间包括：算法程序所占据的存储空间待处置数据所占据的存储空间待处置数据所占据的存储空间算法程序执行中所需求的额外存储空间算法程序执行中所需求的额外存储空间假设额外存储空间大小不随问题规模变化，假设额外存储空间大小不随问题规模变化，那么称之为算法原地任务。那么称之为算法原地任务。降低算法的空间复杂度，应从数据的存储空降低算法的空间复杂度，应从数据的存储空间和额外空间入手。间和额外空间入手。算法定义特征复杂度时间

12、/空间数据构造1.数据的逻辑构造2.数据的存储构造3.数据的运算线性线性表栈、队列非线性树形构造二叉树满二叉树、完全二叉数顺序存储链式存储索引存储散列存储查找顺序、二分修正排序交换、插入、选择插入删除修正数据构造与算法数据构造与算法数据构造的根本概念数据构造的根本概念1、数据构造、数据构造数据构造是指相互有关联的数据元素的集合数据构造是指相互有关联的数据元素的集合数据构造是指带有构造的数据元素的集合。数据构造是指带有构造的数据元素的集合。构造构造 通常指前后件关系。通常指前后件关系。主要研讨：数据元素间的固有逻辑关系主要研讨：数据元素间的固有逻辑关系 数据元素在计算机中的存储关系数据元素在计算

13、机中的存储关系 对各种数据构造进展的运算对各种数据构造进展的运算2、数据的逻辑构造、数据的逻辑构造指反映数据元素之间逻辑关系的数据构造指反映数据元素之间逻辑关系的数据构造前后件前后件(直接前驱和直接后继直接前驱和直接后继)关系就是指逻关系就是指逻辑关系辑关系3、数据的存储构造、数据的存储构造数据的逻辑构造在计算机中的存储方式数据的逻辑构造在计算机中的存储方式存储构造也称为物理构造存储构造也称为物理构造同一种逻辑构造可以有不同的存储构造同一种逻辑构造可以有不同的存储构造常用的有：顺序、链接、索引等方式常用的有：顺序、链接、索引等方式数据构造的根本概念数据构造的根本概念4、数据构造的表示、数据构造

14、的表示二元关系表示：二元关系表示：两个要素：数据元素的集合两个要素：数据元素的集合D，该集合上的，该集合上的关系关系R。即：即：B=(D,R)如：如：D=春春,夏夏,秋秋,冬冬 R=(春春,夏夏),(夏夏,秋秋),(秋秋,冬冬)图形表示：图形表示：标有元素值的方框表示结点，有向线段表示标有元素值的方框表示结点，有向线段表示逻辑关系。逻辑关系。春春 夏夏 秋秋 冬冬5、线性构造和非线性构造、线性构造和非线性构造线性构造：一个非空的线性构造有且只需一线性构造：一个非空的线性构造有且只需一个根结点，每个结点最多只需一个直接前驱、个根结点，每个结点最多只需一个直接前驱、最多只需一个直接后继。最多只需一

15、个直接后继。非线性构造：不是线性构造的数据构造。非线性构造：不是线性构造的数据构造。线性表及其顺序存储构造线性表及其顺序存储构造1、线性表、线性表线性表是由线性表是由 n (n0)个元素组成的有限序列：个元素组成的有限序列：(a1,a2,ai,an)有且只需一个根结点，它无直接前驱。有且只需一个根结点，它无直接前驱。有且只需一个终端结点，它无直接后继。有且只需一个终端结点，它无直接后继。除根结点和终端结点外，其他一切结点都除根结点和终端结点外，其他一切结点都有且只需一个直接前驱和直接后继。结点个有且只需一个直接前驱和直接后继。结点个数数n称为线性表的长度。称为线性表的长度。n=0时，称为空表。

16、时，称为空表。2、线性表的顺序存储、线性表的顺序存储顺序存储也称为顺序分配顺序存储也称为顺序分配线性表中一切元素所占的存储空间是延续的线性表中一切元素所占的存储空间是延续的线性表中各元素在存储空间中按照逻辑顺序线性表中各元素在存储空间中按照逻辑顺序依次存储依次存储3、顺序表的运算、顺序表的运算线性表的顺序存储构造通常称为顺序表线性表的顺序存储构造通常称为顺序表包括：插入、删除、查找、分解、合并、复包括：插入、删除、查找、分解、合并、复制、制、逆转等。逆转等。在高级言语中，顺序表对应一维数组。在高级言语中，顺序表对应一维数组。顺序表的查找方便，插入和删除较费事。顺序表的查找方便，插入和删除较费事

17、。线性表及其顺序存储构造线性表及其顺序存储构造留意：留意： 线性表属于线性构造。线性表属于线性构造。 线性表的顺序存储构造通常称为顺序表。线性表的顺序存储构造通常称为顺序表。 在顺序表中，一切元素按照其逻辑顺序在顺序表中，一切元素按照其逻辑顺序延续存储，前后件元素紧邻，前件元素一定延续存储，前后件元素紧邻，前件元素一定存储在后件元素的前面。逻辑上相邻的数据存储在后件元素的前面。逻辑上相邻的数据元素物理上也相邻元素物理上也相邻 在程序设计言语中，线性表的顺序存储在程序设计言语中，线性表的顺序存储构造对应了一维数组。由于在程序设计言语构造对应了一维数组。由于在程序设计言语中，一维数组与计算机中实践

18、的存储空间构中，一维数组与计算机中实践的存储空间构造是一致的。造是一致的。 在顺序表中，假设要在第在顺序表中，假设要在第 i 个位置插入一个位置插入一个新元素，那么原第个新元素，那么原第 i 个元素以及之后的一个元素以及之后的一切元素都要依次后移一个位置。在平均情况切元素都要依次后移一个位置。在平均情况下，在顺序表中插入一个新元素，需求挪动下，在顺序表中插入一个新元素，需求挪动 n/2 个元素。个元素。 在顺序表中，假设要删除第在顺序表中，假设要删除第 i 个位置的元个位置的元素，那么原第素，那么原第 i 个元素之后的一切元素都要个元素之后的一切元素都要依次前移一个位置。在平均情况下，在顺序依

19、次前移一个位置。在平均情况下，在顺序表中删除一个元素，需求挪动表中删除一个元素，需求挪动 n/2 个元素。个元素。数据构造与算法数据构造与算法栈及其根本运算栈及其根本运算1、栈、栈栈栈(stack)是限定在一端进展插入和删除的线是限定在一端进展插入和删除的线性表性表允许进展插入或删除的一端称为栈顶。允许进展插入或删除的一端称为栈顶。不允许进展插入或删除的另一端称为栈底。不允许进展插入或删除的另一端称为栈底。其特点为其特点为“先入后出先入后出(FILO)或或“后入先出后入先出(LIFO)。(记忆作用记忆作用)通常设置指针通常设置指针top指向栈顶，指针指向栈顶，指针bottom指指向栈底。向栈底

20、。2、栈的顺序存储构造、栈的顺序存储构造栈的各个数据元素按其逻辑顺序依次延续存栈的各个数据元素按其逻辑顺序依次延续存储。储。由于插入删除操作只能在栈顶一端进展，所由于插入删除操作只能在栈顶一端进展，所以以不需求挪动数据元素。不需求挪动数据元素。3、栈的根本运算、栈的根本运算入栈：在栈顶位置插入新元素。入栈：在栈顶位置插入新元素。出栈：取出栈顶位置的元素。出栈：取出栈顶位置的元素。读栈顶元素：读出栈顶位置的元素。读栈顶元素：读出栈顶位置的元素。“上溢：入栈时堆栈已满。上溢：入栈时堆栈已满。“下溢：下溢：出栈时堆栈已空。出栈时堆栈已空。数据构造与算法数据构造与算法队列及其根本运算队列及其根本运算1

21、、队列、队列队列队列(queue)是限定在一端进展插入另一端进是限定在一端进展插入另一端进展删除的线性表展删除的线性表允许进展插入的一端称为队尾。允许进展插入的一端称为队尾。允许进展删除的另一端称为队头。允许进展删除的另一端称为队头。其特点为其特点为“先入先出先入先出(FIFO)或或“后入后出后入后出(LILO)。(先来先效力先来先效力)通常设置指针通常设置指针rear指向队尾，指针指向队尾，指针front指向指向队头。队头。2、队列的顺序存储构造、队列的顺序存储构造队列的各个数据元素按其逻辑顺序依次延续队列的各个数据元素按其逻辑顺序依次延续存储。存储。由于插入删除操作只能在队列的两端进展，由

22、于插入删除操作只能在队列的两端进展，所以所以不需求挪动数据元素。不需求挪动数据元素。3、队列的根本运算、队列的根本运算在实践运用中经常运用循环队列。在实践运用中经常运用循环队列。入队：在队尾位置插入新元素。入队：在队尾位置插入新元素。 出队：取出队头位置的元素。出队：取出队头位置的元素。 “上溢：入队时队列已满。上溢：入队时队列已满。“下溢：下溢：出队时队列已空。出队时队列已空。数据构造与算法数据构造与算法线性链表线性链表1、链式存储方式、链式存储方式 结点由两部分组成：数据域结点由两部分组成：数据域(存储数据存储数据)、指针域指针域(指向其前件或后件指向其前件或后件)。 数据构造的存储空间可

23、以不延续，存储顺数据构造的存储空间可以不延续，存储顺序与逻辑关系可以不一致。序与逻辑关系可以不一致。 链式存储方式既可以用来表示线性构造，链式存储方式既可以用来表示线性构造，也可以表示非线性构造。也可以表示非线性构造。2、线性链表、线性链表线性表的链式存储构造称为线性链表。线性表的链式存储构造称为线性链表。(栈的链式存储构造称为链栈、队列的链式存栈的链式存储构造称为链栈、队列的链式存储构造称为链队列储构造称为链队列)常用的线性链表有：常用的线性链表有：单链表单链表 (一个指针域，指向直接后继一个指针域，指向直接后继)双向链表双向链表 (两个指针域，指向直接后继及后继两个指针域，指向直接后继及后

24、继) 循环链表循环链表 (一切结点的指针构成循环链一切结点的指针构成循环链)3、线性链表的根本运算、线性链表的根本运算查找：在线性链表中查找指定元素。查找：在线性链表中查找指定元素。插入：在线性链表中插入新结点。插入：在线性链表中插入新结点。删除：在线性链表中删除指定结点。删除：在线性链表中删除指定结点。表头指针表头指针data next newnodepnewnodep数据构造与算法数据构造与算法树的根本概念树的根本概念1、树、树树是一种简单的非线性构树是一种简单的非线性构造。造。元素间的关系具有明显的元素间的关系具有明显的层次构造。层次构造。2、相关的术语、相关的术语根结点根结点叶节点叶节

25、点父结点父结点子结点子结点子树子树结点的度结点的度树的度树的度树的深度树的深度数据构造与算法数据构造与算法二叉树二叉树1、二叉树的特点、二叉树的特点非空二叉树只需一个根结点。非空二叉树只需一个根结点。每个结点最多有左右两棵子树。每个结点最多有左右两棵子树。2、二叉树的根本性质、二叉树的根本性质第第 k 层上最多有层上最多有 2 k-1个结点个结点深度为深度为 m 的二叉树最多有的二叉树最多有 2m-1个结个结点点任何二叉树叶结点总比度为任何二叉树叶结点总比度为 2 的节点的节点多一个多一个n 个节点的二叉树的深度为个节点的二叉树的深度为 log2n+13、满二叉树、满二叉树4、完全二叉树、完全

26、二叉树5、二叉树的遍历、二叉树的遍历先序遍历先序遍历 中序遍历中序遍历后序遍后序遍历历ABDEGCFHI DBGEACHFIDGEBHIFCA数据构造与算法数据构造与算法查找技术查找技术1、顺序查找、顺序查找从线性表的第一个元素开场，依次与指定数从线性表的第一个元素开场，依次与指定数据比较，假设相等那么查找胜利，假设比较据比较，假设相等那么查找胜利，假设比较的一切元素都不相等，那么查找失败。的一切元素都不相等，那么查找失败。最坏情况的比较次数为表长最坏情况的比较次数为表长n，平均情况为，平均情况为n/2。无序顺序表的查找只能采用顺序查找的方法。无序顺序表的查找只能采用顺序查找的方法。线性表在链

27、式存储时也只能采用顺序查找的线性表在链式存储时也只能采用顺序查找的方法。方法。2、二分法查找、二分法查找在顺序存储的线性表为有序的情况下，可以在顺序存储的线性表为有序的情况下，可以运用二分法查找。运用二分法查找。方法为：方法为：将待查数据与线性表的中间项比较：将待查数据与线性表的中间项比较：假设相等，那么查找胜利；假设相等，那么查找胜利；假设小于，那么在线性表的前半部分进展假设小于，那么在线性表的前半部分进展二分法查找；二分法查找；假设大于，那么在线性表的后半部分进展假设大于，那么在线性表的后半部分进展二分法查找；二分法查找；反复进展直到相等反复进展直到相等(查找胜利查找胜利)或子表长度或子表

28、长度为为0(查找失败查找失败)。数据构造与算法数据构造与算法排序技术排序技术1、交换类排序、交换类排序起泡排序起泡排序最坏情况下的比较次数为最坏情况下的比较次数为 n(n-1)/2 。 快速排序快速排序最坏情况下的比较次数为最坏情况下的比较次数为 n(n-1)/2 。 2、插入类排序、插入类排序简单插入排序简单插入排序最坏情况下的比较次数为最坏情况下的比较次数为 n(n-1)/2 。 希尔排序希尔排序最坏情况下的比较次数为最坏情况下的比较次数为 O( n 1.5) 。3、选择类排序、选择类排序简单项选择择排序简单项选择择排序最坏情况下的比较次数为最坏情况下的比较次数为 n(n-1)/2 。堆排

29、序堆排序最坏情况下的比较次数为最坏情况下的比较次数为 O( n log2n) 。数据构造与算法数据构造与算法本章重点本章重点1、算法是问题处置方案正确而完好的描画，算、算法是问题处置方案正确而完好的描画，算法的效率与数据的存储构造有亲密的关系。法的效率与数据的存储构造有亲密的关系。2、数据的逻辑构造在计算机中的表示、数据的逻辑构造在计算机中的表示(存储方存储方式式)称为数据的存储构造称为数据的存储构造(物理构造物理构造)。一种逻。一种逻辑构造可以有多种存储构造。辑构造可以有多种存储构造。3、在长度为、在长度为 n 的顺序表中，插入或删除一个元的顺序表中，插入或删除一个元素平均需求挪动一半元素。

30、素平均需求挪动一半元素。4、栈是特殊的线性表，具有记忆作用。特点是、栈是特殊的线性表，具有记忆作用。特点是“先进后出先进后出(后进先出后进先出)。栈顶指针动态反映。栈顶指针动态反映了栈中元素的变化情况。了栈中元素的变化情况。5、队列是特殊的线性表。特点是、队列是特殊的线性表。特点是“先进先出先进先出(后后进后出进后出)。队头和队尾指针动态地反映了队。队头和队尾指针动态地反映了队列中元素的变化情况。列中元素的变化情况。6、线性链表是线性表的链式存储构造。在线性、线性链表是线性表的链式存储构造。在线性链表中，各元素节点的存储空间可以不延续，链表中，各元素节点的存储空间可以不延续，存储顺序也可以与逻

31、辑顺序不一致。线性链存储顺序也可以与逻辑顺序不一致。线性链表的插入删除操作不需求挪动数据元素。表的插入删除操作不需求挪动数据元素。7、二叉树是一种非线性构造。主要性质有：、二叉树是一种非线性构造。主要性质有：第第k层上最多有层上最多有 2 k-1 个结点个结点深度为深度为 m 时，最多有时，最多有2 m 1 个结点个结点度为度为0的结点比度为的结点比度为2的多一个的多一个深度至少为深度至少为 log2n +1数据构造与算法数据构造与算法本章重点本章重点8、满二叉树是二叉树的特殊形状，满二叉树的、满二叉树是二叉树的特殊形状，满二叉树的各层结点都到达最大值，叶结点只出如今最各层结点都到达最大值，叶

32、结点只出如今最后一层。后一层。9、完全二叉树是二叉树的特殊形状，完全二叉、完全二叉树是二叉树的特殊形状，完全二叉树除最后一层外，各层结点都到达最大值，树除最后一层外，各层结点都到达最大值，叶结点只出如今最后两层。满二叉树属于完叶结点只出如今最后两层。满二叉树属于完全二叉树。全二叉树。10、根据扫描根结点的顺序，按照先左后右的、根据扫描根结点的顺序，按照先左后右的原那么，遍历二叉树有三种原那么，遍历二叉树有三种方法：前序遍历、中序遍历、后序遍历。方法：前序遍历、中序遍历、后序遍历。11、在长度为、在长度为 n 的线性表中进展顺序查找，最的线性表中进展顺序查找，最坏情况需求比较坏情况需求比较 n

33、次。次。12、在长度为、在长度为 n 的线性表中进展对分查找，最的线性表中进展对分查找，最坏情况需求比较坏情况需求比较 log2n 次。但对分查找只适用次。但对分查找只适用于有序顺序表。于有序顺序表。13、在冒泡排序、快速排序、简单插入排序、在冒泡排序、快速排序、简单插入排序、选择排序的方法中，最坏情况下需求比较的选择排序的方法中，最坏情况下需求比较的次数为次数为 n(n-1)/2 。程序设计根底程序设计根底关键考点关键考点构造化设计的原那么构造化设计的原那么面向对象方法的根本概念面向对象方法的根本概念程序设计根底程序设计根底程序设计方法与风格程序设计方法与风格1、程序设计方法、程序设计方法就

34、程序设计的方法和技术的开展而言就程序设计的方法和技术的开展而言主要阅历了构造化程序设计和面向对象程主要阅历了构造化程序设计和面向对象程序设计两个阶段序设计两个阶段2、程序设计风格、程序设计风格程序设计风格是指编写程序时所表现出来的程序设计风格是指编写程序时所表现出来的特点、习惯和逻辑思绪。特点、习惯和逻辑思绪。程序设计风格会深化影响软件的质量和可维程序设计风格会深化影响软件的质量和可维护性，良好的程序设计风格可以使程序的构护性，良好的程序设计风格可以使程序的构造明晰合理，使程序代码便于维护。造明晰合理，使程序代码便于维护。程序设计风格的主导：程序设计风格的主导：“明晰第一，效率第二明晰第一，效

35、率第二。主要要素：主要要素：源程序文档化源程序文档化数听阐明的方法数听阐明的方法语句的构造语句的构造输入和输出输入和输出程序设计根底程序设计根底构造化程序设计构造化程序设计1、构造化程序设计、构造化程序设计要求把程序的构造限制为顺序、选择和循环要求把程序的构造限制为顺序、选择和循环三种根本构造。三种根本构造。2、构造化程序设计的原那么、构造化程序设计的原那么自顶向下自顶向下先总体后细节，先全局后部分。先总体后细节，先全局后部分。逐渐求精逐渐求精对复杂问题设计子目的过度，对复杂问题设计子目的过度，逐渐细化。逐渐细化。模块化模块化 将复杂问题分解为假设干简单问题。将复杂问题分解为假设干简单问题。限

36、制运用限制运用GOTO语句语句防止呵斥程序逻辑构防止呵斥程序逻辑构造混乱。造混乱。3、三种根本构造、三种根本构造顺序构造顺序构造 选择构造选择构造循环构造循环构造4、特点、特点一切控制构造由三种根本构造组成一切控制构造由三种根本构造组成各个模块单入口单出口各个模块单入口单出口模块的内聚性强模块的内聚性强 模块间的巧合性低模块间的巧合性低程序设计根底程序设计根底面向对象的程序设计面向对象的程序设计1、面向对象、面向对象面向对象方法的本质，是从客观世界固有的面向对象方法的本质，是从客观世界固有的事物出发来构造系统，用现实生活中常用的事物出发来构造系统，用现实生活中常用的思想方法来描画客观事物，是系

37、统中的对象思想方法来描画客观事物，是系统中的对象及对象间的关系能照实反映事物及其关系。及对象间的关系能照实反映事物及其关系。2、主要优点、主要优点与人类习惯的思想方法一致与人类习惯的思想方法一致稳定性好稳定性好可重用性好可重用性好易于开发大型软件产品易于开发大型软件产品可维护性好可维护性好3、根本概念、根本概念对象对象类和实例类和实例音讯音讯承继承继多态性多态性程序设计根底程序设计根底本章重点本章重点1、程序设计并不等于编程，编程只是程序设、程序设计并不等于编程，编程只是程序设计过程中的一小步。计过程中的一小步。2、构造化程序设计要求把程序的构造限制为、构造化程序设计要求把程序的构造限制为顺序

38、、选择、循环三种根本构造。顺序、选择、循环三种根本构造。3、模块化设计是指把一个大程序按人们能了、模块化设计是指把一个大程序按人们能了解的大小规模进展分解。划分模块的根本原解的大小规模进展分解。划分模块的根本原那么是使每个模块都易于了解。在按功能划那么是使每个模块都易于了解。在按功能划分模块时，要求各模块功能尽量单一，各模分模块时，要求各模块功能尽量单一，各模块之间的联络尽量的少。块之间的联络尽量的少。4、客观世界是由实体及其联络所组成的。客、客观世界是由实体及其联络所组成的。客观世界中的实体称为问题域的对象。观世界中的实体称为问题域的对象。5、类描画的是具有类似性质一组对象。一个、类描画的是

39、具有类似性质一组对象。一个对象称为类的实例。对象称为类的实例。6、允许作用于某个对象上的各种操作称为方、允许作用于某个对象上的各种操作称为方法。法。7、音讯是用来恳求对象执行某一处置或回答、音讯是用来恳求对象执行某一处置或回答某些信息的要求。某些信息的要求。8、承继是表示类之间的类似性的一种机制。、承继是表示类之间的类似性的一种机制。9、封装是一种信息隐蔽机制，目的是将对象、封装是一种信息隐蔽机制，目的是将对象的运用者与对象的设计者分开。用户只需了的运用者与对象的设计者分开。用户只需了解对象封装界面上的信息，不用知道内部的解对象封装界面上的信息，不用知道内部的详细细节。详细细节。软件工程根底软

40、件工程根底关键考点关键考点软件定义与特点软件定义与特点软件开发过程的过程化原那么软件开发过程的过程化原那么构造化分析方法构造化分析方法构造化设计方法构造化设计方法软件测试技术与方法软件测试技术与方法程序调试根本概念程序调试根本概念软件工程根底软件工程根底软件工程根本概念软件工程根本概念1、软件、软件软件是包括程序、数据及相关文档的完好集软件是包括程序、数据及相关文档的完好集合。合。2、软件的特点、软件的特点笼统性笼统性可大量拷贝可大量拷贝无磨损及老化问题无磨损及老化问题受计算机系统限制受计算机系统限制(移植问移植问题题)复杂性高本钱昂贵复杂性高本钱昂贵开发过程涉及诸多社会要开发过程涉及诸多社会

41、要素素3、软件工程、软件工程软件工程是运用于计算机软件的定义、开发软件工程是运用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实际规和维护的一整套方法、工具、文档、实际规范和工序。范和工序。三个要素三个要素方法：完成软件工程工程的技术手段。方法：完成软件工程工程的技术手段。工具：支持软件的开发、管理、文档生成。工具：支持软件的开发、管理、文档生成。过程：支持软件开发各个环节的管理、控过程：支持软件开发各个环节的管理、控制。制。目的：在给定本钱、进度的前提下，开发出目的：在给定本钱、进度的前提下，开发出具有有效性、可靠性、可了解性、可维护性、具有有效性、可靠性、可了解性、可维护性、可顺

42、应性、可追踪性、可互操作性满足用户可顺应性、可追踪性、可互操作性满足用户要求的软件产品。要求的软件产品。软件工程根底软件工程根底软件开发过程的过程化原那么软件开发过程的过程化原那么1、软件工程过程、软件工程过程 为获得软件产品，在软件工具支持下的一为获得软件产品，在软件工具支持下的一系列软件工程活动。系列软件工程活动。Plan 软件规格阐明。软件规格阐明。Do软件软件开发。开发。Check软件确认。软件确认。Action软件演进。软件演进。 运用适当的资源，为开发软件进展的一组运用适当的资源，为开发软件进展的一组开发活动，在过程终了时将用户要求转化为开发活动，在过程终了时将用户要求转化为软件产

43、品。软件产品。软件工程过程应确定方法运用的顺序、要求软件工程过程应确定方法运用的顺序、要求交付的文档资料、为保证质量与顺应变化所交付的文档资料、为保证质量与顺应变化所需求的管理、软件开发各阶段要完成的义务。需求的管理、软件开发各阶段要完成的义务。2、软件生命周期、软件生命周期 定义阶段定义阶段可行性研讨及工程方案可行性研讨及工程方案需求分需求分析析 开发阶段开发阶段概要设计概要设计详细设计详细设计实现实现测试测试 维护阶段维护阶段运用运用维护维护退役退役软件工程根底软件工程根底构造化分析方法构造化分析方法在系统分析阶段，构造化分析方法用来对系统在系统分析阶段，构造化分析方法用来对系统进展逻辑设

44、计。进展逻辑设计。1、需求分析、需求分析需求分析的义务是发现需求、求精、建模和需求分析的义务是发现需求、求精、建模和定义需求。定义需求。 常见的需求分析方法：构造化分析方法常见的需求分析方法：构造化分析方法 面向对象的分析方法面向对象的分析方法2、构造化分析方法、构造化分析方法 构造化分析就是运用数据流图构造化分析就是运用数据流图(DFD)、数据、数据字典字典(DD)、构造化英语、断定表和断定树等、构造化英语、断定表和断定树等工具，来建立一种被称为构造化规格阐明的工具，来建立一种被称为构造化规格阐明的目的文档。目的文档。 构造化分析方法的本质是着眼于构造化分析方法的本质是着眼于数据流的、自顶向

45、下逐层分解的、建立系统数据流的、自顶向下逐层分解的、建立系统的处置流程，它以数据流图和数据字典为主的处置流程，它以数据流图和数据字典为主要工具，建立系统的逻辑模型。要工具，建立系统的逻辑模型。3、 软件需求规格阐明书软件需求规格阐明书是需求分析阶段的最后成果，是软件开发的是需求分析阶段的最后成果，是软件开发的重要文档之一。重要文档之一。软件需求规格阐明书把软件方案中确定的软软件需求规格阐明书把软件方案中确定的软件范围加以展开，制定出完好的信息描画、件范围加以展开，制定出完好的信息描画、详细的功能阐明、恰当的检验规范、其他与详细的功能阐明、恰当的检验规范、其他与要求有关的信息。要求有关的信息。软

46、件工程根底软件工程根底构造化设计方法构造化设计方法1、软件设计、软件设计软件设计是把软件需求转换为软件表示的过软件设计是把软件需求转换为软件表示的过程。程。从技术角度：软件设计包括构造设计、数据从技术角度：软件设计包括构造设计、数据设计、接口设计、过程设计。设计、接口设计、过程设计。从工程角度：软件设计包括概要设计、详细从工程角度：软件设计包括概要设计、详细设计。设计。软件设计的根本原理包括：笼统、模块化、软件设计的根本原理包括：笼统、模块化、信息隐蔽、模块独立性信息隐蔽、模块独立性2、概要设计、概要设计概要设计的根本义务：系统构造设计概要设计的根本义务：系统构造设计数数据构造设计据构造设计编

47、写设计文档编写设计文档设计文设计文档评审档评审构造图是软件构造设计的常用工具。构造图是软件构造设计的常用工具。3、详细设计、详细设计详细设计的义务，是为软件构造图中的每一详细设计的义务，是为软件构造图中的每一个模块确定算法和部分数据构造，用某种选个模块确定算法和部分数据构造，用某种选定的工具表示算法和数据构造的细节。定的工具表示算法和数据构造的细节。常见的设计工具：常见的设计工具：图形工具：流程图、图形工具：流程图、N - S、PAD、HIPO表格工具：断定表表格工具：断定表言语工具：言语工具：PDL(伪码伪码)软件工程根底软件工程根底软件测试软件测试1、测试、测试软件测试的目的是在精心控制的

48、环境下执行软件测试的目的是在精心控制的环境下执行程序，以发现程序中的错误，给出程序可靠程序，以发现程序中的错误，给出程序可靠性的鉴定。性的鉴定。测试不是为了证明程序是正确的，目的是设测试不是为了证明程序是正确的，目的是设法暴露程序中的错误和缺陷。法暴露程序中的错误和缺陷。测试只能阐明程序有错，不能证明程序无错。测试只能阐明程序有错，不能证明程序无错。程序不能程序不能100%可靠。可靠。2、测试方法、测试方法程序的静态分析程序的静态分析程序的动态分析程序的动态分析自自动测试工具动测试工具3、测试层次、测试层次模块测试模块测试(单元测试单元测试)整体测试整体测试(集成测试集成测试)又分为又分为 功

49、能测试功能测试 和和 验收测试验收测试 两种。两种。4、白盒法、白盒法根据对程序内部逻辑构造的分析来导出测试根据对程序内部逻辑构造的分析来导出测试用例。用例。5、黑盒法、黑盒法不思索程序的内部构造特征，根据程序功能不思索程序的内部构造特征，根据程序功能导出测试用例。导出测试用例。软件工程根底软件工程根底程序调试程序调试1、调试与测试、调试与测试 测试的目的是发现错误，评价可靠性；调测试的目的是发现错误，评价可靠性；调试的目的是发现错误的位置，矫正发现的错试的目的是发现错误的位置，矫正发现的错误。误。 测试提示设计人员的过失，由非设计人员测试提示设计人员的过失，由非设计人员承当；调试协助设计人员

50、矫正错误，由设计承当；调试协助设计人员矫正错误，由设计人员本人承当。人员本人承当。 测试是机械的、强迫的、严厉的、可预测测试是机械的、强迫的、严厉的、可预测的；调试要求随机应变、联想、阅历、智力，的；调试要求随机应变、联想、阅历、智力，并要求自主地完成。并要求自主地完成。 测试发现的错误可立刻进展调试矫正，然测试发现的错误可立刻进展调试矫正，然后还必需再进展测试。后还必需再进展测试。 调试用例与测试用例可以一致也可以不一调试用例与测试用例可以一致也可以不一致。致。2、调试方法、调试方法 强行排错法强行排错法 回溯法回溯法 缘由排除法缘由排除法软件工程根底软件工程根底本章重点本章重点1、软件生命

51、周期分为三个时期共八个阶段：、软件生命周期分为三个时期共八个阶段：软件定义期：问题定义、可行性研讨、需求软件定义期：问题定义、可行性研讨、需求分析。分析。软件开发期：系统设计、详细设计、编码、软件开发期：系统设计、详细设计、编码、测试。测试。软件维护期：运转维护。软件维护期：运转维护。2、在系统分析阶段，构造化分析方法用来对、在系统分析阶段，构造化分析方法用来对系统进展逻辑设计，此时不思索物理实现的系统进展逻辑设计，此时不思索物理实现的问题，而只思索问题，而只思索“做什么的问题，系统的物做什么的问题，系统的物理设计理设计(“如何做如何做)的问题留在系统设计阶段的问题留在系统设计阶段用构造化设计

52、方法来完成。用构造化设计方法来完成。3、数据流图有两种典型的构造方式：变换型、数据流图有两种典型的构造方式：变换型、事务型。事务型。4、评价模块的独立性的规范有两个：、评价模块的独立性的规范有两个：耦合性：阐明两个模块间联络的强弱。耦合性：阐明两个模块间联络的强弱。内聚性：阐明模块内部联络能否严密。内聚性：阐明模块内部联络能否严密。内聚性要强，巧合性要弱。内聚性要强，巧合性要弱。5、软件测试是在精心控制的环境下执行程序，、软件测试是在精心控制的环境下执行程序，发现程序中的错误，给出程序可靠性的鉴定。发现程序中的错误，给出程序可靠性的鉴定。6、测试是程序执行的过程，目的在于发现错、测试是程序执行

53、的过程，目的在于发现错误；一个好的测试在于能发现至今未能发现误；一个好的测试在于能发现至今未能发现的错误，一个胜利的测试是发现了至今未发的错误，一个胜利的测试是发现了至今未发现的错误。现的错误。7、测试发现错误后，可进展调试；调试后的、测试发现错误后，可进展调试；调试后的程序还应再测试，以检验调试效果。程序还应再测试，以检验调试效果。数据库设计根底数据库设计根底关键考点关键考点数据库系统根本概念数据库系统根本概念数据模型数据模型数据库设计根底数据库设计根底数据库系统的根本概念数据库系统的根本概念1、数据库、数据库 DB是数据的集合，具有一致的构造方式并存放是数据的集合，具有一致的构造方式并存放

54、于一致的存储介质中，是多种运用数据的集于一致的存储介质中，是多种运用数据的集成，可被各个运用程序所共享。成，可被各个运用程序所共享。2、数据库管理系统、数据库管理系统 DBMS数据库的管理机构，系统软件，担任数据组数据库的管理机构，系统软件，担任数据组织、支配、维护、控制、维护等。织、支配、维护、控制、维护等。为数据库构作方式为数据库构作方式为数据方式的实现提供方法和手段为数据方式的实现提供方法和手段为用户运用提供查询、插入、修正、删除为用户运用提供查询、插入、修正、删除等功能等功能提供对数据库中数据的多种效力功能提供对数据库中数据的多种效力功能(复复制、重组、检测等制、重组、检测等)。3、D

55、BMS提供的言语提供的言语数据定义言语数据定义言语数据支配言语数据支配言语数据控制言语数据控制言语数据库设计根底数据库设计根底数据库系统的根本概念数据库系统的根本概念4、数据库系统、数据库系统 DBS由由DB、DBMS、数据库管理员、数据库管理员(DBA)、硬件、硬件平台、软件平台组成。平台、软件平台组成。5、数据库系统的根本特点、数据库系统的根本特点数据的集成性数据的集成性数据的高共享性低冗余性数据的高共享性低冗余性数据的独立性数据的独立性数据一致管理和控制数据一致管理和控制6、数据库系统的三级方式、数据库系统的三级方式概念方式：概念方式：数据库中全局数据的逻辑描画，与详细的数据库中全局数据

56、的逻辑描画，与详细的软硬件环境无关。软硬件环境无关。外方式：外方式：也叫用户方式，是用户的数据视图。也叫用户方式，是用户的数据视图。内方式：内方式：也叫物理方式，描画数据库中数据的存储也叫物理方式，描画数据库中数据的存储构造和存取方式。构造和存取方式。数据库设计根底数据库设计根底数据模型数据模型1、三种不同运用层次的数据模型、三种不同运用层次的数据模型概念模型：概念模型：概念数据模型，面向客观世界、面向用户，概念数据模型，面向客观世界、面向用户，与详细的与详细的DBMS无关。无关。数据模型：数据模型：逻辑数据模型，面向逻辑数据模型，面向DBS的模型，着重于数的模型，着重于数据库系统的实现。据库

57、系统的实现。物理模型：物理模型：物理数据模型，面向计算机系统，是数据模物理数据模型，面向计算机系统，是数据模型的物理表示。型的物理表示。2、实体集之间的联络、实体集之间的联络一对一一对一 一对多或多对一一对多或多对一多对多多对多3、E - R模型的图示法模型的图示法实体集表示法：在实体集表示法：在E - R图中用矩形表示实体图中用矩形表示实体集，矩形内注明实体集称号。集，矩形内注明实体集称号。属性表示法：在属性表示法：在E - R图中用椭圆，椭圆中注图中用椭圆，椭圆中注明属性称号。明属性称号。联络表示法：在联络表示法：在E - R图中用菱形表示联络，图中用菱形表示联络，菱形中注明联络称号。菱形

58、中注明联络称号。实体集与属性之间的衔接关系：在实体集与属性之间的衔接关系：在E - R图中图中用衔接两个图形的无向线段表示。用衔接两个图形的无向线段表示。数据库设计根底数据库设计根底数据模型数据模型4、层次模型、层次模型 层次模型的根本构造是树形构造。层次模型的根本构造是树形构造。5、网状模型、网状模型网状模型是一个不加任何条件限制的无向图。网状模型是一个不加任何条件限制的无向图。6、关系模型、关系模型关系模型用二维表表示关系。关系模型用二维表表示关系。二维表有表框架二维表有表框架(关系方式关系方式)和表元组组成。和表元组组成。表框架由表框架由n个命名的属性组成。个命名的属性组成。属性的取值范

59、围称为值域。属性的取值范围称为值域。二维表中可以独一标识元组的最小属性集成二维表中可以独一标识元组的最小属性集成为为“键键(关键字关键字)。二维表中能够有假设干键，称为侯选键二维表中能够有假设干键，称为侯选键(侯选侯选关键字关键字) 。侯选键中选择作为用户运用的称为主键侯选键中选择作为用户运用的称为主键(主关主关键字键字) 。关系框架和关系元组构成关系。关系框架和关系元组构成关系。数据库设计根底数据库设计根底关系代数关系代数1、关系模型的根本操作、关系模型的根本操作插入插入删除删除 修正修正 查询查询2、根本运算、根本运算并运算并运算(插入插入)差运算差运算(删除删除)投影投影(查询查询)选择选择(查询查询) 笛卡尔积笛卡尔积(查询查询)交运算交运算除运算除运算衔接运算衔接运算(有条件的笛卡尔积有条件的笛卡尔积) 自然衔接运算自然衔接运算(公共域等值衔接公共域等值衔接)数据库设计根底数据库设计根底数据库设计与管理数据库设计与管理1、数据库设计、数据库设计数据库设计的根本义务是根据用户的