计算机二级公共基础知识重点

全国计算机二级公共基础知识必背考点1. 算法的有穷性是指算法必须能执行有限个步骤之后终止.2. 算法的时间复杂度是指算法在执行过程中所需要的基本运算次数3. 队列、栈、线性表属于线性数据结构，二叉树不属于4. 数据的存储结构是指：数据的逻辑结构在计算机中的表示5. 一个逻辑数据结构可有多种存储结构，且各种存储结构影响数据处理的效率6. 线性链表是线性表的链式存储结构7. 栈是先进后出、后进先出的线性链表，具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针，是特殊的线性表，只能在一端插入或者删除元素8. 线性链表存储空间不一定连续，且各元素的存储顺序是任意的9. 在深度为7 的满二叉树中，叶子节点的个数为：6410. 能用二分法查找的是顺序存储的有序线性表11. 对长度为N 的线性表进行顺序查找，在最坏的情况下需要比较的次数为：N12. 对于长度为N 的线性表，在最坏的情况下，下列各排序法所对应的比较次数中正确的是：快速排序为N(N-1)/213. 算法的复杂度包括时间复杂度和空间复杂度14. 算法在执行过程中所需要的存储空间称为算法的空间复杂度15. 问题处理方案的正确而完整的描述称为算法16. 数据的逻辑结构在计算机存储控件中的存放方式称为数据的存储结构或者物理结构或者物理存储结构17. 按照逻辑结构分类，数据结构可以分为线性结构和非线性结构，二叉树属于非线性结构18. 数据结构分为逻辑结构和存储结构，循环队列属于存储结构19. 某二叉树中度为2 的结点有18 个，则该二叉树中共有19 个叶子结点20. 一颗二叉树第六层(根节点为第一层)的结点数最多为32 个21. 对长度为10 的线性表进行冒泡排序，最坏的情况下需要比较的次数为4522. 程序经调试改错后还应进行再调试23. 符合结构化程序设计风格的是使用顺序、选择和重复三种基本控制结构标示程序的控制结构24. 结构化程序设计的一种基本方法是逐步求精法、自顶向下、模块法25. 在面向对象的方法中，一个对象请求另一个对象为其服务的方式是通过发送消息26. 在软件工程学中，我们把一组具有相同的数据结构和相同的行为特征的对象的集合定义为类27. 面向对象的方法有对象/继承/类28. 在面向对象的方法中，类的实例称为对象9. 在面向对象的方法中，类描述的是具有相同属性与操作的一组对象30. 结构化程序设计的3 种基本逻辑机构为顺序、选择和重复(循环)31. 在面向对象的方法中，类之间共享属性和操作的机制称为继承32. 软件是程序、数据与相关文档的集合33. 在软件开发中，属于设计阶段的是：数据结构设计、给出系统模块结构、定义模块算法34. 软件工程的主要思想是强调在软件开发的过程中需要应用工程化原则35. 软件交付使用后还应进行维护36. 在结构化方法中，用数据流程图(DFD )作为描述工具的软件开发阶段是需求分析37. 软件设计的原则有抽象、模块化、信息隐蔽38. 为了是模块尽可能独立，需求模块的内聚程度要尽量高，且各模块的耦合程度要尽量弱39. 在软件设计中，属于过程设计工具的是：PDL 过程设计语言、PAD 图、N-S 图40. 软件测试的目的是尽可能多地发现程序中的错误41. 软件需求阶段的工作，可以分为四个方面：需求获取、需求分析、编写需求规格说明书和需求评审42. 在结构化方法中，软件功能分解属于总体设计阶段43. 软件工程的三要素：工具过程方法44. 若按功能划分，软件测试的方法通常分为白盒测试和黑盒测试45. 在进行模块测试时，要为每个被测试的模块另外设计两类模块：驱动模块和承接模块(桩模块)，其中驱动模块的作用是将测试数据传送给被测试的模块，并显示被测试模块的测试结果46. 程序测试分为静态分析和动态测试，其中静态分析(静态测试)是指不执行程序，而只是对程序文本进行检查，通过阅读和讨论，分析和发现程序中的错误47. 诊断和改正程序中错误的工作通常称为调试48. 软件是程序、数据和文档的集合49. 软件工程研究的内容主要是软件开发技术和软件工程管理50. 数据库系统的核心是数据库管理系统51. 数据库系统的根本目标是解决数据共享问题52. 能给出数据库物理存储与物理存取方法的是内模式53. 在数据库的两极映射中，从概念模式到内模式的映射一般由数据库管理系统实现54. 支持数据库各种操作的软件系统叫作数据库管理系统55. 数据库(DB )\数据库系统(DBS )、数据库管理系统(DBMS )之间的关系是：DBS 包含DB 和DBMS56. 在关系数据库模型中，通常可以把字段称为属性，其值称为属性值57. 用树形结构来表示实体之间联系的模型称为层次模型58. 在E-R 图中，用来表示实体的图形是矩形59. 商品与顾客两个实体之间的联系一般是多对多60. 数据库系统在其内部分为三级模式，即概念模式、内模式和外模式，其中内模式给出了数据库中物理存储结构与物理存取方法62. 数据管理技术发展过程经过人工管理、文件系统和数据库系统三个阶段，其中数据独立性最高的阶段是数据库系统62. 数据独立性分为逻辑独立性和物理独立性，当数据的存储结构改变时，其逻辑结构可以不变，因此，基于逻辑结构的应用程序不必修改，称为物理独立性63.如果一个工人可以管理多台设备，而一个设备只被一个工人管理，则实体工人与实体设备之间存在一对多的关系64. 关系模型的完整性规则是对关系的某种约束条件，包括实体完整性、参照完整性和自定义完整性65. 在关系数据库中，把数据表示成二维表，每一个二维表称为关系或关系表66. 关系数据库管理系统能实现的专门关系运算包括选择、连接和投影。

