公共基础知识(lrw).ppt

《公共基础知识(lrw).ppt》由会员分享，可在线阅读，更多相关《公共基础知识(lrw).ppt（251页珍藏版）》请在课桌文档上搜索。

1、计算机二级考试公共基础知识,2,计算机二级考试公共基础知识大纲,数据结构与算法 程序设计基础 软件工程基础 数据库设计基础,1.掌握算法的基本概念。2.掌握基本数据结构及其操作3.掌握基本排序和查找算法。4.掌握逐步求精的结构化程序设计方法。5.掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。6.掌握数据库的基本知识，了解关系数据库的设计。,3,一、基本数据结构与算法,1.算法的基本概念；时间复杂度与空间复杂度。2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。4.栈和队列的定

2、义；栈和队列的顺序存储结构及其基本运算。5.线性单链表、双向链表与循环链表的结构及其基本运算。6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。,4,二、程序设计基础,1.程序设计方法与风格。2.结构化程序设计。3.面向对象的程序设计方法，对象，方法，属性及类、继承与多态性。,5,三、软件工程基础,1.软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。2.结构化分析方法，数据流图，数据字典，软件需求规格说明书。3.结构化设计方法，总体设计与详细设计。4.软件测试的方法，白盒测试与

3、黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。5.程序的调试，静态调试与动态调试。,6,四、数据库设计基础,1.数据库的基本概念：数据库，数据库管理系统，数据库系统。2.数据模型：实体联系模型及E-R图，从E-R图导出关系数据模型。3.关系代数运算：包括集合运算及选择、投影、连接运算，数据库规范化理论。4.数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。,7,算法 算法的基本概念 2.算法复杂度的概念和意义,一、基本数据结构与算法,数据结构 数据结构的概念 线性表 栈和队列 树与二叉树 查找技术 排序技术,对于等级考试，这个部分的考核重点主要在算

4、法和数据结构的基本概念、二叉树(遍历、结点），还有排序和查找考试中也经常会涉及到。,8,算法的定义对解题方案准确而完整的描述算法。,算法是程序设计的核心,算法的基本概念,算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程(计算的方法)。在这个过程中，无论是形成解题思路(推理实现的算法)还是编写程序(操作实现的算法)，都是在实施某种算法。,9,2.算法的基本特征,可行性 有穷性 确定性 输入 输出,拥有足够的情报,10,3.算法的表示,传统的算法-图形法，如“流程图”和N-S图目前常用的方法-使用伪码描述算法。,11,4.算法的两个基本要素：,基本运算和操作

5、 算术运算 关系运算 逻辑运算 数据传输,控制结构 顺序 选择 循环,一是对数据对象的运算和操作；二是算法的控制结构。,12,算法设计基本方法列举法归纳法递推递归减半递推技术回溯法,根据提出的问题，列举出所有可能的情况,通过列举少量的特殊情况，经过分析，最后找出一般的关系,从已知的初始条件出发，逐次推出所要求的各个中间环节和最后结果,将复杂问题逐层分解，最后归结为一些最简单的问题。,将问题的规模减半，然后，重复相同的递推操作,采用试探的方法，通过对问题的分析，找出解决问题的线索,13,5 算法复杂度,时间复杂度是指执行算法所需要的计算工作量。算法在执行过程中所需基本运算的执行次数来度量算法的工

6、作量.算法所执行的基本运算次数与问题的规模n有关.,14,例子3：for(i=2;i=n;+i)for(j=2;j=i-1;+j)+x;,基本运算：基本运算的执行次数：,X增1,i=2 0i=3 1i=4 2i=n n-2,1+2+3+(n-2),=(n-1)(n-2)/2,O（）,例子1：+x;,O（1）,例子2：for(i=1;i=n;+i)+x;,O（n）,时间复杂度：,O(n*n-3n+2)/2),基本运算：基本运算的执行次数：时间复杂度：,1,X增1,基本运算：基本运算的执行次数：时间复杂度：,X增1,n,15,空间复杂度 一般是指执行这个算法所需要的内存空间一个算法所占用的存储空间

