学习攻略

真题

真题，建议从 10 年开始做，10 - 15 年的真题练习用，16 - 18 年真题自己卡时间模拟考

程序员考试重点汇总

计算机系统基础知识

进制之间的转化

==表示符：八进制还可以用Q表示==

==ASCII：美国信息交换标准代码。一般使用7位二进制数来表示字母、数字、标点符号及部分特殊控制字符。==

十进制和其他进制之间的转换

==除基取余法：从下往上==

==乘基取整法：从上往下==

==不足x位时，小数前在高位加0，小数后在末尾加0==

==1024 = 2^10^==

奇校验：整个校验码（有效信息位和校验位）中“1”的个数为奇数。

偶校验：整个校验码（有效信息位和校验位）中“1”的个数为偶数。

奇偶校验，可检查1位的错误，不可纠错。

原、反、补、移码运算和逻辑运算

原码：将数据用二进制形式表示，最高位为符号位, 正数为 0, 负数为 1。

反码：正数的反码是其本身；负数的反码是在其原码的基础上, 符号位不变，其余各位取反。

补码：正数的补码是其本身；负数的补码是在其原码的基础上, 符号位不变, 在反码的基础上+1。

移码：将补码的符号位取反得相应的移码。

注意：==在补码和移码表示中，0 有唯一的编码，补码中+0 和-0 均为 0000 0000（八位二进制表示下）==。

多数计算机都采用补码进行加减运算，其符号位和数值位一样参与运算，无须做特殊处理。

在 n 位二进制表示下：

原码、反码表示的数据范围为：-（2^n-1^-1）～+（2^n-1^-1）

补码、移码表示的数据范围为：-2^n-1^～+（2^n-1^-1）

==补码中，用 1000 0000 表示-128。==

浮点数

两浮点数进行运算的过程

运算过程：

对阶 > 尾数计算 > 结果格式化

对阶时，小数向大数看齐，对阶是通过==较小数的尾数右移（小数点左移）==实现的

结果格式化 01、10开头（0.5~1之间）

逻辑运算

校验码

1、奇偶校验码

由若干位有效信息（如一个字节），再加上一个二进制位（校验位）组成校验码。

奇校验：整个校验码（有效信息位和校验位）中“1”的个数为奇数。

偶校验：整个校验码（有效信息位和校验位）中“1”的个数为偶数。

奇偶校验，可检查 1 位的错误，不可纠错。

==奇偶校验，可检查奇数位的错误，不可纠错。如果偶数位发生错误，则发现不了。==

2、海明码

在数据位之间插入 K 个校验位，通过扩大码距来实现检错和纠错。

3、循环冗余校验码（n,k）码

信息码占 k 位，校验码占 n-k 位，校验码位数越长，校验能力越强。采用了模二运算。

计算机系统与中央处理器构成

CPU 指令执行过程（流水线技术）

计算机每执行一条指令都可分为三个阶段：取指令—分析指令—执行指令。

取指令：根据程序计数器 PC 中的值从程序存储器读出现行指令，送到指令寄存器 IR。

分析指令：将指令寄存器中的指令操作码取出后进行译码，分析其指令性质。

执行指令：控制、指挥、协调整个计算机系统的各个子系统, 相互配合、有条不紊的完成各项任务。

执行程序的过程实际上就是逐条指令地重复上述操作过程，直至遇到停机指令可循环等待指令。

运算器和控制器的组成

运算器的构成：

i. 算术逻辑单元 ALU：数据的算术运算和逻辑运算

ii. 累加寄存器 AC（数据寄存器）：通用寄存器，为 ALU 提供一个工作区，用在暂存数据

iii. 数据缓冲寄存器 DR：写内存时，暂存指令或数据

iv. 状态条件寄存器 PSW：存状态标志与控制标志（争议：也有将其归为控制器的）

控制器的构成：

i. 程序计数器 PC：存储下一条要执行指令的地址

ii. 指令寄存器 IR：存储正在执行的指令

iii. 指令译码器 ID：对指令中的操作码字段进行分析解释

