信息学奥赛基础知识.ppt

初赛复习初赛复习一、计算机的两位重要人物一、计算机的两位重要人物图灵：被称为“人工智能之父”，1966年设立的图灵奖是计算机界最负盛名的奖项，有“计算机界诺贝尔奖”之称冯冯 诺依曼：诺依曼：被称为“计算机之父”，他的精髓贡献是2点：2进制思想与程序内存思想。1.1.在下面各世界顶级的奖项中，为计算机科学与技术领域作在下面各世界顶级的奖项中，为计算机科学与技术领域作出杰出贡献的科学家设立的奖项是（出杰出贡献的科学家设立的奖项是（）（）（20062006）A.A.沃尔夫奖沃尔夫奖B.B.诺贝尔奖诺贝尔奖C.C.菲尔兹奖菲尔兹奖 D.D.图灵奖图灵奖E.E.南丁格尔奖南丁格尔奖 2.2.美籍匈牙利数学家冯美籍匈牙利数学家冯 诺依曼对计算机科学发展所做出的诺依曼对计算机科学发展所做出的贡献包括（贡献包括（）（）（20042004）A.A.提出理想计算机的数学模型，成为计算机科学的理论基础。提出理想计算机的数学模型，成为计算机科学的理论基础。B.B.提出存储程序工作原理，对现代电子计算机的发展产生深提出存储程序工作原理，对现代电子计算机的发展产生深远影响。远影响。C.C.设计出第一台具有存储程序功能的计算机设计出第一台具有存储程序功能的计算机EDVACEDVAC。D.D.采用集成电路作为计算机的主要功能部件。采用集成电路作为计算机的主要功能部件。E.E.指出计算机性能将以每两年翻一番的速度向前发展。指出计算机性能将以每两年翻一番的速度向前发展。DBC二、计算机的组成二、计算机的组成冯冯 诺依曼提出的计算机系统由五大部分组成，并一诺依曼提出的计算机系统由五大部分组成，并一直沿用至今：直沿用至今：运算器：完成运算的算术逻辑单元（运算器：完成运算的算术逻辑单元（ALUALU）和存）和存放操作数和运算结果的寄存器放操作数和运算结果的寄存器控制器：全机的指挥中心，负责象整个电脑各个控制器：全机的指挥中心，负责象整个电脑各个部分发出命令部分发出命令存储器：内存储器（只读存储器ROM和随机存储器RAM）和外存储器（硬盘，u盘，光盘）输入设备：鼠标，键盘，麦克风，数码相机，扫描仪输出设备：显示器，打印机，音箱，投影仪等1 1、在以下各项中（、在以下各项中（）不是）不是CPUCPU的组成部分。（的组成部分。（20062006）A.A.控制器控制器B.B.运算器运算器C.C.寄存器寄存器D.ALUE.RAMD.ALUE.RAM2.BIOS2.BIOS（基本输入输出系统）是一组固化在计算机内（基本输入输出系统）是一组固化在计算机内（）上一个）上一个ROMROM芯片上的程序（芯片上的程序（20062006）A.A.控制器控制器B.CPUC.B.CPUC.主板主板D.D.内存条内存条E.E.硬盘硬盘 3.3.以下断电之后将不能保存数据的有（以下断电之后将不能保存数据的有（）（）（20062006）A.A.硬盘硬盘B.ROMC.B.ROMC.显存显存D.RAMD.RAM4.4.以下哪个（些）不是计算机的输出设备（以下哪个（些）不是计算机的输出设备（）（）（20052005）A.A.鼠标鼠标B.B.显示器显示器C.C.键盘键盘D.D.扫描仪扫描仪E.E.绘图仪绘图仪 5.5.以下断电之后将不能保存数据的有（以下断电之后将不能保存数据的有（）（）（20052005）A.A.硬盘硬盘B.B.寄存器寄存器C.C.显存显存D.D.内存内存E.E.高速缓存高速缓存6.6.下列哪个（些）不是计算机的存储设备（下列哪个（些）不是计算机的存储设备（）（）（20042004）A.A.文件管理器文件管理器B.B.内存内存C.C.显卡显卡D.D.硬盘硬盘E.UE.U盘盘ECCDACDEBCDEAC三、进制转换三、进制转换二进制数转换成十进制数：按权展开求和例：将二进制数1011.01转换成十进制数（1011.01）2=（123+022+121+120+02-1+12-2）10二进制数转换成八进制数：由于一位八进制数对应位二进制数，所以二进制数转换成八进制数时，只要以小数点为界，整数部分向左，小数部分向右每3位分为一组，各组用对应的1位八进制数字表示，即可得到对应的八进制数值。最左最右端分组不足3位时，可用0补足。例：将二进制数1101101.10101转换为对应的八进制数001101101.10101015552所以（1101101.10101）2=（155.52）8二进制数转换成十六进制数：和二进制数转换成八进制数类似，只不过分组的时候是四位为一组。例：将二进制数1101101.10101转换为对应的十六进制数01101101.101010006DA8所以（1101101.10101）2=（6D.A8）16注：八、十六进制数转换成二进制数过程与此两过程相反十进制数转换成二进制数：对于整数部分，用被除数反复除以2，除第一次外，每次除以2均取前一次商的整数部分作为被除数并依次记下每次的余数。另外，所得到的商的最后一位余数是所求二进制数的最高位。例：将十进制数117.625转换成二进制数整数部分：除除2取余，逆序输出取余，逆序输出582911771413022222221111100小数部分：乘乘2取整，顺序输出取整，顺序输出0.62520.2520.500.521.01.250101所以（117.625）10=（1110101.101）21 1、以下二进制数的值与十进制数以下二进制数的值与十进制数23.45623.456的值最接近的是的值最接近的是（）。）。（20052005）A.10111.0101B.11011.1111A.10111.0101B.11011.1111C.11011.0111D.10111.0111E.10111.1111C.11011.0111D.10111.0111E.10111.11112 2、(3725)8+(B)16(3725)8+(B)16的运算结果是（的运算结果是（）。）。（20052005）A.(3736)8B.(2016)10A.(3736)8B.(2016)103.3.与十进制数与十进制数1770.6251770.625对应的八进制数是（对应的八进制数是（）(2006)(2006)A.3352.5B.3350.5C.3352.1161A.3352.5B.3350.5C.3352.1161D.3350.1151E.D.3350.1151E.前前4 4个答案都不对个答案都不对 4.(2010)16+(32)84.(2010)16+(32)8的结果是（的结果是（）DBCEABA四、逻辑运算四、逻辑运算与运算：运算符号通常为And，或00=001=010=011=1假假=假假真=假真假=假真真=真或运算：运算符号通常为Or，或00=001=110=111=1假假=假假真=真真假=真真真=真非运算：运算符号通常为Not，或0=11=0假=真真=假异或运算：运算符号通常为Xor0 xor0=00 xor1=01xor0=01xor1=1假xor假=假假xor真=真真xor假=真真xor真=假逻辑运算中运算符号的优先级为：notandor1.1.设设A=B=D=trueA=B=D=true，C=E=falseC=E=false，以下逻辑运算表达式值为真，以下逻辑运算表达式值为真的有（的有（）（）（20062006）A.(-AA.(-AB)B)(C(CD)D)-EB.-(A-EB.-(AB)B)C)C)D DE)E)C.AC.A(B(BC CD DE)D.(AE)D.(A(B(BC)C)D DEE2.2.设设A=trueA=true，B=falseB=false，C=falseC=false，D=trueD=true，以下逻辑运算，以下逻辑运算表达式值为真的有（表达式值为真的有（）。（）。（20052005）A.(AA.(AB)B)(D(DC)B.(BC)B.(BA)A)C)C)DDC.AC.A(B(BC)C)D)D)D.(AD.(A(B(BC)C)DE.(ADE.(AB)B)(C(CD)D)3.3.在在PascalPascal语言中，表达式语言中，表达式(21xor2)(21xor2)的值是（的值是（）（20062006）A.441B.42C.23D.24E.25A.441B.42C.23D.24E.25ABCABCCDECDEC C栈的定义：栈是一种特殊的表这种表只在表头进行插入和删除操作。因此，表头对于栈来说具有特殊的意义，称为栈顶。相应地，表尾称为栈底。不含任何元素的栈称为空栈。栈的逻辑结构：假设一个栈S中的元素为an,an-1,.,a1，则称a1为栈底元素，an为栈顶元素。栈中的元素按a1,a2,.,an-1,an的次序进栈。在任何时候，出栈的元素都是栈顶元素。换句话说，栈的修改是按后进先出的原则进行的，如图1所示。因此，栈又称为后进先出后进先出(Last In First Out)表表，简称为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)51.树的概念树的递归定义如下：（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.21(2005)4.完全二叉树的结点个数为4*N+3，则它的叶结点个数为（）A.2*NB.2*N-1C.2*N+1D.2*N-2E.2*N+2(2004)满二叉树的叶结点个数为N，则它的结点总数为（）A.NB.2*NC.2*N1D.2*N+1E.2N1(2002)17.按照二叉树的定义，具有3个结点的二叉树有()种。A)3B)4C)5D)6CCBE5.树的遍历第一种分法：前序遍历中序遍历后序遍历也称为（前根遍历，中根遍历，后根遍历）第二种分法：深度优先遍历和广（宽）度优先遍历对于右边一棵二叉树的遍历分别为：ABCDEFGHIJ前序遍历为：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，则其后序遍历序列为（）A.4257631B.4275631C.4275361B.D.4723561E.4526371BCBCB