7、包括:算法程序所占的空间输入的初始数据所占的存储空间某种数据结构所需要的附加存储空间,16,(1)在计算机中，算法是指_。A.查询方法 B.加工方法 C.解题方案的准确而完整的描述 D.排序方法(2)下列叙述中正确的是（07年4月）A)算法的效率只与问题的规模有关，而与数据的存储结构无关B)算法的时间复杂度是指执行算法所需要的计算工作量C)数据的逻辑结构与存储结构是一一对应的D)算法的时间复杂度与空间复杂度一定相关(3)算法的有穷性是指(08年4月)A）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的 C）算法程序的长度是有限的 D）算法只能被有限的用户使用,(c),(B),算法

8、习题:,(A),17,(4)算法的时间复杂度是指(2010年3月)A)算法的执行时间B)算法所处理的数据量C)算法程序中的语句或指令条数D)算法在执行过程中所需要的基本运算次数(5)算法的空间复杂度是指(09年9月)A）算法在执行过程中所需要的计算机存储空间B）算法所处理的数据量C）算法程序中的语句或指令条数D）算法在执行过程中所需要的临时工作单元数(6)下列叙述中正确的是(06年9月)A）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间复杂度必定小C）一个算法的时间复杂度大，则其空间复杂度必定小 D）上述三种说法都不对,(D)计算工作量,(A),(D),18

9、,计算机在进行数据处理时，实际需要处理的数据元素一般有很多，而这些大量的数据元素都需要存放在计算机中，因此，大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题。,二、数据结构,程序=算法+数据结构,19,二.数据结构,数据结构是指相互有关联的数据元素的集合。数据结构是研究数据和数据之间关系的一门学科，它包括三个方面。（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。,20,21,1.逻辑结构 数据的逻辑结构是指反

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

11、,(A,B,C,，X,Y,Z),例:学生成绩表,线性表,例:英文字母表,如果一个非空的数据结构满足如下条件，则该数据结构为线性结构：有且只有一个根结点每一个结点最多只有一个前件，也最多只有一个后件,A.线性结构,线性表,栈后进先出LIFO,A.线性结构,线性表,栈后进先出LIFO队列先进先出FIFO,树形结构,例:全校学生档案管理的组织方式,B非线性结构,例:数据结构B(D,R)D=1,2,3,4 R=(1,2),(1,3),(1,4),(2,3),(3,4),(2,4),例:数据结构C(D,R)D=1,2,3 R=,图形结构,28,2.存储结构（物理结构）存储结构指数据结构在计算机存储空间中

12、的具体实现。常见的存储结构有：顺序存储结构 链式存储结构索引存储结构,注意：数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的。一个逻辑数据结构可以有多种存储结构，且不同的存储结构影响数据处理的效率。,29,3.数据的运算 检索 插入 删除 更新 排序,常见的数据结构,1.线性表 2.栈和队列 3.树,31,线性表（Linear List）,线性表是由n（n0）个数据元素 a1，a2，ai，an组成的一个有限序列。其中n称作表的长度，当n=0时，称作空表。,线性表的特点：1.线性表中所有元素的性质相同。2.除第一个和最后一个数据元素之外，其它数据元素有且仅有一个前驱和一个后继.

13、第一个数据元素无前驱,最后一个数据元素无后继。3.数据元素在表中的位置只取决于它自身的序号。,32,设线性表为（a1，a2，a3，a4，a5）,2、链式存储结构,1、顺序存储结构,线性表的存储结构有两种：,33,线性表的顺序存储结构顺序表,存储地址,2000,2004,2000+4*(i-1),2000+4*(n-1),占4个字节,Loa（ai）=Loa（a1）+L*（i-1）,第i个数的地址,第一个数的地址,L为该类型数所占的字节,顺序存储结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里,具有以下特点:1.随机存取。2.作插入或删除操作时，需移动大量元数。3.长度变化较大时，需按最大

