初赛复习课件

Pascal程序设计初赛绍兴市长城中学-----陈龙（一）初赛

初赛全部为笔试，满分100分。试题由四部分组成：

1、选择题：共20题，每题1.5分，共计30分。每题有5个备选答案，前10个题为单选题（即每题有且只有一个正确答案，选对得分），后10题为不定项选择题（即每题有1至5个正确答案，只有全部选对才得分）。普及组20个都是单选题。

2、问题求解题：共2题，每题5分，共计10分。试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。考生给出的答案与标准答案相同，则得分；否则不得分。

3、程序阅读理解题：共4题，每题8分，共计32分。题目给出一段程序（不一定有关于程序功能的说明），考生通过阅读理解该段程序给出程序的输出。输出与标准答案一致，则得分；否则不得分。

4、程序完善题：共2题，每题14分，共计28分。题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句或语句的一部分并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填出被略去的语句。填对则得分；否则不得分。1、计算机的基本常识考纲2、计算机的基本操作3、程学设计的基本知识初赛内容与要求5．信息系统组成及互连网的基本知识（计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP协议、HTTP协议、WEB应用的主要方式和特点）6．人机交互界面的基本概念（窗口系统、人和计算机交流信息的途径（文本及交互操作））7．信息技术的新发展、新特点、新应用等。1、计算机的基本常识2、计算机的基本操作1.Windows和LINUX的基本操作知识2.

互联网的基本使用常识（网上浏览、搜索和查询等）3.

常用的工具软件使用（文字编辑、电子邮件收发等）3、程学设计的基本知识分类内容数据结构1．程序语言中基本数据类型(字符、整数、长整、浮点)2.

浮点运算中的精度和数值比较3．一维数组（串）与线性表4．记录类型（PASCAL）/

结构类型（C）程序设计1．结构化程序设计的基本概念2．阅读理解程序的基本能力3．具有将简单问题抽象成适合计算机解决的模型的基本能力4．具有针对模型设计简单算法的基本能力5．程序流程描述（自然语言/伪码/NS图/其他）6．程序设计语言（PASCAL/C/C++）-2003仍允许BASIC基本算法处理1．初等算法（计数、统计、数学运算等）2．排序算法（冒泡法、插入排序、合并排序、快速排序）3．查找（顺序查找、二分法）4．回溯算法分类内容数据结构1．指针类型2．多维数组3．单链表及循环链表4．二叉树5．文件操作（从文本文件中读入数据，并输出到文本文件中）程序设计1．算法的实现能力2．程序调试基本能力3．设计测试数据的基本能力4．程序的时间复杂度和空间复杂度的估计基本算法处理1．离散数学知识的应用（如排列组合、简单图论、数理逻辑）2．分治思想3．模拟法4．贪心法5．简单搜索算法（深度优先广度优先）搜索中的剪枝6．动态规划的思想及基本算法复赛内容与要求一、计算机历史与发展阶段时间逻辑器件应用范围图片第一代1946-1958真空电子管科学计算、军事研究第二代1959-1964晶体管数据处理、事务处理第三代1965-1970集成电路包括了工业控制的各个领域第四代1971-至今大规模集成电路应用到各个领域5.4.控制器是计算机的指挥系统，由程序计数器、指令寄存器、指令译码器、时序产生器和操作控制器组成，用来完成协调和指挥整个计算机系统的操作；二、计算机硬件知识5.CPU（中央处理器）负责完成大部分的信息处理操作，是执行各种运算的中心和控制调度全机工作的中心。由运算器、控制器和一些寄存器组成。寄存器用于在指令执行过程中存放操作数和中间数据，存取速度远远大于内存和外存。CPU的主要指标是主频和字长；品牌：intelAMDIBM二、计算机硬件知识8.输出设备：音响、耳机、显示器、打印、绘

图仪等9.输入输出接口：VGA（视频）DVI（数字）HDMI（高清）10.各个部件之间传送信息的公共通路叫总线

分三类：数据总线、地址总线和控制总线11.台式机内部各个硬件形态（1）CPU（2）主板（3）内存（4）硬盘二、计算机硬件知识11.台式机内部各个硬件形态二、计算机硬件知识（5）电源（6）显卡12.计算机工作原理

各种各样的信息，通过输入设备，进入计算机的存储器，最后通过输出设备显示出来。整个过程由控制器进行控制。计算机的整个工作过程及基本硬件结构如下图：二、计算机硬件知识输入设备内存储器运算器控制器输出设备外存储器信息（如程序、原始数据）（存）数据输入命令输出信息数据程序命令存取指令运算指令（取）数据（存）数据输出命令12.计算机工作原理三、计算机软件知识2.操作系统：管理和控制计算机系统中的所有

软硬件资源；常见的操作系统:

