2022年全国计算机等级考试二级公共基础知识点总结.docx

《2022年全国计算机等级考试二级公共基础知识点总结.docx》由会员分享，可在线阅读，更多相关《2022年全国计算机等级考试二级公共基础知识点总结.docx（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、秋风清,秋月明 ,落叶聚仍散 ,寒鸦栖复惊；1、算法是指解决方案的精确而完整的描述2、算法的四个基本特性： 可行性确定性有穷性拥有足够的情报3、算法有两个基本的要素组成：一、数据对象的运算和操作二、算法的掌握结构4、运算机中的基本操作 算术运算规律运算关系运算数据运算5、算法的掌握结构给出了算法的基本框架,不仅打算了算法中各操作的执行次序, 而且也直接反应了算法的设计是否符合结构化的原就；一个算法都可以用次序、挑选、循环 3 钟基本掌握结构组成6、算法的复杂度主要包括时间复杂度和空间复杂度7、算法的时间复杂度是执行算法所需要的运算工作量；他不仅应当与使用的运算机、程序设计语言及程序编制者无关,

2、 而且应当与算法实现过程中的很多细节无关；8、算法的空间复杂度是指执行这个算法所需要的内存空间；9、假如一个数据结构中没有一个数据元素,就称该数据结构为空的数据结构；10、 依据数据结构中个数据元素之间前后件关系的复杂程度,一般将数据结构分为线性结构 和 非线性结构11、 假如一个非空的数据结构满意1、有且只有一个根结点； 2、 每一个结点最多有一个前件,也最多有一个后件,就称该数据结构为线性结构；线性结构又称线性表；12、 在一个线性结构中插入或删除任何一个结点后仍是线性结构；13、 在运算机中存放线性表,一种最简洁的方法是次序储备； 、14、 线性表的次序储备结构具有两个基本的特点：一、线

3、性表中全部元素所占的储备空间是连续的；二、线性表中各数据在储备空间中是按规律次序依次存放的；15、 线性表的插入运算和删除运算P.8-916、 栈是一种特殊的线性表,其插入和删除只能在表的一端进行；17、 在栈中答应插入与删除的一端称为栈顶,而不答应插入与删除的一端称为栈底, 栈的修改原就是先进后出或后进先出；18、 入栈运算： 1、第一将栈顶指针进 1,然后将新元素入到栈顶指针指向的位置；19、 退栈预算：第一将栈顶元素给予一个指定的变量,然后将栈顶指针退1；20、 队列：是指答应在一端进行插入、而在另一端进行删除的线性表,答应插入的一端称为队尾, 答应删除的一端称为排头； 队列又称 先进先

4、出 或 后进后出的线性表,表达了“先来先服务的原就”21、 队列的次序储备结构一般采纳循环队列的形式；即将队列的储备空间的最终一个位置绕到第一个位置,形成规律上的环状空间,供列队循环使用；22、 线性表的次序储备结构具有简洁、运算便利等优点；但是对于大的线性表,特殊是元素变动频繁的大线性表不宜采纳次序的储备结构,二是采纳链式储备结构23、 链式储备结构中,要求每个结点有两部分组成： 一 用于存放数据元素值,称为数据域； 另一部分用于存放指针, 称为指针域； 其中指针用于指向该结点的前一个或后一个结点；24、 在链式储备结构中的储备空间可以不连续,各数据结点的储备结构与数据之间的规律关系可以不一

5、样,而数据元素之间的规律关系是由指针域来确定的；链式储备方式既可以用于表示线性结构,也可以表示非线性结构25、 线性链表： 线性表的链式储备结构称为线性链表；26、 树： 树是一种简洁的非线性结构；在树结构中,每一个结点只有一个前件,称为父结点,没有前结点的只有1 个,称为根结点,简称为树的根；每一个结点可以有多个后件,他们都称为子结点；27、 二叉树是一种重要的非线性结构；二叉树具有两个特点：非空二叉树只有一个根结点；每个结点最多有两颗子树,且分别称为该结点的左子树与右子树；28、 在二叉树的第 K 层上,最多有 2k-1（ k=1）个结点29、 深度为 M 的二叉树最多有 2M -1 个结