14、空间分配。4.表的容量难以扩充。,34,顺序表的插入运算,在线性表顺序存储情况下，要插入或删除一个元素，都会由于数据元素的移动而消耗大量的处理时间，所以这种存储方式对于小线性表或其中数据元素不经常变动的线性表是合适的。,ai-1,.,a2,a1,alength,ai+1,ai,x,ai-1,.,a2,a1,alength,ai+1,ai,顺序表的删除运算,35,线性表的链式存储结构,1.比顺序存储结构多用空间(存储密度小)(每个节点都由数据域和指针域组成)。2.逻辑上相邻的节点物理上不必相邻。3.插入、删除灵活(不必移动节点，只要改变节点中的指针)。4.非随机存取。,36,线性链表的删除运算,

15、线性链表的插入运算,采用链式存储结构，存储空间开销较大，但是进行插入和删除运算不会造成大量元素的移动。,37,循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点。可以从任何一个结点开始访问链表的所有结点.,38,双向链表 在每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接确定一个结点的前驱和后继结点。可提高效率。,39,2.栈和队列,栈和队列都是特殊的线性表。栈（Stack）及其基本运算 队列（Queue）及其基本运算 循环队列及其基本运算,40,1.栈,栈是限定仅在表尾进行插入或删除操作的线性表。栈顶表尾。栈底表头。空栈不含元素的空表。,入栈,出栈,栈

16、s=(a1,a2,an),后进先出（LIFO）先进后出（FILO）,41,2.栈的顺序存储结构及其基本运算,顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量top指示栈顶位置，称为栈顶指针，它始终指向待插入元素的位置。,基本运算：入栈：PUSH出栈：POP读栈顶元素：gettop,在顺序栈中插入和删除运算不需要移动表中其他数据元素。,42,例子：,空栈：topbase非空栈：top始终在栈顶元素的后一个位置,栈的元素个数：,top-base,上溢,下溢,3.队列定义：一种特殊的线性结构，限定只能在表的一端进行插入，在 表的另一端进行删除的线性表。此种结

17、构称为先进先出（FIFO）表。,4.队列的顺序存储结构及其基本运算,空队列:非空队列:队列元素个数:,rear=front=-1,front始终指向队头元素前一个位置，而rear始终指向队尾元素的位置,rear-front,循环队列,将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。,队列的顺序存储结构一般采用队列循环的形式。计算循环队列的元素个数：“尾指针减头指针”，若为负数，再加其容量即可。,46,数据存储结构方面的考题,1：数据的存储结构是指（2005年4月）A)存储在外存中的数据 B)数据所占的存储空间量C)数据在计算机中的顺序存储方式 D)数据的逻辑结构在计算机中的表

18、示2：下列叙述中正确的是（2009年3月）A）栈是“先进先出”的线性表 B）队列是“先进后出”的线性表 C）循环队列是非线性结构 D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构 3.数据结构分为线性结构和非线性结构，带链的队列属于。4.下列数据结构中，属于非线性结构的是A）循环队列 B)带链队列C)二叉树 D）带链栈,答案：D。,答案：D。,答案：线性结构。,答案：c,47,5。下列叙述中正确的是（）。（2008年9月）A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的 B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构 C）顺序存储结构能存储有序

19、表，链式存储结构不能存储有序表 D）链式存储结构比顺序存储结构节省存储空间,答案：A。,6。下列关于栈的叙述正确的是（2008年4月）A）栈按“先进先出”组织数据 B)栈按“先进后出”组织数据 C）只能在栈底插入数据 D）不能删除数据,答案：B。,7.一个队列的初始状态为空。现将元素A，B，C，D，E，F，5，4，3，2，1依次入队，然后再依次退队，则元素退队的顺序为【1】。（2010年3月）,答案：A，B，C，D，E，F，5，4，3，2，1,48,一个栈的入栈序列是a,b,c,d,e则栈的不可能的输出序列是：（）A、edcba B、decba C、dceab D、abcde,栈之根本先进后出