微软公司的Dos、Windows系列、

LINUX系列，UNIX系列，Mac（苹果）1.计算机软件系统分为：系统软件和应用软件

系统软件通常负责管理、控制和维护计算机的各种软硬件资源，并未用户提供有好多操作界面，如操作系统；应用软件是用户为解决实际问题开发的专门程序。三、计算机软件知识2.常见的操作系统：（2）UNIXUNIX基本都是安装在服务器上，没有用户界面，基本上都是命令操作。所以你进入该系统的时候就是一个黑乎乎的界面，然后就之后一个光标在闪呀闪。没有什么娱乐软件，不能看图片，不能听歌。有SOLARIS,BSD系列三、计算机软件知识2.常见的操作系统：（3）LINUX系列Linux算是UNIX的孩子吧，他继承了UNIX的许多特性，还加入自己的一些新的功能。有的linux有界面有的没有。而且Linux是开源的，免费的。谁都可以拿去做修改，然后开发出有自己特色的操作系统。做的比较好的有：红旗，ubuntu，Fedora，Debian等。这些都可以装在台式机或笔记本上。也有相应的软件可以用，比如：QQ，IE等一些常用的软件。三、计算机软件知识3.应用软件分类类型软件名称办公软件微软office，金山WPS图像处理ACDSee，AdobePhotoshop，美图秀秀，光影魔术手媒体播放器WindowsMdiaPlayer，暴风影音，千千静听，酷狗音乐盒，媒体编辑软件CoolEdit，GoldWave，会声会影，Primere，Vegas,AE浏览器360安全，360极速，遨游，猎豹，QQ，百度，搜狗通信工具QQ，MSN，阿里旺旺，飞信网络电视腾讯视频，PPlive，PPS，风行，迅雷看看，爱奇艺，优酷下载软件迅雷，QQ旋风，快车，电驴，百度下载器，维棠，硕鼠杀毒软件瑞星，360杀毒，卡巴斯基，金山毒霸数据库管理系统Access，SQLServer，Oracle，sybase系统优化360安全卫士，鲁大师，电脑管家，瑞星卡卡，超级兔子其他Flash（动画制作），Dreamwear（网页制作）AodbeReader(pdf阅读器)，格式工厂，有道词典，winrar压缩软件，Nero（光盘刻录）浏览器软件聊天软件输入法软件下载软件视频软件音乐软件图像软件压缩软件杀毒软件办公软件三、计算机软件知识3.应用软件分类三、计算机软件知识5.驱动程序

是一种可以使计算机和设备通信的特殊程序。相当于硬件的接口，操作系统只有通过这个接口，才能控制硬件设备的工作，假如某设备的驱动程序未能正确安装，便不能正常工作。6.BIOS（BasicInputOutputSystem）基本输入输出系统：它是一组固化到计算机内主板上一个ROM芯片上的程序，它保存着计算机最重要的基本输入输出的程序、开机后自检程序和系统自启动程序，它可从CMOS中读写系统设置的具体信息。四、计算机学科知识1.程序设计语言分为机器语言、汇编语言、高

级语言。常用的高级语言：Fortran，Algol，Cobol，Pascal，C，C++，VisualBasic等；2.支持部分或绝大部分面向对象特征的语言成

为面向对象的语言。如Java，C#，Eiffel；

比较早的面向过程的语言业吸收了对象的概

念，如C->C++，Basic->VisualBasic，Pascal->ObjectPascal,Ada->Ada953.数据库是长期纯属在计算机内，有组织、可共享的数据集合。数据库管理系统是位于用户和操作系统间的一层数据管理软件。

四、计算机学科知识4.数据库语言-SQL语言（结构化查询语言）5.进制转换

（1）二进制：由0和1组成，每位计满2就向高位进1，即逢二进一；除了二进制，还会接触到八进制、十六进制；为了区分我们常用下标“2”来表示，如（10）2=3；而十六进制中，我们通常用A，B，C….表示10,11,12…

（2）R进制转化为十进制如二进制转化为十进制：(110111)2=1*25+1*24+0*23+1*22+1*21+1*20=32+16+0+4+2+1=59四、计算机学科知识（3）十进制转换成R进制(26)10=(11010)22613631222201011整数转化倒着写(0.3125)10=（0.0101）20.3125*2=0.625……整数部分为00.625*2=1.25……整数部分为10.25*2=0.5……整数部分为00.5*2=1……整数部分为1四、计算机学科知识（3）十进制转换成R进制小数转化顺着写注意：十进制小数常常不能准确地换算为等值的二进制小数，例如：四、计算机学科知识（3）十进制转换成R进制(0.5627)10

