NOIP初赛复习(基础知识).ppt

复习纲要: 1. 计算机基础知识 2. 计算机网络 3. 数据结构 4. 数据库 5. 数值数论知识 6. 阅读程序 7. 完善程序,分析试卷,计算机基础知识,知识点:,1. 计算机的应用与发展,2. 计算机系统 (软硬件系统),3. 数据在计算机中的表示,4. 计算机的维护与使用安全,计算机的应用与发展,诞生: 1946年，在美国宾西法尼亚大学世界上第一台电子数字计算机ENIAC（Electronic Numerical Integrator And Calculator电子数值积分和计算机）诞生了，它标志着计算机时代的来临.,计算机发展阶段,第一代计算机: 1946-20世纪50年代末 电子管时代,第二代计算机: 1958-1964年 晶体管时代,第三代计算机: 1964-1972年 集成电路,第四代计算机: 1972 至今 大规模,超大规模集成电路,(微型计算机),计算机的应用与发展,常识: 1. ENIAC : 1946 2. 冯. 诺依曼 : 存储程序控制原理,硬件系统结构模型 3.图灵 (图灵测试) : 英国人 4. Ada Lovelace : 第一个程序员 (女) 5. 曙光服务器: 6.银河:我国自行设计和研制的第一台每秒运算速度达亿次的巨型计算机“银河I”。 7. 神威:代表国内CPU研制最高水平的高性能嵌入式32位微处理器“神威号”. 8. 龙芯:通用64位处理器, 达国际先进水平,计算机的应用与发展,习题,以微处理器为核心组成的微型计算机属于( )计算机 A. 第一代 B.第二代 C. 第三代 D.第四代,2 . 第一代电子计算机使用的逻辑元件是( ) A. 晶体管 B. 电子管 C. 小规模集成电路 D.大规模集成电路,3.微型计算机的问世是由于( ) 的出现。 A) 中小规模集成电路 B) 晶体管电路 C) (超)大规模集成电路 D) 电子管电路,D,B,C,3. 美籍匈牙利数学家 冯诺依曼 对计算机科学发展所做出的贡献是：（ ） A、提出理想计算机数学模型，成为计算机科学理论基础 B、是世界上第一个编写计算机程序的人 C、提出存储程序工作原理，并设计出第一台具有存储程序功能的计算机EDVAC D、采用集成电路作为计算机的主要功能部件 E、指出计算机性能将以每两年翻一番的速度向前发展,C,计算机系统,计算机系统-硬件,计算机的硬件 (五大部件),1. CPU,运算器:进行算术运算和逻辑运算的部件,控制器:控制和协调计算机各部件自动、连 续地执行各条指令,(中央处理器),2. 存储器:,内存储器(主存): ROM, RAM,外存储器: (辅存),3. I/O设备,输入设备: 鼠标,键盘,扫描仪,数字化仪,输出设备:显示器,投影仪,绘图仪,打印机,CPU的主要性能指标: 字长和时钟频率(主频) 字长: 计算机一次能处理二进制的位数(单位:bit)如80486及Pentium系列的CPU一次可以处理32位二进制数据. 时钟频频: 计算机主时钟在一秒钟内发出的脉冲数,主要以MHz为单位来度量，通常时钟频率越高，其处理速度也越快。如时东芝(Toshiba)公司日前宣布推出一款高端处理器核MeP-h1，钟频率达到1GHz,思考:微机的主要技术指标,计算机的存储系统:,主存储器(内存): ROM: 只读存储器 (read only, 不可写,断电不丢失数据) RAM: 随机读写存储器 ( access, 断电后数据丢失),存储容量以字节（Byte）为单位，一个字节由8位二进制位(bit)组成。大部分都用KB，MB，GB，TB等表示，具体换算公式为：,辅助存储器(外存): 软盘, 硬盘, U盘, 光盘等,计算机的存储系统:,存储容量: 3寸软盘: 1.44M U盘: 32M 1G 光盘: CD 650700 MB 左右 DVD: 4.7GB 硬盘: G 内存: 32M 512M,存取速度: 寄存器 cache(高速缓存) RAM内存 硬盘 U盘 光盘 软盘,寄存器:寄存器是CPU内部的元件，寄存器拥有非常高的读写速度,因功能不同分为多种类型.相当于一个临时仓库. 高速缓存:在主存和CPU之间的一个高速的容量较小的存储器,如果当前正在执行的程序和数据存放在这个存储器中,当程序运行时,不必从主存中取数据和指令,直接访问这个存储器即可.,计算机的I/O设备:,输入设备: 数字化仪(图形输入设备 ) 它能将各种图形,根据坐标值,准确地输入电脑,并通过屏幕显示出来,大量用于工程设计图纸的输入,输出设备: 绘图仪:精确的绘图,如一些工程制图 打印机:,既是输入,又是输出: 触摸屏,针式打印机: 打印头的一排钢针，撞击色带,喷墨打印机:通过喷嘴将很小的黑色或彩色的墨滴喷射到打印纸上，在强电场作用下把墨滴高速喷射在纸上形成图像或文字。,激光打印机:静电吸附碳粉,加热固化于纸上,计算机系统-软件1,计算机的系统的分层结构:,1、BIOS（Basic Input-Output System） BIOS功能：它是一种软件，为计算机系统提供最低级、最直接的对硬件的控制手段。BIOS是计算机硬件与软件的桥梁。 工作原理：计算机接通电源时，首先运行BIOS，完成对系统硬件的初始化的设置和检测中央处理器、内存、只读存储器、系统主板、通信接口、磁盘及键盘以及其他设备的操作。如果没出现异常，会在指定的驱动器中寻找操作系统，找到相应的程序存入内存中运行。,计算机系统-软件2,计算机语言 1. 机器语言: 用二进制代码表示的计算机能直接识别和执行的一种机器指令的集合.不同型号的计算机其机器语言是不相通的. 目标程序既为机器语言程序 2. 汇编语言: 采用与代码指令含义相近的英文缩写词,字母和数字等符号来取代指令代码. (助记符) 3. 高级语言: 与人类自然语言相近且能为计算机所接受的语义确定,规则明确,自然直观和通用易学的计算机语言. 如:a: = c+b;,面向过程:,面向对象: ( simula, smalltalk, EIFFEF,VC+,LISP, JAVA),Fortran语言:1954年问世,历史上的第一门计算机高级语言,主要用于科学计算,计算机系统-软件3,计算机软件: (两大类),系统软件,应用软件,操作系统: DOS, LINUX, UNIX, windows, OS/2, MAC/OS,语言的编译或解释程序,编译程序: 产生目标程序,然后再执行.如pascal, C, FORTRAN, COBOL, JAVA,LISP,PROLOG等大部分高级语言编译程序. 解释程序: 将高级语言解释一句,执行一句,不形成目标程序.如BASIC语言的翻译程序.,数据库管理系统(DBMS): FoxPro, Access, Oracle, Sybase, DB2,数据库应用软件,字处理软件,多媒体信息处理软件等,计算机系统,习题,1.一个完整的计算机系统应当包括( ) 计算机与外设 B.硬件系统和软件系统 C. 主机,键盘和显示器 D. 系统硬件与系统软件,2. 操作系统是一种( )软件 系统 B. 编辑 C. 应用 D.实用,3.某单位的人事档案管理程序属于:( ) 工具软件 B. 应用软件 C. 系统软件 D. 字表处理软件,4.计算机中存储数据的最小单位是( ) A. 字节 B.位 C. 字 D.KB,5.计算机软件一般包括( ) 程序及数据 B. 程序及文档 C. 文档及数据 D.算法及数据结构,B,A,B,A,B,6.下列说法中正确的是( ) 。 A) 计算机体积越大,其功能就越强 B) CPU的主频越高,其运行速度越快 C) 两个显示器屏幕大小相同,则它们的分辨率必定相同 D)点阵打印机的针数越多,则能打印的汉字字体越多,7.下列哪一种程序设计语言是解释执行的( ) 。 A) Pascal B) GWBASIC C) C+ D) FORTRAN,8. 下列关于高级语言的说法错误的是（ ）。 A. Fortran是历史上的第一个面向科学计算的高级语言 B. Pascal和C都是编译执行的高级语言 C. C+是历史上的第一个支持面向对象的语言 D. 编译器将高级语言程序转变为目标代码 E. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上,9. 以下哪个不是计算机的输出设备（ ）。 A. 音箱B. 显示器C. 打印机D. 扫描仪E. 绘图仪,B,B,C,C,10、用静电吸附磨粉后转移到纸张上，是那种输出设备的工作方式（ ） A、针式打印机 B、喷墨打印机 C、激光打印机 D、笔式绘图仪 E、喷墨绘图仪,12、下列哪个程序设计语言不支持面向对象的程序设计方法（ ） A、C+ B、Object Pascal C、C D、Smalltalk E、Java,11下列分辨率的显示器所显示出的图像，最清晰的是( )。 A)800*600 B)1024*768 C)640*480 D)1280*1024 E)800*1000,13CPU访问内存的速度比访问下列哪个存储设备要慢( )。 A)寄存器 B)硬盘 C)软盘 D)磁带 E)光盘,C,D,C,A,数据在计算机中的表示,数值数据的表示,数值数据有大小和正负之分。 通常在微型计算机中，用两个字节表示一个整数(integer)，用四个字节表示一个实数。在二进制数的最前面规定一个符号位：“0”表示正数，“1”表示负数。,1.二进制位与字节 计算机系统的内存储器，是由许多称为字节的单元组成的，1个字节由8个二进制位（bit）构成，每位的取值为0/1。最右端的那1位称为“最低位”，编号为0；最左端的那1位称为“最高位”，而且从最低位到最高位顺序，依次编号。下图是2个字节各二进制位的编号。,2. 数值数据在计算机中的表示方式: 补码: 在计算机系统中，数值一律用补码表示（存储），原因在于：使用补码，可以将符号位和其它位统一处理；同时，减法也可按加法来处理。另外，两个用补码表示的数相加时，如果最高位（符号位）有进位，则进位被舍弃。,215=32768,Integer: -32768- 32767,数值的原码表示 数值的原码表示是指，将最高位用作符号位（0表示正数，1表示负数），其余各位代表数值本身的绝对值（以二进制形式表示）的表示形式。为简化描述起见，本节约定用1个字节表示1个整数 例如，+9的原码是00001001 符号位上的0表示正数 -9的原码是10001001。 符号位上的1表示负数,数值的反码表示 数值的反码表示分两种情况： （1）正数的反码：与原码相同。 例如，+9的反码是00001001。 （2）负数的反码：符号位为1，其余各位为该数绝对值的原码按位取反（1变0、0变1）。 例如，-9的反码：因为是负数，则符号位为“1”；其余7位为-9的绝对值+9的原码0001001按位取反为1110110，所以-9的反码是11110110。,数值的补码表示 数值的补码表示也分两种情况： （1）正数的补码：与原码相同。 例如，+9的补码是00001001。 （2）负数的补码：符号位为1，其余位为该数绝对值的原码按位取反；然后整个数加1。 例如，-9的补码：因为是负数，则符号位为“1”；其余7位为-9的绝对值+9的原码0001001按位取反为1110110；再加1，所以-9的补码是11110111。 已知一个数的补码，求原码的操作分两种情况： （1）如果补码的符号位为“0”，表示是一个正数，所以补码就是该数的原码。 （2）如果补码的符号位为“1”，表示是一个负数，求原码的操作可以是：符号位不变，再整个数减1,其余各位取反。 例如，已知一个补码为11111001，则原码是10000111（-7）：因为符号位为“1”，表示是一个负数，所以该位不变，仍为“1”；其余7位1111001取反后为0000110；再加1，所以是10000111。,数据在计算机中的表示,字符的表示,(1) ASCII 编码 (char: 8bit),(2) 汉字的编码 (16bit=2个字节),国家标准汉字编码集（GB2312-80）共收集和定义了7445个基本汉字。其中，使用频度较高的3755个汉字定义为一级汉字，以拼音顺序排列。使用频率较低的3008个汉字定义为二级汉字，以部首的笔划顺序排列，二级字库共有6763个汉字。另外还定义了拉丁字母、俄文字母、汉语拼音字母、数字和常用符号等682个。 GB231280规定每个汉字用2个字节的二进制编码，每个字节最高位为1，其余7位用于表示汉字信息,汉字的表示:,机内码: 汉字内码是用于汉字信息的存储、交换、检索等操作的机内代码，一般采用两个字节表示。英文字符的机内代码是七位的ASCII码，当用一个字节表示时，最高位为0，为与之相区别，汉字机内代码中两个字节的最高位均为1。,汉字输入方法很多，如区位、拼音、五笔字型等。不同输入法有自己的编码方案，所采用的编码方案统称为输入码。输入码进入机器后必须转换为机内码进行存储和处理,字型码,输入码:,汉字字形码是一种用点阵表示字形的码，是汉字的输出形式。它把汉字排成点阵。常用的点阵由1616、2424、3232或更高。 一个1616点阵的汉字字形要占32个字节，2424点阵要占72个字节。 所有不同的汉字字体的字形构成汉字库，一般存储在硬盘上，当要显示输出时，才调入内存，检索到要输出的字形送到显示器输出。,数据在计算机中的表示,图像,声音的表示,一幅图像可认为是由一个个像点构成的，这些像点称为像素。每个像素必须用若干二进制位进行编码，才能表示出现实世界中的五彩缤纷的图像。 当将图像分解成一系列像点、每个点用若干bit表示时，我们就把这幅图象数字化了。 数字图像数据量特别巨大，假定画面上有150000个点，每个点用24个bit来表示，则这幅画面要占用450000个字节。如果想在显示器上播放视频信息，一秒钟需传送25幅画面，相当与11250000个字节的信息量。因此，用计算机进行图像处理，对机器的性能要求是很高的。,(1)图像的表示,(1)声音的表示,声音是一种连续变化的模拟量，我们可以通过“模拟信号/数字信号”转换器对声音信号按固定的时间进行采样，把它变成数字量。一旦转变成数字形式，便可把声音储存在计算机中并进行处理了。,数据在计算机中的表示,进制间的转换,(1). 十进制,十进制计数制由0、1、2、3、4、5、6、7、8、9共10个数字符号组成。相同数字符号在不同的数位上表示不同的数值，每个数位计满十就向高位进一，即“逢十进一”。 如：555.5可以表示成 555.55100+510+51+5（1/10）,(2). 二进制,二进制计数制由0和1共2个数字符号组成。相同数字符号在不同的数位上表示不同的数值，每个数位计满二就向高位进一，即“逢二进一”。 如：（1011.1）2 18+04+12+11+1（1/2）,(3). 八进制,八进制计数制由0、1、2、3、4、5、6、7共8个数字符号组成。相同数字符号在不同的数位上表示不同的数值，每个数位计满八就向高位进一，即“逢八进一”。 如：（555.5）8可以表示成 （555.5）8564+58+51+5（1/8 ),(3). 十六进制,十六进制数由0、1、2、3、4、5、6、7、8、9、A、B、C、D、E和F共十六个符号组成，“逢十六进一”。不同的是用A、B、C、D、E和F分别表示10、11、12、13、14和15六个数字符号。,进制间的转换:,(1) 二 , 八, 十六进制,十进制,方法: 按权展开求多项式和,例题1. 将二进制数1011.1转换成对应的十进制 解：1011.1=123+022+121+120+12-1 =8+0+2+1+0.5 =11.5,例题2. 将八进制数1011.1转换成对应的十进制 解：1011.1=183+082+181+180+18-1 =512+0+8+1+0.125 =521.125,例题3. 将十六进制数1011.1转换成对应的十进制 解：1011.1=1163+0162+1161+1160+116-1 =4096+0+16+1+0.0625 =4113.0625,方法: 对于整数部分，用被除数反复除以2，每次除以2均取前一次商的整数部分(div)作被除数并依次记下每次的余数(mod)。另外，所得到的商的最后一位余数是所求二进制数的最高位。 对于小数部分，采用连续乘以基数2，并依次取出的整数部分，直至结果的小数部分为0为止。故该法称“乘基取整法”。,例题: 将十进制117.625转换成二进制数,整数部分,小数部分,结论: 117.6251110101.101,由于1位八进制数对应3位二进制数，所以二进制数转换成八进制数时，只要以小数点为界，整数部分向左，小数部分向右每3位分成一组，各组用对应的1位八进制数字表示，即可得到对应的八进制数值。最左最右端分组不足3位时，可用0补足。 例：将1101101.10101B转换成对应的八进制数。 解： 所以，1101101.10101155.52。 同理，用相反的方法可以将八进制数转换成对应的二进制数。,由于1位十六进制数对应4位二进制数，所以二进制数转换为十六进制时，只要以小数点为界，整数部分向左，小数部分向右每4位分成一组，各组用对应的1位十六进制数字表示，即可得到对应的十六进制数值。两端的分组不足4位时，用0补足。 例：将1101101.10101转换成对应的十六进制数 解： 所以 1101101.101016D.8A。 同理，用相反的方法可以将十六进制数转换成对应的二进制数。,数据在计算机中的表示,练习,1.在计算机内部,数据是以( )形式加工处理和传送的 十进制码 B. 十六进制码 C. 八进制码 D. 二进制码,2. 计算机中存书数据的最小单位是 ( ) A. 字节 B. 位 C. 字 D. KB,3.在内存中,每个基本单元被赋予一个唯一的序号,这个序号是( ) A.字节 B. 编号 C. 地址 D.容量,4.汉字国标共有( ) 个汉字 A. 7445 B.3755 C.6763 D. 3008,5.(0.5)10=( ) 16. A) 0.1 B) 0.75 C) 0.8 D) 0.25,D,A,C,C,C,6.算式(2047)10一(3FF)16+(2000)8的结果是( ) 。 A) (2048)10 B) (2049)10 C) (3746)8 D) (1AF7)16,7、十进制2004等于八进制数（ ） A、3077 B、3724 C、2766 D、4002 E、3755,A,B,计算机的维护与使用安全,(1) 计算机的维护与安全使用常识,计算机及其外部设备的其核心部件主要是由大规模和超大规模集成电路组成的。这些集成电路由半导体材料经特殊工艺加工而成，具有功耗小、耐压低等特点，故对供电电源、静电、接地、温度、湿度及抗干扰性等均具有一定的要求。正确的安装、操作、维护和使用，不仅能大大地提高计算机的使用寿命，也有利于充分发挥它的使用效率。 1.电源 要求