计算机二级公共基础知识笔记

大家好，又见面了，我是你们的朋友全栈君。

计算机二级公共基础知识

计算机系统

考点一：计算机概述

1.计算机的发展历程
目前公认的第一台电子数字计算机是ENIAC，它于1946年在美国宾夕法尼亚大学研制成功。
根据计算机本身采用的物理器件不同，将其发展分为4个阶段

• 第一阶段是电子管计算机时代，时间为1946年到20世纪50年代
• 第二阶段是晶体管计算机时代，时间为20世纪50年代后期到20世纪60年代中期
• 第三阶段是中小规模集成电路计算机时代，时间是20世纪60年代中期到20世纪70年代初期
• 第四阶段是大规模和超大规模集成电路计算机时代，时间是20世纪70年代初期至今

2.计算机体系结构
美籍匈牙利数学家冯.诺伊曼为首的研制小组于1946年提出了“存储程序控制”的思想，并开始研制存储程序控制的计算机EDVAC。1951年，EDVAC问世，直到今天，计算机基本结构的设计仍采用冯.诺依曼提出的思想和原理，人们把符合这种设计的计算机称为“冯.诺伊曼机”。冯.诺伊曼也被誉为“现代电子计算机之父”

EDVAC的主要特点如下

1. 在计算机内部，程序和数据采用二进制数表示。
2. 程序和数据放在存储器中，即采用程序存储的概念。计算机执行程序时，无需人工干预，能自动的，连续的执行程序，并得到预期的结果。
3. 计算机硬件由运算器、控制器、存储器、输入其及输出设备五大基本部件组成。

３.计算机系统基本组成

考点二：计算机硬件系统

1.中央处理器
中央处理器(CPU)主要用于节时计算机指令和处理软件中的数据。CPU主要包括运算器和控制器两个部件.它们都包含寄存器,并通过总线连接起来。其主要运算指标有字长、主频、运算速度等。
2.存储器
用于存储程序和数据的元件,它可以自身完成程序或数据的存取。
3.外部设备
计算机中的CPU和主存储器构成主机,除主机以外,围绕着主机设置的各种硬件装置称之为外部设备.
4.总线
总线是一组能被多个部件”分时共享”的公共信息传输线路.分时是指同一时刻总线上只能传输一个部件发输的信息;共享是指总线上可以”挂接”多个部件,各个部件之间相互交换的信息都可通过这组公共线路传输.
分类:

• 片内总线
• 系统总线
• 通信总线

5.计算机的工作原理

1. 指令格式:由一串二进制代码表示的,包括操作码和操作数.
2. 指令寻址:指找到当前正在执行指令的数据地址和吓一跳将要执行指令的地址的方法.
3. 计算机指令系统:一台计算机所能执行的全部指令的集合.
4. 指令的执行过程:分为取指令,分析指令和执行指令三个过程.

考点三: 数据的内部表示

1.计算机中的数据及其存储单位
计算机内部均使用二进制数表示各种信息,但计算机在与外部沟通皇兄会采用人们比较熟悉和方便阅读的形式,如十进制数.其间的转换,主要由计算机系统的硬件和软件来实现.
2.计算机中数据的存储单位
位是计算机中数据的最小单位,二进制数码只有0和1,计算机采用多个数码表示一个数,每一个数码称1位
字节是存储容量的基本单位,一个字节由8位二进制组成.

考点四：操作系统

1.操作系统概述

操作系统是现代计算机系统中最基本和最核心的系统软件之一，所有其他的软件都依赖于操作系统的支持。
操作系统是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充。其主要作用是管理好硬件设备，提高它们的利用率和系统的吞吐量，并为用户和应用程序提供一个简单的接口，便于用户使用。
如果把操作系统看成计算机系统资源的管理者，则操作系统的任务及其功能主要有以下几个方面

• 存储器管理
• 处理器管理
• 设备管理
• 文件管理
• 提供用户接口

