计算机竞赛试题.doc

合肥市第二十二届“讯飞”杯青少年信息学
（计算机）竞赛中学组笔试试题

【请将所有答案写在答题纸上】
第一大题：填空题(每空1分，共10分)
一、计算机中数据的表示形式是   （1） 进制。
二、计算机指令一般包括:  （2）   。操作码与地址码
三、1等于     （3）      字节。1024*1024
四、是由美国国防部的（4）演变而来的，这个网络上运行的通信协议统称
   （5）    协议簇。。阿帕网或  
五、网络中的统一资源定位器(网页地址)的英文缩写为   (6)    。
六、演示文档的扩展名是     （7）      。 
七、在中，要把插入点光标快速移到文档的头部，应按组合键   （8）  。
八、结构化程序设计所规定的三种基本控制结构是  （9）      。顺序、选择、循环
九、当利用大小为n 的数组顺序存储一个队列时，该队列的最大长度为   （10）    。1
十、有6个数需要从大到小进行排序，如果采用选择法排序，则排序过程中比较数据的次
数为     （11）   次。15
十一、已知一颗完全二叉树中共有768结点，则该树中共有（12）个叶子结点。384
十二、在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数为（13）。2
十三、对称的n阶矩阵的下三角各元素存储在一维数组V中，则V包含   （14）      个元素。n*(1)/2
十四、平均时间复杂度是指所有可能的输入实例均以  （15）    出现的情况下，算法的期望运行时间。相等概率

第二大题：单项选择题(每空1分，共32分)
一、中的（      ）是存放程序中间结果的。
         (Ａ) 运算器   （Ｂ）寄存器   (Ｃ) 控制器 （Ｄ）内存储器
二、所谓操作系统就是能有效地管理计算机系统中的各种（     ）资源、合理地组织计算机的工作流程。 
（A） 语言和用户  （B）主机和外部设备  （C） 软件和硬件 （D） 用户和计算机
三、内存中的每一个基本单位都被赋予一个唯一的号，称为：(          )。
   （A）地址    （B）字节     (C)  编号    （D）容量
四、计算机累加器作用是：(          )。
   （A）作加法运算    （B）作加法与逻辑运算   
  (C) 作逻辑运算    （D）计算机程序运行的中间结果和最终结果
五、计算机能自动按人们意图进行工作的最基本思想是：(        )。
   （A）采用逻辑器件  (B) 程序存贮  (C)  识别控制代码  (D) 总线结构
六、在 下，应用程序的窗口最小化后，该程序处于（　　）状态。
（A）暂停         （B）关闭     （C）运行         （D）退出
七、资源管理器中，选定多个不连续的文件应同时按(   )。
（A）  （B）  （C）   （D）
八、启动后的应用程序名或打开的文档名，都显示在窗口的（    ）上。
（A）状态栏 （B）标题栏  （C）菜单栏  （D）工具栏
九、资源管理器中，文件夹框中文件夹左边的“＋”表示：（   ）。
（A）文件夹中含有隐藏文件    （B）该文件夹为空 
（C）该文件夹中含有子文件夹  （D）该文件夹中含有系统文件    

                                                                                                 1.

