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

《Dlypeq全国计算机等级考试二级公共基础知识点总结5393.docx》由会员分享，可在线阅读，更多相关《Dlypeq全国计算机等级考试二级公共基础知识点总结5393.docx（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、秋风清，秋月明,落叶聚还散,寒鸦栖复惊。1、 算法是指解解决方案案的准确确而完整整的描述述2、 算法的四个个基本特特性： 可行性性 确确定性 有穷穷性 拥有足足够的情情报3、 算法有两个个基本的的要素组组成： 一、数数据对象象的运算算和操作作 二、算算法的控控制结构构4、 计算机中的的基本操操作 算算术运算算 逻逻辑运算算 关关系运算算 数数据运算算5、 算法的控制制结构给给出了算算法的基基本框架架，不仅仅决定了了算法中中各操作作的执行行顺序，而而且也直直接反应应了算法法的设计计是否符符合结构构化的原原则。一一个算法法都可以以用顺序序、选择择、循环环3钟基基本控制制结构组组成6、 算法的复杂杂

2、度主要要包括时时间复杂杂度和空空间复杂杂度7、 算法的时间间复杂度度是执行行算法所所需要的的计算工工作量。 他不仅仅应该与与使用的的计算机机、程序序设计语语言及程程序编制制者无关关，而且且应该与与算法实实现过程程中的许许多细节节无关。8、 算法的空间间复杂度度是指执执行这个个算法所所需要的的内存空空间。9、 如果一个数数据结构构中没有有一个数数据元素素，则称称该数据据结构为为空的数数据结构构。10、 根据数据结结构中个个数据元元素之间间前后件件关系的的复杂程程度，一一般将数数据结构构分为 线性结结构 和和 非线线性结构构11、 如果一个非非空的数数据结构构满足 1、有有且只有有一个根根结点；

3、2、 每一个个结点最最多有一一个前件件，也最最多有一一个后件件，则称称该数据据结构为为线性结结构。线线性结构构又称线线性表。12、 在一个线性性结构中中插入或或删除任任何一个个结点后后还是线线性结构构。13、 在计算机中中存放线线性表，一一种最简简单的方方法是顺顺序存储储。、14、 线性表的顺顺序存储储结构具具有两个个基本的的特点：一、线线性表中中所有元元素所占占的存储储空间是是连续的的。二、线线性表中中各数据据在存储储空间中中是按逻逻辑顺序序依次存存放的。15、 线性表的插插入运算算和删除除运算 P.8-9916、 栈是一种特特殊的线线性表，其其插入和和删除只只能在表表的一端端进行。17、

4、在栈中允许许插入与与删除的的一端称称为栈顶顶，而不不允许插插入与删删除的一一端称为为栈底，栈栈的修改改原则是是先进后后出或后后进先出出。18、 入栈运算： 1、首首先将栈栈顶指针针进1，然然后将新新元素入入到栈顶顶指针指指向的位位置。19、 退栈预算：首先将将栈顶元元素赋予予一个指指定的变变量，然然后将栈栈顶指针针退1。20、 队列：是指指允许在在一端进进行插入入、而在在另一端端进行删删除的线线性表，允允许插入入的一端端称为队队尾，允允许删除除的一端端称为排排头。队队列又称称 先进进先出 或 后后进后出出的线性性表，体体现了“先来先先服务的的原则”21、 队列的顺序序存储结结构一般般采用循循环

5、队列列的形式式。即 将队列列的存储储空间的的最后一一个位置置绕到第第一个位位置，形形成逻辑辑上的环环状空间间，供列列队循环环使用。22、 线性表的顺顺序存储储结构具具有简单单、运算算方便等等优点。但但是对于于大的线线性表，特特别是元元素变动动频繁的的大线性性表不宜宜采用顺顺序的存存储结构构，二是是采用链链式存储储结构23、 链式存储结结构中，要要求每个个结点有有两部分分组成： 一 用于存存放数据据元素值值，称为为数据域域。 另另一部分分用于存存放指针针，称为为指针域域。其中中指针用用于指向向该结点点的前一一个或后后一个结结点。24、 在链式存储储结构中中的存储储空间可可以不连连续，各各数据结结

