第十五届全国青少年信息学奥林匹克联赛初赛试题

第十五届全国青少年信息学奥林匹克联赛“建平杯”上海赛区初赛试题（小学组 PASCAL语言 90分钟完成）一、选择一个正确的答案代码（A/B/C/D），填入每题的括号内（每题2分，共30分）；1、以下不属于文件管理功能的是( )。

A．删除文件 B．拷贝文件 C．运行文件 D．移动文件2、下列有关图像分辨率的说法正确的是图像分辨率越高，( )。

A．所需的打印时间越长，存储空间越小 B．所需的打印时间越长，存储空间越大C．所需的打印时间越短，存储空间越大 D．所需的打印时间越短，存储空间越小3、在制作电子小报时有过程如下：①确定主题②评价修改③设计版面④制作作品⑤收集与选择素材其合理的顺序是( )。

A．①②③④⑤ B．①⑤③④② C．②①⑤④③ D．⑤④③②①4、用IE浏览器浏览网页时，有时图片无法正常显示，下列操作有可能使图片正常显示的是单击( ) 按钮。

A．“停止” B．“搜索” C．“刷新”D．“历史”5、小明经常浏览学校网站，下列能使操作更加便捷的是( )。

①将学校网址设为浏览器主页地址②直接在地址栏中输入学校名称③通过搜索引擎搜索学校的网址再打开④将学校网址添加到收藏夹中A．②③ B．①④ C．①③ D．②④6、按照覆盖范围来说，校园网属于( )。

A．因特网 B．互联网 C．局域网 D．广域网7、在因特网上提供的服务很多，以下不是其中的服务的是（）。

A．传统电话 B．ＩＰ电话 C．在线电影 D．ＱＱ聊天8、计算机网络给人们带来了极大的便利，最基本的功能是（）。

A．数据传输和资源共享 B．运算速度快 C．内存容量大 D．可以相互通讯9、关于电子邮件，不正确的描述是（）。

A．可向多个收件人发送同一消息B．发送消息可包括文本、语音、图象、图形C．不可能携带计算机病毒 D．可发送一条由计算机程序自动作出应答的消息10、在以下网络应用中，要求带宽最低的应用是（）。

A．可视电话 B．数字电视 C．网上视频聊天 D．收发邮件11、在Ｇoogle搜索引擎中输入关键词“光明小学”，单击“Ｇoogle搜索”按钮后，出现的网页内容是（）。

NOI a[i]1.① 0② inchah[i, ]或者 hah[i][]:= hah[i][]1③ wor,,tot1④ dechah[i, ] 或者 hah[i][]:= hah[i][]-1⑤ wor0,0,0注意：②④两空，不一定要1 或者 -1。

也可以是④ -1 , ② 1 也可以是 , 也可以 - , 甚至任何加标记的操作如位运算都可以，只要相互撤销。

（所以答案非常多）。

附：关于NOIP2022初赛普及组Paca语言一道题目的问题与阅卷处理意见经查，NOIP2022初赛普及组（Paca版本）第四大题（阅读程序写结果）第4小题题目中存在一处数据输入格式的错误：该题提供的输入为“NOIP 3”，本意是分别读入到一个字符串和整型变量中，但是由于本题的输入在同一行，数据中缺少一个换行，按照程序的写法，Paca语言会将这一行输入都作为字符串读入，而无法读到3，因此程序的实际运行无法得到答案给出的结果。

经过讨论，该题在阅卷时接受以下三种情况的答案（仅限Paca语言，不涉及C/C语言的试卷），即以下3种情形均可得分：（注：按照题目本意理解并正确完成）。

3 （注：此种情况是输入“NOIP 3”后，程序等待继续输入时，输入CtrZ结束输入，也包括文件流定向到标准输入的情形）。

3结果处给出适当文字说明，例如“等待输入”；“程序无法结束”；“根据不同的n值，输出结果不同”等，各地阅卷小组可灵活掌握。

但结果处简单空白且不加任何说明将不给分。

