计算机二级公共基础知识总结.docx
《计算机二级公共基础知识总结.docx》由会员分享,可在线阅读,更多相关《计算机二级公共基础知识总结.docx(13页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、精品名师归纳总结第1章数据结构与算法1.1 算法的复杂度1. 算法的基本概念1、算法是指解题方案的精确而完整的描述。换句话说,算法是对特定问题求解步骤的一种描述。* 算法不等于程序,也不等运算机方法,程序的编制不行能优于算法的设计。(1) 算法的基本特点算法一般具有 4个基本特点:可行性、确定性、有穷性、拥有足够的情报。注:& 确定性,算法中每一步骤都必需有明确定义,不充许有模棱两可的说明,不答应有多义性。&有穷性,算法必需能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义。* 算法的基本要素: 一是对数据对象的运算和操作。 二是算法的掌握结构 。(2) * 算法的基本
2、运算和操作包括:算术运算、规律运算、关系运算、数据传输。(3) * 算法的 3种基本掌握结构是:次序结构、挑选结构、循环结构。(4) 算法基本设计方法:列举法、归纳法、递推、递归、减半递推技术、回溯法。(5) 指令系统 : 指的是一个运算机系统能执行的全部指令的集合。2. 算法复杂度* 算法复杂度包括时间复杂度和空间复杂度 。留意两者的区分,无混淆,见表1-1。表1-1算法复杂性 可编辑资料 - - - 欢迎下载精品名师归纳总结名称描述时间复杂度执行算法所需要的运算工作量空间复杂度执行这个算法所需要的内存空间1.2 数据结构可以用执行算法的过程中所需基本运算的执行次数来度量。可编辑资料 - -
3、 - 欢迎下载精品名师归纳总结1.2.1 规律结构和储备结构1. 数据结构的基本概念(1) * 数据结构 : 指相互有关联的数据元素的集合。2 数据结构讨论的三个方面: 、数据集合中各数据元素之间所固有的规律关系,即数据的规律结构。、在对数据进行处理时,各数据元素在运算机中的储备关系,即数据的储备结构 。、 对各种数据结构进行的运算。2. 规律结构数据的规律结构是对数据元素之间的规律关系的描述。数据的规律结构有两个要素:一是数据元素的集合, 通常记为 D 。二是 D 上的关系,它反映了数据元素之间的前后件关系,通常记为R。一个数据结构可以表示成: B=D,R3. 储备结构数据的储备结构有次序、
4、链接、索引等。注: 次序储备方式主要用于线性的数据结构,它把规律上相邻的数据元素储备在物理上相邻的储备单元里,结点之间的关系由储备单元的邻接关系来表达。链式储备结构就是在每个结点中至少包含一个指针域,用指针来表达数据元素之间规律上的联系。* :数据的规律结构反映数据元素之间的规律关系,数据的储备结构(也称数据的物理结构)是数据的逻辑结构在运算机储备空间中的存放形式。同一种规律结构的数据可以采纳不同的储备结构,但影响数据处理效率。1.2.2 线性结构和非线性结构依据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为两大类型:线性结构与非线性结构。(1)假如一个非空的数据结构满意以下
5、两个条件:* 有且只有一个根结点。 每一个结点最多有一个前件,也最多有一个后件。可编辑资料 - - - 欢迎下载精品名师归纳总结就称该数据结构为线性结构。线性结构又称线性表。在一个线性结构中插入或删除任何一个结点后仍应是线性结构。 栈、队列、串、线性链表等都为线性结构。假如一个数据结构不是线性结构,就称之为非线性结构。数组、广义表、树和图等数据结构都是非线性结构。1.2.3 线性表及其次序储备结构线性表的储备结构主要分为次序储备结构和链式储备结构线性表是由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。在复杂线性表中,由如干项数据元素组成的数据元素称为记录, 而
6、由多个记录构成的线性表又称为文件 。非空线性表的结构特点:( 1)且只有一个根结点a1,它无前件。( 2)有且只有一个终端结点an,它无后件。( 3)除根结点与终端结点外,其他全部结点有且只有一个前件,也有且只有一个后件。结点个数n 称为线性表的长度 ,当 n=0 时,称为 空表。* 线性表的次序储备结构具有以下两个基本特点:( 1)线性表中全部元素的所占的储备空间是连续的。( 2)线性表中各数据元素在储备空间中是按规律次序依次存放的。ai 的储备的址为: ADRai=ADRa1+i-1k,ADRa1为第一个元素的的址,k 代表每个元素占的字节数。次序表的运算:查找、插入、删除3 种。1.3
7、栈(重点)1. 栈的基本概念(栈( stack )是一种特别的线性表).栈是限定在一端进行插入与删除运算的线性表。.在栈中,答应插入与删除的一端称为栈顶,不答应插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素, 栈底元素总是最先被插入的元素。即栈是依据 “先进后出”( FILO)或“后进先出” LIFO的原就组织数据的。.栈具有记忆作用。注:用 top 表示栈顶位置,用 bottom 表示栈底。当表中没有元素时称为空栈2. 栈的基本运算:( 1)插入元素称为 入栈运算 。( 2)删除元素称为退栈运算 。( 3) 读栈顶元素 是将栈顶元素赋给一个指定的变量,此时指针无变化。运算栈的个数:
8、栈底栈顶 +1可编辑资料 - - - 欢迎下载精品名师归纳总结1. 队列的基本概念1.4 队列 重点可编辑资料 - - - 欢迎下载精品名师归纳总结队列是指答应在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。Rear指针指向队尾,front指针指向队头。队列是“先进先出”(FIFO)或“后进后出”( LILO)的线性表。2. 队列运算入队运算是往队列队尾插入一个数据元素。退队运算是从队列的队头删除一个数据元素。队列的次序储备结构一般采纳队列循环的形式。循环队列 s=0 表示队列空。 s=1 且 front=rear表示队列满。运算循环队列的元素个数:“尾指针减头指针”,如为负数,再
9、加其容量即可。队列是一种特别的线性表,循环队列是队列的次序储备结构。1.5 链表数据结构中的每一个结点对应于一个储备单元,这种储备单元称为储备结点,简称结点。结点由两部分组成:( 1)用于储备数据元素值,称为数据域 。( 2)用于存放指针,称为 指针域 ,用于指向前一个或后一个结点。在链式储备结构中,储备数据结构的储备空间可以不连续,各数据结点的储备次序与数据元素之间的规律关系可以不一样,而数据元素之间的规律关系是由指针域来确定的。链式储备方式即可用于表示线性结构,也可用于表示非线性结构。线性链表, HEAD称为头指针, HEAD=NUL(L 或 0)称为 空表 ,假如是两指针: 左指针 (L
10、link)指向前件结点, 右指针 ( Rlink )指向后件结点。线性链表的基本运算:查找、插入、删除。可编辑资料 - - - 欢迎下载精品名师归纳总结1、树的基本概念1.6 树与二叉树 可编辑资料 - - - 欢迎下载精品名师归纳总结树是一种简洁的非线性结构,全部元素之间具有明显的层次特性。在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点 ,简称树的根。每一个结点可以有多个后件,称为该结点的子结点 。没有后件的结点称为叶子结点。在树结构中, 一个结点所拥有的后件的个数称为该结点的度,全部结点中最大的度称为树的度。树的最大层次称为树的深度。2、二叉树及其基
11、本性质二叉树是一种很有用的非线性结构 ,具有以下两个特点: (1)非空二叉树只有一个根结点。(2)每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。基本性质 :性质 1 在二叉树的第 k 层上,最多有个结点。性质 2 深度为 m的二叉树最多有个个结点。性质 3 在任意一棵二叉树中,度数为0 的结点(即叶子结点)总比度为2 的结点多一个。性质 4 具有 n 个结点的二叉树,其深度至少为,其中表示取的整数部分3. 满二叉树与完全二叉树.满二叉树:除最终一层外,每一层上的全部结点都有两个子结点。.完全二叉树:除最终一层外,每一层上的结点数均达到最大值。在最终一层上只缺少右边的如干结点。留意
12、:深度为 m的满二叉树最多有个个结点完全二叉树具有以下两个性质:性质 1:具有 n个结点的完全二叉树的深度为。性质 2:设完全二叉树共有n个结点。 假如从根结点开头, 按层次(每一层从左到右) 用自然数 1,2, n给结点进行编号,就对于编号为k( k=1, 2, n)的结点有以下结论: 如k=1,就该结点为根结点,它没有父结点。如k1,就该结点的父结点编号为INT( k/2 )。 如2k n,就编号为 k的结点的左子结点编号为2k。否就该结点无左子结点(明显也没有右子结点)。 如 2k+1 n,就编号为 k 的结点的右子结点编号为2k+1。否就该结点无右子结点。二叉树储备结构采纳链式储备结构
13、,对于满二叉树与完全二叉树可以按层序进行次序储备4、二叉树的遍历二叉树的遍历是指不重复的拜访二叉树中的全部结点。二叉树的遍历可以分为以下三种(1) 前序遍历 DLR:如二叉树为空,就终止返回。否就:第一拜访根结点,然后遍历左子树,最终遍历右子树。并且,在遍历左右子树时,仍旧先拜访根结点,然后遍历左子树,最终遍历右子树。(2) 中序遍历 LDR:如二叉树为空,就终止返回。否就:第一遍历左子树,然后拜访根结点,最终遍历右子树。并且,在遍历左、右子树时,仍旧先遍历左子树,然后拜访根结点,最终遍历右子树。(3) 后序遍历 LRD:如二叉树为空,就终止返回。否就:第一遍历左子树,然后遍历右子树,最终拜访
14、根结点,并且,在遍历左、右子树时,仍旧先遍历左子树,然后遍历右子树,最终拜访根结点.1.7 查找技术查找:依据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素。查找胜利 /查找失败在以下两种情形下也只能采纳次序查找:假如线性表为无序表,就不管是次序储备结构仍是链式储备结构,只能用次序查找。即使是有序线性表,假如采纳链式储备结构,也只能用次序查找。查找分为 :次序查找 二分法查找二分法查找只适用于次序储备的有序表 能使用二分法查找的线性表必需满意用次序储备结构和线性表是可编辑资料 - - - 欢迎下载精品名师归纳总结有序表两个条件。 对于长度为 n 的有序线性表, 最坏情形只需比较次
15、, 而次序查找需要比较n 次。注:“有序”是特指元素按非递减排列,即从小到大排列,但答应相邻元素相等。下一节排序中,有序的含义也是如此1.8 排序技术排序是指将一个无序序列整理成按值非递减次序排列的有序序列。1、交换类排序法(冒泡排序,快速排序)2、插入类排序法(简洁插入排序,希尔排序)3、挑选类排序法(简洁挑选排序,堆排序)冒泡排序法 , 快速排序法 , 简洁插入排序法 , 简洁挑选排序法 , 最坏需要比较的次数为nn-1/2希尔排序 , 最坏需要比较的次数为堆排序 , 最坏需要比较的次数为相比以上几种(除希尔排序法外),堆排序法的时间复杂度最小。(本章应考点拨:本章内容在笔试中会显现5-6
16、 个题目,是公共基础学问部分出题量比较多的一章,所占分值也比较大,约 10 分。)第 2 章程序设计基础2.1 程序设计的方法与风格 清楚第一、效率其次 已成为当今主导的程序设计风格。形成良好的程序设计风格需留意:1、源程序文档化。2、数据说明的方法。3、语句的结构。4、输入和输出。注释分序言性注释和功能性注释。语句结构清楚第一、效率其次。2.2 结构化程序设计1、结构化程序设计方法的四条原就是:1.自顶向下。 2.逐步求精。 3. 模块化。 4. 限制使用 goto 语句。2、结构化程序的基本结构及特点:(1) 次序结构 :一种简洁的程序设计,最基本、最常用的结构。(2) 挑选结构 :又称分
17、支结构,包括简洁挑选和多分支挑选结构,可依据条件,判定应当挑选哪一条分支来执行相应的语句序列。3 循环结构 :又称重复结构,可依据给定条件,判定是否需要重复执行某一相同或类似的程序段。结构化程序设计的特点:只有一个入口和出口2.3 面对对象方法面对对象的程序设计:以60 岁月末挪威奥斯陆高校和挪威运算机中心研制的SIMULA语言为标志。面对对象方法的优点:( 1)与人类习惯的思维方法一样。(2)稳固性好。( 3)可重用性好。(4)易于开发大型软件产品。( 5)可爱护性好。* :面对对象的程序设计主要考虑的是提高软件的可重用性。对象是属性和方法的封装体。* :一个对象由对象名、属性和操作三部分组
18、成。面对对象的基本特点:继承性,多态性,封装性* :信息隐藏是通过对象的封装性来实现的。对象 是面对对象方法中最基本的概念,可以用来表示客观世界中的任何实体,对象是实体的抽象。面对对象的程序设计方法中的对象是系统中用来描述客观事物的一个实体,是构成系统的一个基本单位由一组表示其静态特点的属性和它可执行的一组操作组成。属性 即对象所包含的信息,操作描述了对象执行的功能,是对象的动态属性,操作也称为方法或服务。可编辑资料 - - - 欢迎下载精品名师归纳总结对象的基本特点:(1)标识惟一性。( 2)分类性。( 3)多态性。( 4)封装性。( 5)模块独立性好。类是指具有共同属性、共同方法的对象的集
19、合。所以类是对象的抽象,对象是对应类的一个实例。消息是一个实例与另一个实例之间传递的信息。对象间的通信靠消息传递。它恳求对象执行某一处理回答某一要求的信息,它统一了数据流和掌握流消息是一个实例与另一个实例之间传递的信息。消息的组成包括( 1)接收消息的对象的名称。(2)消息标识符,也称消息名。(3)零个或多个参数。继承是指能够直接获得已有的性质和特点,而不必重复定义他们。继承分单继承和多重继承。单继承指一个类只答应有一个父类,多重继承指一个类答应有多个父类。多态性是指同样的消息被不同的对象接受时可导致完全不同的行动的现象* :在面对对象方法中,一个对象恳求另一个对象为其服务的方式是通过发送消息
20、。(本章应考点拨:本章在考试中会显现约1 个题目,所占分值大约占2 分,是出题量较小的一章。本章内容比较少,也很单,把握住基本的概念就可以轻松应对考试了,所以在这部分丢分,比较惋惜。)第 3 章软件工程基础3.1 软件工程基本概念1. 软件定义与软件特点软件指的是运算机系统中与硬件相互依存的另一部分,包括程序、数据和相关文档的完整集合。依据应用目标的不同,软件可分应用软件、系统软件和支撑软件(或工具软件)软件的特点包括:( 1)软件是一种规律实体。(2)软件的生产与硬件不同,它没有明显的制作过程( 3)软件在运行、使用期间不存在磨损、老化问题。(4)软件的开发、运行对运算机系统具有依靠性,受运
21、算机系统的限制,这导致了软件移植的问题。(5)软件复杂性高,成本昂贵。(6)软件开发涉及诸多的社会因素。2. 软件工程软件工程源自 软件危机 。所谓软件危机是泛指在运算机软件的开发和爱护过程中所遇到的一系列严峻问题软件工程的主要思想是将工程化原就 运用到软件开发过程,它包括3 个要素: 方法、工具和过程 。方法完成软件工程项目的技术手段。工具是支持软件的开发、治理、文档生成。过程支持软件开发的各个环的掌握、治理。软件工程过程是把输入转化为输出的一组彼此相关的资源和活动。包含4 种基本活动:( 1) P软件规格说明。( 2) D软件开发。(3) C软件确认。(4)A软件演进。3.2 软件生命周期
22、1、软件生命周期:软件产品从提出、实现、使用爱护到停止使用退役的过程。2、软件生命周期分为 软件定义 、软件开发及软件运行爱护三个阶段:1)软件定义阶段:包括制定方案和需求分析。制定方案:确定总目标。可行性讨论。探讨解决方案。制定开发方案。需求分析:对待开发软件提出的需求进行分析并给出具体的定义。软件需求规格说明书2) 软件开发阶段:软件设计:分为 概要设计和具体设计两个部分。软件实现:把软件设计转换成运算机可以接受的程序代码。软件测试:在设计测试用例的基础上检验软件的各个组成部分。3) 软件运行爱护阶段:软件投入运行,并在使用中不断的爱护,进行必要的扩充和删改。* :软件生命周期中所花费最多
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机二级公共基础知识总结 计算机 二级 公共 基础知识 总结
限制150内