软考初级程序员

程序员上午考试培训视频教程

01_1计算机硬件基础_数据表示及运算

软考初级知识点（重点、难点）

1.原码

2.反码

如果是正数，反码为本身；如果是负数，反码是除去符号位的部分取反，符号位为1

3.补码

如果是正数，反码为本身；如果是负数，反码是除去符号位的部分取反+1（二进制加法），最高位如果有进位，丢弃进位的值，符号位为1

4.移码

例如：

x=+1011 那么移码为11011 （与补码的符号位相反，1表示正号，0表示负数）

5.奇偶校验码只能发现错误不能纠正错误

小结

本讲主要讲解了二进制编码及其运算相关知识，数制转换、补码在历年试题中出现较多

原码、反码、补码（考的较多）的表示范围和海明码（考概念）是本讲的难点。

01_2_计算机系统的组成

计算机硬件主要由运算器、控制器、存储器、输入输出设备五大部分组成，集成在一起的运算器和控制器成为中央处理单元（CPU）

操作系统是管理硬件的系统软件，应用软件是在操作系统之上运行（如Word）

一条指令一般包括两个基本组成部分：操作码和地址码

寻址方式包括立即寻址、直接寻址、寄存器寻址、寄存器间接寻址、间接寻址、相对寻址、变址寻址。

操作数各位顺序往某一方向移动成为移位，移位指令主要有三种类型：算术移位、逻辑移位和循环移位。算术移位指令对带符号数进行移位。逻辑移位指令对无符号操作数进行移位。循环移位指令分为带进位循环移位和不带进位循环移位两大类。算术右移的左边补位和符号位有关。符号位是1就补1，符号位是0，就补0，算术左移和逻辑左移一样（历年考得比较频繁）

小结

本讲对计算机的组成和系统结构进行了讲解，比较详细介绍了各部分的结构及功能

本章考的比较多的是CPU组成部分、总线、移位操作等知识点

01_3_存储系统

存储器按照是否能读写可分为读写存储器、只读存储器。读写存储器有RAM，可读可写，断电信息无法保存：RAM分为两种：DRAM，再有点情况下，信息随着时间的推移而逐渐消失，因此它会定时刷新；SRAM，在不断电的情况下，信息会一直保持下去。

ROM：只读存储器，只可读无法改写。

存储器访问方式分为顺序存取、直接存取、随机存取、相联存取

存取速度由高到低依次为：CPU内部存储器>cache>主存>磁盘

小结

本讲主要讲述了计算机系统中的存储结构，重点讲解了CACHE地址映射方式以及磁盘参数计算问题，这也是历年常考的知识点。

无论采用什么样的地址映像方式和地址变换方式，都要吧主存和cache划分成同样大小的存储单位，每个存储单位成为“块”。在进行地址映像和地址变换过程中，都以块为单位进行调度。

02_1_操作系统_操作系统类型与结构

操作系统的四个特征：并发性、共享性、虚拟性、不确定性

操作系统五大功能：进程管理、文件管理、存储管理、设备管理、作业管理

批处理操作系统分为单道批处理操作系统和多道批处理操作系统

分时操作系统的典型代表是UNIX，特点是多路性、独立性、交互性、及时性

实时操作系统分为实时控制系统和实时信息处理系统，实时系统与分时系统相同之处是多路性和独立性，区别：系统设计目标不同，交互强弱不同，响应时间的敏感程度不同，可靠性不同；以上三种操作系统为基本操作系统

网络操作系统有两种工作模式：客户机/服务器模式（C/S模式）和对等模式

分布式操作系统最基本的特征是处理上的分布。分布式操作系统与网络操作系统的比较：分布性，并行性，透明性，共享性，健壮性。（分布式操作系统的功能较为强大）

常见的微机操作系统有windows，linux，SCO Unix，DOS等

嵌入式操作系统都具有如下特点：微型化，易于定制，可靠性高，易于移植

