计算机office二级公共基础知识点.ppt

1、全国计算机等级考试,二级公共基础知识,公共基础知识,内容： 考试大纲 数据结构与算法 程序设计基础 软件工程基础 数据库设计基础,考试大纲,考试内容 一、基本数据结构与算法1、算法的基本概念；算法复杂度的概念和意义(空间复杂度与时间复杂度)。2、数据结构的定义；数据的逻辑结构和存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3、线性表的定义；线性表的顺序存储结构及其插入删除运算。4、栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5、线性单链表，双向链表与循环链表的结构及其基本运算。6、树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7、顺序查找与二分查找算

2、法；基本排序算法(交换类排序、选择类排序、插入类排序)。,考试大纲,考试内容 二、程序设计基础1、程序设计方法与风格。2、结构化程序设计。3、面向对象的程序设计方法，对象，方法，属性及继承与多态性。,考试大纲,考试内容 三、软件工程基础1、软件工程的基本概念；软件生命周期概念；软件工具与软件开发环境。2、结构化分析方法；数据流图，数据字典，软件需求规格说明书。3、结构化设计方法； 总体设计，详细设计。4、软件测试的方法；白盒测试，黑盒测试，测试用例设计；软件测试的实施；单元测试，集成测试，系统测试。5、程序的调试，静态调试与动态调试。,考试大纲,考试内容 四、数据库设计基础1、数据库的基本概念

3、；数据库，数据库管理系统，数据库系统。2、数据模型；实体联系模型及E-R图，从E-R图导出关系数据模型。3、关系代数运算，包括集合运算及选择、投影、连接运算；数据库规范化理论。4、数据库设计方法和步骤；需求分析、概念设计、逻辑设计和物理设计的相关策略。,考试大纲,考试题型 选择题10 题每题 2 分共 20 分 填空题5 题每题 2 分共 10 分 合计30 分,数据结构与算法,关键考点 算法基本概念及算法复杂度 数据的存储结构 栈和队列 线性链表 二叉树基本概念及其特性 查找技术,第1节 数据结构与算法,算法的基本概念 1、算法算法是指解题方案的准确而完整的描述。注意：算法与数学上的计算方法

4、不是同一个概念。算法要考虑计算机的特点，要考虑计算方法的可行性。算法也不等于程序。算法不考虑具体的机器及编程语言。解决问题时，总是先设计算法，然后进行编程。 2、算法的基本特征可行性确定性有穷性拥有足够的情报算法是一个动态概念，强调实际的执行过程。数学上的计算方法是一个静态概念，注重理论上的正确性。数学上的计算方法是设计算法的基础。,例题： 算法的有穷性是指 A算法程序的运行时间是有限的 B算法程序所处理的数据量是有限的 C算法程序的长度 D算法只能被有限的用户使用,1. 算法的基本概念,第1节 数据结构与算法,算法的基本概念 3、算法的基本要素算法中对数据的运算和操作基本的运算和操作有：算术

5、运算、逻辑运算、关系运算、数据传输。算法的控制结构控制结构决定操作的执行顺序。要求符合结构化原则，强调易读性。 4、算法设计基本方法列举法 列举所有可能情况，检测其中符合条件的结果。归纳法 列举若干特殊情况，分析归纳出一般规律。递推 从已知初始条件出发，逐步推导出中间及最后结果。递归 将复杂问题归结为简单问题，在归结为更简单问题， 。减半递推技术 将问题规模“减半”，并重复该“减半” 的过程。回溯法 分析问题，找出某些线索，沿线索逐步试探。若试探成功，则继续，若试探失败，则回退。直至问题解决。,第1节 数据结构与算法,算法的基本概念 5、算法的时间复杂度指执行算法所需要的计算工作量算法工作量的

6、度量应与计算机、编程语言、编程细节等无关。算法的工作量用算法所执行的基本运算次数衡量。算法工作量是问题规模的函数：算法的工作量= f (n)度量方法有：平均性态分析 计算其加权平均值最坏情况分析 计算其基本运算的最大次数 6、算法的空间复杂度指执行算法所需要的存储空间包括：算法程序所占据的存储空间待处理数据所占据的存储空间算法程序执行中所需要的额外存储空间如果额外存储空间大小不随问题规模变化，则称之为算法原地工作。降低算法的空间复杂度，应从数据的存储空间和额外空间入手。,例题： 下列叙述中正确的是 A算法的效率只与问题的规模有关，而与数据的存储结构无关 B算法的时间复杂度是指执行算法所需要的计

7、算工作量 C数据的逻辑结构与存储结构是一一对应的 D算法的时间复杂度与空间复杂度一定相关 算法的空间复杂度是指 A.算法在执行过程中所需要的计算机存储空间 B.算法所处理的数据量 C.算法程序中的语句货指令条数 D.算法在纸箱过程中所需要的临时工作单元数 4.算法的时间复杂度是指 A.算法的执行时间 B.算法所处理的数据量 C.算法程序中的语句或指令条数 D.算法在执行过程中所需要的基本运算次数,第2节 数据结构的基本概念,计算机处理数据，主要考虑两个方面： 一 、提高数据处理的速度？ 二 、节省存储空间？ 数据结构主要研究三个方面的问题： （1）数据的逻辑结构：各数据元素间所固有的逻辑关系

