计算机奥赛基础知识.doc

第一章 计算机基础知识
一、1946年2月世界上第一台计算机ENIAC诞生在美国。
二、计算机的发展分为4个阶段：1、电子管时代2、晶体管时代3、中小规模集成电路时代4、大规模与超大规模集成电路时代
三、主存容量：
1024个字节为1K，1024K为1M，1024M为1G
四、数据在计算机内都是用二进制编码形式表示的。
五、四种常用数制
1、十进制：即逢十进位。含有十个数字符号：0…9。形式表示：D
2、二进制：即逢二进位。含有两个数字符号：0、1。形式表示：B
3、八进制：即逢八进位。含有八个数字符号：0..7。形式表示：O
4、十六进制：即逢十六进位。含有十六个数字符号：0..9、A、B、C、D、E、F。形式表示：H
六、进制转换：
1、R进制数转换为十进制数
基数为R的数字，只要将各位数字与它的位权相乘的积相加，与数就是十进制。
例1：（1101101.0101）B
=1×26+1×25+0×24+1×23+1×22+0×21+1×20+0×2-1+1×2-2+0×2-3+1×2-4
=（109.3125）D
例2：（12321.2）O
=（5329.25）D
2、十进制数转换成R进制数
将整数与小数两部分分别转换。整数部分转换方法：除R倒取余。小数部分转换方法：乘R正取整法。
例：（100.345）D≈（1100100.01011）B
八进制与二进制、十六进制与二进制的关系
八进制
对应二进制
十六进制
对应二进制
十六进制
对应二进制
0
000
0
0000
8
1000
1
001
1
0001
9
1001
2
010
2
0010
A
1010
3
011
3
0011
B
1011
4
100
4
0100
C
1100
5
101
5
0101
D
1101
6
110
6
0110
E
1110
7
111
7
0111
F
1111
七、原码、反码与补码
1、正数的反码、补码与其原码相同。
2、负数的反码：除符号位外，各位依次取反。
负数的补码：为其反码加1。
八、计算机系统
一台完整的计算机系统是由硬件系统与软件系统两部分组成的。
1、计算机的硬件系统：其基本结构属于冯·诺依曼型计算机，它的主要特点：
CPU
1）计算机由五个基本部分组成：运算器、控制器、存储器、输入设备与输出设备。
2）程序与数据以同等地位存放在存储器中，并要按地址寻访。
3）程序与数据以二进制表示。
2、CPU：称为中央处理单元，又称微处理器。
3、存储器
存储器的主要功能是存放程序与数据。
存储器通常分为内存储器与外存储器。
内存的存取速度直接影响计算机的运算速度。
内部存储器按其功能特征分为三类：1）随机存储器RAM（一旦关机断电，RAM中的信息将全部消失。）
2）只读存储器ROM
3）高速缓冲存储器Cache
4、计算机软件系统
软件分为系统软件与应用软件两大类。
九、计算机病毒
计算机病毒是一组人为设计的程序。这种特殊的程序隐藏在计算机中，在系统运行过程中能把自身准确复制或有修改地复制到其他程序体内，从而给计算机系统造成一定的损害甚至严重破坏。
计算机病毒的特性：
1）传染性2）潜伏性3）隐蔽性4）破坏性5）寄生性
十、计算机网络
1、计算机网络的类型
1）广域网（WAN）与局域网（LAN）
2）专用网与公共网
2、计算机网络协议
1）TCP/IP传输控制协议与网际协议
规范了网络上所有通信设备之间的数据传输格式及传送方法，以保证数据安全可靠地到达指定的目的地。
2）FTP文件传送协议
3）TELNET远程登录协议
4）SMTP简单邮件传送协议
5）PPP点-点协议
6）HTTP超文本传输协议
3、WWW ：全称是World Wide Web，有时也简称Web或3W。
4、URL统一资源定位标识
任何一个信息文档、图形图像、视频或音频都被看作是资源。为了引用资源，在WWW上，每一信息资源都有统一的且在网上唯一的地址，该地址就叫URL。
第二章 数据结构与算法
1、算法：问题处理方案的正确而完整的描述。
2、算法的4个特性：确定性，可行性，有穷性，拥有足够的情报。
3、算法的复杂度包括：时间复杂度与空间复杂度。
4、算法的时间复杂度是指：算法执行过程中所需要的基本运算次数。
5、算法的空间复杂度是指：算法执行过程中所需要的存储空间。
6、一个算法通常由两种基本要素组成：一是对数据对象的运算与操作，二是算法的控制结构。
7、算法的3种基本控制结构：顺序、选择、循环。
8、算法设计的基本方法：列举法、归纳法、递推、递归与减半递推技术。
9、数据的存储结构：是指数据的逻辑结构在计算机存储空间中的存放形式。
10、数据处理：是指对数据集合中的各元素以各种方式进行运算。
11、数据结构：是指相互有关联的数据元素的集合。
12、数据元素之间的任何关系都可以用前驱与后继关系来描述。
13、常用的存储结构有顺序、链接、索引等存储结构。
14、采用不同的存储结构，数据处理的效率不同。
15、数据结构分为逻辑结构与存储结构，循环队列属于存储结构。
16、在数据结构中，没有前驱的结点称为根结点；没有后继的结点称为叶子结点。
17、数据结构按逻辑关系的不同，通常可分为线性结构与非线性结构两类。
18、在稍微复杂的线性表中，一个数据元素可以由若干个数据项组成，在这种情况下，常把数据元素称为记录，含有大量记录的线性表就称作文件。
19、在计算机中存放线性表，一种最简单的方法是顺序存储。
20、在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。
21、栈：栈是一种只允许在一端进行插入与删除的线性表。
22、栈的特点：1）先进后出（或后进先出） 2）栈具有记忆作用 3）对栈的操作中，不需要改变栈底指针
23、栈的基本运算有三种：入栈、退栈与读栈顶元素。
24、队列：队列是一种允许在一端进行插入、而在另一端进行删除的线性表。
允许插入的一端称为队尾，允许删除的一端称为队头。
25、队列的特点：先进先出（或后进后出）
26、循环队列主要有两种基本运算：入队运算与退队运算。每进行一次入队运算，队尾指针就进一。
27、递归算法一般需要利用栈实现。
28、对长度为n的线性表进行插入一个新元素或删除一个元素时，在最坏情况下所需要的比较次数为 n 。在平均情况下，需要比较次数为 n/2 。
29、线性链表属于链式存储结构，在链式存储结构中，存储空间可以不连续，各元素的存储顺序是任意的。
30、在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。
31、在线性单链表中，每一个结点只有一个指针域，由这个指针只能找到后继结点，但不能找到前驱结点。
32、与单向链表相比，双向链表更容易访问相邻结点。
33、在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。
34、在线性链表中删除一个元素，只需要改变被删除元素所在结点的前一个结点的指针域即可。
35、在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点。在对循环链表进行插入与删除的过程中，实现了空表与非空表的运算统一。
36、二叉树的遍历：是指不重复地访问二叉树中的所有结点。
37、二叉树的遍历有三种：前序遍历、中序遍历、后序遍历。
1）前序遍历：访问根结点； 前序遍历左子树； 前序遍历右子树。
2）中序遍历：中序遍历左子树； 访问根结点； 中序遍历右子树。
3）后序遍历：后序遍历左子树； 后序遍历右子树； 访问根结点。
38、满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。
39、二叉树的性质：
1）在二叉树的第k层上，最多有2k-1个结点。
2）深度为m的二叉树，最多有2m-1个结点。
3）在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。
40、完全二叉树：除最后一层外，每一层上的所有结点都有两个子结点，在最后一层上缺少右边的若干结点。
41、对于长度为n的有序线性表，在最坏情况下，二分法查找需要比较log2n次，而顺序查找需要比较n次。
42、二分法查找只适用于顺序存储的有序线性表。
43、顺序查找一般是指在线性表中查找指定的元素。
44、交换类排序：快速排序法与冒泡排序法。
插入类排序：简单插入排序法与希尔排序法。
选择类排序：简单选择排序法与堆排序法。
45、对于长度为n的线性表，在最坏情况下，各种排序法的比较次数：
冒泡排序：n(n-1)/2
快速排序：n(n-1)/2
简单插入排序：n(n-1)/2
简单选择排序：n(n-1)/2
希尔排序：n1.5
堆排序：nlog2n
46、在最坏情况下，堆排序的时间复杂度最小。
47、快速排序法可以实现通过一次交换而消除多个逆序。
48、快速排序法的关键是对线性表进行分割。
第三章 程序设计基础
1、程序设计风格：清晰第一，效率第二。
2、源程序文档化时程序应加注释。注释一般分为序言性注释与功能性注释。
3、在编写程序时，需要注意数据说明的风格，以便使程序中的数据说明更易于理解与维护。
4、程序应该简单易懂，语句构造应该简单直接，不应该为提高效率而把语句复杂化。
5、当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性。
6、结构化程序设计的主要特点是：
1）程序易于理解、使用与维护。
2）提高了编程工作的效率，降低了软件开发成本。
3）每个控制结构只允许有一个入口与一个出口。
7、结构化程序设计的三种基本逻辑结构为顺序、选择与循环。
8、结构化程序设计的主要原则：自顶向下、逐步求精、模块化、限制使用GOTO语句。
9、结构化程序设计的一种基本方法是逐步求精法。
10、在模块化程序设计中，按功能划分模块的原则是：各模块的功能尽量单一，且各模块之间的联系尽量少。
11、在面向对象方法中，信息隐蔽是通过对象的封装性来实现的。封装是一种信息隐蔽技术。
12、在面向对象方法中，类的实例称为对象。
13、在面向对象方法中，类之间共享属性与操作的机制称为继承。
不是所有的对象都有继承性。
14、在面向对象方法中，一个对象请求另一对象为其服务的方式是通过发送消息。
15、信息隐蔽的概念与模块独立性直接有关。耦合是指模块之间联系的紧密程度。耦合度越高则模块的独立性越差。
16、在面向对象方法学中，直接反映了用户对目标系统的要求的模型是功能模型。
17、面向对象技术中，对象是类的实例。对象有三种成分：标识、属性与方法。
18、多态性：是指同一个操作作用于不同的对象可以有不同的解释，产生不同的执行结果。
第四章 软件工程基础
1、软件工程研究的内容主要包括：软件开发技术与软件工程管理。
2、软件是程序、数据与相关文档的集合。
3、软件工程的主要思想是强调在软件开发过程中需要应用工程化原则。
4、软件的生命周期：是从软件产品提出、实现、使用维护到停止使用退役的过程。
软件交付后还要进行维护。
5、在软件生命周期中，能准确地确定软件系统必须做什么与必须具备哪些功能的阶段是：需求分析。
6、软件工程的三要素是方法、工具与过程。
7、软件开发环境是全面支持软件开发全过程的软件工具集合。
8、软件工程过程是把输入转化为输出的一组彼此相关的资源与活动。
9、软件生命周期一般包括可行性研究与需求分析、设计、实现、测试、交付使用以及维护等活动。
10、软件工程的原则包括抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性与可验证性。
11、结构化方法的核心与基础是：结构化程序设计理论。
12、数据流程图（DFD）：是描述数据处理过程的工具，是需求理解的逻辑模型的图形表示，它直接支持系统的功能建模。
在数据流程图中：’ 表示数据流； ™ 表示加工；═ 表示文件； 表示源、潭，是系统与环境的接口，属系统之外的实体； ═ 表示存储。
13、在数据流程图（DFD）中，带有名字的箭头表示数据的流向。
14、结构化分析（需求分析）常用工具有：数据流程图（DFD）、数据字典（DD）、判定树与判定表。
15、Jackson方法是一种面向数据结构的结构化方法。
16、软件功能分解属于总体设计阶段。
17、软件需求分析阶段的工作，可以分为4个方面：需求获取、需求分析、编写需求规格说明书以及需求评审。
18、数据描述是对软件系统所必须解决的问题作出的详细说明。
19、在结构化分析方法中，用于描述系统中所用到的全部数据与文件的文档称为数据字典。数据字典是结构化分析方法的核心。
20、软件需求规格说明书是需求分析阶段的最后成果。
21、软件设计原则：抽象、模块化、信息隐蔽、模块独立性。
22、在结构化设计方法中生成的结构图（SC）中，带有箭头的连线表示：模块之间的调用关系。
23、为了使模块尽可能独立，要求：模块的内聚程度要尽量高，且各模块间的耦合程度要尽量弱。
24、耦合：是指模块之间联系的紧密程度。耦合度越高则模块的独立性越差。
内聚：是指模块内部各元素之间联系的紧密程度。内聚度越低则模块独立性越差。
25、数据流程图的类型有变换型与事务型两种。
26、将变换型映射成结构图，称为变换分析。
27、好的软件设计结构通常顶层高扇出，中间扇出较少，底层高扇入。
一个模块的扇入是指直接调用该模块的上级模块个数。一个模块的扇出是指该模块直接调用的下级模块的个数。扇入大表示模块的复用程度高，扇出大表示模块的复杂度高。
28、模块的作用范围应在控制范围之内。
29、详细设计的方法主要是结构化程序设计。
30、常用的图形描述工具有：程序流程图、盒图与问题分析图。
31、常见的过程设计工具有：
1）图形工具：程序流程图、N-S、PAD、HIPO。
2）表格工具：判定表。
3）语言工具：PDL（过程设计语言）。
32、详细设计的典型的语言描述工具是：PDL。
33、软件测试的目的：是尽可能多地发现软件产品（主要是指程序）中的错误与缺陷。
34、软件调试的目的：是改正程序中的错误。
35、程序经调试改错后还应进行再测试。
36、黑盒测试：是根据规格说明所规定的功能来设计测试用例，它不考虑程序的内部结构与处理过程。白盒测试：是在程序内部进行，主要用于完成软件内部所有数据结构的验证。
37、软件测试的方法与技术是多种多样的，从是否需要执行被测软件的角度，可以分为：静态测试与动态测试。若按功能划分则可分为白盒测试与黑盒测试方法。
38、静态测试：包括代码检查、静态结构分析、代码质量度量等。静态测试不实际运行软件，主要通过人工进行。
动态测试：是基于计算机的测试，是为了发现错误而执行程序的过程。
39、在进行模块测试时，要为每个被测试的模块另外设计两类模块：驱动模块与承接模块。其中驱动模块的作用是将测试数据传送给被测试的模块，并显示被测试模块所产生的结果。承接模块是用于代替被测试模块调用的其他模块，它仅做少量的数据操作，是一个模拟子程序，不必将子模块的所有功能带入。
40、检查软件产品是否符合需求定义的过程称为确认测试。
41、白盒测试方法一般适合用于单元测试。黑盒测试一般适合用于集成测试与确认测试。
42、软件测试过程一般按4个步骤进行，即单元测试、集成测试、验收测试（确认测试）与系统测试。
43、软件调试方法主要有强行排错法、回溯法与原因排除法。
第五章 数据库设计基础
1、数据库技术的根本目标是要解决数据的共享问题。
2、数据库系统由5部分构成：数据库、数据库管理系统、数据库管理员、硬件与软件。
3、在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段与数据库系统阶段。其中数据独立性最高的阶段是数据库系统。
4、数据库系统减少了数据冗余。
5、数据库系统的核心是：数据库管理系统。（DBMS）
6、数据：就是描述事物的符号记录。
7、数据库是数据的集合，具有统一的结构形式，是多种应用数据的集成，并可被各个应用程序所共享。
8、数据库管理系统提供了3种数据语言：
1）数据定义语言（DDL）。该语言负责数据的模式定义与数据的物理存取构建。
2）数据操纵语言（DML）。该语言负责数据的操纵，包括查询及增、删、改等操作。
3）数据控制语言（DCL）。该语言负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等功能。
9、数据库应用系统由数据库系统、应用软件与应用界面组成。
10、数据独立性一般分为物理独立性与逻辑独立性：
物理独立性：数据的物理结构的改变，不影响数据库的逻辑结构，从而不致引起应用程序的变化。
逻辑独立性：数据库总体逻辑结构的改变，不需要相应修改应用程序，这就是数据的逻辑独立性。
11、所谓数据独立性是指数据不依赖于应用程序，数据的逻辑结构、存储结构与存取方式的改变不会影响应用程序。
12、数据库系统数据集成性的主要特征是：全局与局部的结构模式。
13、数据库系统在其内部具有三级模式及二级映射，三级模式分别是概念级模式、内部级模式与外部级模式。
二级映射分别是概念级到内部级的映射以及外部级到概念级的映射。
概念级模式：是数据库系统中全局数据逻辑结构的描述，是全体用户公共数据视图。
外部级模式：也称子模式或用户模式。它是用户的数据视图，也就是用户所见到的数据模式。
内部级模式：又称物理模式，给出了数据库物理存储结构与物理存取方法，如数据存储的文件结构、索引、集簇及hash等存取方式与存取路径。
14、以内模式为框架所组成的数据库叫物理数据库。
15、相对于数据库系统，文件系统的主要缺陷有数据联系弱、数据的不一致性与数据的冗余性。
16、数据库系统通过二级映射建立了模式间的联系与转换。
17、由于数据库的共享性，因此对数据库的规划、设计、维护、监视等需要有专人管理，称他们为数据库管理员。
18、数据模型所描述的内容有数据结构、数据操作与数据约束三个部分。
19、常见的数据模型有三种：层次模型、网状模型与关系模型。
层次模型：用树形结构来表示实体之间联系的模型。
网状模型：用网状结构来表示实体之间联系的模型。
关系模型：用二维表结构来表示实体之间联系的模型。
20、在关系数据库中，把数据表示成二维表，每一个二维表称为关系。
21、E—R模型的基本概念：实体、属性、联系。
实体：客观存在的并且可以下互区别的事物。
属性：实体的特性。
联系：现实世界中事物间的关联。
22、实体集间的联系有多种，就实体集的个数而言有：
1）两个实体集间的联系 2）多个实体集间的联系 3）一个实体集内部的联系
23、两个实体集间的联系： 一对一（1：1） 一对多（1：M） 多对一（M：1） 多对多（M：N）
24、一个项目具有一个项目主管，一个项目主管可管理多个项目，则实体“项目主管”与实体“项目”的联系属于一对多的联系。
25、一个关系的属性名表称为关系模式。
26、下列数据模型中，具有坚实理论基础的是（ C）
A）层次模型 B）网状模型 C）关系模型 D）以上3个都是
27、关系模型的数据操纵即是建立在关系上的数据操纵，一般有查询、增加、删除及及修改4种操作。
28、对关系数据库的查询可以分解成一个关系内部的属性指定、一个关系内的元组选择、两个关系的合并三个基本定位操作以及一个查询操作。
29、关系表中的每一行称为一个元组。每一列称为一个属性。
30、数据模型分为格式化模型与非格式化模型，层次模型与网状模型属于格式化模型。
31、关系模型的完整性规则是对关系的某种约束条件，包括实体完整性、参照完整性与自定义完整性。
32、关系型数据库管理系统中存储与管理数据的基本形式是二维表。
33、关系代数是以集合代数为基础发展起来的，以关系为运算对象的一组高级运算的集合。常用的操作有并、差、交、笛卡儿积、投影、选择与连接等。
34、下列关系运算中，能使经运算后得到的新关系中属性个数多于原来关系中属性个数的是（ B）
A）选择 B）连接 C）投影 D）并
35、下列关系运算中，能使经运算后得到的新关系中元组个数少于原来关系中元组个数的是（A）
A） 选择 B）连接 C）投影 D）并
36、按条件f对关系R进行选择，其关系代数表达式是：σf(R)
37、关系数据库管理系统能实现的专门关系运算包括：选择、投影、连接。
38、将E—R图转换到关系模式时，实体与联系都可以表示成关系。
39、数据库设计是指在已有数据库管理系统的基础上建立数据库。
40、数据库设计包括两个方面的设计内容，它们是概念设计与逻辑设计。
41、数据库设计一般采用生命周期法。
42、E—R模型可以转换成关系模型。当两个实体间联系是M：N联系时，它通常可转换成3个关系模式。
43、数据库的物理结构主要指数据库的存储记录格式、存储记录安排与存取方法。
44、数据库的建立包括数据模式的建立与数据加载。
基础知识部分习题
一、选择题
1）下列叙述中正确的是（ ）
A)算法的执行效率与数据的存储结构无关B)算法的空间复杂度是指执行算法程序中指令（或语句）的条数C)算法的有穷性是指算法必须能执行有限个步骤之后终止D)以上3种描述都不对
2）以下数据结构中不属于线性数据结构的是（ ）
A)队列 B)线性表 C)二叉树 D)栈
3）在一棵二叉树上第5层的结点数最多是（ ）
A) 8 B) 16 C) 32 D) 15
4)在深度为7的满二叉树中，叶子结点的个数为（ ）
A) 32 B) 31 C） 64 D) 63
5）对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为（ ）
A) log2n B) n/2 C) n D) n+1
6）设树T的度为4，其中度为 1，2，3，4的结点个数分别为4，2，1，1，则叶子结点（ ）
A) 8 B) 7 C) 6 D)5
7）一棵二叉树共有70个叶子结点与80个度为1的结点，则该二叉树中总的结点个数为（ ）
A) 221 B) 219 C) 231 D)229
8）设栈S的初始状态为空，元素a、b、c、d、e、f依次通过栈S，若出栈的顺序是b、d、c、f、e、a则栈的容量至少应该为（ ）
A) 3 B) 4 C) 5 D) 6
9）已知二叉树后序遍历序列是DABEC、中序遍历是DEBAC，则前序遍历是（ ）
A) ACBED B) DECAB C) DEABC D) CEDBA
10）如果进栈序列为e1、e2、e3、e4则可能的出栈序列是（ ）
A)e3、e1、e4、e2 B) e2、e4、e3、e1 C) e3、e4、e1、e2 D) 任意顺序
11）下列选项中不属于结构化程序设计方法的是（ ）
A) 自顶向下 B) 逐步求精 C) 模块化 D) 可复用
12）下面不属于面向对象方法的是（ ）
A) 对象 B) 继承 C) 类 D) 过程调用
13）数据库系统的核心是（ ）
A) 数据模型 B)数据库管理系统 C）软件工具 D)数据库
14）将E-R图转换到关系模式时，实体与联系都可以表示成（ ）
A) 属性 B) 关系 C) 键 D) 域
15）SQL语言又称为（ ）
A) 结构化定义语言 B) 结构化控制语言
C) 结构化查询语言 D) 结构化操纵语言
16）下在不属于软件工程的3个要素的是（ ）
A) 工具 B) 过程 C) 方法 D) 环境
17）下面各项中不属于软件生命周期中的开发阶段的是（ ）
A) 需求分析 B)程序设计 C) 概要设计 D) 软件测试
18）软件生命周期中所花费用最多的阶段是（ ）
A) 详细设计 B) 软件编码 C) 软件测试 D) 软件维护
19）程序设计语言的基本成分是数据成分、运算成分、控制成分与（ ）
A) 对象成分 B) 变量成分 C) 语句成分 D) 传输成分
20）以下不属于对象的基本特点的是（ ）
A) 分类性 B) 多态性 C) 继承性 D) 封装性
二、填空题
1）设一棵完全二叉树共有700个结点，则二叉树中有_________个叶子结点。
2）在一个容量为15的循环队列中，若头指针为front=6，尾指针rear＝9，则该循环队列中共有__________个元素。
3）软件是程序、数据与____________的集合。
4）在一个关系数据库中，把数据表示成二维表，每个二维表称为__________。
5）数据库系统在其内部分为三级模式，即概念模式、内模式与外模式。其中________________给出了数据库中物理存储结构与物理存取方法。
6）在面向对象方法中，信息隐蔽是通过对象的_________性来实现的。
7）面向对象的模型中，最基本的概念是对象与__________。
8）测试的目的是暴露错误，评价程序的可靠性，而_________的目的是发现错误的位置并改正错误。
9）完成下列数制间的转换：
（1） （127）10=（ ）2
（2） （0.45）10=（ ）2
（3） （57.256）10=（ ）2
（4） （1101011）2=（ ）8=（ ）16
（5） （49A.B6）16=（ ）8=（ ）2
第十届全国青少年信息学奥林匹克联赛初赛试题
（普及组 Pascal语言 二小时完成）
一、选择一个正确答案代码（A/B/C/D/E）填入每题的挂号内
1．美籍匈牙利数学家 冯·诺依曼 对计算机科学发展所做出的贡献是：（ ）
A、提出理想计算机数学模型，成为计算机科学理论基础
B、是世界上第一个编写计算机程序的人
C、提出存储程序工作原理，并设计出第一台具有存储程序功能的计算机EDVAC
D、采用集成电路作为计算机的主要功能部件
E、指出计算机性能将以每两年翻一番的速度向前发展
2．下列哪个不是CPU（中央处理单元）（ ）
A、Intel Itanium
B、DDR SDRAM
C、AMD Athlon64
D、AMD Opteron
E、IBM Power 5
3、下列网络中常用的名字缩写对应的中文解释错误的是（ ）
A、WWW(World Wide Web)：万维网
B、URL（Uinform Resource Locator）：统一资源定位器
C、HTTP（Hypertext Transfer Protocol）：超文本传输协议
D、FTP (File Transfer Protocol)：快速传输协议
E、TCP （Transfer Control Protocol）：传输控制协议
4、下面哪个部件对于个人桌面电脑的正常运行不是必需的（ ）
A、cpu
B、显卡（图形卡）
C、光驱
D、主板
E、内存
5、下列哪个软件属于操作系统软件（ ）
A、Microsoft Word
B、金山词霸
C、Foxmail
D、WinRAR
E、Red Hat Linux
6、下列哪个不是计算机存储设备（ ）、
A、文件管理器
B、内存
C、高速缓存
D、硬盘
E、U盘
7、下列说法中错误的是（ ）
A、CPU的基本功能就是执行指令
B、CPU访问内存的速度快于访问高速缓存的速度
C、CPU的主频是指CPU在1秒内完成的指令周期数
D、在一台计算机内部，一个内存地址编码对应唯一的一个内存单元
E、数据中线的宽度决定了一次传递数据量的大小
8、彩色显示器所显示的五彩斑斓的色彩，是由红色，蓝色与（ ）色混合而成的
A、紫色 B、白色 C、黑色 D、绿色 E、橙色
9、用静电吸附磨粉后转移到纸张上，是那种输出设备的工作方式（ ）
A、针式打印机
B、喷墨打印机
C、激光打印机
D、笔式绘图仪
E、喷墨绘图仪
10、一台计算机如果要利用 线上网，就必须配置能够对数字信号与模拟信号进行互相转换的设备，这种设备是（ ）
A、调制解调器
B、路由器
C、网卡
D、网关
E、网桥
11、下列哪个不是数据库软件的名称（ ）
A、MYSQL
B、SQL Sever
C、Oracle
D、金山影霸
E、Foxpro
12、下列哪个程序设计语言不支持面向对象的程序设计方法（ ）
A、C++
B、Object Pascal
C、C
D、Smalltalk
E、Java
13、由3个a，1个b与2个c构成的所有字符串中，包含子串“abc”的共有（ ）个
A、20 B、8 C、16 D、12 E、24
14、某车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时该车站站台为空，从这一时刻开始出入记录为：“进出进进出进进进出出进出”。假设车辆入站的顺序为1,2,3……，则车辆出站的顺序为（ ）
A、1，2，3，4，5
B、1，2，4，5，7
C、1，3，5，4，6
D、1，3，5，6，7
E、1，3，6，5，7
15、二叉树T，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，其后序遍历序列为
A、4 2 5 7 6 3 1
B、4 2 7 5 6 3 1
C、4 2 7 5 3 6 1
D、4 7 2 3 5 6 1
E、4 5 2 6 3 7 1
16、满二叉树的叶节点为N，则它的节点总数为（ ）
A、N
B、2N
C、2N-1
D、2N+1
E、2^N-1
17、十进制2004等于八进制数（ ）
A、3077
B、3724
C、2766
D、4002
E、3755
18、（2004）10 +（32）16的结果是（ ）
A、（2036）10
B、（2054）16
C、（4006）10
D、（100000000110）2
E、（2036）16
C
B
D
E
A
19、在下图，从端点（ ）出发存在一条路径可以遍历图中的每条边一次，而且仅遍历一次
20、某大学计算机专业的必修课及期先修课程如下表所示：
课程
代号
C0
C1
C2
C3
C4
C5
C6
C7
课程
名称
高等
数学
程序
设计
语言
离散
数学
数据
结构
编译
技术
操作
系统
普通
物理
计算
机原
理
先修
课程