操作系统的分类

根据使用环境和对作业处理方式的不同，操作系统分为多道批处理操作系统、分时操作系统、实时操作系统、网络操作系统、分布式操作系统、嵌入式操作系统。

进程管理

程序的执行

程序只有经过执行才能得到结果。程序的执行又分为顺序执行和并发执行。
一个具有独立功能的程序独占处理器直至执行结束的过程称为程序的有顺序执行。顺序执行具有顺序性、封闭性及可再现性等特点。程序的顺序执行可给程序员带来方便，但系统资源利用率低。
程序的并发执行是指一组在逻辑上互相独立的程序或程序段在执行过程中，其执行时间在客观上互相重叠，即一个程序段尚未执行结束，另一个程序段的执行已经开始的执行方式。
并发执行的特点

• 失去了封闭性
• 不可再现性
• 间断性，即程序之间可以互相制约

进程的基本概念

进程是指一个具有一定独立功能的程序关于某个数据集合的一次运行活动。简单地说，进程是指可以并发执行的程序的执行过程。

进程的状态及其转换

• 运行状态
• 就绪状态
• 等待状态
• 创建状态
• 终止状态

进程控制块

每个进程有且仅有一个进程控制块（PCB），它是进程的唯一标识，是操作系统用来记录和刻画进程状态和环境信息的数据结构，是进程动态特征的汇集，也是操作系统掌握进程的唯一资料结构和管理进程的主要依据。
PCB通常应包括以下基本内容

• 进程名
• 特征信息
• 执行状态信息
• 调度优先数
• 现场信息
• 系统栈
• 进程映像信息
• 资源占用信息
• 族关系

进程的组织

• 线性方式
• 链接方式
• 索引方式

进程调度

进程调度又抢占方式和非抢占方式

其他概念

• 线程：线程是比进程更小的能独立运行的基本单位，用它来提高程序的并行程度，减少系统开销，从而进一步提高系统的吞吐量
• 死锁：由于个进程互相独立的动态获得，不断申请和释放系统中的各种软硬件资源，这就有可能使系统中若干个进程均因互相“无知的”等待对方所占有的资源而无限的等待，这种状态称为死锁。

存储管理

存储管理的功能

• 地址变换
• 内存分配
• 存储共享与保护
• 存储器扩充

存储管理技术

• 连续存储管理
• 分页式存储管理
• 分段式存储管理
• 段页式存储管理
• 虚拟存储器管理

文件管理

文件与文件系统的概念

文件时指一组带标识（文件名）的、具有完整逻辑意义的相关信息的集合。
各种操作系统的文件命名规则略有不同，文件名的格式和长度因系统而异。一般来说，文件名由文件名和扩展名两部分组成，前者用于识别文件，后者用于区分文件类型，中间用“.”分隔开。

文件类型

划分标准	文件类型
按用途划分	系统文件、库文件、用户文件等
按性质划分	普通文件、目录文件、特殊文件等
按保护级别划分	只读文件、读写文件、可执行文件、不保护文件等
按文件数据的形式划分	源文件、目标文件、可执行文件

文件系统模型

文件系统的传统模型为层次模型。该模型由许多不同的层组成，每一层都会使用下一层的功能特性来创建新的功能，为上一层服务。层次模型比较适合支持单个文件系统。

文件的组织结构

• 文件的逻辑结构

文件的逻辑结构是用户可见的结构。根据有无逻辑结构，文件可分为记录式文件和流式文件。

• 文件的物理结构

文件按不同的组织方式在外部存储介质上存放，就会得到不同的物理结构。文件的物理结构有时候也成为文件的“存储结构”

文件目录管理

用于描述和控制文件的数据结构称为文件控制块（FCB）。FCB一般包括以下内容

• 有关文件存取控制的信息
• 有关文件结构的信息
• 有关文件使用的信息
• 有关文件管理的信息