操作系统的结构设计模式有5种：模块化结构，层次化结构，C/S结构，对象模式（windowsNT），对称多处理模式

Unix系统结构分为3层，最内层是Unix操作系统核心，最外层是用户程序，中间层是shell命令解释器，实用程序，库函数等

小结

本讲介绍了各种类型的操作系统及其它们的特点，其中一些具有共同特点的操作系统类型注意区别

本讲介绍的知识点，历年考的最多的操作系统的特点和Unix相关知识

02_2_进程管理

程序顺序执行的特征：顺序性，封闭性，可再现性；程序并发执行导致不可再现性

进程实体通常有程序、数据和进程空值块（PCB）组成，进程是系统进行资源分配和

调度的独立的基本单元

进程和程序是两个截然不同的概念，进程具有程序不具备的5个基本特征：动态性（最基本的特征）、并发性、独立性、异步性、结构特征；进程的3种基本状态：运行、就绪和阻塞（后加入新建和终止）

操作系统内核有3个支撑功能：中断处理，时钟管理和原语操作；操作系统内核有3大资源管理功能：进程管理、存储管理、设备管理

进程之间异步执行，同步即是使各进程按一定的制约顺序和速度执行。同步关系是直接制约关系，互斥关系是简介制约关系。

互斥临界区管理的4个原则：有空即进、无空则等、有限等待和让权等待

信号量是整型变量，它分为两类：公用信号量和私用信号量

进程高级通信的类型有3种：共享存储系统、消息传递系统和管道通信

一个作业从提交到完成需要经历高、中、低3个级别的调度（高级调度、中级调度、低级调度）；调度方式分为剥夺与不可剥夺两种。

常用的进程调度算法有：先来先服务，时间片轮转，优先级调度（分为静态优先级算法和动态优先级算法），多级反馈调度（是时间片轮算法和优先级算法的综合）

引发死锁的原因有以下几种：①进程推进顺序不当②PV操作不当③同类资源分配不当（历年考点）

同一个进程中的多个线程可以并发执行。线程也有就绪、运行和阻塞三种基本状态。

小结

本讲是操作系统中的重点之一，本讲的重点是进程状态和PV操作。

要求透彻理解PV操作并能运用

02_3_存储管理

地址空间分为名空间、逻辑地址空间（简称地址空间）、存储空间

地址重定位指将程序的逻辑地址转为物理地址，分为静态重定位和动态重定位。

分页存储管理系统将逻辑地址划分为若干大小相等的片，称为页面或页，相应的，贮存空间也分为跟页一样大小的片，称为物理块或者页框。分页存储管理系统中可以用快表来保存当前访问频率高的少数活动页的页号，对应页框号以及他信息的相联存储器。（页号+页内地址，其中页内地址表示页面的大小，页号表示最多的页）

分段存储管理中，作业的地址空间被分为若干个大小不必相等的段，每个段定义了一组逻辑信息。（段号+段内地址，其中段内地址表示段的最大长度，段号表示作业最多的段）

以上介绍的存储管理方式均为实存管理

虚拟存储器基于局部性原理，可以使一个大的用户程序在较小的内存空间中运行，称其为虚拟存储器

分页虚拟存储器（又称请求分页系统）是在管理实存的分页系统上，增加了请求调页功能和页面置换功能的虚拟存储系统

分段虚拟存储器是在管理实存的分段系统上，增加了请求调页功能和页面置换功能的虚拟存储系统

常见的页面置换算法（服务于虚拟存储器）：最佳页面置换算法（OPT算法，在现实中不可能实现，只是作为评价其他置换算法的标准）；最近最久未使用置换算法（LRU算法）；先进先出置换算法（FIFO算法）；最近未用置换算法（NUR算法）

小结

本讲从实存和虚存管理两个方面讲述了各种存储器管理方式，分页（段）系统在实存和虚存管理中均有应用，不仅仅属于虚存应用

