二级公共基础知识重点讲义资料

第一章数据结构与算法笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找，读者应对此部分进行重点学习。

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

考点2 算法复杂度考试链接：考点2在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为70%，主要是以选择的形式出现，分值为2分，此考点为重点识记内容,读者还应该识记算法时间复杂度及空间复杂度的概念.疑难解答:算法的工作量用什么来计算？算法的工作量用算法所执行的基本运算次数来计算,而算法所执行的基本运算次数是问题规模的函数,即算法的工作量=f（n），其中n是问题的规模。

考点3 数据结构的定义考试链接：考点3在笔试考试中，是一个经常考查的内容，在笔试考试中出现的几率为70%,主要是以选择的形式出现,分值为2分，此考点为识记内容,读者还应该识记数据的逻辑结构和存储结构的概念.考点4 线性结构与非线性结构考试链接：考点4在笔试考试中,虽然说不是考试经常考查的内容,但读者还是对此考点有所了解,在笔试考试中出现的几率为，主要是以填空题出现的形式出现，分值为2分，此考点为识记内容。

疑难解答:空的数据结构是线性结构还是非线性结构?一个空的数据结构究竟是属于线性结构还是属于非线性结构，这要根据具体情况来确定。

如果对该数据结构的算法是按线性结构的规则来处理的，则属于线性结构;否则属于非线性结构。

考点5 栈及其基本运算考试链接：考点5在笔试考试中，是一个必考的内容，在笔试考试中出现的几率为100％，主要是以选择的形式出现,分值为2分，此考点为重点掌握内容，读者应该掌握栈的运算.:栈是按照"先进后出"或”后进先出”的原则组织数据,但是出栈方式有多种选择，在考题中经常考查各种不同的出栈方式。

全国计算机等级考试二级基础知识第一章：数据结构与算法1.] 算法「一、算法的概念：解决问题准确而完整的描述。

•特征^可行性.确定性、有穷性、拥有足够的情报。

•要素：对数据运算操作（算术.逻辑）通过指令序列程序来实现、算法的控制结构（执行顺序）。

•算法设计方法：•列举法：列举所有可能•归纳法：从特殊到一般•递推：从条件到结论•递归：函数的自调用•减半递推：中间分冶•回溯：反证•二、算法复杂度•1 .时间复杂度（工作量）•平均性态（平均值）•最坏情况（最大值）•2 .空间复杂度（资源）•内存资源1.2数据结构的基本概念•研究数据结构——逻辑结构.物理结构、运算的实现•1 .数据结构•数据逻辑结构：数据元素及元素间的关系，B=（DR）•存储结构：内存中的存放形式•线性与非线性结构•有且仅有一个根结点；一个前件，一个后件•只有一个根结点不是线性结构1.3线性表及其顺序存储结构•线性表：连续顺序存储，逻辑结构与存储结构一致。

•插入运算：插入点起所有元素后移•删除运算：删除点后所冇元素前移1.4栈和队列•1、栈：只有一个出入口仅有一个元素宽度的巷道, 先进后出入栈.退栈、读栈顶元素。

•2 .队列•一个出口一个入口仅有一个元素宽度的巷道，先进先岀丁队列移动，循环标志s 0空•入队；上溢、退队；下溢1.5线性链表•线柱表的缺点：插入删除上的复杂性、空间的连续性（预留、不够）•结点：元秦+指针•Head…al *a2…a2 *a3...an null•双链表•栈与队列的链表实现•链表的插入删除•改变前后元素的指针指向，可以不改变位置•循环链表：增加一个表头结点数据不定，最后一指针指向表头1.6树与二叉树•1 .树层次结构•根结点、叶子结点.子结点、深度（层数人节点的度（分叉数）•了解表达式的树表示•2、二叉树•分叉数少于等于2 （左右子树）•一个根节点是二叉树•性质•A. k层节点少于2A（k-l）•B. m深度的树节点总数为•C、度为2的比度为0节点多一个•d.节点为n,则深度为int（log2 N）+l•3、满二叉树与完全二叉树•满二叉树不缺枝•完全二叉树：仅缺右子树•注意完全二叉树节点编号间关系•4、二叉树的存储•采用双链表•5、二叉树的遍历•遍历：不重复访问所有结点•前序：根.左、右•中序：左、根、右•后序：左、右、根•注意从上到下均按上述顺序•例1.33b左•前：abdhiejkcflg•中:hdibjekalfcg•后:hidjkeblfgca1.7查找技术•1、顺序查找•无序表、链表2 .二分法查找•有序表，最多log2N次1.8排序技术•1、交换类排序•A、昌泡法排序•前后顺序交换改变逆序n（n-l）/2•B、快速排序法•取一个中点两边与中点比较交换•2、插入类排序•A、简单插入排序•从第一个开始小的插在前n（n-1 ）/2•B、希尔排序法•分成若于子序列排序后减少子序列个数。

