logo资料库

精—信息学奥赛初赛复习内容.doc

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：0.68M 资料格式：doc 举报 版权申诉
第1页 / 共68页
第2页 / 共68页
第3页 / 共68页
第4页 / 共68页
第5页 / 共68页
第6页 / 共68页
第7页 / 共68页
第8页 / 共68页
资料共68页，剩余部分请下载后查看
    分区联赛初赛复习
    选择题
    一、硬件
    二、进制与编码
    三、软件与操作系统
    四、信息安全
    五、网络
    六、数据结构与算法
    七、排列组合
    八、综合
    其他问题类型
    写运行结果
    程序填空
    数学
    贪心
    二分查找
    回溯法
    模拟
    关键路径
    搜索
    练习
    分区联赛初赛复习 初赛考的知识点就是计算机基本常识、基本操作和程序设计基础知识。其中选择题考查 的是知识，而问题解决类型的题目更加重视能力的考查。一般说来，选择题只要多用心积累 就可以了。问题解决题目的模式比较固定，大家应当做做以前的题目。写运行结果和程序填 空也需要多做题目，并且培养良好的程序阅读和分析能力，就像语文的阅读理解一样。 近几年来，初赛的考查范围有了很大的变化，越来越紧跟潮流了。这就需要大家有比较 广泛的知识，包括计算机硬件、软件、网络、简单的数据结构（例如栈、队列、树和图等） 和简单的算法（例如排序、查找和搜索等），程序设计语言以及一些基本的数学知识和技巧 （例如排列组合）。但最主要的，还是取决于你对程序设计语言的熟悉程度，再加上认真仔 细的心态。 选择题 一、硬件 计算机发展可划分： 第一代 第二代 第三代 第四代 年代 1946－1958 1959－1964 1965－1970 1971－？ 元件 电子管 晶体管 集成电路 大规模集成电路 1946 年 2 月，在美国宾夕法尼亚大学诞生了世界上第一台电子计算机 ENIAC（Electronic Numerical Integrator And Computer），这台计算机占地 170 平方米，重 30 吨，用了 18000 多个电子管，每秒能进行 5000 次加法运算。 冯·诺依曼理论 1944 年，美籍匈牙利数学家 冯·诺依曼 提出计算机基本结构和工作方式的设想，为 计算机的诞生和发展提供了理论基础。时至今日，尽管计算机软硬件技术飞速发展，但计算 机本身的体系结构并没有明显的突破，当今的计算机仍属于冯·诺依曼架构。 其理论要点如下： 1、计算机硬件设备由存储器、运算器、控制器、输入设备和输出设备 5 部分组成。 2、存储程序思想——把计算过程描述为由许多命令按一定顺序组成的程序，然后把程 序和数据一起输入计算机，计算机对已存入的程序和数据处理后，输出结果。 我国的计算机发展情况 1
    ·我国从 1956 年开始计算机的科研和教学工作； ·1960 年我国第一台自行设计的通用电子计算机 107 机诞生； 1964 年我国研制成大型通用电子计算机 119 机； ·1983 年每秒运行一亿次的银河巨型计算机在国防科技大学诞生； 1992 年研制成功每秒运行 10 亿次的“银河Ⅱ”巨型计算机； 1997 年又研制成功每秒运行 130 亿次的“银河Ⅲ”巨型计算机； ·我国较有名的微型计算机品牌有：“联想”、“长城”、“方正”等； 微型机的主要技术指标 1、字长：知己算计能够直接处理的二进制数据的位数。单位为位（BIT） 2、主频：指计算机主时钟在一秒钟内发出的脉冲数，在很大程度上决定了计算机的运 算速度。 3、内存容量：是标志计算机处理信息能力强弱的一向技术指标。单位为字节（BYTE）。 8BIT=1BYTE 1024B=1KB 1024KB=1MB 4、外存容量：一般指软盘、硬盘、光盘。 计算机的特点： 运算速度快，运算精度高，具有记忆能力，具有逻辑判断能力，具有自动控制能力； 计算机的应用： 1、数值计算：弹道轨迹、天气预报、高能物理等等 2、信息管理：企业管理、物资管理、电算化等 3、过程控制：工业自动化控制，卫星飞行方向控制 4、辅助工程：CAD、CAM、CAT、CAI 等 计算机硬件由五大部分组成：运算器、控制器、存储器、输入设备、输出设备。 中央处理器（CPU——Central Processing Unit） 由运算器、控制器和一些寄存器组成； 运算器进行各种算术运算和逻辑运算； 控制器是计算机的指挥系统； CPU 的主要性能指标是主频和字长。 存储器 2
    内部存储器 中央处理器能直接访问的存储器称为内部存储器，它包括快速缓冲存储器和主存储器， 中央处理器不能直接访问的存储器称为外部存储器，外部存储器中的信息必须调入内存后才 能为中央处理器处理。 主存储器：内存也常泛称主存，但严格上说，只有当内存中只有主存，而没有快速缓冲 存储器时，才能称为主存。 主存储器按读写功能，可分只读存储器（ROM）和随机存储器（RAM）两种。 外部存储器 外存储器：也称为辅助存储器，一般容量较大，速度比主存较慢。 硬盘（Hard disk）：目前的硬盘大多采用了温彻斯特技术，所以又称为“温盘”； 温氏技术的特点是：将盘片、读写磁头及驱动装置精密地组装在一个密封盒里；采用接 触式起停，非接触式读写的方式（磁盘不工作时，磁头停在磁盘表面的起停区，一旦加电后， 磁头随着盘片旋转的气流“飞”起来，悬浮在磁盘表面，进行读写）。 软盘（Floppy Disk）：目前常见的是 3.5 英寸/1.44 MB 的软盘。 光盘存储器（CD-ROM）：普通的 CD-ROM，只能读，不能写； CD 盘片的存储量大约是 650 MB。 输入设备 ·键盘（Keyboard）：目前大多使用 104 或 108 键盘 ·鼠标（Mouse）：主要有机械型鼠标和光电型鼠标两种 ·手写笔 ·触摸屏 ·麦克风 ·扫描仪（Scanner）·视频输入设备·条形码扫描器 输出设备 ·显示器（Monitor）：目前主要有 CRT（阴极射线管）显示器和 LCD 液晶显示器。 ·打印机（Printer）：主要有针式打印机、喷墨打印机、激光打印机。 ·绘图仪 ·音箱 例题 微型计算机的问世是由于( C ) 的出现。 A)中小规模集成电路 B)晶体管电路 C) (超)大规模集成电路 D) 电子管电路 中央处理器(CPU)能访问的最大存储器容量取决于( A ) 。 A)地址总线 B)数据总线 C) 控制总线 D) 实际内存容量 微型计算机中，( C ) 的存取速度最快。 A)高速缓存 B)外存储器 C) 寄存器 D) 内存储器 在计算机硬件系统中，cache 是(D )存储器。 A)只读 B)可编程只读 C)可擦除可编程只读 D)高速缓冲 若我们说一个微机的 CPU 是用的 PII300，此处的 300 确切指的是(A )。 3
    A)CPU 的主时钟频率 B)CPU 产品的系列号 C)每秒执行 300 百万条指令 D)此种 CPU 允许最大内存容量 计算机主机是由 CPU 与（ D ）构成的。 A. 控制器 B. 输入、输出设备 C. 运算器 D.内存储器 计算机系统总线上传送的信号有（ B ）。 A.地址信号与控制信号 B. 数据信号、控制信号与地址信号 C.控制信号与数据信号 D. 数据信号与地址信号 不同类型的存储器组成了多层次结构的存储器体系，按存取速度从快到慢的排列是（C）。 A.快存/辅存/主存 D. 主存/辅存/外存 B. 外存/主存/辅存 C. 快存/主存/辅存 微机内存储器的地址是按（C）编址的。 A. 二进制位 B. 字长 C.字节 D. 微处理器的型号 在微机中，通用寄存器的位数是（C）。 A 8 位 B．16 位 C.计算机字长 D．32 位 不同的计算机，其指令系统也不同，这主要取决于（C）。 A 所用的操作系统 B. 系统的总体结构 C．所用的 CPU D．所用的程序设计语言 下列说法中，哪个（些）是错误的（ BDE ）。 A）程序是指令的序列，它有三种结构：顺序、分支和循环。 B）数据总线决定了中央处理器 CPU 所能访问的最大内存空间的大小。 C）中央处理器 CPU 内部有寄存器组，用来储存数据。 D）不同厂家生产的 CPU 所能处理的指令集是相同的。 E）数据传输过程中可能会出错，奇偶校验法可以检测出数据中哪一位在传输中出 了差错。 CPU 访问内存的速度比访问下列哪个（些）存储设备要慢（ A）寄存器 B）硬盘 速缓存 E）光盘 AD C）软盘 ）。 D）高 下列哪个（些）不是个人计算机的硬件组成部分（ B ）。 盘 A）主 板 E）总线 B）虚 拟内 存 C）电 源 D）硬 美籍匈牙利数学家冯·诺依曼对计算机科学发展所做出的贡献是（ C ）。 A. 提出理想计算机的数学模型，成为计算机科学的理论基础。 B. 是世界上第一个编写计算机程序的人。 C. 提出存储程序工作原理，并设计出第一台具有存储程序功能的计算机 EDVAC。 D. 采用集成电路作为计算机的主要功能部件。 4
    E. 指出计算机性能将以每两年翻一番的速度向前发展。 下列哪个不是 CPU（中央处理单元）（ B ）。 A. Intel Itanium Power 5 B. DDR SDRAM C. AMD Athlon64 D. AMD Opteron E. IBM 下列说法中错误的是（ B ）。 A. CPU 的基本功能就是执行指令。 B. CPU 访问内存的速度快于访问高速缓存的速度。 C. CPU 的主频是指 CPU 在 1 秒内完成的指令周期数。 D. 在一台计算机内部，一个内存地址编码对应唯一的一个内存单元。 E. 数据总线的宽度决定了一次传递数据量的大小，是影响计算机性能的因素之一。 用静电吸附墨粉后转移到纸张上，是哪种输出设备的工作方式（ C ）。 A. 针式打印机 B. 喷墨打印机 C. 激光打印机 D. 笔式绘图仪 E. 喷墨绘图仪 处理器A 每秒处理的指令数是处理器B 的2 倍。某一特定程序P 分别编译为处理器A 和处理器B 的指令，编译结果处理器A 的指令数是处理器B 的4 倍。已知程序P 在处 理器A 上执行需要1 个小时，那么在输入相同的情况下，程序P 在处理器B 上执行需 要（D）小时。 A. 4 D. 1 / 2 E. 1 / 4 B. 2 C. 1 以下哪个不是计算机的输出设备（D）。 A. 音箱 B. 显示器 C. 打印机 D. 扫描仪 E. 绘图仪 二、进制与编码 四种常用的数制及它们之间的相互转换： 进制 基数 基数个数 十进制 0、1、2、3、4、5、6、7、8、9 二进制 八进制 十六进制 0、1 0、1、2、3、4、5、6、7 0、1、2、3、4、5、6、7、8、9、 A、B、C、D、E、F 10 2 8 16 权 10i 2i 8i 16i 进数规律 逢十进一 逢二进一 逢八进一 逢十六进一 十进制数转换为二进制数、八进制数、十六进制数的方法： 二进制数、八进制数、十六进制数转换为十进制数的方法：按权展开求和法 1．二进制与十进制间的相互转换： （1）二进制转十进制 方法：“按权展开求和” 例： （1011.01）2 ＝（1×23＋0×22＋1×21＋1×20＋0×2－1＋1×2－2 ）10 ＝（8＋0＋2＋1＋0＋0.25）10 ＝（11.25）10 5
    规律：个位上的数字的次数是 0，十位上的数字的次数是 1，......，依奖递增，而十 分位的数字的次数是-1，百分位上数字的次数是-2，......，依次递减。 注意：不是任何一个十进制小数都能转换成有限位的二进制数。 （2）十进制转二进制 · 十进制整数转二进制数：“除以 2 取余，逆序排列”（短除反取余法） 例： （89）10 ＝（1011001）2 2 2 2 2 89 44 22 11 5 2 1 0 2 2 2 ……1 ……0 ……0 ……1 ……1 ……0 ……1 · 十进制小数转二进制数：“乘以 2 取整，顺序排列”（乘 2 取整法） 例： (0．625)10= (0．101)2 X X X 0．625 2 1．25 2 0．5 2 1．0 1 0 1 2．八进制与二进制的转换： 二进制数转换成八进制数：从小数点开始，整数部分向左、小数部分向右，每 3 位为一 组用一位八进制数的数字表示，不足 3 位的要用“0”补足 3 位，就得到一个八进制数。 八进制数转换成二进制数：把每一个八进制数转换成 3 位的二进制数，就得到一个二进 制数。 例：将八进制的 37.416 转换成二进制数： 3 011 111 ．100 即：（37.416）8 ＝（11111.10000111）2 7 ． 4 001 1 110 6 例：将二进制的 10110.0011 转换成八进制： 0 1 0 2 1 1 0 . 0 0 1 1 0 0 6 . 1 4 即：（10110.011）2 ＝ （26.14）8 3．十六进制与二进制的转换： 二进制数转换成十六进制数：从小数点开始，整数部分向左、小数部分向右，每 4 位为 一组用一位十六进制数的数字表示，不足 4 位的要用“0”补足 4 位，就得到一个十六进制 数。 十六进制数转换成二进制数：把每一个八进制数转换成 4 位的二进制数，就得到一个二 进制数。 例：将十六进制数 5DF.9 转换成二进制： 5 D F ． 9 0101 1101 即：（5DF.9）16 ＝（10111011111.1001）2 1111 ．1001 6
    例：将二进制数 1100001.111 转换成十六进制： 0110 6 0001 ． 1110 1 ． E 即：（1100001.111）2 ＝（61.E）16 注意：以上所说的二进制数均是无符号的数。这些数的范围如下表： 无符号位二进制数位数 数值范围 十六进制范围表示法 8 位二进制数 16 位二进制数 32 位二进制数 带符号数的机器码表示方法 0~255 （255=28-1） 0~65535 （65535=216-1） 0000H~0FFFFH 0~232-1 00~0FFH 00000000H~0FFFFFFFFH 1．带符号二进制数的表示方法： 带符号二进制数用最高位的一位数来表示符号：0 表示正，1 表示负。 含符号位二进制数位数 数值范围 十六进制范围表示法 8 位二进制数 -128 ~ +127 16 位二进制数 -32768 ~ +32767 80H~7FH 8000H~7FFFH 32 位二进制数 -2147483648 +2147483647 ~ 80000000H~7FFFFFFFH 2、符号位的表示：最常用的表示方法有原码、反码和补码。 （1）原码表示法：一个机器数 x 由符号位和有效数值两部分组成，设符号位为 x0，x 真值的绝对值|x|=x1x2x3...xn，则 x 的机器数原码可表示为： xxx 210 [x]原= 例如：已知：x1=-1011B，x2= +1001B，则 x1，x2 有原码分别是 ，当 x>=0 时，x0=0，当 x<0 时，x0=1。 ... nx [x1] 原=11011B，[x2]原=01001B 规律：正数的原码是它本身，负数的原码是取绝对值后，在最高位（左端）补“1”。 （2）反码表示法：一个负数的原码符号位不变，其余各位按位取反就是机器数的反码 表示法。正数的反码与原码相同。  例： 解： 反] = x 1001 B 按位取反的意思是该位上是 1 的，就变成 0，该位上是 0 的就变成 1。即 1=0，0=1 x 1 [ 1x 1011 B  2 [ 2x 10100 ， 反] （3）补码表示法： 首先分析两个十进制数的运算：78-38=41，79+62=141 如果使用两位数的运算器，做 79+62 时，多余的 100 因为超出了运算器两位数的范围 ，求 反] 01001 B [ 1x 和 反] [ 2x 。 ， B = 而自动丢弃，这样在做 78-38 的减法时，用 79+62 的加法同样可以得到正确结果。 模是指一个计量系统的测量范围，其大小以计量进位制的基数为底数，位数为指数的 幂。如两位十进制数的测量范围是 1——9，溢出量是 100，模就是 102=100，上述运算称为 模运算，可以写作： 79+（-38）=79+62 （mod 100) 进一步写为 -38=62，此时就说 –38 的补法（对模 100 而言）是 62。计算机是一种 有限字长的数字系统，因此它的运算都是有模运算，超出模的运算结果都将溢出。n 位二进 制的模是 2n, 一 个 数 的 补 码 记 作 [x] 补 ， 设 模 是 M ， x 是 真 值 ， 则 补 码 的 定 义 如 下 ： ][ x 补  原 ][ x   xM   ( ( x x   )0 )0 例：设字长 n=8 位，x=-1011011B，求[x]补。 7
    解：因为 n=8，所以模 M=28=100000000B，x<0，所以 [x]补=M+x=100000000B-1011011B=10100101B 注意：这个 x 的补码的最高位是“1”，表明它是一个负数。对于二进制数还有一种更 加简单的方法由原码求出补码： （1）正数的补码表示与原码相同； （2）负数的补码是将原码符号位保持“1”之后，其余各位按位取反，末位再加 1 便 得到补码，即取其原码的反码再加“1”：[x]补=[x]反+1。 下表列出 ,0  ,39 127  及  128 的 8 位二进制原码，反码和补码并将补码用十六进制 表示。 真值 +127 +39 +0 -0 -39 -127 原码（B） 0 111 1111 0 010 0111 0 000 0000 1 000 0000 1 010 0111 1 111 1111 反码（B） 0 111 1111 0 010 0111 0 000 0000 1 111 1111 1 101 1000 1 000 0000 补码（B） 0 111 1111 0 010 0111 0 000 0000 0 000 0000 1 101 1001 1 000 0001 补码（H） 7F 27 00 00 D9 81 -128 从上可看出，真值+0 和-0 的补码表示是一致的，但在原码和反码表示中具有不同形式。 1 000 0000 无法表示 无法表示 80 8 位补码机器数可以表示-128，但不存在+128 的补码与之对应，由此可知，8 位二进制补码 能表示数的范围是-128——+127。还要注意，不存在-128 的 8 位原码和反码形式。 定点数和浮点数 （一）定点数（Fixed-Point Number） 计算机处理的数据不仅有符号，而且大量的数据带有小数，小数点不占有二进制一位而 是隐含在机器数里某个固定位置上。通常采取两种简单的约定：一种是约定所有机器数的小 数的小数点位置隐含在机器数的最低位之后，叫定点纯整机器数，简称定点整数。另一种约 定所有机器数的小数点隐含在符号位之后、有效部分最高位之前，叫定点纯小数机器数，简 称定点小数。无论是定点整数，还是定点小数，都可以有原码、反码和补码三种形式。 （二）浮点数（Floating-Point Number） 计算机多数情况下采作浮点数表示数值，它与科学计数法相似，把一个二进制数通过移 动小数点位置表示成阶码和尾数两部分： E   2 N S 其中：E——N 的阶码（Expoent），是有符号的整数 S——N 的尾数（Mantissa），是数值的有效数字部分，一般规定取二进制定点纯 小数形式。 例：1011101B=2+7*0.1011101，101.1101B=2+3*0.1011101，0.01011101B=2-1*0.1011101 浮点数的格式如下： E0 E1E2……………En E0 E1E2……………En 阶符 阶 尾符 尾数 浮点数由阶码和尾数两部分组成，底数 2 不出现，是隐含的。阶码的正负符号 E0，在最 前位，阶反映了数 N 小数点的位置，常用补码表示。二进制数 N 小数点每左移一位，阶增加 1。尾数是这点小数，常取补码或原码，码制不一定与阶码相同，数 N 的小数点右移一位， 在浮点数中表现为尾数左移一位。尾数的长度决定了数 N 的精度。尾数符号叫尾符，是数 N 的符号，也占一位。 例：写出二进制数-101.1101B 的浮点数形式，设阶码取 4 位补码，尾数是 8 位原码。 浮点形式为： -101.1101=-0.1011101*2+3 8
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料