2011计算机2级公共基础知识考前冲刺培训.ppt

1、计算机等级考试公共基础知识,张玲,第2页,计算机二级考试公共基础知识大纲,数据结构与算法 程序设计基础 软件工程基础 数据库设计基础,这四个方面在试卷中出现的情况是：选择题10个（20分），填空题5个（10分），总分值占到了试卷卷面分的30，是一个不小的比例。,第3页,计算机二级考试公共基础知识试卷分析,第4页,算法 算法的基本概念 2.算法复杂度的概念和意义,一、基本数据结构与算法,数据结构 数据结构的概念 线性表 栈和队列 树与二叉树 查找技术 排序技术,对于等级考试，这个部分的考核重点主要在算法和数据结构的基本概念、二叉树(遍历、结点），还有排序和查找考试中也经常会涉及到。,第5页,算法

2、的定义 对解题方案准确而完整的描述称为算法。,算法是程序设计的核心, 算法的基本概念,算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程(计算的方法)。在这个过程中，无论是形成解题思路(推理实现的算法)还是编写程序(操作实现的算法)，都是在实施某种算法。,例： n个数从大到小进行排序。 有多种排序方法 ，常用的有冒泡排序、选择排序等。,第6页,2 . 算法的基本特征 一个算法应该具有以下五个重要的特征：,有穷性 确定性 输入 输出 可行性,第7页,算法与计算机程序 算法_是一组逻辑步骤 程序用计算机语言描述的算法,3. 算法的表示,INPUT r S=3.

3、14 * r*r PTINT S,问题： 输入园的半径，计算园的面积,一个算法的表示需要使用一些语言形式。 传统的算法-图形法，如“流程图”和N-S图 目前常用的方法-使用伪码描述算法。,第8页,冒泡排序的方法： 1.扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的结果使最大的元素排到表的最后 ； 2.除最后一个元素，对剩余的元素重复上述过程，将次大的数排到表的倒数第二个位置； 3.重复上述过程； 对于长度为n的线性表，冒泡排序需要对表扫描n-1遍。,算法举例：n个数排序,第9页,4. 算法的两个基本要素：,基本运算和操作 算术运算 关系运算 逻辑运算 数据传输,控

4、制结构 顺序 选择 循环,一是对数据对象的运算和操作； 二是算法的控制结构。,算法基本设计方法：列举法、归纳法、递推、递归、减半递推技术、回溯法,第10页,5. 算法评价 评价一个算法优劣的主要标准是算法的执行效率和存储需求： 时间复杂度：执行这个算法所需要的计算工作量 一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量 空间复杂度：执行这个算法所需要的内存空间 算法在执行过程中临时占用的存储空间 时间复杂度它大致等于计算机执行一种简单操作所需的平均时间与算法中进行简单操作的次数的乘积。 一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间、算法中的输入输出

5、数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个部分,第11页,一、算法,对解题方案准确而完整的描述称为算法。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法评价： 时间复杂度：执行这个算法所需要的计算工作量 空间复杂度：执行这个算法所需要的内存空间,第12页,(1) 在计算机中，算法是指_。 A. 查询方法 B. 加工方法 C. 解题方案的准确而完整的描述 D. 排序方法 (2)下列叙述中正确的是 （07年4月） A)算法的效率只与问题的规模有关，而与数据的存储结构无关 B)算法的时间复杂度是指执行算法所需要的计算工作量 C)数据的逻辑结构与存储结构是

6、一一对应的 D)算法的时间复杂度与空间复杂度一定相关 (3)算法的有穷性是指 (08年4月) A）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的 C）算法程序的长度是有限的 D）算法只能被有限的用户使用,(c),(B),算法习题:,(A),第13页,(4) 算法的时问复杂度是指 (2010年3月) A)算法的执行时间 B)算法所处理的数据量 C)算法程序中的语句或指令条数 D)算法在执行过程中所需要的基本运算次数 (5) 算法的空间复杂度是指 (09年9月) A）算法在执行过程中所需要的计算机存储空间 B）算法所处理的数据量 C）算法程序中的语句或指令条数 D）算法在执行过程中

7、所需要的临时工作单元数 (6) 下列叙述中正确的是 (06年9月) A）一个算法的空间复杂度大，则其时间复杂度也必定大 B）一个算法的空间复杂度大，则其时间复杂度必定小 C）一个算法的时间复杂度大，则其空间复杂度必定小 D）上述三种说法都不对,(D) 计算工作量,(A),(D),第14页,计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。,二、数据结构,程序=算法+数据结构,数据结构是指相互有关联的数据元素的集合。 一般来说，人

8、们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。 一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。,第15页,二. 数据结构,数据结构是指相互有关联的数据元素的集合。 数据结构是研究数据和数据之间关系的一门学科，它包括三个方面。（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。,第16页,1. 逻辑结构 数据的逻辑结构是指