计算机二级公共基础知识要点总结1.栈按先进后出的原则组织数据，所以入栈最早的最后出栈，而队列是先进先出的线性表。

2.循环队列有队头和队尾两个指针，但是循环队列仍是线性结构的线性表。

在循环队列中只需要对头指针与队尾两个指针来共同反映队列中元素的动态变化情况。

3.当有序线性表为顺序存储时才能用二分法查找。

可以证明的是对于长度为n的有序线性表，在最坏的情况下二分法查找只需要比较log2n次，而顺序查找需要比较n次。

4.链式存储结构既可以针对线性结构也可以针对非线性结构。

链式存储结构中每个结点都由数据域与指针域两部分组成，增加了存储空间。

顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的。

5.数据流图中带箭头的线段表示的是数据流，即沿箭头方向传送数据的通道一般在旁边标注数据流名。

程序流程图中带有箭头的线段表示的是控制流。

6.在软件开发中，需求分析阶段可以使用的工具有数据流图DFD图，数据字典DD，判定树与判定表。

7.“对象”有如下一些基本特点：标识唯一性，分类型，多态性，封装性，模块独立性好。

8.数据管理发展至今已经历了三个阶段：人工管理阶段，文件系统阶段和数据库系统阶段。

其中最后一个阶段结构简单，使用方便，逻辑性强，物理性少，在各方面的表现都最好，一直占据数据库领域的主导地位。

9.自然链接是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性组，并且在结果中把重复的属性列去掉。

10.内存又称主存，是CPU能直接寻址的存储空间，由半导体器件制成。

内存的特点是存取速率快。

所以微机中访问速度最快的存储器是内存。

11.计算机能直接识别和执行的语言是机器语言，机器语言是用二进制代码表示的计算机能直接识别和执行的一种机器指令的集合。

它是计算机的设计者通过计算机的硬件结构赋予计算机的操作功能。

机器语言具有灵活，直接执行和速度快等特点。

12.1MB=1024KB=1024*1024B=220B13.Internet的四层结构分别是：网络接口层，网络层，传输层和应用层。

第一章数据结构与算法算法1、算法：是指解题方案的准确而完整的描述。

算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。