20、（first in，last out）选项1是abcde先入栈，然后依次出栈，正好是edcba选项2是abcd先依次入栈，然后d出栈，e再入栈，e出栈选项3是错误的，d出栈了，abc一定已经入栈，那么abc只能以cba的顺序出栈，选项4是a入栈，然后a出栈；b再入栈，b出栈。依此类推,49,9.设某循环队列的容量为50，如果头指针front=45(指向队头元素的前一位置)，尾指针rear=10(指向队尾元素)，则该循环队列中共有【2】个元素。（2010年3月）,8。假设用一个长度为50的数组（数组元索的下标从0到49）作为栈的存储空间，栈底指针bottom指间栈底元素，栈顶指针top指向栈顶元

21、素，如果bottom=49，top=30（数组下标），则栈中具有【】个元素。（2009年3月）,答案：19,答案：15,50,树型结构是一种重要的非线性结构。树的概念 二叉树的概念 二叉树的存储 二叉树的遍历,3.树与二叉树,51,树的概念,n个结点的有限集。（n=0）仅有一个根结点，结点间有明显的层次结构关系。,若n=0，则称为空树；否则，当n1时，其余结点被分成m（m0）个互不相交的子集T1，T2，.，Tm，每个子集又是一棵树。,C,G,D,H,I,J,M,B,E,L,K,F,结点（Node）：树中的元素父结点（根）:在树结构中，每一个结点只有一个前件 子结点:每一个结点可以有多个后件 结

22、点的度（Degree）：结点拥有的子树数(后件)。叶子（Leaf）：度为0的结点。树的度：结点所具有的最大的度.结点的层次：从根结点开始算起，根为第一层。树的深度（Depth)：树中结点的最大层次数。,A,B,D,F,E,C,G,H,I,J,K,M,二叉树（Binary Tree）的定义,二叉树的五种基本形态,二叉树是一种很有用的非线性结构，具有以下两特点：非空二叉树只有一个根结点；每一个结点最多有两棵子树（左子树、右子树），且子树有左右之分，次序不能颠倒。,性质1:二叉树的第i层上至多有2 i-1（i 1）个结点。,二叉树的基本性质,性质2:深度为k的二叉树中至多含有2k-1个结点。,性质：

23、对任何一棵二叉树T，如果其叶子结点数为n0,度为2的结点数为n2,则n0=n2+1,n2=n0-1。其结点总数为：n=n0+n1+n2=2n0+n1-1性质4：具有n个结点的二叉树，其深度至少为log2n+1,其中log2n表示取log2n的整数部分。,满二叉树：如果一个深度为h的二叉树拥有2h-1个结点，则将它称为满二叉树。完全二叉树：有一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1n的结点位置一一对应，则称这棵二叉树为完全二叉树。,满二叉树,特点：每一层上都含有最大结点数2i

24、-1深度为k的满二叉树拥有2k-1个结点,完全二叉树,特点：(1)除最后一层外，每一层都取最 大结点数(2)最后一层结点都集中在该层最左边的若干位置。,12,13,8,9,10,11,4,5,6,7,1,2,3,已知总结点数，求各类型结点数n0,n1,n2,12,13,8,9,10,11,4,5,6,1,2,3,非完全二叉树,深度为4的完全二叉树,8,4,5,6,7,1,2,3,性质1：具有n个结点的完全二叉树的深度为,11,2,3,4,5,6,7,8,9,10,12,1,结点数n=2n=6n=7n=8n=12,深度k=2k=3k=3k=4k=4,性质2：如果对一棵有n个结点的完全二叉树的结点