iv. 时序部件：提供时序控制信号

指令寻址和存储器

指令系统

立即寻址方式：操作数直接在指令中，速度快，灵活性差

直接寻址方式：指令中存放的是操作数的地址

间接寻址方式：指令中存放了一个地址，这个地址对应的内容是操作数的地址

寄存器寻址方式：寄存器存放操作数

寄存器间接寻址方式：寄存器内存放的是操作数的地址

回收站：外存

剪切板：内存

容量的换算

位（b/bit）：存放一位二进制数

字节（B/Byte）：8 个二进制位为一个字节

1B=8b

1KB=1024B

1MB=1024KB

1GB=1024MB

1TB=1024GB

1PB=1024TB

1EB=1024PB

1ZB=1024EB

1YB=1024ZB

内存编址

内存编址：存储器由一块块的空间（存储单元）组成，为了方便寻找到每一块空间，我们需要对每一个空间进行标识，即用地址（唯一的编号）来标识内存每个单元内存容量=每个芯片容量*芯片个数

每个芯片的容量=一个地址代表的容量*编址总数

总线系统

总线分类：芯片内总线、元件级总线、系统总线（ ISA 总线、EISA 总线、PCI 总线等）和外总线（RS-232C、SCSI 总线、USB、IEEE-1394 等）

系统总线的分类：地址总线、数据总线和控制总线

数据总线：决定 CPU 和外界的数据传送速度。每条传输线一次只能传输 1 位二进制数据。“64 位的CPU”是指 CPU 的数据总线的宽度是 64 位。字长取决于数据总线的宽度。
地址总线：CPU 是通过地址总线来指定存储单元的，其决定了 CPU 所能访问的最大内存空间的大小。例如: 若计算机的地址总线的宽度为 32 位，则最多允许直接访问 4GB 的物理空间，所以最多支持 4G内存。
控制总线：对外部器件进行控制，其宽度决定了 CPU 对外部器件的控制能力。

设有一个64K×32位的存储器(每个存储单元为32位)，其存储单元的地址宽度为64K=2^16^，总共16位。这里32位可以说是每个存储单元为32位，也可以理解为数据总线宽度是32。

系统总线的性能指标：

带宽：单位时间上传送的数据量，即每秒钟传送的最大稳态数据传输率

位宽：能同时传送的二进制数据的位数，或数据总线的位数，32 位、64 位等

CPU 与外设数据交换方式

CPU 与外设之间进行交换数据的方式：

立即程序传送方式：I/O 接口总是准备接收来自主机的数据或向主机输入数据，无需查看接口的状态

程序查询方式：CPU 通过查询执行程序查询外设的状态进行判断是否准备好

中断方式：I/O 接口准备好后会发送中断信号通知 CPU，CPU 确认后保存正在执行程序现场转而执行 I/O 中断服务程序

直接存储器存取 DMA 方式：数据的传送由 DMA 控制器进行控制，不需要 CPU 的干涉，只能进行简单的数据传送操作

通道控制方式：CPU 按约定格式准备数据和命令，然后启动通道，通道执行相应的通道程序完成所要求的操作

计算机的性能指标

计算机系统的主要性能指标：

响应时间：从用户输入完整的操作命令到系统开始显示应答信息为止的这段时间

吞吐量：单位时间内系统完成的工作量

周转时间：用户提交作业到执行后该作业返回给用户所需的时间

时钟频率：即 CPU 主频，直接反映了机器的速度，通常主频越高其速度越快，主频=外频×倍频

平均运算速度：指每秒钟所能执行的指令条数，用“百万条指令／秒”（MIPS）来描述

多媒体基础知识

声音信号数字化过程：采样、量化和编码

图像分辨率：一幅图像的像素密度，每英寸多少点（dpi）表示图像大小；200dpi扫描一幅2x2.5英寸的照片，则可以得到400x500像素点的图像。

像素深度：存储每个像素所用的二进制数，度量图像的色彩分辨率，图像深度为b位，则该图像最多的颜色数或灰度级为2^b^种

