计算机级公共基础知识PPT课件

1、第1页计算机二级考试公共基础知识大纲 q 数据结构与算法q 程序设计基础q 软件工程基础q 数据库设计基础这四个方面在试卷中出现的情况是：选择题10个（20分），填空题5个（10分），总分值占到了试卷卷面分的30，是一个不小的比例。 第1页/共132页第2页计算机二级考试公共基础知识试卷分析 章节章节考试时间考试时间数据结构数据结构与算法与算法程序设程序设计基础计基础软件工软件工程基础程基础数据库设数据库设计基础计基础2007年4月10分2分10分8分2007年9月12分4分8分6分2008年4月10分2分8分10分2008年9月10分2分8分10分2009年3月10分2分8分10分2009年

2、9月10分2分8分10分2010年3月10分0分10分10分第2页/共132页第3页 算法的基本概念 2.2.算法复杂度的概念和意义 数据结构的概念 线性表 栈和队列 树与二叉树 查找技术 排序技术 对于等级考试，这个部分的考核重点主要在算法和数据结构的基本概念、二叉树(遍历、结点），还有排序和查找考试中也经常会涉及到。第3页/共132页第4页算法的定义算法的定义算法是程序设计的核心算法是程序设计的核心 算法是在有限步骤内求解某一问题所使用的一组算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过定义明确的规则。通俗点说，就是计算机解题的过程程( (计算的方法

3、计算的方法) )。在这个过程中，无论是形成解题。在这个过程中，无论是形成解题思路思路( (推理实现的算法推理实现的算法) )还是编写程序还是编写程序( (操作实现的算操作实现的算法法) )，都是在实施某种算法。，都是在实施某种算法。例： n个数从大到小进行排序。 有多种排序方法 ，常用的有冒泡排序、选择排序等。第4页/共132页第5页 2 . 算法的基本特征一个算法应该具有以下五个重要的特征：一个算法应该具有以下五个重要的特征：n 有穷性n 确定性n 输入n 输出n 可行性一个算法必须保证执行有限步之后结束；算法的每一步骤必须有确切的定义；一个算法有0个或多个输入，以刻画运算对象的初始情况，所

4、谓0个输入是指算法本身定除了初始条件；一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成 第5页/共132页第6页 算法与计算机程序 算法_是一组逻辑步骤 程序用计算机语言描述的算法INPUT rS=3.14 * r*rPTINT S开始输入R RS=3.14 * R*R输出S S结束问题：输入园的半径，计算园的面积 一个算法的表示需要使用一些语言形式。传统的算法-图形法，如“流程图”和N-S图目前常用的方法-使用伪码描述算法。第6页/共132页第7页冒泡排序的方法：1.扫描整个线性表，逐次对相邻

5、的两个元素进行比较，若为逆序，则交换；第一趟扫描的结果使最大的元素排到表的最后 ；2.除最后一个元素，对剩余的元素重复上述过程，将次大的数排到表的倒数第二个位置；3.重复上述过程；对于长度为n的线性表，冒泡排序需要对表扫描n-1遍。 算法举例：n个数排序第7页/共132页第8页4. 算法的两个基本要素：n 算术运算n 关系运算n 逻辑运算n 数据传输n 顺序n 选择n 循环u一是对数据对象的运算和操作；u二是算法的控制结构。u算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法 第8页/共132页第9页 评价一个算法优劣的主要标准是算法的执行效率和存储需求： 时间复杂度：执行这个

6、算法所需要的计算工作量一般可以用算法在执行过程中所需基本运算的执行次数来度量计算工作量 空间复杂度：执行这个算法所需要的内存空间 算法在执行过程中临时占用的存储空间 时间复杂度它大致等于计算机执行一种简单操作所需的平均时间与算法中进行简单操作的次数的乘积。 一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间、算法中的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个部分第9页/共132页第10页： 时间复杂度：执行这个算法所需要的计算工作量 空间复杂度：执行这个算法所需要的内存空间第10页/共132页第11页(1) 在计算机中，算法是指_。 A. 查

7、询方法 B. 加工方法 C. 解题方案的准确而完整的描述 D. 排序方法(2)下列叙述中正确的是 （07年4月）A)算法的效率只与问题的规模有关，而与数据的存储结构无关B)算法的时间复杂度是指执行算法所需要的计算工作量C)数据的逻辑结构与存储结构是一一对应的D)算法的时间复杂度与空间复杂度一定相关(3)算法的有穷性是指 (08年4月)A）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的 C）算法程序的长度是有限的 D）算法只能被有限的用户使用(c)(B)算法习题:(A)第11页/共132页第12页(4) 算法的时问复杂度是指 (2010年3月)A)算法的执行时间B)算法所处理的数