25、按层 序编号，则对任一结点i(1=i=n)有：,(2)如果2in,则结点i无左孩子(结点i为叶子结点);否则其左孩子Lchild(i)是结点2i。(3)如果2i+1n,则结点i无右孩子;否则其右孩子Rchild(i)是结点2i+1。,例：,i=1 是树的根,无双亲;其左孩子为2*i=2,右孩子为2*i+1=3.,2*i=1812 2*i+1=1912 其无左、右孩子。,2*i+1=1312 其无右孩子。,62,1：在深度为7的满二叉树中,叶子结点的个数为（2006年4月）A)32 B)31 C)64 D)632：在深度为7的满二叉树中，度为2的结点个数为【】。(07年4月）3：一棵二叉树中共有

26、70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为（07年9月）A）219 B）221 C）229 D）2314：某二叉树中度为2的结点有18个，则该二叉树中有【】个叶子结点。（2005年4月）5：一棵二叉树第六层（根结点为第一层）的结点数最多为【】个。（2005年9月）,树型结构方面的考题,1答案：C。,3答案：A。,5答案：32。,2答案：63。,4答案：19。,63,二叉树的存储,在计算机中，二叉树通常采用链式存储结构。,二叉树的存储结点的结构,A,B,D,C,F,G,E,t,先序遍历：D L R中序遍历：L D R后序遍历：L R D,A,D,B,C,D L R,以先序遍历D

27、 L R为例演示遍历过程,ABDC,BDAC,DBCA,二叉树的遍历：遍历指按某条搜索路线寻访树中每个结点，且每个结点只被访 问一次。遍历的方式有三种：先序遍历、中序遍历、后序遍历,（根D，左L，右R）,65,（1）先（前）序遍历（DLR）（2）中序遍历（LDR）（3）后序遍历（LRD）,A B E C F G H D,E B A F H G C D,E B H G F D C A,66,A,E B H G F D C A,1、绘制二叉树的包线,2、按包线的绘制方向，在每个结点的左边标记，每个结点只标记一下，所得标记序列为先序遍历（DLR）,3、按包线的绘制方向，在每个结点的下方标记，每个结点

28、只标记一下，所得标记序列为中序遍历（LDR）,4、按包线的绘制方向，在每个结点的右边标记，每个结点只标记一下，所得标记序列为后序遍历（LRD）,B,D,E,C,F,G,H,A,B,D,E,C,F,G,H,A,B,D,E,C,F,G,H,L D R,L D R,a,+,L D R,b,*,LDR,c,-,d,-,LDR,e,/,f,中序遍历示图,68,先序序列：ABDGCEFH中序序列：DGBAECHF后序序列：GDBEHFCA,A,B,C,F,H,D,E,G,下图所示的二叉树经过三种遍历得到的顺序分别为？,练习：,根据先序遍历序列，建立二叉树,69,1:设二叉树如下：（2010年3月）对该二叉

29、树进行后序遍历的结果为【3】,树型结构方面的考题 2,2:对如下二叉树（2006年4月）进行后序遍历的结果为A)ABCDEFB)DBEAFC C)ABDECFD)DEBFCA,EDBGHFCA,D,A,B,C,F,H,D,G,E,70,特别讨论：若已知先序（或后序）遍历结果和中序遍历结果，能否“恢复”出二叉树？,分析：由先序遍历特征，根结点必在先序序列头部；由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树的子孙，其右部必全部是右子树的子孙；,仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二叉树，如果同时已知二叉树的中序序列“cbdaegf”,则会如何？,71,a b c d

30、e f g,c b d a e g f,例如:,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列中序序列,72,已知中序遍历：B D C E A F H G已知后序遍历：D E C B H G F A,（B D C E）,（F H G）,A,（D C E）,A,B,B,A,C,C,D C E,练习：,已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 A)acbed B)decab C)deabc D)cedba 已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为 A)GED

31、HFBCA B)DGEBHFCA C)ABCDEFGH D)ACBFEDHG树是结点的集合，它的根结点数目是 A)有且只有1B)1或多于1 C)0或1D)至少2下列叙述中正确的是 A)线性表是线性结构B)栈与队列是非线性结构 C)线性链表是非线性结构D)二叉树是线性结构,例题讲解,在深度为5的满二叉树中，叶子结点的个数为 A)32B)31 C)16 D)15 若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是 A)bdgcefha B)gdbecfha C)bdgaechf D)gdbehfca在树结构中，树根结点没有【1】。具有3