8、（2）数据的存储结构（物理结构）：各数据元素在计算机中的存储关系 （3）对各种数据结构进行的运算。,数据的逻辑结构只抽象反映数据元素的逻辑关系 数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现,数据结构与算法,数据结构的基本概念 数据结构的表示二元关系表示：两个要素：数据元素的集合D，该集合上的关系R。即：B=(D,R)如：D=春,夏,秋,冬 R=(春,夏),(夏,秋),(秋,冬)图形表示：标有元素值的方框表示结点，有向线段表示逻辑关系。春 夏 秋 冬 线性结构和非线性结构线性结构：一个非空的线性结构有且只有一个根结点，每个结点最多只有一个直接前驱、最多只有一个直接后继。非线性结构：

9、不是线性结构的数据结构。,1.下列叙述中正确的是 A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的 B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构 C.顺序存储结构能存储有序表，链式存储结构不能存储有序表 D.链式存储结构比顺序存储结构节省存储空间 2.下列数据结构中，属于非线性结构的是 A.循环队列B.带链队列 C.二叉树D.带链栈 3.数据的存储结构是指_。 A. 数据所占的存储空间量B. 数据的逻辑结构在计算机中的表示C. 数据在计算机中的顺序存储方式D. 存储在外存中的数据,第3节线性表和顺序存储结构 1 线性表的基本概念 线由一组数据元素组成。是

10、最简单、最常用的一种数据结构. 线性表是一种线性结构。 非空线性表有如下结构特征： （1）有且只有一个根结点 （2）有且只有一个终结节点 （3）除以上二结点外，每个结点有且只有一个前件，也有且只有一个后件。,2 线性表的顺序存储结构 具有如下特点逻辑相临，物理相临 （1）线性表中所有元素所占的存储空间是连续的。 （2）数据元素在存储空间中是按逻辑顺序依次存放的。,张三 70 70,李四 65 90,王五 68 80,线性表的顺序存储结构是一种随机存取的存储结构 。可随机访问任意一个结点,3 线性表的插入运算,14,3、线性表的插入运算,14,3、线性表的插入运算,14,3、线性表的插入运算,1

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

12、他元素； 2 如果删除第1个元素，则需要移动所有的元素。 3 在一般情况下，若要删除第i个元素，则原来第i个元素之后的所有元素都必须依次往前移动一个位置。 平均要移动表中一半的元素。 算法的平均时间复杂度为O(n).,结论： 线性表顺序存储，插入或删除一个元素，效率很低，特别是线性表比较大的情况，由于数据元素的移动而消耗较多的处理时间。 线性表的顺序存储结构对于小线性表或者元素不常变动的线性表来说是合适的，因为顺序存储结构比较简单。,对线链表性表，描述正确的是（） A 存储空间不一定连续，且各元素的存储顺序是任意的 B存储空间不一定连续， 且前件元素一定存储在后件元素前面 C存储空间必须连续，

13、 且前件元素一定存储在后件元素后面 D存储空间必须连续，且各元素的存储顺序是任意的,数据结构与算法,线性链表 1、链式存储方式 结点由两部分组成：数据域(存储数据)、指针域(指向其前件或后件)。 数据结构的存储空间可以不连续，存储顺序与逻辑关系可以不一致。 链式存储方式既可以用来表示线性结构，也可以表示非线性结构。 2、线性链表线性表的链式存储结构称为线性链表。(栈的链式存储结构称为链栈、队列的链式存储结构称为链队列)常用的线性链表有：单链表 (一个指针域，指向直接后继)双向链表 (两个指针域，指向直接后继及后继) 循环链表 (所有结点的指针构成循环链) 3、线性链表的基本运算查找：在线性链表

14、中查找指定元素。插入：在线性链表中插入新结点。删除：在线性链表中删除指定结点。,例题： 1.线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的 链式 存储结构。 2.下列叙述中正确的是 A.线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的 B.线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构 C.线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构 D.上述三种说法都不对,3.线性表的顺序存储结构和线性表的链式存储结构分别是_。A. 顺序存取的存储结构、顺序存取的存储结构B. 随机存取的存储结构、顺序存取的存储结构C. 随机存

15、取的存储结构、随机存取的存储结构D. 任意存取的存储结构、任意存取的存储结构4.用链表表示线性表的优点是_。A. 便于插入和删除操作B. 数据元素的物理顺序与逻辑顺序相同C. 花费的存储空间较顺序存储少D. 便于随机存取 5.在单链表中，增加头结点的目的是_。A. 方便运算的实现B. 使单链表至少有一个结点C. 标识表结点中首结点的位置D. 说明单链表是线性表的链式存储实现,数据结构与算法,栈及其基本运算 1、栈栈(stack)是限定在一端进行插入和删除的线性表允许进行插入或删除的一端称为栈顶。不允许进行插入或删除的另一端称为栈底。其特点为“先入后出”(FILO)或“后入先出”(LIFO)。(

16、记忆作用)通常设置指针top指向栈顶，指针bottom指向栈底。 2、栈的顺序存储结构栈的各个数据元素按其逻辑顺序依次连续存储。由于插入删除操作只能在栈顶一端进行，所以不需要移动数据元素。 3、栈的基本运算入栈：在栈顶位置插入新元素。出栈：取出栈顶位置的元素。读栈顶元素：读出栈顶位置的元素。“上溢”：入栈时堆栈已满。“下溢”：出栈时堆栈已空。,第4节 栈和队列 1 栈及其运算 栈是限定在一端进行插入与删除的线性表。 入栈原则：先进后出，后进先出。,栈顶,栈底,6 4,入栈（插入数据）,栈顶,栈底,6,栈顶,栈底,入栈（插入数据）,栈顶,栈底,出栈（删除数据）,栈顶,栈底,出栈（删除数据）,栈顶