9、反映数据元素之间逻辑关系的数据结构。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 例： 1. 一年四季的数据结构 B=(D,R) D=春，夏，秋，冬 R=(春，夏) ,(夏，秋),(秋，冬) 2. 家庭成员的数据结构 B=(D,R) D=父亲，儿子，女儿 R=(父亲，儿子) ,(父亲，女儿),春,夏,秋,冬,数据结构的图形表示,父亲,儿子,女儿,第17页,常见的逻辑结构有： 线性结构、树形结构和图形结构。, 线性结构 结构中的每个元素之间存在一个对一个的关系； 树形结构 结构中的每个元素之间存在一个对多个的关系； 图形结构或网状结构 结构中的每个元

10、素之间存在多个对多个的关系。 其中，树形结构和图形结构统称为非线形结构。数据的逻辑结构可以用二元关系表示，也可以直观地用图形来表示。,第18页,2. 存储结构（物理结构） 计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同。 如：一年四季 家庭成员 计算机存储空间怎样存放？ 存储结构指数据结构在计算机存储空间中的具体实现。 常见的存储结构有： 顺序存储结构 链式存储结构 索引存储结构,只抽象地反映数据元素之间的关系的结构，而不管其存储方式的数据结构称为逻辑结构。 一种数据结构

11、可以根据需要表示成一种或多种存储结构。,第19页,3. 数据的运算 检索 插入 删除 更新 排序,通常，一个数据结构中的元素结点可能是动态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新结点（插入运算），也可以删除某个结点（删除运算），除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改。 在对数据结构的处理过程中，不仅数据结构中结点的个数在动态变化，而且，各数据元素之间的关系也有可能在动态地变化。如：无序表变有序表,数据结构是研究数据和数据之间关系的一门学科，研究以下三方面内容： 数据的逻辑结构 数据的存储结构 数据的运算,第20|92页,常见的数据结构,1.线性表

12、 2.栈和队列 3.树,第21页, 线性表（Linear List）,线性表是由n（n0）个数据元素 a1，a2，ai，an组成的一个有限序列。,简单的线性表,复杂的线性表,记录1 02011001 张三 男,记录2 02011003 李四 女 ,记录3,记录4,第22页,线性表的顺序存储结构,顺序存储结构把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，顺序存储结构只存储结点的值，不存储结点间的关系，结点间的关系由存储单元的邻接关系来体现。,存储地址,2000,2004,2000+4*(i-1),2000+4*(n-1),占4个字节,Loa（ai）=Loa（a1）+L*（i-1）,第i个数

13、的地址,第一个数的地址,L为该类型数所占的字节,线性表的存储结构,线性表的存储结构有两种： 顺序存储结构 链式存储结构,第23页,顺序表的插入运算 顺序表的删除运算,顺序表的插入和删除运算,在线性表顺序存储情况下，要插入或删除一个元素，都会由于数据元素的移动而消耗大量的处理时间，所以这种存储方式对于小线性表或其中数据元素不经常变动的线性表是合适的。,线性表的顺序存储结构称为顺序表。,第24页,线性表的链式存储结构,线性表的链式存储结构称为线性链表。 链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，而且各数据元素的存储顺序也是任意的。各数据元素的先后关系是由各结点的指针域指示。 链式存储结

14、构的每一个存储结点不仅存储结点的值，而且存储结点之间的关系：,第25页,应用举例线性链表的存储结构,设线性表为（a1，a2，a3，a4，a5）,HEAD,3,线性链表的物理状态,线性表的顺序存储结构,注意:1 2 3 此类编号不代表所在的地址单元的地址编码,第26页,单链表的插入运算 单链表的删除运算,线性链表的插入和删除运算,采用链式存储结构，存储空间开销较大，但是进行插入和删除运算不会造成大量元素的移动。,循环链表是加一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点。,第27页,双向链表的存储结构,提问：单向链表的缺点是什么？ 提示：如何寻找结点的直接前趋。 双向链表可

15、以克服单链表的单向性的缺点。 在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。,HEAD,3,1,5,10,双向循环链表,第28页,线性表的存储结构有两种,顺序存储结构,注意： 数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的。 一个逻辑数据结构可以有多种存储结构，且不同的存储结构影响数据处理的效率 。,HEAD,3,链式存储结构,线性表 : a1，a2，a3，a4，a5 ,第29页,2. 栈和队列,栈和队列都是特殊的线性表。 栈（Stack）及其基本运算 队列（Queue）及其基本运算 循环队列及其基本运算,第30页,栈（Stack）是一种特殊的线性表。

16、其特点是插入和删除运算都只能在线性表的一端进行。 栈是按照“先进后出”或“后进先出”的原则组织数据的线性表。 栈的物理存储结构可以用顺序结构，也可以用链表结构。 下面讨论顺序存储结构中栈元素的插入和删除运算。 顺序栈的进栈和出栈运算 栈的基本运算有三种：入栈、退栈和读栈顶元素,在顺序栈中插入和删除运算不需要移动表中其他数据元素。,第31页,队列（Queue）是一种特殊的线性表。其特点是所有的插入都在表的一端进行，所有的删除运算都在表的另一端进行。 队列是按照“先进先出”或“后进后出”的原则组织数据的线性表。 队列的物理存储结构可以用顺序结构，也可以用链式结构。 顺序队列的运算,栈有三种操作：