8、据量C)算法程序中的语句或指令条数D)算法在执行过程中所需要的基本运算次数(5) 算法的空间复杂度是指 (09年9月) A）算法在执行过程中所需要的计算机存储空间B）算法所处理的数据量C）算法程序中的语句或指令条数D）算法在执行过程中所需要的临时工作单元数(6) 下列叙述中正确的是 (06年9月)A）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间复杂度必定小C）一个算法的时间复杂度大，则其空间复杂度必定小 D）上述三种说法都不对(D)计算工作量(A)(D)第12页/共132页第13页 计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据

9、元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。程序=算法+数据结构数据结构是指相互有关联的数据元素的集合。 一般来说，人们不会同时处理特征完全不同且互相之间没有任何关系的各类数据元素，对于具有不同特征的数据元素总是分别进行处理。一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（即联系），这种关系反映了该集合中的数据元素所固有的一种结构。第13页/共132页第14页二. 数据结构数据结构是指相互有关联的数据元素的集合。数据结构是研究数据和数据之间关系的一门学科，它包括三个方

10、面。（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。第14页/共132页第15页1. 逻辑结构逻辑结构 数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。例：1. 一年四季的数据结构 B=(D,R) D=春，夏，秋，冬 R=(春，夏) ,(夏，秋),(秋，冬)2. 家庭成员的数据结构 B=(D,R) D=父亲，儿子，女儿 R=(父亲，儿子) ,(父亲，女儿)春夏秋冬数据结构的图形表示

11、父亲儿子女儿第15页/共132页第16页 常见的逻辑结构逻辑结构有：线性结构、树形结构和图形结构。线性结构树形结构图形结构u 线性结构 结构中的每个元素之间存在一个对一个的关系；u 树形结构 结构中的每个元素之间存在一个对多个的关系；u 图形结构或网状结构 结构中的每个元素之间存在多个对多个的关系。其中，树形结构和图形结构统称为非线形结构。数据的逻辑结构可以用二元关系表示，也可以直观地用图形来表示。第16页/共132页第17页 2. 存储结构（物理结构） 计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定

12、是相同的，而且一般也不可能相同。如：一年四季 家庭成员 计算机存储空间怎样存放？ 存储结构指数据结构在计算机存储空间中的具体实现。常见的存储结构有： 顺序存储结构 链式存储结构索引存储结构 只抽象地反映数据元素之间的关系的结构，而不管其存储方式的数据结构称为逻辑结构。 一种数据结构可以根据需要表示成一种或多种存储结构。第17页/共132页第18页 3. 数据的运算 检索 插入 删除 更新 排序 通常，一个数据结构中的元素结点可能是动态变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新结点（插入运算），也可以删除某个结点（删除运算），除此之外，对数据结构的运算还有查找、分类、合并、分

13、解、复制和修改。 在对数据结构的处理过程中，不仅数据结构中结点的个数在动态变化，而且，各数据元素之间的关系也有可能在动态地变化。如：无序表变有序表数据结构是研究数据和数据之间关系的一门学科，研究以下三方面内容：n 数据的逻辑结构n 数据的存储结构n 数据的运算第18页/共132页第19页常见的数据结构 1.线性表 2.栈和队列 3.树第19页/共132页第20页 线性表是由n（n0）个数据元素 a1，a2，ai，an组成的一个有限序列。春夏秋冬记录1 02011001 张三 男记录2 02011003 李四 女 记录3记录4第20页/共132页第21页 顺序存储结构把逻辑上相邻的数据元素存储在