17、,栈底,出栈（删除数据）,2 栈的特点,1 栈顶元素总是最后被插入的元素，也是最早被删除的元素。 2 栈底元素总是最早被插入的元素，也是最晚被删除的元素。 3 栈具有记忆作用。 4 在顺序存储结构下，栈的插入与删除运算不需要移动表中其他数据。 5 栈顶指针，top动态反映了栈中元素的变化情况。 6 栈和线性表实现方法类似顺序和链接,下列关于栈的描述正确的是（）A 在栈中只能插入元素而不能删除元素 B 在栈中只能删除元素而不能插入元素 C 栈是特殊的线性表，只能在一端插入或删除元素 D 栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素,下列关于栈的描述中错误的是（） A 栈是先进后出的线

18、性表 B 栈只能顺序存储 C 栈具有记忆作用 D 对栈的插入与删除操作中，不需要改变栈底指针,0809： 一个栈的初始状态为空，现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则出栈序列是_。 A) 12345ABCDE B) EDCBA54321 C) ABCDE12345 D) 54321EDCBA,1 若进栈序列为1，2，3，4，进栈过程中可以出栈，则下列不可能的一个出栈序列是（ ） A 1，4，3，2 B 2，3，4，1 C 3，1，4，2 D 3，4，2，1 2 若进栈序列是1，2，3，4，假定进栈和出栈可以穿插进行，则可能的出栈序列是（） A 2，4，1，3

19、 B 3，1，4，2 C 3，4，1，2 D 1，2，3，4,数据结构与算法,队列及其基本运算 1、队列队列(queue)是限定在一端进行插入另一端进行删除的线性表允许进行插入的一端称为队尾。允许进行删除的另一端称为队头。其特点为“先入先出”(FIFO)或“后入后出”(LILO)。(先来先服务)通常设置指针rear指向队尾，指针front指向队头。 2、队列的顺序存储结构队列的各个数据元素按其逻辑顺序依次连续存储。由于插入删除操作只能在队列的两端进行，所以不需要移动数据元素。 3、队列的基本运算在实际应用中常常使用循环队列。入队：在队尾位置插入新元素。 出队：取出队头位置的元素。 “上溢”：入

20、队时队列已满。“下溢”：出队时队列已空。,2 队列及其运算 允许在一端进行插入、而在另一端进行删除的 线性表。 即“先进选出，后进后出”的原则,Front头,Rear尾,入队（插入数据）,Rear尾,2 队列及其运算 允许在一端进行插入、而在另一端进行删除的 线性表。 即“先进先出，后进后出”的原则,入队（插入数据）,Front头,2 队列及其运算 允许在一端进行插入、而在另一端进行删除的 线性表。 即“先进先出，后进后出”的原则,入队（插入数据）,Rear尾,Front头,2 队列及其运算 允许在一端进行插入、而在另一端进行删除的 线性表。 即“先进先出，后进后出”的原则,出队（删除数据）,

21、Rear尾,Front头,2 队列及其运算 允许在一端进行插入、而在另一端进行删除的 线性表。 即“先进先出，后进后出”的原则,出队（删除数据）,Rear尾,Front头,栈和队列的共同点是（ ） A 都是先进先出 B 都是后进先出 C 只允许在端点处插入和删除元素 D 没有共同点,Rear尾,Front头,下列叙述中正确的是（） B 栈与队列是非线性结构 C 线性链表是非线性结构 D 二叉树是线性结构,下列关于队列的叙述中正确的是（） A 在队列中只能插入数据 B 在队列中只能删除数据 D 队列是先进后出的线性表,出队（删除数据）,C 队列是先进先出的线性表,A 线性表是线性结构,Rear尾

22、,Front头,例题： 1. 设某循环队列的容量为50，头指针front=5（指向队头元素的前一位置），尾指针rear=29（指向队尾元素），则该循环队列中共有 24 个元素。 实现循环队列时，头指针指向第一个元素的前一个空间，尾指针指向最后一个元素。因此，此时队列中6、7、829这24个空间存有元素。,5,6,7,29,50,1,5,6,7,29,50,1,数据结构与算法,树的基本概念 1、树树是一种简单的非线性结构。元素间的关系具有明显的层次结构。 2、相关的术语根结点叶节点父结点子结点子树结点的度树的度树的深度,数据结构与算法,二叉树 1、二叉树的特点非空二叉树只有一个根结点。每个结点最