转换成二进制数0.5627*2=1.1254……整数部分为10.1254*2=0.2508……整数部分为00.2508*2=0.5016……整数部分为00.5016*2=1.0032……整数部分为1…此过程会不断进行下去，因此只能取到一定精度：（0.5627）10=（0.1001）2四、计算机学科知识（4）二、八、十六进制相互转换

由于这三个数制存在联系，即23=824=16，所以每位八进制数相当于三位二进制数，每位十六进制数相当于四位二进制数。在转换时，以小数点为中心，向左右两边延伸，两头不够用0补；（1011010.10）2转换成八进制和十六进制：八进制001011010.100132.4=（132.4）8十六进制01011010.10005A.8=（5A.8）166.计算机内码

计算机中运算的数有正负之分，数的符号也用二进制表示（最高位），常用机器码有原码、反码、补码；

（1）原码：正数符号位为0，负数符号位为1；

如：X=+1110001则X原=01110001X=-1110001则X原=11110001（2）反码：符号位法则与原码相同，负数时除

符号位其它各位取值求反；

如：X=+1110001则X反=01110001X=-1110001则X反=10001110四、计算机学科知识四、计算机学科知识

6.计算机内码

（3）补码：正数与原码一致，负数在反码的

基础上末尾加一

如：X=+1110001则X补=01110001X=-1110001则X补=10001111

7.数之间的逻辑运算

与（and∧&）两个都真才为真

或（or∨|）一个为真就为真

非（not┓!）反一反异或（xor⊕）同为0，异为10⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0四、计算机学科知识

8.运算优先级（由高到低）：一元运算（负号－、not）→乘除运算（*、/、div、mod、and）→加减运算（+、－、orxor）→关系运算（=、<>、<、>、<=、>=）

9.（1）ASCII码（美国标准信息交换码），用7位二进制数来编码（占一个字节），可表示128个字符，ord(‘0’)=48ord(‘A’)=65ord(‘a’)=97（2）汉字编码，一个汉字由两个ASCII码（94个）组成（两个字节）。10.1Byte=8bit1KB=1024B以下单位均已1024倍转换，从小到大为：ByteKBMBGBTBPBEBZB11.多媒体技术：用计算机综合处理文本、图形、图像、音频和视频等多种媒体信息，使他们建立逻辑连接，即成为一个具有交互性的系统。12.三基色：红、绿、蓝，大多数的颜色可以

通过红绿蓝三色不同比例合成产生。四、计算机学科知识13.位图与矢量图（图像与图形）

位图又称点阵图，有许多像素点构成；矢量图：以数学向量的方式来计算图像内容；四、计算机学科知识14.动态图（GIF），每一幅画面称为一帧，由于人眼的视觉惰性，每秒24帧的电影画面就形成了连续活动影像；15.音频数字化（脉冲编码调制技术PCM）包括采样、量化、编码三个步骤四、计算机学科知识16.病毒：是人编写的用来破坏计算机功能或者数据的程序。具有传播性、隐蔽性、感染性、潜伏性、可激发性、表现性或破坏性；

木马：病毒的一种，不破坏不感染其他程序，以窃取数据为目的；17.防火墙、杀毒软件、安全卫士

防火墙相当于防盗门防入侵，杀毒软件则用于电脑内部杀毒，安全卫士修复漏洞优化系统；四、计算机学科知识18.黑客(hacker)：通常是指对计算机科学、编程和设计方面具高度理解的人；五、网络知识1.网络的分类：局域网LAN、城域网MAN、广域网WAN；最大的广域网：Internet2.网络的主要功能（1）资源共享（2）信息传输（3）分布处理（4）综合信息服务3.拓扑结构：总线拓扑、星型拓扑、环形拓扑五、网络知识4.网络协议：在计算机网络中一系列的通信规则称为网络协议，如数据的格式是怎么样的，以什么样的控制信号联络，具体传送方式是什么，发送法师怎么样保证数据的完整性、正确性等等；这些都是网络协议需要的功能。常见的网络协议有TCP/IP协议，IPX/SPX协议；五、网络知识5.OSI7层参考模型：

为了解决不同网络中网络协议可能不一致的情况，国际标准化组织在1981年推出了OSI标准。希望所有网络系统向该标准靠拢，消除不同系统之间因协议不同造成的通信障碍。OSI不是一个实际的物理模型，仅仅是一个标准，网络开发者可以根据这个标准开发网络系统，制定网络协议；五、网络知识5.OSI7层参考模型：

通常把计算机网络分成通信子网和资源子网两部分，低三层为通信子网，高三层为资源子网，传输层起承上启下作用；6.网络的发展阶段，4个阶段（1）20世纪60年代中期之前，以单台计算机为中心的远程联机系统（2）20世纪60年代中期至70年代，称为计算机-计算机网络（3）20世纪70年代末至90年代，开放式标准化的网络（4）20世纪90年代末至今，新一代的计算机网络五、网络知识7.网络操作系统：Windows类，NetWare类，Unix系统，LINUX系统五、网络知识8.各英文缩写汇总