无损压缩：利用数据的统计冗余进行压缩，可以保证在数据压缩和还原过程中，图像信息没有损耗或失真。（RAR、ZIP、TIFF、BMP、GIF等）

有损压缩：用于重构信号不一定非要与原始信号完全相同的场合，压缩比高。主要包括：DVD、VCD、MP3 、JPEG、 MPEG 、RMVB、 WMA 、WMV等）

媒体的种类

1) 多媒体的概念及分类

传播信息的载体，如语言、文字、图像、视频、音频等；

存贮信息的载体，如 ROM、RAM、磁带、磁盘、光盘等。

多媒体的分类：

感觉媒体：直接用于人的感觉器官，使人产生直接感觉的媒体

表示媒体：传输感觉媒体的中介媒体，用于数据交换的编码

表现媒体：进行信息输入输出的媒体

存储媒体：用于存储表示媒体的物理介质

传输媒体：传输表示媒体的物理介质

交换媒体包括存储媒体和传输媒体。

多媒体编辑软件

硬件系统：多媒体主机、多媒体输入设备、多媒体输出设备、多媒体存储设备、多媒体板卡、多媒体操作控制设备

软件系统：多媒体操作系统、多媒体创作工具软件、多媒体素材编辑软件、多媒体应用软件

多媒体素材编辑软件：

文本工具：WPS、Notebook（记事本）、Writer（写字板）、word 和 OCR

图形/图像工具：Photoshop、Illustrator、PhotoDeluxe、PageMaker、Coredraw、AutoCAD、Freehand、3ds Max、Screen Thief等

动画工具：GIF Construction Set、Xara 3D

视频工具：Media Studio Pro、Premiere

音频工具：CoolEditPro、GoldWave、Cake Walk Pro Audio

播放工具：Media Player、ACDSee

音频

声音信号的数字化过程

采样（采样频率，与采样周期成反比）

量化（量化精度(量化分辨率):样本用二进制表示,位数多少反映精度）

编码（按照一定格式进行数据编码及组织成文件）

常见音频文件格式

（.wav）：微软公司发布的音频文件格式, Windows 系统使用的标准音频文件格式。记录音乐的模拟信号的采样数值。质量高，数据量大。

（.mod）：乐谱和乐曲使用的各种音色样本

（.mp3）：最流行的音频文件格式

（.ra）：网络上的音频格式，流媒体技术，强大压缩比和极小失真

（.mid）：非波形采样点音乐格式，工业标准，文件非常小

（.voc）：Create 公司发布的波形音频文件格式

（.snd）：数字声音文件格式，支持压缩

（.aif）：APPLE 计算机上的音频格式

（.au）：Unix 系统中的数字文件格式

图形和图像

图形/图像区别

图形：矢量表示，用数学的方式来描述一幅图，放大、缩小、扭曲等变换后不会损失画面细节。（用于线框型图画、工程制图和美术字等）

图像：像素点表示，用若干二进制位来指定像素的颜色、亮度和属性。放大后会失真。存储空间大，需进行压缩。

图形图像主要性能指标

显示分辨率：显示屏上能够显示的像素数目，1024x768 表示显示屏分为 768 行（垂直分辨率），每行（水平分辨率）显示 1024 像素。

图像分辨率：一幅图像的像素密度，**每英寸多少点（dpi）**表示图像大小；200dpi 扫描一幅 2x2.5 英寸的照片，则可以得到400x500 像素点的图像。

像素深度：存储每个像素所用的二进制数，度量图像的色彩分辨率，图像深度为 b 位，则该图像最多的颜色数或灰度级为 2^b^ 种

常见图像文件格式

（.bmp）：windows 标准位图文件格式

（.gif）：用于网络传输，数据块为单位传输信息，采用无损压缩算法

（.tif）：扫描仪和桌面出版系统中较为普及

（.pcx）：PC 画笔的图像文件格式

（.png）：作为 GIF 替代品

（.jpg）：有损压缩，压缩比例高，适合于处理大量图像的场合

（.wmf）：只在 windows 中使用，保存函数调用信息

