江苏省计算机三级偏软知识点第一章计算机基础1.1十进制和二进制的转化整数部分除2按位取余.小数部分乘2取整数.1.2带符号数的表示方法正数:X原=X补=X反负数:1.3二进制信息编码汉子编码:GB2312-80国标码＝区位码＋2020H 内码＝国标码＋8080H1.4 算术运算和逻辑运算1.5 微型计算机系统的基本组成硬件系统：微处理器（CPU）、主存储器、辅助存储器、输入设备、输出设备。

总线结构：数据总线、地址总线、控制总线等三部分。

数据总线的特点是双向、三态，地址总线的特点是单向、三态，而控制总线有单向、双向，三态，二态等不同情况，是其中较为复杂、灵活，功能又最强的一类总线压缩BCD码总线标准为：ISA、EISA、VESA、PCI第二章软件概念与数据结构2.1软件及其发展计算机系统的软件是计算机系统中所有计算机程序以及开发、使用、维护程序所需的所有文档与数据的总称。

目前常用的三种软件开发技术：1.结构化方法；2.快速原型法；3.面向对象方法。

2.2算法及其描述算法具有的特性：1.有穷性；2.确定性；3.可行性；4.输入；5.输出。

在算法效率的度量：时间复杂度和空间空间复杂度。

2.3 操作系统的概念操作系统的形成与发展：人工操作、早期批处理系统、多道程序系统、操作系统、高性能系统。

多道程序系统标志着操作系统的形成。

多任务操作系统中影响较大的有：UNIX、WINDOWS（95、98、NT、2000、xp、2003）新型操作系统：网络操作系统、分布式操作系统、多机系统、多媒体操作系统。

操作系统的结构：模块组合结构、层次结构、虚拟机结构、客户/服务器结构。

2.4 编译程序和解释程序解释程序与编译程序的主要区别在于解释程序不生成目标程序。

编译程序不需内存，而解释程序必需内存，且比较慢。

2.5 数据库系统、汉字处理和应用软件的概念数据管理技术的发展:经历了人工管理阶段、文件系统阶段、数据库系统阶段。

数据库管理系统（DBMS）：位于用户和操作系统之间的一个数据管理软件，具有数据定义、数据操纵、数据库的建立和维护、数据库运行管理和数据通信接口等功能。

数据库系统：计算机软件硬件、数据库、数据库管理系统、应用系统、数据库管理员和终端用户数据库管理系统分为：层次模型、网状模型、关系模型。

2.6汉字处理基础知识汉字编码：GB2312—GBK—GB180302.7应用软件2.8计算机网络基础计算机网络经历了四个时代：面向终端的计算机通信网（终端网）；以通信子网为中心的计算机网络（分组交换网）；以体系结构为基础的计算机网络；新一代计算机网络。

计算机网络的基本功能包括：1.数据通信；2.资源共享；3.负荷均衡和分布处4.计算机冗余。

TCP/IP协议:TCP称为传输控制协议，它是信息在网上正确传输的保证；IP称为网际协议，负责将信息从一处传送到另一处。

2.9多媒体基础知识多媒体的5 种类型:1.感觉媒体；2.表示媒体；3.显示媒体；4.存储媒体；5.传输媒体。

视频：电视信号使用YUV，Y亮度，UV色度。

信息压缩：有损压缩、无损压缩。

JPEG静态图像压缩编码标准、MPEG动态图像压缩编码标准。

2.10 数据、数据元素和数据结构数据是能被计算机识别、存储和处理的符号集合。

数据元素是数据的基本单位。

数据元素可能由若干个数据项组成，数据项是数据和不可分割的最小单位。

数据结构包括三方面的内容：逻辑结构和存储结构。

1) 逻辑结构通常有4类结构：集合；线性结构：1:1；树形结构：1：n；图或网状结构n:n。

2) 存储结构4种基本存储方式：顺序方式（逻辑相邻-存储相邻）；链接方式（指针表示）；索引方式（索引表）；散列方式（关键字）。

3) 数据的运算基本的运算主要有：插入；删除；更新；查找；排序。

分为加工型和引用型。

在数据结构中与所使用的计算机无关的是数据的逻辑结构。

2.11线性表线性表：由n个具有相同特性的数据元素组成的线性序列。

线性表特点：线性表中的数据元素可以是各种各样的，但同一线性表中的元素必定具有相同的特性。

线性表的运算：插入、删除……2.12 栈栈是限定仅在表尾进行插入删除的线性表，尾端称为栈顶，另一端称为栈底。

栈的特点：先进后出。

栈的顺序存储结构：用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。

同时设指针top指示栈顶位置。

栈的基本运算：置空栈、进栈、出栈、读取栈顶元素、判栈空。

2.13队列队列：队列是先进先出的线性表。

允许在队尾插入、允许在队头删除。

队列的基本运算：置空队、入队、出队、判空队、判队满。

2.14 数组数组是一种随机存取的结构，一般对数组不作插入或删除运算。

数组的存储结构是顺序方式存储结构。

常用的存储方式有两种：一种以行序为主序的存储方式；一种以列序为主序的存储方式。

稀疏矩阵常用的稀疏矩阵压缩存储有顺序存储方式的三元组表、链接存储方式的十字链表等2.15线性链表链接存储方式的特点是：1.存储空间可以是连续的，也可以是不连续的，存储空间分配灵活，用完收回，易于扩充；2.有数据域和指针域。

线性链表的运算：插入运算、删除运算2.16链栈、链队列和双向链表链栈的入栈、出栈运算都是在栈顶进行的，栈顶指针为空是链栈为空的判别条件。

链队列的入队、出队运算通过队尾指针、队头指针进行，队头指针为空是链队列空的判别条件。