17、入栈出栈读栈顶元素 队列有三种操作：入队出队读队首元素,例：有入栈元素序列：ABCD，求可能的出栈序列 如是队列又是什么情况呢？,第32页,循环队列 把队列的存储空间在逻辑上看作一个环，当R指向存储空间的末端后，就把它重新置于始端。 循环队列的运算,队列中进行插入的一端称做队尾(rear),进行删除的一端称做队首(front)。,习题：数据结构分为逻辑结构和存储结构，循环队列属于【 】结构。（2005年9月）,答案：存储结构。,第33页,常见数据结构的逻辑结构,线性表 线性结构 栈 是特殊的线性表 队列 也是一种操作受限的特殊的线性表 树 （树型结构） 是一种重要的非线形数据结构,第34页,数

18、据存储结构方面的考题,1：数据的存储结构是指 （2005年4月） A) 存储在外存中的数据 B) 数据所占的存储空间量 C) 数据在计算机中的顺序存储方式 D) 数据的逻辑结构在计算机中的表示 2. 下列叙述中正确的是 （2009年3月） A）栈是“先进先出”的线性表 B）队列是“先进后出”的线性表 C）循环队列是非线性结构 D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构 3. 数据结构分为线性结构和非线性结构，带链的队列属于 。 4. 下列数据结构中，属于非线性结构的是 A）循环队列 B) 带链队列 C) 二叉树 D）带链栈,答案：D。,答案：D。,答案：线性结构。,答案：c,

19、第35页,5。下列叙述中正确的是（ ）。 （2008年9月） A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的 B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构 C）顺序存储结构能存储有序表，链式存储结构不能存储有序表 D）链式存储结构比顺序存储结构节省存储空间,答案：A。,6。下列关于栈的叙述正确的是 （2008年4月） A）栈按“先进先出”组织数据 B)栈按“先进后出”组织数据 C）只能在栈底插入数据 D）不能删除数据,答案：B。,7. 一个队列的初始状态为空。现将元素A，B，C，D，E，F，5，4，3，2，1依次入队，然后再依次退队，则元素退队的顺序为

20、 【1】 。（2010年3月）,答案：A，B，C，D，E，F，5，4，3，2，1,第36页,9. 设某循环队列的容量为50，如果头指针front=45(指向队头元素的前一位置)，尾指针rear=10(指向队尾元素)，则该循环队列中共有 【2】 个元素。 （2010年3月）,8。假设用一个长度为50的数组（数组元索的下标从0到49）作为栈的存储空间，栈底指针bottom指间栈底元素，栈顶指针top指向栈顶元素，如果bottom=49，top=30（数组下标），则栈中具有【 】个元素。 （2009年3月）,答案：19,答案：15,第37页,一个非空的数据结构若满足下面的两个条件，则这种数据结构即为

21、线性结构。 有且仅有一个根结点； 除第一个结点外，每一个结点最多有一个直接前驱结点； 除最后一个结点外，每一个结点最多有一个直接后继结点。,线性结构与非线性结构 线性表、栈和队列都是线性结构 一个数据结构不是线性结构，则称其为非线性结构。,第38页,树型结构是一种重要的非线性结构。 树的概念 二叉树的概念 二叉树的存储 二叉树的遍历,3. 树与二叉树,第39页,树的概念,树的定义：n个结点的有限集。（n=0）,A,B,D,F,E,C,G,H,I,J,K,M,根：only one 若n=0，则称为空树； 否则，当n1时，其余结点被分成m（m0）个互不相交的子集T1，T2，.，Tm，每个子集又是一

22、棵树。由此可以看出，树的定义是递归的。 Question：如何辨别根？,A,只有一个结点的树,第40页,树型结构的常用术语,A,B,D,F,E,C,G,H,I,J,K,M,结点的度 一个结点的子树的个数； Q：结点A、G的度数？ 树的度 树中所有结点度的最大值；Q：右图中树的度？ 终端结点 度为0的结点； Q：图中叶子结点有几个？7 非终端结点 度不为0的结点； Q：图中非终端结点有几个？ 5,孩子结点、双亲结点、兄弟结点、结点的子孙、结点的祖先,第41页,树型结构的常用术语,A,B,D,F,E,C,G,H,I,J,K,M,结点的层次 树中根结点的层次为1，根结点子树的根为第2层，以此类推；

23、Q：图中结点F的层次？ 树的深度 树中所有结点层次的最大值； Q：图中树的深度？ 有序树、无序树 如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。,第42页,二叉树的概念,定义：二叉树是一种有序的树形结构。它与一般树形结构的区别是： 每个结点最多有两棵子树； 子树有左右之分，次序不能任意颠倒。,二叉树的5种基本形态,第43页,二叉树的性质,【性质1】 在二叉树的第i层上最多有2i-1个结点（i1）,第44页,【性质2】深度为h的二叉树最多有2h -1个结点（h 1） 满二叉树：如果一个深度为h的二叉树拥有2h-1个结点，则将它称为满二叉树。 完全二叉树：有

