2009年信息学奥林匹克竞赛

《2009年信息学奥林匹克竞赛》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2009年信息学奥林匹克竞赛（考试时间：120分钟）学校：_________________班级：______________姓名：______________●●全部试题答案要求写在答卷纸上，写在试卷上一律无效。●●一.选择一个正确答案代码(A/B/C/D)，填入括号内（每题1.5分，共30分）1.BIOS（基本输入输出系统）是一组固化在计算机内（）上一个ROM芯片上的程序。A.控制器B.CPUC.主板D.硬盘2.与十进制数1770.625对应的八进制数是（）。A.3352.25B.3350.5C.3352.1161D.前4个答案都不对3.将5个数的

2、序列排序，不论原先的顺序如何，最少可以通过（）次比较，完成从小到大的排序。A.6B.7C.8D.94.完全二叉树的结点个数为13，则它的叶结点个数为（）。A.3B.4C.5D.65.微型计算机的运算器、控制器及内存储器的总称是（）。A.CPUB.ALUC.主机D.MPU6.在计算机领域中，下列各项中属于表现媒体的是（）。A.声音B.显示器C.光盘D.ASCII码7.在用DIR命令列目录时，如果想中断显示，下列方法中正确的是（）。A.按任一键B.按空白键C.按Ctrl+Break键D.按Pause键8.DRAM存储器的中文含义是（）。A．静态随机存储器B

3、.动态随机存储器C.静态只读存储器D.动态只读存储器9.下列算法中，用于磁盘移臂调度的是（）。A.时间片轮转法B.LRU算法C.最短寻找时间优先算法D.优先级高者优先算法10.文件系统采用二级目录结构，这样可以（）。A.缩短访问文件存储器时间B.实现文件共享C.节省内存空间D.解决不同用户之间的文件名冲突问题11.实现虚拟存储器的目的是（）。A.实现存储保护B.实现程序浮动C.扩充内存容量D.扩充辅存容量12.一个关系数据库文件中的各条记录（）A.前后顺序不能任意颠倒，一定要按照输入的顺序排列B.前后顺序可以任意颠倒，不影响库中数据的数据关系C.前后顺

4、序可以任意颠倒，但排列顺序不同，统计处理的结果可能不同D.前后顺序不能任意颠倒，一定要按照关键词段值的顺序排列。13.数据的存储结构是指（）。A.数据所占的存储空间量B.数据的逻辑结构在计算机中的表示C.数据在计算机中的顺序存储方式D.存储在外存中的数据14.已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是()。A.堆排序B.直接插入排序C.快速排序D.直接选择排序15.以下断电之后仍能保存数据的有（）。A.寄存器B.ROMC.RAMD.高速缓存16.以下哪个不是计算机的输出设备（）。A.绘图仪B.显示器C.打印机D.传真机17.以下

5、哪个协议可以用于邮件发送。()A.FTPB.HTTPC.IMAPD.POP318.在下列各种排序算法中，不是以“比较”作为主要操作的算法是（）。A.选择排序B.冒泡排序C.插入排序D.基数排序19.已知7个结点的二叉树的前序遍历为DBACEGF(字母表示结点编号，以下同)，中序遍历是ABCDEFG，则该二叉树的后序遍历是（）A.ACBFGEDB.ABCEFGDC.CAFGEBDD.CBFEGAD20.在下列关于计算机算法的说法中，不正确的是（）。A.一个正确的算法至少要有一个输入B.算法的改进，在很大程度上推动了计算机科学与技术的进步C.判断一个算法的

6、好坏的主要标准是算法的时间复杂性与空间复杂性D.目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法二．问题求解（每题5分，共10分）21.（空间行走问题）从空间直角坐标系的原点(0,0,0)走到(2,2,2)，要求只能朝各坐标轴的正方向行走，且每步走1个单位，则到达点(2,2,2)的走法有___________种。22.（进栈出栈问题）栈是常用的一种数据结构，n个元素组成一个输入序列，在栈顶端一侧等待进栈，栈顶端另一端是出栈序列。已知栈的操作有两种：push和pop，前者是将一个元素进栈，后者是将栈顶元素弹出。由这两种操作

7、组成的一个操作序列，可以唯一确定一个出栈序列。假设在输入序列中，没有相同元素，则对于给定的包含n个元素的输入序列，用F(n)表示经过一系列的push和pop操作可能得到的出栈序列的总数。易知F(3)=5,即输入序列：{1，2，3}可能的五种输出序列：{3，2，1},{2，3，1}，{2，1，3}，{1，3，2},{1，2，3}求F(4),F(6),F(8)。三.阅读程序（4题，7’+7’+8’+8’，共30分）23.阅读以下程序，给出运行结果programprog1;varn,p,cnt:integer;beginreadln(n);p:=1;cnt:

8、=0;repeatifodd(p)thenp:=pdiv2+1+nelsep:=pdiv2;i