6、点；深度为 M 的二叉树是指二叉树共有 M层；30、 在任意一颗二叉树中,度为 0 的结点（即叶子结点）总比度为 2 的结点多一个；31、 具有 N 个结点的二叉树,其深度至少为log2n+1,32、 满二叉树,除了最终一层外,每一层上的全部结点都有两个子结点的二叉树为满二叉树；即深度为 K 的满二叉树,其第K 层上有 2k-1 个结点,且深度为 M 的满二叉树共有 2M-1 个结点；33、 在运算机中,二叉树通常采纳链式储备结构；与线性链表类似,用于储备二叉树中各元素的储备结点也有两部分组成：数据域和指针域；34、 二叉树的遍历可以分为三种：前序遍历中序遍历后序遍历35、 前序遍历： 第一拜

7、访根结点,然后遍历左子树,最终遍历右子树；36、 中序遍历：第一遍历左子树,然后拜访根结点,最终遍历右子树；37、 后序遍历：第一遍历左子树,然后遍历右子树,最终拜访根结点；38、 次序查找：又称次序搜寻,一般指在线性表中查找指定元素；对于大的线性表来说,次序查找效率很低；但在以下两种情形只能用次序查找：1、假如线性表是无序的（即表中的元素是无序的） ,就不管是次序储备结构仍是链式储备结构, 都只能次序查找； 2、即使是有序线性表,假如采纳链式储备结构,也只能用次序查找；39、 二分法查找 : 二分法查找只能用于次序储备的有序表；对于长度为N 的有序线性表,在最坏的情形下, 二分查找只需要比较

8、 log2n 次,而次序查找就需要比较N 次；40、 交换类排序法：是指借助数据元素之间的相互交换进行排序的一种方法；包括冒泡排序法和 快速排序法；41、 冒泡排序法：一种最简洁的交换类排序方法,它是通过相邻数据元素的交换逐步将线性表变成有序；假设线性表的长度为N,就在最坏的情形下,冒泡排序需要经过 N/2 遍从前往后的扫描和 N/2 遍从后往前的扫描, 需要的比较次数为 nn-1/2.但一般情形下要小于这个工作量；42、 快速排序法：是一种交换类的排序方法,但由于它比冒泡排序法的速度快,因此称为快速排序法；43、 插入类排序法 包括 简洁插入类排序法 希尔排序法44、 简洁插入排序法的效率与

9、冒泡排序法相同；在最坏的情形下需要nn-1/2 次比较45、 希尔排序的效率与所选取的增量序列有关；在最坏的情形下,希尔排序所需要的比较次数为 On1.546、 挑选类排序法 包括 简洁挑选排序法和 堆排序法47、 简洁排序法在最坏的情形下需要比较Nn-1/2 次48、 堆排序法在最坏情形下需要比较Onlog2n49、 就程序设计方法和技术的进展而言,主要经过了结构化程序设计和面对对象的程序设计两个阶段；50、 面对对象设计的主要优点是：与人类习惯的思维方法一样；稳固性好；可重用性好；易于开发大型软件产品；可保护性好；51、 清楚第一,效率其次的论点已经成为当今主导的程序设计风格；52、 结构

10、化程序实际方法的主要原就为自顶向下,逐步求精,模块化,限制使用 GOTO语句53、 结构化程序语言仅使用次序、挑选、重复3 钟基本掌握结构就足以表达出各种其他形式的程序设计方法；54、 次序就够是一种简洁的程序设计结构,它是最基本、最常用的结构；55、 挑选结构又称为分支结构,它包括简洁挑选结构和分支挑选结构；56、 重复结构又称为循环结构；在程序设计语言中,重复结构对应两类循环语句,对先判定后执行循环体的称为当型循环结构；对先执行循环体后判定的称为直到型循环结构；即直到型循环至少执行一次运算；57、 遵循结构化程序的设计原就,按结构化程序设计方法设计出的程序具有明显的特点；一、程序结构良好、

