二级公共基础知识.ppt

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

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

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

3、黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。5.程序的调试，静态调试与动态调试。,公共基础考试大纲,四、数据库设计基础1.数据库的基本概念：数据库，数据库管理系统，数据库系统。2.数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。3.关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。4.数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。,公共基础考试大纲,考试方式 公共基础知识有10道选择题和5道填空题共三十分。,第一章 数据结构与算法,1、算法：解决问题的方案。例如：求出a,b,c 3个数的最大值。,解决方案e=a

4、 if be e=b if cee=c,写出交换两个大小相同的杯子中 的液体(A 水、B 酒)的一个算法,第一步,找一个大小与A相同的空杯子C.第二步,将A 中的水倒入C中.第三步,将B中的酒精倒入A中.第四步,将C中的水倒入B中,结束.,设计一个算法判断7是否为质数.,第一步,用2除7,得到余数1.因为余数不为0，所以2不能整除7.,第二步,用3除7,得到余数1.因为余数不为0，所以3不能整除7.,第三步,用4除7,得到余数3.因为余数不为0，所以4不能整除7.,第四步,用5除7,得到余数2.因为余数不为0，所以5不能整除7.,第五步,用6除7,得到余数1.因为余数不为0，所以6不能整除7.

5、因此，7是质数.,二分法,对于区间a,b 上连续不断、且f(a)f(b)0的函数y=f(x),通过不断地把函数f(x)的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫做二分法.,探究解决,解决问题,第四步,若f(a)f(m)0,则含零点的区间为a,m；,第一步,令.给定精确度d.,第二步,给定区间a,b,满足f(a)f(b)0,第三步,取中间点,第五步,判断a,b的长度是否小于d或者f(m)是否等于.,将新得到的含零点的仍然记为a,b.,否则，含零点的区间为m,b.,若是，则m是方程的近似 解;否则，返回第三步,解决问题,当d=0.05时,一个农夫带着一只狼、

6、一头山羊和一篮蔬菜要过河,但只有一条小船.乘船时,农夫只能带一样东西.当农夫在场的时候,这三样东西相安无事.一旦农夫不在,狼会吃羊,羊会吃菜.请设计一个方案,使农夫能安全地将这三样东西带过河.,算法的基本特征,可行性确定性有穷性拥有足够的情报,算法的复杂度,算法的复杂度分为：时间复杂度和空间复杂度。时间复杂度：执行算法时所需要的工作量。用执行算法时所需要的基本运算次数来衡量。空间复杂度：执行算法所需要的内存空间。,数据结构,数据结构：具有一定结构的相关数据集合。数据结构分为：逻辑结构和物理结构,数据的逻辑结构,数据逻辑结构描述了数据结构里相关数据元素的逻辑关系，逻辑关系就是前后件关系。,春,夏

7、,秋,冬,逻辑结构的分类,按照逻辑关系的不同逻辑结构分为线性结构和非线性结构。线性结构：数据结构里面的数据元素的前后关系是线性的。非线性结构：数据结构里面的数据元素的前后件关系是非线性的。,线性结构,春,夏,秋,冬,线性结构的特点,对于非空的线性结构有如下特点：第一个元素没有前件。最后一个元素没有后件。除了最后一个和第一的其它元素有且只有前件和一个后件。,春,夏,秋,冬,线性结构的存储方式,按照线性结构里面元素的存储方式不同分为顺序存储和链式存储。顺序存储：按照数据元素的逻辑关系依次连续存储在计算机的存储空间中链式存储：数据随机存储在计算机中存储空间中，数据的逻辑关系由相应的指针表示。,顺序表

8、的特点,顺序存储的线性表称为顺序表。,春,夏,秋,冬,春,夏,秋,冬,101,103,105,107,顺序表的特点,存储空间连续在存储空间里的元素前后关系和逻辑上的前后关系一致可以随机访问元素对于元素的很多的线性表不便进行插入和删除运算。,线性链表的特点,线性链表的元素是随机存在的计算机的存储空间上，线性链表里除了需要存储数据元素本身之外(数据域)，还需要一个存储下一元素的地址（指针域）。,春,101,234,夏,500,秋,206,冬,null,101,500,500,线性链表的特点,随机存储，空间不连续顺序访问元素。插入和删除元素时不需要更改元素的位置，只需要更改相应的元素的指针域内容即可