2、算法的基本特征：是一组严谨地泄义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。

特征包括：（1）可行性；（2）确定性（3）有穷性（4）拥有足够的情报。

3、算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。

4、指令系统：一个计算机系统能执行的所有指令的集合。

5、基本运算包括：算术运算、逻借运算、关系运算、数据传输。

6、算法的控制结构：顺序结构、选择结构、循环结构。

7、算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。

8、算法复杂度：算法时间复杂度和算法空间复杂度。

9、算法时间复杂度是指执行算法所需要的计算工作量。

20、算法空间复杂度是指执行这个算法所需要的内存空间。

数据结构的基本基本概念1、数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻借关系，即数据的逻辑结构：（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数拯的存储结构：（3）对各种数据结构进行的运算。

数据结构是指相互有关联的数据元素的集合。

2、数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。

数据的存储结构有顺序、链接、索引等。

3、线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。

非线性结构：不满足线性结构条件的数据结构。

线性表及其顺序存储结构1、线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。

在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。

2、非空线性表的结构特征：（1）且只有一个根结点al,它无前件：（2）有且只有一个终端结点an.它无后件：（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。

第一章数据结构与算法算法1、算法：是指解题方案的准确而完整的描述。

算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。

2、算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。

特征包括：（1）可行性；（2）确定性（3）有穷性（4）拥有足够的情报。

3、算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。

4、指令系统：一个计算机系统能执行的所有指令的集合。

5、基本运算包括：算术运算、逻辑运算、关系运算、数据传输。

6、算法的控制结构：顺序结构、选择结构、循环结构。

7、算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。

8、算法复杂度：算法时间复杂度和算法空间复杂度。

9、算法时间复杂度是指执行算法所需要的计算工作量。

10、算法空间复杂度是指执行这个算法所需要的内存空间。

数据结构的基本基本概念1、数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。

数据结构是指相互有关联的数据元素的集合。

2、数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。

数据的存储结构有顺序、链接、索引等。

3、线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。

非线性结构：不满足线性结构条件的数据结构。

线性表及其顺序存储结构1、线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。

在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。

2、非空线性表的结构特征：（1）且只有一个根结点a1，它无前件；（2）有且只有一个终端结点an，它无后件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。

全国计算机全国计算机二级公共基础知识二级公共基础知识二级公共基础知识((重点部分重点部分))第一章 数据结构基础1.1算法1.1.1 算法的基本概念算法是解题方案的准确而完整的描述算法是解题方案的准确而完整的描述，，它不等于程序它不等于程序，，也不等计算方法也不等计算方法。

算法的基本特征可行性(effectiveness) 确定性(definiteness) 有穷性(finiteness) 拥有足够的情报 算法的时间复杂度执行算法所需要的计算工作量 与下列因素有关：书写算法的程序设计语言 ,编译产生的机器语言，代码质量 机器执行指令的速度 ,问题的规模 问题的规模函数 算法的工作量=f(n)算法中基本操作重复执行的频率T(n)，是问题规模n 的某个函数f(n)，记作记作：：T(n)=O(f(n)) 记号“O ”读作“大O ”。

表示随问题规模n 的增加，算法执行时间的增长率和f(n)相应增加。

常见算法复杂度常见算法复杂度：：O(1)：常数阶 O(n)：作线性阶 O(n2)：平方阶 O(n3)：立方阶 O(logn)：对数阶 O(2n)：指数阶算法的空间复杂度算法执行过程中所需的最大存储空间 存储量包括以下三部分算法程序所占的空间 ,输入的初始数据所占的存储空间 ,算法执行过程中所要的额外空间1.2 数据结构的基本概念数据的逻辑结构对数据元素之间的逻辑关系的描述只抽象地反映数据元素之间的逻辑关系，与计算机中的存储无关 数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式 常用的存储结构：顺序, 链式, 索引一种数据结构可根据需要采用不同的存储结构。

采用不同的存储结构，其数据处理的效率是不同 线性结构如果一个非空数据结构满足下列两个条件：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件。

常见的线性结构有：线性表、栈与队列、线性链表非线性结构1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。

