信息学奥赛基础知识.ppt

初赛复习 一 计算机的两位重要人物图灵 被称为 人工智能之父 1966年设立的图灵奖是计算机界最负盛名的奖项 有 计算机界诺贝尔奖 之称冯 诺依曼 被称为 计算机之父 他的精髓贡献是2点 2进制思想与程序内存思想 1 在下面各世界顶级的奖项中 为计算机科学与技术领域作出杰出贡献的科学家设立的奖项是 2006 A 沃尔夫奖B 诺贝尔奖C 菲尔兹奖D 图灵奖E 南丁格尔奖2 美籍匈牙利数学家冯 诺依曼对计算机科学发展所做出的贡献包括 2004 A 提出理想计算机的数学模型 成为计算机科学的理论基础 B 提出存储程序工作原理 对现代电子计算机的发展产生深远影响 C 设计出第一台具有存储程序功能的计算机EDVAC D 采用集成电路作为计算机的主要功能部件 E 指出计算机性能将以每两年翻一番的速度向前发展 D BC 二 计算机的组成 冯 诺依曼提出的计算机系统由五大部分组成 并一直沿用至今 运算器 完成运算的算术逻辑单元 ALU 和存放操作数和运算结果的寄存器 控制器 全机的指挥中心 负责象整个电脑各个部分发出命令 存储器 内存储器 只读存储器ROM和随机存储器RAM 和外存储器 硬盘 u盘 光盘 输入设备 鼠标 键盘 麦克风 数码相机 扫描仪 输出设备 显示器 打印机 音箱 投影仪等 1 在以下各项中 不是CPU的组成部分 2006 A 控制器B 运算器C 寄存器D ALUE RAM2 BIOS 基本输入输出系统 是一组固化在计算机内 上一个ROM芯片上的程序 2006 A 控制器B CPUC 主板D 内存条E 硬盘3 以下断电之后将不能保存数据的有 2006 A 硬盘B ROMC 显存D RAM4 以下哪个 些 不是计算机的输出设备 2005 A 鼠标B 显示器C 键盘D 扫描仪E 绘图仪5 以下断电之后将不能保存数据的有 2005 A 硬盘B 寄存器C 显存D 内存E 高速缓存6 下列哪个 些 不是计算机的存储设备 2004 A 文件管理器B 内存C 显卡D 硬盘E U盘 E C CD ACDE BCDE AC 三 进制转换 二进制数转换成十进制数 按权展开求和例 将二进制数1011 01转换成十进制数 1011 01 2 1 23 0 22 1 21 1 20 0 2 1 1 2 2 10 二进制数转换成八进制数 由于一位八进制数对应位二进制数 所以二进制数转换成八进制数时 只要以小数点为界 整数部分向左 小数部分向右每3位分为一组 各组用对应的1位八进制数字表示 即可得到对应的八进制数值 最左最右端分组不足3位时 可用0补足 例 将二进制数1101101 10101转换为对应的八进制数001101101 101010 1 5 5 5 2 所以 1101101 10101 2 155 52 8 二进制数转换成十六进制数 和二进制数转换成八进制数类似 只不过分组的时候是四位为一组 例 将二进制数1101101 10101转换为对应的十六进制数01101101 10101000 6 D A 8 所以 1101101 10101 2 6D A8 16 注 八 十六进制数转换成二进制数过程与此两过程相反 十进制数转换成二进制数 对于整数部分 用被除数反复除以2 除第一次外 每次除以2均取前一次商的整数部分作为被除数并依次记下每次的余数 另外 所得到的商的最后一位余数是所求二进制数的最高位 例 将十进制数117 625转换成二进制数 整数部分 除2取余 逆序输出 小数部分 乘2取整 顺序输出 所以 117 625 10 1110101 101 2 1 以下二进制数的值与十进制数23 456的值最接近的是 2005 A 10111 0101B 11011 1111C 11011 0111D 10111 0111E 10111 11112 3725 8 B 16的运算结果是 2005 A 3736 8B 2016 10C 11111100000 2D 3006 10E 7E0 163 与十进制数1770 625对应的八进制数是 2006 A 3352 5B 3350 5C 3352 1161D 3350 1151E 前4个答案都不对4 2010 16 32 8的结果是 2006 A 8234 10B 202A 16C 100000000110 2D 2042 16 D BCE AB A 四 逻辑运算 与运算 运算符号通常为And 或 0 0 00 1 01 0 01 1 1假 假 假假 真 假真 假 假真 真 真 或运算 运算符号通常为Or 或 0 0 00 1 11 0 11 1 1假 假 假假 真 真真 假 真真 真 真 非运算 运算符号通常为Not 或 0 1 1 0 假 真 真 假 异或运算 运算符号通常为Xor0 xor0 00 xor1 01xor0 01xor1 1假xor假 假假xor真 真真xor假 真真xor真 假 逻辑运算中运算符号的优先级为 not and or 1 设A B D true C E false 以下逻辑运算表达式值为真的有 2006 A A B C D EB A B C D E C A B C D E D A B C D E2 设A true B false C false D true 以下逻辑运算表达式值为真的有 2005 A A B D C B B A C DC A B C D D A B C DE A B C D 3 在Pascal语言中 表达式 21xor2 的值是 2006 A 441B 42C 23D 24E 25 ABC CDE C 栈的定义 栈是一种特殊的表这种表只在表头进行插入和删除操作 因此 表头对于栈来说具有特殊的意义 称为栈顶 相应地 表尾称为栈底 不含任何元素的栈称为空栈 栈的逻辑结构 假设一个栈S中的元素为an an 1 a1 则称a1为栈底元素 an为栈顶元素 栈中的元素按a1 a2 an 1 an的次序进栈 在任何时候 出栈的元素都是栈顶元素 换句话说 栈的修改是按后进先出的原则进行的 如图1所示 因此 栈又称为后进先出 LastInFirstOut 表 简称为LIFO表 所以 只要问题满足LIFO原则 就可以使用栈 四 栈 历年奥赛试题 2006 2004 7 某个车站呈狭长形 宽度只能容下一台车 并且只有一个出入口 已知某时刻该车站状态为空 从这一时刻开始的出入记录为 进 出 进 进 进 出 出 进 进 进 出 出 假设车辆入站的顺序为1 2 3 则车辆出站的顺序为 c A 1 2 3 4 5B 1 2 4 5 7C 1 4 3 7 6D 1 4 3 7 2E 1 4 3 7 5 2006 13 设栈S的初始状态为空 元素a b c d e依次入栈 以下出栈序列不可能出现的有 A a b c e dB b c a e dC a e c b dD d c e b a 2005 多项 14 设栈S的初始状态为空 元素a b c d e f g依次入栈 以下出栈序列不可能出现的有 A a b c e d f gB b c a f e g dC a e c b d f gD d c f e b a gE g e f d c b a 2003 19 已知元素 8 25 14 87 5l 90 6 19 20 问这些元素以怎样的顺序进入栈 才能使出栈的顺序满足 8在5l前面 90在87后面 20在14后面 25在6前面 19在90后面 A 20 6 8 51 90 25 14 19 87B 51 6 19 20 14 8 87 90 25C 19 20 90 7 6 25 5l 14 87D 6 25 51 8 20 19 90 87 14E 25 6 8 51 87 90 19 14 20 队列的定义 队列是一种特殊的线性表 对这种线性表 删除操作只在表头 称为队头 进行 插入操作只在表尾 称为队尾 进行 队列的修改是按先进先出的原则进行的 所以队列又称为先进先出 FirstInFirstOut 表 简称FIFO表 队列的数学性质 假设队列为a1 a2 an 那么a1就是队头元素 an为队尾元素 队列中的元素是按a1 a2 an的顺序进入的 退出队列也只能按照这个次序依次退出 也就是说 只有在a1离开队列之后 a2才能退出队列 只有在a1 a2 an 1都离开队列之后 an才能退出队列 图1是队列的示意图 五 队列 历年奥赛试题 2003 6 已知队列 13 2 11 34 4l 77 5 7 18 26 15 第一个进入队列的元素是13 则第五个出队列的元素是 A 5B 41C 77D 13E 18 2002 20 设找栈S和队列Q的初始状态为空 元素e1 e2 e3 e4 e5 e6依次通过栈S 一个元素出栈后即进入队列Q 若出队的顺序为e2 e4 e3 e6 e5 e1 则栈S的容量至少应该为 A 2B 3C 4D 5 1 树的概念树的递归定义如下 1 至少有一个结点 称为根 2 其它是互不相交的子树 1 树的度 也即是宽度 简单地说 就是结点的分支数 以组成该树各结点中最大的度作为该树的度 如上图的树 其度为3 树中度为零的结点称为叶结点或终端结点 树中度不为零的结点称为分枝结点或非终端结点 除根结点外的分枝结点统称为内部结点 2 树的深度 组成该树各结点的最大层次 如上图 其深度为4 六 树 2 二叉树二叉树的基本形态 二叉树也是递归定义的 其结点有左右子树之分 逻辑上二叉树有五种基本形态 1 空二叉树 a 2 只有一个根结点的二叉树 b 3 右子树为空的二叉树 c 4 左子树为空的二叉树 d 5 完全二叉树 e 3 两种重要的树 1 完全二叉树 只有最下面的两层结点度小于2 并且最下面一层的结点都集中在该层最左边的若干位置的二叉树 2 满二叉树 除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树 如下图 4 二叉树的性质 1 在二叉树中 第i层的结点总数不超过2 i 1 2 深度为h的二叉树最多有2h 1个结点 h 1 最少有h个结点 3 对于任意一棵二叉树 如果其叶结点数为N0 而度数为2的结点总数为N2 则N0 N2 1 历年奥塞试题 2006 8 高度为n的均衡的二叉树是指 如果去掉叶结点及相应的树枝 它应该是高度为n 1的满二叉树 在这里 树高等于叶结点的最大深度 根结点的深度为0 如果某个均衡的二叉树共有2381个结点 则该树的树高为 A 10B 11C 12D 13E 2 1 2005 4 完全二叉树的结点个数为4 N 3 则它的叶结点个数为 A 2 NB 2 N 1C 2 N 1D 2 N 2E 2 N 2 2004 满二叉树的叶结点个数为N 则它的结点总数为 NB 2 NC 2 N 1D 2 N 1E 2N 1 2002 17 按照二叉树的定义 具有3个结点的二叉树有 种 A 3B 4C 5D 6 C C B E 5 树的遍历第一种分法 前序遍历中序遍历后序遍历也称为 前根遍历 中根遍历 后根遍历 第二种分法 深度优先遍历和广 宽 度优先遍历 对于右边一棵二叉树的遍历分别为 前序遍历为 ABDHECFIGJ中序遍历为 DHBEAIFCJG后序遍历为 HDEBIFJGCA深度优先遍历为 ABDHECFIGJ广度优先遍历为 ABCDEFGHIJ 历年奥赛试题 2006 多项 14 已知6个结点的二叉树的先根遍历是123456 数字为结点的编号 以下同 后根遍历是325641 则该二叉树的可能的中根遍历是 A 321465B 321546C 231546D 231465 2005 多项 13 二叉树T的宽度优先遍历序列为ABCDEFGHI 已知A是C的父结点 D是G的父结点 F是I的父结点 树中所有结点的最大深度为3 根结点深度设为0 可知E的父结点可能是 A AB BC CD DE F 2004 二叉树T 已知其前序遍历序列为1243576 中序遍历序列为4215736 则其后序遍历序列为 4257631B 4275631C 4275361D 4723561E 4526371 BC BC B