/*声明:此小笔记对于没有看过公共基础的同学或许有点帮助,只要记住就行,没必要弄懂为什么,篇幅很少,只为考前突击*/目录-------------数据结构与算法部分------------- (2)-------------程序设计基础部分------------- (2)-------------软件工程基础部分------------- (2)-------------数据结构与算法------------- (3)-------------数据结构与算法部分-------------1.算法特点:1可行性2确定性3有穷性4有足够情报2.算法的复杂度：1时间复杂度2空间复杂度3.算法的时间复杂度：执行算法的计算工作量，可以用基本元算的执行次数来度量4.算法的空间复杂度: 算法执行过程中所需要的存储空间5.栈先进后出6.队列先进先出7.二叉树不是线性表8.二叉树的遍历：1前序遍历2中序遍历3后序遍历（请自己查阅详细资料）9.具有n个节点的二叉树，深度至少为[log2n]+110.具有n个节点的完全二叉树，深度为[log2n]+1-------------程序设计基础部分-------------12.结构化程序设计方法:1自顶而下2逐步求精3模块化4限制goto语句使用13.对象的特点:1标识唯一性2分类性3多态性4封装性5模块独立性14.模块要高内聚低耦合好-------------软件工程基础部分-------------15.软件=程序+数据+文档16.软件危机原因:1对软件开发和维护认识错误2软件本身复杂又庞大17.软件工程概念:应用于软件定义、开发、维护的一绕方法、工具、文档、实践标准、工序18.软件工程三要素：1方法2工具3过程19.软件工程原则1抽象2信息隐蔽3模块化4局部化5确定性6一致性7完备性、可验证性20.软件工程内容：1软件开发技术2软件工程管理21.软件的生命周期：定义->开发->维护定义阶段：1问题定义2可行性研究3需求分析需求分析方法：1结构化分析（SA）2面向对象分析（OOA）需求分许工具：1数据流图（DFD）2数据字典（DD）开发阶段：软件设计的结构化设计原则1模块化2抽象3信息隐藏4模块独立22.软件测试的目的：1发现错误（！：没有改正）2发现迄今为止为发现的错误好3能发现迄今为止未发现的错误23.程序调试（Debug，排错）步骤：1寻找错误位置2排错3重新测试-------------数据结构与算法-------------24.数据库应用系统包含数据库系统包含数据库管理系统25.数据库的发展：人工管理阶段->文件系统阶段->数据库系统阶段.(由低级到高级)26.数据库系统特点:1数据集成2数据共享性高3数据独立性高(!:分为物理独立性和逻辑独立性)4数据的统一管理、控制27.数据库系统的三级模式结构28.数据模型：对数据特性的抽象29.数据模型三要素：1数据结构2数据操作3数据约束30.数据模型的三类型：1概念数据模型2逻辑数据模型（详细见23项）3物理数据模型31.逻辑数据模型的类型：1、E-R模型：矩形框表示实体、椭圆框表示属性、菱形框表示联系2层次模型：树形结构3网状模型4关系模型：关系模型的重要术语：1关系：用二维表表示关系2属性：二维表中的列3值域：每个属性的范围4元组：二维表中的行关系模型的三种完整性约束：1实体完整性约束2参照完整性约束3用户定义完整性约束32.数据库设计：对给定应用环境，构造最优的数据库模式，建立性能良好的数据库，使之满足各种用户需求33.数据库设计根本目标：解决数据共享问题34.数据库设计的方法：1面向对象的方法2面向过程的方法35.数据库设计步骤：需求分析(成果:需求说明书)->概念性设计阶段(成果:概念数据模型)->逻辑设计阶段(成果:逻辑数据模型)->物理设计阶段(成果:物理数据模型)。

二级公共基础知识完整版公共基础知识是一门涵盖众多领域的综合性学科，对于我们提升综合素质和应对各种考试都具有重要意义。

首先，我们来谈谈政治方面的基础知识。

政治是公共基础知识中的重要组成部分。

了解国家的政治制度、政党制度以及政治运行机制是必不可少的。

我国实行的是人民代表大会制度，这是我国的根本政治制度，保障了人民当家作主的权利。

同时，中国共产党领导的多党合作和政治协商制度也是我国政治制度的特色之一，它充分发挥了各民主党派和无党派人士在国家政治生活中的作用。

在法律方面，了解基本的法律概念和法律体系至关重要。

宪法作为国家的根本大法，具有最高的法律效力，规定了国家的根本制度和公民的基本权利义务。

此外，民法、刑法、行政法等部门法也与我们的日常生活息息相关。

比如，民法调整平等主体之间的人身关系和财产关系，当我们签订合同、处理财产纠纷时，就需要依据民法的相关规定。

经济知识也是公共基础知识的重要板块。

宏观经济和微观经济的概念及相关原理需要我们掌握。

宏观经济中，了解经济增长、通货膨胀、失业等经济现象的原因和应对策略，对于理解国家的经济政策具有重要意义。

微观经济方面，掌握供求关系、市场竞争等基本原理，有助于我们分析企业的经营决策和市场行为。