6、点的存存储结构构与数据据之间的的逻辑关关系可以以不一致致，而数数据元素素之间的的逻辑关关系是由由指针域域来确定定的。链链式存储储方式既既可以用用于表示示线性结结构，也也可以表表示非线线性结构构25、 线性链表： 线性性表的链链式存储储结构称称为线性性链表。26、 树： 树是是一种简简单的非非线性结结构。在在树结构构中，每每一个结结点只有有一个前前件，称称为父结结点，没没有前结结点的只只有1个个，称为为根结点点，简称称为树的的根。每每一个结结点可以以有多个个后件，他他们都称称为子结结点。27、 二叉树是一一种重要要的非线线性结构构。二叉叉树具有有两个特特点： 非空二二叉树只只有一个个根结点点。每

7、个个结点最最多有两两颗子树树，且分分别称为为该结点点的左子子树与右右子树。28、 在二叉树的的第K层层上，最最多有22k-11（k=1）个个结点29、 深度为M 的二叉叉树最多多有2M-1个个结点。深深度为MM 的二二叉树是是指二叉叉树共有有M 层层。30、 在任意一颗颗二叉树树中，度度为0的的结点（即即叶子结结点）总总比度为为2的结结点多一一个。31、 具有N个结结点的二二叉树，其其深度至至少为logg2n+1,32、 满二叉树，除除了最后后一层外外，每一一层上的的所有结结点都有有两个子子结点的的二叉树树为满二二叉树。即即深度为为K 的的满二叉叉树，其其第K层层上有22k-11个结点点，且深

8、深度为MM 的满满二叉树树共有22M-1个个结点。33、 在计算机中中，二叉叉树通常常采用链链式存储储结构。与与线性链链表类似似，用于于存储二二叉树中中各元素素的存储储结点也也有两部部分组成成：数据据域和指指针域。34、 二叉树的遍遍历可以以分为三三种： 前序遍遍历 中序遍遍历 后序遍遍历35、 前序遍历： 首先先访问根根结点，然然后遍历历左子树树，最后后遍历右右子树。36、 中序遍历：首先遍遍历左子子树，然然后访问问根结点点，最后后遍历右右子树。37、 后序遍历：首先遍遍历左子子树，然然后遍历历右子树树，最后后访问根根结点。38、 顺序查找：又称顺顺序搜索索，一般般指在线线性表中中查找指指定

9、元素素。对于于大的线线性表来来说，顺顺序查找找效率很很低。但但在以下下两种情情况只能能用顺序序查找： 1、如如果线性性表是无无序的（即即表中的的元素是是无序的的），则则不管是是顺序存存储结构构还是链链式存储储结构，都都只能顺顺序查找找。2、即即使是有有序线性性表，如如果采用用链式存存储结构构，也只只能用顺顺序查找找。39、 二分法查找找: 二二分法查查找只能能用于顺顺序存储储的有序序表。对对于长度度为N 的有序序线性表表，在最最坏的情情况下，二二分查找找只需要要比较llog22n次，而而顺序查查找则需需要比较较N 次次。40、 交换类排序序法：是是指借助助数据元元素之间间的相互互交换进进行排序

10、序的一种种方法。包包括 冒冒泡排序序法和 快速排排序法。41、 冒泡排序法法：一种种最简单单的交换换类排序序方法，它它是通过过相邻数数据元素素的交换换逐步将将线性表表变成有有序。假假设线性性表的长长度为NN,则在在最坏的的情况下下，冒泡泡排序需需要经过过N/22遍从前前往后的的扫描和和N/22遍从后后往前的的扫描，需需要的比比较次数数为n(n-11)/22.但一一般情况况下要小小于这个个工作量量。42、 快速排序法法：是一一种交换换类的排排序方法法，但由由于它比比冒泡排排序法的的速度快快，因此此称为快快速排序序法。43、 插入类排序序法 包包括 简简单插入入类排序序法 希希尔排序序法 44、