23、多有左右两棵子树。 2、二叉树的基本性质 第 k 层上最多有 2 k-1个结点 深度为 m 的二叉树最多有 2m-1个结点 任何二叉树叶结点总比度为 2 的节点多一个 n 个节点的二叉树的深度为 log2n+1 3、满二叉树 4、完全二叉树 5、二叉树的遍历 先序遍历 中序遍历 后序遍历 ABDEGCFHI DBGEACHFI DGEBHIFCA,一棵二叉树第六层的结点数最多为 （ ） 个 某二叉树中，度为2的结点有18个，则有（ ）个叶子结点。一棵完全二叉树有700个结点，该二叉树中有（ ）个叶子结点,32,19,350,N0+N2+N1=700 N1=1 N0=N2+1 2*N2+N1+1

24、=700 N2=349 N0=350,6 二叉树的遍历 遍历是指不重复地访问二叉树中所有结点。,C,遍历分三种方式：前序、中序和后序遍历。,前序遍历法 首先访问根结点,再访问左子树,最后访问右子树，并且在访问左子树和右子树时,仍然是先访问根，再左子树，最后右子树。,例：用前序法访问：,FCADBEGHP,ACBDFEHGP,中序遍历法 首先访问历左子树，再访问根结点，最后中序右子树。 并且在访问左子树和右子树时,仍然是先访问左子树，再访问根，最后是右子树。,例：用中序法访问：,后序遍历 首先后序遍历左子树，再右子树，最后访问根结点，并且在访问左子树和右子树时,仍然是先访问左子树，再访问右子树，

25、最后是根。,ABDCHPGEF,例：用后序法访问：,A bdc,F,HPGe,实例：已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是_。 A. cedba B. acbed C. decab D. deabc,c,e,a,d,b,实例：已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是_。 A. cedba B. acbed C. decab D. deabc 由后序由以知道根节点是C； 而C又在中序的最后，说明 没有右子树。,c,e,a,d,b,实例：已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是

26、_。 A. cedba B. acbed C. decab D. deabc,c,e,a,d,b,设一棵二叉树的中序遍历结果为DBEAFC,前序遍历结果为ABDECF,则后序遍历结果为_。,DEBFCA,如图所示的二叉树，其中序遍历的结果为（ ） A abcdef B abdefc C dbefac D defbca,a,b,c,e,f,d,数据结构与算法,查找技术 1、顺序查找从线性表的第一个元素开始，依次与指定数据比较，若相等则查找成功，若比较的所有元素都不相等，则查找失败。最坏情况的比较次数为表长n，平均情况为n/2。无序顺序表的查找只能采用顺序查找的方法。线性表在链式存储时也只能采用顺

27、序查找的方法。 2、二分法查找在顺序存储的线性表为有序的情况下，可以使用二分法查找。方法为：将待查数据与线性表的中间项比较：若相等，则查找成功；若小于，则在线性表的前半部分进行二分法查找；若大于，则在线性表的后半部分进行二分法查找；反复进行直到相等(查找成功)或子表长度为0(查找失败)。 最坏情况的比较次数为log2n,数据结构与算法,排序技术 1、交换类排序起泡排序最坏情况下的比较次数为 n(n-1)/2 。 快速排序最坏情况下的比较次数为 n(n-1)/2 。 2、插入类排序简单插入排序最坏情况下的比较次数为 n(n-1)/2 。 希尔排序最坏情况下的比较次数为 O( n 1.5) 。 3

28、、选择类排序简单选择排序最坏情况下的比较次数为 n(n-1)/2 。堆排序最坏情况下的比较次数为 O( n log2n) 。,数据结构与算法,本章重点 1、算法是问题处理方案正确而完整的描述，算法的效率与数据的存储结构有密切的关系。 2、数据的逻辑结构在计算机中的表示(存储方式)称为数据的存储结构(物理结构)。一种逻辑结构可以有多种存储结构。 3、在长度为 n 的顺序表中，插入或删除一个元素平均需要移动一半元素。 4、栈是特殊的线性表，具有记忆作用。特点是“先进后出(后进先出)”。栈顶指针动态反映了栈中元素的变化情况。 5、队列是特殊的线性表。特点是“先进先出(后进后出)”。队头和队尾指针动态

29、地反映了队列中元素的变化情况。 6、线性链表是线性表的链式存储结构。在线性链表中，各元素节点的存储空间可以不连续，存储顺序也可以与逻辑顺序不一致。线性链表的插入删除操作不需要移动数据元素。 7、二叉树是一种非线性结构。主要性质有：第k层上最多有 2 k-1 个结点 深度为 m 时，最多有2 m 1 个结点度为0的结点比度为2的多一个 深度至少为 log2n +1,数据结构与算法,本章重点 8、满二叉树是二叉树的特殊形态，满二叉树的各层结点都达到最大值，叶结点只出现在最后一层。 9、完全二叉树是二叉树的特殊形态，完全二叉树除最后一层外，各层结点都达到最大值，叶结点只出现在最后两层。满二叉树属于完

30、全二叉树。 10、根据扫描根结点的顺序，按照先左后右的原则，遍历二叉树有三种方法：前序遍历、中序遍历、后序遍历。 11、在长度为 n 的线性表中进行顺序查找，最坏情况需要比较 n 次。 12、在长度为 n 的线性表中进行对分查找，最坏情况需要比较 log2n 次。但对分查找只适用于有序顺序表。 13、在冒泡排序、快速排序、简单插入排序、选择排序的方法中，最坏情况下需要比较的次数为 n(n-1)/2 。,68,程序设计基础,关键考点 结构化设计的原则 面向对象方法的基本概念,69,程序设计基础,程序设计方法与风格 1、程序设计方法就程序设计的方法和技术的发展而言主要经历了结构化程序设计和面向对象