文化常识同样不可或缺。

包括我国的传统文化、现代文化以及世界文化。

我国有着悠久灿烂的传统文化，如儒家思想、诗词歌赋、书法绘画等，这些都是中华民族的瑰宝。

同时，了解现代文化的发展趋势和多元的世界文化，有助于我们开阔视野，增强文化交流与融合的能力。

科技知识在当今时代显得尤为重要。

从信息技术的飞速发展到生物技术的不断突破，科技的进步正在深刻地改变着我们的生活。

了解常见的科技成果、科技创新的趋势以及科技对社会发展的影响，能够让我们更好地适应这个科技日新月异的时代。

历史知识也是公共基础知识的一部分。

通过学习历史，我们可以了解国家和世界的发展脉络，从古代文明的兴衰到近代社会的变革，从重大历史事件到重要历史人物，历史为我们提供了宝贵的经验和启示。

二级公共基础知识全套课件原力文档全国计算机二级有10个公共基础知识选择题，对于想考90分以上的人来说，是必须了解的，不奢求100%全对，但也应该尽可能的
少错。

对于不想追求高分、只求稳过的人来说，不太需要在这些东西上花费太多的时间，毕竟这部分内容是属于高付出、低回报的知识点。

本篇文章只是整理了最基本的、较核心的知识点，如果追求知识点的完整性，建议购买高教社的推荐教材。

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

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

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

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

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

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

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

数据结构与算法一、基本概念：数据(Data)：信息的载体，能够被计算机识别、存储和加工处理的物理符号。

包括文本类型的数据(如：字母、数字、汉字)和多媒体类型的数据(如：声音、动画、图像)。

数据元素(Data Element)：是数据的基本单位，有时也称为元素、结点、顶点、记录，可以有若干个数据项（字段、域、属性）组成。

数据结构（Data Structure）：指的是数据之间的相互关系，即数据的组织形式。

其包括三个部分：1、逻辑结构：数据元素之间的逻辑关系2、存储结构：数据元素及其关系在计算机存储器内的表示。

3、数据的运算（算法）：即对数据施加的操作数据的逻辑结构有两大类：1、线性结构：特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点最多只有一个直接前趋和一个直接后继。

例：一维数组、链表、栈、队列、串2、非线性结构：特征是：一个结点可能有多个直接前趋和直接后继。

例：多维数组、广义表、树、图数据的存储结构有以下基本存储方法：1、顺序存储方法：该方法是将逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，一般通过数组来实现的。

2、链接存储方法：该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。

通过指针类型来实现的。

3、索引存储方法：该方法通常是在存储结点信息的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：关键字，地址。

4、散列存储方法：该方法的基本思想是根据结点的关键字直接计算出该结点的存储地址，通过散列函数实现。

例：除余法散列函数、相乘取整法散列函数算法的基本特征：1、可行性(Effectiveness)：针对实际问题而设计的算法，执行后能够得到满意的结果。

2、确定性(Definiteness)：算法中的每一个步骤都必须有明确的定义，不允许出现歧义性。

3、有穷性(Finiteness)：算法必须在有限时间内做完，即必须在执行有限个步骤之后终止。

二级公共基础知识第一部分数据结构(5-6个题目，占10分)*1.所谓算法是指解题方案的准确而完整的描述。

严格来说，一个算法必须具有以下五个主要特征：⏹报）2.算法的组成要素⏹算法中对数据的运算和操作及算法的控制结构3.算法设计基本方法⏹列举法归纳法递推递归减半递推回溯法*4.算法的复杂度可分为时间复杂度和空间复杂度，是衡量算法优劣的量度。

（1）算法的时间复杂度：算法的时间复杂度是指执行算法所需要的工作量。

一般情况下，算法的时间复杂度为算法中的基本操作重复执行的次数。

是问题规模n的某个函数f(n)。

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

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

（一定要注意是数据元素的集合，不是数据的集合）*6. 数据结构主要研究三个方面的问题：1) 逻辑结构是各数据元素之间的逻辑关系。

它与在计算机中的存储位置无关，是独立于计算机的。

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

3)对各种数据结构进行的运算。

7.常见的存储结构：⏹顺序存储结构链式存储结构索引存储结构散列存储结构⏹一般分为：线性存储和非线性存储8.线性表的顺序存储结构用一组地址连续的存储单元依次存放线性表中的数据元素，即以“存储位置相邻”表示“存储，表中第一个元素的存储位置作称作线性表的基地址。

所有数据元素的存储位置均可由第一个数据元素的存储位置得到ADR(ai) = ADR(a1) + (i-1)×C↑↑基地址一个数据元素所占存储量9. 线性表的插入和删除运算最坏的时间复杂度为O(n-1),最好为O(o).10.栈是限定仅在表的一端进行插入和删除操作的线性表。

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

栈顶元素总是最后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入，也是最后被删除的元素。

栈是一种后进先出的线性表。

通常用指针top指示栈顶位置，用指针bottom指示栈底位置。