页面置换算法中，OPT算法是以未来页面调度状况为依据的，因为不可能预知未来调入页面的状况，因此无法实现，而其他几种置换算法则是依据页面调度的历史数据，他假设未来的页面调度情况跟过去一段时间内的情况一样。

分页存储管理和页面置换算法是本讲重点

02_4_设备管理

设备管理的任务：记录和监控设备状态，设备的分配和释放，管理缓冲区，实现I/O设备的物理操作，为用户提供设备使用的接口，设备的访问和控制，输入输出缓冲和调度 缓冲技术根据实现方式分为硬件缓冲和软件缓冲，硬件缓冲是利用专门的硬件寄存器作为缓冲，而软件缓冲则是通过操作系统实现的。

缓冲可分为单缓冲、双缓冲和循环缓冲

Spooling技术（假脱机技术，考点），利用该技术可使对外设的操作跟CPU对数据的处理同时进行。假脱机其实就是对脱机输入输出技术中输入输出工作的程序模拟。

Spooling系统（假脱机）主要有以下3个部分组成：①输入井、输出井和井管理程序

②输入缓冲区和输出缓冲区③预输入程序和缓输程序

磁盘调度分为移臂调度和旋转调度两类，并且先进行移臂调度然后进行旋转调度。移臂

调度有:先来先服务算法；最短寻道时间优先算法；扫描算法（又称电梯调度算法）；循环扫描算法（基于扫描算法，又称单向扫描算法）。旋转调度有旋转调度算法

小结

本讲简略的介绍了操作系统的设备管理功能

本讲涉及的内容在历年考题中的比例比较少，主要考概念，比如spooling技术、缓冲，以及他们之间的区别。

02_5_文件管理

常见的文件系统的类型有：FAT,VFAT,FAT32,NTFS,EXT2（linux系统中标准的文件系统）,HPFS,HFS

常见的文件系统的物理结构有3种：连续结构、链式结构和索引结构

常见的目录结构有：以及目录结构、二级目录结构和多级目录结构

以\/：*？<>|‘’命名的文件名是非法的文件名，空格命名的文件是合法的文件；合法的可执行文件的扩展名包括exe,com（command）,bat（batch）

一个完整的文件名由驱动器号，路径，文件名和文件的扩展名组成C:\a.txt

小结

本讲介绍了文件相关知识，历年考得比较多的是文件命名的合法性以及文件的路径（相对路径与绝对路径）等知识

其他知识点较少考，但作为备考也要了解

02_6_作业管理

控制用户作业运行有两种方式：脱机方式和联机方式

作业由程序、数据和作业说明书组成。

作业有四种状态：提交、后备、执行和完成

作业调度的算法：先来先服务调度算法，短作业优先调度算法，高响应比调度算法

小结

本讲作业介绍了作业控制及调度，人机界面等知识点

本讲重点是3个作业调度算法：先来先服务调度算法，短作业优先调度算法和高响应比算法（历年试题中常有考察）

03_1_数据库基础知识知识_数据库系统

数据库系统阶段的特点是：数据结构化，数据共享性高、冗余度低且易扩充、数据独立性高。

数据模型三要素：数据结构，数据操作和数据约束条件

E-R模型用来表达人对现实师姐的抽象，是一种概念模型（又称为模式）的表达方法。 常见的三种数据模型是层次结构、网状模型和关系模型。层次模型采用树形结构来表示数据之间的关系；网络结构表示实体类型及实体键联系的数据模型成为网状模型，他允

许多个节点无双亲，也允许一个节点有多个双亲；关系模型（主流模型）中用表结构表示实体集以及实体之间的联系，其最大的特点是描述的一致性，表中行称为元数据，列称为属性

一个1:1联系可以转换为一个独立的关系模式，也可以与任意一端对应的关系模式合并。

一个1:n联系可以转换为一个独立的关系模式，也可以与任意n端对应的关系模式合并。

一个m:n联系只能转换为一个独立的关系模式；三个以上实体之间一个多元联系可以转换为一个独立的关系模式。

