二级公共基础知识

全国计算机全国计算机二级公共基础知识二级公共基础知识二级公共基础知识((重点部分重点部分))第一章 数据结构基础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、数据的运算：检索、排序、插入、删除、修改等。

算法算法的定义1.算法是指对解题方案准确而完整的描述，简单的说，就是解决问题提的操作步骤。

在编程时由于受到计算机系统运行环境的限制，所以，程序的编制通常不可能优于算法的设计。

2.算法的基本特征可行性：算法在特定的执行环境中执行应能得到满意的结果，即必须有一个或多个输出。

一个算法即使在数学理论上成立，但如果在实际计算工具上不能执行，则该算法也不具有可行性。

确定性：算法的可行性表现在对算法中的每一步的描述都是明确的。

有穷性：算法的操作步骤是有限个的，且每个步骤都能在有限时间内完成。

拥有足够的情报：在也拥有足够的输入信息和初始化信息时，才是有效的。

3.算法的基本元素1)算法中对数据对象的运算和操作指令系统：一个计算机系统能执行的所有指令的集合，称为该计算机的指令系统。

计算机的算法就是计算机能执行的操作所组成的指令序列2)算法的控制结构算法的控制结构是算法中个操作之间的执行顺序。

算法一般由顺序、选择、循环3中基本结构组成。

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

1.算法的时间复杂度：是指执行算法所需要的计算工作量，是由所执行的基本运算次数来度量的。

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

由三个部分组成，输入程序所占的储存空间；程序本身所占的内存空间；算法执行过程中所需要的额外空间。

数据的结构基本概念数据结构的定义1.数据结构的研究的内容包括三个方面：●数据集合中各数据元素之间固有的逻辑关系，即数据的逻辑结构。

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

●对数据结构进行的运算。

1。