14、物理上相邻的存储单元里，顺序存储结构只存储结点的值，不存储结点间的关系，结点间的关系由存储单元的邻接关系来体现。a1a2aian存储地址200020042000+4*(i-1)2000+4*(n-1)占4个字节第i个数的地址第一个数的地址L为该类型数所占的字节线性表的存储结构有两种：u 顺序存储结构u 链式存储结构第21页/共132页第22页 顺序表的插入运算 顺序表的删除运算 在线性表顺序存储情况下，要插入或删除一个元素，都会由于数据元素的移动而消耗大量的处理时间，所以这种存储方式对于小线性表或其中数据元素不经常变动的线性表是合适的。线性表的顺序存储结构称为顺序表。第22页/共132页第23

15、页 线性表的链式存储结构称为线性链表。 链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，而且各数据元素的存储顺序也是任意的。各数据元素的先后关系是由各结点的指针域指示。 链式存储结构的每一个存储结点不仅存储结点的值，而且存储结点之间的关系：数据域数据域指针域指针域第23页/共132页第24页设线性表为（a1，a2，a3，a4，a5）1a2923a1145a4106789a3510a50HEAD3a1a2a5a3a4HEAD319510线性链表的逻辑状态线性链表的物理状态1 a12 a23 a34 a45 a567注意:1 2 3 此类编号不代表所在的地址单元的地址编码第24页/共132页

16、第25页 单链表的插入运算 单链表的删除运算采用链式存储结构，存储空间开销较大，但是进行插入和删除运算不会造成大量元素的移动。循环链表是加一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点。 a1a2a5a3a4HEAD319510第25页/共132页第26页双向链表的存储结构 提问：单向链表的缺点是什么？ 提示：如何寻找结点的直接前趋。 双向链表可以克服单链表的单向性的缺点。 在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。 HEAD31510 a2 a3 a4 a1双向循环链表 第26页/共132页第27页 顺序存储结构注意：注意：n 数据元素在计算机

17、数据元素在计算机存储空间中的位置关存储空间中的位置关系与它们的逻辑关系系与它们的逻辑关系不一定是相同的。不一定是相同的。n 一个逻辑数据结构一个逻辑数据结构可以有多种存储结构，可以有多种存储结构，且不同的存储结构影且不同的存储结构影响数据处理的效率响数据处理的效率 。1a2923a1145a4106789a3510a50HEAD31 a12 a23 a34 a45 a567u链式存储结构线性表 : a1，a2，a3，a4，a5 第27页/共132页第28页栈和队列都是特殊的线性表。第28页/共132页第29页是一种特殊的线性表。其特点是插入和删除运算都只能在线性表的一端进行。 栈是按照“”或“

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

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

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

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

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

23、种数据结构即为。 有且仅有一个根结点； 除第一个结点外，每一个结点最多有一个直接前驱结点； 除最后一个结点外，每一个结点最多有一个直接后继结点。 线性结构与非线性结构线性表、栈和队列都是线性结构线性表、栈和队列都是线性结构 一个数据结构不是线性结构，则称其为。a1a2a5a3a4HEAD319510线性链表的逻辑状态第36页/共132页第37页树型结构是一种重要的非线性结构。 树的概念 二叉树的概念 二叉树的存储 二叉树的遍历第37页/共132页第38页 树的定义：n个结点的有限集。（n=0） ABDFECGHIJKMn 根：only onen 若n=0，则称为空树；n 否则，当n1时，其余结

24、点被分成m（m0）个互不相交的子集T1，T2，.，Tm，每个子集又是一棵树。由此可以看出，树的定义是递归的。n Question：如何辨别根？A只有一个只有一个结点的树结点的树第38页/共132页第39页ABDFECGHIJKMn 一个结点的子树的个数； Q：结点结点A、G的度数？的度数？n 树中所有结点度的最大值；Q：右图中树的度？右图中树的度？n 度为0的结点； Q：图中叶子结点有几个？图中叶子结点有几个？7 度不为0的结点； Q：图中非终端结点有几个？图中非终端结点有几个？ 5第39页/共132页第40页ABDFECGHIJKMn 树中根结点的层次为1，根结点子树的根为第2层，以此类推；

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

26、称为满二叉树满二叉树。有一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1n的结点位置一一对应，则称这棵二叉树为完全二叉树完全二叉树。第43页/共132页第44页121314158910114567123满二叉树完全二叉树12138910114567123 完全二叉树是满二叉树 满二叉树也是完全二叉树第44页/共132页第45页1213891011456123非完全二叉树深度为4的完全二叉树84567123第45页/共132页第46页【性质3】二叉树上叶子结点数比度为2的结点数多1A