32、个结点的二叉树有 A)2种形态 B)4种形态 C)7种形态 D)5种形态设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为 A)12 B)13 C)14D)15,双亲结点,设一棵完全二叉树共有700个结点，则该二叉树中有（）个叶子结点。在一个容量为15的循环队列中，若头指针front=6，尾指针rear=9，则该循环队列中共有（）个元素。设一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为（）。,350,3,DEBFCA,设有下列二叉树：对此二叉树前序遍历的结果为A)ZBTTCPXA B)ATBZXCTP C)ZBTACTXP D)AT

33、BZXCPT,76,查找技术,查找是在一个给定的数据结构中，根据给定的条件查找满足条件的结点。不同的数据结构采用不同的查找方法。查找的效率直接影响数据处理的效率。查找的结果：查找成功：找到满足条件的结点查找失败：找不到满足条件的结点。通常根据不同的数据结构，采用不同的查找方法：顺序查找 二分查找,顺序查找（线性查找）,查找过程：对给定的一关键字K，从线性表的一端开始，逐个进行记录的关键字和K的比较，直到找到关键字等于K的记录或到达表的另一端。可以采用从前向后查，也可采用从后向前查的方法。在平均情况下，大约要与表中一半以上元素进行比较，效率较低。平均查找长度较大。最好情况：1 最坏情况：n在下面

34、两种情况下只能采取顺序查找：a.线性表为无序表（元素排列是无序的）；b.即使是有序线性表，但采用的是链式存储结构。,折半查找（二分法查找）,思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。前提：必须在具有顺序存储结构的有序表中进行。分三种情况：1）若中间项的值等于x,则说明已查到。2）若x小于中间项的值,则在线性表的前半部分查找；3）若x大于中间项的值，则在线性表的后半部分查找。特点：比顺序查找方法效率高。最坏的情况下，需要比较 log2n次。,折半查找算法举例,对给定数列（有序）3，5，11，17，21，23，28，30，32，50，按折半查找算法，查找关

35、键字值为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,80,练习假设待查有序（升序）顺序表中数据元素的关键字序列为（8,18,27,42,47,50,56,68,95,120），用折半查找方法查找关键字值为27的数据元素.,对于长度为n的有序线性表，最坏情况只需比较lo

36、g2n次。,81,排序技术,排序指将一个无序序列整理成按关键字值递增或递减排列的有序序列。排序方法中其排序对象一般是顺序存储的线性表。根据排序序列的规模以及数据处理的要求，可以采用不同的排序方法,排序方法,插入排序,选择排序,交换排序,归并排序,简单插入排序,希尔排序,简单选择排序,堆排序,起泡排序,快速排序,插入排序 简单插入、希尔排序,1、简单插入排序:基本思想：从数组的第2号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上。,该算法适合于n 较小的情况，时间复杂度为O(n2).,待排元素序列：53 27 36 15 69 42第一次排序：27 53 36

37、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趟,最坏情况下：需要n(n-1)/2次比较最好：n-1次比较,希尔排序：,希尔排序的基本思想:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序.最坏情况下：需要O(n1.5)次比较,1、简单选择排序 思想：首先从1n个元素中选出关键字最小的记录交换到第

38、一个位置上。然后再从第2 个到第n个元素中选出次小的记录交换到第二个位置上，依次类推。,选择排序 简单选择排序、堆排序,初态,8 3 9 1 6,8 3 9 1 6,8 3 9 1 6,8 3 9 1 6,1 3 9 8 6,1 3 9 8 6,1 3 9 8 6,时间复杂度为O(n2)，适用于待排序元素较少的情况。,比较次数：n(n-1)/2次,选择排序,选择排序的方法：扫描整个线性表，从中找出最小的元素，与第一个元素交换；除第一个元素，对剩下的子表采用相同的方法找出次小的数，与第二个数交换；重复上述过程；对于长度为n的线性表，选择排序需要对表扫描n-1遍。,简单选择排序法,最坏情况需要n(

39、n-1)/2次比较；,初态：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，15，15 37，22，30第五趟：11，14，15，15，22 37，30第六趟：11，14，15，15，22，30 37 有序序列,例：设待排数据元素的关键字为（15，14，22，30，37，11），每一趟排序后的序列状态如图所示：,2、堆排序（也是一种选择排序）堆是具有特定条件的顺序存储的完全二叉树，其特定条件是：任何一个非叶子结点的关键字大于等于（或小于等于