十、是一种(     )的静态图像文件存储格式。
（A）有损压缩  （B）无损压缩  （C）不可压缩  （D）以上都正确
十一、在幻灯片放映方式的“循环放映”中，按（  ）键终止放映。
（A）  （B）（C） （D）
十二、窗口的状态栏上不显示（    ）。
（A）文件名    （B）光标位置    （C）页数    （D）页码
十三、在 系统中，单元格出现字符被截或“＃＃＃＃＃”符号表示（   ）。
（A）列宽不够   （B）数据无效  （C）数据错误     （D）行高不够
十四、在文字编辑中，不能实现的功能是：（     ）。
（A）   把文档的标题文字设置成不同颜色 （B）把选定的英文单词翻译成相应的中文
（C）打开一个低版本的文档            （D）把当前文档保存成一个纯文本文档
十五、在文字编辑中，下面哪种方法可以选择一个矩形的文字块：（     ）。
（A）    按住键，再按下鼠标左键，并拖动到矩形字块的右下角
（B）    不能一次选定，只能分步来选
（C）    按住键，再按下鼠标左键，并拖动到矩形字块的右下角
（D）按住键，再按下鼠标左键，并拖动到矩形字块的右下角
十六、在中，要给一段选定的文本加上边框，应从（    ）菜单中选择“边框和底
纹”命令。
（A）插入    （B）视图   （C）格式   （D）编辑
十七、程序启动后会自动打开一个默认文档，是(    )。
　（A）1　  （B）演示文稿1  　     （C）文件1       　（D）文档1
十八、（    ）成为多媒体时代的主流软件。
（A）  （B）   （C）浏览器   （D）
十九、在一所大学中，每个系都有自己的局域网，则连接各个系的校园网（   ）。
（A）是广域网 （B）还是局域网  （C）是城域网 （D）这些局域网不能互连
二十、指的是：（    ）。
（A）文件传输协议　（B远程登陆  （C）电子公告板  （D）电子函件
二十一、甲通过网络给乙发消息，表示甲已同意与乙签订合同，不久后甲不承认发过
该消息。为了防止这种情况的出现，应该在计算机网络中采取（    ）技术。
（A）数据压缩   （B）数据加密   （C）数据备份    （D）数字签名
二十二、和的一些端口保留给一些特定的应用使用。为协议保留的端口
号为：（    ）。
　（A）的80端口 （B）的80端口 （C）的25端口 （D）的25端口
二十三、在因特网域名中，通常表示：（   ）。
（A）商业组织（B）教育机构      （C）政府部门    （D）军事部门
二十四、关于防火墙以下哪种说法是错误的？（    ）
（A）    防火墙能隐藏内部地址 （B）防火墙能控制进出内网的信息流向和信息包
（C）防火墙能提供功能    （D）防火墙能阻止来自内部的威胁
二十五、上每一个页都有独立的地址，这些地址称作统一资源定位器，即：（   ）。
（A）      （B）     （C）     （D）
二十六、英特尔公司运用虚拟现实和三维技术，把中国的著名景点（  ）搬上因特网，从
而使全世界各地的因特网用户可以足不出户，作一次身临其境的旅行。。
（A）庐山  （B）黄山   （C）长江三峡  （D）故宫

二十七、随着的飞速发展及3D技术的日益成熟，人们希望将变成一个三维立体空间。主页上不再仅仅是图片和文字，而可以包含类似三维游戏的场景，这得依靠上的虚拟现实技术。现在虚拟现实技术采用(    )语言来实现。。
（A） （B）      （C）    （D）
二十八、下列无符号数中，最小的数是：（　）。
（A）（）2      （B）(75)10     （C）(37)8     （D）(2A)16
二十九、下列字符中码值最小的是：(      )。
  （A）A     （B）a    （C）x         （D）Z 
三十、在有N个叶子节点的哈夫曼树中，其节点总数为（     ）。
   （A）不确定   （B）21   （C）21    （D）2N
三十一、已知数组中A中，每个元素A（I，J）在存贮时要占3个字节，设I从1变化
到8，J从1变化到10，分配内存时是从地址开始连续按行存贮分配的。试问：
A（5，8）的起始地址为：（　　）。
   （A）141   （B）180   （C）222    （D）225
三十二、线性表若采用链表存贮结构，要求内存中可用存贮单元地址（     ）。
   （A）必须连续       （B）部分地址必须连续  
（C）一定不连续    （D）连续不连续均可