11、简单插入排排序法的的效率与与冒泡排排序法相相同。在在最坏的的情况下下需要nn(n-1)/2 次次比较45、 希尔排序的的效率与与所选取取的增量量序列有有关。在在最坏的的情况下下，希尔尔排序所所需要的的比较次次数为 O(nn1.55)46、 选择类排序序法 包包括 简简单选择择排序法法 和 堆排序序法47、 简单排序法法在最坏坏的情况况下需要要比较NN(n-1)/2次48、 堆排序法在在最坏情情况下需需要比较较O(nnlogg2n)49、 就程序设计计方法和和技术的的发展而而言，主主要经过过了结构构化程序序设计和和面向对对象的程程序设计计两个阶阶段。50、 面向对象设设计的主主要优点点是：与与人

12、类习习惯的思思维方法法一致；稳定性性好；可可重用性性好；易易于开发发大型软软件产品品；可维维护性好好。51、 清晰第一，效效率第二二 的的论点已已经成为为当今主主导的程程序设计计风格。52、 结构化程序序实际方方法的主主要原则则为自顶顶向下，逐逐步求精精，模块块化，限限制使用用GOTTO语句句53、 结构化程序序语言仅仅使用顺顺序、选选择、重重复3钟钟基本控控制结构构就足以以表达出出各种其其他形式式的程序序设计方方法。54、 顺序就够是是一种简简单的程程序设计计结构，它它是最基基本、最最常用的的结构。55、 选择结构又又称为分分支结构构，它包包括简单单选择结结构和分分支选择择结构。56、 重复

13、结构又又称为循循环结构构。在程程序设计计语言中中，重复复结构对对应两类类循环语语句，对对先判断断后执行行循环体体的称为为当型循循环结构构。对先先执行循循环体后后判断的的称为直直到型循循环结构构。即直直到型循循环至少少执行一一次运算算。57、 遵循结构化化程序的的设计原原则，按按结构化化程序设设计方法法设计出出的程序序具有明明显的特特点。一一、程序序结构良良好、易易读、易易理解、易易维护。二二、可以以提高编编程工作作的效率率，降低低软件开开发成本本。58、 对象是面向向对象方方法中最最基本得得概念。对对象具有有以下的的一些基基本特点点：1、标标识的唯唯一性。22、分类类性。33、多态态性。、44

14、、封装装性。55、模块块独立性性好。59、 类：将属性性、操作作相似的的对象归归为类。即即类是具具有共同同属性、共共同方法法的对象象的集合合。60、 消息：一个个消息有有三部分分组成：1、接接受消息息的对象象名称、22、消息息标识符符3、零零个或多多个参数数。61、 在面向对象象方法中中，实现现信息隐隐蔽是依依靠对象象的封装装。62、 程序中添加加的必要要注释：程序的的代码要要层次分分明，清清晰明了了，满足足视觉要要求。注注释一般般分为序序言性注注释和功功能性注注释。序序言性注注释通常常位于程程序的开开头部分分，他给给出了程程序的整整体说明明。功能能性注释释一般嵌嵌在源程程序体之之中，主主要描

15、述述其后的的语句或或程序。63、 从程序行文文角度，编编写程序序源代码码应该注注意 源源程序文文档化、程程序的语语句结构构、数据据的说明明和输入入输出等等方面的的要求。64、 衡量模块的的独立程程度使用用耦合性性和内聚聚性两个个度量标标准。模模块的内内聚程度度越高越越独立，耦耦合程序序越低越越独立。65、 继承性是面面向对象象的方法法的一个个主要特特性。继继承是使使用已有有的类定定义作为为基础建建立新类类的定义义技术。已已有的类类可以当当作基类类来引用用，新类类相应的的可当做做派生类类来引用用。这种种层次结结构系统统的一个个重要性性质是继继承性，一一个类直直接继承承其父类类的描述述或特性性，子