2.17树、树：具有相同特性的n个节点的有限集最上面的为根节点，2.18二叉树元素：根结点、左子树、右子树二叉树的基本性质包括：1. 二叉树的第i层上至多有2^(i-1)（i>=1）个结点；2. 深度为k的二叉树中至多有2^k－1（k>=1）个结点；3. 在任意一棵二叉树中，若有终端结点数为n0，度为2 的结点数为n2,则no=n2+1.4.具有n个节点的完全二叉树深度为log2（n）+1；二叉树是非线性结构，通常采用链式存储结构。

表示二叉树的结点需要三个域：数据域和左、右指针域。

所谓二叉树的遍历，就是以一定的规律访问二叉树的每个结点，使每个结点均被访问一次且仅访问一次的过程。

限定先左后右的次序，只有3种方式:DLR LDR LRD (先序后遍历、中序遍历、后序遍历)。

一个结点的二叉树的度为0.在树形结构中，二叉树的存储空间利用率最高。

链式存储结构的二叉树中，结点数越多，空指针数就越多。

（空指针数＝结点数＋1）采用链式存储结构的二叉树，结点之间的关系通过指针表示。

二叉树顺序存储结构中，可能有空结点，没有空指针。

二叉树不是树的特殊形式。

二叉树排序树的平均检索长度与对半查找为同一数量级，即O(log2n)2.19图图是网状关系的数据结构，是较为复杂的结构形式。

在线性表中，数据元素之间是线性关系，每个数据元素只有一个前驱、一个后继；在树中，数据元素之间是层次关系，每一层上的数据元素可以和下一层中零个或多个元素相关，但只能和上一层中的一个元素相关；在图中，数据元素之间的关系是可以任意的，任意两个元素之间都可能相关。

图的存储：1）邻接矩阵；2）邻接表。

图的遍历通常采用的遍历方法有两种：深度优先搜索和广度优先搜索。

由n个顶点组成的无向连通图最多可以有n(n-1)/2条边。

由n个顶点组成的有向图的最多弧的数目为n(n-1)条弧。

2.20线性查找、对半查找和分块查找/散列查找线性查找从一端逐个向另一端对比查找对半查找与中间元素比较，是适合于对有序表进行查找的方法。

分块查找散列函数常用的几种：1）直接定址法；2）除留余数法；3）平方取中法；4）折叠法;５）数字分析法。

冲突的处理方法：1）开放定址法；2）链地址法（拉链法）；３）再散列法。

与其它查找方法相比，散列查找法的特点是：由关键字计算元素的存储地址后，可再进行关键字的比较，进行查找。

2.20-21 选择排序、插入排序和冒泡排序；快速排序和归并排序选择排序选关键字最小的靠左，不稳定。

比较次数与序列的初始状态无关，次数为n(n-1)/2,复杂度为O（n2）插入排序1）直接插入排序；2）对半插入排序。

是稳定的。

冒泡排序各种方法的运算特点：排序方法运算特点选择选择－交换插入移动－插入冒泡两两交换快速交换－分区快速排序不稳定归并排序稳定第三章操作系统3.1操作系统及其分类从作业处理方式和系统功能特征来看，操作系统可分为3种类型：批处理系统、分时系统、实时系统。

又出现了几种新型的操作系统：微机操作系统、网络操作系统、分布式操作系统。

操作系统的作用：有效的管理计算机系统的软硬件资源、提高资源利用率；作为用户和计算机硬件之间的接口，提供用户与计算机系统之间的界面；扩充计算机的功能，为用户提供虚拟机。

操作系统具有的４个基本特征：并发性、共享性、虚拟性、不确定性。

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

3.2进程管理进程的概念：多个程序在同一台计算机上运行进程的特点：动态性、并发性、独立性、异步性、结构性。

进程的基本状态与转换：阻塞状态、运行状态、就绪状态进程控制块：（PCB）进程标识符信息、处理器状态信息、进程调度信息、进程控制信息。

进程控制：创建进程、撤销进程、阻塞进程、唤醒进程、挂起进程、激活进程。

线程：内核级线程、用户级线程、混合式线程。

处理器调度：高级调度（作业调度）、中级调度（对换调度）、低级调度（线程/进程调度）：进程调度分为非剥夺式和剥夺式（能被抢占）。

调度算法：先来先服务算法（FCFS）、短作业优先算法、时间片轮转算法、优先级算法、多反馈队列算法。

3.3进程同步与通信进程同步：进程互斥：争夺资源临界资源：空闲让进、忙则等待、有限等待、让权等待。

进程通信：低级通信原语：开锁、关锁、P操作、V操作高级通信原语：共享存储区、消息传递系统、管道通信。

死锁产生的4个必要条件：1）互斥条件；2）不可剥夺；3）请求和保持条件；4）环路等待。

防死锁：预先静态分配法、有序资源分配法（银行家算法）。

死锁的解除：撤销进程法、剥夺资源法。

3.4存储管理：存储管理：主要指对主存储器的管理。

存储层次结构：寄存器—高速缓存—主存—外存程序的装入：编译—链接—装入地址重定位：将逻辑地址变换为内存空间的物理地址静态重定位：动态重定位：单一连续分配：内存被分为系统区和用户区。

分区分配：固定分区、可变分区、动态重定位分区、覆盖。

分页存储管理方式：将一个进程逻辑地址空间分成若干大小相等的页，称之为页面分段存储管理方式：作业的地址空间由若干逻辑分段组成分段和分页的区别：采用离散分配方式、地址变换机构也相似页是信息是物理单位、段是信息的逻辑单位。

页的大小固定而段的长度不固定，分页的优点在于管理内存空间上，分段在于管理地址空间上。

3.5虚拟存储管理程序局部性原理：时间局部性、空间局部性。

虚拟存储器：比实际内存大的多。