文件与FCB一一对应，而人们把多个FCB的有序集合称为文件目录。
文件目录结构

• 单机目录
• 二级目录
• 多层级目录
• 无环图结构目录和图状结构目录

存储权限
存储权限可以通过建立访问控制表和存取权限表来实现
大型文件系统主要采用两个措施来进行安全性保护

• 对文件和目录进行权限设置
• 对文件和目录进行加密

I/O设备管理

I/O的层次结构

• 用户层软件
• 设备独立性软件
• 设备驱动程序
• 中断处理程序

中断处理过程：

• CPU检查响应中断的条件是否满足
• 如果条件满足，CPU响应中断，否则CPU关中断，使其进入不可再次响应中断的状态
• 保存被中断进程的CPU环境
• 分析中断原因，调用中断处理子程序
• 执行中断处理子程序
• 退出中断，恢复被中断进程的CPU现场或调度新进程占用CPU
• 开中断，CPU继续执行

数据结构与算法

考点一：什么是算法

算法及其基本特征

算法是指对解题方案准确而完整的描述。简单地说，算法就是解决问题的操作步骤。
算法的基本特征

• 可行性
• 确定性
• 有穷性
• 拥有足够的情报

算法复杂度

算法复杂度用来衡量算法的优劣，它包括算法的空间复杂度和时间复杂度。

考点二：数据结构的基本概念

什么是数据结构

数据结构是指相互有关联的数据元素的集合。它包含两个要素，即“数据”和“结构”。
数据是需要处理的数据元素的集合
所谓结构，讲就是关系，是集合中各个数据元素之间存在的某种关系（联系）

数据结构的表示

数据的逻辑结构的数学形式定义——数据结构是一个二元组：
B=（D，R）
其中B表示数据结构，D是数据元素的集合，R是D上关系的集合，它反映了D中各数据元素之间的前后件关系。前后件关系也可以用一个二元组来表示。
一个数据结构除了用二元关系表示外，还可以用图形来表示。用中间标有元素值的方框表示的数据元素，一般称为数据节点。对于每一个二元组，用一条有向线段从前件指向后件。

基本概念	含义
根节点	数据结构中，没有前件的节点
终端节点（叶子节点）	没有后件的节点
内部节点	处理根节点和终端节点以外的节点

线性结构与非线性结构

类型	含义
线性结构	一个非空数据节点有且只有一个根节点，每个节点最多只有一个前件，也最多只有一个后件
非线性结构	不满足以上条件的数据结构，主要是树形结构和网状结构

考点三：线性表及其顺序存储结构

线性表的基本概念

数据结构中，线性结构习惯性称为线性表，线性表是最简单、也是最常用的一种数据结构。
线性表是由n（n≥0）个数据元素构成的有限序表，表中除第一个元素外的每一个元素，有且只有一个前件，除最后一个元素外，有且只有一个后件。
线性表要么是空表，要么则可以表示为
（a1,a2,…ai,…an）ai(i=1,23,…n)是线性表的数据元素，也称为线性表的一个节点。同一线性表中断数据元素必定具有相同的特性，即属于统一数据对象。

线性表的顺序存储结构

通常线性表可以采用顺序存储和链式存储两种存储结构
顺序结构是存储线性表最简单的存储，具体做法：将线性表中的元素一个接一个地存储在一片相邻的存储区域中。这种顺序存储的线性表也被称为顺序表
顺序表的特征、

• 线性表中所有元素所占的存储空间是连续的
• 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的

栈和队列

栈及其基本运算

栈是一种特殊的线性表，它所有插入与删除都限定在表的同一端进行，允许插入与删除的一端称为栈顶，不允许插入与删除的一端称为栈底。当栈中没有元素时，称为空栈。
栈的修改原则是“后进先出”或“先进后出”（类似于压弹夹）
通常用指针top来表示栈顶的位置，用指针bottom来指向栈底。栈顶top反映了栈不断变化的状态。
栈的基本运算：入栈、退栈、读取栈顶元素
栈和一般线性表的存储方法类似，通常也可以采取顺序存储和链式存储。