31、程序设计两个阶段 2、程序设计风格程序设计风格是指编写程序时所表现出来的特点、习惯和逻辑思路。程序设计风格会深刻影响软件的质量和可维护性，良好的程序设计风格可以使程序的结构清晰合理，使程序代码便于维护。程序设计风格的主导：“清晰第一，效率第二”。主要因素：源程序文档化数据说明的方法语句的结构输入和输出,70,程序设计基础,结构化程序设计 1、结构化程序设计要求把程序的结构限制为顺序、选择和循环三种基本结构。 2、结构化程序设计的原则自顶向下先总体后细节，先全局后局部。逐步求精对复杂问题设计子目标过度，逐步细化。模块化将复杂问题分解为若干简单问题。限制使用GOTO语句防止造成程序逻辑结构混乱。

32、3、三种基本结构顺序结构 选择结构循环结构 4、特点所有控制结构由三种基本结构组成各个模块单入口单出口模块的内聚性强 模块间的偶合性低,71,程序设计基础,面向对象的程序设计 1、面向对象面向对象方法的本质，是从客观世界固有的事物出发来构造系统，用现实生活中常用的思维方法来描述客观事物，是系统中的对象及对象间的关系能如实反映事物及其关系。 2、主要优点与人类习惯的思维方法一致稳定性好可重用性好易于开发大型软件产品可维护性好 3、基本概念对象类和实例消息继承多态性,例： 下列叙述中，不符合良好程序设计风格要求的是 A.程序的效率第一，清晰第二 B.程序的可读性好 C.程序中要有必要的注释 D.输

33、入数据前要有提示信息 信息隐蔽的概念与下述哪一种概念直接相关_。A. 软件结构定义B. 模块独立性C. 模块类型划分D. 模拟耦合度,1. 程序设计方法与风格,例： 在结构化程序设计中，模块划分的原则是 A各模块应包括尽量多的功能 B各模块的规模应尽量大 C各模块之间的联系应尽量紧密 D模块内具有高内聚度，模块间具有低耦合度 为了使模块尽可能独立，要求 A模块的内聚程度要尽量高，且各模块间的耦合程度要尽量强 B模块的内聚程度要尽量高，且各模块间的耦合程度要尽量弱 C模块的内聚程度要尽量低，且各模块间的耦合程度要尽量弱 D模块的内聚程度要尽量低，且各模块间的耦合程度要尽量强 3. 结构化程序设计

34、主要强调的是 A程序的规模B程序的效率 C程序设计语言的先进性D程序的易读性 4. 结构化程序设计的基本原则不包括 A.多态性B.自顶向下C.模块化D.逐步求精 多态性是面向对象程序设计语言的特点。,2. 结构化程序设计,3. 面向对象的程序设计方法、对象、方法、属性及继承与多态性,1.下列选项中不属于面向对象程序设计特征的是 A继承性B多态性 C类比性D封装性 2.在面向对象方法中，实现信息隐蔽是依靠 A.对象的继承B.对象的多态 C.对象的封装D.对象的分类 3.面向对象方法中，集成是指 A.一组对象所具有的相似性质B.一个对象具有另一个对象的性质 C.各对象之间的共同性质D.类之间共享属

35、性和操作的机制 4.下面对对象概念描述错误的是_。A. 任何对象都必须有继承性B. 对象是属性和方法的封装体C. 对象间的通讯靠消息传递D. 操作是对象的动态性属性,5.在面向对象方法中，一个对象请求另一对象为其服务的方式是通过发送_。A. 调用语句 B. 命令C. 口令D. 消息,76,程序设计基础,本章重点 1、程序设计并不等于编程，编程只是程序设计过程中的一小步。 2、结构化程序设计要求把程序的结构限制为顺序、选择、循环三种基本结构。 3、模块化设计是指把一个大程序按人们能理解的大小规模进行分解。划分模块的基本原则是使每个模块都易于理解。在按功能划分模块时，要求各模块功能尽量单一，各模块

36、之间的联系尽量的少。 4、客观世界是由实体及其联系所组成的。客观世界中的实体称为问题域的对象。 5、类描述的是具有相似性质一组对象。一个对象称为类的实例。 6、允许作用于某个对象上的各种操作称为方法。 7、消息是用来请求对象执行某一处理或回答某些信息的要求。 8、继承是表示类之间的相似性的一种机制。 9、封装是一种信息隐蔽机制，目的是将对象的使用者与对象的设计者分开。用户只需了解对象封装界面上的信息，不必知道内部的具体细节。,77,软件工程基础,关键考点 软件定义与特点 软件开发过程的过程化原则 结构化分析方法 结构化设计方法 软件测试技术与方法 程序调试基本概念,78,软件工程基础,软件工程

37、基本概念 1、软件软件是包括程序、数据及相关文档的完整集合。 2、软件的特点抽象性可大量拷贝无磨损及老化问题受计算机系统限制(移植问题)复杂性高成本昂贵开发过程涉及诸多社会因素 3、软件工程软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。三个要素方法：完成软件工程项目的技术手段。工具：支持软件的开发、管理、文档生成。过程：支持软件开发各个环节的管理、控制。目标：在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可适应性、可追踪性、可互操作性满足用户要求的软件产品。,79,软件工程基础,软件开发过程的过程化原则 1、软件工程过程 为获得

