江苏省计算机三级偏软知识点

1江苏省计算机三级偏软知识点(2010秋)1.1计算机的发展计算机由五个基本部件组成－－运算器、控制器、存储器、输入设备及输出设备。1.3带符号数的表示方法结论：（1）当X为正数时，X原＝X补＝X反；（2）当X为负数时，X原的符号位为1,数值位与真值中的数值位相同，X反的符号仍为1,数值位由X原按位取反，而X补则等于X原除符号位外求反加1,即X补＝X反＋1。（3）对于+0和-0其表示方法为：[+0]原＝000...0[-0]原＝100...0[+0]补=[-0]补=000...0[+0]反＝000...0[-0]反＝111...1理解：（任何）0表示‘+’；1表示‘-’反码、补码都是对于数值位来说。字长为n：原码表示范围：-2（n+1）+1～2（n-1）-1补码表示范围：-2（n+1）～2（n-1）-1汉字编码（GB2312-80）国标码＝区位码＋2020H内码＝国标码＋8080H1.6算术运算和逻辑运算在采用原码时符号位不能参加运算而在采用补码时，数的符号位可以参加运算。逻辑运算的特点是按对应位进行，对其他位无影响，因此不存在算术运算中的进位、错位及溢出等问题。逻辑非逻辑和逻辑异或（不同为1,相同为0）1.7微型计算机系统的基本组成硬件系统：微处理器（CPU）、存储器（ROM、RAM）、I/O接口、总线、电源的、I/O设备总线结构：数据总线、地址总线、控制总线等三部分。数据总线的特点是双向、三态，地址总线的特点是单向、三态，而控制总线有单向、双向，三态，二态等不同情况，是其中较为复杂、灵活，功能又最强的一类总线压缩BCD码（8421码）规格化数-9.6252.1软件及其发展系统包括硬件和软件。计算机系统的硬件是计算机系统中使用的所有物理设备的总称。计算机系统的软件是计算机系统中所有计算机程序以及开发、使用、维护程序所需的所有文档与数据的总称。目前常用的三种软件开发技术：1.结构化方法；2.快速原型法；3.面向对象方法。信息处理是计算机系统的基本功能，包括四种方式：数据处理、信息处理和智能处理。2.2算法及其描述算法具有的特性：1.有穷性；2.确定性；3.可行性；4.输入；5.输出。在算法正确的前提下，评价一外算法的标准是：时间量度和空间量度。一个好的算法应具备的条件有正确性、可读性、健壮性、高效性。2.3操作系统的概念2WINDOWS发展历程和技术特征：1.01平面窗口2.0重叠窗口，动态数据交换3.0支持扩展内存，支持多任务3.1对象链接和嵌入，多应用集成3.2中文版95独立操作系统，开始支持设备的即插即用98提供InternetExplorer上网软件2000加入WINDOWSNT多环境方式操作系统管理的硬件资源可分为处理机管理、存储管理、设备管理、文件管理和用户界面。2.4编译程序和解释程序的概念编译程序可以划分为五个阶段：词法分析、语法分析、中间代码优化和目标代码生成。其中词法分析、语法分析和目标代码生成是必需的阶段。解释程序与编译程序的主要区别在于解释程序不生成目标程序。编译程序不需内存，而解释程序必需内存，且比较慢。把汇编语言源程序转换为目标程序，要经过汇编过程。编译程序出现在计算机时期是：第二2.5数据库系统、汉字处理和应用软件的概念数据管理技术的发展大致经历了人工管理、文件系统、数据库系统等三个阶段。在汉字处理系统中汉字库用于汉字的显示和打印。在使用不同的输入法输入同一汉字时它们的内码和交换码是一致的。2.6-7网络的概念/多媒知识计算机网络经历了四个时代：面向终端的计算机通信网（终端网）；以通信子网为中心的计算机网络（分组交换网）；以体系结构为基础的计算机网络；宽带综合业务数字计算机网络的基本功能包括：1.数据通信；2.资源共享；3.负荷均衡和分布处理。TCP/IP协议:TCP称为传输控制协议，它是信息在网上正确传输的保证；IP称为网际协议，负责将信息从一处传送到另一处。多媒体的5种类型:1.感觉媒体；2.表示媒体；3.显示媒体；4.存储媒体；5.传输媒体。2.8数据、数据元素和数据结构数据是能被计算机识别、存储和处理的符号集合。数据元素是数据的基本单位。数据元素可能由若干个数据项组成，数据项是数据和不可分割的最小单位。数据结构包括三方面的内容：逻辑结构，存储结构和对数据进行的运算。1)逻辑结构通常有4类结构：集合；纯属结构；树形结构；图或网状结构。2)存储结构4种基本存储方式：顺序方式；链接方式；索引方式；散列方式。3)数据的运算基本的运算主要有：插入；删除；更新；查找；排序。在数据结构中与所使用的计算机无关的是数据的逻辑结构。对于存储同样一组数据元素而言，顺序结构占用整块空间而链接结构不要求整块空间。顺序结构中，存储空间必须事先定义，在运算过程中难以扩充；链接结构中，元素之间通过指针链接，空间易于扩充。2.9线性表线性表是由n个具有相同特性的数据元素组成的线性序列。线性表中的数据元素可以是各种各样的，但同一线性表中的元素必定具有相同的特性。线性表可采用顺序存储和链接存储。顺序存储是在一片连续的单元中连续进行存储，把3逻辑上相邻的数据元素存储在物理上相邻的存储单元里。链接存储是在每个结点中包括指针域，用指针来体现数据元素之间的逻辑关系。线性表的逻辑结构是线性结构，也就是说数据元素之间是线性关系。线性表的顺序存储结构是一种随机存取的存储结构，可以用一维数据来描述。2.10-11栈、队列栈是一个运算操作限制在同一端进行的线性结构，栈中元素的进出是按后进先出的原则进行的，不能随机存取。尾端称为栈顶，另一端称为栈底。队列是先进先出原则。2.12数组的概念及其存储结构数组是一种随机存取的结构，一般对数组不作插入或删除运算。数组的存储结构是顺序方式存储结构。常用的存储方式有两种：一种以行序为主序的存储方式；一种以列序为主序的存储方式。稀疏矩阵常用的稀疏矩阵压缩存储有顺序存储方式的三元组表、链接存储方式的十字链表等2.13线性链表链接存储方式的特点是：1.存储空间可以是连续的，也可以是不连续的，存储空间分配灵活，用完收回，易于扩充；2.进行插入、删除等运算时，不需要移动其它结点。2.14链栈、链队列和双向链表链栈的入栈、出栈运算都是在栈顶进行的，栈顶指针为空是链栈为空的判别条件。链队列的入队、出队运算通过队尾指针、队头指针进行，队头指针为空是链队列空的判别条件。2.15-16树/二叉树二叉树的基本性质包括：1.二叉树的第i层上至多有2i-1（i=1）个结点；2.深度为k的二叉树中至多有2k－1（k=1）个结点；3.在任意一棵二叉树中，若有终端结点数为n0，度为2的结点数为n2,则no=n2+1.二叉树是非线性结构，通常采用链式存储结构。表示二叉树的结点需要三个域：数据域和左、右指针域。所谓二叉树的遍历，就是以一定的规律访问二叉树的每个结点，使每个结点均被访问一次且仅访问一次的过程。限定先左后右的次序，只有3种方式:DLRLDRLRD(先序后遍历、中序遍历、后序遍历)。一个结点的二叉树的度为0.在树形结构中，二叉树的存储空间利用率最高。链式存储结构的二叉树中，结点数越多，空指针数就越多。（空指针数＝结点数＋1）采用链式存储结构的二叉树，结点之间的关系通过指针表示。二叉树顺序存储结构中，可能有空结点，没有空指针。二叉树不是树的特殊形式。二叉树排序树的平均检索长度与对半查找为同一数量级，即O(log2n)2.17图图是网状关系的数据结构，是较为复杂的结构形式。在线性表中，数据元素之间是线性关系，每个数据元素只有一个前驱、一个后继；在树中，数据元素之间是层次关系，每一层上的数据元素可以和下一层中零个或多个元素相关，但只能和上一层中的一个元素相关；在图中，数据元素之间的关系是可以任意的，任意两个元素之间都可能相关。4图的存储：1）邻接矩阵；2）邻接表。图的遍历通常采用的遍历方法有两种：深度优先搜索和广度优先搜索。由n个顶点组成的无向连通图最多可以有n(n-1)/2条边。由n个顶点组成的有向图的最多弧的数目为n(n-1)条弧。2.18-19线性查找、对半查找和分块查找/散列查找线性查找从一端逐个向另一端对比查找对半查找与中间元素比较，是适合于对有序表进行查找的方法。分块查找散列函数常用的几种：1）直接定址法；2）除留余数法；3）平方取中法；4）折叠法;５）数字分析法。冲突的处理方法：1）开放定址法；2）链地址法（拉链法）；３）再散列法。与其它查找方法相比，散列查找法的特点是：由关键字计算元素的存储地址后，可再进行关键字的比较，进行查找。2.20-21选择排序、插入排序和冒泡排序；快速排序和归并排序选择排序选关键字最小的靠左，不稳定。比较次数与序列的初始状态无关，次数为n(n-1)/2,复杂度为O（n2）插入排序1）直接插入排序；2）对半插入排序。是稳定的。冒泡排序各种方法的运算特点：排序方法运算特点选择选择－交换插入移动－插入冒泡两两交换快速交换－分区快速排序不稳定归并排序稳定3.1操作系统及其分类从作业处理方式和系统功能特征来看，操作系统可分为3种类型：批处理系统、分时系统、实时系统。又出现了几种新型的操作系统：微机操作系统、网络操作系统、分布式操作系统。操作系统具有的４个基本特征：并发性、共享性、虚拟性、不确定性。操作系统的５大功能：进程管理、存储器管理、设备管理、文件管理、作业管理。从单道批处理系统到多道批处理系统，其必要的硬件条件是：中断技术和直接存储器访问（DMA）。操作系统是程序的集合；分时系统。的响应时间与进程执行时间长短无关。中的I/O设备不是分时运行的；实时系统的主要特点就是能够及时响应外部的信号请求并在规定的时间内完成处理，以保证被控制对象的工作正确可靠。3.2处理机管理及进程控制与调度若多个进程同时在一台计算机上运行，就称作程序的并发执行。进程是可并发执行的具有一定功能的程序段在给定的数据空间上的一次执行过程。进程具有五大特征：动态性；并发性；独立性；异步性；结构性。进程的基本状态：就绪状态；执行状态；等待状态。进程控制块是进程存在的唯一标志。5与硬件紧密相关的部分称作操作系统的内核。内核中通常包括中断处理、进程管理、资源管理中的基本操作。进程调度：优先级数调度算法；时间片轮转法；多级反馈队列调度方法分时操作系统一般用的进程调度方式是：时间片轮。3.3进程同步与通信死锁产生的4个必要条件：1）互斥条件；2）正在作用的资源不可剥夺；3）请求和保持；4）环路等待。不同进程所执行的程序代码可以不同；进程同步是指某些进程在逻辑上的相互制约关系；有序资源分配法能破坏死锁4个必要条件中的环路等待条件，因此可以预防死锁的发生。在操作系统中，P、V操作是一种低级进程通信原语。用P、V操作管理临界区时，任何一个进程在进入临界区之前应调用P操作，在退出临界区时应调用V操作。临界资源：互斥方式工作在P、V操作中，信号S的物理意义是当信号量S值大于零时表示可用资源的数目，当信号量S值小于零时，其绝对值为因请求该资源而被阻塞的进程数目。3.4作业及其管理作业的状态：进入、后备、运行、完成。最有利于提高系统吞吐量的作业调度算法是：短作业优先。计算型作业的优先权通常应低于I/O型作业的优先权。作业控制块（JCB）是作业存在的唯一标志。系统级安全管理主要两个措施：一是注册二是登入3.5常规的存储管理方法存储管理主要是对主存储器（即内存）的管理。存储管理主要有以下几个方面：1）内存分配；2）地址转换；3）内存保护；4）内存扩充。多用户系统的存储器管理——分区式分配根据内存分区方式的不同，分区式分配又可分成固定式分区、可变式分区、可重定位分区。固定式分区分配会产生用户作业占用区内的存储碎片；可变式分区分配减少了碎片，提高了主存利用率，但仍未避免碎片问题；可重定位分区觖了这个问题。分区的存储保护常采用界限寄存器和存储保护键两种方法。采用界限寄存器方法实现存储保护时，基址寄存器和限长寄存器分别存放作业的起始地址及作业的地址空间长度。地址重定位是将目标程序中的逻辑地址转换成主存空间的物理地址；把作业装入内存并随机进行地址变换的方