信息学竞赛初赛信息学竞赛初赛 复习一.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 文件操作 从文本文件中读入数据 并输出到文本文件中 二 程序设计 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 信息浏览 www 2 文件传输 ftp 3 发送接收电子邮件 e mail 4 电子公告牌 bbs 5 远程登录 telnet 6 电子商务4 网址的结构 http 超文本浏览协议 www sina 表示主机域名 com 网络机构域名 这里是商业网 cn 地区域名 这里是中国域名 5 电子邮件的地址 zhangming 这里zhangming是用户 是分隔符号 yahoo主机名 雅虎 com是域名 url 统一资源定位器 用来表示网页所在www服务器的名称以及存放的路径 浏览器根据网页的url访问相应的服务器 打开相应的网页 基本格式 协议名或传输方式 服务器名或ip地址 端口号 路径 文件名常见的协议 http超文本传输协议 www服务器 ftp文件传输协议 ftp文件服务器 telnet远程登录协议 telnet公共与注册服务器 常见的传输方式 电子邮件传送方式mailtonntp新闻组传送方式news本机文件传送方式 file注意 服务器域名可以不分大小写 但路径 文件名的大小写要正确ie浏览器默认读取方式是http和www服务器url地址栏可以是字符形式的协议 服务器域名及文件名 也可以是数字形式的ip地址 如上海热线地址 202 96 209 5 每组数字小于256 电脑知识竞赛 万维网是www的中文命名 英语是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的形成与发展又称国际互联网 规范的译名是 因特网 指当前各国 各地区众多开发的网络连接在一起而形成的全球性网络 我国internet的发展情况 八十年代末 九十年代初才起步 1989年我国第一个公用分组交换网cnpac建成运行 我国已陆续建成与internet互联的四个全国范围的公用网络 中国公用计算机互联网 chinanet 中国金桥信息网 chinagbn 中国教育和科研计算机网 cernet 中国科学技术网 cstnet 10 ip地址 把整个internet看作一个单一的 抽象的网络 所谓ip地址 就是为internet中的每一台主机分配一个在全球范围唯一地址 ip地址分a b c d e五类 目前大量使用的是a b c三类 d类为internet体系结构委员会iab专用 e类保留在今后使用 如果一个ip地址aaa的值在1 126之间 表示它属于a类地址 如果aaa的值在128 191之间 表示它属于b类地址 如果aaa的值在192 254之间 表示它属于c类地址 ip地址 4组 每组8位二进制 因此每组值 255 11 域名 dn 域名是由四部分组成 开头 主机名 主机类别 国家名 可以不要 如 域名地址采用层次结构 一个域名一般有3 5个子段 中间用 隔开 顶级域名有三类 国家顶级域名 如cn 中国 us 美国 uk 英国 国际顶级域名 int 国际性组织可在int下注册 通用顶级域名 如 com net edu gov 12 internet的服务与工具internet的服务有 电子邮件 远程登陆 文件传输 信息服务等 远程登陆 telnet 指通过internet与其它主机连接 登陆上另一主机 你就可以使用该主机对外开放的各种资源 如联机检索 数据查询 文件传输 ftp 用于在计算机间传输文件 如下载软件等 全球信息网 www worldwideweb 又称万维网 是一个全球规模的信息服务系统 由遍布于全世界的数以万计的web站点组成 13 ie的用法前进 后退 浏览 收藏夹 搜索 设置主页 编码等 二 计算机病毒计算机病毒 一种人为制造的 在计算机运行中对计算机信息或系统起破坏作用的程序 特点 寄生性 传染性 潜伏性 隐蔽性 破坏性 防范 数据备份 安装防病毒软件 复制文件前先查病毒 不要轻易打开不认识的人寄来的电子邮件 上网时使用防火墙 三 计算机法规软件保护法 随着计算机领域发展的日新月异 软件也越来越多 为了保护知识产权 推出了软件保护法 用来保护软件的著作权 六 网上下载信息的方法 一 复制文本信息二 复制或下载图片信息三 下载网页信息四 下载文件 蓝牙是一种支持设备短距离通信 一般是10m之内 的无线电技术 能在包括移动电话 pda 无线耳机 笔记本电脑 相关外设等众多设备之间进行无线信息交换 蓝牙的标准是ieee802 15 工作在2 4ghz频带 带宽为1mb s 蓝牙 bluetooth 原是一位在10世纪统一丹麦的国王 他将当时的瑞典 芬兰与丹麦统一起来 用他的名字来命名这种新的技术标准 含有将四分五裂的局面统一起来的意思 蓝牙技术使用高速跳频 fh frequencyhopping 和时分多址 tdma timedivesionmuli access 等先进技术 在近距离内最廉价地将几台数字化设备 各种移动设备 固定通信设备 计算机及其终端设备 各种数字数据系统 如数字照相机 数字摄像机等 甚至各种家用电器 自动化设备 呈网状链接起来 蓝牙技术将是网络中各种外围设备接口的统一桥梁 它消除了设备之间的连线 取而代之以无线连接 蓝牙是一种短距的无线通讯技术 电子装置彼此可以透过蓝牙而连接起来 省去了传统的电线 透过芯片上的无线接收器 配有蓝牙技术的电子产品能够在十公尺的距离内彼此相通 传输速度可以达到每秒钟1兆字节 以往红外线接口的传输技术需要电子装置在视线之内的距离 而现在有了蓝牙技术 这样的麻烦也可以免除了 把图片 铃声输到手机里1 先通过网络寻找想放到手机的图片或铃声 然后用鼠标右击图片 选择传送 bluetooth 手机名称 2 很快地 电脑会找到手机 并且自动把图片或铃声文档传到手机上 3 当手机开始接收从电脑传过来的文档时 就会自动出现接收项目中的画面 4 当文档传输完毕时 手机也会自动显示信息 如 sonyericssont160手机会自动判定传入的文档格式 并且将文档分类存入各自的储存空间 若接收的是图片 就会存到我的图片集 而铃声则会存入我的音乐集 提示 想把手机的照片传到电脑上 只要在传送时选择以蓝牙来传送 就可以传给电脑或别的蓝牙手机了 七 计算机中有关数 编码的基本常识1 计算机是智能化的电器设备计算机就其本身来说是一个电器设备 为了能够快速存储 处理 传递信息 其内部采用了大量的电子元件 在这些电子元件中 电路的通和断 电压高低 这两种状态最容易实现 也最稳定 也最容易实现对电路本身的控制 我们将计算机所能表示这样的状态 用0 1来表示 即用二进制数表示计算机内部的所有运算和操作 2 二进制数的运算法则 二进制数运算非常简单 计算机很容易实现 其主要法则是 0 0 00 1 11 0 11 1 0 0 0 00 1 01 0 01 1 1由于运算简单 电器元件容易实现 所以计算机内部都用二进制编码进行数据的传送 计算 1 汉字输入方法汉字输入方法有很多种 大体可以分为 流水码 音码 形码 音形码 1 流水码 区位码 电报码 通讯密码等均属于流水码 优点重码率少 缺点难于记忆 2 音码 以汉语拼音作为编码输入汉字 优点是大多数人都易于掌握 但同音字多 重码率高 影响输入的速度 3 音形码 将音码和形码结合起来 输入汉字 减少重码率 提高汉字输入速度 4 形码 根据汉字的字型进行编码 编码的规则比较多 难于记忆 必须经过训练才能较好地掌握 一个汉字的机内码目前通常用2个字节来表示 第一个字节是区码的区号加 160 10 第二个字节是区位码的位码加 160 10 已知 汉字 却 的区位码是4020 试写出机内码两个字节的二进制的代码 1100100010110100根据题意 正确答案是 却 的机内区码是160 40 200 其二进制代码是 11001000 2 却 的机内位码是160 20 180 其二进制代码是 10110100 2如果用一个字节来表示整数 最高位用作符号位 其它位表示数值 例如 00000001表示 110000001表示 1 符号位表示正 符号位表示负 试问这样表示法的整数a的范围应该是 a 127 a 127 b 128 a 128 c 128 a 128 d 128 a 128根据题意 正确答案选择 a 因为正整数的范围仅能用7位的二进制数表示 由于最高位是零 当后7位全为1时 表示整数127 再加1 需要进位 则符号位变为1 数据发生值的变化 数据由正变为负 而负数道理基本同正数 在这样表示法中 以下 说法是正确的 a 范围内的每一个数都只有唯一的格式 b 范围内每一个数都有两种格式 c 范围内的一半数有两种格式 d 范围内只有一个数有两种表示格式本题正确答案选择 d 这是因为正数 负数都只有唯一的表示格式 而零可以有两种格式即 00000000和10000000 1998年初中基础题第7题 高中组基础第6题 小张用十六进制 八进制和十进制写了如下的一个等式 52 19 33式中三个数是各不相同进位制的数 试问52 19 33 分别为 八进制 十进制 十六进制十进制 十六进制 八进制 c 八进制 十六进制 十进制 d 十进制 八进制 十六进制 如果用一个字节来表示整数 最高位用作符号位 其它位表示数值 例如 符号位表示正 符号位表示负 试问这样表示法的整数a的范围应该是 a 127 a 127 b 128 a 128 c 128 a 128 d 128 a 128 表示 1表示 1 在这样表示法中 以下 说法是正确的 a 范围内的每一个数都只有唯一的格式 b 范围内每一个数都有两种格式 c 范围内的一半数有两种格式 d 范围内只有一个数有两种表示格式计算机中的数有浮点与定点数两种 其中用浮点数表示的数 通常由 这两部分组成 a指数与基数b尾数与小数c阶码与尾数d整数与小数习题 十进制算术表达式 3 512 7 64 4 8 5的运算结果 用二进制表示为 a10111100101b11111100101c11110100101d11111101101 十进制与二进制 八进制 十六进制数之间的相互转换 1 数的进制与基数计数的进制不同 则它们的基数也不相同 如表1 1所示 八 数据结构的基本知识 一 线性表的知识线性表的定义线性表的存储结构 1 顺序结构 数组 按照下标顺序存储 2 链表结构 利用指针将结点链接起来3 线性表的特点 只有一个直接前驱和一个直接后继4 特殊线性表 1 栈 先进后出 filo 2 队列 先进先出 fifo 5 递归程序执行过程 调用过程时将变量和返回地址存入栈变量区称为进栈 返回调用的程序时 根据栈顶地址返回 并将变量返回调用程序中 队列的操作 一般用于图的遍历 广度优先遍历方法访问一个结点 或输出 删除该结点 出队 并将其后继结点全部进队 入队 再访问下一个结点 将其后继结点进队栈和队列在编程中最好用数组实现 二 二叉树的基本知识1 二叉树的定义 空树或由一个根结点和两棵互不相交的分别称为左子树和右子