40、）子女的关键字的值。,(a):堆顶元素取最大值,(b):堆顶元素取最小值,堆排序需要比较的次数为O(nlog2n),(1)堆的示例,交 换 排 序交换排序的特点在于交换。有冒泡和快速排序两种。1、冒泡排序（起泡排序）思想：小的浮起，大的沉底。从左端开始比较。第一趟：第1个与第2个比较，大则交换；第2个与第3个比较，大则交换，关键字最大的记录交换到最后一个位置上；第二趟：对前n-1个记录进行同样的操作，关键字次大的记录交换 到第n-1个位置上；依次类推，则完成排序。,第六趟排序后,第五趟排序后,第四趟排序后,第三趟排序后,第二趟排序后,第一趟排序后,初始关键字,思想：小的浮起，大的沉底。,排序n

41、个记录最多需要n-1趟冒泡排序正序：比较次数为O(n-1)逆序：比较次数为O(n(n-1)/2)适合于数据较少的情况。,2、快速排序(对冒泡排序的改进）思想：通过一趟排序将待排序列分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分排序，以达到整个序列有序。时间复杂度：O(log2n)当待排序列逆序时，蜕变成冒泡排序，时间复杂度:O(n(n-1)/2),内部排序方法的选择各种排序方法各有优缺点，故在不同情况下可作不同的选择。通常需考虑的因素有：待排序的记录个数；记录本身的大小；记录的键值分布情况等。若待排序的记录个数n较小时，可采用简单排序方法。若n 较大时，应采用快速排序或堆

42、排序。若待排序的记录已基本有序，可采用简单插入和起泡 排序。,查找:,排序:,n-1n(n-1)/2,n1.5,n(n-1)/2,nlog2n,n-1n(n-1)/2,log2n,n(n-1)/2,正序的表、n小的表,与表的初始数据无关、n小的表,正序的表、n小的表,n大的表,但逆序的表会蜕变为起泡排序,借助辅助空间最多的方法,n大的表,97,排序查找方面的考题：,(1)对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是（2005年4月）A)冒泡排序为n/2 B)冒泡排序为nC)快速排序为n D)快速排序为n(n-1)/2(2)在长为64的有序线性表中进行顺序查找，最坏

43、情况下需要比较的次数为_。（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,98,第二章 程序设计基础,内容：1.程序设计方法与风格。2.结构化程序设计。3.面向对象的程序设计方法，对象，方法，属性及继承与多态性。,99,结构化程序设计,结构化程序设计方法的四条原则是：1.自顶向下；2.逐步求精；3.模块化；4.限制使用

44、goto语句。结构化程序的基本结构和特点：（1）顺序结构：简单的程序设计，最基本、最常用的结构；（2）选择结构（分支结构）：包括简单选择和多分支选择结构，（3）重复结构（循环结构）：可根据给定条件，判断是否需要重复执行某一相同程序段。,2.1 程序设计方法与风格,2.1.1 程序设计方法结构化设计方法面向对象程序设计方法,1.源程序的文档化符号的命名:见名知意注释（序言性和功能性注释）程序的视觉组织:空格、空行、缩进。2.数据说明数据说明的次序应该规范化变量安排有序化对复杂数据结构应注释说明3.语句的结构每条语句简单明了尽量不用或少用GOTO语句尽量只采用3种基本控制结构编程4.输入和输出对所

45、有输入数据进行校验和合理性检查输入输出格式保持一致设计良好的输出报表,清晰第一，效率第二,2.1.2 程序设计风格,2.2 结构化程序设计,2.2.1 基本概念基本思想 对大型的程序设计，使用一些基本的结构来设计程序，无论多复杂的程序，都可以使用这些基本结构按一定的顺序组合起来。这些基本结构的特点都是只有一个入口、一个出口。由这些基本结构组成的程序就避免了任意转移、阅读起来需要来回寻找的问题。三种基本结构顺序结构选择结构循环结构三种基本结构的特点只有一个入口只有一个出口每一个基本结构中的每一部分都有机会执行到结构内不存在“死循环”,2.2.2 设计原则自顶向下（先总体，后细节）逐步求精（设计子

