计算机等级考试二级公共基础知识点总结.doc
《计算机等级考试二级公共基础知识点总结.doc》由会员分享,可在线阅读,更多相关《计算机等级考试二级公共基础知识点总结.doc(13页珍藏版)》请在咨信网上搜索。
1、二级公共基础知识总结第一章 数据结构与算法心之所向,所向披靡1.1 算法算法:是一组有穷指令集,是解题方案的准确而完整的描述。通俗地说,算法就是计算机解题的过程。算法不等于程序,也不等于计算方法,程序的编制不可能优于算法的设计。算法是一组严谨地定义运算顺序的规则,每一个规则都是有效的,且是明确的,此顺序将在有限的次数下终止。所以其四个基本特征包括:(1)确定性,算法中每一步骤都必须有明确定义,不允许有模棱两可的解释,不允许有多义性; (2)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止;(3)可行性,算法原则上能够精确地执行;(4)拥有足够的情报。算法的基本要素:一是对数据对
2、象的运算和操作;二是算法的控制结构。指令系统:一个计算机系统能执行的所有指令的集合。基本运算和操作包括:算术运算、逻辑运算、关系运算、数据传输。算法的三种基本控制结构:顺序结构、选择结构、循环结构。算法基本设计方法:列举法、归纳法、递推、递归、减半递推技术、回溯法。算法效率的度量算法复杂度:算法时间复杂度和算法空间复杂度。算法时间复杂度:指执行算法所需要的计算工作量。即算法执行过程中所需要的基本运算次数。通常,一个算法所用的时间包括编译时间和运行时间。算法空间复杂度:指执行这个算法所需要的内存空间。包括算法程序所占的空间,输入的初始数据所占的空间,算法执行过程中所需的额外空间。1.2 数据结构
3、的基本概念数据结构:指相互有关联的数据元素的集合。数据结构研究的三个方面:(1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构;(2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;(3)对各种数据结构进行的运算。数据的逻辑结构应包含:(1)表示数据元素的信息;(2)表示各数据元素之间的前后件关系(指逻辑关系,与存储位置无关)。数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构,也称数据物理结构。数据的存储结构有顺序、链接、索引等。线性结构的条件,(一个非空数据结构):(1)有且只有一个根结点; (2)每一个结点最多有一个前件,也最多有一个后件。非线
4、性结构:不满足线性结构条件的数据结构。1.3 线性表及其顺序存储结构线性表是由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。在复杂线性表中,由若干项数据元素组成的数据元素称为记录;由多个记录构成的线性表称为文件。非空线性表的结构特征:(1)且只有一个根结点a1,它无前件;(2)有且只有一个终端结点an,它无后件;(3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。结点个数n称为线性表的长度,当n=0时,称为空表。线性表的顺序存储结构具有以下两个基本特点:(1)线性表中所有元素所占的存储空间是连续的;(2)线性表中各数据元素在存储空间中
5、是按逻辑顺序依次存放的。元素ai的存储地址为:ADR(ai)=ADR(a1)+(i-1)k,ADR(a1)为第一个元素的地址,k代表每个元素占的字节数。顺序表的运算:查找、插入、删除。 1.4线性链表数据结构中的每一个结点对应于一个存储单元,这种存储单元称为存储结点,简称结点。结点由两部分组成:(1) 用于存储数据元素值,称为数据域;(2) 用于存放指针,称为指针域,用于指向前一个或后一个结点。在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式即可用于表示线性结构,也可用于表示非线
6、性结构。线性单链表中,HEAD称为头指针,HEAD=NULL(或0)称为空表。如果是双项链表的两指针:左指针(Llink)指向前件结点,右指针(Rlink)指向后件结点。线性链表的基本运算:查找、插入、删除。1.5栈和队列栈:限定在一端进行插入与删除的线性表。其允许插入与删除的一端称为栈顶,用指针top表示栈顶位置。不允许插入与删除的另一端称为栈底,用指针bottom表示栈底。栈按照“先进后出”(FILO)或“后进先出”(LIFO)组织数据,栈具有记忆作用。栈的存储方式有顺序存储和链式存储。栈的基本运算:(1) 入栈运算,在栈顶位置插入元素;(2) 退栈运算,删除元素(取出栈顶元素并赋给一个指
7、定的变量);(3) 读栈顶元素,将栈顶元素赋给一个指定的变量,此时指针无变化。队列:指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。用rear指针指向队尾,用front指针指向队头元素的前一个位置。队列是“先进先出”(FIFO)或“后进后出”(LILO)的线性表。队列运算包括:(1) 入队运算:从队尾插入一个元素; (2) 退队运算:从队头删除一个元素。队列的顺序存储结构一般采用队列循环的形式。循环队列s=0表示队列空;s=1且front=rear表示队列满。计算循环队列的元素个数:“尾指针减头指针”,若为负数,再加其容量即可。1.6 树与二叉树树是一种简单的非线性结构,其所
8、有元素之间具有明显的层次特性。在树结构中,每一个结点只有一个前件,称为父结点。没有前件的结点只有一个,称为树的根结点,简称树的根。每一个结点可以有多个后件,称为该结点的子结点。没有后件的结点称为叶子结点。在树结构中,一个结点所拥有的后件的个数称为该结点的度,所有结点中最大的度称为树的度。树的最大层次称为树的深度。二叉树的特点:(1) 非空二叉树只有一个根结点;(2) 每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。满二叉树是指除最后一层外,每一层上的所有结点有两个子结点,则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。完全二叉树是指除最后一层外,每一层上的结点数均达到最
9、大值,在最后一层上只缺少右边的若干结点。二叉树基本性质:(1)在二叉树的第k层上,最多有2k-1(k1)个结点; (2)深度为m的二叉树最多有2m-1个结点; (3)度为0的结点(即叶子结点)总是比度为2的结点多一个; (4)具有n个结点的二叉树,其深度至少为log2n+1,其中log2n表示取log2n的整数部分(5) 具有n个结点的完全二叉树的深度为log2n+1;(6) 设完全二叉树共有n个结点。如果从根结点开始,按层序(每一层从左到右)用自然数1,2,n给结点进行编号(k=1,2.n),有以下结论:若k=1,则该结点为根结点,它没有父结点;若k1,则该结点的父结点编号为INT(k/2)
10、;若2kn,则k结点的左子结点编号为2k;否则该结点无左子结点(也无右子结点);若2k+1n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点。补充:增加度为1的结点不会影响二叉树的叶子结点数,每增加一个度为2的结点便会增加一个叶子结点,没有度为2的结点时叶子结点数为1。已知完全二叉树有x个结点,求其叶子结点数:确定层数为k; 第k层的结点数y=x-(2 k-1-1);第k-1层的叶子结点数n=2 (k-1)-1-y/2; 最后y+n。二叉树存储结构采用链式存储结构,对于满二叉树与完全二叉树可以按层序进行顺序存储。二叉树的遍历:(1)前序遍历(DLR),首先访问根结点,然后遍历左
11、子树,最后遍历右子树;(树根在第一,下走不跳结点)(2)中序遍历(LDR),首先遍历左子树,然后访问根结点,最后遍历右子树;(有左先左,再寻根,后找右。最左边的结点最先遍历,最右边的结点最后遍历)(3)后序遍历(LRD)首先遍历左子树,然后访问遍历右子树,最后访问根结点。(有左先左,再找右,后寻根,到最右一路上行,树根在最后)小结:逻辑结构可分为线性表和非线性表。 线性表包括栈、队列,其存储方式为顺序存储、链式存储均可。链式型有:线性链表,带链的栈, 带链的队列,循环链表等。 非线性表包括树(二叉树),其存储方式为链式存储。1.7 查找技术只能使用顺序查找的两种情况:(1)线性表为无序表,不管
12、是顺序存储还是链式存储;(2)表采用链式存储结构,即使是有序线性表。二分法查找只适用于顺序存储的有序表,对于长度为n的有序线性表,最坏情况只需比较log2n次,而顺序查找需要比较n次。1.8 排序技术排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。交换类排序法:(1)冒泡排序法,需要比较的次数为n(n-1)/2; (2 ) 快速排序法。插入类排序法:(1)简单插入排序法,最坏情况需要n(n-1)/2次比较; (2) 希尔排序法,最坏情况需要O(n1.5)次比较。选择类排序法:(1)简单选择排序法, 最坏情况需要n(n-1)/2次比较;(2) 堆排序法,最坏情况需要O(nlog2n)次
13、比较。相比以上几种(除希尔排序法外),堆排序法的时间复杂度最小。第二章 程序设计基础2.1 程序设计设计方法和风格“清晰第一、效率第二”已成为当今主导的程序设计风格。形成良好的程序设计风格需注意:(详见书P27)1、源程序文档化; 2、数据说明的方法; 3、语句的结构; 4、输入和输出。注释分序言性注释和功能性注释。 语句结构清晰第一、效率第二。2.2 结构化程序设计结构化程序设计方法的四条原则是:1、自顶向下; 2、逐步求精; 3、模块化; 4、限制使用goto语句。结构化程序的基本结构及特点:(1)顺序结构:一种简单的程序设计,最基本、最常用的结构;(2)选择结构:又称分支结构,包括简单选
14、择和多分支选择结构,可根据条件,判断应该 选择哪一条分支来执行相应的语句序列;(3)循环结构:又称重复结构,可根据给定条件,判断是否需要重复执行某一相同或类似的程序段。结构化程序设计的特点:只有一个入口和出口2.3 面向对象的程序设计面向对象的程序设计的首次提出以60年代末挪威奥斯陆大学和挪威计算机中心研制的SIMULA语言为标志。面向对象方法的优点:(1)与人类习惯的思维方法一致; (2)稳定性好; (3)可重用性好;(4)易于开发大型软件产品; (5)可维护性好。对象是面向对象方法中最基本的概念,可以用来表示客观世界中的任何实体,对象是实体的抽象。面向对象的程序设计方法中,对象是由数据的容
15、许的操作组成的封装体,是系统中用来描述客观事物的一个实体,是构成系统的一个基本单位,由一组表示其静态特征的属性和它可执行的一组操作组成。属性即对象所包含的信息,它在设计对象时确定,一般只能通过执行对象的操作来改变。操作描述了对象执行的功能,是对象的动态属性,操作也称为方法或服务。对象的基本特点:(1)标识惟一性; (2)分类性; (3)多态性; (4)封装性; (5)模块独立性好。类是指具有共同属性、共同方法的对象的集合。类是关于对象性质的描述。类是对象的抽象,对象是其对应类的一个实例。消息是一个实例与另一个实例之间传递的信息。对象间的通信靠消息传递。它请求对象执行某一处理或回答某一要求的信息
16、,它统一了数据流和控制流。消息的组成包括:(1)接收消息的对象的名称; (2)消息标识符,也称消息名; (3)零个或多个参数。继承是使用已有的类定义作为基础建立新类的定义技术,广义指能够直接获得已有的性质和特征,而不必重复定义他们。继承具有传递性,一个类实际上继承了他上层的全部基类的特性。继承分单继承和多重继承。单继承指一个类只允许有一个父类,即类等级为树形结构;多重继承指一个类允许有多个父类。多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象第三章 软件工程基础3.1 软件工程基本概念计算机软件是包括程序、数据及相关文档的完整集合。软件的特点包括:(1)软件是一种逻辑实体,具有
17、抽象性;(2)软件的生产与硬件不同,它没有明显的制作过程;(3)软件在运行、使用期间不存在磨损、老化问题;(4)软件的开发、运行对计算机系统具有依赖性,受计算机系统的限制,这导致了软件移植的问题;(5)软件复杂性高,成本昂贵;(6)软件开发涉及诸多的社会因素。软件按功能分为应用软件、系统软件、支撑软件(或工具软件)。软件危机主要表现在成本、质量、生产率等问题。软件工程是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。简单的说就是使软件走向工程化。软件工程的核心思想是把软件产品看作是一个工程产品来处理。软件工程包括3个要素:方法、工具和过程。软件工程过程是把软件转化为
18、输出的一组彼此相关的资源活动,包含4种基本活动:(1)P(plan)软件规格说明; (2)D(do)软件开发; (3)C(check)软件确认; (4)A(action)软件演进。软件生命周期:软件产品从提出、实现、使用维护到停止使用退役的过程。软件生命周期分三个阶段:软件定义、软件开发、运行维护,主要活动阶段是:(1)可行性研究与计划制定; (2)需求分析;(3)软件设计(概要设计和详细设计); (4)软件实现; (5)软件测试; (6)运行和维护。软件工程的目标:在给定成本、进度的前提下,开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足
19、用户需求的产品。基本目标:付出较低的开发成本;达到要求的软件功能;取得较好的软件性能;开发软件易于移植;需要较低的费用;能按时完成开发,及时交付使用。软件工程的理论和技术性研究的内容主要包括:软件开发技术和软件工程管理。软件开发技术包括:软件开发方法学、开发过程、开发工具和软件工程环境。软件开发环境或软件工程环境是指全面支持软件开发全过程的软件工具的集合。软件工程管理包括:软件管理学、软件工程经济学、软件心理学等内容。软件管理学包括人员组织、进度安排、质量保证、配置管理、项目计划等。软件工程基本原则:抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。3.2 结构化分析方法结构化
20、方法的核心和基础是结构化程序设计理论。软件定义阶段中,可行性研究与计划的制定是确定待开发目标和总的要求,给出它的功能、性能、可靠性以及接口等方面的可能方案,制定完成开发的实施计划。需求分析,对待开发软件提出的需求分析并给出详细的定义。需求分析阶段的工作:需求获取,需求分析,编写需求规格说明书,需求评审。需求分析方法有:(1)结构化需求分析方法; 面向数据结构的Jackson方法(ISD);面向数据流的结构化分析方法(SA);面向数据结构的结构化数据系统开发方法(DSSD);(2)面向对象的分析的方法(OOA)。从需求分析建立的模型的特性来分:静态分析和动态分析。结构化分析方法的实质:着眼于数据
21、流,自顶向下,逐层分解,建立系统的处理流程,以数据流图和数据字典为主要工具,建立系统的逻辑模型。结构化分析的常用工具:数据流图;数据字典;判定树;判定表。(1)数据流图(DFD图):描述数据处理过程的工具,是需求理解的逻辑模型的图形表示,它直接支持系统功能建模。加工(转换)圆框,输入数据经加工变换产生的输出。数据流箭头,沿箭头方向传递数据的通道,一般在旁边标注数据流名。存储文件(数据源)双横线,表示处理过程中存放各种数据的文件。源、潭方框,表示系统和环境的接口,属系统之外的实体。(2)数据字典:对所有与系统相关的数据元素的一个有组织的列表,以及精确的、严格的定义,使得用户和系统分析员对于输入、
22、输出、存储成分和中间计算结果有共同的理解。数据字典是结构化分析的核心。(3)判定树:从问题定义的文字描述中分清哪些是判定的条件,哪些是判定的结论,根据描述材料中的连接词找出判定条件之间的从属关系、并列关系、选择关系,根据它们构造判定树。(4)判定表:与判定树相似,当数据流图中的加工要依赖于多个逻辑条件的取值,即完成该加工的一组动作是由于某一组条件取值的组合而引发的,使用判定表描述比较适宜。软件需求规格说明书的特点:正确性; 无岐义性; 完整性; 可验证性; 一致性; 可理解性; 可修改性; 可追踪性。3.3 结构化设计方法软件设计是确定系统的物理模型。软件设计是开发阶段最重要的步骤,是将需求准
- 配套讲稿:
如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。