jpeg：静态图像压缩标准

动画和视频

常见视频文件格式

（.gif）：用于网络传输

（.avi）：微软公司发布的视频文件格式（AVI 文件）

（.mov/.qt）：Apple 公司发布的视频文件格式，较小存储空间，开放性（Quick Time 文件）

（.rm/.rmvb）：Real Networks 公司格式，影像实时传输与播放（RealVideo 文件）

（.mpeg/.mpg/.dat/.mp4）：运动图像压缩标准，压缩效率高，质量好，兼容性好

（.fli/.foc）:Autodesk 公司出品答得彩色动画文件格式（Flic 文件）

多媒体相关计算

有损&无损压缩格式

无损压缩：利用数据的统计冗余进行压缩，可以保证在数据压缩和还原过程中，图像信息没有损耗或失真。（RAR、ZIP、TIFF、BMP、GIF 等）

有损压缩：用于重构信号不一定非要与原始信号完全相同的场合，压缩比高。主要包括：DVD、VCD、MP3 、JPEG、 MPEG 、RMVB、 WMA 、WMV 等）

操作系统

信号量S：整型变量，并根据控制对象进行赋值。S≧0表示资源可用数，S<0表示排队进程数。

互斥模型：多进程共享一台打印机。

同步模型：单缓冲区生产者、消费者问题；多缓冲区生产者、消费者问题

操作系统概述

操作系统的基本概念

操作系统：组织和管理软件、硬件资源以及计算机系统中的工作流程，并控制程序的执行，向用户提供接口。

特征：并发性、共享性、虚拟性和不确定性。

功能：进程管理、存储管理、文件管理、作业管理和设备管理。

类型：批处理、分时、实时、网络、分布式、微机和嵌入式。

操作系统的五大功能

进程管理：进程控制、进程同步、进程通信、进程调度

文件管理：文件存储空间管理、目录管理、文件的读写管理、存取控制

存储管理：存储分配与回收、存储保护、地址映射（变换）、主存扩充

设备管理：对硬件设备管理，对输入输出设备的分配、启动、完成和回收

作业管理：任务、界面管理，人机交互、图形界面、语音控制、虚拟现实

操作系统的分类

批处理操作系统：单道批和多道批操作系统

分时操作系统：一个计算机系统与多个终端设备连接，特点：多路性、独立性、交互性和及时性

实时操作系统：实时控制系统和实时信息系统，交互能力要求不高，可靠性要求高

网络操作系统：方便有效共享网络资源，提供服务软件和有关协议的集合，主要的网络操作系统有：Unix、Linux 和 Windows Server 系统

分布式操作系统：任意两台计算机可以通过通信交换信息，是网络操作系统的更高级形式，具有透明性、可靠性和高性能等特性

微机操作系统：Windows：Microsoft 开发的图形用户界面、多任务、多线程操作系统和 Linux：免费使用和自由传播的类 Unix 操作系统，多用户、多任务、多线程和多 CPU 的操作系统

嵌入式操作系统：运行在智能芯片环境中，特点：微型化、可定制、实时性、可靠性、易移植性

操作系统能方便用户之间的交流（x）正确答案是网络

进程管理

进程三态模型

三态模型：哪三种状态和状态之间的转换

信号量机制

进程通信：各个进程交换信息的过程。

分类：同步（直接制约）、互斥（申请临界资源间接制约）。

信号量 S：整型变量，并根据控制对象进行赋值。S≧0 表示资源可用数，S<0 表示排队进程数。

n个资源m个进程：S的范围是 n-m ~ n

n个进程，每个进程需要m个资源

一定不会产生死锁：资源数 >= n * (m - 1) + 1

一定会产生死锁：资源数 <= m - 1

分类：公用信号量（互斥）、私用信号量（同步）

PV 机制、互斥和同步

互斥模型：多进程共享一台打印机。

同步模型：单缓冲区生产者、消费者问题；多缓冲区生产者、消费者问题

在单缓冲区生产者消费模型中：s1、s2 是同步信号量，s1 的初值为 1，s2 的初值为 0。

