第一章 计算机的基本常识.docVIP

目 录 第一章 计算机的基本常识 1 第一节 计算机的基本常识 1 第二节 中央处理器 1 第三节 存储器系统 3 第四节 输入输出系统 5 第五节 计算机中有关数及编码的知识 6 第六节 操作系统 14 第七节 计算机网络常识 17 第八节 计算机信息安全基础知识 20 第二章 Pascal语言程序设计 24 第一节 开始编写pascal语言程序 26 第二节 Pascal语言基础知识 28 第三节 顺序结构程序设计 34 第四节 选择结构程序设计 38 第五节　循环程序 42 第六节 数组与字符串 57 第七节 函数和过程 62 第八节 子界与枚举类型 66 第九节 集合类型 68 第十节 记录与文件类型 70 第十一节 指针类型 74 第十二节 程序调试 78 第三章 常用算法与策略 84 第一节 算法 84 第二节 递归 87 第三节 回溯 94 第四节 排序 100 第五节 查找(检索) 113 第六节 穷举（枚举）策略 118 第七节 贪心策略 124 第四章 数据结构 132 第一节 什么是数据结构 132 第二节 线性表 134 第三节 栈 143 第四节 队列 146 第五节 树和二叉树 150 第五章 历届全国青少年信息学奥林匹克联赛初赛试题及答案 155 第十六届全国青少年信息学奥林匹克联赛初赛试题 155 第十五届全国青少年信息学奥林匹克联赛初赛试题 165 第十四届全国青少年信息学奥林匹克联赛初赛试题 174 第十三届全国青少年信息学奥林匹克联赛初赛试题 181 附：青少年信息学奥林匹克竞赛情况简介 1 第一章 计算机的基本常识 第一节 计算机的基本常识 一、 计算机的产生与发展20世纪最重要的科学技术大事件之一。世界上的第一台计算机（ENIAC）于1946年诞生在美国宾夕法尼亚大学，到目前为止，计算机的发展大致经历了四代： ①?第一代电子管计算机，始于1946年，结构上以CPU为中心，使用计算机语言，速度慢，存储量小，主要用于数值计算； ②第二代晶体管计算机，始于1958年，结构上以存储器为中心，使用高级语言，应用范围扩大到数据处理和工业控制； ③?第三代中小规模集成电路计算机，始于1964年，结构上仍以存储器为中心，增加了多种外部设备，软件得到了一定的发展，文字图象处理功能加强； ④第四代大规模和超大规模集成电路计算机，始于1971年，应用更广泛，很多核心部件可集成在一个或多个芯片上，从而出现了微型计算机。 我国从1956年开始电子计算机的科研和教学工作，1983年研制成功1亿/秒运算速度的“银河”巨型计算机，1992年11月研制成功10亿/秒运算速度的“银河II”巨型计算机，1997年研制了每秒130亿运算速度的“银河III”巨型计算机。 目前计算机的发展向微型化和巨型化、多媒体化和网络化方向发展。计算机的通信产业已经成为新型的高科技产业。计算机网络的出现，改变了人们的工作方式、学习方式、思维方式和生活方式。 ?? ?????? 第节 中央处理器 一、中央处理器的组成 ??? 中央处理器简称CPU，由控制器、运算器组成。 运算器及控制器的基本功能：运算器是计算机进行算术和逻辑运算的部件，控制器是整个计算机中统一指挥和控制计算机各部件进行工作的控制中心。二、运算器??? 运算器是负责对数据进行算术运算或逻辑运算的部件。运算器由算术逻辑单元（ALU）、累加器、状态寄存器、通用寄存器组等组成。如图：????? ??? 算术逻辑运算单元、累加器和通用寄存器的位数决定了CPU的字长。 三、控制器??? 是计算机的指令执行部件，其工作是取指令、解释指令以及完成指令的执行。控制器由指令指针寄存器、指令寄存器、控制逻辑电路和时钟控制电路等组成。??? 指令指针寄存器（IP）用于产生及存放一条待取指令的地址。??? 指令寄存器用于存放指令。指令从内存取出后放入指令寄存器。 四、寄存器??? 寄存器数量增多可以提高CPU运行速度，但是不能太多，太多会使地址编码和指令长度变长，增加复杂度。由累加器、通用寄存器组、状态寄存器、指令寄存器、地址寄存器、其他寄存器等组成。 五、指令基本格式??? 单目运算：操作码 地址码??? 二目运算：操作码 第一地址 第二地址 六、寻址方式：CPU执行指令时寻找数据地址的方式?? 1立即寻址：ADD AH,78? 其中ADD是操作码，表示做加法；AH是寄存器名；78是个常数；该指令的意思是寄存器AH的值加上78。?? 2直接寻址：ADD AH,(78)? 78表示操作数的地址?? 3.间接寻址：ADD AH,((78))? 78表示操作数地址的地址?? 4.相对寻址：ADD AH,*78?? *78表示本指令地址+78，