江苏省计算机一级基础知识.doc

计算机基础知识目 录一、计算机的系统及工作原理二、网络的基本知识三、计算机中有关数、编码的基本常识四、机器数与真值五、数据结构（data structure）六、排列组合七、二项式定理八、容斥原理及应用九、归纳与递推十、逻辑判断问题内 容一、计算机的系统及工作原理 1计算机系统组成 计算机系统是由硬件和软件两部分组成的。硬件是指构成计算机的电子元器件即计算机的设备；软件是指程序和有关的文档资料。 （1）计算机的主要硬件 输入设备：常见有键盘、鼠标、扫描仪等。输出设备：常见有显示器、打印机、绘图仪等。磁盘既是输入设备又是输出设备。 中央处理器：又称为CPU，它包括运算器、控制器。运算器可以进行算术运算和逻辑运算；控制器是计算机的指挥系统，它的操作过程是取指令分析指令执行指令，循环执行。 存储器：具有记忆功能的物理器件，用于存储信息。存储器分为内存和外存。内存是半导体存储器：它分为只读存储器（ROM）和随机存储器（RAM）；RAM内的数据资料停电后会丢失，而ROM中的则不会。 外存：磁性存储器软盘和硬盘；光电存储器光盘，它们可以作为永久性存储器；还有U盘（闪存）也是常用的外存设备。 存储器的两个重要技术指标：存取速度和存储容量。内存的存取速度最快（与CPU速度相匹配），软盘存取速度最慢。存储容量是指存储的信息量，它用字节（BIT）作为基本单位，1字节用 8位二进制数表示，IKB=1024B，1MB=1024KB，1GB= 1024MB （2）计算机的软件 计算机的软件主要分为系统软件和应用软件两类： 系统软件：为了使用和管理计算机的软件，主要有操作系统软件如，WINDOWS 95982000NT40，DOS 60UNIX等；WINDOWS 95982000NT40是多任务可视化图形界面。 应用软件：为了某个应用目的而编写的软件，主要有辅助教学软件、辅助设计软件、文字处理软件、工具软件以及其他的应用软件。 2计算机的工作原理 到目前为止，电子计算机的工作原理均采用冯诺依曼的存储程序，并自动完成程序的设计思想。其工作过程如下图所示： 需要注意的是：程序中的数据、指令都采用数字化编码方式，保存在存储器中；程序中的指令必须是属于这台机器的指令系统。 3计算机病毒 计算机病毒是一种程序，是人为设计的具有破坏性的程序。它往往使计算机不能正常工作。计算机病毒具有破坏性、传播性、可激发性、潜伏性、隐蔽性等特点。由于计算机病毒危害极大，需要注意隔离计算机病毒的来源，经常用杀病毒软件检查计算机系统和存储器。二、网络的基本知识1网络的定义：所谓计算机网络，就是利用通信线路和设备，把分布在不同地理位置上的多台计算机连接起来。计算机网络是现代通信技术与计算机技术相结合的产物。网络中计算机与计算机之间的通信依靠协议进行。协议是计算机收、发数据的规则。TCP/IP：用于网络的一组通讯协议。包括IP(Internet Protocol)和TCP(Transmission Control Protocol)2网络的发展计算机网络的发展过程大致可以分为三个阶段： 远程终端联机阶段：主机终端 计算机网络阶段：计算机计算机Internet阶段： Internet3网络的主要功能： （1）资源共享 （2）信息传输 （3）分布处理 （4）综合信息服务4网络的分类按覆盖地域分：局域网、城域网、广域网、Internet 按拓扑结构分： （网络拓扑结构是指网络中节点间的物理连接方式）总线形、环形、星形（树形）、混合形：5网络的体系结构OSI 的七层体系结构：计算机网络体系结构是分层的，共分为七层：第1层：物理层：涉及在通信信道上传送原始二进制位。规定通信双方相互连接的机械特性、电气特性、功能特性和规程特性。第2层：数据链路层：在物理层提供服务的基础上向网络层提供服务。解决相邻节点之间的可靠传递。第3层：网络层：将源端发出的分组经过各种途径送到目的端。它是处理端到端数据传送的最低层。第4层：运输层：真正完成了“主机主机”即端到端的连接和传输。第5层：会话层：对会话进行管理和对会话进行同步控制服务。第6层：表示层：处理系统之间用户信息的表示问题。第7层：应用层：是网络的最高层，是网络系统和人的接口，其任务是向用户提供各种直接的服务。如文件服务、共享打印机服务、电子邮件服务、虚终端以及远程登录等。主机之间是通过通信子网进行通信的，每一台主机配备这7层功能，其中1至3层直接与通信子网相连，称为低层，相应地将4至7层称为高层。6局域网的工作方式 通常有两种： 客户机/服务器(Client/Server): 提供资源并管理资源的计算机称为服务器；使用共享资源的计算机称客户机； 对等(Peer-to-Peer): 不使用服务器来管理网络共享资源，所以的计算机处于平等的地位。7Internet的形成与发展 又称国际互联网，规范的译名是“因特网”，指当前各国、各地区众多开发的网络连接在一起而形成的全球性网络。 我国Internet的发展情况： 八十年代末，九十年代初才起步。1989年我国第一个公用分组交换网CNPAC建成运行。 我国已陆续建成与Internet互联的四个全国范围的公用网络： 中国公用计算机互联网（CHINANET）、中国金桥信息网（CHINAGBN） 中国教育和科研计算机网（CERNET）、中国科学技术网（CSTNET）8IP地址： 我们把整个Internet看作一个单一的、抽象的网络，所谓IP地址，就是为Internet中的每一台主机分配一个在全球范围唯一地址。 IP地址是用“.”隔开地四个十进制整数，每个数字取值为0255。IP地址分A、B、C、D；E五类，目前大量使用的是A、B、C三类，D类为Internet体系结构委员会IAB专用，E类保留在今后使用。9域名域名地址采用层次结构，一个域名一般有35个子段，中间用“. ”隔开。顶级域名有三类： 国家顶级域名,如cn（中国）、us（美国）、uk（英国）； 国际顶级域名 int ，国际性组织可在int 下注册； 通用顶级域名，如：com、net、edu、gov、 10Internet的服务与工具 Internet的服务有：电子邮件、远程登陆、文件传输、信息服务等； 电子邮件（E_mail）：电子邮件地址格式为 收信人邮箱名邮箱所在主机的域名例：winner01 远程登陆（Telnet）：指通过Internet与其它主机连接。 登陆上另一主机，你就可以使用该主机对外开放的各种资源，如联机检索、数据查询。 文件传输（FTP）：用于在计算机间传输文件。如下载软件等。11全球信息网（WWWWorld Wide Web）：又称万维网，是一个全球规模的信息服务系统，由遍布于全世界的数以万计的Web站点组成。12网络分类 局域网：局限于某个范围内的网络连接 广域网：跨地区的局域网称为广域网。因特网是覆盖全球的广域网。 13因特网提供的服务功能主要有： （1）信息测览（WWW）； （2）文件传输（FTP） （3）发送接收电子邮件（Emaill） （4）电子公告牌（BBS） （5）远程登录（telnet） （6）电子商务14网址的结构：http：http：超文本浏览协议， www.sina表示主机域名， com网络机构域名，这里是商业网，cn地区域名，这里是中国域名。 15电子邮件的地址：zhangming这里zhangming是用户，是分隔符号，yahoo是主机名（雅虎），com是域名。16、计算机网络的分类按照网络的地域覆盖范围，网络主要分为：局或网（LAN）、城域网（MAN）、广域网（WAN）和网际网（WWW）。按照网络的拓扑结构分，网络可分为：总线型、星形、环形、树形、全连通形。三、计算机中有关数、编码的基本常识 （一）1计算机是智能化的电器设备 计算机就其本身来说是一个电器设备，为了能够快速存储、处理、传递信息，其内部采用了大量的电子元件，在这些电子元件中，电路的通和断、电压高低，这两种状态最容易实现，也最稳定、也最容易实现对电路本身的控制。我们将计算机所能表示这样的状态，用0，1来表示，即用二进制数表示计算机内部的所有运算和操作。 2二进制数的运算法则 二进制数运算非常简单，计算机很容易实现，其主要法则是： 000 011 101 1十1=10； 0 x 0=0 0 xl0 1x 0 0 1xl=1 由于运算简单，电器元件容易实现，所以计算机内部都用二进制编码进行数据的传送、计算。 3十进制与二进制、八进制、十六进制数之间的相互转换（1）数的进制与基数。 计数的进制不同，则它们的基数也不相同，如表1l所示。进制基数十进制数典型示例（转换）二进制0，110,7,231010111,10111三进制0,1,210,7,23101,21,212四进制0,1,2,310,7,2322,13,113八进制0,1,2,3,4,5,6,710,63,12612,77,176十进制0,1,2,3,4,5,6,7,8,9十六进制0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F10,63,254A,3F,15E （2）数的权 不同进制的数，基数不同，其每位上所代表的值的大小也不相同，我们称之为“权” 十进制数，逢十进一。如，（219）10=2x1021x1019x100 二进制数，逢二进一。如，（11010）2=lx24lx230x22lx210x2026 八进制数，逢八进一。如，（273）8 2x827x813x80187 十六进制数，逢十六进一。如，（27B）162x1627x16111x160635 从以上的计算中，可以看到，进制不同，基数不同，每位上权值大小也不相同，数值大小也不相同。 （3）十进制数转换成任意进制数 将十进制数转换成任意进制数的基本方法是：将十进制数除以所定的进制数反向取余。 例如： 将39用二进制数表示，用如下的短除法，求余数，并反向取余。如果转换成二进制还可以用右边的2的N次幂表示。2 39 2 19 12 9 1 2 4 12 2 02 1 02 0 12的N次幂表示：(39)10=(100111)2= lx25+0x240x231x22lx211x20 短除法 39=（100111）2将245用八进制数表示，我们可以用如下的短除法，求余数，并反向取余。想一想，为什么要反向取余。对于十进制小数要转换成其他进制的数，则是不断将小数部分乘以进制数取整，作为转换后的小数部分，直到为零或精确到小数点后几位。如： (0.35)10（0.01011）2 (0.125)10=(0.001)2（4）任意进制的数转换成十进制数将任意进制数转换成十进制数的基本方法是按权展开，见（2）数的权内容。 （二）ASCII码 ( American Standard Code for Information Interchange )美国的标准信息交换代码 将每个字符用7位的二进制数来表示，共有128种状态 大小字母、09、其它符号、控制符 0 48 A 65 a 97（三）汉字信息编码1 汉字输入码汉字输入方法大体可分为：区位码（数字码）、音码、形码、音形码。 区位码：优点是无重码或重码率低，缺点是难于记忆； 音码：优点是大多数人都易于掌握，但同音字多，重码率高，影响输入的速度； 形码：根据汉字的字型进行编码，编码的规则较多，难于记忆，必须经过训练才能较好地掌握；重码率低 音形码：将音码和形码结合起来，输入汉字，减少重码率，提高汉字输入速度；2汉字交换码汉字交换码是指不同的具有汉字处理功能的计算机系统之间在交换汉字信息时所使用的代码标准。自国家标准GB231280公布以来，我国一直延用该标准所规定的国标码作为统一的汉字信息交换码。GB231280标准包括了6763个汉字，按其使用频度分为一级汉字3755个和二级汉字3008个。一级汉字按拼音排序，二级汉字按部首排序。此外，该标准还包括标点符号、数种西文字母、图形、数码等符号682个。区位码的区码和位码均采用从01到94的十进制，国标码采用十六进制的21H到73H（数字后加H表示其为十六进制数）。区位码和国标码的换算关系是：区码和位码分别加上十进制数32。如“国”字在表中的25行90列，其区位码为2590，国标码是397AH。* 由于GB231280是80年代制定的标准，在实际应用时常常感到不够，所以，建议处理文字信息的产品采用新颁布的GB18030信息交换用汉字编码字符集，这个标准繁、简字均处同一平台，可解决两岸三地间GB码与BIG5码间的字码转换不便的问题。3字形存储码字形存储码是指供计算机输出汉字（显示或打印）用的二进制信息，也称字模。通常，采用的是数字化点阵字模。1616点表示一般的点阵规模有1616，2424，6464等，每一个点在存储器中用一个二进制位（bit）存储。例如，在1616的点阵中，需832 bit 的存储空间，每8 bit为1字节，所以，需32字节的存储空间。在相同点阵中，不管其笔划繁简，每个汉字所占的字节数相等。为了节省存储空间，普遍采用了字形数据压缩技术。所谓的矢量汉字是指用矢量方法将汉字点阵字模进行压缩后得到的汉字字形的数字化信息。（四）其它信息的数字化1 图像信息的数字化一幅图像可以看作是由一个个像素点构成，图像的信息化，就是对每个像素用若干个二进制数码进行编码。图像信息化后，往往还要进行压缩。图像文件的后缀名有：bmp、gif、jpg、pdf等；2 声音信息的数字化 自然界的声音是一种连续变化的模拟信息，可以采用A/D转换器对声音信息进行数字化。 声音文件的后缀名有：wav、mp3、mid等； 3 视频信息的数字化视频信息可以看成连续变换的多幅图像构成，播放视频信息，每秒需传输和处理25幅以上的图像。视频信息数字化后的存储量相当大，所以需要进行压缩处理。视频文件后缀名有：avi、mpg等； 四、机器数与真值数有正、负两种，在计算机中数的符号是用数码表示的。一般情况下，用0表示正数，用1表示负数。通常符号位放在数的最高位。机器数：连同符号位在一起作为一个数，称为机器数。真值数：一个数的数值部分称为真值数。如：x1=+1011011 x2=-1011011, 则X1的机器数是01011011，真值数是+1011011，X2的机器数是11011011，真值数是-1011011。（一）数的定点表示和浮点表示(1) 定点小数格式任何一个M位的小数可以表示成：N=Ns . N-1N-2N-m (其中Ns 是符号位，其值表示的范围|N|=1-2-m)(2) 定点整数格式任何一个N位带符号的整数都可表示为：N=Ns Nn-1Nn-2N0 (其中Ns 是符号位，其值表示的范围|N|=2n-1)(3) 数的浮点表示浮点数是指小数点在数据中的位置可以左右移动的数。一个数N要用浮点表示可以写成：N=MRE 其中M表示浮点数的尾数,E表示浮点数的指数或称为阶码,R指的是在这个指数下的基数。浮点数通常表示成如下格式：MsEM1位 m位 n位M：浮点数的尾数，用定点小数表示，小数点在尾数最高位之前，是默认的。尾数用于表示浮点数的有效位，其位数N的大小反映了此浮点数的精度。E：浮点数的阶码，用定点整数表示。Ms：浮点数的符号位，也就是尾数的符号位，一般放在整个浮点数的最高位。(4)浮点数的规格化当尾数用二进制数表示时，浮点规格化数定义尾数S应满足下面关系：（I）对于正数，S应大于等于1/2，小于1，用二进制数表示为：S=0.1*(其中*为0或1)（II）对于负数，如果尾数用原码表示，S应小于等于-1/2，大于-1，表示为：S=1.1*(其中*为0或1)（III）机器零：当一个浮点数的尾数为0，不论其阶码为何值；或阶码的值遇到比它能表示的最小值还小时，不管其尾数为何值，计算机都把该浮点数看成零，即把阶码尾数全变为0，称它为机器0。（二）二进制数值数据的编码方法最常用的编码方法有原码表示法、补码表示法和反码表示法三种。1、原码表示法用机器数的最高（最左）一位代表符号，其余各位给出数值的绝对值。X原=符号位+|X|（0代表正号，1代表负号）真值零的原码表示法，有正零和负零两种表示：+0原=00000 -0原=100002、补码表示法如果X为正数，则：X补=X原如果X为负数，则：X补=（把X原 除符号位外，其余各位全变反（0变1，1变0），再在最末位加1 ）+0补=-0补=0000同理有：如果X为负数，则：X原=（把X补 除符号位外，其余各位全变反（0变1，1变0），再在最末位加1 ）3、反码表示法如果X为正数，则：X反=X原如果X为负数，则：X反=（把X原 除符号位外，其余各位全变反（0变1，1变0）+0反=00000 -0反=11111可见，如果真值X=0，则X补 有唯一的编码，X原 和 X反 都有两个不同的编码。9