24、一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1n的结点位置一一对应，则称这棵二叉树为完全二叉树。,第45页,满二叉树,完全二叉树,12,13,8,9,10,11,4,5,6,7,1,2,3,完全二叉树是满二叉树 满二叉树也是完全二叉树,第46页,12,13,8,9,10,11,4,5,6,1,2,3,非完全二叉树,深度为4的完全二叉树,8,4,5,6,7,1,2,3,第47页,【性质3】二叉树上叶子结点数比度为2的结点数多1,度为2的结点,叶子结点,第48页,【性质4】具有n个结

25、点的完全二叉树的深度为 log2 (n+1) 其中，log2n 的结果是不大于log2n的最大整数,深度为4的满二叉树,深度为4的完全二叉树,深度为3的完全二叉树具有47 深度为4的完全二叉树具有815 深度为5的完全二叉树具有1531,log2(8+1) = ln9/In2=4 log2 (15+ 1) =In16/In2=4,深度为6的完全二叉树 具有3263 深度为7的完全二叉树 具有64127 深度为8的完全二叉树 具有128255 深度为9的完全二叉树 具有256511 深度为10的完全二叉树具有5121023 深度为11的完全二叉树具有10242047,第49页,1：在深度为7的满

26、二叉树中,叶子结点的个数为（2006年4月） A)32 B)31 C)64 D)63 2：在深度为7的满二叉树中，度为2的结点个数为【 】 。(07年4月） 3：一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为 （07年9月） A）219 B）221 C）229 D）231 4： 某二叉树中度为2的结点有18个，则该二叉树中有 【 】个叶子结点。（2005年4月） 5：一棵二叉树第六层（根结点为第一层）的结点数最多为【 】个。（2005年9月）,树型结构方面的考题,1答案：C。,3答案：A。,5答案：32。,2答案：63。,4答案：19。,第50页,二叉树的存储,在

27、计算机中，二叉树通常采用链式存储结构。,二叉树的存储结点的结构,A,B,D,C,F,G,E,t,第51页,二叉树的遍历,遍历指不重复地访问二叉树中的所有结点。 二叉树的遍历的次序与树型结构上的大多数运算有联系。 遍历的方式有三种 （1）先（前）序遍历（DLR） （2）中序遍历（LDR） （3）后序遍历（LRD）,第52页,二叉树的遍历,遍历指不重复地访问二叉树中的所有结点。 （1）先（前）序遍历（DLR） 若二叉树为空，则结束遍历操作；否则 访问根结点； 先序遍历左子树； 先序遍历右子树。,先序遍历的结果： A B E C F G H D,第53页,（2）中序遍历（LDR） 若二叉树为空，则结

28、束遍历操作；否则 中序遍历左子树； 访问根结点； 中序遍历右子树。 中序遍历的结果： E B A F H G C D （3）后序遍历（LRD） 若二叉树为空，则结束遍历操作；否则 后序遍历左子树； 后序遍历右子树； 访问根结点。 后序遍历的结果： E B H G F D C A,第54页,先序序列：ABDGCEFH 中序序列：DGBAECHF 后序序列：GDBEHFCA,A,B,C,F,H,D,E,G,下图所示的二叉树经过三种遍历得到的顺序分别为？,练习：,根据先序遍历序列，建立二叉树,第55页,1:设二叉树如下： （2010年3月）对该二叉树进行后序遍历的结果为 【3】,树型结构方面的考题

29、2,2: 对如下二叉树（2006年4月） 进行后序遍历的结果为 A) ABCDEF B) DBEAFC C) ABDECF D) DEBFCA,EDBGHFCA,D,A,B,C,F,H,D,G,E,第56页, 查找技术,查找是数据处理的重要内容。 查找指在一个给定的数据结构中查找指定的元素，该元素也称关键字。 若找到了满足条件的结点，称查找成功；否则称查找失败。 衡量一个查找算法的主要标准是查找过程中对关键字进行的平均比较次数。 通常根据不同的数据结构，采用不同的查找方法： 顺序查找 二分查找,第57页,顺序查找,线性表中最简单的查找方法。 方法：从线性表的第一个元素开始，依次将线性表中的元素

30、与关键字进行比较，若相等，则查找成功；若将所有元素都与关键字进行了比较但不相等，则查找失败。 顺序查找法的适用场合： 对线性表中元素的排列次序没有要求； 对线性表的存储结构没有要求，链式结构和顺序结构均可。,第58页,二分查找(折半查找),是一种效率较高的查找方法，但是只适合顺序存储的有序表。 二分查找的方法：首先将关键字与线性表中间位置的结点比较，相等则查找成功；不相等则根据比较结果确定下一步查找应在哪个子表中进行；重复上述过程，直至查找成功或子表长度为0。 二分查找法的适用场合： 线性表中的元素按关键字值递增或递减的次序排列； 线性表采用顺序存储结构。,第59|92页,折半查找算法举例,对