38、软件产品，在软件工具支持下的一系列软件工程活动。Plan软件规格说明。Do软件开发。Check软件确认。Action软件演进。 使用适当的资源，为开发软件进行的一组开发活动，在过程结束时将用户要求转化为软件产品。软件工程过程应确定方法使用的顺序、要求交付的文档资料、为保证质量与适应变化所需要的管理、软件开发各阶段要完成的任务。 2、软件生命周期 定义阶段可行性研究及项目计划需求分析 开发阶段概要设计详细设计实现测试 维护阶段使用维护退役,80,软件工程基础,结构化分析方法 在系统分析阶段，结构化分析方法用来对系统进行逻辑设计。 1、需求分析需求分析的任务是发现需求、求精、建模和定义需求。 常见

39、的需求分析方法：结构化分析方法 面向对象的分析方法 2、结构化分析方法 结构化分析就是使用数据流图(DFD)、数据字典(DD)、结构化英语、判定表和判定树等工具，来建立一种被称为结构化规格说明的目标文档。 结构化分析方法的实质是着眼于数据流的、自顶向下逐层分解的、建立系统的处理流程，它以数据流图和数据字典为主要工具，建立系统的逻辑模型。 3、 软件需求规格说明书是需求分析阶段的最后成果，是软件开发的重要文档之一。软件需求规格说明书把软件计划中确定的软件范围加以展开，制定出完整的信息描述、详细的功能说明、恰当的检验标准、其他与要求有关的信息。,81,软件工程基础,结构化设计方法 1、软件设计软件

40、设计是把软件需求转换为软件表示的过程。从技术角度：软件设计包括结构设计、数据设计、接口设计、过程设计。从工程角度：软件设计包括概要设计、详细设计。软件设计的基本原理包括：抽象、模块化、信息隐蔽、模块独立性 2、概要设计概要设计的基本任务：系统结构设计数据结构设计编写设计文档设计文档评审结构图是软件结构设计的常用工具。 3、详细设计详细设计的任务，是为软件结构图中的每一个模块确定算法和局部数据结构，用某种选定的工具表示算法和数据结构的细节。常见的设计工具：图形工具：流程图、N - S、PAD、HIPO表格工具：判定表语言工具：PDL(伪码),82,软件工程基础,软件测试 1、测试软件测试的目标是

41、在精心控制的环境下执行程序，以发现程序中的错误，给出程序可靠性的鉴定。测试不是为了证明程序是正确的，目的是设法暴露程序中的错误和缺陷。测试只能说明程序有错，不能证明程序无错。程序不能100%可靠。 2、测试方法程序的静态分析程序的动态分析自动测试工具 3、测试层次模块测试(单元测试)整体测试(集成测试)又分为 功能测试 和 验收测试 两种。 4、白盒法根据对程序内部逻辑结构的分析来导出测试用例。 5、黑盒法不考虑程序的内部结构特征，根据程序功能导出测试用例。,83,软件工程基础,程序调试 1、调试与测试 测试的目的是发现错误，评价可靠性；调试的目的是发现错误的位置，改正发现的错误。 测试揭示设

42、计人员的过失，由非设计人员承担；调试帮助设计人员改正错误，由设计人员自己承担。 测试是机械的、强制的、严格的、可预测的；调试要求随机应变、联想、经验、智力，并要求自主地完成。 测试发现的错误可立即进行调试改正，然后还必须再进行测试。 调试用例与测试用例可以一致也可以不一致。 2、调试方法 强行排错法 回溯法 原因排除法,例题： 1. 需求分析阶段的任务是确定 A软件开发方法B软件开发工具 C软件开发费用D软件系统功能 2. 算法的有穷性是指 A算法程序的运行时间是有限的 B算法程序所处理的数据量是有限的 C算法程序的长度 D算法只能被有限的用户使用 下列叙述中正确的是 A算法的效率只与问题的规

43、模有关，而与数据的存储结构无关 B算法的时间复杂度是指执行算法所需要的计算工作量 C数据的逻辑结构与存储结构是一一对应的 D算法的时间复杂度与空间复杂度一定相关 软件的生命周期可分为多个阶段，一般分为定义阶段、开发阶段、维护阶段。编码和测试属于 开发 阶段。 4. 软件工程三要素包括方法、工具、过程，其中 过程 支持软件开发的各个环节的控制和管理。 方法提供了“如何做”的技术；工具支持软件的开发、管理、文档生成；过程支持软件开发的各个环节的控制和管理。,1. 软件工程、软件生命周期、软件工具与开发环境,5.软件是指 A.程序B.程序和文档 C.算法加数据结构D.程序、数据与相关文档的完整集合

44、6.下面描述中，不属于软件危机表现的是 A.软件过程不规范B.软件开发生产率低 C.软件质量难以控制D.软件成本不断提高 7.软件生命周期是指 A.软件产品从提出、实现、使用维护到停止使用退役的过程 B.软件从需求分析、设计、实现到测试完成的过程 C.软件的开发过程 D.软件的运行维护过程 8.在软件开发中，下面任务不属于设计阶段的是_。A. 数据结构设计B. 给出系统模块结构C. 定义模块算法D. 定义需求并建立系统模型 9.在软件生命周期中，能准确地确定软件系统必须做什么和必须具备哪些功能的阶段是_。(D)A. 概要设计B. 详细设计C. 可行性分析D. 需求分析,2. 结构化分析方法，数