DBMS的功能：数据定义功能（DDL），数据操作功能（DML），数据运行管理，数据组织、存储和管理，数据库的建立与维护

数据控制功能：①数据库的安全与维护②数据的完整性③并发控制④故障恢复

DBMS主要由存储管理器和查询管理器两大部分组成

数据库的三级模式结构：外模式，模式，内模式

数据库系统体系结构包括：集中式数据库系统，C/S数据库系统，分布式数据库系统

小结

本讲介绍了数据库系统的相关知识;数据模型，DBMS的功能，三级模式结构等，大部分是一些基本概念

本讲的重点在于对三级模式结构的理解和把握。

03_2_关系运算

完整性约束包括：实体完整性（主属性，注意不是主码），参照完整性（主外码关系），用户自定义完整性

集合运算包括：笛卡尔积，并，交，差（行操作），投影（列操作），选择（行操作），连接（如果两个关系中进行比较的分量必须是相同的属性组，并且在结果中把重复的属性列，成为自然连接）

小结

本讲主要讲述了基本的关系运算：笛卡尔积，并，交，差等传统稽核操作以及投影，选择等专门的关系运算

本讲重点是连接操作，历年试题中常出现对自然连接的考察

03_3_数据库语言

SQL组成部分：数据定义语言DDL，数据操作语言DML,事务控制，完整性，权限管理

SELECT历年考察较多

一个汉字占用2个字符。例：查询名字中第二个字为“阳”的学生的姓名，学号则可以写成：SELECT sname,sno F ROM student WHERE sname LIKE ‘_ _阳%’；

带EXISTS谓词的子查询不返回任何数据，只产生逻辑真值或逻辑假值

小结

本讲较详细介绍了SQL的功能：定义基本表，视图和索引；SELECT基本查询语句，单表查询，连接查询，嵌套查询，聚集函数和EXISTS谓词等查询方式；对表的修改，删除，权限管理

本讲的重点是基本表的创建语句和查询语句

03_4_数据库控制安全

数据库管理运行的基本工作单位是事务。事务具有以下特性：原子性，一致性，隔离性，持续性。事务通常以BEGIN TRANSACTION（事务开始）语句开始，以COMMIT或ROLLBACK语句结束

数据库的并发操作的3个问题：丢失数据，读脏数据，不可重复读。解决数据并发操作的问题引入锁机制，封锁类型包括排他型封锁（简称X封锁，又称写锁），共享型封锁（简称S封锁，又称读锁）

事物内部故障的恢复是由系统自动完成的，对用户是透明的。系统故障的恢复在重新启动时自动完成，不需要用户干预

用户标识和鉴别是系统提供的最外层的安全保护措施。

存取控制，在SQL中授权和收回就是通过GRANT和REVOKE来实现的

审计往往是保证数据库完全的一种补救措施。数据库系统中的审计工作包括以下几种：设备安全审计，操作审计，应用审计，攻击审计

完整性约束中参照完整性约束删除元组时，有三种删除方式：级联删除（cascades），受限删除（restrict默认），置空删除

小结

本讲主要介绍了事务的特征，并发控制存在3个问题：丢失数据，读脏数据和不可重复读，数据恢复与控制

数据恢复不管是用的什么方式，其基本原理都是简历冗余数据

本讲重点在于并发控制的3个问题

04_1_数据结构_概述及线性表

数据结构中，元素之间的相互关系称为数据的逻辑结构，元素及元素之间关系在计算机中的存储形式称为数据的存储结构或物理结构。数据结构按逻辑结构不同分为线性结构和非线性结构两大类，常见的线性结构有线性表，栈和队列，常见的非线性机构有树，图等

线性表的存储结构主要有两种存储方式：顺序存储和链接存储。其中最基本的节点结构有两个域：数据域和指针域

栈具有先进后出的特征。队列（顺序队列，循环队列克服了顺序队列的越界问题）具有先进先出的特性