31、给定数列（有序） 3，5，11，17，21，23，28，30，32，50，按折半查找算法，查找关键字值为30的数据元素。 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 第1次： 3，5，11，17，21，23，28，30，32，50 K=30 mid1=（1+10）/2 = 5 ka(mid1)=a(5)=21 第2次： 23，28，30，32，50 mid2 = （6+10） /2 = 8 K=a(mid2)=a(8)=30,low,high,mid,low,high,mid,第60页,练习 假设待查有序（升序）顺序表中数据元素的关键字序列为（8,18,27,42,47,50

32、,56, 68,95,120），用折半查找方法查找关键字值为27的数据元素.,对于长度为n的有序线性表，最坏情况只需比较log2n次。,第61页, 排序技术,排序指将一个无序序列整理成按关键字值递增或递减排列的有序序列。 排序方法中其排序对象一般是顺序存储的线性表。 根据排序序列的规模以及数据处理的要求，可以采用不同的排序方法： 交换类排序法 冒泡排序 快速排序 插入类排序法 简单插入排序 希尔排序 选择类排序法 简单选择排序 堆排序,第62页,冒泡排序,冒泡排序的方法： 扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的结果使最大(或最小)的元素排到表的最后(或最前

33、) ； 除最后(或最前)一个元素，对剩余的元素重复上述过程，将次大(或次小)的数排到表的倒数(或正数)第二个位置； 重复上述过程； 对于长度为n的线性表，冒泡排序需要对表扫描n-1遍。,第63|92页,冒泡排序的方法,设待排数据元素的关键字为（18，20，15，32，4，25），第一趟冒泡排序后的序列状态如图所示： 18 20 15 32 4 25 18 20 15 32 4 25 18 15 20 32 4 25 18 15 20 32 4 25 18 15 20 4 32 25 18 15 20 4 25 32 最大数,第二趟冒泡排序,第64|92页,Q：第二趟冒泡排序后的结果是什么样的？

34、达到了最终的排序目标吗？一共需要多少次能够最后成为有序序列？ Q：你觉得冒泡排序的效率如何？如果是你，你会用什么方法来排序？ 冒泡排序比较简单，当初始序列基本有序时，冒泡排序有较高的效率，反之效率较低。 冒泡排序终止条件: 本趟排序未发生交换，终止排序算法,第65|92页,初始 第一趟 第二趟 第三趟 第四趟 第五趟 序列 排序后 排序后 排序后 排序后 排序后 26 18 18 18 18 9 18 26 26 26 9 15 32 32 32 9 15 18 54 47 9 15 26 47 9 15 32 9 15 47 15 54,设待排数据元素的关键字为（26,18,32,54,47

35、,9,15 ),冒泡排序法，需要比较的次数为n(n-1)/2；,第66页,选择排序,选择排序的方法： 扫描整个线性表，从中找出最小的元素，与第一个元素交换； 除第一个元素，对剩下的子表采用相同的方法找出次小的数，与第二个数交换； 重复上述过程； 对于长度为n的线性表，选择排序需要对表扫描n-1遍。,简单选择排序法,最坏情况需要n(n-1)/2次比较；,第67|92页,初态： 15，14，22，30，37，15，11 第一趟： 11 14，22，30，37，15，15 第二趟： 11，14 22，30，37，15，15 第三趟： 11，14，15 30，37，22，15 第四趟： 11，14，1

36、5，15 37，22，30 第五趟： 11，14，15，15，22 37，30 第六趟： 11，14，15，15，22，30 37 有序序列,例：设待排数据元素的关键字为（15，14，22，30，37，11），每一趟排序后的序列状态如图所示：,第68页,排序法小结：,简单选择排序法,最坏情况需要n(n-1)/2次比较； 冒泡排序法, 最坏情况需要n(n-1)/2次比较； 希尔排序法, 最坏情况需要O(n1.5)次比较； 堆排序法, 最坏情况需要O(nlog2n)次比较；,第69页,排序查找方面的考题：,(1) 对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是（2005

37、年4月） A) 冒泡排序为n/2 B) 冒泡排序为n C) 快速排序为n D) 快速排序为n(n-1)/2 (2)在长为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为_。（06年9月） A）、63 B）、64 C）、6 D）、7 (3) 下列数据结构中，能用二分法进行查找的是（2005年9月） A）顺序存储的有序线性表 B）线性链表 C）二叉链表 D）有序线性链表 (4) 下列排序方法中，最坏情况下比较次数最少的是（09年3月） A）冒泡排序 B）简单选择排序 C）直接插入排序 D）堆排序,D,B,A,D,第70页,第二章 程序设计基础,内容： 1. 程序设计方法与风格。 2. 结