FTP：文件传输协议HTTP：超文本传输协议POP3/SMTP：接收/发送邮件协议TCP：传输控制协议UDP：用户数据报协议Telnet：远程登录P2P：点对点

9.云计算：一种按使用量付费的模式，这种模式提供便捷的、按需的网络访问，进入计算资源共享池（资源包括网络，服务器，存储，应用软件，服务），这些资源能够被快速提供，只需投入很少的管理工作或与服务供应商进行很少的交互。五、网络知识10.网络硬件系统

（1）服务器：一台速度快，存储量大的计算机，负责网络资源管理和用户服务；（2）工作站：具有独立处理能力的计算机，用户可以在工作站上处理日产工作，随时向服务器索取信息，请求服务器提供服务；

（3）网卡（网络适配器）：它的作用是将计算机与通信设备相连接，将计算机的数字信号转换成通信线路能够传送的电子信号和电磁信号；

五、网络知识10.网络硬件系统

（4）调制解调器（modem，猫）：把计算机的数字信号“调制”成通信线路的模拟信号，将通信线路的模拟信号“解调”回计算机的数字信号；（5）路由器：它会根据信道的情况自动选择和设定路由，以最佳路径，按前后序发送信号。现在主要实现有线和无线、一支和多支的转化；五、网络知识10.网络硬件系统

（6）交换机：主要用于企业中，多台上网设备，如机房、一幢住宅楼；实现多台上网设备之间的汇聚与数据交换；（7）中继器用于完全相同的两类网络的互连，主要功能是通过对数据信号的重新发送或者转发，来扩大网络传输的距离。中继器是对信号进行再生和还原的网络设备；五、网络知识（8）双绞线（网线）由两根具有绝缘保护层的铜导线组成（9）光纤：是一种由玻璃或塑料制成的纤

维，可作为光传导工具。五、网络知识光纤与双绞线（10）无线网卡五、网络知识10.IP地址Internet中的每一台主机分配一个在全球范围唯一地址。IPv4地址是由32位二进数码表示的，每8个一段用“.”隔开，再把每一段的二进制数化成十进制数，也就得到我们现在所看到的IP地址形式，每个数字取值为0—255。如00IPv4地址分A、B、C、D、E五类，目前大量使用的是A、B、C三类，D类为Internet体系结构委员会IAB专用，E类保留在今后使用。最高位1..126为A类，128..191是B类，192..223是C类。五、网络知识10.IP地址

IPv6用于替代现行版本IP协议（IPv4）的下一代IP协议，号称可以为全世界的每一粒沙子编上一个网址。IPv6的地址长度为128位，是IPv4地址长度的4倍。一个IPv6地址中问可能包含很长的一段0，可以把连续的一段0压缩为“::”五、网络知识11.域名：ip地址对于使用者来说，太难记忆，于是又研究出一种字符型的地址：域名。域名地址采用层次结构，一个域名一般有3－5个子段，中间用“.”隔开。如：顶级域名有三类：国家顶级域名,如cn（中国）、us（美国）、uk（英国）；国际顶级域名:ini，国际性组织可在ini下注册；通用顶级域名，如：com（商业机构）、

net（网络服务机构）、edu（教育、科研机构）、

gov（政府）、org（专业团体）、……

六、数据结构1.数组二维数组/多维数组2.链表单链表、循环链表、双向链表3.哈希表六、数据结构4.栈先进后出（FILO）5.队列先进先出（FIFO）

循环队列6.树和二叉树

高度、度、叶子

完全二叉树、满二叉树

先序、中序、后序遍历

最小生成树六、数据结构7.堆：大根堆、小根堆8.图：有向图和无向图完全图最小生成树算法：Prim算法和Kruskal算法

基于点基于边最短路算法：Dijkstra算法和Floyd算法七、算法1.时空复杂度常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),...，k次方阶O(nk),指数阶O(2n)2.递归和分治七、算法3.排序

选择、插入、冒泡、快排、归并4.贪心算法5.动态规划七、算法6.搜索

广度优先搜索BFS和深度优先搜索DFS7.高精度（压位）八、数学1.对数函数（1）ab=N（a>0,a≠1），则b叫做以a为底N的对数，b=logaN。当a=10时称作常用对数lgN，当a=e时称作自然对数InN。（2）基本运算loga+logb=log（a*b）loga-logb=log（a/b）n*loga=log(an)logab/logac=logcblogab*logca=logcb（3）一棵完全二叉树共有N个节点，它的深度是多少？Alog2NBlog2N+1C[log2N]D[log2N]+1[x]表示向下取整D八、数学2.排列与组合（1）排列：从n个不同元素中，任取m个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m