信息技术奥林匹克竞赛复习纲要.ppt

1、4信息的存储、组织与管理（存储介质、存储器结构、文件管理、数据库管理） 5信息系统组成及互连网的基本知识（计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP协议、HTTP协议、WEB应用的主要方式和特点） 6人机交互界面的基本概念（窗口系统、人和计算机交流信息的途径（文本及交互操作） 7信息技术的新发展、新特点、新应用等。,二、计算机的基本操作 1. Windows和LINUX的基本操作知识 2. 互联网的基本使用常识 （网上浏览、搜索和查询等） 3. 常用的工具软件使用（文字编辑、电子邮件收发等） 三、程序设计的基本知识 1、数据结构：,(1) 程序语言

2、中基本数据类型(字符、整数、长整数、浮点) (2) 浮点运算中的精度和数值比较 (3) 一维数组（串）与线性表 (4) 记录类型（PASCAL） 2、程序设计的基本知识 （1）结构化程序设计的基本概念 （2）阅读理解程序的基本能力 （3）具有将简单问题抽象成适合计算机解决的模型的基本能力,（4）具有针对模型设计简单算法的基本能力 （5）程序流程描述（自然语言/伪码/NS图/其他） （6）程序设计语言（PASCAL/C/C+） 3、算法的基本知识 （1）初等算法（计数、统计、数学运算等） （2）排序算法（冒泡法、插入排序、合并排序、快速排序） （3）查找（顺序查找、二分法） （4）回溯算法,复赛

3、： 一、数据结构 1指针类型 2多维数组 3单链表及循环链表 4二叉树 5文件操作（从文本文件中读入数据，并输出到文本文件中） 二、程序设计,仿生机器人 “模仿生物的身体结构和功能，从事生物特点工作的仿生机器人，有望代替传统的工业机器人，成为未来机器人领域的发展方向。”正在此间举行的“机器人学与仿生学国际学术会议”上，与会的机器人学专家这样表示。 专家普遍认为，当前工业机器人应用最为广泛，一些典型品种如焊接、装配、喷漆、搬运机器人等，从事专门劳动，方式单一、缺乏变化，主要用于代替工人完成枯燥、乏味而又劳累的流水线工作，难免给人一副“冷冰冰”的面孔。随着人类社会的进步，机器人需要真正意义的走出工

4、厂，进入百姓家庭，广泛用于生活、娱乐和教育中。而活动方式和身体结构酷似动物的仿生机器人显得更加聪明、灵活，也更易被人们所接受。,专家认为，仿生机器人只是根据不同人的特殊需要而设计特殊的生物功能，即使在遥远的将来，也不能按照同一模式批量生产。目前由于社会需要还不充分，难免被人们视为“不实用”，但是在这种机器人身上体现的技术，可以为其他领域的潜在技术需要做好准备，即其他领域如果需要用到仿生机器人研究中已经成熟的相关技术，直接拿过去就可以了。所以，仿生机器人必将是超出人类一般需求之前探索的一门真正的前沿科学。,蓝牙是一种支持设备短距离通信（一般是10m之内）的无线电技术。能在包括移动电话、PDA、无

5、线耳机、笔记本电脑、相关外设等众多设备之间进行无线信息交换。蓝牙的标准是IEEE802.15，工作在2.4GHz 频带，带宽为1Mb/s。 “蓝牙”（Bluetooth）原是一位在10世纪统一丹麦的国王，他将当时的瑞典、芬兰与丹麦统一起来。用他的名字来命名这种新的技术标准，含有将四分五裂的局面统一起来的意思。蓝牙技术使用高速跳频（FH，Frequency Hopping）和时分多址（TDMA，Time DivesionMuliaccess）等先进技术，在近距离内最廉价地将几台数字化设备（各种移动设备、固定通信设备、计算机及其终端设备、各种数字数据系统，如数字照相机、数字摄像机等，甚至各种家用电

6、器、自动化设备）呈网状链接起来。,蓝牙技术将是网络中各种外围设备接口的统一桥梁，它消除了设备之间的连线，取而代之以无线连接。 蓝牙是一种短距的无线通讯技术，电子装置彼此可以透过蓝牙而连接起来，省去了传统的电线。透过芯片上的无线接收器，配有蓝牙技术的电子产品能够在十公尺的距离内彼此相通，传输速度可以达到每秒钟1兆字节。以往红外线接口的传输技术需要电子装置在视线之内的距离，而现在有了蓝牙技术，这样的麻烦也可以免除了。 把图片、铃声输到手机里 1、先通过网络寻找想放到手机的图片或铃声，然后用鼠标右击图片，选择传送Bluetooth手机名称； 2、很快地，电脑会找到手机，并且自动把图片或铃声文档传到手

7、机上；,奥赛辅导讲座二 一、算法及算法的特点： 算法概念： 计算机对问题的求解过程是通过一系列命令来完成的，这种为了完成某个任务而编写的命令的有序集合，我们称之为程序。在设计程序过程中需要考虑对问题求解的方法和步骤，对问题求解的过程和步骤，我们称之为算法。算法的优劣将影响程序运行的效率和执行的结果。 算法的特点： 确定性、有穷性、可行性、输入、输出 3 算法的评估：,算法的评估：算法的复杂性 （1）时间复杂性：牵涉方面比较多，有机器、有语言、问题解决的规模等，若在相同条件下，则取决于算法的优劣。 例如：一般用乘法计算 T(n)= O( n3 ) for x:=1 to n do for y:=