27、BCDFEHG度为2的结点叶子结点第46页/共132页第47页【性质4】具有n个结点的完全二叉树的深度为 log2 (n+1) 其中， log2n 的结果是不大于log2n的最大整数121314158910114567123深度为4的满二叉树深度为4的完全二叉树84567123深度为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的完全二叉树 具有25

28、6511深度为10的完全二叉树具有5121023深度为11的完全二叉树具有10242047第47页/共132页第48页1 1：在深度为7 7的满二叉树中, ,叶子结点的个数为（20062006年4 4月） A)32A)32 B)31 B)31 C)64C)64 D)63D)632 2：在深度为7 7的满二叉树中，度为2 2的结点个数为【 】 。(07(07年4 4月）3 3：一棵二叉树中共有7070个叶子结点与8080个度为1 1的结点，则该二叉树中的总结点数为 （0707年9 9月） A A）219 B219 B）221 C221 C）229 D229 D）2312314 4： 某二叉树中度

29、为2 2的结点有1818个，则该二叉树中有 【 】个叶子结点。（20052005年4 4月）5 5：一棵二叉树第六层（根结点为第一层）的结点数最多为【 】个。（20052005年9 9月） 树型结构方面的考题 1答案：C。3答案：A。5答案：32。2答案：63。4答案：19。第48页/共132页第49页 在计算机中，二叉树通常采用链式存储结构。LlinkinfoRlink二叉树的存储结点的结构ABDCFGE A G E F B C Dt第49页/共132页第50页 遍历指不重复地访问二叉树中的所有结点。 二叉树的遍历的次序与树型结构上的大多数运算有联系。（1）先（前）序遍历（DLR）（2）中序

30、遍历（LDR）（3）后序遍历（LRD）ABCDFEHG第50页/共132页第51页 遍历指不重复地访问二叉树中的所有结点。（1）先（前）序遍历（DLR） 若二叉树为空，则结束遍历操作；否则 访问根结点；遍历左子树；遍历右子树。ABCDFEHG先序遍历的结果： A A B E C F G H D B E C F G H D第51页/共132页第52页（2）中序遍历（LDR） 若二叉树为空，则结束遍历操作；否则 中序遍历左子树； 访问根结点； 中序遍历右子树。中序遍历的结果： E B A F H G C D（3）后序遍历（LRD） 若二叉树为空，则结束遍历操作；否则 后序遍历左子树； 后序遍历右子

31、树； 访问根结点。后序遍历的结果： E B H G F D C AABCDFEHG第52页/共132页第53页 先序序列：ABDGCEFH 中序序列：DGBAECHF 后序序列：GDBEHFCAABCFHDEG下图所示的二叉树经过三种遍历得到的顺序分别为？练习：练习：根据先序遍历序列，建立二叉树第53页/共132页第54页1:设二叉树如下： （2010年3月）对该二叉树进行后序遍历的结果为 【3】 树型结构方面的考题 22: 对如下二叉树（2006年4月）进行后序遍历的结果为A) ABCDEF B) DBEAFC C) ABDECF D) DEBFCA EDBGHFCA DABCFHDGE第5

32、4页/共132页第55页 查找是数据处理的重要内容。 查找指在一个给定的数据结构中查找指定的元素，该元素也称关键字。 若找到了满足条件的结点，称查找成功；否则称查找失败。 衡量一个查找算法的主要标准是查找过程中对关键字进行的平均比较次数。 通常根据不同的数据结构，采用不同的查找方法： 顺序查找 二分查找第55页/共132页第56页 线性表中最简单的查找方法。 方法：从线性表的第一个元素开始，依次将线性表中的元素与关键字进行比较，若相等，则查找成功；若将所有元素都与关键字进行了比较但不相等，则查找失败。 顺序查找法的适用场合： 对线性表中元素的排列次序没有要求； 对线性表的存储结构没有要求，链式

