中国计算机学会 CSP-J初赛知识点汇总资料

CSP- 用在不不语准 。 目录 目录 第一章 计算机基础. 第1节 计算机常识 第2节 计算机的基本构成 第3节 计算机软件 第4节 计算机网络和lnternet的基本概念 第5节 程序设计语言以及程序编译和运行的基本概念 第6节 进制的基本概念与进制转换、字节与字 -....1. 算法.... 第二章 ..... 第1节 算法的基本概念... 第2节 入门组基础算法理论 第三章 数据结构. 第1节 线性数据结构 -.... 第2节 非线性数据结构 第四章 组合数学.. _ 第一章计算机基础 第1节 计算机常识 一、发展史 1. 计算机发展代别划分: 代别 年代 逻辑(电子)元件 第一代 1946-1958 电子管 第二代 1959-1964 晶体管 第三代 1965-1970 集成电路 第四代 1971-至今 大规模、超大规模集成电路 2. 第一台电子计算机 1946年2月,在美国宾夕法尼亚大学诞生了世界上第一台电子计算机ENIAC(Electronic Numerical Integrator andComputer),这台计算机占地170平方米,质量30吨,用了18000 多个电子管,每秒能进行5000次加法运算 3. 冯·诺依曼理论 1944年,美籍匈牙利数学家冯·诺依曼提出计算机基本结构和工作方式的设想,为计 算机的诞生和发展提供了理论基础。时至今日,尽管计算机软硬件技术飞速发展,但计算机 本身的体系结构并没有明显的突破,当今的计算机仍属于冯·诺依曼架构。 其理论要点如下: 计算机硬件设备由存储器、运算器、控制器、输入设备和输出设备5部分组成。 存储程序思想一一把计算过程描述为由许多命令按一定顺序组成的程序,然后把程序和 数据一起输入计算机,计算机对已存的程序和数据处理后,输出结果。 二、计算机的分类 根据计算机的性能指标,如机器规模的大小、运算速度的高低、主存储容量的大小、指 令系统性能的强弱以及机器的价格等,可将计算机分为巨型机、大型机、中型机、小型机、 微型机和工作站。 巨型机:具有很强的计算和处理数据的能力,主要特点表现为高速度和大容量,配有多 种外部和外围设备及丰富的、高功能的软件系统。主要用来承担重大的科学研究、国防尖端 技术和国民经济领域的大型计算课题及数据处理任务。如大范围天气预报,整理卫星照片, 原子核物的探索,研究洲际导弹、宇宙飞船等。“天河一号”为我国首台千万亿次超级计算 机。2010年9月开始进行系统调试与测试,并分步提交用户使用。 大、中型机:大型机使用专用的处理器指令集、操作系统和应用软件,大量使用元余 等技术确保其安全性及稳定性,擅长非数值计算(数据处理),主要用于商业领域,如银行 和电信。 小型机是指采用精简指令集处理器,性能和价格介于PC服务器和大型主机之间的一科 高性能64位计算机。 小型机与普通服务器相比具有: (1)高可靠性(Reliability):计算机能够持续运转,从来不停机。 (2)可用性(Availability):重要资源都有备份:能够检测到潜在要发生的问题,并且 能够转移其上正在运行的任务到其他资源,以减少停机时间,保持生产的持续运转;具有实 时在线维护和延迟性维护功能。 (3)高服务性(Serviceability):能够实时在线诊断,精确定位根本问题所在,做到准 确无误的快速修复。 微型机:通常作为个人计算机,由硬件系统和软件系统组成,是一种能独立运行,完成 特定功能的设备。个人计算机不需要共享其他计算机的处理、磁盘和打印机等资源也可以独 立工作。从台式机(或称台式计算机、桌面电脑)、笔记本电脑到上网本和平板电脑以及超 级本等都属于个人计算机的范畴。 工作站是一种高端的通用微型计算机。它是为了单用户使用并提供比个人计算机更强大 的性能,尤其是在图形处理能力,任务并行方面的能力。通常配有高分辨率的大屏、多屏显 示器及容量很大的内存储器和外部存储器,并且具有极强的信息和高性能的图形、图像处理 功能的计算机。另外,连接到服务器的终端机也可称为工作站。 三、计算机的应用 计算机的快速性、通用性、准确性和逻辑性等特点,使它不仅具有高速运算能力,而目 还具有逻辑分析和逻辑判断能力。如今,计算机已渗透到人们生活和工作的各个层面中,主 要体现在以下几个方面的运用。 1. 科学计算 科学计算(或数值计算)是指利用计算机来完成科学研究和工程技术中提出的数学问题 的计算。在现代科学技术工作中,科学计算问题是大量的和复杂的。利用计算机的高速计算、 大存储容量和连续运算的能力,可以实现人工无法解决的各种科学计算问题。 2. 信息处理 信息处理(数据处理)是指对各种数据进行收集、存储、整理、分类、统计、加工、利 用、传播等一系列活动的统称。据统计,80%以上的计算机主要用于数据处理,这类工作量 大、面宽,决定了计算机应用的主导方向。 3. 自动控制 自动控制(过程控制)是利用计算机及时采集检测数据,按最优值迅速地对控制对象进 行自动调节或自动控制。采用计算机进行自动控制,不仅可以大大提高控制的自动化水平, 而且可以提高控制的及时性和准确性,提高产品质量及合格率。目前,计算机过程控制已在 机械、冶金、石油、化工、纺织、水电、航天等部门得到了广泛的应用 4. 计算机辅助技术 计算机辅助技术是指利用计算机帮助人们进行各种设计、处理等过程,它包括计算机辅 助设计(CAD)、计算机辅助制造(CAM)、计算机辅助教学(CAI)和计算机辅助测试(CAT) 等。另外,计算机辅助技术还有辅助生产、辅助绘图和辅助排版等 5.人工智能 人工智能(ArtificialIntelligence,AD)又可称为智能模拟,是计算机模拟人类的智能活 动,诸如感知、判断、理解、学习、问题求解和图像识别等。人工智能的研究目标是使计算 机更好地模拟人的思维活动,那时的计算机将可以完成更复杂的控制任务。 6. 网络应用 _ 随着社会信息化的发展,通信业也发展迅速,计算机在通信领域的作用越来越大,特别是促 进了计算机网络的迅速发展。目前,全球最大的网络(lnternet.即国际互联网)已把全球的 大多数计算机联系在一起。除此之外,计算机在信息高速公路、电子商务、娱乐和游戏等领 域也得到了快速的发展。 第2节 计算机的基本构成 计算机系统由硬件和软件两部分组成。硬件系统是计算机的“躯干”,是物质基础。而 软件系统则是建立在这个“躯于”上的“灵魂” [控制器 中央处理器CPU [运算器 主机 [ROM(只读存储器 内存RAM(读写存储器) 硬件系统 Cache(高速缓冲存储器) [输入设备一一键盘、鼠标、扫描仪、麦克风等 计算机 外设输出设备一-显示器、打印机、音响等 外存一-硬盘、软盘、光盘、闪存(优盘)等 [操作系统 系统软件编译程序和解释程序 软件系统 数据库管理系统 应用软件 [各种字处理系统 l各种软件包 一、计算机硬件 计算机硬件由五大部分组成:运算器、控制器、存储器、输入设备、输出设备。 1. 中央处理器(CPU--Central Processing Unit) 由运算器、控制器和一些寄存器组成 运算器进行各种算术运算和逻辑运算 控制器是计算机的指挥系统 CPU的主要性能指标是主频和字长。 2. 存储器 存储器的主要功能是用来保存各类程序的数据信息 存储器可分为主存储器和输助存储器两类。 ①主存储器(也称为内存储器),属于主机的一部分。用于存放系统当前正在执行的数 据和程序,属于临时存储器。 ②辅助存储器(也称外存储器),属于外部设备。用于存放暂不用的数据和程序,属于 永久存储器。存储器与CPU的关系表示 CPU 内存储器 外存储器 (1)内存储器 内存又称为主存,它和CPU一起构成了计算机的主机部分,它存储的信息可以被CPU 4 直接访问。内存由半导体存储器组成,存取速度较快,但一般容量较小。内存中含有很多的 存储单元,每个单元可以存放1个8位的二进制数,即1个字节(Byte,简称“B”)。内存 中的每个字节各有一个固定的编号,这个编号称为地址。CPU在存取存储器中的数据时是 按地址进行的。所谓存储器容量,即指存储器中所包含的字节数,通常用KB、MB、GB、 TB和PB作为存储器容量单位,它们之间的关系为 1KB-1024B 1MB-1024 KB 1GB-1024MB 1TB-1024GB 1PB-1024TB 内存储器通常可以分为随机存储器RAM、只读存储器ROM和高速缓冲存储器Cache 三种。 ①RAM是一种读写存储器,其内容可以随时根据需要读出,也可以随时重新写入新的 信息。当电源电压去掉时,RAM中保存的信息都将全部丢失。 ②ROM是一种内容只能读出而不能写入和修改的存储器,其存储的信息是在制作该存 储器时就被写入的。在计算机运行过程中,ROM中的信息只能被读出,而不能写入新的内 容。计算机断电后,ROM中的信息不会丢失。它主要用于检查计算机系统的配置情况并提 供最基本的输入/输出(I/O)控制程序。 ③由于CPU速度的不断提高,RAM的速度很难满足高速CPU的要求,所以,在读/写 系统内存时都要加入等待的时间,这对高速CPU来说是一种极大的浪费。Cache是指在CPU 与内存之间设置的一级或两级高速小容量存储器,称之为高速缓冲存储器,固化在主板上。 在计算机工作时,系统先将数据由外存读入RAM中,再由RAM读入Cache中,然后CPU 直接从Cache中取数据进行操作。 CPU >Cache 内存器 外存储器 (2)外存储器 外存储器又称为辅助存储器,它的容量一般都比较大,而且大部分可以移动,便于 在不同计算机之间进行信息交流。在微型计算机中,常用的外存有软盘、硬盘、闪存和 光盘4种。 ①软盘存储器 软盘存储器由软盘、软盘驱动器和软盘适配器三部分组成。软盘是活动的存储介质,软 盘驱动器是读写装置,软盘适配器是软盘驱动器与主机连接的接口。软盘驱动器安装在主机 箱内,软盘驱动器插暴露在主机箱的前面板上,可方便地插入或取出软盘。 ②硬盘存储器 硬盘存储器是由电机和硬盘组成的,一般置于主机箱内。硬盘是涂有磁性材料的磁盘组 件,用于存放数据。硬盘的机械转轴上串有若干个盘片,每个盘片的上下两面各有一个读 写磁头,与软盘磁头不同,硬盘的磁头不与磁盘表面接触,它们“飞”在离盘片面百万分之 一英寸的“气垫”上。硬盘是一个非常精密的机械装置,磁道间只有百万分之几英寸的间隙 磁头传动装置必须把磁头快速而准确地移到指定的磁道上。 ③闪存 闪存又名优盘,是在存储速度与容量上介于软盘与硬盘之间的一种外部存储器。 ④光盘 光盘的存储介质不同于磁盘,它属于另一类存储器。由于光盘的容量大、存取速度较快 不易受干扰等特点,其应用越来越广泛。光盘根据其制造材料和记录信息方式的不同一般分 为三类:只读光盘、一次写入型光盘和可擦写光盘。 __ 3. 输入设备 输入设备是外界向计算机传送信息的装置。在微型计算机系统中,最常用的输入设备是 键盘和鼠标。此外,还有光电笔、数字化仪、图像扫描仪、触摸屏、麦克风、视频输入设备、 条形码扫描器等,也可以用磁盘和磁带进行输入。 4. 输出设备 输出设备的作用是将计算机中的数据信息传送到外部媒介,并转化成某种为人们所认识 的表示形式。在微型计算机中,最常用的输出设备有显示器和打印机。此外,还有绘图仪等 也可以通过磁盘和磁带输出 二、总线结构 按照总线上传输信息的不同,总线可以分为数据总线(DB)、地址总线(AB)和控制总 线(CB)三种。 ①数据总线:用来传送数据信息,它主要连接了CPU与各个部件,是它们之间交换信 息的通路。数据总线是双向的,而具体的传送方向由CPU控制。 ②地址总线:用来传送地址信息。CPU通过地址总线中传送的地址信息访问存储器。通 常地址总线是单向的。同时,地址总线的宽度决定可以访问的存储器容量大小,如20条地 址总线可以控制1MB的存储空间。 ③控制总线:用来传送控制信号,以协调各部件之间的操作。控制信号包括CPU对内 存储器和接口电路的读写控制信号、中断响应信号,也包括其他部件传送给CPU的信号 如中断中请信号、准备就绪信号等。 三、主要的性能指标 计算机的常用指标有: 1. 字长 字长是指一台计算机所能处理的二进制代码的位数。计算机的字长直接影响它的精度 功能和速度。字长越长,能表示的数值范围就越大,计算出的结果的有效位数也就越多;字 长越长,能表示的信息就越多,机器的功能就更强。目前常用的是16位、32位、64位字长 2. 运算速度 运算速度是指计算机每秒钟所能执行的指令条数,一般用MIPS(MillionofInstructions PerSecond,即每秒百万条指令)为单位。由于不同类型的指令执行时间长短不同,因而运 算速度的计算方法也不同。 3. 主频 主频是指计算机CPU的时钟频率,它在很大程度上决定了计算机的运算速度。一般时 钟频率越高,运算速度就越快。主频的单位一般是MHz(兆赫)或GHz(吉赫),如微处理 器Pentium4/2.0 GHz的主频为2*1000MHz。 4. 内存容量 内存容量是指内存储器中能够存储信息的总字节数,一般以GB为单位。内存容量反映 内存储器存储数据的能力。目前计算机的内存容量有2GB、4GB、8GB等。 四、CPU CPU(中央处理单元)是微机的核心部件,是决定微机性能的关键部件。20世纪70年 代微型机的CPU问世,微型计算机的核心部件微处理器从Intel4004,80286,80386,80486 发展到PentiumII/III和Pentium4,数位从4位、8位、16位、32位发展到64位,主频从几 MHz到今天的数GHz以上(1GHz三1000MHz),CPU芯片里集成的晶体管数由2万个跃 升到1000万个以上。CPU的发展和技术的进展直接推动了微型计算机的发展,也是微机各 个发展阶段的主要标志。 接口一 基板 -编码 核心 一散热片 桥接。 电路 从原理上看,CPU的内部结构分控制单元、逻辑单元、存储单元三部分。从组成器件上 看,CPU的内部是由成千上万个晶体管组成,晶体管实质上就是一双位开关:即“开”和 “关”。 CPU的主要性能指标包括时钟主频、字长、高速缓存容量、指令集合和动态处理技术 制造工艺、封装方式和工作电压等。 主频是指CPU的工作时钟频率,是CPU内核电路的实际运行频率。一般来说,主频越 高,一个时钟周期里面完成的指令数也越多,速度也越快。主频的单位为兆赫兹(MHz)和 吉赫兹(GHz)。我们通常所说的2.8GHz、3.0GHz就是指CPU的主频。 字长(wordsize)指的是微处理器CPU能够同时处理的二进制位数的个数。字长的大 小取决于ALU中寄存器的容量和连接着这些寄存器的电路性能。例如,8位字长的微处理 器有8位的寄存器,每次能处理8位的数据,因此,被称为“8位处理器”。有更大字长的 处理器能够在每个处理器周期内处理更大的数据,因此,字长越长计算机性能越好。目前的 个人计算机通常都带有32位或64位的处理器。 高速缓存(Cache)也称为“RAM缓存”或“缓冲存储器”。它是一种具有很高速度的 特殊内部存储器,与安装在主板上其他位置的内存相比,它能够使微处理器更快地获得数据。 字节和字长的区别:常用的英文字符用8位二进制就可以表示,所以通常就将8位称为 一个字节,字节是一种存储容量单位。而字长是CPU处理能力的一种标准,字长的长度是 不固定的,对于不同的CPU字长的长度也不一样。8位的CPU一次只能处理一个字节,而 32位的CPU一次就能处理4个字节。同理,字长为64位的CPU一次可以处理8个字节。 1971年,英特尔公司推出了世界上第一款微处理器4004,字长4位,是4位微处理器 1978年,英特尔公司生产的8086是第一个16位的微处理器。 1985年,英特尔生产出32位字长处理器80386。 目前市场上主流的CPU的字长几乎都达到了64位。 第3节 计算机软件 软件是计算机的灵魂。没有安装软件的计算机称为“裸机”,无法完成任何工作。硬件 为软件提供运行平台。软件和硬件相互关联,两者之间可以相互转化、互为补充。计算机的 软件分成系统软件和应用软件两大类。 _ [操作系统 Windows: 窗口式操作系统 Dos:磁盘操作系统 UNIX:网络操作系统 系统软件 各种计算机语言处理程序 机器语言 汇编语言 软件系统 高级语言 数据库管理系统 支持软件 [程序库 软件包 应用软件 套装软件 用户程序 一、系统软件 系统软件是指控制和协调计算机及外部设备,支持应用软件开发和运行的系统,是无需 用户干预的各种程序的集合,主要功能是调度,监控和维护计算机系统;负责管理计算机系 统中各种独立的硬件,使得它们可以协调工作。系统软件使得计算机使用者和其他软件将计 算机当作一个整体而不需要顾及到底层每个硬件是如何工作的。 常用的操作系统: 1. 桌面操作系统从软件上可主要分为两大类,分别为类Unix操作系统和Windows操 作系统。 Unix和类Unix操作系统:MacOSX,Linux 发行版(如Debian.Ubuntu,Linux Mint openSUSE, Fedora, Mandrake, Red Hat, Centos): 微软公司Windows操作系统[5l:Windows98,Windows 2ooo.WindowsXP,Windows Vista, Windows 7, Windows 8, Windows 8.1, Windows 1o等。 2. 服务器操作系统。 服务器操作系统主要集中在三大类 Unix 系列:SUNSolaris,IBM-AIX,HP-UX,FreeBSD, OS X Server[6]等: Linux 系列: Red Hat Linux,CentOS,Debian,UbuntuServer等; Windows 系列:Windows NT Server, Windows Server 2oo3, Windows Server 20o8, Windows Server 2oo8 R2, windows server 2012, windows server technical 等. 二、应用软件 应用软件是用户为了解决各自应用领域里的具体任务而编写的各种应用程序和有关文 档资料的统称。这类软件能解决特定问题。应用软件与系统软件的关系是;系统软件为应用 软件提供基础和平台,没有系统软件应用的软件是无源之本,反过来应用软件又为系统软件 服务。 常用的应用软件有以下几类:(1)字处理软件:(2)电子制表软件:(3)计算机辅助设 计软件:(4)图形软件:(5)教育软件:(6)电子游戏软件。 x 用户 应用软件 实用系统软件 操作系统 硬件 三、计算机的指令 指令是一组二进制代码,它规定了由计算机执行的程序的一步操作。一条指令由操作码 和操作数组成,前者规定指令要完成的操作,必不可少;后者是这个操作针对的对象,可以 没有。 指令系统是一种计算机所能识别并可执行的全部指令的集合。例如,80386的指令系统 共有123种指令,可分为9类指令操作;数据传递、算术运算、逻辑运算、串操作、位操作 程序控制、高级语言指令、保护模式、处理器控制指令。 程序是计算机为了执行某种操作任务而将一条条指令按照一定的顺序排列起来的指 令集。 第4节 计算机网络和lnternet的基本概念 一、网络的定义 所谓计算机网络,就是利用通信线路和设备,把分布在不同地理位置上的多台计算机连 接起来。 计算机网络是现代通信技术与计算机技术相结合的产物 网络中计算机与计算机之间的通信依靠协议进行。协议是计算机收、发数据的规则 TCP/lP:用于网络的一组通信协议。包括lP(lnternet Protocol)和TCP(Transmission Control Protocol) 二、网络的发展 计算机网络的发展过程大致可以分为三个阶段 远程终端联机阶段:主机一终端 [计算机-计算机 计算机网络阶段: IInternet阶段: Internet 三、网络的主要功能 (1)资源共享:(2)信息传输:(3)分布处理;(4)综合信息服务。 四、网络的分类 按网络的地理范围进行分类:局域网(LAN)、城域网(MAN)、广域网(WAN)。 1. 局域网(Local Area Network)