信息技术奥赛复习一

考试纲要初赛：一、计算机的基本常识1．计算机和信息社会（信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化）2．信息输入输出基本原理（信息交换环境、文字图形多媒体信息的输入输出方式）3．信息的表示与处理（信息编码、微处理部件MPU、内存储结构、指令，程序，和存储程序原理、程序的三种基本控制结构）4．信息的存储、组织与管理（存储介质、存储器结构、文件管理、数据库管理）5．信息系统组成及互连网的基本知识（计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP协议、HTTP协议、WEB应用的主要方式和特点）6．人机交互界面的基本概念（窗口系统、人和计算机交流信息的途径（文本及交互操作））7．信息技术的新发展、新特点、新应用等。二、计算机的基本操作1.Windows和LINUX的基本操作知识2.互联网的基本使用常识（网上浏览、搜索和查询等）3.常用的工具软件使用（文字编辑、电子邮件收发等）三、程序设计的基本知识1、数据结构：(1)程序语言中基本数据类型(字符、整数、长整数、浮点)(2)浮点运算中的精度和数值比较(3)一维数组（串）与线性表(4)记录类型（PASCAL）2、程序设计的基本知识（1）结构化程序设计的基本概念（2）阅读理解程序的基本能力（3）具有将简单问题抽象成适合计算机解决的模型的基本能力（4）具有针对模型设计简单算法的基本能力（5）程序流程描述（自然语言/伪码/NS图/其他）（6）程序设计语言（PASCAL/C/C++）3、算法的基本知识（1）初等算法（计数、统计、数学运算等）（2）排序算法（冒泡法、插入排序、合并排序、快速排序）（3）查找（顺序查找、二分法）（4）回溯算法复赛：一、数据结构1．指针类型2．多维数组3．单链表及循环链表4．二叉树5．文件操作（从文本文件中读入数据，并输出到文本文件中）二、程序设计1．算法的实现能力2．程序调试基本能力3．设计测试数据的基本能力4．程序的时间复杂度和空间复杂度的估计三、算法处理1．离散数学知识的应用（如排列组合、简单图论、数理逻辑）2．分治思想3．模拟法4．贪心法5．简单搜索算法（深度优先广度优先）搜索中的剪枝6．动态规划的思想及基本算法计算机竞赛复习（一）一、计算机产生与发展计算机的产生是20世纪最重要的科学技术大事件之一。1946年美国宾夕法尼亚大学经过几年的艰苦努力，研制出世界上第一台数字电子计算机——埃尼阿克（“ENIAC“）。自从第一台电子计算机诞生至今的50多年内，电子计算机以异常迅猛的速度发展，到目前为止，计算机发展大致经历了四代：①第一代电子管计算机，开始于1946年，结构上以CPU为中心，使用机器语言，速度慢、存储量小，主要用于数值计算；②第二代晶体管计算机，开始于1958年，结构上以存储器为中心，使用高级语言，应用范围扩大到数据处理和工业控制；③第三代中小规模集成电路计算机,开始于1964年,结构上仍以存储器为中心,增加了多种外部设备,软件得到一定发展,计算机处理图象、文字和资料功能加强；④第四代大规模和超大规模集成电路计算机，开始于1971年，应用更加广泛，出现了微型计算机。我国从1956年开始电子计算机的科研和教学工作，1983年12月研制成功每秒运行1亿次的“银河”巨型计算机，1992年11月研制成功每秒运行10亿次的“银河Ⅱ”巨型计算机，1997年又研制成功每秒运行130亿次的“银河Ⅲ”巨型计算机。目前计算机的发展向微型化和巨型化、多媒体化和网络化方向发展。我国比较著名的微型计算机有：联想计算机、清华紫光、长城计算机、方正计算机等。由于计算机向网络化发展，计算机通信产业已经成为新型高科技产业。计算机网络的出现，改变了人们的工作方式、学习方式、思维方式和生活方式。二、计算机的系统及工作原理1．计算机系统组成计算机是由硬件和软件两部分组成的。硬件是指构成计算机的电子元器件即计算机的设备；软件是指程序和有关的文档资料。（1）计算机的主要硬件输入设备:常见有键盘、鼠标、扫描仪等输出设备：常见有显示器、打印机、绘图仪等中央处理器：又称为CPU，它包括运算器、控制器。运算器可以进行算术运算和逻辑运算；控制器是计算机的指挥系统，它的操作过程是取指令──分析指令──执行指令，循环执行。存储器：具有记忆功能的物理器件，用于存储信息。存储器分为内存和外存。①内存：半导体存储器，它分为只读存储器（ROM）和随机存储器（RAM）；②外存：磁性存储器──软盘和硬盘；光电存储器──光盘，它们可以作为永久性存储器；③存储器的两个重要技术指标：存取速度和存储容量。内存的存取速度最快（与CPU速度相匹配），软盘存取速度最慢。存储容量是指存储的信息量，它用字节（BIT）作为基本单位，1字节用8位二进制数表示，1KB=1024B，1MB=1024KB，1GB=1024MB（2）计算机的软件计算机的软件主要分为系统软件和应用软件两类：①系统软件：为了使用和管理计算机的软件，主要有操作系统软件如，WINDOWS95/98/2000/NT4.0、DOS6.0、UNIX，Linux,OS/2NETWARE等；数据库管理系统如，FOXBASE，VFP5.0等；程序设计语言如，BASIC、PASCAL、C语言等。WINDOWS95/98/2000/NT4.0是多任务可视化图形界面，而DOS是字符命令形式的单任务的操作系统。②应用软件：为了某个应用目的而编写的软件，主要有辅助教学软件、辅助设计软件、文字处理软件、工具软件以及其它的应用软件。2、计算机的工作原理到目前为止，电子计算机的工作原理均采用冯·诺依曼的存储程序，并自动完成程序的设计思想。需要注意地是：程序中的数据、指令都采用数字化编码方式，保存在存储器中；程序中的指令必须是属于这台机器的指令系统。3、计算机病毒计算机病毒是一种程序，是人为设计的具有破坏性的程序。它往往使计算机不能正常工作。计算机病毒具有破坏性、传播性、可激发性、潜伏性、隐蔽性等特点。由于计算机病毒危害极大，需要注意隔离计算机病毒的来源，经常用杀病毒软件检查计算机系统和存储器。4、黑客所谓黑客是技术上的行家或热衷于解决问题克服限制的人。在精神上,hacker并不单指(限制于)这种软件hacker的文化，在任何一种科学或艺术的最高境界，你都可以发现hacker的特质.软件hacker们认为,那些类似的精神也都可以称为黑客。三、网络的基本知识1.网络概念：将地理位置不同的计算机，用通信线连接起来，共同遵守一定的协议，共享计算机的软、硬件资源。因特网是网络的集合，是全球最大的网络。2.网络分类：（广域网、局域网、城域网）局域网：局限于某个范围内网络连接广域网：跨地区的局域网称为广域网。因特网是覆盖全球的广域网。3．因特网提供的服务功能主要有：（1）信息浏览（）（2）文件传输（FTP）（3）发送接收电子邮件（E-MAIL）（4）电子公告牌（BBS）（5）远程登录（TELNET）（6）电子商务4．网址的结构：——超文本浏览协议，——表示主机域名，COM——网络机构域名，这里是商业网，cn——地区域名，这里是中国域名。5．电子邮件的地址：[e-mail]这里zhangming是用户,＠是分隔符号，yahoo主机名（雅虎），com是域名。6.URL:统一资源定位器，用来表示网页所在服务器的名称以及存放的路径，浏览器根据网页的URL访问相应的服务器，打开相应的网页。基本格式：协议名或传输方式：//服务器名或IP地址：端口号/路径/文件名常见的协议：http超文本传输协议（服务器）ftp文件传输协议（FTP文件服务器）telnet远程登录协议（telnet公共与注册服务器）常见的传输方式：电子邮件传送方式mailtoNNTP新闻组传送方式news本机文件传送方式：file注意：服务器域名可以不分大小写，但路径、文件名的大小写要正确IE浏览器默认读取方式是http和地址栏可以是字符形式的协议、服务器域名及文件名，也可以是数字形式的IP地址，如上海热线地址：202.96.209.5，每组数字小于256。电脑知识竞赛——地址分为：A、B、C三类Internet的规范译名应为（）A英特尔网B因特网C万维网D以太网正确答案选择B，因特网又称国际互联网。我国于1994年正式联入因特网。全国科学技术名词审定委员会于1997年7月18日为Internet作出了命名，中文名词为“因特网”，注译是“指全球最大的、开放的、由众多网络相互连接而成的计算机网络。万维网是的中文命名，英语是worldwideweb广泛联络世界的网，这里是指“基于超文本的、方便用户信息浏览和信息搜索的信息服务系统。人们通过信息服务系统浏览网上信息。以太网（Ethermet）是一种可以随机存取的计算机局域网，它用电缆线连接，在比较小的范围内互通信息共享网络资源。学校计算机房内的教学网是局域网。四、网上搜索信息的基本方法一、分类搜索信息按照信息的类型进行分类搜索：如，电脑、生活商品、资料等用户到比较著名的搜索网站查询、浏览信息。中文雅虎网站、搜狐网站、新浪网站等二、根据关键字搜索信息在一些著名网站中，提供了“文本输入框”，用户在该文本框内输入待查找信息的主题字即“关键字”，计算机根据关键字内容提供相应网址或网页，便于用户快速查找信息。三、直接输入网址查找所需要的信息补充：1、计算机网络是现代通信技术与计算机技术相结合的产物。网络中计算机与计算机之间的通信依靠协议进行。协议是计算机收、发数据的规则。TCP/IP：用于网络的一组通讯协议。包括IP(InternetProtocol)和TCP(TransmissionControlProtocol)2、调制解调器(Modem)既是收发器，又是接受器。它可以将计算机的数据(Digital)信号转换（调制）为模拟(Analog)信号在传输线路上进行传送，同时也可以将线路上传输的模拟信号解调回数字信号传送给计算机。3、网络的发展计算机网络的发展过程大致可以分为三个阶段：远程终端联机阶段：主机—终端（研究实验阶段）计算机网络阶段：计算机—计算机（实用发展阶段）Internet阶段：Internet（商业化阶段）4．网络的主要功能：（1）信息资源共享（2）数据信息传输（3）分布处理（4）综合信息服务5．网络的分类·按覆盖地域分：局域网、城域网、广域网、Internet局域网：LocalAreaNetwork,简写为LAN城域网：MetropolitanAreaNetwork,简写为MAN广域网：WideAreaNetwork,简写为WAN·按拓扑结构分：（网络拓扑结构是指网络中节点间的物理连接方式）总线形、环形、星形（树形）、混合形：6、数据通信中的几个主要指标a.数据传输速率指每秒能传输的二进制代码的位数，单位为位/秒（记为bit/s或bitpersecond,简写为bps）。如调制解调器的传输速率由早期的300bps逐步提高到现在的28.8Kbps,33.6Kbps和56Kbps,速度越来越快。b.误码率衡量数据通信系统在正常工作情况下传输可靠性的指标，指的是二进制码元传输出错的概率。如收到100000个码元，经检查后发现有一个错了，则误码率为十万分之一。c.信道容量表示一个信道的传输能力，对数字信号用数据传输速率作为指标，是以信道每秒钟能传输的比特为单位的，记为比特/秒或位/秒。7．网络的体系结构OSI的七层体系结构：应用层表示层会话层运输层网络层数据链路层物理层8．局域网的工作方式通常有两种：·客户机/服务器(Client/Server):提供资源并管理资源的计算机称为服务器；使用共享资源的计算机称客户机；·对等(Peer-to-Peer):不使用服务器来管理网络共享资源，所以的计算机处于平等的地位9．Internet的形成与发展又