计算机二级公共基础知识重点全国计算机二级等级考试的笔试包括基础知识和程序设计两部分，其中基础知识占30分。

以下是由店铺整理关于计算机二级公共基础知识重点的内容，希望大家喜欢!计算机二级公共基础知识重点1、第一台计算机ENIAC淡生于1946年，是电子管计算机;第二代是晶体管计算机;第三代是中小规模集成电路;第四代是大规模集成电路;2、计算机的应用领域主要有：科学计算;信息管理;实时控制;办公、生产自动化;人工智能，网络通信;电子商务;辅助设计(CAI);辅助设计(CAD);3、计算机的信息表示形式为二进制，它采用了冯。

诺依曼的思想原理，即以0 和1两个数字形式用于展现，“逢二进一”;它的基本信息单位为位，即一个二进制位。

常用的换算单位有：1 B ===8bit; 1KB====1024B ;1MB====1024KB; 1GB===1024MB;1TB===1024GB;1个汉字===2B;4、二进制换算法则：将十进制转化为二进制时除二取佘;二进制转化为八进制时以三位为一组，三位的权重等于八进进中的一位权重，二进制转化为十六进制时以四位为一组;5、对于字符的编码，普遍采用的是ASCII码，中文含义为美国标准信息交换码;被国际标准化组织ISO采纳，作用通用信息交换标准。

6、计算机的系统的组成由软件系统和硬件系统两部分组成;7、硬件系统包括运算器，控制器，存储器，输入，输出设备，控制器和运算器合成为中央处理器即CPU ，存储器主要有内存和外内之分;内存又分为只读存储器(ROM)和随机存储器(RAM)，断电内容丢失的是RAM，外存主要有硬盘(GB)，软盘(3。

5寸，1。

44MB)，光盘(650MB左右)，移动存储器优盘(MB)，MP3(MB)等;8、软件指在硬件设备上运行的各种程序及其有关的资料。

主要有系统软件(操作系统、语言处理程序、数据库管理系统)和应用程序软件即实用程序(如WPS，OFFICE，PHOTOSHOP等)。

全国计算机等级考试二级公共基础知识总结第一章数据结构及算法1.1 算法算法：是指解题方案的准确而完整的描述。

算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的设计。

算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。

特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。

算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。

指令系统：一个计算机系统能执行的所有指令的集合。

基本运算包括：算术运算、逻辑运算、关系运算、数据传输。

算法的控制结构：顺序结构、选择结构、循环结构。

算法基本设计方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。

算法复杂度：算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。

算法空间复杂度是指执行算法所需要的内存空间。

1.2 数据结构的基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。

数据结构是指相互有关联的数据元素的集合。

数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。

数据的存储结构有顺序、链接、索引等。

线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。

非线性结构：不满足线性结构条件的数据结构。

1．3 线性表及其顺序存储结构线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。

在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。

计算机等级考试二级公共基础知识部分重点归纳.txt男人偷腥时的智商仅次于爱因斯坦。

美丽让男人停下,智慧让男人留下.任何东西都不能以健康做交换. 本文由蓝鸟知道贡献 doc文档可能在WAP端浏览体验不佳.建议您优先选择TXT，或下载源文件到本机查看. 计算机等级考试二级公共基础知识部分重点归纳计算机等级考试二级公共基础知识部分重点归纳 2010-08—02 16：31 1.算法是一种设计好的计算序列，用来解决一类问题。

1 2.算法复杂的包括：时间复杂度和空间复杂度。

时间复杂度指计算工作量，空间复杂度指内存空间的要求。

3。

数据元素的集合，记为 D，数据之间的前后关系，记为 R,B=（D,R），B 表示数据结构。

二元组表示D 中各元素间的前后关系。

4.数据的逻辑结构在计算机存储空间中的存放形式称为存储结构（物理结构）。

5.常用的存储结构：顺序存储，链接存储。

6.数据的存储结构中，不接要存放数据元素的信息，还要存放数据元素之间的前后件关系的信息。