烦请各地特派员及时通知至阅卷小组。

对于因我们的失误和疏忽所造成的后果深表歉意。

如有其它问题请随时联系。

NOI科学委员会2009-10-19。

第十五届全国青少年信息学奥林匹克联赛初赛试题（提高组 Pascal语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一．单项选择题（共10题，每题1.5分，共计15分。

每题有且仅有一个正确答案。

）1、关于图灵机下面的说法哪个是正确的：A)图灵机是世界上最早的电子计算机。

B)由于大量使用磁带操作，图灵机运行速度很慢。

C)图灵机只是一个理论上的计算模型。

D)图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。

2、关于BIOS下面的说法哪个是正确的：A)BIOS是计算机基本输入输出系统软件的简称。

B)BIOS里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程序。

C)BIOS一般由操作系统厂商来开发完成。

D)BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。

3、已知大写字母A的ASCII编码为65（十进制），则大写字母J的十六进制ASCII编码为：A) 48 B) 49 C) 50 D) 以上都不是4、在字长为16位的系统环境下，一个16位带符号整数的二进制补码为1111111111101101。

其对应的十进制整数应该是：A)19 B) -19 C) 18 D) -185、一个包含n个分支结点（非叶结点）的非空满k叉树，k>=1，它的叶结点数目为：A) nk + 1 B) nk-1 C) (k+1)n-1 D. (k-1)n+16. 表达式a*(b+c)-d的后缀表达式是：A) abcd*+-B) abc+*d-C) abc*+d-D) -+*abcd7、最优前缀编码，也称Huffman编码。

这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。

下面编码组合哪一组不是合法的前缀编码。

A)（00，01，10，11）B)（0，1，00，11）C)（0，10，110，111）D)（1，01，000，001）8、快速排序平均情况和最坏情况下的算法时间复杂度分别为：A) 平均情况O(nlog2n)，最坏情况O(n2)B) 平均情况O(n)，最坏情况O(n2)C) 平均情况O(n)，最坏情况O(nlog2n)D) 平均情况O(log2n)，最坏情况O(n2)9、左图给出了一个加权无向图，从顶点V0开始用prim算法求最小生成树。

第十五届（2009年）信息学奥赛初赛试题及答案一.单项选择题（共10题，每题1.5分，共计15分，每题有且仅有一个正确答案。

）1 、关于图灵机下面的说法哪个是正确的：图灵机是世界上最早的电子计算机。

由于大量使用磁带操作，图灵机运行速度很慢。

图灵机只是一个理论上的计算模型。

图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。

答案（C）2、关于BIOS下面的说法哪个是正确的：BIOS是计算机基本输入输出系统软件的简称。

BIOS里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程序。

BIOS一般由操作系统厂商来开发完成。

BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。

答案（A）3 、已知大写字母A的ASCII编码为65（十进制），则大写字母J的十六进制ASCII编码为：A）48 B）49 C）50 D）以上都不是答案（D）4 、在字长为16位的系统环境下，一个16位带符号整数的二进制补码为1111111111101101。

其对应的十进制整数应该是：A）19 B）-19 C）18 D）-18答案（B）5 、一个包含n个分支结点（非叶结点）的非空满k叉树，k>=1，它的叶结点数目为：nk+1 B）nk-1 C）(k+1)n-1 D）(k-1)n+1答案（D）6 、表达式a*(b+c)-d的后缀表达式是：abcd*+- B）abc+*d- C）abc*+d- D）-+*abcd答案（B）7 、最优前缀编码，也称Huffman编码。

这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。

下面编码组合哪一组不是合法的前缀编码：A）（00，01，10，11）B）（0，1，00，11）C）（0，10，110，111）D）（1，01，000，001）答案（B）8 、快速排序平均情况和最坏情况下的算法时间复杂度分别为：平均情况O(nlog(2,n))，最坏情况O(n^2)平均情况O(n)，最坏情况O(n^2)平均情况O(n)，最坏情况O(nlog(2,n))平均情况O(log(2,n))，最坏情况O(n^2)答案（A）9 、左图给出了一个加权无向图，从顶点V0开始用prim算法求最小生成树。