33、结构和顺序结构均可。第56页/共132页第57页折半查找折半查找) ) 是一种效率较高的查找方法，但是只适合顺序存储的有序表。 二分查找的方法：首先将关键字与线性表中间位置的结点比较，相等则查找成功；不相等则根据比较结果确定下一步查找应在哪个子表中进行；重复上述过程，直至查找成功或子表长度为0。 二分查找法的适用场合： 线性表中的元素按关键字值递增或递减的次序排列； 线性表采用顺序存储结构。第57页/共132页第58页练习假设待查有序（升序）顺序表中数据元素的关键字序列为（8,18,27,42,47,50,56, 68,95,120），用折半查找方法查找关键字值为27的数据元素.对于长度为对于

34、长度为n n的有序线性表，最坏情况只需比较的有序线性表，最坏情况只需比较log2nlog2n次。次。 第58页/共132页第59页 排序指将一个无序序列整理成按关键字值递增或递减排列的有序序列。 排序方法中其排序对象一般是顺序存储的线性表。 根据排序序列的规模以及数据处理的要求，可以采用不同的排序方法：交换类排序法 冒泡排序 快速排序 插入类排序法 简单插入排序 希尔排序选择类排序法 简单选择排序 堆排序第59页/共132页第60页 冒泡排序的方法： 扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的结果使最大(或最小)的元素排到表的最后(或最前) ； 除最后(或最前

35、)一个元素，对剩余的元素重复上述过程，将次大(或次小)的数排到表的倒数(或正数)第二个位置； 重复上述过程； 对于长度为n的线性表，冒泡排序需要对表扫描n-1遍。 第60页/共132页第61页冒泡排序的方法u 设待排数据元素的关键字为（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 最大数u第二趟冒泡排序第61页/共132页第62|92页Q：第二趟冒泡排序后的结果是什么样的

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

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

38、第二趟： 11，14 22，30，37，15，15u第三趟： 11，14，15 30，37，22，15u第四趟： 11，14，15，15 37，22，30u第五趟： 11，14，15，15，22 37，30u第六趟： 11，14，15，15，22，30 37 有序序列例：设待排数据元素的关键字为（15，14，22，30，37，11），每一趟排序后的序列状态如图所示：第65页/共132页第66页 简单选择排序法, 最坏情况需要n(n-1)/2次比较； 冒泡排序法, 最坏情况需要n(n-1)/2次比较； 希尔排序法, 最坏情况需要O(n1.5)次比较； 堆排序法, 最坏情况需要O(nlog2n)次

39、比较； 第66页/共132页第67页(1) 对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是（2005年4月）A) 冒泡排序为n/2 B) 冒泡排序为nC) 快速排序为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）

40、直接插入排序 D）堆排序DBAD第67页/共132页第68页 1. 程序设计方法与风格。 2. 结构化程序设计。 3. 面向对象的程序设计方法，对象，方法，属性及继承与多态性。第68页/共132页第69页 结构化程序设计方法的四条原则是：1. 自顶向下；2. 逐步求精；3. 模块化；4. 限制使用goto语句。 结构化程序的基本结构和特点：（1）顺序结构： 简单的程序设计，最基本、最常用的结构；（2）选择结构（分支结构）： 包括简单选择和多分支选择结构，（3）重复结构（循环结构）： 可根据给定条件，判断是否需要重复执行某一相同程序段。第69页/共132页第70页 对象是面向对象方法中最基本的概

41、念。 对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，由一组表示其静态特征的属性和它可执行的一组操作组成。 属性即对象所包含的信息 操作描述了对象执行的功能，操作也称为方法或服务。第70页/共132页第71页 类是指具有共同属性、共同方法的对象的集合。 所以类是对象的抽象，对象是对应类的一个实例。 消息是一个实例与另一个实例之间传递的信息。消息的组成包括 （1）接收消息的对象的名称； （2）消息标识符，也称消息名； （3）零个或多个参数。 继承是指能够直接获得已有的性质和特征，而不必重复定义他们。 单继承指一个类只允许有一个父类 多重继承指一个类允许有多个父类。 多态性是指同

42、样的消息被不同的对象接受时可导致完全不同的行动的现象。第71页/共132页第72页程序设计基础方面的考题1.符合结构化原则的三种基本控制结构是：选择结构、循环结构和【 】 . (2009年3月)2. 下列选项中不属于结构化程序设计原则的是（2009年9月）A) 可封装 D) 自顶向下 C) 模块化 D) 逐步求精3. 以下叙述中正确的是。（2010年3月） A）程序设计的任务就是编写程序代码并上机调试 B）程序设计的任务就是确定所用数据结构 C）程序设计的任务就是确定所用算法 D）以上三种说法都不完整4.在面向对象方法中，类的实例称为 【_】 。（2005年4月）5.在面向对象方法中, 【_】