队列及其基本运算

队列的定义

队列是指允许在一端进行插入，而在另一端进行删除的线性表。允许进行删除运算的称为对头（排头），允许进行插入运算的一端称为队尾。若有队列：
Q=（q1,q2…qn）
那么，q1为队头元素，qn为队尾元素。与栈相反。队列又称为“先进先出”或“后进后出”的线性表

队列的运算

可以用顺序存储的线性表来表示队列。为了指示当前执行退队运算的队头位置，需要一个对头指针front；为了指示当前执行入队运算的队尾位置，需要一个队尾指针rear。队头指针总是指向对头元素的前一个位置，而队尾指针rear总是指向队尾元素。

循环队列及其运算

在实际应用中，队列的存储结构一般采用循环队列的形式。
所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，行成逻辑上的环状空间，供队列循环使用。
在循环队列中，用队尾指针rear指向队列中的队尾元素，用队头指针front指向排头元素的前一个位置。因此，从队头指针front指向的后一个位置直到队尾指针rear指向的位置之间的所有元素均为队列中的元素。

考点五：线性链表

线性链表的基本概念

线性链表指线性表的链式存储结构，简称链表。这种链表每个节点只有一个指针域，又称为单链表。
在线性链表中，第一一个元素没有前件，因此指向链表中第一个节点的指针是一个特殊指针，称为这个链表的头指针。最后一个元素没有后件。因此，线性链表最后一个节点的指针域为空，用NULL或0表示。
线性链表的存储单元是任意的，即各数据节点的存储序号可以是连续的，也可以是不连续的；各节点在存储空间中的位置关系与逻辑关系不一致，前/后件关系由存储节点的指针来表示。
当线性链表指向第一个数据元素的头指针等于NULL或0时，该表称为空表。
在某些应用中，对线性链表中的每个节点设置两个指针，一个指针域存放前件的地址，称为左指针（Llink），一个指针域存放后件的地址称为右指针（Rlink）。

顺序表和链表的优缺点比较

类型	优点	缺点
顺序表	1.可以随机存取表中的任意节点 2.无需为表示节点间的逻辑关系额外增加存储空间	1.插入和删除的运算效率很低2.存储空间不便于扩充3.不便于对存储空间进行动态分配
链表	1.当进行插入和删除运算时，只需要改变指针即可，不需要移动元素2.存储空间便于扩充并且方便空间的动态分配	需要额外的空间（指针域）来表示数据元素之间的逻辑关系，存储密度比顺序表低

考点六：树与二叉树

树的基本概念

树是一种简单的非线性结构。如一个家中的族谱关系为A有后代B、C；B有后代D、E、F，C有后代G；E有后代H、I，则这个家族的成员和血缘关系图则可以用下图表示

基本概念	含义
（父亲点）根	在树结构中，每一个节点只有一个前件，称为该节点的父亲点；没有前件的节点只有一个，称为树的根节点，简称根
子节点和叶子节点	每一个节点后面可以有多个后件，称为该节点的子节点。没有后件的节点称为叶子节点
度	一个节点所拥有的后件个数称为该节点的度，所有节点中最大的度称为树的度
深度	定义一棵树的根节点所在的层次为1，其他节点所在的层次等于其父亲点所在的层次加一。树的最大层次称为树的深度
子树	在树中，以某节点的一个子节点为根构成的树称为该节点的一棵子树

二叉树及其性质

二叉树的性质

二叉树与树不同，但它与树的结构很相似，下图表示一棵二叉树。

二叉树的特点

1. 二叉树可以为空，空的二叉树没有节点，非空二叉树有且只有一个根节点。
2. 每个节点最多有两棵子树，换句话说，二叉树中不存在度数大于2 的节点
3. 二叉树的子树有左右之分，其次序不能任意颠倒