第十五届全国青少年信息学奥林匹克联赛初赛试题（普及组二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一.单项选择题（共20题，每题1.5分，共计30分。

每题有且仅有一个正确答案。

）1、关于图灵机下面的说法哪个是正确的：A)图灵机是世界上最早的电子计算机B)由于大量使用磁带操作，图灵机运行速度很慢。

C)图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。

D)图灵机只是一个理论上的计算模型。

【分析】选择DA最早的计算机是ENIACB图灵机是计算机模型，没有运行速度，更谈不上磁带操作C图灵机是英国人阿兰图灵提出的理论，阿兰图灵本人在二战中破译德军密码系统发挥重要作用，而不是图灵机发挥作用。

2、关于计算机内存，下列说法哪个是正确的：A)随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的。

B)1MB内存通常是指1024*1024字节大小的内存。

C)计算机内存严格说来包括主存（memory）、高速缓存（cache）和寄存器（register）三个部分。

D)一般内存中的数据即使在断电的情况下也能保留2个小时以上。

【分析】选择B1MB=1024KB=1024*1024BA中RAM不是位置随机，而是随时访问，所谓“随机存取”，指的是当存储器中的消息被读取或写入时，所需要的时间与信息所在的位置无关。

C中高速缓存和寄存器的物理实现是集成在CPU中，这两部分不属于冯诺依曼体系中的五大部分的任意一个部分。

D中2秒都保留不住马上丢失3、下列关于BIOS的说法哪个是正确的：A)BIOS是计算机基本输入输出系统软件的简称。

B)BIOS包含了键盘、鼠标、声卡、显卡、打印机等常用输入输出设备的驱动程序。

C)BIOS一般由操作系统厂商来开发完成。

D)BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。

【分析】选A其实bios=Basic Input Output System。

信息学命题（十）A 、二进制码B 、八进制码C 、十进制码D 、智能拼音码2、计算机的软件系统通常分为（A 、硬件系统和软件系统 C 、系统软件和应用软件3、关于软盘读写孔，正确的说法是（ ）。

A .从该孔读信息C.当该孔处于开状态时，不能删除盘中文件。

D .该孔没有作用4、一棵二叉树的中序遍历序列为 DGBAECHF 后序遍历序列为 GDBEHFCA 则前序遍历的序列是（）b5E2RGbCAPA 、ABCDFGHEB 、ABDGCEFHC 、ACBGDHEFD 、ACEFHBGD lEanqFDPw5、下列叙述中错误的是（）。

A.微型计算机应避免置于强磁场之中B •微型计算机使用时间不宜过长，而应隔几个小时关机一次C.微型计算机应避免频繁关开，以延长其使用寿命D.计算机应经常使用，不宜长期闲置不用6、 计算机网络最主要的优点是（ ）。

A 、运算速度快B 、共享资源C 、精度高D 、存储容量大7、 下列4个不同进制表示的数中，最大的一个数是（ ）A 、（220.1）10B 、（11011011.1）2C 、（334.1）8 &为了区分汉字与 ASCII 码，计算机中汉字编码的最高位为（ ）A 、1B 、0C 、-1D 、2 9、下列正确的文件名是（）。

A. comma nd 。

ComB. comma nd_comC. comma nd,comD. comma RTCrpUDGiT10、 .一般来说，TCP/IP 的IP 提供的服务是（ A.运输层服务B.会话层服务 C 表示层服务11、 通信时，模拟信号也可以用数字信道来传输， 5PCzVD7HxAA 、D/AB 、A/DC ModemD 、 Codec12、一个栈的输入顺序为 1、 2、 3、4、5,卜列序列中可能是栈的输出序列是（）A 、 54312B 、 24135C 、 21543D 、 1253413、属于In ternet 的功能是（）A 、聊天B 、远程教育C 、查询资料D 、传送能量14、下列描述计算机病毒的特性中，（）是正确的。