43、 描述的是具有相似属性与操作的一组对象。（2006年4月）（顺序结构）A D对象类第72页/共132页第73页第三章 软件工程基础计算机软件是包括程序、数据及相关文档的完整集合。软件按功能分为应用软件、系统软件、支撑软件（或工具软件）。第73页/共132页第74页1.软件工程概念 软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。软件工程包括3个要素：方法、工具和过程。 软件周期：软件产品从提出、实现、使用维护到停止使用退役的过程。软件生命周期三个阶段:软件定义、软件开发、运行维护，主要活动阶段是：（1）可行性研究与计划制定；（2）需求分析；（3）软件设计；

44、（4）软件实现；（5）软件测试；（6）运行和维护。第74页/共132页第75页：着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具,建立系统的逻辑模型。 结构化分析的常用工具 （1）数据流图； （2）数据字典； （3）判定树； 判定表。 （4）软件需求规格说明书第75页/共132页第76页 软件设计包括：总体设计与详细设计 在程序结构中各模块的内聚性越强，则耦合性越弱。优秀软件应高内聚，低耦合。 常见的过程设计工具有：图形工具（程序流程图,N-S,PAD）表格工具（判定表）语言工具（PDL伪码）第76页/共132页第77页 程序流程图N-S图PAD图第77页/

45、共132页第78页 软件测试的目的：发现错误而执行程序的过程。 软件测试方法：静态测试： 包括代码检查、静态结构分析、代码质量度量。不实际运行软件，主要通过人工进行。动态测试： 是基本计算机的测试，主要包括白盒测试方法和黑盒测试方法 软件测试过程一般按4个步骤进行：单元测试、集成测试、验收测试（确认测试）和系统测试。第78页/共132页第79页 程序调试的任务是诊断和改正程序中的错误，主要在开发阶段进行。 软件调试 静态调试主要是指通过人的思维来分析源程序代码和排错，是主要的设计手段。 动态调试是辅助静态调试。主要调试方法有：（1）强行排错法；（2）回溯法；（3）原因排除法。第79页/共132

46、页第80页(1) 下面叙述中错误的是 (2009年3月） A）软件测试的目的是发现错误并改正错误 B）对被调试的程序进行“错误定位”是程序调试的必要步骤 C）程序调试通常也称为Debug D）软件测试应严格执行测试计划，排除测试的随意性 (2) 软件测试可分为白盒测试和黑盒测试。基本路径测试属于【 】测试。(2009年3月）(3) 按照软件测试的一般步骤，集成测试应在_测试之后进行。(4) 软件工程三要素包括方法、工具和过程，其中，_支持软件开发的各个环节的控制和管理。(2008年9月)(5)软件设计中划分模块的一个准则是(2009年9月）A) 低内聚低耦合 B) 高内聚低耦合C) 低内聚高耦

47、合 D) 高内聚高耦合A 软件工程方面的考题：白盒 单元过程 B第80页/共132页第81页(6) 下列叙述中正确的是（2005年9月）AA）软件交付使用后还需要进行维护B）软件一旦交付使用就不需要再进行维护C）软件交付使用后其生命周期就结束D）软件维护是指修复程序中被破坏的指令(7) 程序流程图中的菱形框表示的是 【2】(2009年9月) 。(8)软件开发过程主要分为需求分析、设计、编码与测试四个阶段，其中 【3】 阶段产生“软件需求规格说明书。（2009年9月） (9)下列叙述中正确的是（2006年4月） A)软件测试应该由程序开发者来完成 B)程序经调试后一般不需要再测试 C)软件维护只

48、包括对程序代码的维护 D)以上三种说法都不对A 逻辑条件需求分析D第81页/共132页第82页(3)软件按功能可以分为：应用软件、系统软件和支撑软件(或工具软件)。下面属于系统软件的是 A)编辑软件 B)操作系统C)教务管理系统D)浏览器(4)软件(程序)调试的任务是 A)诊断和改正程序中的错误B)尽可能多地发现程序中的错误C)发现并改正程序中的所有错误D)确定程序中错误的性质(5)数据流程图(DFD图)是 A)软件概要设计的工具 B)软件详细设计的工具C)结构化方法的需求分析工具D)面向对象方法的需求分析工具(6)软件生命周期可分为定义阶段，开发阶段和维护阶段。详细设计属于 A)定义阶段 B

