《信息学竞赛初赛信息学竞赛初赛 复习》由会员分享，可在线阅读，更多相关《信息学竞赛初赛信息学竞赛初赛 复习（29页珍藏版）》请在金锄头文库上搜索。
1、考试纲要考试纲要初赛：初赛：一、计算机的基本常识一、计算机的基本常识1计计算算机机和和信信息息社社会会（信信息息社社会会的的主主要要特特征征、计计算算机机的的主要特征、数字通信网络的主要特征、数字化）主要特征、数字通信网络的主要特征、数字化）2信信息息输输入入输输出出基基本本原原理理（信信息息交交换换环环境境、文文字字图图形形多多媒体信息的输入输出方式）媒体信息的输入输出方式）3信信息息的的表表示示与与处处理理（信信息息编编码码、微微处处理理部部件件MPU、内内存存储储结结构构、指指令令，程程序序，和和存存储储程程序序原原理理、程程序序的的三三种基本控制结构）种基本控制结构）4信信息息的的存存
2、储储、组组织织与与管管理理（存存储储介介质质、存存储储器器结结构构、文件管理、数据库管理）文件管理、数据库管理）5信信息息系系统统组组成成及及互互连连网网的的基基本本知知识识（计计算算机机构构成成原原理理、槽槽和和端端口口的的部部件件间间可可扩扩展展互互连连方方式式、层层次次式式的的互互连连结结构构、互互联联网网络络、TCP/IP协协议议、HTTP协协议议、WEB应应用用的的主要方式和特点）主要方式和特点）6人人机机交交互互界界面面的的基基本本概概念念（窗窗口口系系统统、人人和和计计算算机机交流信息的途径（文本及交互操作）交流信息的途径（文本及交互操作）7信息技术的新发展、新特点、新应用等。信
3、息技术的新发展、新特点、新应用等。二、计算机的基本操作二、计算机的基本操作1.Windows和和LINUX的基本操作知识的基本操作知识2.互互联联网网的的基基本本使使用用常常识识（网网上上浏浏览览、搜搜索索和和查查询等）询等）3.常用的工具软件使用（文字编辑、电子邮件收发常用的工具软件使用（文字编辑、电子邮件收发等）等） 三、程序设计的基本知识三、程序设计的基本知识1、数据结、数据结构：构： (1)程程序序语语言言中中基基本本数数据据类类型型(字字符符、整整数数、长长整整数、浮点数、浮点)(2)浮点运算中的精度和数值比较浮点运算中的精度和数值比较(3)一维数组（串）与线性表一维数组（串）与线性
4、表(4)记录类型（记录类型（PASCAL）2、程序设计的基本知识、程序设计的基本知识（1）结构化程序设计的基本概念）结构化程序设计的基本概念（2）阅读理解程序的基本能力）阅读理解程序的基本能力（3）具具有有将将简简单单问问题题抽抽象象成成适适合合计计算算机机解解决决的的模模型的基本能力型的基本能力（4）具有针对模型设计简单算法的基本能力）具有针对模型设计简单算法的基本能力（5）程序流程描述（自然语言）程序流程描述（自然语言/伪码伪码/NS图图/其他）其他）（6）程序设计语言（程序设计语言（PASCAL/C/C+）3、算法的基本知识、算法的基本知识（1）初等算法（计数、统计、数学运算等）初等算法
5、（计数、统计、数学运算等）（2）排排序序算算法法（冒冒泡泡法法、插插入入排排序序、合合并并排排序序、快速排序）快速排序）（3）查找（顺序查找、二分法）查找（顺序查找、二分法）（4）回溯算法）回溯算法 复赛：复赛：一、数据结一、数据结构构 1 1指针类型指针类型 2 2多维数组多维数组 3 3单链表及循环链表单链表及循环链表 4 4二叉树二叉树 5 5文文件件操操作作（从从文文本本文文件件中中读读入入数数据据，并并输输出出到文本文件中）到文本文件中） 二、程序设计二、程序设计仿生机器人仿生机器人“模模仿仿生生物物的的身身体体结结构构和和功功能能，从从事事生生物物特特点点工工作作的的仿仿生生机机器
6、器人人，有有望望代代替替传传统统的的工工业业机机器器人人，成成为为未未来来机机器器人人领领域域的的发发展展方方向向。”正正在在此此间间举举行行的的“机机器器人人学学与与仿仿生生学学国国际际学学术术会会议议”上上，与与会会的的机机器器人人学学专家这样表示。专家这样表示。专家普遍认为，当前工业机器人应用最为广泛，一些典专家普遍认为，当前工业机器人应用最为广泛，一些典型品种如焊接、装配、喷漆、搬运机器人等，从事专门劳型品种如焊接、装配、喷漆、搬运机器人等，从事专门劳动，方式单一、缺乏变化，主要用于代替工人完成枯燥、动，方式单一、缺乏变化，主要用于代替工人完成枯燥、乏味而又劳累的流水线工作，难免给人一
7、副乏味而又劳累的流水线工作，难免给人一副“冷冰冰冷冰冰”的的面孔。随着人类社会的进步，机器人需要真正意义的走出面孔。随着人类社会的进步，机器人需要真正意义的走出工厂，进入百姓家庭，广泛用于生活、娱乐和教育中。而工厂，进入百姓家庭，广泛用于生活、娱乐和教育中。而活动方式和身体结构酷似动物的仿生机器人显得更加聪明、活动方式和身体结构酷似动物的仿生机器人显得更加聪明、灵活，也更易被人们所接受。灵活，也更易被人们所接受。专专家家认认为为，仿仿生生机机器器人人只只是是根根据据不不同同人人的的特特殊殊需需要要而而设设计计特特殊殊的的生生物物功功能能，即即使使在在遥遥远远的的将将来来，也也不不能能按按照照同
8、同一一模模式式批批量量生生产产。目目前前由由于于社社会会需需要要还还不不充充分分，难难免免被被人人们们视视为为“不不实实用用”，但但是是在在这这种种机机器器人人身身上上体体现现的的技技术术，可可以以为为其其他他领领域域的的潜潜在在技技术术需需要要做做好好准准备备，即即其其他他领领域域如如果果需需要要用用到到仿仿生生机机器器人人研研究究中中已已经经成成熟熟的的相相关关技技术术，直直接接拿拿过过去去就就可可以以了了。所所以以，仿仿生生机机器器人人必必将将是是超超出出人人类类一一般般需需求求之前探索的一门真正的前沿科学。之前探索的一门真正的前沿科学。蓝蓝牙牙是是一一种种支支持持设设备备短短距距离离通
9、通信信（一一般般是是10m之之内内）的的无无线线电电技技术术。能能在在包包括括移移动动电电话话、PDA、无无线线耳耳机机、笔笔记记本本电电脑脑、相相关关外外设设等等众众多多设设备备之之间间进进行行无无线线信信息息交交换换。蓝蓝牙牙的的标标准准是是IEEE802.15，工工作作在在2.4GHz频频带带，带带宽宽为为1Mb/s。“蓝蓝牙牙”（Bluetooth）原原是是一一位位在在10世世纪纪统统一一丹丹麦麦的的国国王王，他他将将当当时时的的瑞瑞典典、芬芬兰兰与与丹丹麦麦统统一一起起来来。用用他他的的名名字字来来命命名名这这种种新新的的技技术术标标准准，含含有有将将四四分分五五裂裂的的局局面面统统
10、一一起起来来的的意意 思思 。 蓝蓝 牙牙 技技 术术 使使 用用 高高 速速 跳跳 频频 （ FH， FrequencyHopping）和和时时分分多多址址（TDMA，Time DivesionMuliaccess）等等先先进进技技术术，在在近近距距离离内内最最廉廉价价地地将将几几台台数数字字化化设设备备（各各种种移移动动设设备备、固固定定通通信信设设备备、计计算算机机及及其其终终端端设设备备、各各种种数数字字数数据据系系统统，如如数数字字照照相相机机、数数字字摄摄像像机机等等，甚至各种家用电器、自动化设备）呈网状链接起来。甚至各种家用电器、自动化设备）呈网状链接起来。蓝蓝牙牙技技术术将将是
11、是网网络络中中各各种种外外围围设设备备接接口口的的统统一一桥桥梁梁，它它消除了设备之间的连线，取而代之以无线连接。消除了设备之间的连线，取而代之以无线连接。 蓝牙是一种短距的无线通讯技术，电子装置彼此可以蓝牙是一种短距的无线通讯技术，电子装置彼此可以透过蓝牙而连接起来，省去了传统的电线。透过芯片上的透过蓝牙而连接起来，省去了传统的电线。透过芯片上的无线接收器，配有蓝牙技术的电子产品能够在十公尺的距无线接收器，配有蓝牙技术的电子产品能够在十公尺的距离内彼此相通，传输速度可以达到每秒钟离内彼此相通，传输速度可以达到每秒钟1兆字节。以往兆字节。以往红外线接口的传输技术需要电子装置在视线之内的距离，红
12、外线接口的传输技术需要电子装置在视线之内的距离，而现在有了蓝牙技术，这样的麻烦也可以免除了。而现在有了蓝牙技术，这样的麻烦也可以免除了。把图片、铃声输到手机里把图片、铃声输到手机里1、先先通通过过网网络络寻寻找找想想放放到到手手机机的的图图片片或或铃铃声声，然然后后用鼠标右击图片，选择传送用鼠标右击图片，选择传送Bluetooth手机名称；手机名称；2、很很快快地地，电电脑脑会会找找到到手手机机，并并且且自自动动把把图图片片或或铃铃声文档传到手机上；声文档传到手机上；奥赛辅导讲座二奥赛辅导讲座二一、算法及算法的特点：一、算法及算法的特点：1算法概念：算法概念：计算机对问题的求解过程是通过一系列
13、命令来完成计算机对问题的求解过程是通过一系列命令来完成的，这种为了完成某个任务而编写的命令的有序集合，的，这种为了完成某个任务而编写的命令的有序集合，我们称之为程序。在设计程序过程中需要考虑对问题我们称之为程序。在设计程序过程中需要考虑对问题求解的方法和步骤，对问题求解的过程和步骤，我们求解的方法和步骤，对问题求解的过程和步骤，我们称之为算法。算法的优劣将影响程序运行的效率和执称之为算法。算法的优劣将影响程序运行的效率和执行的结果。行的结果。2算法的特点：算法的特点：确定性、有穷性、可行性、输入、输出确定性、有穷性、可行性、输入、输出3算法的评估：算法的评估：算法的评估：算法的复杂性算法的评估
14、：算法的复杂性（1）时间复杂性：牵涉方面比较多，有机器、有语言、问）时间复杂性：牵涉方面比较多，有机器、有语言、问题解决的规模等，若在相同条件下，则取决于算法的优劣。题解决的规模等，若在相同条件下，则取决于算法的优劣。例如：一般用乘法计算例如：一般用乘法计算T(n)=O(n3)forx:=1tondofory:=1tondobegincx,y:=0;fork:=1tondocx,y:=cx,y+ax,k*bk,yend;算法中基本操作重复执行的次数是问题规模算法中基本操作重复执行的次数是问题规模N的某个函数的某个函数F(n)，时间度量时间度量T(n)=O(f(n),时间取决于时间取决于n和和f
15、(n).时间复杂性：时间复杂性：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)=1N=1）都都满满足足U U n+2n+2 =U=Un+1n+1+U+Un n 。试试对对数数列列1 12 2，2 22 2，3 32 2，n n2 2, ,求求K K和和a a1 1,a,a2 2, , ,a,aK K使得（使得（A A）式成立。）式成立。1515、将将LnLn定定义义为为求求在在一一个个平平面面中中用用n n条条直直线线所所能能确确定定的的最最大大区区域域数数目目。例例如如：当当n=1n=1时时，L1=2,L1=2,进进一一步步考考虑虑，用用n n条条折折成成角角的的直直线线
16、（角角度度任任意意），放放在在平平面面上上，能能确确定定的的最最大大区域数目区域数目ZnZn是多少？例如：当是多少？例如：当n=1n=1时，时，Z1=2Z1=2（如下图所示）（如下图所示） 当给出当给出n n后，请写出以下的表达式：后，请写出以下的表达式：LnLn = _ 1 _ = _ 1 _Zn = _ 2 _ Zn = _ 2 _ 高精度计算高精度计算一、高精度计算问题一、高精度计算问题高精度计算中需要处理好以下几个问题：高精度计算中需要处理好以下几个问题：( 1 ) ( 1 ) 数据的接收方法和存贮方法数据的接收方法和存贮方法 数数据据的的接接收收和和存存贮贮：当当输输入入的的数数很很
17、长长时时, ,可可采采用用字字符符串串方方式式输输入入，这这样样可可输输入入数数字字很很长长的的数数, ,利利用用字字符符串串函函数数和和操操作作运运算算, ,将将每每一一位位数数取取出出，存存入入数数组组中中。另另一一种种方方法法是是直直接接用用循循环环加加数数组组方方法法输输入入数据。数据。( 2 ) ( 2 ) 计算结果位数的确定计算结果位数的确定位数的确定：利用对数函数位数的确定：利用对数函数L=truncL=trunc(log(x)/log(10)+1,(log(x)/log(10)+1,定定义义数数组组 ; ;( 3 ) ( 3 ) 进位、借位处理进位、借位处理进位、借位处理：进位
18、、借位处理：加法进位：加法进位：I:= I:= IIII，若，若II则则II：I-I-，I+I+ ： I+I+减法借位：减法借位： 若若IIII则则II ： I I II：II，II：II 乘法进位：乘法进位： ：IIII，：，： DIV DIV II： （4 4） 商和余数的求法商和余数的求法商和余数处理：视被除数和除数的位数情况进商和余数处理：视被除数和除数的位数情况进行处理。行处理。 例题例题1 1、高精度乘法运算。、高精度乘法运算。分析：分析： (1) (1) 数据的接收用字符串方式数据的接收用字符串方式 ； (2) (2) 位位数数的的确确定定：设设被被乘乘数数为为，乘乘数数为为，它
19、它们们的的位位数数分分别别是是，所所以以积积的的位位数数最最长长是是：；完善程序题解题方法完善程序题解题方法一、完善程序题解题步骤：一、完善程序题解题步骤：1、仔细阅读文字解释，理解题意和提供的解题思路、仔细阅读文字解释，理解题意和提供的解题思路2、根据问题的求解要求，了解输入、输出内容和问题处、根据问题的求解要求，了解输入、输出内容和问题处理方法理方法3、先阅读主程序，了解输出变量和输出要求以及主程序、先阅读主程序，了解输出变量和输出要求以及主程序中需要调用的过程或函数是哪些。中需要调用的过程或函数是哪些。4、阅读过程或函数，了解其完成的功能、阅读过程或函数，了解其完成的功能5、填空方法：一般从主程序最后输出要求，反推主程序、填空方法：一般从主程序最后输出要求，反推主程序中的变量填写或表达式、语句等的书写中的变量填写或表达式、语句等的书写