青少年奥林匹克信息学竞赛初级篇题库1.输入10个正整数，计算它们的和，平方和；2.输入20个整数，统计其中正、负和零的个数；3.在1——500中，找出能同时满足用3除余2，用5除余3，用7除余2的所有整数；4.输出1——999中能被3整除，且至少有一位数字是5的数；5.输入20个数，求出它们的最大值、最小值和平均值。

6.甲、乙、丙三人共有384本书，先由甲分给乙、丙，所给书数分别等于乙、丙已有的书数，再由乙分给甲、丙，最后由丙分给甲、乙，分法同前，结果三人图书数相等。

编程求甲、乙、丙三人原各有书多少本？7.某养金鱼爱好者，决定出售他的金鱼。

第一次卖出了全部金鱼的一半加2分之一条金鱼；第二次卖出剩金鱼的三分之一加三分之一条金鱼；第三次卖出剩金鱼的四分之一加四分之一条金鱼；第四次卖出剩金鱼的五分之一加五分之一条金鱼，最后还剩11条。

问原来有多少条金鱼？（每次卖的金鱼都是整数条）8.猴子吃桃子问题：猴子第一天摘下若干个桃子，当即吃了一半还不过瘾，又多吃了一个；第二天又将剩下的桃子吃掉一半又多吃了一个；以后每天早上都吃了前一天剩下的一半零一个。

到了第十天想再吃时，见只剩下一个桃子，求第一天共摘了多少个桃子？9.从键盘输入整数l，统计出边长为整数的周长为l的不等边三角形的个数。

10.输入三个整数，以这三个数为边长，判断是否构成三角形；若构成三角形，进一步判断它们构的是：锐角三角形或直角三角形或钝角三角形。

11.1*2*3*...*1000结果是一个很大的数，求这个数末尾有多少个连续的零。

12.任意输入两个整数，求这两个整数的最大公约数，并求这两个整数的最小公倍数。

13.一个整数的立方可以表示为两个整数的平方差，如19853=19711052-19691202。

编程：输入一个整数N，自动将其写成N3=X2-Y2。

14.求100以内的所有素数。

纯粹素数是这样定义的：一个素数，去掉最高位，剩下的数仍为素数，再去掉剩下的数的最高位，余下的数还是素数。

第十五届（2009年）信息学奥赛初赛试题答案一.单项选择题（共10题，每题1.5分，共计15分，每题有且仅有一个正确答案。

）1 、关于图灵机下面的说法哪个是正确的：答案（C）A）图灵机是世界上最早的电子计算机。

B）由于大量使用磁带操作，图灵机运行速度很慢。

C）图灵机只是一个理论上的计算模型。

D）图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。

最早的计算机是ENIAC图灵机是计算机模型，没有运行速度，更谈不上磁带操作图灵机是英国人阿兰图灵提出的理论，阿兰图灵本人在二战中破译德军密码系统发挥重要作用，而不是图灵机发挥作用。

图灵是英国著名的数学家和逻辑学家，被称为计算机科学之父、人工智能之父，是计算机逻辑的奠基者，提出了“图灵机”和“图灵测试”等重要概念。

人们为纪念其在计算机领域的卓越贡献而设立“图灵奖”。

1936年，阿兰.图灵提出了一种抽象的计算模型── 图灵机(Turing Machine)。

图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：在纸上写上或擦除某个符号；把注意力从纸的一个位置移动到另一个位置；“图灵机”不是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算机装置，用来计算所有能想像得到的可计算函数。

装置由一个控制器和一根假设两端无界的工作带（起存储器的作用）组成。

工作带被划分为大小相同的方格，每一格上可书写一个给定字母表上的符号。

控制器可以在带上左右移动，它带有一个读写出一个你期待的结果。

外行人看了会坠入云里雾里，而内行人则称它是“阐明现代电脑原理的开山之作”，并冠以“理想计算机”的名称。