49、)开发阶段C)维护阶段 D)上述三个阶段2010年3月计算机等级考试 BA C B 第82页/共132页第83页数据库设计基础知识点得分表数据库的数据库的基本概念基本概念数据数据模型模型关系关系代数代数数据库设数据库设计与管理计与管理小计08年年4月月2分6分2分10分08年年9月月2分4分2分2分10分09年年3月月2分2分2分4分10分09年年9月月2分2分2分4分10分10年年3月月2分4分2分2分10分时间知识点第83页/共132页第84页实际上就是描述事物的符号记录。：是数据的集合，具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序共享。：一种系统软

50、件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等，是数据库的核心。：由数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、硬件平台（硬件）、软件平台（软件）五个部分构成的运行实体。：由数据库系统、应用软件及应用界面三者组成。第84页/共132页第85页数据库系统第85页/共132页86常见的关系数据库管理系统 小型数据库： Visual FoxPro （以后简称为VFP） Access (office套件中的一个) Paradox 大型数据库： Oracle Informix SYBASE SQL server 等 第86页/共132页第87页数据库管理系统提供

51、的数据语言：（1）数据定义语言：负责数据的模式定义与数据的物理存取构建；（2）数据操纵语言： 负责数据的操纵，如查询与增、删、改等；（3）数据控制语言：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等。数据库管理系统的发展(1)文件系统阶段：提供了简单的数据共享与数据管理能力，但是它无法提供完整的、统一的、管理和数据共享的能力。(2)层次数据库与网状数据库系统阶段 ：为统一与共享数据提供了有力支撑。(3)关系数据库系统阶段1.数据库系统的基本概念第87页/共132页第88页 关系数据库系统的基本特点： 数据的集成性 数据的高共享性与低冗余性 数据独立性（物理独立性与逻辑独立性） 数据

52、统一管理与控制。 数据库存放数据是按数据所提供的数据模式存放的，具有集成与共享的特点。 数据库系统的三级模式：（1）概念模式（2）外模式（3）内模式 数据库系统的两级映射：（1）概念模式到内模式的映射；（2）外模式到概念模式的映射。 1.数据库系统的基本概念第88页/共132页89应用外模式(用户数据库)应用外模式(用户数据库)应用外模式(用户数据库)概念模式(概念数据库)内模式(物理数据库)数据库外模式概念模式映射概念模式内模式映射模式第89页/共132页902. 数据模型数据模型（Data Model）是对客观事物及其关系的数据描述。 数据库中的数据模型可以将复杂的现实世界要求反映到计算机

53、数据库中的物理世界。现实世界信息世界计算机世界 数据模型是数据特征的抽象，静态特征、动态行为和约束条件。数据模型所描述的内容包含：数据结构、数据操作和数据约束。第90页/共132页第91页（1）实体：现实世界中的事物；（2）属性：事物的特性；（3）联系：现实世界中事物间的关系。实体集的关系有一对一、一对多、多对多的联系。 一个班级的学生，学生与学生之间是一对一的关系。 在一所学校，一门课程与学生之间是一对多的关系。 在一所学校，多门课程与多个学生之间是多对多的关系。第91页/共132页92E-R模型的图示法用简单的几何图形表示实体集、属性与联系。(1)实体集表示法在E-R图中用矩形表表示实体集

