全国计算机等级考试二级公共基础知识讲义.doc
《全国计算机等级考试二级公共基础知识讲义.doc》由会员分享,可在线阅读,更多相关《全国计算机等级考试二级公共基础知识讲义.doc(22页珍藏版)》请在咨信网上搜索。
1、(完整版)全国计算机等级考试二级公共基础知识讲义全国计算机等级考试二级公共基础知识辅导讲义目录第一章 数据结构与算法11。1 算法11.2 数据结构的基本概念11。3 线性表及其顺序存储结构21。4 栈和队列21。5 线性链表31.6 树与二叉树41。7 查找技术51.8 排序技术6本章应考点拨6第二章 程序设计基础72。1 程序设计风格72.2 结构化程序设计(面向过程的程序设计方法)72。3 面向对象的程序设计8本章应考点拨8第三章 软件工程基础93。1 软件工程基本概念93。2 结构化分析方法103。3 结构化设计方法113.4 软件测试133。5 程序的调试15本章应考点拨15第四章
2、数据库设计基础164.1 数据库系统的基本概念164.2 数据模型184。3 关系代数204。4 数据库设计方法和步骤21本章应考点拨2121第一章 数据结构与算法1。1 算法1、算法是指解题方案的准确而完整的描述。换句话说,算法是对特定问题求解步骤的一种描述.*:算法不等于程序,也不等于计算方法。程序的编制不可能优于算法的设计这是因为:在编写程序时要受到计算机系统运行环境的限制,程序通常还要考虑很多与方法和分析无关的细节问题。.2、算法的基本特征(1)可行性。针对实际问题而设计的算法,执行后能够得到满意的结果。(2)确定性。每一条指令的含义明确,无二义性。并且在任何条件下,算法只有唯一的一条
3、执行路径,即相同的输入只能得出相同的输出。(3)有穷性.算法必须在有限的时间内完成.有两重含义,一是算法中的操作步骤为有限个,二是每个步骤都能在有限时间内完成。(4)拥有足够的情报。算法中各种运算总是要施加到各个运算对象上,而这些运算对象又可能具有某种初始状态,这就是算法执行的起点或依据.因此,一个算法执行的结果总是与输入的初始数据有关,不同的输入将会有不同的结果输出。当输入不够或输入错误时,算法将无法执行或执行有错.一般说来,当算法拥有足够的情报时,此算法才是有效的;而当提供的情报不够时,算法可能无效。*:综上所述,所谓算法,是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的,且是明确
4、的,此顺序将在有限的次数下终止。3、算法复杂度主要包括时间复杂度和空间复杂度。(1)算法时间复杂度是指执行算法所需要的计算工作量,可以用执行算法的过程中所需基本运算的执行次数来度量.(2)算法空间复杂度是指执行这个算法所需要的内存空间.1。2 数据结构的基本概念1、数据结构是指相互有关联的数据元素的集合。2、数据结构主要研究和讨论以下三个方面的问题:(1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构.数据的逻辑结构包含:1)表示数据元素的信息;2)表示各数据元素之间的前后件关系前后件关系:一般情况下,在具有相同特征的数据元素集合中,各个数据元素之间存在某种关系(即联系),这种关系
5、反映了该集合中的数据元素所固有的一种结构。在数据处理领域中,通常把数据元素之间这种固有的关系简单地用前后件关系(即直接前驱与直接后继关系)来描述。(2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构。数据的存储结构有顺序、链接、索引等。1)顺序存储。它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现.由此得到的存储表示称为顺序存储结构。2)链接存储。它不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构.3)索引存储:除建立存储结点信息外,还建立附加的索引表来标
6、识结点的地址.*:数据的逻辑结构反映数据元素之间的逻辑关系,数据的存储结构(也称数据的物理结构)是数据的逻辑结构在计算机存储空间中的存放形式。同一种逻辑结构的数据可以采用不同的存储结构,但影响数据处理效率。(3)对各种数据结构进行的运算。3、数据结构的图形表示一个数据结构除了用二元关系表示外,还可以直观地用图形表示.在数据结构的图形表示中,对于数据集合D中的每一个数据元素用中间标有元素值的方框表示,一般称之为数据结点,并简称为结点;为了进一步表示各数据元素之间的前后件关系,对于关系R中的每一个二元组,用一条有向线段从前件结点指向后件结点。4、数据结构分为两大类型:线性结构和非线性结构.(1)线
7、性结构(非空的数据结构)条件:1)有且只有一个根结点在数据结构中,没有前件的结点称为根结点。;2)每一个结点最多有一个前件,也最多有一个后件。*:常见的线性结构有线性表、栈、队列和线性链表等。(2)非线性结构:不满足线性结构条件的数据结构。:常见的非线性结构有树、二叉树和图等。1。3 线性表及其顺序存储结构1、线性表由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。线性表是由n(n0)个数据元素组成的一个有限序列,表中的每一个数据元素,除了第一个外,有且只有一个前件,除了最后一个外,有且只有一个后件。线性表中数据元素的个数称为线性表的长度。线性表可以为空表.2、
8、线性表的顺序存储结构具有两个基本特点:(1)线性表中所有元素所占的存储空间是连续的;(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。:由此可以看出,在线性表的顺序存储结构中,其前后件两个元素在存储空间中是紧邻的,且前件元素一定存储在后件元素的前面,可以通过计算机直接确定第i个结点的存储地址。3、顺序表的插入、删除运算(1)顺序表的插入运算:在一般情况下,要在第i(1in)个元素之前插入一个新元素时,首先要从最后一个(即第n个)元素开始,直到第i个元素之间共n-i+1个元素依次向后移动一个位置,移动结束后,第i个位置就被空出,然后将新元素插入到第i项。插入结束后,线性表的长度就增加了
9、1。:顺性表的插入运算时需要移动元素,在等概率情况下,平均需要移动n/2个元素.(2)顺序表的删除运算:在一般情况下,要删除第i(1in)个元素时,则要从第i+1个元素开始,直到第n个元素之间共ni个元素依次向前移动一个位置。删除结束后,线性表的长度就减小了1。*:进行顺性表的删除运算时也需要移动元素,在等概率情况下,平均需要移动(n1)/2个元素。插入、删除运算不方便。1.4 栈和队列1、栈及其基本运算栈是限定在一端进行插入与删除运算的线性表。在栈中,允许插入与删除的一端称为栈顶,不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素,栈底元素总是最先被插入的元素。即栈是按照“先进后
10、出”或“后进先出”的原则组织数据的.栈具有记忆作用。栈的基本运算:1)插入元素称为入栈运算;2)删除元素称为退栈运算;3)读栈顶元素是将栈顶元素赋给一个指定的变量,此时指针无变化。栈的存储方式和线性表类似,也有两种,即顺序栈和链式栈。2、队列及其基本运算队列是指允许在一端(队尾)进行插入,而在另一端(队头)进行删除的线性表.尾指针(Rear)指向队尾元素,头指针(front)指向排头元素的前一个位置(队头)。队列是“先进先出或“后进后出的线性表。队列运算包括:1)入队运算:从队尾插入一个元素;2)退队运算:从队头删除一个元素.循环队列及其运算:所谓循环队列,就是将队列存储空间的最后一个位置绕到
11、第一个位置,形成逻辑上的环状空间,供队列循环使用。在循环队列中,用队尾指针rear指向队列中的队尾元素,用排头指针front指向排头元素的前一个位置,因此,从头指针front指向的后一个位置直到队尾指针rear指向的位置之间,所有的元素均为队列中的元素.*:循环队列是队列的链式存储结构,循环队列中元素的个数=rearfront。1。5 线性链表1、线性表顺序存储的缺点:(1)插入或删除的运算效率很低.在顺序存储的线性表中,插入或删除数据元素时需要移动大量的数据元素;(2)线性表的顺序存储结构下,线性表的存储空间不便于扩充;(3)线性表的顺序存储结构不便于对存储空间的动态分配。2、线性链表:线性
12、表在这里特别要提醒考生注意一下,线性表是一种存储结构,它的存储方式:顺序和链式。的链式存储结构称为线性链表,是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接来实现的。因此,在链式存储方式中,每个结点由两部分组成:一部分用于存放数据元素的值,称为数据域;另一部分用于存放指针,称为指针域,用于指向该结点的前一个或后一个结点(即前件或后件),如下图所示:线性链表分为单链表、双向链表和循环链表三种类型.在单链表中,每一个结点只有一个指针域,由这个指针只能找到其后件结点,而不能找到其前件结点。因此,在某些应用中,对于线性链表中的每个结点设置两个指针,一个称为左指针,
13、指向其前件结点;另一个称为右指针,指向其后件结点,这种链表称为双向链表,如下图所示:3、线性链表的基本运算(1)在线性链表中包含指定元素的结点之前插入一个新元素.:在线性链表中插入元素时,不需要移动数据元素,只需要修改相关结点指针即可,也不会出现“上溢当为一个线性表分配顺序存储空间后,如果出现线性表的存储空间已满,但还需要插入新的元素时,就会发生“上溢”现象。”现象。(2)在线性链表中删除包含指定元素的结点.:在线性链表中删除元素时,也不需要移动数据元素,只需要修改相关结点指针即可。(3)将两个线性链表按要求合并成一个线性链表。(4)将一个线性链表按要求进行分解。(5)逆转线性链表。(6)复制
14、线性链表。(7)线性链表的排序。(8)线性链表的查找。:线性链表不能随机存取在链表中,即使知道被访问结点的序号i,也不能像顺序表中那样直接按序号i访问结点,而只能从链表的头指针出发,顺着链域逐个结点往下搜索,直至搜索到第i个结点为止。因此,链表不是随机存储结构。4、循环链表及其基本运算在线性链表中,其插入与删除的运算虽然比较方便,但还存在一个问题,在运算过程中对于空表和对第一个结点的处理必须单独考虑,使空表与非空表的运算不统一。为了克服线性链表的这个缺点,可以采用另一种链接方式,即循环链表。与前面所讨论的线性链表相比,循环链表具有以下两个特点:1)在链表中增加了一个表头结点,其数据域为任意或者
15、根据需要来设置,指针域指向线性表的第一个元素的结点,而循环链表的头指针指向表头结点;2)循环链表中最后一个结点的指针域不是空,而是指向表头结点。即在循环链表中,所有结点的指针构成了一个环状链.下图a是一个非空的循环链表,图b是一个空的循环链表:循环链表的优点主要体现在两个方面:一是在循环链表中,只要指出表中任何一个结点的位置,就可以从它出发访问到表中其他所有的结点,而线性单链表做不到这一点;二是由于在循环链表中设置了一个表头结点,在任何情况下,循环链表中至少有一个结点存在,从而使空表与非空表的运算统一。:循环链表是在单链表的基础上增加了一个表头结点,其插入和删除运算与单链表相同。但它可以从任一
16、结点出发来访问表中其他所有结点,并实现空表与非空表的运算的统一。1.6 树与二叉树1、树的基本概念树是一种简单的非线性结构.在树这种数据结构中,所有数据元素之间的关系具有明显的层次特性。在树结构中,每一个结点只有一个前件,称为父结点。没有前件的结点只有一个,称为树的根结点,简称树的根.每一个结点可以有多个后件,称为该结点的子结点.没有后件的结点称为叶子结点。在树结构中,一个结点所拥有的后件的个数称为该结点的度,所有结点中最大的度称为树的度。树的最大层次称为树的深度。2、二叉树及其基本性质(1)什么是二叉树二叉树是一种很有用的非线性结构,它具有以下两个特点:1)非空二叉树只有一个根结点;2)每一
17、个结点最多有两棵子树,且分别称为该结点的左子树与右子树。:根据二叉树的概念可知,二叉树的度可以为0(叶结点)、1(只有一棵子树)或2(有2棵子树)。(2)二叉树的基本性质性质1 在二叉树的第k层上,最多有 个结点。例:一棵二叉树第六层(根结点为第一层)的结点数最多为 个。性质2 深度为m的二叉树最多有 个结点。例:深度为5的二叉树至多有 个结点.性质3 在任意一棵二叉树中,度数为0的结点(即叶子结点)总比度为2的结点多一个.例:某二叉树中度数为2的结点有18个,则该二叉树中有 个叶子结点。性质4 具有n个结点的二叉树,其深度至少为 ,其中 表示取 的整数部分。例:具有88个结点的二叉树,其深度
18、至少为 .3、满二叉树与完全二叉树满二叉树:除最后一层外,每一层上的所有结点都有两个子结点。例:在深度为7的满二叉树中,叶子结点的个数为 个。完全二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点.:根据完全二叉树的定义可得出:度为1的结点的个数为0或1。下图a表示的是满二叉树,下图b表示的是完全二叉树:完全二叉树还具有如下两个特性:性质5 具有n个结点的完全二叉树深度为 。例:具有90个结点的完全二叉树的深度为 。性质6 设完全二叉树共有n个结点,如果从根结点开始,按层序(每一层从左到右)用自然数1,2,n给结点进行编号,则对于编号为k(k=1,2,n)的结
19、点有以下结论:若k=1,则该结点为根结点,它没有父结点;若k1,则该结点的父结点的编号为INT(k/2)。若2kn,则编号为k的左子结点编号为2k;否则该结点无左子结点(显然也没有右子结点).若2k+1n,则编号为k的右子结点编号为2k+1;否则该结点无右子结点。例:设一棵n个结点的完全二叉树从根结点这一层开始,每一层上的结点按从左到右的顺序存储在数组A中,设某个结点在数组中的位置为i,则其父结点的位置是 。4、二叉树的存储结构在计算机中,二叉树通常采用链式存储结构。与线性链表类似,用于存储二叉树中各元素的存储结点也由两部分组成:数据域和指针域。但在二叉树中,由于每一个元素可以有两个后件(即两
20、个子结点),因此,用于存储二叉树的存储结点的指针域有两个:一个用于指向该结点的左子结点的存储地址,称为左指针域;另一个用于指向该结点的右子结点的存储地址,称为右指针域.:一般二叉树通常采用链式存储结构,对于满二叉树与完全二叉树来说,可以按层序进行顺序存储这样,不仅节省了存储空间,又能方便地确定每一个结点的父结点与左右子结点的位置,但顺序存储结构对于一般的二叉树不适用。5、二叉树的遍历二叉树的遍历是指不重复地访问二叉树中的所有结点.二叉树的遍历可以分为以下三种:(1)前序遍历(DLR):若二叉树为空,则结束返回。否则:首先访问根结点,然后遍历左子树,最后遍历右子树;并且,在遍历左右子树时,仍然先
21、访问根结点,然后遍历左子树,最后遍历右子树。(2)中序遍历(LDR):若二叉树为空,则结束返回。否则:首先遍历左子树,然后访问根结点,最后遍历右子树;并且,在遍历左、右子树时,仍然先遍历左子树,然后访问根结点,最后遍历右子树。(3)后序遍历(LRD):若二叉树为空,则结束返回。否则:首先遍历左子树,然后遍历右子树,最后访问根结点,并且,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后访问根结点。1。7 查找技术查找:根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素。查找结果:(查找成功:找到;查找不成功:没找到。)平均查找长度:查找过程中关键字和给定值比较的平均次数。
22、1、顺序查找基本思想:从表中的第一个元素开始,将给定的值与表中逐个元素的关键字进行比较,直到两者相符,查到所要找的元素为止.否则就是表中没有要找的元素,查找不成功.在平均情况下,利用顺序查找法在线性表中查找一个元素,大约要与线性表中一半的元素进行比较,最坏情况下需要比较n次。顺序查找一个具有n个元素的线性表,其平均复杂度为O(n)。下列两种情况下只能采用顺序查找:1)如果线性表是无序表(即表中的元素是无序的),则不管是顺序存储结构还是链式存储结构,都只能用顺序查找。2)即使是有序线性表,如果采用链式存储结构,也只能用顺序查找。2、二分法查找思想:先确定待查找记录所在的范围,然后逐步缩小范围,直
23、到找到或确认找不到该记录为止。前提:必须在具有顺序存储结构的有序表中进行.查找过程:1)若中间项中间项mid=(n+1)/2,mid值不进位取整。的值等于x,则说明已查到;2)若x小于中间项的值,则在线性表的前半部分查找;3)若x大于中间项的值,则在线性表的后半部分查找。特点:比顺序查找方法效率高。最坏的情况下,需要比较log2n次.*:二分法查找只适用于顺序存储的线性表,且表中元素必须按关键字有序(升序,但允许相邻元素值相等)排列。对于无序线性表和线性表的链式存储结构只能用顺序查找.在长度为n的有序线性表中进行二分法查找,其时间复杂度为O(log2n)。1.8 排序技术排序是指将一个无序序列
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 全国 计算机等级考试 二级 公共 基础知识 讲义
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。