“图灵机”更在电脑史上与“冯·诺依曼机”齐名，被永远载入计算机的发展史中。

回顾20世纪科学技术的辉煌发展时，不能不提及20世纪最杰出的数学家之一的冯·诺依曼（美籍匈牙利人）。

20世纪40年代，冯·诺依曼在参与世界上第一台计算机-ENIAC的研制小组工作时，发现ENIAC有两个致命的缺陷：一是采用十进制运算，逻辑元件多，结构复杂，可靠性低；二是没有内部存贮器，操纵运算的指令分散存贮在许多电路部件内，这些运算部件如同一副积木，解题时必须像搭积木一样用人工把大量运算部件搭配成各种解题的布局，每算一题都要搭配一次，非常麻烦且费时。

2009第十五届全国青少年信息学奥林匹克联赛初赛试题（提高组C++语言二小时完成）全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效一．单项选择题（共10题，每题1.5分，共计15分。

每题有且仅有一个正确答案。

）1、关于图灵机下面的说法哪个是正确的：A)图灵机是世界上最早的电子计算机。

B)由于大量使用磁带操作，图灵机运行速度很慢。

C)图灵机只是一个理论上的计算模型。

D)图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。

2、关于BIOS下面的说法哪个是正确的：A)BIOS是计算机基本输入输出系统软件的简称。

B)BIOS里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程序。

C)BIOS一般由操作系统厂商来开发完成。

D)BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。

3、已知大写字母A的ASCII编码为65（十进制），则大写字母J的十六进制ASCII 编码为：A) 48 B) 49 C) 50 D) 以上都不是4、在字长为16位的系统环境下，一个16位带符号整数的二进制补码为1111111111101101。

其对应的十进制整数应该是：A)19 B) -19 C) 18 D) -185、一个包含n个分支结点（非叶结点）的非空满k叉树，k>=1，它的叶结点数目为：A) nk + 1 B) nk-1 C) (k+1)n-1 D. (k-1)n+16. 表达式a*(b+c)-d的后缀表达式是：A) abcd*+- B) abc+*d- C) abc*+d- D) -+*abcd7、最优前缀编码，也称Huffman编码。

这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。

下面编码组合哪一组不是合法的前缀编码。

A)（00，01，10，11）B)（0，1，00，11）C)（0，10，110，111）D)（1，01，000，001）8、快速排序平均情况和最坏情况下的算法时间复杂度分别为：A) 平均情况O(nlog2n)，最坏情况O(n2)B) 平均情况O(n)，最坏情况O(n2)C) 平均情况O(n)，最坏情况O(nlog2n)D) 平均情况O(log2n)，最坏情况O(n2)9、右图给出了一个加权无向图，从顶点V0开始用prim算法求最小生成树。

第十五届全国青少年信息学奥林匹克联赛初赛试题(2009)（普及组C++语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一．单项选择题（共20题，每题1.5分，共计30分。

每题有且仅有一个正确答案。

）1、关于图灵机下面的说法哪个是正确的：A)图灵机是世界上最早的电子计算机。

B)由于大量使用磁带操作，图灵机运行速度很慢。

C)图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。

D)图灵机只是一个理论上的计算模型。

2、关于计算机内存下面的说法哪个是正确的：A)随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的。

B)1MB内存通常是指1024*1024字节大小的内存。

C)计算机内存严格说来包括主存（memory）、高速缓存（cache）和寄存器（register）三个部分。

D)一般内存中的数据即使在断电的情况下也能保留2个小时以上。

3、关于BIOS下面说法哪个是正确的：A)BIOS是计算机基本输入输出系统软件的简称。

B)BIOS里包含了键盘、鼠标、声卡、显卡、打印机等常用输入输出设备的驱动程序。

C)BIOS一般由操作系统厂商来开发完成。

D)BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。

4、关于CPU下面哪个说法是正确的：A)CPU全称为中央处理器（或中央处理单元）。

