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

0 CSP-J CSP-J 初赛知(识点汇编 1 目录 目录 第一章 计算机基础 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 2 第一章计算机基础 第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部分组成。 存储程序思想——把计算过程描述为由许多命令按一定顺序组成的程序，然后把程序和 数据一起输入计算机，计算机对已存的程序和数据处理后，输出结果。 二、计算机的分类 根据计算机的性能指标，如机器规模的大小、运算速度的高低、主存储容量的大小、指 令系统性能的强弱以及机器的价格等，可将计算机分为巨型机、大型机、中型机、小型机、 微型机和工作站。 巨型机：具有很强的计算和处理数据的能力，主要特点表现为高速度和大容量，配有多 种外部和外围设备及丰富的、高功能的软件系统。主要用来承担重大的科学研究、国防尖端 技术和国民经济领域的大型计算课题及数据处理任务。如大范围天气预报，整理卫星照片， 原子核物的探索，研究洲际导弹、宇宙飞船等。“天河一号”为我国首台千万亿次超级计算 机。2010年9月开始进行系统调试与测试，并分步提交用户使用。 大、中型机：大型机使用专用的处理器指令集、操作系统和应用软件，大量使用冗余 等技术确保其安全性及稳定性，擅长非数值计算(数据处理),主要用于商业领域，如银行 和电信。 小型机是指采用精简指令集处理器，性能和价格介于PC 服务器和大型主机之间的一种 高性能64位计算机。 小型机与普通服务器相比具有： 3 (1)高可靠性 (Reliability): 计算机能够持续运转，从来不停机。 (2)可用性 (Availability): 重要资源都有备份；能够检测到潜在要发生的问题，并且 能够转移其上正在运行的任务到其他资源，以减少停机时间，保持生产的持续运转；具有实 时在线维护和延迟性维护功能。 (3)高服务性 (Serviceability): 能够实时在线诊断，精确定位根本问题所在，做到准 确无误的快速修复。 微型机：通常作为个人计算机，由硬件系统和软件系统组成，是一种能独立运行，完成 特定功能的设备。个人计算机不需要共享其他计算机的处理、磁盘和打印机等资源也可以独 立工作。从台式机(或称台式计算机、桌面电脑)、笔记本电脑到上网本和平板电脑以及超 级本等都属于个人计算机的范畴。 工作站是一种高端的通用微型计算机。它是为了单用户使用并提供比个人计算机更强大 的性能，尤其是在图形处理能力，任务并行方面的能力。通常配有高分辨率的大屏、多屏显 示器及容量很大的内存储器和外部存储器，并且具有极强的信息和高性能的图形、图像处理 功能的计算机。另外，连接到服务器的终端机也可称为工作站