38、构化程序设计。 3. 面向对象的程序设计方法，对象，方法，属性及继承与多态性。,第71页,1结构化程序设计,结构化程序设计方法的四条原则是： 1. 自顶向下； 2. 逐步求精； 3. 模块化； 4. 限制使用goto语句。 结构化程序的基本结构和特点：（1）顺序结构： 简单的程序设计，最基本、最常用的结构；（2）选择结构（分支结构）： 包括简单选择和多分支选择结构，（3）重复结构（循环结构）： 可根据给定条件，判断是否需要重复执行某一相同程序段。,第72页,2面向对象的程序设计,对象是面向对象方法中最基本的概念。 对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，由一组表示其静

39、态特征的属性和它可执行的一组操作组成。 属性即对象所包含的信息 操作描述了对象执行的功能，操作也称为方法或服务。,第73页,类是指具有共同属性、共同方法的对象的集合。 所以类是对象的抽象，对象是对应类的一个实例。 消息是一个实例与另一个实例之间传递的信息。消息的组成包括 （1）接收消息的对象的名称； （2）消息标识符，也称消息名； （3）零个或多个参数。 继承是指能够直接获得已有的性质和特征，而不必重复定义他们。 单继承指一个类只允许有一个父类 多重继承指一个类允许有多个父类。 多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象。,第74页,程序设计基础方面的考题,1.符合结构化

40、原则的三种基本控制结构是：选择结构、循环结构和【 】 . (2009年3月) 2. 下列选项中不属于结构化程序设计原则的是（2009年9月） A) 可封装 D) 自顶向下 C) 模块化 D) 逐步求精 3. 以下叙述中正确的是。（2010年3月） A）程序设计的任务就是编写程序代码并上机调试 B）程序设计的任务就是确定所用数据结构 C）程序设计的任务就是确定所用算法 D）以上三种说法都不完整 4.在面向对象方法中，类的实例称为 【_】 。（2005年4月） 5.在面向对象方法中, 【_】 描述的是具有相似属性与操作的一组对象。（2006年4月）,（顺序结构）,A,D,对象,类,第75页,第三章

41、 软件工程基础,计算机软件是包括程序、数据及相关文档的完整集合。 软件按功能分为应用软件、系统软件、支撑软件（或工具软件）。,第76页,1.软件工程概念,软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。软件工程包括3个要素：方法、工具和过程。 软件周期：软件产品从提出、实现、使用维护到停止使用退役的过程。软件生命周期三个阶段:软件定义、软件开发、运行维护，主要活动阶段是：（1）可行性研究与计划制定；（2）需求分析；（3）软件设计；（4）软件实现；（5）软件测试；（6）运行和维护。,第77页,2结构化分析方法,结构化分析方法：着眼于数据流，自顶向下，逐层分解

42、，建立系统的处理流程，以数据流图和数据字典为主要工具,建立系统的逻辑模型。 结构化分析的常用工具 （1）数据流图； （2）数据字典； （3）判定树；判定表。 （4）软件需求规格说明书,第78页,3结构化设计方法,软件设计包括：总体设计与详细设计 在程序结构中各模块的内聚性越强，则耦合性越弱。优秀软件应高内聚，低耦合。 常见的过程设计工具有： 图形工具（程序流程图,N-S,PAD） 表格工具（判定表） 语言工具（PDL伪码）,第79页,程序流程图,N-S图,PAD图,第80页,4软件测试,软件测试的目的：发现错误而执行程序的过程。 软件测试方法：静态测试： 包括代码检查、静态结构分析、代码质量度

43、量。不实际运行软件，主要通过人工进行。动态测试： 是基本计算机的测试，主要包括白盒测试方法和黑盒测试方法 软件测试过程一般按4个步骤进行：单元测试、集成测试、验收测试（确认测试）和系统测试。,第81页,5 程序的调试,程序调试的任务是诊断和改正程序中的错误，主要在开发阶段进行。 软件调试 静态调试主要是指通过人的思维来分析源程序代码和排错，是主要的设计手段。 动态调试是辅助静态调试。主要调试方法有：（1）强行排错法；（2）回溯法；（3）原因排除法。,第82页,(1) 下面叙述中错误的是 (2009年3月） A）软件测试的目的是发现错误并改正错误 B）对被调试的程序进行“错误定位”是程序调试的必

44、要步骤 C）程序调试通常也称为Debug D）软件测试应严格执行测试计划，排除测试的随意性 (2) 软件测试可分为白盒测试和黑盒测试。基本路径测试属于【 】测试。(2009年3月） (3) 按照软件测试的一般步骤，集成测试应在_测试之后进行。 (4) 软件工程三要素包括方法、工具和过程，其中，_支持软件开发的各个环节的控制和管理。(2008年9月) (5)软件设计中划分模块的一个准则是(2009年9月） A) 低内聚低耦合 B) 高内聚低耦合 C) 低内聚高耦合 D) 高内聚高耦合,A,软件工程方面的考题：,白盒,单元,过程,B,第83页,(6) 下列叙述中正确的是（2005年9月）A A）软