B)CPU可以直接运行汇编语言。

C)同样主频下，32位的CPU比16位的CPU运行速度快一倍。

D)CPU最早是由Intel公司发明的。

5、关于ASCII，下面哪个说法是正确的：A)ASCII码就是键盘上所有键的唯一编码。

B)一个ASCII码使用一个字节的内存空间就能够存放。

C)最新扩展的ASCII编码方案包含了汉字和其他欧洲语言的编码。

D)ASCII码是英国人主持制定并推广使用的。

6、下列软件中不是计算机操作系统的是：A)WindowsB)LinuxC)OS/2D)WPS7、关于互联网，下面的说法哪一个是正确的：A)新一代互联网使用的IPv6标准是IPv5标准的升级与补充。

历年noip初赛普及组试题芜湖县实验学校noip初赛复习资料整理：zq多年来noip推广组预赛试题汇编芜湖县实验学校noip初赛复习资料芜湖市实验学校noip初审数据整理：ZQ第十五届全国青少年信息学奥林匹克联赛初赛试题(2021)（通用C++语言组在两小时内完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单选题（共20道题，每道题1.5分，共30分。

每道题有且只有一个正确答案。

）1.关于图灵机，以下哪项陈述是正确的：a)图灵机是世界上最早的电子计算机。

b）由于磁带操作的广泛使用，图灵机运行非常缓慢。

c)图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。

d)图灵机只是一个理论上的计算模型。

2、关于计算机内存下面的说法哪个是正确的：a）随机存取存储器（RAM）是指当程序运行时，每次分配给程序的特定内存位置是随机的机而不确定的。

b） 1MB内存通常指1024*1024字节的内存。

c）严格来说，计算机内存包括主存、缓存和寄存器三个部分。

d）通常，即使在断电的情况下，内存中的数据也可以保留2小时以上。

3.关于BIOS，以下哪项陈述是正确的：a)bios是计算机基本输入输出系统软件的简称。

b） BIOS包含常用输入和输出设备的驱动程序，如键盘、鼠标、声卡、图形卡和打印机。

c） BIOS通常由操作系统制造商开发。

d)bios能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。

4、关于cpu下面哪个说法是正确的：a） CPU被称为中央处理器（CPU）。

b） CPU可以直接运行汇编语言。

c)同样主频下，32位的cpu比16位的cpu运行速度快一倍。

d)cpu最早是由intel 公司发明的。

5、关于ascii，下面哪个说法是正确的：a） ASCII码是键盘上所有键的唯一代码。

b)一个ascii码使用一个字节的内存空间就能够存放。

c）新扩展的ASCII编码方案包括汉字和其他欧洲语言的编码。

第十五届全国青少年信息学奥林匹克联赛初赛试题（普及组 C语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一．单项选择题（共20题，每题1.5分，共计30分。

每题有且仅有一个正确答案。

）1、关于图灵机下面的说法哪个是正确的：A)图灵机是世界上最早的电子计算机。

B)由于大量使用磁带操作，图灵机运行速度很慢。

C)图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。

D)图灵机只是一个理论上的计算模型。

2、关于计算机内存下面的说法哪个是正确的：A)随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的。

B)1MB内存通常是指1024*1024字节大小的内存。

C)计算机内存严格说来包括主存（memory）、高速缓存（cache）和寄存器（register）三个部分。

D)一般内存中的数据即使在断电的情况下也能保留2个小时以上。

3、关于BIOS下面说法哪个是正确的：A)BIOS是计算机基本输入输出系统软件的简称。

B)BIOS里包含了键盘、鼠标、声卡、显卡、打印机等常用输入输出设备的驱动程序。

C)BIOS一般由操作系统厂商来开发完成。

D)BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。

4、关于CPU下面哪个说法是正确的：A)CPU全称为中央处理器（或中央处理单元）。

B)CPU可以直接运行汇编语言。

C)同样主频下，32位的CPU比16位的CPU运行速度快一倍。