1 算法考点1 算法的基本概念计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法.算法(algorithm）是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，同时是明确的；此顺序将在有限的次数后终止。

算法是对特定问题求解步骤的一种描述,它是指令的有限序列，其中每一条指令表示一个或多个操作.1算法的基本特征(1)可行性(effectiveness)：针对实际问题而设计的算法，执行后能够得到满意的结果。

(2)确定性（definiteness）：算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。

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

(4)拥有足够的情报：要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时，此算法才最有效的;而当提供的情报不够时，算法可能无效。

2算法的基本要素(1）算法中对数据的运算和操作：每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列.计算机可以执行的基本操作是以指令的形式描述的。

一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。

计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列在一般的计算机系统中，基本的运算和操作有以下4类：①算术运算：主要包括加、减、乘、除等运算；②逻辑运算：主要包括“与”、“或”、“非"等运算；③关系运算：主要包括“大于"、“小于”、“等于”、“不等于"等运算；④数据传输：主要包括赋值、输入、输出等操作。

(2)算法的控制结构：一个算法的功能不仅仅取决于所选用的操作，而且还与各操作之间的执行顺序有关.算法中各操作之间的执行顺序称为算法的控制结构.算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。

全国计算机二级考试公共基础知识一、选择题1.八进制基数为8，因此在八进制数中可使用的数字符号是0和1。

A、正确B、错误*2.第三代计算机时代是从1965年到1971年。

A、正确*B、错误3.硬盘的转速指的是每秒多少转。

A、正确B、错误*4.计算机存储的基本单位的比特。

A、正确B、错误*5.显示器的垂直扫描频率又称为刷新率，刷新率越高图像越稳定，闪烁感越小。

A、正确*B、错误6.每个汉字具有唯一的内码和外码。

A、正确B、错误*7.在Windows中，可以对桌面上的图标顺序进行重新排列。

A、正确*B、错误8.在数据表中设置字段标题后，如果查询中输入了该字段也将显示字段标题而不是字段名。

A、正确B、错误*9.查询记录表中显示的字段必须是数据库中已有的字段。

A、正确B、错误*10.两个之间必须存在着相互关联的字段，才能在两个表之间建立关系。

A、正确*B、错误11.回收站是内存中的一块区域，用于暂存被删除的文件。

A、正确B、错误*12.共享软件是作者免费让用户使用的软件，不需要缴费购买。

A、正确B、错误*13.删除多余的输入法可以提高计算机的性能。

A、正确*B、错误14.剪切板中只能存放文字，不能存放图像。

A、正确B、错误*15.证书机制是非对称密码算法的一种应用。

A、正确*B、错误16.计算机网络的通信子网负责全网面向用户的数据处理与管理。

A、正确B、错误*。

二级公共基础知识（经典版）编制人：__________________审核人：__________________审批人：__________________编制单位：__________________编制时间：____年____月____日序言下载提示：该文档是本店铺精心编制而成的，希望大家下载后，能够帮助大家解决实际问题。

文档下载后可定制修改，请根据实际需要进行调整和使用，谢谢!并且，本店铺为大家提供各种类型的经典范文，如工作报告、致辞讲话、条据书信、合同范本、规章制度、应急预案、心得体会、教学资料、作文大全、其他范文等等，想了解不同范文格式和写法，敬请关注!Download tips: This document is carefully compiled by this editor. I hope that after you download it, it can help you solve practical problems. The document can be customized and modified after downloading, please adjust and use it according to actual needs, thank you!Moreover, our store provides various types of classic sample essays, such as work reports, speeches, policy letters, contract templates, rules and regulations, emergency plans, insights, teaching materials, essay encyclopedias, and other sample essays. If you want to learn about different sample formats and writing methods, please pay attention!二级公共基础知识二级公共基础知识_二级计算机二级考试是全国计算机等级考试四个等级中的一个等级，考核计算机基础知识和使用一种高级计算机语言编写程序以及上机调试的基本技能。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

全国计算机等级考试二级教程——公共基础知识一、操作系统基础知识1.操作系统是什么？请简要说明其作用和功能。

操作系统是计算机系统中的一种软件，它负责管理和控制计算机硬件资源，并为用户程序提供运行环境。

其主要功能包括进程管理、内存管理、文件系统管理和设备管理等。

2.请列举几种常见的操作系统。

常见的操作系统包括Windows、Linux、Mac OS、Android等。

3.什么是进程？什么是线程？进程是正在执行的程序的实例，是操作系统资源分配与调度的基本单位。

线程是进程中的一个执行单元，一个进程可以包含多个线程。

4.什么是文件系统？文件系统是一种组织和管理计算机存储设备上数据的方法，用于存储和检索文件，并提供对文件的访问控制和保护。

二、计算机网络基础知识1.什么是IP地址？IP地址的作用是什么？IP地址是因特网协议（IP）的网络接口的标识，用于唯一地标识和定位网络上的计算机设备。

IP地址的作用是用于在数据通信中确定源和目标的地址。

2. 请简述Internet的结构。

Internet的结构是由成千上万个相互连接的计算机网络组成的，形成一个全球性的网络。

它使用一种称为互联网协议（IP）的通信协议进行数据传输，通过路由器相互连接。

3.什么是HTTP协议？HTTP协议有哪些特点？HTTP协议（Hypertext Transfer Protocol）是一种用于从服务器传输超文本到客户端的协议。

它的特点包括无连接性、无状态性和可扩展性。

三、数据库基础知识1.什么是数据库？数据库的作用是什么？数据库是存储、管理和组织数据的集合，它提供了一种结构化的方式来组织和存储数据，以便于数据的存取和处理。

数据库的作用是存储和管理大量的数据，并为用户提供数据查找、插入、更新和删除等功能。

2.请简述关系数据库的特点和优点。

关系数据库是一种以关系为基础的数据模型。

它的特点包括数据的结构化、数据间的关系建立、数据的操作和约束等。

关系数据库的优点是数据的一致性、数据的可扩展性、数据的安全性和数据的完整性。

二级公共基础知识总结第一章数据结构与算法1.1 算法算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。

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

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

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

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

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

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

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

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

1.2 数据结构的基本基本概念数据结构研究的三个方面：（1（2（3）对各种数据结构进行的运算。

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

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

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

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

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

1．3 线性表及其顺序存储结构线性的。

非空线性表的结构特征：（1）且只有一个根结点a1，它无前件；（2）有且只有一个终端结点an，它无后件；。

1。

1 算法考点1算法的基本概念计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。

算法(algorithm）是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，同时是明确的；此顺序将在有限的次数后终止.算法是对特定问题求解步骤的一种描述,它是指令的有限序列，其中每一条指令表示一个或多个操作。

1算法的基本特征(1）可行性（effectiveness)：针对实际问题而设计的算法，执行后能够得到满意的结果.（2)确定性(definiteness)：算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。

(3)有穷性(finiteness)：算法必需在有限时间内做完，即算法必需能在执行有限个步骤之后终止.（4）拥有足够的情报：要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时，此算法才最有效的；而当提供的情报不够时，算法可能无效。

2算法的基本要素（1)算法中对数据的运算和操作：每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列.计算机可以执行的基本操作是以指令的形式描述的。

一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。

计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列在一般的计算机系统中，基本的运算和操作有以下4类：①算术运算：主要包括加、减、乘、除等运算;②逻辑运算:主要包括“与"、“或”、“非"等运算；③关系运算：主要包括“大于”、“小于"、“等于"、“不等于”等运算;④数据传输：主要包括赋值、输入、输出等操作。

（2）算法的控制结构：一个算法的功能不仅仅取决于所选用的操作,而且还与各操作之间的执行顺序有关。

算法中各操作之间的执行顺序称为算法的控制结构.算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。

二级公共基础知识第一部分数据结构(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指示栈底位置。

公共基础知识总结第一章数据结构与算法1.1算法算法：是指解题方案的准确而完整的描述。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第一章数据结构与算法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计算机上运行，效率均不同。