11、易读、易懂得、易保护；二、可以提高编程工作的效率, 降低软件开发成本；58、 对象是面对对象方法中最基本得概念；对象具有以下的一些基本特点：1、标识的唯独性； 2、分类性； 3、多态性；、4、封装性； 5、模块独立性好；59、 类：将属性、操作相像的对象归为类；即类是具有共同属性、共同方法的对象的集合；60、 消息：一个消息有三部分组成： 1、接受消息的对象名称、 2、消息标识符 3、零个或多个参数；61、 在面对对象方法中,实现信息隐藏是依靠对象的封装；62、 程序中添加的必要注释：程序的代码要层次分明,清楚明白,满意视觉要求；注释一般分为序言性注释和功能性注释；序言性注释通常位于程序的开头

12、部分,他给出了程序的整体说明；功能性注释一般嵌在源程序体之中,主要描述其后的语句或程序；63、 从程序行文角度,编写程序源代码应当留意源程序文档化、程序的语句结构、数据的说明和输入输出等方面的要求；64、 衡量模块的独立程度使用耦合性和内聚性两个度量标准；模块的内聚程度越高越独立,耦合程序越低越独立；65、 继承性是面对对象的方法的一个主要特性；继承是使用已有的类定义作为基础建立新类的定义技术；已有的类可以当作基类来引用,新类相应的可当做派生类来引用；这种层次结构系统的一个重要性质是继承性,一个类直接继承其父类的描述或特性,子类自动的共享基类中定义的数据和方法；66、 通常,将软件产品从提出、

13、实行、使用保护到停止使用退役的过程称为软件的生命周期；软件生存期一般包括可行性讨论与需求分析、设计、实现、测试、交付使用以及保护等活动；67、 软件工程的概念显现源自软件危机； 而软件危机归结为成本、质量、生产率的问题；68、 软件工程是建立并使用完善的工程化原就；软件工程主要包括3 个要素：方法、工具、过程；69、 软件工程的核心思想是把软件产品看做是一个工程产品来处理；70、 软件工程的原就： 抽象、信息隐藏、模块化、局部化、确定性、一样性、完备性和可验证性；71、 结构化分析方法是结构化程序设计理论在软件需求分析阶段的运用；72、 结构化分析方法的实质：着眼于数据流、自顶向下、逐层分解、

14、建立系统的流程；以数据流图和数据字典为主要工具,建立系统的规律模型；73、 数据流图 从数据传递和加工的角度来刻画数据流从输入到输出的移动变换过程；符号含义示例及说明 | 或X=a|b表示 X 由 a或 b组成 重复X=a表示 X 由 0个或多个 a组成74、 数据字典是结构化分析方法的核心；数据字典是对全部与系统相关的数据元素的一个有组织的列表,具有精确、严格的定义,使得用户和系统分析员对于输入、储备成分和中间的运算结构有共同的懂得；=被定义为+与X=a+b 表示 X由 a和 b组成X=2a5表示 X 中最少显现 2次 a,最多m n重复显现 5次 a, 5、 2为重复次数的上下限X= （

15、a） 表示 a可在 X 中显现, 也可不（ ）可选显现X= “ a ” 表示 X 是取值为字符 a的数据“ ”数据元素元素X=19 表示 X 可取 1到 9中的任意一个连接符值* *注释*a*表示 a为说明或注释75、 表 4-6数据字典中采纳的符号76、 判定树和判定表77、 软件需求规格说明书是需求分析阶段的最终成果,是软件开发的重要文档之一；78、 软件需求规格说明书的作用； 1、便于用户、开发人员进行懂得和沟通；2、反映出用户问题的结构； 可以作为软件开发工具的基础和依据； 3、作为确认测试和验收的依据；79、 有关软件设计的基本内容；从技术观点看,软件设计包括软件结构设计、数据设计、接口设计、过程设计；其中,结构设计用于定义软件系统各主要部件之间的关系；数据设计用于将分析时创建的模型转化为数据结构的定义；接口实际用于描述软件内部、软件和协作系统之间以及软件与人之间如何通信；过程设计就是把系统结构部件转化成软件的过程性描述；80、 从工程治理角度来看,软件设计分为两步完成：概要设计和具体设计；81、 软件设计的基本原理： 抽象、模块化、信息隐藏、模块独立性；82、