45、件交付使用后还需要进行维护 B）软件一旦交付使用就不需要再进行维护 C）软件交付使用后其生命周期就结束 D）软件维护是指修复程序中被破坏的指令 (7) 程序流程图中的菱形框表示的是 【2】(2009年9月) 。 (8)软件开发过程主要分为需求分析、设计、编码与测试四个阶段，其中 【3】 阶段产生“软件需求规格说明书。 （2009年9月） (9)下列叙述中正确的是（2006年4月） A)软件测试应该由程序开发者来完成 B)程序经调试后一般不需要再测试 C)软件维护只包括对程序代码的维护 D)以上三种说法都不对,A,逻辑条件,需求分析,D,第84页,(3)软件按功能可以分为：应用软件、系统软件和支

46、撑软件(或工具软件)。下面属于系统软件的是 A)编辑软件 B)操作系统 C)教务管理系统D)浏览器 (4)软件(程序)调试的任务是 A)诊断和改正程序中的错误B)尽可能多地发现程序中的错误 C)发现并改正程序中的所有错误D)确定程序中错误的性质 (5)数据流程图(DFD图)是 A)软件概要设计的工具 B)软件详细设计的工具 C)结构化方法的需求分析工具D)面向对象方法的需求分析工具 (6)软件生命周期可分为定义阶段，开发阶段和维护阶段。详细设计属于 A)定义阶段 B)开发阶段 C)维护阶段 D)上述三个阶段,2010年3月计算机等级考试,B,A,C,B,第85页,数据库设计基础知识点得分表,时

47、间,知识点,第86页,第四章 数据库设计基础,数据：实际上就是描述事物的符号记录。 数据库：是数据的集合，具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序共享。 数据库管理系统：一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等，是数据库的核心。 数据库系统：由数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、硬件平台（硬件）、软件平台（软件）五个部分构成的运行实体。 数据库应用系统：由数据库系统、应用软件及应用界面三者组成。,第87页,数据库系统,88,常见的关系数据库管理系统,小型数据库： Visual FoxP

48、ro （以后简称为VFP） Access (office套件中的一个) Paradox 大型数据库： Oracle Informix SYBASE SQL server 等,第89页,数据库管理系统提供的数据语言：（1）数据定义语言： 负责数据的模式定义与数据的物理存取构建； （2）数据操纵语言： 负责数据的操纵，如查询与增、删、改等；（3）数据控制语言：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等。 数据库管理系统的发展 (1)文件系统阶段：提供了简单的数据共享与数据管理能力，但是它无法提供完整的、统一的、管理和数据共享的能力。 (2)层次数据库与网状数据库系统阶段 ：为统一与

49、共享数据提供了有力支撑。 (3)关系数据库系统阶段,1.数据库系统的基本概念,第90页,关系数据库系统的基本特点： 数据的集成性 数据的高共享性与低冗余性 数据独立性（物理独立性与逻辑独立性） 数据统一管理与控制。 数据库存放数据是按数据所提供的数据模式存放的，具有集成与共享的特点。 数据库系统的三级模式：（1）概念模式（2）外模式（3）内模式 数据库系统的两级映射：（1）概念模式到内模式的映射；（2）外模式到概念模式的映射。,1.数据库系统的基本概念,91,应用,外模式 (用户数据库),应用,外模式 (用户数据库),应用,外模式 (用户数据库),概念模式 (概念数据库),内模式 (物理数据库

50、),数据库,外模式概念模式映射,概念模式内模式映射模式,92,2. 数据模型,数据模型（Data Model）是对客观事物及其关系的数据描述。 数据库中的数据模型可以将复杂的现实世界要求反映到计算机数据库中的物理世界。 现实世界 信息世界 计算机世界 数据模型是数据特征的抽象，从抽象层次上描述了系统的静态特征、动态行为和约束条件。 数据模型所描述的内容包含：数据结构、数据操作和数据约束。,第93页,2. 数据模型,E-R模型的基本概念（1）实体：现实世界中的事物；（2）属性：事物的特性；（3）联系：现实世界中事物间的关系。实体集的关系有一对一、一对多、多对多的联系。 一个班级的学生，学生与学生