16、类类自动的的共享基基类中定定义的数数据和方方法。66、 通常，将软软件产品品从提出出、实行行、使用用维护到到停止使使用退役役的过程程称为软软件的生生命周期期。软件件生存期期一般包包括可行行性研究究与需求求分析、设设计、实实现、测测试、交交付使用用以及维维护等活活动。67、 软件工程的的概念出出现源自自 软件件危机。 而软件件危机归归结为成成本、质质量、生生产率的的问题。68、 软件工程是是建立并并使用完完善的工工程化原原则。软软件工程程主要包包括3个个要素：方法、工工具、过过程。69、 软件工程的的核心思思想是把把软件产产品看做做是一个个工程产产品来处处理。70、 软件工程的的原则： 抽象象、

17、信息息隐蔽、模模块化、局局部化、确确定性、一一致性、完完备性和和可验证证性。71、 结构化分析析方法是是结构化化程序设设计理论论在软件件需求分分析阶段段的运用用。72、 结构化分析析方法的的实质：着眼于于数据流流、自顶顶向下、逐逐层分解解、建立立系统的的流程。以以数据流流图和数数据字典典为主要要工具，建建立系统统的逻辑辑模型。73、 数据流图 从数据据传递和和加工的的角度来来刻画数数据流从从输入到到输出的的移动变变换过程程。74、 数据字典是是结构化化分析方方法的核核心。数数据字典典是对所所有与系系统相关关的数据据元素的的一个有有组织的的列表，具具有精确确、严格格的定义义，使得得用户和和系统分

18、分析员对对于输入入、存储储成分和和中间的的计算结结构有共共同的理理解。符号含义示例及说明明=被定义为+与X=a+bb 表示示 X 由 aa 和 b 组组成 | 或X=a|b 表示 X 由由 a 或 bb 组成成 重复X=a 表示示 X 由 00 个或或多个 a 组组成m nn重复X=2aa5 表示 X 中中最少出出现 22 次 a ，最最多出现现 5 次 aa ， 5 、 2 为为重复次次数的上上下限（ ）可选X= （ a ） 表示 a 可可在 XX 中出出现，也也可不出出现“ ”数据元素X= “ a” 表示 X 是是取值为为字符 a 的的数据元元素连接符X=199 表示示 X 可取 1 到到

19、 9 中的任任意一个个值* *注释*a* 表表示 aa 为说说明或注注释75、 表 4-66 数据据字典中中采用的的符号76、 判定树和判判定表77、 软件需求规规格说明明书 是是需求分分析阶段段的最后后成果，是是软件开开发的重重要文档档之一。78、 软件需求规规格说明明书的作作用。11、便于于用户、开开发人员员进行理理解和交交流。22、反映映出用户户问题的的结构。可可以作为为软件开开发工具具的基础础和依据据。3、作作为确认认测试和和验收的的依据。79、 有关软件设设计的基基本内容容。从技技术观点点看，软软件设计计包括软软件结构构设计、数数据设计计、接口口设计、过过程设计计。其中中，结构构设计用用于定义义软件系系统各主主要部件件之间的的关系；数据设设计用于于将分析析时创建建的模型型转化为为数据结结构的定定义。接接口实际际用于描描述软件件内部、软软件和协协作系统统之间以以及软件件与人之之间如何何通信；过程设设计则是是把系统统结构部部件转化化成软件件的过程程性描述述。80、 从工程管理理角度来来看，软软件设计计分为两两步完成成：概要要设计和和详细设设计。81、 软件设计的的基本原原理： 抽象、模模块化、信信息隐蔽蔽、模块块独立性性。82、