46、目标过渡）模块化（分解总目标）限制使用goto语句,结构化程序设计方法特点要求把程序的结构规定为顺序、选择和循环三种基本机构，并提出了自顶向下、逐步求精、模块化程序设计等原则。结构化程序设计是把模块分割方法作为对大型系统进行分析的手段，使其最终转化为三种基本结构，其目的是为了解决由许多人共同开发大型软件时，如何高效率地完成可靠系统的问题。缺点：程序和数据结构松散地耦合在一起。解决此问题的方法就是采用面向对象的程序设计方法(OOP)。,2.3 面向对象的程序设计方法,2.3.1 关于面向对象方法对系统的复杂性进行概括、抽象和分类，使软件的设计与现实形成一个由抽象到具体、由简单到复杂这样一个循序渐

47、进的过程，从而解决大型软件研制中存在的效率低、质量难以保证、调试复杂、维护困难等问题。结构化的分解突出过程，即如何做(How to do)?它强调代码的功能是如何实现的；面向对象的分解突出现实世界和抽象的对象，即做什么(What to do)?,主要优点与人类习惯的思维方法一致稳定性好可重用性好可维护性好易于开发大型软件产品,2.3.2 基本概念对象(Object)对象是基本的运行时认得实体，它既包括数据（属性），也包括作用于数据的操作（行为）。一个对象把属性和行为封装为一个整体一个对象通常可由对象名、属性和操作3部分组成对象的基本特性：（1）标识唯一性（对象可区分）（2）分类性（对象抽象成类

48、）（3）多态性（同一操作可以是不同对象的行为）（4）封装性（只能看到对象的外部特性）（5）模块独立性好（对象内部各元素结合紧密、内聚性强）,类(Class)和实例一个类定义了一组大体上相似的对象。一个类所包含的方法和数据描述一组对象的共同行为和属性。类是在对象之上的抽象，对象是类的具体化，是类的实例封装(Encapsulation)将数据和操作数据的函数衔接在一起，构成一个具有类类型的对象的描述。对象的内部实现受保护，外界不能访问封装简化了程序员对对象的使用,继承(Inheritance)继承是父类和子类之间共享数据的方法的机制一个子类可以继承它的父类（或祖先类）中的属性和操作子类中可以定义自

49、己的属性和操作单重继承、多重继承多态性(Polymorphism)不同的对象收到同一消息可以产生完全不同的结构，这一现象叫做多态性多态的实现受到继承的支持,消息(Message)对象之间进行通信的一种构造,结构化程序设计的3种结构是 A)顺序结构、选择结构、转移结构 B)分支结构、等价结构、循环结构 C)多分支结构、赋值结构、等价结构 D)顺序结构、选择结构、循环结构在设计程序时，应采纳的原则之一是 A)不限制goto语句的使用 B)减少或取消注解行 C)程序越短越好 D)程序结构应有助于读者理解程序设计语言的基本成分是数据成分、运算成分、控制成分和 A)对象成分B)变量成分 C)语句成分D)

50、传输成分,例题讲解,结构化程序设计主要强调的是 A)程序的规模B)程序的效率 C)程序设计语言的先进性 D)程序易读性 以下不属于对象的基本特点的是 A)分类性 B)多态性 C)继承性D)封装性 对建立良好的程序设计风格，下面描述正确的是 A)程序应简单、清晰、可读性好 B)符号名的命名只要符合语法 C)充分考虑程序的执行效率 D)程序的注释可有可无在结构化程序设计思想提出之前，在程序设计中曾强调程序的效率，现在，与程序的效率相比，人们更重视程序的 A)安全性B)一致性 C)可理解性D)合理性,程序的3种基本控制结构是 A)过程、子过程和分程序B)顺序、选择和重复 C)递归、堆栈和队列 D)调