7.线性结构（条件：非空数据结构):1 有且只有一个根节点；2 每一个节点最多有一个前件, 有最多有一个后件。

8.栈、队列、串等都是线性结构. 9.数组、广义表、树和图等数据结构都是非线性结构。

10。

根据数据结构中各数据元素之间前后件关系的复杂度分：线性结构和非线性结构。

11。

栈,特殊的线性表，按“先进后出”或“先出后进”原则组织数据。

如射击时射出子弹，顺序为后进弹匣先射出. 12.栈的一端封闭,另一端开口，仅开口端允许插入和删除元素。

允许插入与删除的一端称为栈顶，另一端称为栈底。

无元素为空栈。

13.栈的基本运算有 3 种：入栈、退栈、与读栈顶元素。

14.队列只允许在一端(队头)进行删除，另一端(队尾）进行插入。

无元素为空队列。

15 队列的修改是依照先进先出的原则进行。

16.链式存储方式可用于两种数据结构中的任一种。

17.链式中的结点由两部分组成：一部分用于存放数据元素值,称为数据域，另一部分用于存放指针，称为指针域.指针用于指向该结点的前一个或后一个结点（即前件或后件）。

计算机二级公共基础知识点（一）1.算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。

2.算法的基本要素：(1)算法中对数据的运算和操作一个算法由两种基本要素组成：一是对数据对象的运算和操作;二是算法的控制结构。

在一般的计算机系统中，基本的运算和操作有以下4类：算术运算、逻辑运算、关系运算和数据传输。

(2)算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。

描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。

一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成3.算法的时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量。

同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同。

这表明使用绝对的时间单位衡量算法的效率是不合适的。

撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法运行工作量的大小，只依赖于问题的规模(通常用整数n表示)，它是问题规模的函数。

即算法的工作量=f(n)4.算法的空间复杂度算法的空间复杂度是指执行这个算法所需要的内存空间。

一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。

其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。

如果额外空间量相对于问题规模来说是常数，则称该算法是原地工作的。

在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。

疑难解答：算法的工作量用什么来计算?算法的工作量用算法所执行的基本运算次数来计算，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f(n)，其中n是问题的规模。

（二）(1)数据集合中个数据元素之间所固有的逻辑关系，即数据的逻辑结构;(2)在对数据元素进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构;(3)对各种数据结构进行的运算。

计算机考试公共基础知识重点笔记完整版第1章数据结构与算法1。

1 算法的复杂度1。

算法的基本概念利用计算机算法为计算机解题的过程实际上是在实施某种算法.（1)算法的基本特征算法一般具有4个基本特征：可行性、确定性、有穷性、拥有足够的情报.（2）算法的基本运算和操作算法的基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。

(3)算法的3种基本控制结构算法的3种基本控制结构是：顺序结构、选择结构、循环结构。

（4)算法基本设计方法算法基本设计方法：列举法、归纳法、递推、递归、减半递推技术、回溯法。

（5)指令系统所谓指令系统指的是一个计算机系统能执行的所有指令的集合。

2。

算法复杂度算法复杂度包括时间复杂度和空间复杂度。

注意两者的区别，无混淆,见表1-1。

表1—1 算法复杂性名称描述时间复杂度执行算法所需要的计算工作量空间复杂度执行这个算法所需要的内存空间1。

2 数据结构1。

2。

1 逻辑结构和存储结构1。

数据结构的基本概念（1)数据结构指相互有关联的数据元素的集合。

(2)数据结构研究的3个方面①数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；②在对数据进行处理时，各数据元素在计算机中的存储关系,即数据的存储结构；③对各种数据结构进行的运算。

2. 逻辑结构数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。

数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D;二是D上的关系，它反映了数据元素之间的前后件关系，通常记为R。

一个数据结构可以表示成：B=（D，R）其中，B表示数据结构.为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。