第三大题：编程题。(第一题18分，第二题20分，第三题20分，共58分)
要求：1、写出解题思路及算法分析（得分30%）
2、写出程序注解说明（得分20%）
3．写出正确程序（得分50%）
一、字母排列（）：编程求出给定英文字母表中前n个字母的无重复排列数p（n<10）。例如：3时，即表示给定字母为，就有、、、、、这六种满足题意的排列，即6。
二、最短路径（）：如图1所示的带权有向图，图中各顶点到其余各点的距离存储在二维数组中，如[i][j]表示顶点到顶点的距离，若两点间无直接路径则值为∞，如图2所示。编程求V0点到其他各点的最短距离及所经过的顶点。
∞ ∞ 10 ∞ 30 100
∞ ∞ 5 ∞ ∞ ∞
∞ ∞ ∞ 50 ∞ ∞
∞ ∞ ∞ ∞ ∞ 10
∞ ∞ ∞ 20 ∞ 60
∞ ∞ ∞ ∞ ∞ ∞

             图1                图2

                  2.

三、数字塔（）：有如下图所示的五层数字塔，从顶部出发，在每一个结点可以选择向左走或是向右走，一直走到最底层。编程找出一条路径，使路径上的值最大。

2006年合肥市青少年信息学（计算机）竞赛

注意事项
1.      务必看清题目，严格按照所要求的格式输入、输出。
2.      在调试程序时请先使用题目中的示例数据，然后再自行设计多组测试数据进行调试。
3.      测试有严格的时间限制，请尽可能优化算法。
4.      命名规则：
(1)每题都规定了该题的英文名称。
(2)程序文件和数据文件的主文件名都是该题的英文名字。
(3)程序文件扩展名采用语言环境的默认扩展名。
(4)数据文件都是文本文件，输入和输出文件的扩展名分别是和。
5.      程序应从输入文件读取数据，并严格地按照规定的输出格式将结果输出到输出文件中。输入数据文件和输出数据文件都与程序在同一个目录中，由于程序所在目录是不确定的，因此不允许在文件名中含有盘符信息和任何形式的路径信息。
6.      每位选手必须在指定分区的根目录下建立以本人参赛号命名的文件夹。选手在竞赛结束时应将所完成各题的各类文件，包括源程序文件和编译所产生的可执行文件(即扩展名为的文件) 拷入该文件夹下。
题目
1.      通关密码（）
周末，小雪到游乐园去游玩，在智力大冒险的游戏中，他一路过关斩将，现在只剩下一个问题，只要他能回答出来，那么智力宝库的大门就会打开,小雪就能得到过关的奖品。宝库的大门上有形如A □ B □ C的算术表达式，其中A、B、C是任意整数（－102525），符号□中要填放加或减运算符。宝库的守门人会按顺序任意给出A、B、C三个数，小雪要做的就是想想如何向符号□中填放加、减号，使运算结果为4。如能得到4，那么告诉守门人计算式，他就会为你打开宝库大门。如不能得到4，就告诉守门人“”，那么他就会重新给你一组数据。你能编程帮助小雪解决这个难题吗？
输入：一共有三行。每行包含一个整数，按顺序分别表示A，B，C。
输出：如果结果可以为4，则输出运算表达式，否则输出“”。
样例：
输入（）：
4
2
2
输出（）：
4+2-2
注意：A，B，C可以为负数，假设4，2，－2，这时表达式不允许为：4＋2＋（－2），正确形式应为：4＋2－2。
2.  陪审团（）
小雪的学校成立了学生法庭，他被推举为大法官。法庭的裁决取决于陪审团的决定，陪审团的人员来自学校的同学。每次开庭前，法庭会聘请n人作为侯选陪审员，其编号分别为1，2，…，n；然后由大法官从n位侯选陪审员中选出m人作为正式陪审员。具体的选择过程如下：由原告和被告分别给每一位候选陪审员打分，分值范围为[0, 20]，0分表示完全不喜欢，20分表示此人非常适合作陪审员。大法官将根据原告和被告双方对每一位侯选陪审员打出的分数来选择m人作为正式的陪审员。为了保证公平审判，原告被告双方对最终陪审团的喜好程度应该尽量平衡。具体而言，给定n个侯选陪审员以后，选出m个人组成陪审团的原则是：原告方和被告方对这m个人的所打的分数之和应该尽量接近（两个数“尽量接近”表示他们的差的绝对值尽量小）；若存在多个方案，则应该选择其中一个方案，使原告和被告方对这m个人所打的分数的总和最大。
例如：n = 4, m = 2
原告方打分：  ① 5     ② 11     ③ 7     ④  9
被告方打分：  ① 9     ② 11     ③ 8     ④  14
此时最佳方案是选择第②和第③号候选人，这是因为这个方案中原告对②③打分之和为11＋7＝18，被告对②③打分之和为11＋8＝19，两者之差的绝对值为1，这是所有方案中最小的。
再比如：n = 4,  m = 2
原告方打分：  ① 10     ② 1     ③ 1      ④ 2
被告方打分：  ① 1      ② 2     ③ 10     ④ 1
如果选择①③，则
原告对①③的打分和 = 10 + 1 = 11
被告对①③的打分和 = 1 + 10 = 11
原告和被告对①③的打分和的差的绝对值 = |11-11| = 0
原告和被告对①③的打分和的总和 = 11 + 11 = 22
如果选择②④，则
原告对②④的打分和 = 1 + 2 = 3
被告对②④的打分和 = 2 + 1 = 3
原告和被告对②④的打分和的差的绝对值 = |3-3| = 0
原告和被告对②④的打分和的总和 = 3 + 3 = 6
    虽然这两种方案中原告和被告打分和同样地接近，但是选择①③可使原告和被告打分和的总和达到最大，所以最佳方案应该选择①③。