C0,C1
C1,C2
C3
C3,C7
C0
C6
请判断下列课程安排哪个是不合理的（ ）
A、C0,C6,C7,C1,C2,C3,C4,C5
B、C0,C1,C2,C3,C4,C6,C7,C5
C、C0,C1,C6,C7,C2,C3,C4,C5
D、C0,C1,C6,C7,C5,C2,C3,C4
E、C0,C1,C2,C3,C6,C7,C5,C4
二、问题求解（5分一题，共10分）
1、一个家具公司生产桌子与椅子。现有113个单位的木材。每张桌子要使用20个单位的木材，售价是30元；每张椅子要用16个单位的木材，售价是20元。使用已有的木材生产桌椅（不一定要用光木材）做多可以买_____元钱。
2、75名儿童去游乐场玩。他们可以骑旋转木马，坐滑行轨道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中两种。若每玩一样的费用为5元，游乐场总共收入700，可知有_____名儿童没有玩过其中任何一种。
三、阅读程序（8’一题，共32’）
1、-------------------------------------------
program program1;
Var
a,b,c,d,e:integer;
begin
a:=79 ; b:=34; c:=57;d:=0 ; e:=-1;
if (a<c) or (b>c) then d:=d+e
else if (d+10<e) then d:=e+10
else d:=e-a;
writeln(d);
end.
输出：_____________________。
2、-------------------------------------------
program program2;
var
i,j:integer;
str1,str2:string;
begin
str1:='pig-is-stupid';
str2:='clever';
str1[1]:='d'; str1[2]:='o';
i:=8;
for j:=1 to 6 do begin
str1[i]:=str2[j];inc(i);
end;
writeln(str1);
end.
输出：_____________________。
3、-------------------------------------------
program program3;
var
u:array[0..3] of integer;
a,b,c,x,y,z:integer;
begin
read(u[0],u[1],u[2],u[3]);
a:=u[0]+u[1]+u[2]+u[3]-5;
b:=