数组是线性表的扩展。二维数组的存储结构分为以行为主序和以列为主序两种方式，影响到地址计算

稀疏矩阵有两种存储方式：三元组存储和十字链表存储

两个字符串的比较适宜字符的ASCII码值作为依据

小结

本讲主要探讨了数据结构中最简单的线性结构：线性表，栈，队列，数组和字符串。其中栈，循环队列，数组地址计算考的比较多

矩阵的压缩存储其实是将数组的存储和系数矩阵集合起来考察的一种形式

04_2_树和二叉树

一个结点的子树数目称为该结点的度，树中各结点度的最大值称为树的度，度为0的结点称为叶子结点，除叶子结点以外的结点称为分支结点，除根结点和叶子结点外的结点称为内部结点

树的遍历主要有三种方式：①前序遍历②后序遍历③层次遍历

二叉树有顺序存储（适合完全二叉树）和链式存储两种方式。链式存储

二叉树遍历有4种方式：①前序遍历②中序遍历③后序遍历④层次遍历

根据前序和中序遍历序列可以确定一个二叉树；根据后序和中序遍历序列也可确定一棵二叉树；前序和后序遍历序列不能确定一棵二叉树

没有度为1的二叉树称为严格二叉树或者正则二叉树，哈夫曼树属于正则二叉树，哈夫曼树一般也称为最优二叉树，哈夫曼树构造算法知识构造最忧二叉树的充分条件，而不是必要条件

哈夫曼编码属于前缀编码，利用哈夫曼树来得到的前缀编码的平均码长最小，称为最优前缀码

小结

本讲主要讲述了树，二叉树，哈夫曼树三大知识点及其相关知识，对在理解上述知识时存在的可能误区做了详细的提示。

对于程序员级别来说，用栈来实现二叉树前序遍历、后序遍历和中序遍历的非递归算法是有必要的，这作为课后思考题留给大家练习

有兴趣的同学可以试着用C语言实现哈夫曼树构造算法和哈弗编码算法，这对练习编码很有帮助。

04_3_图

图可以用一个邻接矩阵存储。对于无向图，定点vi度是邻接矩阵中第i行或者列元素之和；对于有向图，定点vi出度是邻接矩阵中第i行元素之和，入度是滴i列元素之和 图也可用邻接链表存储。邻接链表中有两种结点：表节点和表头节点

图的遍历包括：广度优先遍历，深度优先遍历

按深度和广度优先搜索分别进行遍历将得到不同的生成树，分别为深度生成树和广度生成树；连通图的生成树是该图的最小连通子图，有n个顶点的连通图的生成树有n-1条边，在该生成树任意加一条边必形成回路。对一个带权的图，在一棵生成树中，个条边的权值之和称为这棵生成树的代价，其中代价最小的生成树称为最小代价生成树，简称最小生成树。

小结

本讲主要讲述了图的相关知识，图的遍历，拓扑排序，最小生成树算法相对来说比较重要本讲中的个算法是依赖图的存储结构的，在学习算法的C语言实现的程序时要注意这一点

04_4_排序

直接插入排序算法（有一个监视哨，算法思想为两两比较）的时间复杂度为为O() 是一种稳定的排序方法。希尔排序算法的时间复杂度为O()，是一种不稳定的算法。

直接插入排序与空间排序的空间复杂度都是O(1)

直接选择排序（选择记录中最小的记录与第一个记录交换，其余的记录中最小的与第二个记录交换），是一种不稳定的算法的平均时间复杂度为O()，空间复杂度是O(1)。

堆排序是一种树形选择排序，堆排序的关键步骤有两个：一个是建立初始堆；二是将未排好序的序列最后一个元素跟根结点交换，并输出根结点（不在参加排序），继续调整使之重新成为堆，重复上述两步。堆排序是一种不稳定的算法，最坏最好的情况下的时间复杂度均为O(nlogn)，空间复杂度是O(1)。