如果是多缓冲区生产者消费者问题，则：s1、s2 是同步信号量，s1 的初值为 n，s2 的初值为 0（n 表示缓冲区可以容纳的产品数量）。

存储管理

存储管理：目的是解决多个用户使用主存的问题。

分类：分区存储管理、分页存储管理、分段存储管理、段页式存储管理以及虚拟存储管理。

分页存储管理：用户程序的地址空间被划分成若干固定大小的区域，称为“页”，相应地，内存空间分成若干个物理块，页和块的大小相等。可将用户程序的任一页放在内存的任一块中，实现了离散分配。

分段存储管理：将用户程序地址空间分成若干个大小不等的段，每段可以定义一组相对完整的逻辑信息。存储分配时，以段为单位，段与段在内存中可以不相邻接，也实现了离散分配。作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。

段页式存储管理：用分段方法来分配和管理虚拟存储器。程序的地址空间按逻辑单位分成基本独立的段，而每一段有自己的段名，再把每段分成固定大小的若干页。

(2) 用分页方法来分配和管理实存。把整个主存分成与上述页大小相等的存储块，可装入作业的任何一页。程序对内存的调入或调出是按页进行的。

相对地址/虚地址/逻辑地址：在目标程序中，程序指令和数据的位置按照字或字节单位根据它们的相对顺序来确定，称为相对地址，一般从O开始依次进行编号。

相对地址空间通过地址再定位机构转换到绝对地址空间(物理地址空间)。

虚拟存储管理

虚拟存储器：利用外部辅存暂存主存待加载的数据，组成主存+辅存的虚拟存储结构。

虚拟存储器的最大容量是由计算机系统的地址结构和外存空间决定的。

采用虚拟存储器的目的是扩大用户的地址空间。

局限性：时间局限性、空间局限性。

实现方式：请求分页系统、请求分段系统、请求段页式系统。

页面置换算法

页面置换算法：最佳置换算法、先进先出置换算法、最近最少未使用置换算法、最近未用置换算法。

先根据所采用的方式确定淘汰的页面，然后再淘汰掉这个页面，再把缺的页面置换进去即可。

逻辑地址都是页号+页内地址

设备管理

CPU 与外设之间进行交换数据的方式：

直接程序控制：

1）立即程序传送方式：I/O 接口总是准备接收来自主机的数据或向主机输入数据，无需查看接口的状态；

2）程序查询方式：CPU 通过查询执行程序查询外设的状态进行判断是否准备好，I/O 设备不主动反馈信息；

中断方式：I/O 接口准备好后会发送中断信号通知 CPU，CPU 确认后保存正在执行程序现场转而执行 I/O 中断服务程序；

直接存储器存取 DMA 方式：数据的传送由 DMA 控制器进行控制，不需要 CPU 的干涉，只能进行简单的数据传送操作；

通道控制方式：CPU 按约定格式准备数据和命令，然后启动通道，通道执行相应的通道程序完成所要求的操作。

磁盘调度

磁盘调度：采用适当的调度算法，使各进程对磁盘的平均访问时间最小。硬/磁盘的主要技术指标：道密度、位密度、存储容量、平均存取时间、寻道时间、等待时间、数据传输率。

数据读取时间：通常由磁道搜索、扇区搜索、数据传输三个部分组成。

驱动调度：先来先服务、最短寻道时间优先、扫描算法、单向扫描调度算法。

磁盘调度算法

先来先服务算法：该算法实际上不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。有可能随时改变移动臂的方向。

最短寻找时间优先调度算法：从等待的访问者中挑选寻找时间最短的那个请求执行，而不管访问者的先后次序。这也有可能随时改变移动臂的方向。

电梯调度算法：从移动臂当前位置沿移动方向选择最近的那个柱面的访问者来执行，若该方向上无请求访问时，就改变臂的移动方向再选择。