满二叉树与完全二叉树

• 满二叉树

指除最后一层外，每一层上的所有节点都有两个子节点的二叉树。即满二叉树在其第k层上有2的(k-1)方个节点，且深度为m的满二叉树共有2的m方减一个节点。

• 完全二叉树

指除最后一层外，每一层的节点数均达到最大值，在最后一次只缺少右边若干节点的二叉树。

二叉树的存储结构

在计算机中，二叉树通常采用链式存储结构。用于存储二叉树中元素的存储系欸但由数据域和指针域两部分构成。由每一个元素可以有连个后件，因此用于存储二叉树的存储节点的指针域由两个，一个用于指向该节点的左子节点即左指针域；另一个用于指向该节点的右子节点即右指针域。

左指针域L（i）	数据域Data(i)	右指针域R（i）

由于二叉树的存储结构每一个存储节点有两个指针域，因此二叉树的链式存储也成为二叉链表。

二叉树的遍历

二叉树的遍历是指不重复的访问二叉树中所有节点。
在遍历二叉树的过程中，一般先遍历左子树再遍历右子树。再先左后右的原则下，根据访问根节点的不同次序可以分为3种：前序遍历（DLR）、中序遍历（LDR）、后序遍历（LRD）

• 前序遍历

首先访问根节点，然后遍历左子树，再遍历右子树；并且在遍历左子树和右子树时，依然先访问根节点，再遍历左子树，最后遍历右子树。
例如上图二叉树进行前序遍历的结果为A、B、D、H、E、I、C、F、G

• 中序遍历

首先遍历左子树然后访问根节点，最后遍历右子树；并且再遍历左子树和右子树时，依然首先遍历左子树，然后访问根节点，最后遍历右子树
例如上图中序遍历结果为H、D、B、E、I、A、C、G、F

• 后序遍历

首先遍历左子树，然后遍历右子树，最后访问根节点；并且在遍历左子树和右子树时，仍然首先遍历左子树，然后遍历右子树，最后访问根节点。
例如上图后序遍历为H、D、I、E、B、G、F、C、A
如果已知一颗二叉树的前序遍历序列和中序遍历序列，也可以唯一确定这棵二叉树，已知一棵二叉树的后序遍历和中序遍历，也可以唯一确定一棵二叉树。但是，已知一棵二叉树的前序遍历和后序遍历，不能唯一确定这棵二叉树的。

考点七：查找

顺序查找

基本思想：从线性表的第一个元素开始，逐个将线性表中的元素与被查找元素进行比较，若相等，则查找成功，停止查找；若整个线性表扫描完毕，仍未找到与被查元素相等的元素，则表示线性表中没有要查找的元素，查找失败。

二分法查找

能使用二分法查找的线性表必须满足两个条件：用顺序存储结构、线性表是有序表。此处的“有序”特指元素按非递减顺序排列，即从小到大的排列，但允许相邻元素相等
对于长度为n的有序线性表，利用二分法查找元素X的过程如下。

• 如果X的值与中间项相等，则查找成功，结束查找。
• 如果X小于中间项的值，则在线性表的前半部分以二分法继续查找。
• 如果X大于中间项的值，则在线性表的后半部分以二分法继续查找。

考点八：排序

排序是指将一个无序序列整理成按值非递减顺序排列的有序排列。

交换类排序

交换类排序是借助数据元素的“交换”来进行排序的一种方法。

• 冒泡排序
• 快速排序

插入类排序

插入类排序是每次将一个待排序的元素，按其元素值的大小插入前面已经排好序的子表中的适当位置，直到全部元素插入完成为止。

• 简单插入排序
• 希尔排序

选择类排序

选择类排序的基本思想是通过每一次从待排序序列中选出值最小的元素，然后将其顺序放在已排好序的有序子表的后面，直到全部序列满足排序要求为止。

• 简单选择排序
• 堆排序