作为大法官，小雪已经非常的忙了，几乎没有空闲的时间。所以想请你帮他计算最佳方案中原告和被告分别对陪审员打分和的差的绝对值和总和。相信你一定能轻松的完成任务的。
输入：输入文件的第一行是两个被空格隔开的整数n和m，其中n为候选人的数目，1£ n £ 200；m为需要选择的陪审员的数目，1 £ m £ 20且m £ n。接下来有n行，每行包含两个用空格隔开的整数，分别表示原告和被告对某个候选人所打的分，分值在0到20之间包含0和20）。
输出：输出文件只有一行，包含两个用空格隔开的整数，第一个数表示原告和被告对所选择的m个人打分和的差的绝对值，第二个数表示原告和被告对所选择的m个人的打分总和。
样例：
输入（）：
4 2
5 9
11 11
7 8
9 11
输出（）：
1 37

3.     夺宝奇兵（）
市地下有一份宝藏，数不清的黄金、钻石……。令人遗憾的是，千年来未曾有人得到过这份宝藏。其中一个主要原因就是，要得到这份宝藏之前，首先需要通过一个迷宫。这个迷宫的结构非常复杂，一共有N个秘密房间。广为流传的一种说法是，必须在1天之内将这N个房间的门全部打开，才能找到迷宫的出口，否则就会葬身于其中。传说中同时指出，这些房间之间有着错综复杂的联系。对于每个房间而言，仅有一把能够打开这个房间的钥匙，这把钥匙可能位于这N个房间中的任意一个。每当一个房间被打开后，就可以得到房间里面的钥匙，并以打开其他的房间。被世人称为有史以来最天才的探险家小雪准备于近日进入迷宫探险。为了确保万无一失，他携带了足量的新型炸弹，每枚炸弹可以将一个房间的门直接炸掉。由于炸弹的威力太大，可能破坏整个迷宫的结果，小雪准备用最少的炸弹打开所有的房间，你能够帮助小雪计算一下吗？
输入：第一行包含一个整数N（N<=），表示迷宫中房间的数目。接下来的N行，每行包含一个整数，表示能够打开第i个房间的钥匙的位置。
输出：仅包含一个整数，表示最少需要的炸弹的数目。
样例：
输入（）：
4
2
1
2
4
输出（）：
    　 2
说明：第1、3号房间的钥匙都在第2号房间里面，第2号房间的钥匙在第1号房间里面，第4号房间的钥匙就在第4号房间里面。小雪用炸弹打开第1、4号房间之后，所有的房间就都可以打开了。