51、之间是一对一的关系。 在一所学校，一门课程与学生之间是一对多的关系。 在一所学校，多门课程与多个学生之间是多对多的关系。,94,E-R模型的图示法 用简单的几何图形表示实体集、属性与联系。 (1)实体集表示法 在E-R图中用矩形表表示实体集，在矩形内写上实体集名称。如实体集学生(student)、实体集课程(course) (2)属性表示法 在E-R图中用椭圆形表示属性，在椭圆形内写上该属性名称。如学生有属性：学号(S#)、姓名(Sn)及年龄(Sa)可用如下表示。,student,course,S#,Sn,Sa,95,(3)联系表示法 在E-R图中用菱形(内写上联系名)表示联系。如学生与课程的

52、联系SC,如下图所示： (4)实体集与属性间的联系关系 属性依附于实体集，它们之间有联系关系用无向线段表示。,SC,student,S#,Sn,Sa,96,属性也依附于联系，它们之间也有联系关系，因此也可用无向线段，如联系SC可与学生的课程成绩属性G建立联系并用下图表示。 (5)实体集与联系间的连接关系(也可用无向线段),SC,G,student,course,SC,第97页,E-R模型之间的联接关系： 实体是概念世界中的基本单位， 属性有属性域，每个实体可取属性域内的值。 一个实体的所有属性值叫元组。 E-R模型的图示法： （1）实体集表示法；用长方形 （2）属性表法；用椭圆形 （3）联系表

53、示法。用菱形，(m:n),第98页,层次模型（采用树型结构）,图1-4 层次模型示例,第99页,网络模型（采用无向图型结构）,第100页,关系模型（采用二维表结构）,第101页,关系数据模型,关系模型采用二维表来表示，简称表，由表框架及表的元组组成。一个二维表就是一个关系。 关系数据库系统的特点之一是它建立在数据理论的基础之上，有很多数据理论可以表示关系模型的数据操作，其中最为著名的是关系代数与关系演算。,102,1.关系的数据结构 二维表由表框架与表元组组成。 表框架由n个命名的属性组成(n称为属性元素)。 每个属性有一个取值范围称为值域。 表框架对应了关系的模式，即类型的概念。 每行数据称

54、为元组，一个元组由n个元组分量所组成，每个元组分量是表结构中每个属性的投影值。,103,一个二维表要满足下面7个性质就可称为一个关系。 二维表中元组个数是有限的 二维表中元组均不相同 二维表中元组的次序可任意交换 二维表中元组的分量是不可分割的基本数据项 二维表中属性名各不相同 二维表中属性与次序无关，可任意交换 二维表属性中的分量具有与该属性相同的值域,惟一标识元组的最小属性集称为该表的键(或码)，在VFP表中称为主关键字,104,关系模型的基本运算： 1. 数据查询 查询关系数据库中的数据，一个关系内的查询以及多个关系间的查询。 查询的基本单位为元组分量，先定位后操作。 纵向定位（列指定）

55、 横向定位（行选择） 2. 数据插入 插入一个元组（不定位） 3. 数据删除 删除一个元组（定位、操作） 4. 数据修改 删除需修改的元组再插入修改后的元组,关系操作,105,关系模型的基本运算： 1. 插入 集合的并运算 2. 删除 集合的差(交) 运算 3. 修改 集合的差|并(除)运算。 4. 查询 （投影、选择、笛卡尔积运算）,3.关系代数,集合的并运算,106,由关系R和S通过交运算得到关系T，,107,用于查询的集合运算： （1）投影 对于关系R内的域指定称为投影运算。 S关系就是对R关系指定A和B两个域的结果,R,S,3.关系代数,108,关系代数,（2）选择 选择运算的关系是由

56、关系R中那些满足逻辑条件的元组所组成。 S关系就是R关系中满足A=a的结果,R,S,有了投影和选择运算，我们对一个关系内的任意行、列的数据都可以方便的找到。,109,笛卡尔积是对两个关系的合并操作。 有三个关系R、S和T R关系 n1行, m1列 S关系 n2行， m2列 T关系 行数= n1*n2 列数= m1+m2,R,S,T,（3）笛卡尔积运算,110,笛卡尔积建立两个关系的连接，但得到的关系庞大且数据大量冗余。在实际应用中一般相互连接的关系往往须满足一些条件，所得到的结果也较为简单。 自然连接满足两个关系中有公共域，通过公共域的相等值进行连接。 有三个关系R、S和T R关系 n1行,

57、m1列 S关系 n2行， m2列 T关系 行数(n1或n2中行数多的一个) 列数m1+m2,（4）自然连接运算,111,有三个关系R、S和T，由关系R和S通过运算得到关系T，则使用的运算为,笛卡尔积,R,S,T,自然连接,R,S,T,112,在三个关系R ， S和T如下： 由关系R和S通过自然连接运算得到关系T。,R,S,T,第113页,数据库设计与管理,数据库设计的两种方法：（1）面向数据：以信息需求为主，兼顾处理需求；（2）面向过程：以处理需求为主，兼顾信息需求。 数据库的生命周期： 需求分析阶段 结构析方法和面向对象的方法 数据字典是各类数据描述的集合，包括5个部分：数据项、数据结构、数据流、数据存储、处理过程。 概念设计阶段 分析数据内在语义关系。E-R模型 逻辑设计阶段 物理设计阶段 编码阶段 测试阶段 运行阶段 进一步修改阶段,114,4.4 数据库设计与管理,数据库应用系统(DBAS)中,核心问题是数据库设计。,需求分析,概念设计,逻辑设计,物理设计,编码,测试,运行,进一步修改,分析客户的业务和数据处理需求;,设计数据库的E-R模型图，确认需求信息的正确和完整;,将E-R图转换为多张表，进行逻辑设计,并应用数据库设计的三大范式进行审核;,数据库内模式包括存储结构和存取方法。,重点记,8个阶段,选择具体数据库进行物理实现，并编写代码实现前