D)CPU最早是由Intel公司发明的。

5、关于ASCII，下面哪个说法是正确的：A)ASCII码就是键盘上所有键的唯一编码。

B)一个ASCII码使用一个字节的内存空间就能够存放。

C)最新扩展的ASCII编码方案包含了汉字和其他欧洲语言的编码。

D)ASCII码是英国人主持制定并推广使用的。

6、下列软件中不是计算机操作系统的是：A) Windows B) Linux C) OS/2 D) WPS7、关于互联网，下面的说法哪一个是正确的：A)新一代互联网使用的IPv6标准是IPv5标准的升级与补充。

第十五届全国青少年信息学奥林匹克联赛初赛试题（普及组 Pascal语言二小时完成）一．单项选择题（共20题，每题1.5分，共计30分。

每题有且仅有一个正确答案。

）1、关于图灵机下面的说法哪个是正确的：（D）A)图灵机是世界上最早的电子计算机。

B)由于大量使用磁带操作，图灵机运行速度很慢。

C)图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。

D)图灵机只是一个理论上的计算模型。

解析：所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。

有一个机器头在纸带上移来移去。

机器头有一组内部状态，还有一些固定的程序。

在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。

2、关于计算机内存下面的说法哪个是正确的：（B）A)随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的。

B)1MB内存通常是指1024*1024字节大小的内存。

C)计算机内存严格说来包括主存（memory）、高速缓存（cache）和寄存器（register）三个部分。

D)一般内存中的数据即使在断电的情况下也能保留2个小时以上。

解析：存储容量以字节（Byte）为单位，一个字节由8位二进制位(bit)组成。

大部分都用KB，MB，GB，TB等表示，具体换算公式为：1B=8b1KB=1024B=210B1MB=1024KB=1024*1024B=220B1GB=1024MB=1024*1024*1024B=230B1TB=1024GB=1024*1024*1024*1024B=240B计算机存储系统：主存储器(内存):ROM: 只读存储器(read only, 不可写,断电不丢失数据)RAM: 随机读写存储器( access, 断电后数据丢失)辅助存储器(外存):软盘, 硬盘, U盘, 光盘等寄存器:寄存器是CPU内部的元件，寄存器拥有非常高的读写速度,因功能不同分为多种类型.相当于一个临时仓库.高速缓存:在主存和CPU之间的一个高速的容量较小的存储器,如果当前正在执行的程序和数据存放在这个存储器中,当程序运行时,不必从主存中取数据和指令,直接访问这个存储器即可.3、关于BIOS下面说法哪个是正确的：（A）A)BIOS是计算机基本输入输出系统软件的简称。

一.单项选择题（共10题，每题1.5分，共计15分，每题有且仅有一个正确答案。

）1 、关于图灵机下面的说法哪个是正确的：图灵机是世界上最早的电子计算机。

由于大量使用磁带操作，图灵机运行速度很慢。

图灵机只是一个理论上的计算模型。

图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。

答案（C）2、关于BIOS下面的说法哪个是正确的：BIOS是计算机基本输入输出系统软件的简称。

BIOS里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程序。

BIOS一般由操作系统厂商来开发完成。

BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。

答案（A）3 、已知大写字母A的ASCII编码为65（十进制），则大写字母J的十六进制ASCII编码为：A）48 B）49 C）50 D）以上都不是答案（D）4 、在字长为16位的系统环境下，一个16位带符号整数的二进制补码为1111111111101101。

其对应的十进制整数应该是：A）19 B）-19 C）18 D）-18答案（B）5 、一个包含n个分支结点（非叶结点）的非空满k叉树，k>=1，它的叶结点数目为：nk+1 B）nk-1 C）(k+1)n-1 D）(k-1)n+1答案（D）6 、表达式a*(b+c)-d的后缀表达式是：abcd*+- B）abc+*d- C）abc*+d- D）-+*abcd答案（B）7 、最优前缀编码，也称Huffman编码。

这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。

