计算机二级重要基础知识点

1 第一章 信息技术概述

一. 信息与信息技术

(一) 信息：

1. 客观事物立场：事物运动的状态及状态变化的方式

2. 认识主体立场：认识主体所感知或所表述的事物运动及其变化方式的形式、内容和效用

3. 信息是人们认识世界和改造世界的一种基本资源。

(二) 信息处理过程（行为和活动）：信息收集、信息加工、信息存储、信息传递、信息施用

(三) 信息技术IT：用来扩展人的信息器官功能、协助人们进行信息处理的一类技术

1. 扩展人类感觉器官功能的感测（获取）技术与识别技术——雷达

2. 扩展神经系统功能的通信技术

3. 扩展大脑功能的计算（处理）与存储技术——信息系统

4. 扩展效应器官功能的控制与显示技术

(四) 常见信息处理系统

1. 电视/广播系统：单向的、点到多点（面）的以信息传递为主要目的的系统

2. 电话：双向的、点到点的以信息交互为主要目的的系统

3. Internet是一种跨越全球的多功能信息处理系统

4. 网络聊天是一种双向的、以信息交互为目的的系统

(五) 现代信息技术

1. 特点：以数字技术为基础、以计算机为核心、采用电/光子技术。

2. 涉及领域：通信、广播、计算机、微电子、遥感遥测、自动控制、机器人等

3. 核心技术：微电子技术、通信技术、计算机技术

二. 微电子技术简介

(一) 微电子技术以集成电路为核心；集成电路芯片是信息产业的基础

(二) 集成电路IC：

1. 定义：以半导体单晶片作为材料，经平面工艺加工制造，将大量晶体管、电阻等元器件及互连线构成的电子线路集成在基片上，构成一个微型化的电路或系统。

2. 特点：体积小、重量轻、可靠性高、功耗小

3. 现代集成电路使用的半导体材料：硅（Si）、砷化镓（GaAs）等

4. 制造：

1) 工序：从原料熔炼开始到最终产品包装大约需要400多道工序。

2) 条件：必须在恒温、恒湿、超洁净的无尘厂房内完成。

3) 工艺技术名称：硅平面工艺

二级公共基础知识考点分析

第1章 数据结构与算法

1.1 算法和数据结构的基本概念

1.算法

（1）算法的基本概念

算法是指解题方案的准确而完整的描述。

A.算法的基本特征：①可行性；②确定性；③有穷性；④拥有足够

的情报。

B.算法的基本要素：①算法中对数据的运算和操作：基本的运算和

操作包括算术运算、逻辑运算、关系运算和数据传输；②算法的控制结

构：基本的控制结构包括顺序结构、选择结构、循环结构。

C.算法设计的基本方法：①列举法；②归纳法；③递推；④递归；

⑤减半递推技术；⑥回溯法。

（2）算法的复杂度

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

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

工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算

次数是问题规模的函数。即：算法的工作量=f(n)其中n是问题的规模。

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

一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据

所占用的存储空间以及算法执行过程中所需要的额外空间。

2.数据结构的基本概念

数据结构作为计算机的一门学科，主要研究和讨论以下三个方面的

问题：

①数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结

构；

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

据的存储结构；

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

（1）数据结构的定义

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

②数据处理是指对数据集合中的各元素以各种方式进行运算，包括

插入、删除、查找、更改等运算，也包括对数据元素进行分析。

③数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。

④数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储

结构（也称数据的物理结构）。常用的存储结构有顺序、链接、索引等

存储结构。 （2）数据结构的图形表示

在数据结构的图形表示中，对于数据集合D中的每一个数据元素用

计算机二级公共基础知识重点讲解汇总

第一章 数据机构与算法

数据结构与算法

◆算法的基本概念

1. 算法：是对问题处理方案的正确而完整的描述，是求解问题的方法，是指令的有效序列。

2. 具有5个特性：

（1） 有穷性（在有穷步后完成）算法程序的运行时间是有限的

（2） 确定性（每一步都有确定的含义）

（3） 可行性

（4） 输入（一个算法有零个或多个输入）

（5） 输出（一个算法有一个或多个输出）

3. 算法的复杂度

包括：时间复杂度和空间复杂度。 二者没有必然的联系。

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

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

◆数据结构的定义

1. 数据结构包括数据的逻辑结构、数据的存储结构、数据的操作

数据的逻辑结构：数据的外部结构，指各数据元素之间的逻辑关系，反映人们对数据含义的解释。 包括：线性结构（线性表、栈、队列）和非线性结构（树和图） 章节 名称 内容简介

第一章 数据结构与算法 本章主要介绍算法的基本概念、数据结构的定义、线性表、树等重点知识的讲解。

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

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

第四章 数据库设计基础 本章主要介绍数据库、数据库管理系统（DBMS）、数据库系统、数据模型、关系运算、专门关系运算、数据库设计步骤等重点知识的讲解。 数据的存储结构：数据的物理结构，指数据的逻辑结构在计算机中的表示。

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

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

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

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

第一部分 算法与数据结构 (历年比例41%) 1、算法 ◆问题处理方案的正确而完整的描述称为【算法】。算法分析的目的是，分析算法的效率以求改进。算法的基本特征是【可行性】、【确定性】、【有穷性】和拥有足够情报。

◆算法的有穷性是指：算法程序的运行时间是有限的。

◆算法的复杂度是衡量算法好坏的度量，分为【时间复杂度】和【空间复杂度】。

★★时间复杂度是指执行算法所需要的【计算工作量】；算法的空间复杂度是指算法执行过程中所需的【存储空间】。

◆算法时间复杂度或空间复杂度中的一项的值，没有办法推出另一项的值。

2、数据结构 ◆数据结构分为【逻辑结构】和【存储结构】。线性结构和非线性结构属于逻辑结构；顺序、链式、索引属于存储结构(物理结构)。循环队列属于【存储结构】。

★ 数据的存储结构又称为物理结构，是数据的逻辑结构在计算机存储空间中的存放形式。

◆一个逻辑结构可以有多种存储结构，且各种存储结构影响数据处理的效率。程序执行的效率与数据的存储结构密切相关。

◆数据结构分为线性结构和非线性结构，带链的队列属于【线性结构】。

◆线性表的存储结构主要分为顺序存储结构和链式存储结构。顺序存储结构的存储一定是连续的，链式存储的存储空间不一定是连续的。

◆有序线性表既可以采用顺序存储结构，也可以采用链式存储结构。

◆队列是一种特殊的线性表，循环队列按照【先进先出】原则组织数据。循环队列是队列的【顺序】存储结构。

◆数据的独立性分为【物理独立】性和【逻辑独立性】。当数据的存储结构改变时，其逻辑结构可以不变，因此，基于逻辑结构的应用程序可以不用修改，称为【物理独立性】。

3、栈和队列 ★★栈是一种特殊的线性表，是只能在一端进行插入和删除的线性表，特点是FILO(FirstIn Last Out)。

★★栈是【先进后出】的线性表；栈具有记忆作用；对栈的插入与删除操作中，不需要改变【栈底指针】。假定让元素1、2、3、A、B依次入栈，则出栈的顺序是：B、A、3、2、1。