54、，在矩形内写上实体集名称。如实体集学生(student)、实体集课程(course)(2)属性表示法在E-R图中用椭圆形表示属性，在椭圆形内写上该属性名称。如学生有属性：学号(S#)、姓名(Sn)及年龄(Sa)可用如下表示。studentcourseS#SnSa第92页/共132页93(3)联系表示法在E-R图中用菱形(内写上联系名)表示联系。如学生与课程的联系SC,如下图所示：(4)实体集与属性间的联系关系属性依附于实体集，它们之间有联系关系用无向线段表示。SCstudentS#SnSa第93页/共132页94属性也依附于联系，它们之间也有联系关系，因此也可用无向线段，如联系SC可与学生的课

55、程成绩属性G建立联系并用下图表示。(5)实体集与联系间的连接关系(也可用无向线段)SCGstudentcourseSC第94页/共132页第95页E-R模型之间的联接关系：实体是概念世界中的基本单位，属性有属性域，每个实体可取属性域内的值。一个实体的所有属性值叫元组。E-R模型的图示法：（1）实体集表示法；用长方形（2）属性表法；用椭圆形（3）联系表示法。用菱形，(m:n)第95页/共132页第96页层次模型（采用树型结构）图图1-4 层次模型示例层次模型示例第96页/共132页第97页网络模型（采用无向图型结构）第97页/共132页第98页关系模型（采用二维表结构）第98页/共132页第99

56、页 关系模型采用二维表来表示，简称表，由表框架及表的元组组成。一个二维表就是一个关系。 关系数据库系统的特点之一是它建立在数据理论的基础之上，有很多数据理论可以表示关系模型的数据操作，其中最为著名的是关系代数与关系演算。学号学号姓名姓名性别性别出生日期出生日期入学成绩入学成绩四级通过否四级通过否计算机等级考试计算机等级考试备注备注04001001尚杰尚杰男男86-11-20520.5T一级一级04001002余习芳余习芳女女86-12-26513.5F二级二级04001057张轶一张轶一男男86-01-09612.0T04002023陶红莉陶红莉女女85-02-14535.0F二级二级第99页

57、/共132页1001.关系的数据结构二维表由表框架与表元组组成。表框架由n个命名的属性组成(n称为属性元素)。每个属性有一个取值范围称为值域。表框架对应了关系的模式，即类型的概念。每行数据称为元组，一个元组由n个元组分量所组成，每个元组分量是表结构中每个属性的投影值。学号学号姓名姓名性别性别出生日期出生日期入学成绩入学成绩四级通过否四级通过否计算机等级考试计算机等级考试备注备注04001001尚杰尚杰男男86-11-20520.5T一级一级04001002余习芳余习芳女女86-12-26513.5F二级二级04001057张轶一张轶一男男86-01-09612.0T04002023陶红莉陶红莉

58、女女85-02-14535.0F二级二级第100页/共132页101一个二维表要满足下面7个性质就可称为一个关系。二维表中元组个数是有限的二维表中元组均不相同 二维表中元组的次序可任意交换 二维表中元组的分量是不可分割的基本数据项二维表中属性名各不相同二维表中属性与次序无关，可任意交换二维表属性中的分量具有与该属性相同的值域二维表二维表关系模型关系模型VFP表文件表文件二维表框架二维表框架关系模式关系模式数据表结构数据表结构行行元组元组记录记录 元组分量元组分量数据项数据项列列属性属性字段字段 属性值域属性值域字段值域字段值域惟一标识元组的最小属性集称为该表的键(或码)，在VFP表中称为主关键

59、字第101页/共132页102关系模型的基本运算： 1. 数据查询 查询关系数据库中的数据，一个关系内的查询以及多个关系间的查询。 查询的基本单位为元组分量，先定位后操作。 纵向定位（列指定） 横向定位（行选择） 2. 数据插入 插入一个元组（不定位） 3. 数据删除 删除一个元组（定位、操作） 4. 数据修改 删除需修改的元组再插入修改后的元组关系操作第102页/共132页103关系模型的基本运算： 1. 插入 集合的并运算 2. 删除 集合的差(交) 运算 3. 修改 集合的差|并(除)运算。 4. 查询 （投影、选择、笛卡尔积运算）3.关系代数集合的并运算第103页/共132页104 由

60、关系R和S通过交运算得到关系T，第104页/共132页105用于查询的集合运算：（1）投影对于关系R内的域指定称为投影运算。S关系就是对R关系指定A和B两个域的结果ABCa32b01c21ABa3b0c2RS3.关系代数第105页/共132页106关系代数（2）选择选择运算的关系是由关系R中那些满足逻辑条件的元组所组成。S关系就是R关系中满足A=a的结果ABCa32b01a69c21RSABCa32a69有了投影和选择运算，我们对一个关系内的任意行、列的数据都可以方便的找到。第106页/共132页107 笛卡尔积是对两个关系的合并操作。有三个关系R、S和T R关系 n1行, m1列 S关系 n