45、据流图，数据字典，软件需求规格说明书,程序流程图是人们对解决问题的方法、思路、算法的一种描述。其中： 图框各种操作的类型 图框中的文字和符号操作的内容 流程线操作的先后顺序 带箭头的线段数据流（数据流程图中），控制流（程序流程图中） 例题： 1.程序流程图中带有箭头的线段表示的是 A.图元关系B.数据流C.控制流D.调用关系 2.数据流图用于抽象描述一个软件的逻辑模型，数据流图由一些特定的图符构成。下列图符名标识的图符不属于数据流图合法图符的是_。(A) A. 控制流 B. 加工C. 数据存储D. 源和潭,例题： 3.为了避免流程图在描述程序逻辑时的不灵活性，提出了用方框图来代替传统的程序流程

46、图，通常也把这种图称为 APAD图BN-S图 C结构图D数据流图 4.在结构化分析使用的数据流图（DFD）中，利用 数据字典 对其中的图形元素进行确切解释。 数据字典用来定义数据流图中各个成分的具体含义。 5.在软件开发中，在需求分析阶段可以使用的工具是 A.N-S图B.DFD图 C.PAD图 D.程序流程图 数据流图简称DFD，采用图形方式来表达系统的逻辑功能、数据在系统内部的逻辑流向和逻辑变换过程，是结构化系统分析方法的主要表达工具及用于表示软件模型的一种图示方法。 6.软件需求规格说明书应具有完整性、无歧义性、正确性、可验证性、可修改性等特性，其中最重要的是：无歧义性 7.在软件开发中，

47、需求分析阶段产生的主要文档是 A.可行性分析报告B.软件需求规格说明书 C.概要设计说明书D.集成测试计划 需求分析的工作包括：需求获取、需求分析、编写需求规格说明书、需求评审,8.软件需求分析阶段的工作，可以分为四个方面：需求获取、需求分析、编写需求规格说明书以及_。 A. 阶段性报告B. 需求评审C. 总结D. 都不正确,3. 结构化设计方法（总体、详细）,1.软件生命周期分为定义阶段、开发阶段、维护阶段。详细设计属于 A.定义阶段B.开发阶段 C.维护阶段D.上述三个阶段 2.下面描述中，符合结构化程序设计风格的是_。A. 使用顺序、选择和重复（循环）三种基本控制结构表示程序的控制逻辑B

48、. 模块只有一个入口，可以有多个出口(可以有0个入口)C. 注重提高程序的执行效率D. 不使用goto语句（只是限制使用）,例题： 1.下列叙述中正确的是 A.软件测试的主要目的是发现程序中的错误 B.软件测试的主要目的是确定程序中错误的位置 C.为了提高软件测试的效率，最好有程序编制者自己来完成软件测试的工作 D.软件测试是证明软件没有错误 2. 软件测试分为白箱（盒）测试和黑箱（盒）测试。等价类划分法属于 黑箱（盒）测试 。 3.软件测试分为白箱（盒）测试和黑箱（盒）测试。基本路径测试属于 白箱（盒）测试 。 4.在两种基本测试方法中， 白盒 测试的原则之一是帮正所测模块中每一个独立路径至

49、少要执行一次。 5. 测试用例包括输入值集和 输出 值集。 6.检查软件产品是否符合需求定义的过程称为_。 确认测试 B. 集成测试C. 验证测试D. 验收测试,5. 程序的调试,例题： 1.软件调试的目的是 A.发现错误B.改正错误 C.改善软件的性能D.验证软件的正确性 2.下列不属于软件调试技术的是_。A. 强行排错法B. 集成测试法C. 回溯法D. 原因排除法,92,软件工程基础,本章重点 1、软件生命周期分为三个时期共八个阶段：软件定义期：问题定义、可行性研究、需求分析。软件开发期：系统设计、详细设计、编码、测试。软件维护期：运行维护。 2、在系统分析阶段，结构化分析方法用来对系统进

50、行逻辑设计，此时不考虑物理实现的问题，而只考虑“做什么”的问题，系统的物理设计(“如何做”)的问题留在系统设计阶段用结构化设计方法来完成。 3、数据流图有两种典型的结构形式：变换型、事务型。 4、评价模块的独立性的标准有两个：耦合性：表明两个模块间联系的强弱。内聚性：表明模块内部联系是否紧密。内聚性要强，偶合性要弱。 5、软件测试是在精心控制的环境下执行程序，发现程序中的错误，给出程序可靠性的鉴定。 6、测试是程序执行的过程，目的在于发现错误；一个好的测试在于能发现至今未能发现的错误，一个成功的测试是发现了至今未发现的错误。 7、测试发现错误后，可进行调试；调试后的程序还应再测试，以检验调试效