单向扫描调度算法：不考虑访问者等待的先后次序，总是从 0 号柱面开始向里道扫描，按照各自所要访问的柱面位置的次序去选择访问者。在移动臂到达最后一个柱面后，立即快速返回到 0 号柱面，返回时不为任何的访问者提供服务，在返回到 0 号柱面后，再次进行扫描。

文件管理

文件结构

文件：具有符号名的、在逻辑上具有完整意义的一组相关信息项的集合。

目录结构：一级目录结构、二级目录结构、三级目录结构

文件路径

绝对路径：从根目录开始的路径（如：C:\username\desktop\document\ABC.docx）

相对路径：从用户当前工作目录下开始的路径（如：document\ABC.docx）

文件命名要求

文件夹命名规则：

1）最大长度为 255 个字符

2）允许使用英文字母，数字。￥ @ & +（）、下划线、空格、汉字，不允许使用？ \ * < > ： / | ”

3）在操作系统中搜索时可以用 * 匹配 0 个或多个字符，用 ? 匹配任何一个字符

文件管理

建立文件夹结构：建立适合自己的文件夹结构，注意控制文件夹结构的级数和每个文件夹中文件的个数（级数不要超过 5 级，每个文件夹的个数控制在 100 以内）

文件和文件夹命名：规范的对文件夹和文件命名方便查看和检索

数据备份 backup：对关键数据定期及时的备份，以免数据被毁造成重大损失

文件类型

文件类型和文件后缀名的对应关系

系统的安全

系统的安全：

系统级：主要任务是不允许未经核准的用户进入系统，主要措施有：注册和登录

用户级：对所有用户分类和对指定用户分配访问权，设置不同的存储权限分为超级用户、系统操作员和一般用户

文件级：通过系统管理员或文件主对文件属性的设置来控制用户对文件的访问用户对文件的访问，包含：用户访问权、目录访问权限及文件属性权限

用户权限管理

windows 中系统对用户的默认权限情况：

Administrators：管理员组，用户对计算机/域有不受限制的完全访问权。

Power Users：高级用户组可以执行除了为 Administrators 组保留的任务外的其他任何操作系统任务。

Users：普通用户组，这个组的用户无法进行有意或无意的改动。

Everyone：所有的用户，这个计算机上的所有用户都属于这个组。

Guests：来宾组，来宾组跟普通组 Users 的成员有同等访问权，但来宾账户的限制更多。

作业管理

正在执行的作业是进程。

作业调度：先来先服务、短作业优先、响应比高优先、优先级调度、均衡调度。

用户界面

用户界面（ User interface ）：计算机中实现用户与计算通信的软件、硬件部分总称，也称之为用户接口或人机界面。

用户界面设计原则：简易性、用户的语言、记忆负担最小化、一致性、利用用户的熟悉程度、从用户的观点考虑（最关键的判断点）、排列分组、安全性、人性化

程序设计语言

程序设计语言及其构成

表达式

中缀转后缀：运算顺序保持不变

后缀表达式运算过程：通过==栈==：先取出来放后面，后取出来放前面

传值和传址调用

语言处理程序

编译程序

有限自动机和正规式

数据结构和算法知识

栈是只能在一端进行插入和删除操作的线性表，其中允许插入和删除的一端叫做栈顶，另一端叫做栈底。栈是一种后进先出（LIFO）的数据结构，先入栈的元素要比后入栈的元素后出栈。故将一串数据全部入栈后再全部出栈，数据的次序将前后颠倒。栈主要应用于函数调用或中断调用过程中。

队列是一种先进先出（FIFO）的数据结构，先入队列的元素要先于后入队列的元素出队列。故一串数据无论以何种操作次序通过队列，其次序都不会发生变化。

如果对一棵有n个结点的完全二叉树的结点按层序编号则对任一结点i（1≤i≤n），有： ①如果i=1，则结点i无父结点，是二叉树的根；如果i>1，则父结点是$\lfloor i/2 \rfloor$； ② 如果2i>n，则结点i为叶子结点，无左子结点；否则，其左子结点是结点2i； ③ 如果2i+1>n，则结点i无右子叶点，否则，其右子结点是结点2i+1。向下取整