《全国计算机等级考试二级公共基础知识点总结3784.docx》由会员分享，可在线阅读，更多相关《全国计算机等级考试二级公共基础知识点总结3784.docx（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、秋风清，秋秋月明,落叶聚聚还散,寒鸦栖栖复惊。1、 算法是指指解决方方案的准准确而完完整的描描述2、 算法的四四个基本本特性： 可行行性 确定性性 有有穷性 拥有有足够的的情报3、 算法有两两个基本本的要素素组成： 一、数据对对象的运运算和操操作 二、算法的的控制结结构4、 计算机中中的基本本操作 算术运运算 逻辑运运算 关系运运算 数据运运算5、 算法的控控制结构构给出了了算法的的基本框框架，不不仅决定定了算法法中各操操作的执执行顺序序，而且且也直接接反应了了算法的的设计是是否符合合结构化化的原则则。一个个算法都都可以用用顺序、选择、循环33钟基本本控制结结构组成成6、 算法的复复杂度主主要
2、包括括时间复复杂度和和空间复复杂度7、 算法的时时间复杂杂度是执执行算法法所需要要的计算算工作量量。 他他不仅应应该与使使用的计计算机、程序设设计语言言及程序序编制者者无关，而而且应该该与算法法实现过过程中的的许多细细节无关关。8、 算法的空空间复杂杂度是指指执行这这个算法法所需要要的内存存空间。9、 如果一个个数据结结构中没没有一个个数据元元素，则则称该数数据结构构为空的的数据结结构。10、 根据数据据结构中中个数据据元素之之间前后后件关系系的复杂杂程度，一一般将数数据结构构分为 线性结结构 和和 非线线性结构构11、 如果一个个非空的的数据结结构满足足 1、有且只只有一个个根结点点； 22
3、、 每每一个结结点最多多有一个个前件，也也最多有有一个后后件，则则称该数数据结构构为线性性结构。线性结结构又称称线性表表。12、 在一个线线性结构构中插入入或删除除任何一一个结点点后还是是线性结结构。13、 在计算机机中存放放线性表表，一种种最简单单的方法法是顺序序存储。、14、 线性表的的顺序存存储结构构具有两两个基本本的特点点：一、线性表表中所有有元素所所占的存存储空间间是连续续的。二二、线性性表中各各数据在在存储空空间中是是按逻辑辑顺序依依次存放放的。15、 线性表的的插入运运算和删删除运算算 PP.8-916、 栈是一种种特殊的的线性表表，其插插入和删删除只能能在表的的一端进进行。17
4、、 在栈中允允许插入入与删除除的一端端称为栈栈顶，而而不允许许插入与与删除的的一端称称为栈底底，栈的的修改原原则是先先进后出出或后进进先出。18、 入栈运算算： 11、首先先将栈顶顶指针进进1，然然后将新新元素入入到栈顶顶指针指指向的位位置。19、 退栈预算算：首先先将栈顶顶元素赋赋予一个个指定的的变量，然然后将栈栈顶指针针退1。20、 队列：是是指允许许在一端端进行插插入、而而在另一一端进行行删除的的线性表表，允许许插入的的一端称称为队尾尾，允许许删除的的一端称称为排头头。队列列又称 先进先先出 或或 后进进后出的的线性表表，体现现了“先来先先服务的的原则”21、 队列的顺顺序存储储结构一一
5、般采用用循环队队列的形形式。即即 将队队列的存存储空间间的最后后一个位位置绕到到第一个个位置，形形成逻辑辑上的环环状空间间，供列列队循环环使用。22、 线性表的的顺序存存储结构构具有简简单、运运算方便便等优点点。但是是对于大大的线性性表，特特别是元元素变动动频繁的的大线性性表不宜宜采用顺顺序的存存储结构构，二是是采用链链式存储储结构23、 链式存储储结构中中，要求求每个结结点有两两部分组组成： 一 用用于存放放数据元元素值，称称为数据据域。 另一部部分用于于存放指指针，称称为指针针域。其其中指针针用于指指向该结结点的前前一个或或后一个个结点。24、 在链式存存储结构构中的存存储空间间可以不不连
6、续，各各数据结结点的存存储结构构与数据据之间的的逻辑关关系可以以不一致致，而数数据元素素之间的的逻辑关关系是由由指针域域来确定定的。链链式存储储方式既既可以用用于表示示线性结结构，也也可以表表示非线线性结构构25、 线性链表表： 线线性表的的链式存存储结构构称为线线性链表表。26、 树： 树树是一种种简单的的非线性性结构。在树结结构中，每每一个结结点只有有一个前前件，称称为父结结点，没没有前结结点的只只有1个个，称为为根结点点，简称称为树的的根。每每一个结结点可以以有多个个后件，他他们都称称为子结结点。27、 二叉树是是一种重重要的非非线性结结构。二二叉树具具有两个个特点： 非空空二叉树树只有
7、一一个根结结点。每每个结点点最多有有两颗子子树，且且分别称称为该结结点的左左子树与与右子树树。28、 在二叉树树的第KK层上，最最多有22k-11（k=1）个个结点29、 深度为MM 的二二叉树最最多有22M-1个个结点。深度为为M 的的二叉树树是指二二叉树共共有M 层。30、 在任意一一颗二叉叉树中，度度为0的的结点（即即叶子结结点）总总比度为为2的结结点多一一个。31、 具有N个个结点的的二叉树树，其深深度至少少为llog22n+1,32、 满二叉树树，除了了最后一一层外，每每一层上上的所有有结点都都有两个个子结点点的二叉叉树为满满二叉树树。即深深度为KK 的满满二叉树树，其第第K层上上有
8、2kk-1个个结点，且且深度为为M 的的满二叉叉树共有有2M-1个个结点。33、 在计算机机中，二二叉树通通常采用用链式存存储结构构。与线线性链表表类似，用用于存储储二叉树树中各元元素的存存储结点点也有两两部分组组成：数数据域和和指针域域。34、 二叉树的的遍历可可以分为为三种： 前序序遍历 中序序遍历 后序序遍历35、 前序遍历历： 首首先访问问根结点点，然后后遍历左左子树，最最后遍历历右子树树。36、 中序遍历历：首先先遍历左左子树，然然后访问问根结点点，最后后遍历右右子树。37、 后序遍历历：首先先遍历左左子树，然然后遍历历右子树树，最后后访问根根结点。38、 顺序查找找：又称称顺序搜搜
9、索，一一般指在在线性表表中查找找指定元元素。对对于大的的线性表表来说，顺顺序查找找效率很很低。但但在以下下两种情情况只能能用顺序序查找： 1、如果线线性表是是无序的的（即表表中的元元素是无无序的），则则不管是是顺序存存储结构构还是链链式存储储结构，都都只能顺顺序查找找。2、即使是是有序线线性表，如如果采用用链式存存储结构构，也只只能用顺顺序查找找。39、 二分法查查找: 二分法法查找只只能用于于顺序存存储的有有序表。对于长长度为NN 的有有序线性性表，在在最坏的的情况下下，二分分查找只只需要比比较loog2n次，而而顺序查查找则需需要比较较N 次次。40、 交换类排排序法：是指借借助数据据元素
10、之之间的相相互交换换进行排排序的一一种方法法。包括括 冒泡泡排序法法和 快快速排序序法。41、 冒泡排序序法：一一种最简简单的交交换类排排序方法法，它是是通过相相邻数据据元素的的交换逐逐步将线线性表变变成有序序。假设设线性表表的长度度为N,则在最最坏的情情况下，冒冒泡排序序需要经经过N/2遍从从前往后后的扫描描和N/2遍从从后往前前的扫描描，需要要的比较较次数为为n(nn-1)/2.但一般般情况下下要小于于这个工工作量。42、 快速排序序法：是是一种交交换类的的排序方方法，但但由于它它比冒泡泡排序法法的速度度快，因因此称为为快速排排序法。43、 插入类排排序法 包括 简单插插入类排排序法 希尔
11、排排序法 44、 简单插入入排序法法的效率率与冒泡泡排序法法相同。在最坏坏的情况况下需要要n(nn-1)/2 次比较较45、 希尔排序序的效率率与所选选取的增增量序列列有关。在最坏坏的情况况下，希希尔排序序所需要要的比较较次数为为 O(n1.5)46、 选择类排排序法 包括 简单选选择排序序法 和和 堆排排序法47、 简单排序序法在最最坏的情情况下需需要比较较N(nn-1)/2次次48、 堆排序法法在最坏坏情况下下需要比比较O(nloog2n)49、 就程序设设计方法法和技术术的发展展而言，主主要经过过了结构构化程序序设计和和面向对对象的程程序设计计两个阶阶段。50、 面向对象象设计的的主要优
12、优点是：与人类类习惯的的思维方方法一致致；稳定定性好；可重用用性好；易于开开发大型型软件产产品；可可维护性性好。51、 清晰第一一，效率率第二 的论论点已经经成为当当今主导导的程序序设计风风格。52、 结构化程程序实际际方法的的主要原原则为自自顶向下下，逐步步求精，模模块化，限限制使用用GOTTO语句句53、 结构化程程序语言言仅使用用顺序、选择、重复33钟基本本控制结结构就足足以表达达出各种种其他形形式的程程序设计计方法。54、 顺序就够够是一种种简单的的程序设设计结构构，它是是最基本本、最常常用的结结构。55、 选择结构构又称为为分支结结构，它它包括简简单选择择结构和和分支选选择结构构。5
13、6、 重复结构构又称为为循环结结构。在在程序设设计语言言中，重重复结构构对应两两类循环环语句，对对先判断断后执行行循环体体的称为为当型循循环结构构。对先先执行循循环体后后判断的的称为直直到型循循环结构构。即直直到型循循环至少少执行一一次运算算。57、 遵循结构构化程序序的设计计原则，按按结构化化程序设设计方法法设计出出的程序序具有明明显的特特点。一一、程序序结构良良好、易易读、易易理解、易维护护。二、可以提提高编程程工作的的效率，降降低软件件开发成成本。58、 对象是面面向对象象方法中中最基本本得概念念。对象象具有以以下的一一些基本本特点：1、标标识的唯唯一性。2、分分类性。3、多多态性。、4
14、、封装性性。5、模块独独立性好好。59、 类：将属属性、操操作相似似的对象象归为类类。即类类是具有有共同属属性、共共同方法法的对象象的集合合。60、 消息：一一个消息息有三部部分组成成：1、接受消消息的对对象名称称、2、消息标标识符33、零个个或多个个参数。61、 在面向对对象方法法中，实实现信息息隐蔽是是依靠对对象的封封装。62、 程序中添添加的必必要注释释：程序序的代码码要层次次分明，清清晰明了了，满足足视觉要要求。注注释一般般分为序序言性注注释和功功能性注注释。序序言性注注释通常常位于程程序的开开头部分分，他给给出了程程序的整整体说明明。功能能性注释释一般嵌嵌在源程程序体之之中，主主要描
15、述述其后的的语句或或程序。63、 从程序行行文角度度，编写写程序源源代码应应该注意意 源程程序文档档化、程程序的语语句结构构、数据据的说明明和输入入输出等等方面的的要求。64、 衡量模块块的独立立程度使使用耦合合性和内内聚性两两个度量量标准。模块的的内聚程程度越高高越独立立，耦合合程序越越低越独独立。65、 继承性是是面向对对象的方方法的一一个主要要特性。继承是是使用已已有的类类定义作作为基础础建立新新类的定定义技术术。已有有的类可可以当作作基类来来引用，新新类相应应的可当当做派生生类来引引用。这这种层次次结构系系统的一一个重要要性质是是继承性性，一个个类直接接继承其其父类的的描述或或特性，子
16、子类自动动的共享享基类中中定义的的数据和和方法。66、 通常，将将软件产产品从提提出、实实行、使使用维护护到停止止使用退退役的过过程称为为软件的的生命周周期。软软件生存存期一般般包括可可行性研研究与需需求分析析、设计计、实现现、测试试、交付付使用以以及维护护等活动动。67、 软件工程程的概念念出现源源自 软软件危机机。 而而软件危危机归结结为成本本、质量量、生产产率的问问题。68、 软件工程程是建立立并使用用完善的的工程化化原则。软件工工程主要要包括33个要素素：方法法、工具具、过程程。69、 软件工程程的核心心思想是是把软件件产品看看做是一一个工程程产品来来处理。70、 软件工程程的原则则：
17、 抽抽象、信信息隐蔽蔽、模块块化、局局部化、确定性性、一致致性、完完备性和和可验证证性。71、 结构化分分析方法法是结构构化程序序设计理理论在软软件需求求分析阶阶段的运运用。72、 结构化分分析方法法的实质质：着眼眼于数据据流、自自顶向下下、逐层层分解、建立系系统的流流程。以以数据流流图和数数据字典典为主要要工具，建建立系统统的逻辑辑模型。73、 数据流图图 从数数据传递递和加工工的角度度来刻画画数据流流从输入入到输出出的移动动变换过过程。74、 数据字典典是结构构化分析析方法的的核心。数据字字典是对对所有与与系统相相关的数数据元素素的一个个有组织织的列表表，具有有精确、严格的的定义，使使得用
18、户户和系统统分析员员对于输输入、存存储成分分和中间间的计算算结构有有共同的的理解。符号含义示例及说说明=被定义为为+与X=a+b 表表示 XX 由 a 和和 b 组成 | 或X=aa|b 表示示 X 由 aa 或 b 组组成 重复X=aa 表表示 XX 由 0 个个或多个个 a 组成m n重复X=2a55 表示示 X 中最少少出现 2 次次 a ，最多多出现 5 次次 a ， 55 、 2 为为重复次次数的上上下限（ ）可选X= （ a ） 表示 a 可可在 XX 中出出现，也也可不出出现“ ”数据元素素X= “ a” 表示 X 是是取值为为字符 a 的的数据元元素连接符X=19 表表示 XX
19、 可取取 1 到 99 中的的任意一一个值* *注释*a* 表示 a 为为说明或或注释75、 表 4-6 数数据字典典中采用用的符号号76、 判定树和和判定表表77、 软件需求求规格说说明书 是需求求分析阶阶段的最最后成果果，是软软件开发发的重要要文档之之一。78、 软件需求求规格说说明书的的作用。1、便便于用户户、开发发人员进进行理解解和交流流。2、反映出出用户问问题的结结构。可可以作为为软件开开发工具具的基础础和依据据。3、作为确确认测试试和验收收的依据据。79、 有关软件件设计的的基本内内容。从从技术观观点看，软软件设计计包括软软件结构构设计、数据设设计、接接口设计计、过程程设计。其中，结结构设计计用于定定义软件件系统各各主要部部件之间间的关系系；数据据设计用用于将分分析时创创建的模模型转化化为数据据结构的的定义。接口实实际用于于描述软软件内部部、软件件和协作作系统之之间以及及软件与与人之间间如何通通信；过过程设计计则是把把系统结结构部件件转化成成软件的的过程性性描述。80、 从工程管管理角度度来看，软软件设计计分为两两步完成成：概要要设计和和详细设设计。81、 软件设计计的基本本原理： 抽象象、模块块化、信信息隐蔽蔽、模块块独立性性。82、