8、1 to n do begin cx,y := 0 ; for k:=1 to n do cx,y:= cx,y + a x,k * b k, y end; 算法中基本操作重复执行的次数是问题规模N的某个函数 F(n) ， 时间度量 T(n)= O(f(n) , 时间取决于n和f(n).,时间复杂性： O(1) O(log n) O(n) O(nlog n) O(n2) O(n3) O(2n) 指数级所花费的时间最长 （2）空间复杂性： S(n) = O( f(n) ) 空间复杂性： 所占用内存空间的多少。一般指所用的变量数。若用递归程序设计，则当递归调用层次太多，也会造成栈溢出。 例题： H

9、数的算法问题：H数是指除1以外，最多只有2，3，5，7 四种因子。如630即为H数，而22不是。要求对键盘输入的自然数N，求出第N个H数。如N=30 应输出49。规定要求的H数不超出长整型数的范围。,（6） 堆排序（改进的选择排序） 算法思想： 堆的定义：有一系列元素R1，R2，Rn，对应的排序码为（S1，S2，,Sn），若此排序码序列满足如下情况的一种，则称此序列为堆。 Si S2i 和 Si S2i+1 ( 1 i n/2 ) Si S2i 和 Si S2i+1 ( 1 i n/2 ) 前者为小根堆，后者为大根堆。堆是一棵完全二叉树 堆排序：建堆和利用堆排序 数据结构书的201204 页

10、建堆的过程 筛运算排序过程,初赛复习三 问题求解与分析 一、问题求解题一般解决方法： 1、分析题意，了解条件与求解的问题 2、根据题意，由特殊、个别，推导出问题求解的一般规律或公式（个别到一般的归纳分析） 3、根据公式或规律求出问题解答结果 二、掌握基本数据结构知识和基本算法,（四）、问题分析与解答： 1、平面上有三条平行直线，每条直线上分别有8，5，7个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同的三角形？ 2、剪纸片：把一张纸剪成6块，从所得的纸片中取出若干块，每块各剪成6块；再从所得的纸片中取出若干块，每块各剪成6块如此进行下去，到剪完某一次后停止。问所得

11、纸片总数有可能是2000，2001，2002，2003这四个数中的哪一个数？为什么？,3、在书架上放有编号为1,2,.n的n本书。现将n本书全部取下然后再放回去,当放回去时要求每本书都不能放在原来的位置上。例如:n=3时: 原来位置为:123 放回去时只能为:312或231这两种 问题:求当n=5时满足以上条件的放法共有多少种?(不用列出每种放法) 4、设有一棵k叉树,其中只有度为0和k两种结点,设n0,nk分别表示度为0和度为k的结点个数,试求出n0,nk之间的关系(n0=数学表达式,数学表达式仅含nk,k和数字),5、 如下图,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个

12、车厢。其中每个车厢可以向左行走,也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是3号车厢，请写出所有可能的到达出口的车厢排列总数(不必给出每种排列),6、将N个红球和M个黄球排成一行。例如:N=2,M=3可得到以下10种排法: 红红黄黄黄 红黄红黄黄 红黄黄红黄 黄红红黄黄 黄红黄红黄 黄黄黄红红 问题:当N=4,M=3时有多少种不同排法?(不用列出每种排法) 问题解答： 3、 答：当n=5时，满足以上条件的方法共有44种。 4、 答：n0和nk 之间的关系为：n0=(k-1) nk+ 1 。 5、答：所有可能到达出口的车厢排列总数为 9 。 6、答：当N=4，M=3时有 35 种不同

13、排列。,7、已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：CBGEAFHDIJ 与 CGEBHFJIDA则该二叉树的先序遍历的顺序为： 8、平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形？ 7、答：该二叉树先序遍历的顺序为：ABCEGDFHIJ 8、答：这些点为顶点，能组成2250个不同四边形,9、已知一棵度为m的树中有N1个度为1的结点，N2个度为2的结点，Nn个度为m的结点，问该树有多少个叶子结点？ 10、在a,b,c,d,e,f六件物品中，按下面的条件能选出的物品是： (1)a,b

14、两样至少有一样 (2)a,d不能同时取 (3)a,e,f中必须有2样 (4)b,c要么都选，要么都不选 (5)c,d两样中选一样 (6)若d不选，则e也不选,11、若已知一个栈的入栈顺序是1，2，3，n，其输出序列为P1，P2，P3，Pn，若P1是n，则Pi是( ) A)i B)n-1 C)n-i+1 D)不确定 12、 无向图G=(V，E)，其中V=a,b,c,d,e,f E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d) 对该图进行深度优先遍历,得到的顶点序列正确的是( ) A)a,b,e,c,d,f B)a,c,f,e,b,d C)a,e,b,c,f,

15、d D)a,b,e,d,f,c,14、已知一个数列U1，U2，U3，UN， 往往可以找到一个最小的K值和K个数a1,a2, ,an使得数列从某项开始都满足：UN+K=a1UN+K-1+a2UN+K-2+akUN (A) 例如对斐波拉契数列1，1，2，3，5，可以发现：当K=2，a1 =1，a2 =1时，从第3项起（即N=1）都满足U n+2 =Un+1+Un 。试对数列12，22，32，n2,求K和a1,a2, ,aK使得（A）式成立。,15、将Ln定义为求在一个平面中用n条直线所能确定的最大区域数目。例如：当n=1时，L1=2,进一步考虑，用n条折成角的直线（角度任意），放在平面上，能确定的最大区域数目Zn