例如，如果把一年四季看作一个数据结构，则可表示成：B =(D,R)D ={春季,夏季，秋季,冬季｝R =｛(春季，夏季）,(夏季，秋季），(秋季，冬季）｝3. 存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）.由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同,因此,为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后件关系），在数据的存储结构中,不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。

计算机二级公共基础知识重点讲解汇总章节名称内容简介第一章数据结构与算法本章主要介绍算法的基本概念、数据结构的定义、线性表、树等重点知识的讲解。

第二章程序设计基础本章主要介绍程序设计风格、结构化程序设计、面向对象程序设计等重点知识的讲解。

第三章软件工程基础本章主要介绍软件工程的基本概念、结构化分析方法、软件设计等重点知识的讲解。

第四章数据库设计基础本章主要介绍数据库、数据库管理系统（DBMS）、数据库系统、数据模型、关系运算、专门关系运算、数据库设计步骤等重点知识的讲解。

第一章数据机构与算法数据结构与算法◆算法的基本概念1. 算法：是对问题处理方案的正确而完整的描述，是求解问题的方法，是指令的有效序列。

2. 具有5个特性：（1）有穷性（在有穷步后完成）算法程序的运行时间是有限的（2）确定性（每一步都有确定的含义）（3）可行性（4）输入（一个算法有零个或多个输入）（5）输出（一个算法有一个或多个输出）3. 算法的复杂度包括：时间复杂度和空间复杂度。

二者没有必然的联系。

时间复杂度：执行算法所需要的计算工作量或基本运算次数。

空间复杂度：算法所需要的空间的度量。

◆数据结构的定义1. 数据结构包括数据的逻辑结构、数据的存储结构、数据的操作数据的逻辑结构：数据的外部结构，指各数据元素之间的逻辑关系，反映人们对数据含义的解释。

包括：线性结构（线性表、栈、队列）和非线性结构（树和图）数据的存储结构：数据的物理结构，指数据的逻辑结构在计算机中的表示。

一个逻辑结构可以有多种存储结构。

◆线性表：线性表中元素的个数n（n>=0）定义为线性表的长度。

顺序存储是线性表的一种最常用的存储方式。

线性表的顺序存储结构和线性表的链式存储结构分别是随机存取的存储结构和顺序存取的存储结构。

1.栈：是限定在表尾进行插入和删除操作的线性表。

具有记忆功能只能顺序存储（错）允许插入和删除的一端叫栈顶。

另一端叫栈底。

后进先出的线性表2队列：是限定在一端插入而在另一端删除，插入端叫队尾，删除端叫对头。

公用基础上一：算法的概念算法是指用系统的方法描述解决问题的策略机制。

算法的基本特征（4或5点）：有穷性、确定性（指意义确定），可行性（程序运行时，所需要的资源很容易获取）、拥有足够的情报=（有零个或多个输入、至少要有一个输出）。

算法的构成要素：（简单了解）对数据对象的运算和操作、算法的控制结构二：算法复杂度时间复杂度概念：执行算法所需要的计算工作量（基本工作量）。

工作量大称为时间复杂度高。

时间复杂度的值1、最坏情况复杂性2、期望复杂性空间复杂度概念：执行算法所需要的内存空间。

需要的内存空间越多，空间复杂度越高。

内存空间包括三部分：算法程序所占空间、输入初始数据所占空间、算法执行中所需额外空间。

时空复杂度（综合考虑时间空间两因素）最坏情况时间复杂度（冒泡排序、快速排序、简单插入、简单选择）————n(n-1)/2希尔排序O（n的1.5次方）O代表最坏情况时间复杂度的符号堆排序O(n log以2为底n的对数)顺序排序n二分查找log以二为底n的对数三、数据结构的基本概念数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储表示（即所谓数据的逻辑结构和物理结构），并对这种结构定义相应的运算，设计出相应的运算，而且确保经过这些运算后，所得到的的新结构仍然是原来的结构类型。

通常把数据的逻辑结构称为数据结构。

(线性结构非线性结构第28分钟1、栈和队列都是线性表2、线性表两种存储形式：顺序存储【随机访问】。

逻辑相邻物理相邻，链式存储【顺序访问】。

逻辑相邻物理不相邻。

循环队列属于链式存储3、第55分钟：单链表头节点的作用：方便…便于…有利于…。

数据域data 指针域next单链表的插入操作（节点后）：1. s.next=p.next 2. p.next=s单链表的插入操作（节点前）单链表的删除操作（删除第i个节点）：p.next=p.next.next循环链表、双链表双链表的插入操作：1. s.pre=p.pre 2.p.pre.next=s 3.s.next=p 4.p.pre=s 我的重点双链表的删除操作：1.p.pre.next=p.next 2.p.next.pre=p.pre我的重点)四、树与二叉树（1）开始结点为根结点，终端结点为叶子结点。

全国计算机等级考试二级公共基础知识总结第一章数据结构与算法1.1 算法1 算法的基本特征：可行性；确定性，有穷性；拥有足够的情报。

，2 确定性：算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；3 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。

5 算法时间复杂度是指执行算法所需要的计算工作量。

可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。

6 算法时间复杂度取决于问题的规模和待处理的数据的初态。

7 如果算法P调用另一个算法Q，而算法Q又调用算法P8 工程上常用的分治法是减半递推技术910如果查找的x一定在数组中，此时q=1，则A(n)=(n+1)/2。

也就是说，在这种情况下，用顺序搜索法在长度为n 的一维数组中查找值为x的元素，在平均的情况下需要检查数组中一半的元素。

如果已知需要查找的x有一半机会在数组中，此时q=1/2。

则A(n)=[(n+1)/4]+n/2=3n/4。

x不在数组中时，A(n)=n。

11下面程序段的时间复杂度是for(int i=0;i<n;i++)for(int j=1;j<=m;j++)A[i][j]=0;语句的频度指的是该语句重复执行的次数，一个算法中所有语句的频度之和构成了该算法的运行时间。

本例中语句:A[i][j]=0;的频度是n*m，所以该程序段的时间复杂度是：O(m*n)1213 一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程较慢。

141.2 数据结构的基本基本概念1数据结构研究的三个方面：；数据运算。

2逻辑结构是数据元素间关系的描述，与所用的计算机无关3数据的逻辑关系是指数据元素的关联。

4数据的不可分割的基本单位是数据项。

56 一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、7。

索引等存储结构。

而采用不同的存储结构，其数据处理的效率是不同的。

全国计算机二级公共基础知识点整理一、计算机基本操作与管理1. 计算机系统组成及基本原理2. 计算机硬件设备及其功能3. 操作系统及其常用功能4. 常见办公软件的使用与操作5. 网络基础知识及网络应用二、计算机网络与网络应用1. 网络概述及基本概念2. 网络通信协议与技术3. 互联网应用与网络安全4. 局域网和广域网的搭建与管理5. 常用网络设备的配置与管理三、多媒体技术与应用1. 图形图像处理基础2. 声音与视频处理技术3. 多媒体技术的应用与开发4. 数字媒体的存储与传输5. 常用多媒体软件的使用与操作四、数据库与数据管理1. 数据库基本概念及模型2. 数据库的设计与管理3. 数据库查询与应用4. 数据库安全与备份5. 数据库管理工具的使用与操作五、计算机程序设计基础1. 程序设计基本概念与方法2. 常见编程语言及其特点3. 程序开发环境与工具4. 程序流程控制与函数调用5. 程序调试与错误处理六、信息系统基础知识1. 信息系统的基本概念与结构2. 信息系统分析与设计方法3. 信息系统的开发与维护4. 信息系统的安全与管理5. 信息系统的应用与发展趋势七、办公自动化与信息处理1. 办公自动化系统与应用2. 电子邮件与办公信息管理3. 文档处理与信息发布4. 数据处理与统计分析5. 信息的获取与利用八、计算机硬件与操作系统1. 计算机硬件的基本组成与功能2. 计算机操作系统的基本原理3. 操作系统的安装与配置4. 硬件设备的安装与维护5. 硬件设备的故障排除与修复九、信息安全与网络管理1. 信息安全的基本概念与原理2. 网络安全技术与措施3. 网络管理与维护4. 网络故障排除与修复5. 网络性能优化与提升十、计算机应用基础知识1. 计算机应用的基本概念与特点2. 常用办公软件的功能与应用3. 图像处理软件的功能与应用4. 数据库管理软件的功能与应用5. 网络应用软件的功能与应用十一、软件开发与应用1. 软件开发的基本流程与方法2. 常见软件开发语言与工具3. 软件测试与调试技术4. 软件项目管理与开发流程5. 软件应用与维护以上是全国计算机二级公共基础知识点的整理，涵盖了计算机基本操作与管理、计算机网络与网络应用、多媒体技术与应用、数据库与数据管理、计算机程序设计基础、信息系统基础知识、办公自动化与信息处理、计算机硬件与操作系统、信息安全与网络管理、计算机应用基础知识、软件开发与应用等方面的知识点。

第一章数据结构与算法12经过对部分考生的调查以及对近年真题的总结分析，笔试部分经常考查的是算法3复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找，读者应对此部分进行4重点学习。

5详细重点学习知识点：61．算法的概念、算法时间复杂度及空间复杂度的概念72．数据结构的定义、数据逻辑结构及物理结构的定义83．栈的定义及其运算、线性链表的存储方式94．树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历105．二分查找法116．冒泡排序法121.1算法13考点1 算法的基本概念14考试链接：15考点1在笔试考试中考核的几率为30%，主要是以填空题的形式出现，分值为2分，16此考点为识记内容，读者还应该了解算法中对数据的基本运算。

17计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。

181．算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。

192．算法的基本要素：20（1）算法中对数据的运算和操作21一个算法由两种基本要素组成：一是对数据对象的运算和操作；二是算法的控制22结构。

23在一般的计算机系统中，基本的运算和操作有以下4类：算术运算、逻辑运算、24关系运算和数据传输。

25（2）算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。

26描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。

一个27算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。

28考点2 算法复杂度29考试链接：30考点2在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为70%，主31要是以选择的形式出现，分值为2分，此考点为重点识记内容，读者还应该识记算法时32间复杂度及空间复杂度的概念。

331.算法的时间复杂度34算法的时间复杂度是指执行算法所需要的计算工作量。

35同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的36计算机上运行，效率均不同。

第一章数据结构与算法1.1 算法1、算法是指解题方案的准确而完整的描述。

换句话说，算法是对特定问题求解环节的一种描述。

*算法不等于程序，也不等于计算方法。

程序的编制不也许优于算法的设计(注释1)。

2、算法的基本特性(1)可行性。

针对实际问题而设计的算法，执行后可以得到满意的结果。

(2)拟定性。

每一条指令的含义明确，无二义性。

并且在任何条件下，算法只有唯一的一条执行途径，即相同的输入只能得出相同的输出。

(3)有穷性。

算法必须在有限的时间内完毕。

有两重含义，一是算法中的操作环节为有限个，二是每个环节都能在有限时间内完毕。

(4)拥有足够的情报。

算法中各种运算总是要施加到各个运算对象上，而这些运算对象又也许具有某种初始状态，这就是算法执行的起点或依据。

因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。

当输入不够或输入错误时，算法将无法执行或执行有错。

一般说来，当算法拥有足够的情报时，此算法才是有效的;而当提供的情报不够时，算法也许无效。

*：综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。

3、算法复杂度重要涉及时间复杂度和空间复杂度。

(1)算法时间复杂度是指执行算法所需要的计算工作量，可以用执行算法的过程中所需基本运算的执行次数来度量。

(2)算法空间复杂度是指执行这个算法所需要的内存空间。

注释1：这是由于在编写程序时要受到计算机系统运营环境的限制，程序通常还要考虑很多与方法和分析无关的细节问题1.2 数据结构的基本概念1、数据结构是指互相有关联的数据元素的集合。

2、数据结构重要研究和讨论以下三个方面的问题：(1)数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。

数据的逻辑结构包含：1)表达数据元素的信息;2)表达各数据元素之间的前后件关系[wx1] 。

(2)在对数据进行解决时，各数据元素在计算机中的存储关系，即数据的存储结构。