冒泡排序（选择排序的分支）冒泡排序最好的时间复杂度是为O(n)，最坏的时间复杂度为O()，是一种稳定的算法。快速排序是一种不稳定的算法，在最坏的情况下时间复杂度是O（），最好的情况下比较次数为O(nlogn)，快速排序是基于关键字比较的内部排序算法中最快的。

归并排序是一种稳定的排序算法，无论最好还是最坏的情况下时间复杂度均为O(nlog2n)，可用顺序存储结构，也易于在链表上实现。

基数排序算法是稳定的

04_5_查找

顺序查找适用于顺序存储结构，也适用于链式存储结构

二分查找可用二叉树描述

分块查找

以上查找为静态查找表

二叉排序树的右孩子比根结点大，左孩子比根结点小。

小结

本讲主要讲述了查找方面的知识，考的比较多的是二分查找、二叉排序树

二叉排序树上节点的删除是个难点，要结合例子理解（必须熟悉中序遍历）

05_1_2多媒体基础知识

考试大纲需要掌握多媒体的知识点有：

考点1 音频和图形图像的相关概念

考点2 多媒体相关计算问题

考点3 常见多媒体标准

考点4 压缩技术

音频相关概念：音量、音调、音色、声音的带宽。需要了解和记忆的频率范围。人耳能听到的音频范围：20Hz~20kHz。人说话的音频范围：300~3400Hz。乐器的音频范围：

20Hz~20kHz。采样、采样频率和采样精度的相关概念

图形和图像的相关概念：图形被称为矢量图，图像被成为位图。图像和图形最大的区别在于记录的方式不同。亮度、色度和饱和度

光的三原色为红绿蓝

图像文件大小计算

音频文件的大小计算

文件的字节数=采样频率(Hz)*采样位数(位)*声道数(单声道、双声道…)/8

视频文件大小计算

文件的字节数=每帧图像容量(Byte)*每秒帧数*时间

05_3_4多媒体基础知识

常见的多媒体标准：MPEG-1（音频编码规定）,MPEG-2（右面都是视频编码）,MPEG-4,MPEG-7（多媒体内容描述接口）,MPEG-21

常见的图形文件：BMP,DIB,PCX,DIF,WMF,GIF,JPEG,PSD（PS存储格式）,CDR,PCD 常见的音频格式：WAVE,MOD,MP3(MPEG1-Layer3),Real Audio,CD Audio，MIDI（占用文件空间最小）

视频信息在计算机中存放具体格式有很多，常见的有以下几种：QuickTime，AVI，RealMedia，ASF（采用MPEG-4标准）

多媒体数据中存在多个冗余：空间冗余，时间冗余，视觉冗余，信息熵冗余，结构冗余，知识冗余

压缩技术包括有损压缩和无损压缩。有损压缩（MP3，JPEG）无法还原，无损压缩是可以还原的。

06_1_网络基础知识_网络相关基础概念

考试大纲需要掌握数据通信与网络通信的知识点：

考点1 网络相关基础概念

考点2 OSI模型

考点3 TCP/IP协议族

考点4 IP地址的划分及子网划分

考点5 常见网络应用

网络的功能包括：数据通信，资源共享，负载均衡，高可靠性

网络的分类：局域网（范围1km以内，传输快）、城域网、广域网

网络的拓扑结构：总线型结构，星型结构，环形结构，树形结构，网状结构（分布式结构）

总线型结构：优点是扩充性能好，可靠性高，廉价，安装方便；缺点是负载重时，线路利用率低。

星型结构：优点是维护方便，网络延迟低；缺点是线路利用率低，中央单元符合重

环形结构：优点是路径控制简单，可靠性高；缺点是扩充性差

树形结构和总线型结构相同

网状结构：优点是可靠性高，资源共享方便，响应速度快；缺点是硬件成本高，管理复杂

06_2_OSI模型

OSI模型层次结构

06_3_TCPIP协议族

TCP/IP分层模型：进程/应用层，主机-主机层，网络互联层，网络接口层（层次顺序