csp-J初赛知识点汇编.pdf

CSP-J 初 赛 知 识 点 汇 编 0 目录 目录 第一章 计算机基础 2 第 1 节 计算机常识2 第 2 节 计算机的基本构成 4 第 3 节 计算机软件7 第 4 节 计算机网络和 Internet 的基本概念 9 第 5 节 程序设计语言以及程序编译和运行的基本概念 15 第 6 节 进制的基本概念与进制转换、字节与字 16 第二章 算法 23 第 1 节 算法的基本概念 23 第 2 节 入门组基础算法理论 24 第三章 数据结构 28 第 1 节 线性数据结构 28 第 2 节 非线性数据结构35 第四章 组合数学43 1 第一章 计算机基础 第1节 计算机常识 一、发展史 1．计算机发展代别划分： 代别 年代 逻辑（电子）元件 第一代 1946—1958 电子管 第二代 1959—1964 晶体管 第三代 1965—1970 集成电路 第四代 1971—至今 大规模、超大规模集成电路 2 ．第一台电子计算机 1946 年 2 月，在美国宾夕法尼亚大学诞生了世界上第一台电子计算机ENIAC（Electronic Numerical Integrator and Computer ），这台计算机占地 170 平方米，质量 30 吨，用了 18000 多个电子管，每秒能进行 5000 次加法运算。 3 ．冯·诺依曼理论 1944 年，美籍匈牙利数学家冯·诺依曼提出计算机基本结构和工作方式的设想，为计 算机的诞生和发展提供了理论基础。时至今日，尽管计算机软硬件技术飞速发展，但计算机 本身的体系结构并没有明显的突破，当今的计算机仍属于冯·诺依曼架构。 其理论要点如下： 计算机硬件设备由存储器、运算器、控制器、输入设备和输出设备 5 部分组成。 存储程序思想——把计算过程描述为由许多命令按一定顺序组成的程序，然后把程序和 数据一起输入计算机，计算机对已存的程序和数据处理后，输出结果。 二、计算机的分类 根据计算机的性能指标，如机器规模的大小、运算速度的高低、主存储容量的大小、指 令系统性能的强弱以及机器的价格等，可将计算机分为巨型机、大型机、中型机、小型机、 微型机和工作站。 巨型机：具有很强的计算和处理数据的能力，主要特点表现为高速度和大容量，配有多 种外部和外围设备及丰富的、高功能的软件系统。主要用来承担重大的科学研究、国防尖端 技术和国民经济领域的大型计算课题及数据处理任务。如大范围天气预报，整理卫星照片， 原子核物的探索，研究洲际导弹、宇宙飞船等