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