信息学奥赛初赛复习

初赛复习一、计算机的两位重要人物图灵：被称为“人工智能之父”，1966年设立的图灵奖是计算机界最负盛名的奖项，有“计算机界诺贝尔奖”之称冯·诺依曼：被称为“计算机之父”，他的精髓贡献是2点：2进制思想与程序内存思想。1.在下面各世界顶级的奖项中，为计算机科学与技术领域作出杰出贡献的科学家设立的奖项是（

）（2006）

A.沃尔夫奖

B.

诺贝尔奖

C.菲尔兹奖

D.图灵奖

E.

南丁格尔奖2.美籍匈牙利数学家冯·诺依曼对计算机科学发展所做出的贡献包括（）（2004）A.提出理想计算机的数学模型，成为计算机科学的理论基础。B.提出存储程序工作原理，对现代电子计算机的发展产生深远影响。C.设计出第一台具有存储程序功能的计算机EDVAC。D.采用集成电路作为计算机的主要功能部件。E.指出计算机性能将以每两年翻一番的速度向前发展。DBC二、计算机的组成

冯·诺依曼提出的计算机系统由五大部分组成，并一直沿用至今：①运算器：完成运算的算术逻辑单元（ALU）和存放操作数和运算结果的寄存器②控制器：全机的指挥中心，负责象整个电脑各个部分发出命令

③存储器：内存储器（只读存储器ROM和随机存储器RAM）和外存储器（硬盘，u盘，光盘）④输入设备：鼠标，键盘，麦克风，数码相机，扫描仪⑤输出设备：显示器，打印机，音箱，投影仪等1、在以下各项中（

）不是CPU的组成部分。（2006）

A.控制器

B.运算器

C.寄存器

D.ALU

E.RAM2.BIOS（基本输入输出系统）是一组固化在计算机内（

）上一个ROM芯片上的程序（2006）

A.控制器

B.CPU

C.主板

D.内存条

E.硬盘3.以下断电之后将不能保存数据的有（

）（2006）

A.硬盘

B.ROM

C.显存

D.RAM

4.以下哪个（些）不是计算机的输出设备（）（2005）

A.鼠标B.显示器C.键盘D.扫描仪E.绘图仪5.以下断电之后将不能保存数据的有（）（2005）

A.硬盘B.寄存器C.显存D.内存E.高速缓存6.下列哪个（些）不是计算机的存储设备（）（2004）

A.文件管理器B.内存C.显卡D.硬盘E.U盘ECCDACDEBCDEAC三、进制转换①二进制数转换成十进制数：按权展开求和例：将二进制数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转换为对应的八进制数

001

101

101.101

01015552所以（1101101.10101）2=（155.52）8③二进制数转换成十六进制数：和二进制数转换成八进制数类似，只不过分组的时候是四位为一组。例：将二进制数1101101.10101转换为对应的十六进制数

0110

1101.1010

10006DA8所以（1101101.10101）2=（6D.A8）16注：八、十六进制数转换成二进制数过程与此两过程相反①十进制数转换成二进制数：对于整数部分，用被除数反复除以2，除第一次外，每次除以2均取前一次商的整数部分作为被除数并依次记下每次的余数。另外，所得到的商的最后一位余数是所求二进制数的最高位。例：将十进制数117.625转换成二进制数整数部分：除2取余，逆序输出58291177141302222222…………1…………1…………1…………1…………1…………0…………0小数部分：乘2取整，顺序输出0.62520.2520.500.521.01.250…………1…………0…………1×××所以（117.625）10=（1110101.101）21、以下二进制数的值与十进制数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.5

B.3350.5

C.3352.1161

D.3350.1151

E.前4个答案都不对4.

(2010)16+(32)8的结果是（

）(2006)

A.(8234)10

B.(202A)16

C.(100000000110)2

D.(2042)16DBCEABA四、逻辑运算①与运算：运算符号通常为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－假=真－真=假④异或运算：运算符号通常为Xor0xor0=00xor1=01xor0=01xor1=1

假xor假=假假xor真=真真xor假=真真xor真=假逻辑运算中运算符号的优先级为：

not>and>or1.设A=B=D=true，C=E=false，以下逻辑运算表达式值为真的有（

）（2006）

A.(-A∧B)∨(C∧D)∨-E

B.-(((A∧B)∨C)∧D∧E)

C.A∧(B∨C∨D∨E)

D.(A∧(B∨C))∧D∧E

2.设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.441

B.42

C.23

D.24

E.25ABCCDEC栈的定义：栈是一种特殊的表这种表只在表头进行插入和删除操作。因此，表头对于栈来说具有特殊的意义，称为栈顶。相应地，表尾称为栈底。不含任何元素的栈称为空栈。栈的逻辑结构：假设一个栈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,5

B.1,2,4,5,7

C.1,4,3,7,6

D.1,4,3,7,2

E.1,4,3,7,5（2006）13.设栈S的初始状态为空，元素a,b,c,d,e依次入栈，以下出栈序列不可能出现的有（

）。

A.a,b,c,e,d

B.b,c,a,e,d

C.a,e,c,b,d

D.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,g

D.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，87

B)51，6，19，20，14，8，87，90，25

C)19，20，90，7，6，25，5l，14，87

D)6，25，51，8，20，19，90，87，14

E)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)2

B)3

C)4

D)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.10

B.11

C.12

D.13

E.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)3

B)4

C)5

D)6CCBE5.树的遍历第一种分法：前序遍历