计算机二级公共基础电子书pdf
计算机二级公共基础电子书.pdf 可适用于职业技术培训领域，主题内容包含第1章数据结构与算法经过对部分考生的调查以及对近年真题的总结分析，小编给大家准备了计算机二级公共基础电子书pdf，有需要的就快来下载吧
内容介绍计算机二级公共基础电子书.pdf 文档类型 pdf / 本文档为《计算机二级公共基础电子书.pdf.pdf》，可适用于职业技术培训领域，主题内容包含第1章数据结构与算法经过对部分考生的调查以及对近年真题的总结分析，
笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找，读者应对此部分进行重点学习
详细重点学习知识点：1．算法的概念、算法时间复杂度及空间复杂度的概念2．数据结构的定义、数据逻辑结构及物理结构的定义3．栈的定义及其运算、线性链表的存储方式4．树与二叉树的概念、二叉树的基本性质、完全二叉树的概念、二叉树的遍历5．二分查找法6．冒泡排序法1.1算法考点1算法的基本概念计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。1．算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。2．算法的基本要素：（1）算法中对数据的运算和操作一个算法由两种基本要素组成：一是对数据对象的运算和操作；二是算法的控制结构。在一般的计算机系统中，基本的运算和操作有以下4类：算术运算、逻辑运算、关系运算和数据传输。（2）算法的控制结构：算法中各操作之间的执行顺序称为算法的控制结构。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。考点2等等。
全国计算机等级考试二级公共基础知识考试大纲基本要求
1．掌握计算机系统的基本概念，理解计算机硬件系统和计算机操作系统。
2．掌握算法的基本概念。
3．掌握基本数据结构及其操作。
4．掌握基本排序和查找算法。
5．掌握逐步求精的结构化程序设计方法。
6．掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。
7．掌握数据库的基本知识，了解关系数据库的设计。
考试内容一、计算机系统
１．掌握计算机系统的结构。
２．掌握计算机硬件系统结构，包括ＣＰＵ的功能和组成，存储器分层体系，总线和外部设备。
３．掌握操作系统的基本组成，包括进程管理、内存管理、目录和文件系统、Ｉ／Ｏ设备管理。
二、基本数据结构与算法
１．算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。２．数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。
３．线性表的定义；线性表的顺序存储结构及其插入与删除运算。
４．栈和队列的定义；栈和队列的顺序存储结构及其基本运算。
５．线性单链表、双向链表与循环链表的结构及其基本运算。
６．树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。
７．顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。
三、程序设计基础
１． 程序设计方法与风格。
２．结构化程序设计。
３．面向对象的程序设计方法，对象，方法，属性及继承与多态性。
四、软件工程基础
１．软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。
２．结构化分析方法，数据流图，数据字典，软件需求规格说明书。
３．结构化设计方法，总体设计与详细设计。
４．软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。
５．程序的调试，静态调试与动态调试。
五、数据库设计基础
１．数据库的基本概念：数据库，数据库管理系统，数据库系统。
２．数据模型，实体联系模型及Ｅ－Ｒ图，从Ｅ－Ｒ图导出关系数据模型。
３．关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。
４．数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。
考试方式
１．公共基础知识不单独考试，与其他二级科目组合在一起，作为二级科目考核内容的一部分。
２．上机考试，１０ 道单项选择题，占１０ 分。
计算机二级公共基础知识笔记一、数据结构与算法
算法的基本运算和操作：算术运算，逻辑运算，关系运算，数据传输。
算法基本设计方法：列举法、归纳法、递推、递归、减半递推技术。
数据元素：数据元素是数据的基本单位。
数据对象：数据对象是性质相同的数据元素的集合。
数据结构：是指由某一数据对象中所有数据成员之间的关系组成的集合。
数据的逻辑结构包括数据对象和数据对象之间的关系。
数据的存储结构包括数据元素的存储方式和关系的存储方式。
一种数据的逻辑结构可以表示成多种存储结构。
线性结构的条件（一个非空数据结构)：
（1）有且只有一个根结点；
（2）每一个结点最多有一个前件，也最多有一个后件。
栈、队列、双向链表是线性结构；树、二叉树为非线性结构。
线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。具有“一对一”逻辑关系的数据，最佳的存储方式是使用线性表。除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
线性表的存储结构：顺序存储结构（顺序表，图3a)）和链式存储结构（链表，图3b)）。
线性表的顺序存储结构有两个特点：
（1）线性表中所有元素所占的存储空间连续；
（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
线性表的链式存储结构存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。结点包含：数据域、指针域。（注：链式存储方式既可用于表示线性结构，也可用于表示非线性结构）。
栈和队列隶属于线性表，是特殊的线性表，因为它们对线性表中元素的进出做了明确的要求。
栈具有记忆功能，队列没有记忆功能。栈的特点是先进后出,后进先出,所以对一个栈进行出栈操作,出来的元素肯定是最后存入栈中的元素,所以栈有记忆功能。而队列是先进先出,取队列的第一个元素,得到的是最先存入队列的元素,而不是上一个存入队列的元素,所以没有记忆功能。
栈、队列的存储结构：
（1）顺序存储结构：用一组地址连续的存储单元即一维数组来存储；
（2）链式存储：线性链表。
计算循环队列的元素个数：“尾指针减头指针”，若为负数，再加其容量即可。
树是 
个结点的有限集合，是一种非线性结构。
结点的度：结点所拥有的子树的个数。
叶子结点：度为0的结点。
分支结点：除叶子结点以外的结点。
结点的层次：根结点在第一层。
树的深度：所处层次最大的那个结点的层次。
树的度：树中所有结点的度的最大值。
二叉树每个结点最多只有两棵子树，且有左右之分，不能互换，二叉树有五种不同的形态。
在二叉树的第 
层上，最多有 
个结点。
深度为 
的二叉树最多有 
个结点。
在任意一棵二叉树中，度为 
的结点（叶子结点）总是比度为 
的结点多一个。
具有 
个结点的二叉树，其深度不小于 
，其中 
表示为 
的整数部分。
满二叉树：每一层上的结点数都达到最大值，即在满二叉树的第 层上有 
个结点。
完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。
具有 个结点的完全二叉树的深度为 。
完全二叉树中度为 
的结点数为 或 。
前序遍历：先访问根结点、然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
中序遍历：先遍历左子树、然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。
后序遍历：先遍历左子树、然后遍历右子树，最后访问根结点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。
顺序查找是从表的一端开始，依次扫描表中的各个元素，并与所要查找的数进行比较。
只能采用顺序查找：
（1）线性表为无序表，则不管是顺序存储结构还是链式存储结构，只能用顺序查找。（2）有序线性表，如果采用链式存储结构，也只能用顺序查找。
二分查找的条件：
（1）用顺序存储结构，
（2）线性表是有序表。
对于长度为 的有序线性表，在最坏情况下，二分法查找只需比较 
次，而顺序查找需要比较 次。
排序算法
1、交换类排序
（1）冒泡排序法，在最坏的情况下，冒泡排序需要比较次数为 
。
（2）快速排序法 ，在最坏的情况下，快速排序需要比较次数为 。
2、插入类排序：
（1）简单插入排序法，最坏情况需要 次比较；
（2）希尔排序法，最坏情况需要 
次比较。
3、选择类排序：
（1）简单选择排序法，最坏情况需要 次比较；
（2）堆排序法，最坏情况需要 
次比较。 相比以上几种(除希尔排序法外)，堆排序法的时间复杂度最小。
发表于 2021-8-24 19:16:58
[/url]
[/url]
[/url]