9、。,栈和队列,栈和队列都是特殊的线性结构。栈：允许在一段插入和删除的特殊线性表。允许插入的一端为栈顶，不允许插入和删除的那端称为栈底。,栈的特点及运算,特点：先进后出基本运算：入栈，出栈，读栈顶元素。入栈时如果栈中已满，称为上溢错误。出栈时栈中没有元素，称为下溢错误。,队列的运算及特点,先进先出。允许在一端插入，而在另一端删除元素的线性表。允许插入一端为队尾，插入操作称为入队。允许删除一端为队头，删除操作称为出队。,树,a,b,c,d,e,f,g,h,g,m,i,l,k,树的定义和基本术语定义：树(Tree)是n(n=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：（1）有且仅

10、有一个特定的称为根的结点；（2）其余的结点可分为m（m=0）个互不相交的子集T1，T2，,Tm,其中每个子集又是一棵树，并称其为子树。,树的基本概念,根结点：没父结点的结点。树的深度，结点的度，叶子结点，树的度。,树的三种形态,A,A,B,C,E,F,G,H,D,(a),（空树）,(b),(c),A,B,C,E,F,G,H,D,结点：在树中通常把数据元素和构造数据元素之间关系的指针统称为结点。比如左图中有8个结点。结点A的元素为A，有3个分别指向结点B、C、D的指针。,A,B,C,E,F,G,H,D,结点的度：结点所拥有的子树个数称为该结点的度。比如图中，结点A有3个子树，所以它的度为3。,A

11、,B,C,E,F,G,H,D,叶子结点：度数为0的结点称作叶子结点。比如图中结点E、F、G、H都是叶子结点。,A,B,C,E,F,G,H,D,孩子结点：一个结点的子树的根结点称作该结点的孩子结点。比如图中，结点B、C、D是结点A的孩子结点。,A,B,C,E,F,G,H,D,双亲结点：若一个结点有孩子结点，则该结点被称作它的孩子结点的双亲结点。比如图中，结点B、C、D的双亲结点都是A。需要注意的是，根结点没有双亲结点，根结点之外的其他结点的双亲结点是唯一的。,A,B,C,E,F,G,H,D,兄弟结点：具有同一个双亲结点的所有结点互称为兄弟结点。比如图中，结点B、C、D互相之间称为兄弟结点。,A,

12、B,C,E,F,G,H,D,结点的祖先：是从根到该结点所经分支上的所有结点。结点的子孙：是以该结点为根的所有子树上的结点。,A,B,C,E,F,G,H,D,结点的层次：我们称根结点位于树的第1层。某个结点所处的层次数是其双亲结点的层次数加1。比如，根结点A的层次为第1层，结点B、C、D的层次为第2层，结点E、F、G、H的层次为第3层。,A,B,C,E,F,G,H,D,树的高度（或者称为树的深度）：树中处在最高层的结点的层次数就是树的高度。比如左图所示树的高度为4。,树的度：所有节点中最大的度3。,G,注意二者区别！,二叉树(Binary Tree),定义,五种形态,一棵二叉树是结点的一个有限集

13、合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,特点,每个结点至多只有两棵子树（二叉树中不存在度大于2的结点）,哪些是二叉树？,A,A,A,B,A,B,B,C,C,D,E,F,满二叉树,指除最后一层外，每一层上的所有结点的都有两个子结点的二叉树。,满二叉树,1,2,3,4,5,7,6,1,2,3,4,5,7,6,8,9,11,10,12,13,14,15,满二叉树的特点,满二叉树第i层上有,2i-1,每一层的结点都达到最大值,一个深度为k的满二叉树的总结点数为：,2k-1,只存在度为0和度为2的结点，度为0的结点为最后一层，其它层的结点为度为2的

14、结点。,定义2 完全二叉树(Complete Binary Tree)若设二叉树的高度为h，则共有h层。除第 h 层外，其它各层(1 h-1)的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。,特点：若对结点按从上到下，自左至右连续编号，则完全二叉树每个结点和相同高度满二叉树的编号结点一一对应。叶结点只可能在层次最大的两层上出现。任一结点，若其右分支下的子孙的最大层次为l,则其左分支下的子孙的最大层次必为l或l+1。,谁是完全二叉树？,或者这样判断：如果在一棵深度为k(k=1)的满二叉树上删去第k层上最右边的连续j(0=j)个结点，就得到一棵深度为k的完全二叉树。,二

15、叉树性质,性质1：在二叉树的第i层上的结点数2i-1（i0）,性质2：深度为k的二叉树的结点数2k-1（k0）,性质3：对任一棵非空的二叉树T，如果其叶子数为n0，度为2的结点数为n2，则有下面的关系式成立：n0=n2+1,性质4：有n个结点的完全二叉树(n0)的深度为log2n+1,性质5：在编号的完全二叉树中，各结点的编号之间的关系为：编号为i的结点如果存在左孩子，则其编号为2i，如果存在右孩子，则其编号为2i+1，如果存在父结点，则其编号为i/2,性质1 在二叉树的第 i 层上至多有 2i 1个结点。(i 1)证明用归纳法证明：当i=1时，只有根结点，2 i-1=2 0=1。假设对所有j

16、，ij1，命题成立，即第j层上至多有2 j-1 个结点。由归纳假设第i-1 层上至多有 2i 2个结点。由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2*2i 2=2 i-1。,二叉树的性质,性质2 深度为 k 的二叉树至多有 2 k-1个结点(k 1)。证明：由性质1可见，深度为k的二叉树的最大结点数为,性质3 对任何一棵二叉树T,如果其叶结点数为 n0,度为2的结点数为 n2,则n0n21.证明：若度为1的结点有 n1 个，总结点个数为 n，总边数为 e，则根据二叉树的定义，n=n0+n1+n2（结点总度数计算）e=2n2+n1=n 1（边数

17、结点数减一）因此，有 2n2+n1=n0+n1+n2-1 n2=n0-1 n0=n2+1,性质4 具有 n(n 0)个结点的完全二叉树的深度为log2(n)1。证明：设完全二叉树的深度为 h，则根据性质2和完全二叉树的定义有2h1-1 n 2h-1或 2h1 n 2h取对数 h1 log2n h，又h是整数，因此有 h=log2(n)1,性质5 如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号 1,2,n，则有以下关系：若i=1,则 i 无双亲;若i 1,则 i 的双亲为i/2;若2i n,则 i 无左孩子;否则，i的左孩子为2i;若2i+1 n,则 i无右孩子;否则，i的

18、右孩子为2i+1;,例：一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为_。A.349B.350C.255D.351考点数据结构与算法评析完全二叉树：若二叉树中最多只有最下面两层的结点的度可以小于2，并且最下面一层的结点（叶结点）都依次排列在该层最左边的位置上，这样的二叉树为完全二叉树。完全二叉树除叶结点层外的所有结点数（叶结点层以上所有结点数）为奇数，此题中，699是奇数，叶结点层以上的所有结点数为保证是奇数，则叶结点数必是偶数，这样我们可以立即选出答案为B！如果完全二叉树的叶结点都排满了，则是满二叉树，易得满二叉树的叶结点数是其以上所有层结点数+1此题的其实是一棵满二叉树，我们

19、根据以上性质，699+1=700，700/2=350，即叶结点数为350，叶结点层以上所有结点数为350-1=349。,书P47 填空题 2,设n0,n1,n2为度为0,1,2的节点对任意二叉树有 n0=n2+1.(1)对于完全二叉树而言,叶子节点只出现在最后2层.即每个节点左右子数的高度最多相差1可以很容易知道,完全二叉树中度为1的节点为0个或1个(即至多1个)由n0+n1+n2=total,且有(1)式得,2*n0=total+1-n1,n1=0或1显然,当total+1为偶数时,n1取0;当total+1为奇数时,n1取1故：n0=(total+1)/2,注意：完全二叉树中度为1的节点数

20、为1或者0，故叶子数n0=(total+1)/2,重要！,遍历二叉树,定义：树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。,设访问根结点记作 D 遍历根的左子树记作 L 遍历根的右子树记作 R 则可能的遍历次序有 先序 DLR 中序 LDR 后序 LRD,二叉树的遍历,前序遍历：根结点，左子树，右子树后序遍历：左子树，右子树，根结点中序遍历：左子树，根结点，右子树在遍历子树的时候，也是按照相应的遍历规则进行遍历。,D L R,前序遍历序列：A B D C,前序遍历:先访问根结点,然后分别先序遍历左子树、右子树,L D R,中序遍历序列：B D A C,中序遍历:先中序

21、遍历左子树，然后访问根结点，最后中序遍历右子树,L R D,后序遍历序列：D B C A,后序遍历:先后序遍历左、右子树，然后访问根结点,例如：,先序序列：,中序序列：,后序序列：,A B C D E F G H K,B D C A E H G K F,D C B H K G F E A,遍历的特点,在前序中每个子树中最前面的结点一定是该子树的根结点。在后序中每棵子树中最后一个结点一定是该树的根结点。在中序中每棵子树中根结点右侧的子树结点一定是该子树中左子树存在的结点，右侧的子树结点一定是该子树中右子树存在的结点。,例：已知前序序列为 ABHFDECKG，中序序列为 HBDFAEKCG,试构造

22、二叉树。解：过程如下：,查找技术,查找分为顺序查找和二分法查找。顺序查找的适用情况：线性表为无序表（里面元素不是升序排序也不是降序排序）；采用链式存储的表。二分法查找适用的情况顺序存储的有序线性表。,排序技术,1、交换类排序 A、冒泡法排序 前后顺序交换改变逆序n(n-1)/2 B、快速排序法 取一个中点两边与中点比较交换2、插入类排序 A、简单插入排序 从第一个开始小的插在前n(n-1)/2 B、希尔排序法 分成若于子序列排序后减少子序列个数。,3、选择类排序法 A、简单选择排序法 找出最小元素排在队列前n(n-1)/2 B、堆排序法 建二叉树、调整二叉树位置达到排序效果。,排序算法复杂度,

23、第二章 程序设计基础,程序设计：设计，编制，调试程序的方法和过程。程序设计风格的要求 根据需要添加相应的注释，在程序正确的前提下，要做到清晰第一，效率第二。注释分为：功能性注释和序言性注释。,软件危机,软件危机是指在开发软件的过程中所遇到的一系列问题。出现软件危机之后，人们在开发软件过程中，开始关注结构化程序设计，引入软件工程思想。,结构化程序设计原则,自顶向下：先全局，后局部。逐步求精：逐步细化模块化：问题分解限制使用goto语句,面向对象程序设计,程序设计方法分为：面向过程和面向对象。面向过程程序设计是一过程为单位组装程序的过程，面向对象程序设计的过程是组装类的过程。,对象:客观世界的任何

24、事物。对象的静态特性：属性对象的动态特性：动作，行为，方法。在面向对象编程中，一个对象是属性和行为的封装体。类和实例 具有共同属性和行为的类的集合称为类。类是关于对象的抽象描述。一个具体对象对应类的一个实例。大学生：类。学生张某：类的实例。消息类之间传递信息的方式。,继承:是指直接获得已经存在的性质和特征，而不比重复定义它们。多态性 同样的消息被不同对象接受时导致完全不同行为的现象。,软件,软件：程序，数据，相关文档的集合软件特点：1、抽象性2、不存在明显的制作过程。3、在运行期间不存在磨损和老化问题。4、对计算机系统有依赖性。,软件工程,软件工程概念的出现源自软件危机。通过认真研究消除软件危

25、机的途径，逐渐行程了一门新兴的工程学科计算机软件工程学（简称软件工程）软件工程包括3个要素：方法、工具和过程,软件工程研究内容分为：软件开发技术和软件工程管理 软件工程规则：抽象，信息屏蔽，模块化，局部化，确定性，一致性，完备性，可验证性。,软件生命周期,软件生命周期：软件产品从提出、实现、使用维护到停止使用退役的过程。软件生命周期分为3个时期8个阶段，软件定义期：包括问题定义、可行性研究和需求分析3个阶段软件开发期：包括概要设计和详细设计、实现和测试4个阶段。其中概要设计和详细设计可合为软件设计阶段。运行维护期：即运行维护阶段。,结构化分析方法,需求分析是发现和了解目标用户的需求，进而确定软

26、件的功能，建立相应的需求模型。需求分析阶段分为4个方面：需求获取，需求分析，编写需求规格说明书，需求评审。,结构化分析方法的常用工具,数据流图（DFD）数据流图是用一些图形符号来表示程序中数据流向的一个工具。数据流图的图形元素：数据流，加工，存储文件，源和潭。,数据字典（DD）数据字典的作用是对数据流图里面出现的图形符号进行定义和详细解释说明的。数据流类型分为：事物型和变换型。,软件设计,从工程管理角度看，软件设计分为概要设计和详细设计。概要设计：把需求分析阶段确定的软件功能进行分解，分解为各个相应的几个模块。详细阶段的任务：确定每个模块的具体实现算法和细节。,详细阶段的工具：程序流程图，判定

27、表，pdl.程序流程图的图形符号。,模块独立性,模块独立性：耦合和内聚性。优秀的软件应该是高内聚，低偶合。耦合性：模块间之间的联系程度。内聚性：模块内各元素之间的联系程度。,软件测试的目的，及原则。,目的：发现错误原则：1、排除测试随意性。2、注意集群现象。3、避免检查自己的程序 4、穷举测试不可能，测试不能发现所有错误，测试不能程序中没有错误。,测试的分类,按照是否执行被测试软件分为：静态测试和动态测试。按照功能来划分：黑盒测试和白盒测试。白盒测试就是根据程序的内部逻辑结构来完成软件的功能测试。黑盒测试就是完全不考虑内部逻辑结构的一个功能测试。黑盒测试方法分为：等价类划分法，边界值分析法，错

28、误推测法，因果图。,软件测试的4个步骤及作用，依据。单元测试：以模块为单位的测试，主要发现模块内部的错误。集成测试：把模块组装起来进行的测试。主要发现模块间的接口错误。依据是概要设计说明书。确认测试：验证软件是否满足软件规格说明书。,软件调试,改正错误,第四章,数据，数据库，信息，数据库系统，数据管理发展经历的几个阶段及特点。,数据：符号。数据库：结构化相关数据集合。数据库管理系统：用来管理数据库和维护数据库的软件，ACCESS,VF,数据管理的几个阶段,人工管理阶段：主要用于人工计算，没有操作系统，没有数据和程序之分。文件系统阶段：提供了简单的数据共享和数据管理功能，数据和程序开始分开存储。

29、数据库系统阶段：数据独立性大大提供，共享性好。,数据一致性：同一个数据，在不同地方出现时，值应该是一致。,数据独立性,物理独立性和逻辑独立性逻辑独立性：数据库里面的局部数据逻辑改变时，可以不影响相应的程序。物理独立性：数据库里面的物理结构改变时不影响相应的程序。,数据库的3级模式,概念模式（模式）：全局数据逻辑结构的描述，全体用户的公共数据视图。外模式（子模式）：局部逻辑结构的描述，是用户所能看到的模式。内模式（物理模式）：数据库物理存户结构和存取方法的描述。例如：索引，存储路径。,E-R模型的概念及表示工具。,E-R实体联系模型（1）用矩形来表示实体集（2）用椭圆表示属性。（3）用菱形表示联系。,关系模型,行，列，主键（主码，关键字）关系运算（并，差，交，选择，投影，连接，笛卡尔积）,数据库设计,包括两方面内容：概念设计和逻辑设计。概念设计：建立概念数据模型，e-r模型逻辑设计：E-R转换称相应的关系。,