下面编码组合哪一组不是合法的前缀编码：A）（00，01，10，11）B）（0，1，00，11）C）（0，10，110，111）D）（1，01，000，001）答案（B）8 、快速排序平均情况和最坏情况下的算法时间复杂度分别为：平均情况O(nlog(2,n))，最坏情况O(n^2)平均情况O(n)，最坏情况O(n^2)平均情况O(n)，最坏情况O(nlog(2,n))平均情况O(log(2,n))，最坏情况O(n^2)答案（A）9 、左图给出了一个加权无向图，从顶点V0开始用prim算法求最小生成树。

全国青少年信息学奥林匹克联赛初赛模拟试题（三）（普及组 Pascal语言两小时完成）●●全部试题答案均要求卸载答卷纸上，写在试卷上一律无效●●一、单项选择题（共20题，每题1.5分，共计30分。

每题有且仅有一个正确选项。

）1. 2E+03表示（）。

A.2.03B.5C.8D.20002.一个字节（byte）由（）个二进制组成。

A.8B.16C.32D.以上都有可能3.以下逻辑表达式的值恒为真的是（）。

A.P∨（┓P∧Q）∨(┓P∧┓Q)B.Q∨（┓P∧Q）∨（P∧┓Q）C.P∨Q∨（P∧┓Q）∨（┓P∧Q）D.P∨┓Q∨（P∧┓Q）∨(┓P∧┓Q)4.Linux下可执行文件的默认扩展名是( )。

A. exeB. comC.dll D.以上都不是5.如果树根算第1层，那么一颗n层的二叉树最多有（）个结点。

A. 2n-1B. 2nC. 2n+1D. 2n+16.提出“存储程序”的计算机工作原理的是（）。

A. 克劳德•香农B. 戈登•摩尔C. 查尔斯•巴比奇 D.冯•诺依曼7.设X、Y、Z分别代表三进制下的一个数字，若等式XY + ZX = XYX在三进制下成立，那么同样在三进制下，等式 XY * ZX = ( )也成立。

A. YXZB. ZXYC.XYZ D.XZY8.Pascal语言、C语言和C++语言都属于（）。

A. 面向对象语言B. 脚本语言C. 解释性语言D.编译性语言9.前缀表达式“+ 3 * 2 + 512 ” 的值是（）。

A. 23B. 25C.37 D. 6510.主存储器的存取速度比中央处理器(CPU)的工作速度慢的多，从而使得后者的效率受到影响。

而根据局部性原理，CPU所访问的存储单元通常都趋于一个较小的连续区域中。

于是，为了提高系统整体的执行效率，在CPU中引入了( )。

A. 寄存器B. 高速缓存C. 闪存 D. 外存11.一个字长为8位的整数的补码是11111001，则它的原码是（）。

NOIP2009年提高组（Pascal语言）参考答案与评分标准一、单项选择题：（每题1.5分）1. C2. A3. D4. B5. D6. B7. B8. A9. A 10. C二、不定项选择题（共10题，每题1.5分，共计15分。

每题正确答案的个数大于或等于1。

多选或少选均不得分）。

1. AB2. BD3. BC4. C5. BD6. ABD7. AC8. ABC9. ABCD 10. ACD三、问题求解：（共2题，每空5分，共计10分）1．4322．35四、阅读程序写结果（共4题，每题8分，共计32分）1. 32. 58503. 487 (杨辉三角)4. 0.(384615)（分数变小数）五．完善程序 (前5空，每空2分，后6空，每空3分，共28分)（说明：以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，不一定上报科学委员会审查）1.① 0② tmp+a[i]=ans或者 a[i]+tmp=ans 或者ans=a[i]+tmp等③ <0④ i⑤ inc(tmp, a[i])或者tmp := tmp+a[i]2.① now<=maxnum 或者 not(now>maxnum)② second-first③ (ans-1)④ hash[first]>=ans 或者 hash[second]>=ans 或者 hash[first+delta]>=ans⑤ ok⑥ work(0)。