51、果。,93,数据库设计基础,关键考点 数据库系统基本概念 数据模型,94,数据库设计基础,数据库系统的基本概念 1、数据库 DB是数据的集合，具有统一的结构形式并存放于统一的存储介质中，是多种应用数据的集成，可被各个应用程序所共享。 2、数据库管理系统 DBMS数据库的管理机构，系统软件，负责数据组织、操纵、维护、控制、保护等。为数据库构作模式为数据模式的实现提供方法和手段为用户使用提供查询、插入、修改、删除等功能提供对数据库中数据的多种服务功能(复制、重组、检测等)。 3、DBMS提供的语言数据定义语言数据操纵语言数据控制语言,95,数据库设计基础,数据库系统的基本概念 4、数据库系统 DB

52、S由DB、DBMS、数据库管理员(DBA)、硬件平台、软件平台组成。 5、数据库系统的基本特点数据的集成性数据的高共享性低冗余性数据的独立性数据统一管理和控制 6、数据库系统的三级模式概念模式：数据库中全局数据的逻辑描述，与具体的软硬件环境无关。外模式：也叫用户模式，是用户的数据视图。内模式：也叫物理模式，描述数据库中数据的存储结构和存取方式。,96,数据库设计基础,数据模型 1、三种不同应用层次的数据模型概念模型：概念数据模型，面向客观世界、面向用户，与具体的DBMS无关。数据模型：逻辑数据模型，面向DBS的模型，着重于数据库系统的实现。物理模型：物理数据模型，面向计算机系统，是数据模型的物

53、理表示。 2、实体集之间的联系一对一一对多或多对一多对多 3、E - R模型的图示法实体集表示法：在E - R图中用矩形表示实体集，矩形内注明实体集名称。属性表示法：在E - R图中用椭圆，椭圆中注明属性名称。联系表示法：在E - R图中用菱形表示联系，菱形中注明联系名称。实体集与属性之间的连接关系：在E - R图中用连接两个图形的无向线段表示。,97,数据库设计基础,数据模型 4、层次模型 层次模型的基本结构是树形结构。 5、网状模型网状模型是一个不加任何条件限制的无向图。 6、关系模型关系模型用二维表表示关系。二维表有表框架(关系模式)和表元组组成。表框架由n个命名的属性组成。属性的取值范

54、围称为值域。二维表中能够唯一标识元组的最小属性集成为“键”(关键字)。二维表中可能有若干键，称为侯选键(侯选关键字) 。侯选键中选择作为用户使用的称为主键(主关键字) 。关系框架和关系元组构成关系。,98,数据库设计基础,关系代数 1、关系模型的基本操作插入删除修改查询 2、基本运算并运算(插入)差运算(删除)修改 投影(查询)选择(查询) 笛卡尔积(查询)交运算除运算连接运算(有条件的笛卡尔积) 自然连接运算(公共域等值连接),RR RR （ RR ）R” F(R) T=RS RS=R-(R-S) TR=S R| |S R|S,99,数据库设计基础,数据库设计与管理 1、数据库设计数据库设计

55、的基本任务是根据用户的信息需求、处理需求、软硬件环境设计出数据模式。在数据库设计中有两种方法：面向数据的方法以信息需求为主兼顾处理需求。面向过程的方法以处理需求为主兼顾信息需求。数据库设计中一般采用生命周期法。需求分析：用户需求调查，产生需求说明书。概念设计：分析数据的内在关联，产生概念数据模型。逻辑设计：将E R图转换为关系模式，产生逻辑数据模型。物理设计：调整内部结构选择存取路径，产生数据库内模式。 2、数据库管理包括：数据库建立数据库调整数据库重组安全性控制完整性控制故障恢复运行监控,100,数据库设计基础,本章重点 1、数据管理技术的发展分为三个阶段：人工管理、文件管理、数据库管理。

56、2、数据库系统是由操作系统、数据库管理系统和应用程序在一定的硬件支持下所构成的。数据库管理系统(DBMS)是整个数据库系统的核心，它对数据库中的数据进行管理，还作为用户应用与数据库之间的接口。 3、数据库技术的根本目标是要解决数据的共享问题。 4、数据库技术的特点之一是数据的独立性。数据的物理独立性表示数据的物理结构改变不会影响数据库的逻辑结构，不致引起应用程序的变化。数据的逻辑独立性表示数据库总体逻辑结构改变不会影响局部逻辑结构，基于局部逻辑结构的应用程序也不必修改。 5、实体与实体之间的联系归结为三类：一对一联系、一对多联系、多对多联系。 6、在数据库系统中，由于采用的数据模型不同，响应的

57、数据库管理系统(DBMS)也不同。目前常用的有：层次模型、网状模型、关系模型。,101,数据库设计基础,本章重点 7、网状模型和层次模型都属于格式化模型。所谓格式化模型，是指在建立数据模型时，根据应用的需要，事先将数据之间的逻辑关系固定下来(先对数据的逻辑结构进行设计使其结构化)。 8、在关系模型中，把数据看成二维表，每个二维表是一个关系。表中的列成为属性(记录的数据项)，表中的行称为元组，相当于记录。 9、选择运算是在关系中选择满足条件的元组构成新的关系，该新关系是原关系的一个子集，它在关系的行方向上进行运算。 10、投影运算是在关系的某些域上进行操作，它是在关系的列方向上进行运算。 11、数据库设计是指在已有数据库管理系统的基础上建立数据库的过程。 12、数据库设计分为需求分析、概念结构设计、逻辑结构设计、物理结构设计等阶段。 13、E-R图(实体-联系图)是设