信息学竞赛初赛信息学竞赛初赛 复习.ppt

考试纲要初赛 一 计算机的基本常识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 文件操作 从文本文件中读入数据 并输出到文本文件中 二 程序设计 仿生机器人 模仿生物的身体结构和功能 从事生物特点工作的仿生机器人 有望代替传统的工业机器人 成为未来机器人领域的发展方向 正在此间举行的 机器人学与仿生学国际学术会议 上 与会的机器人学专家这样表示 专家普遍认为 当前工业机器人应用最为广泛 一些典型品种如焊接 装配 喷漆 搬运机器人等 从事专门劳动 方式单一 缺乏变化 主要用于代替工人完成枯燥 乏味而又劳累的流水线工作 难免给人一副 冷冰冰 的面孔 随着人类社会的进步 机器人需要真正意义的走出工厂 进入百姓家庭 广泛用于生活 娱乐和教育中 而活动方式和身体结构酷似动物的仿生机器人显得更加聪明 灵活 也更易被人们所接受 专家认为 仿生机器人只是根据不同人的特殊需要而设计特殊的生物功能 即使在遥远的将来 也不能按照同一模式批量生产 目前由于社会需要还不充分 难免被人们视为 不实用 但是在这种机器人身上体现的技术 可以为其他领域的潜在技术需要做好准备 即其他领域如果需要用到仿生机器人研究中已经成熟的相关技术 直接拿过去就可以了 所以 仿生机器人必将是超出人类一般需求之前探索的一门真正的前沿科学 蓝牙是一种支持设备短距离通信 一般是10m之内 的无线电技术 能在包括移动电话 pda 无线耳机 笔记本电脑 相关外设等众多设备之间进行无线信息交换 蓝牙的标准是ieee802 15 工作在2 4ghz频带 带宽为1mb s 蓝牙 bluetooth 原是一位在10世纪统一丹麦的国王 他将当时的瑞典 芬兰与丹麦统一起来 用他的名字来命名这种新的技术标准 含有将四分五裂的局面统一起来的意思 蓝牙技术使用高速跳频 fh frequencyhopping 和时分多址 tdma timedivesionmuli access 等先进技术 在近距离内最廉价地将几台数字化设备 各种移动设备 固定通信设备 计算机及其终端设备 各种数字数据系统 如数字照相机 数字摄像机等 甚至各种家用电器 自动化设备 呈网状链接起来 蓝牙技术将是网络中各种外围设备接口的统一桥梁 它消除了设备之间的连线 取而代之以无线连接 蓝牙是一种短距的无线通讯技术 电子装置彼此可以透过蓝牙而连接起来 省去了传统的电线 透过芯片上的无线接收器 配有蓝牙技术的电子产品能够在十公尺的距离内彼此相通 传输速度可以达到每秒钟1兆字节 以往红外线接口的传输技术需要电子装置在视线之内的距离 而现在有了蓝牙技术 这样的麻烦也可以免除了 把图片 铃声输到手机里1 先通过网络寻找想放到手机的图片或铃声 然后用鼠标右击图片 选择传送 bluetooth 手机名称 2 很快地 电脑会找到手机 并且自动把图片或铃声文档传到手机上 奥赛辅导讲座二一 算法及算法的特点 算法概念 计算机对问题的求解过程是通过一系列命令来完成的 这种为了完成某个任务而编写的命令的有序集合 我们称之为程序 在设计程序过程中需要考虑对问题求解的方法和步骤 对问题求解的过程和步骤 我们称之为算法 算法的优劣将影响程序运行的效率和执行的结果 算法的特点 确定性 有穷性 可行性 输入 输出3算法的评估 算法的评估 算法的复杂性 1 时间复杂性 牵涉方面比较多 有机器 有语言 问题解决的规模等 若在相同条件下 则取决于算法的优劣 例如 一般用乘法计算t n o n3 forx 1tondofory 1tondobeginc x y 0 fork 1tondoc x y c x y a x k b k y end 算法中基本操作重复执行的次数是问题规模n的某个函数f n 时间度量t n o f n 时间取决于n和f n 时间复杂性 o 1 o logn o n o nlogn o n2 o n3 o 2n 指数级所花费的时间最长 2 空间复杂性 s n o f n 空间复杂性 所占用内存空间的多少 一般指所用的变量数 若用递归程序设计 则当递归调用层次太多 也会造成栈溢出 例题 h数的算法问题 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 前者为小根堆 后者为大根堆 堆是一棵完全二叉树 堆排序 建堆和利用堆排序数据结构书的201 204页 建堆的过程 筛运算排序过程 初赛复习三问题求解与分析一 问题求解题一般解决方法 1 分析题意 了解条件与求解的问题2 根据题意 由特殊 个别 推导出问题求解的一般规律或公式 个别到一般的归纳分析 3 根据公式或规律求出问题解答结果二 掌握基本数据结构知识和基本算法 四 问题分析与解答 1 平面上有三条平行直线 每条直线上分别有8 5 7个点 且不同直线上三个点都不在同一条直线上 问用这些点为顶点 能组成多少个不同的三角形 2 剪纸片 把一张纸剪成6块 从所得的纸片中取出若干块 每块各剪成6块 再从所得的纸片中取出若干块 每块各剪成6块 如此进行下去 到剪完某一次后停止 问所得纸片总数有可能是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共五个车厢 其中每个车厢可以向左行走 也可以进入栈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种不同排列 7 已知一棵二叉树的结点名为大写英文字母 其中序与后序遍历的顺序分别为 cbgeafhdij与cgebhfjida则该二叉树的先序遍历的顺序为 8 平面上有三条平行直线 每条直线上分别有7 5 6个点 且不同直线上三个点都不在同一条直线上 问用这些点为顶点 能组成多少个不同四边形 7 答 该二叉树先序遍历的顺序为 abcegdfhij8 答 这些点为顶点 能组成2250个不同四边形 9 已知一棵度为m的树中有n1个度为1的结点 n2个度为2的结点 nn个度为m的结点 问该树有多少个叶子结点 10 在a b c d e f六件物品中 按下面的条件能选出的物品是 1 a b两样至少有一样 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 ib n 1c n i 1d 不确定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 fb a c f e b dc a e b c f dd 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 都满足un 2 un 1 un 试对数列12 22 32 n2 求k和a1 a2 ak使得 a 式成立 15 将ln定义为求在一个平面中用n条直线所能确定的最大区域数目 例如 当n 1时 l1 2 进一步考虑 用n条折成角的直线 角度任意 放在平面上 能确定的最大区域数目zn是多少 例如 当n 1时 z1 2 如下图所示 当给出n后 请写出以下的表达式 ln 1 zn 2 高精度计算一 高精度计算问题高精度计算中需要处理好以下几个问题 1 数据的接收方法和存贮方法数据的接收和存贮 当输入的数很长时 可采用字符串方式输入 这样可输入数字很长的数 利用字符串函数和操作运算 将每一位数取出 存入数组中 另一种方法是直接用循环加数组方法输入数据 2 计算结果位数的确定位数的确定 利用对数函数 l trunc log x log 10 1 定义数组 3 进位 借位处理进位 借位处理 加法进位 i i i 若 i 则 i i i i 减法借位 若 i i 则 i i i i i i 乘法进位 i i div i 4 商和余数的求法商和余数处理 视被除数和除