第五届全国青少年信息学奥林匹克联赛初赛试题及答案（提高组PASCAL）

全国青少年信息学奥林匹克联赛初赛练习卷（二）(普及组PASCAL语言二小时完成)●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（20题，每题1.5分，共30分）1.完全二叉树的结点个数为11，则它的叶结点个数为（）。

A. 4B. 3C. 5D. 2E. 6 （最后一个分支结点：n\2=11\2=5，故叶子有6个）2.平面上有五个点A(5,3)、B(3,5)、C(2,1)、D(3,3)、E(5,1)，以这五点作为完全图G的顶点，每两点之间的直线距离是图G中对应边的权值。

以下哪条边不是图G的最小生成树中的边（）。

A. ADB. BDC. CDD. DEE. EA3.Intel的首颗16位处理器是（）。

A.8088B.80386C.80486D.8086E.Pentium（The first chip used in PCs was Intel's 8088. This was not, at the time it was chosen, the best available CPU, ... The 8088 was chosen for reasons of economics: its 8-bit data bus required less costly motherboards than the 16-bit 8086.）4.下列活动中不属于信息学奥赛的系列活动的是（）。

A. NOIPB. NOIC. IOID. 冬令营E. 程序员等级考试5.以下哪个软件不是即时通信软件（）。

A.网易泡泡B.MSN MessengerC.Google TalkD.3DS MaxE.QQ6.下列关于高级语言的说法错误的是（）。

A.Fortran是历史上的第一个面向科学计算的高级语言B.Pascal和C都是编译执行的高级语言C.C++是历史上的第一个支持面向对象的语言D.编译器将高级语言程序转变为目标代码E.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上7.常见的邮件传输服务器使用（）协议接收邮件。

全国青少年信息学奥林匹克联赛初赛练习卷（六）答案(普及组PASCAL语言二小时完成)●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（20题，每题1.5分，共30分）1.小张用十六进制，八进制和十进制写了如下一个等式：52 – 19 = 33式中三个数是各不相同进位制的数，试问52、19、33，分别为___________.（A）八进制，十进制，十六进制（B）十进制，十六进制，八进制（C）八进制，十六进制，十进制（D）十进制，八进制，十六进制2.下列if语句中，endif表示相应if的结束：y=0if x<0then y=5else if x<10 theny=10if x<100 then y=100 endifelse y=200endifendif试指出：当x=80时，运行的结果为__E__，当x=5时结果为__D_。

A、y=9B、y=5C、y=10D、y=100E、y=2003.下列哪个网络上常用的名字缩写是错误的（）。

A.WWW（World Wide Web）B.URL（Uniform Resource Locator）C.HTTP（Hypertext Transfer Protocol）D.FTP（Fast Transfer Protocol）{应该是“File Transfer Protocol”}E.TCP（Transfer Control Protocol）。

4.不能在Linux 上使用的网页浏览器是（）。

A. Internet ExplorerB. NetscapeC. OperaD. FirefoxE. Mozilla5.一位艺术史学家有20000 幅1024 * 768 的真彩色图像，如果将这些图像以位图形式保存在CD 光盘上（一张CD 光盘的容量按600M计算），大约需要（）张CD光盘。

A. 1B. 10C. 100D. 1000E. 10000（1024*768*32*20000）/ （8*1024*1024*600） =100张6.由3个a，5个b和2个c构成的所有字符串中，包含子串“abc”的共有（）个。

NOIP2013第十九届全国青少年信息学奥林匹克联赛初赛（提高组）试题解析一、单选题（15*1.5）1、A，一个字节有8个bit，32位整型变量占用4个字节，故选A。

2、A，二进制11.01转为十进制，（11.01）2 = 1*2+1+0*0.5+1*0.25 = （3.25）10 。

3、B,老和尚给小和尚讲的故事里边有故事本身，递归是函数内部调用函数本身，故选B，递归。

4、D，香农信息论鼻祖。

5、A，一定是满二叉树时拥有2个字节点的节点数最多，最下一层会有2013-1023=990个节点，于是倒数第二层会有990/2=495个节点有2个字节点，从第1层到倒数第三层共有1023-2^9=511个节点，且这些节点都是用2个子节点的节点，所以共有495+511=1006个，选A。

6、B，要使图不联通，只要其中某一个节点不连通即可，所有顶点度最少是3，所以最少需要删除3条边，选B。

7、D，此题最开始一眼扫到的时候脑子进水，跟学生将选B，O（n），实际上不是，计算F1需要1次，计算F2需要一次，计算Fn需要计算F(n-1)的次数加上F （n-2）的次数，所以其实就是计算Fn次，于是答案选择D，至于这个Fn到底是多大，数学上可以计算，它等于O((（1+sqrt(5)）/2)^n).8、B，这个必须是B，没有什么好说的，中序遍历保证左边都是小于根的，右边都是大于根的，所以可以保证是一个有序序列。

9、D，A项6和17对11取余都是6发生冲突，B项10的平方和17的平方对11取余都是1发生冲突，C项6的两倍和17的两倍对11取余都是1发生冲突，D项分别为1，2，3，4，不冲突。

10、D，IPV6地址是128位的。

谢谢网友指正！11、C，二分为6个和6个的顶点，此时边最多，有36条边。

12、B，我的学生几乎全选A去了，因为之前讲题只介绍过ASCII码，但是看到统一二字也应该想到Uni...前缀啊。

13、D，64位非零浮点数强制转换成32位浮点数，两个数会有大小上的细微差别，但不会发生符号变化，因为有专门的符号位。

第二十二届全国青少年信息学奥林匹克联赛初赛提高组Pascal 语言试题竞赛时间：2016 年10 月22 日14:30~16:30选手注意：●试题纸共有13 页，答题纸共有2 页，满分100 分。

请在答题纸上作答，写在试题纸上的一律无效。

●不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。

一、单项选择题（共15 题，每题1.5 分，共计22.5 分；每题有且仅有一个正确选项）1. 以下不是微软公司出品的软件是（）。

A. Powerpoint C. ExcelB. Word D. Acrobat Reader2. 如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键A、字母键S 和字母键D 的顺序来回按键，即CapsLock、A、S、D、S、A、CapsLock、A、S、D、S、A、CapsLock、A、S、D、S、A、……，屏幕上输出的第81 个字符是字母（）。

A. AB. SC. DD. a3. 二进制数00101100 和01010101 异或的结果是（）。

A. 00101000B. 01111001C. 01000100D. 001110004. 与二进制小数0.1 相等的八进进制数是（）。

A. 0.8B. 0.4C. 0.2D. 0.15. 以比较作为基本运算，在N 个数中找最小数的最少运算次数为（）。

A. NB. N-1C. N2D. log N6. 表达式a*(b+c)-d 的后缀表达形式为（）。

A. abcd*+-B. abc+*d-C. abc*+d-D. -+*abcd7. 一棵二叉树如右图所示，若采用二叉树链表存储该二叉树（各个结点包括结点的数据、左孩子指针、右孩子指针）。

如果没有左孩子或者右孩子，则对应的为空指针。

那么该链表中空指针的数目为（）。

A. 6B. 7C. 12D. 148. G 是一个非连通简单无向图，共有28 条边，则该图至少有（）个顶点。

第十五届全国青少年信息学奥林匹克联赛初赛试题（提高组 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算法求最小生成树。

第五届全国青少年信息学（计算机）奥林匹克分区联赛提高组复赛试题（上机编程三小时完成）第一题拦截导弹（28分）某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。

但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

某天，雷达捕捉到敌国的导弹来袭。

由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000 的正整数），计算这套系统最多能拦截多少导弹，和如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

样例：INPUT389 207 155 300 299 170 158 65OUTPUT6（最多能拦截的导弹数）2（要拦截所有导弹最少要配备的系统数）第二题回文数（25分）若一个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称之为回文数。

例如：给定一个 10进制数 56，将 56加 65（即把56从右向左读），得到 121是一个回文数。

又如，对于10进制数87，STEPl： 87＋78= 165 STEP2： 165＋561= 726STEP3： 726＋627＝1353 STEP4：1353+3531=4884 在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。

写一个程序，给定一个N（2＜n＜＝10，N=16）进制数 M．求最少经过几步可以得到文数。

如果在30步以内（包含30步）不可能得到回文数，则输出“Inpossible”样例：INPUTN＝9 M＝87OutputSTEP=6第三题旅行家的预算（27分）一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。

给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）．每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格 Pi（ i＝l，2，...N）。

第五届全国青少年信息学（计算机）奥林匹克分区联赛小学教育其他考试卷与考试题姓名:_____________ 年级:____________ 学号:______________【题目】辽宁赛区小学组初赛试卷 将下列英语单词或缩写在计算机知识中所代表的意义写在括弧中。

WINDOWS（___________________）DOS （___________________）CPU （___________________）CD-ROM （___________________）INTERNET （___________________）UCDOS （___________________）LOGO （___________________）CAI （_________l 请写出实现下列功能的DOS 命令。

列出磁盘文件目录（___________________）清屏幕（___________________）拷贝文件（___________________）删除文件（___________________）建立子目录（___________________）进入指定的子目录（___________________） 参考答案：, , , , , （本题2分）【题目】请写出你知道的计算机输入设备（三种）和输出设备（两种）。

输入设备：_________________________________________________________输出设备：______________________________________参考答案：, , , , （本题1分）【题目】计算机的信息存储容量的基本单位是字节，常用B 表示，还有千字节（KB ）、兆字节（MB ）、千兆字节（GB ）等单位（分别简称为：K 、M 、G ）。

这些单位也用来表示文件的大小。

请回答下列问题：一个文件的大小为：2K=___________________B一个硬盘的存储容量为：6.4G=___________________M一台计算机的内存为：16M=___________________K参考答案：, , （本题2分）【题目】写出能画出下列图形的命令组。

第八届全国青少年信息学奥林匹克联赛初赛试题（提高组Pascal 语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一．选择一个正确答案代码，填入每题的括号内（每题1.5分，多选无分，共30分）1．微型计算机的问世是由于（）的出现。

A）中小规模集成电路B）晶体管电路C）（超）大规模集成电路D）电子管电路2．中央处理器（CPU）能访问的最大存储器容量取决于（）。

A）地址总线B）数据总线C）控制总线D）实际内存容量3．十进制书11/128可用二进制数码序列表示为：（）。

A）1011/1000000 B）1011/100000000 C）0.001011 D）0.00010114．算式（2047）10 －（3FF）16 ＋（2000）8的结果是（）。

A）（2048）10B）（2049）10C）（3746）8D）（1AF7）165．已知x =（0.1011010）2，则[ x / 2 ]补=（）2 。

A）0.1011101 B）11110110 C）0.0101101 D）0.1001106．IPv4地址是由（）位二进制数码表示的。

A）16 B）32 C）24 D）87．计算机病毒传染的必要条件是：（）。

A）在内存中运行病毒程序B）对磁盘进行读写操作C）在内存中运行含有病毒的可执行的程序D）复制文件8．在磁盘上建立子目录有许多优点，下列描述中不属于建立子目录优点的是（）。

A）便于文件管理B）解决根目录中目录项个数有限问题C）加快文件查找速度D）节省磁盘使用空间9．在使用E-mail前，需要对Outlook进行设置，其中ISP接收电子邮件的服务器称为（）服务器。

A）POP3 B）SMTP C）DNS D）FTP10．多媒体计算机是指（）计算机。

A）专供家庭使用的B）装有CD-ROM的C）连接在网络上的高级D）具有处理文字、图形、声音、影像等信息的11．微型计算机中，（）的存取速度最快。

【21年试题】历年全国青少年信息学奥林匹克联赛初赛试题1995-2015
1995 全国青少年信息学奥林匹克联赛初赛试题
1996 全国青少年信息学奥林匹克联赛初赛试题
1997 全国青少年信息学奥林匹克联赛初赛试题
1998 全国青少年信息学奥林匹克联赛初赛试题
1999 全国青少年信息学奥林匹克联赛初赛试题
2000 全国青少年信息学奥林匹克联赛初赛试题
2001 全国青少年信息学奥林匹克联赛初赛试题
2002 全国青少年信息学奥林匹克联赛初赛试题
2003 全国青少年信息学奥林匹克联赛初赛试题
2004 全国青少年信息学奥林匹克联赛初赛试题
2005 全国青少年信息学奥林匹克联赛初赛试题
2006 全国青少年信息学奥林匹克联赛初赛试题
2007 全国青少年信息学奥林匹克联赛初赛试题
2008 全国青少年信息学奥林匹克联赛初赛试题
2009 全国青少年信息学奥林匹克联赛初赛试题
2010 全国青少年信息学奥林匹克联赛初赛试题
2011 全国青少年信息学奥林匹克联赛初赛试题
2012 全国青少年信息学奥林匹克联赛初赛试题
2013 全国青少年信息学奥林匹克联赛初赛试题
2014 全国青少年信息学奥林匹克联赛初赛试题
2015 全国青少年信息学奥林匹克联赛初赛试题。

NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试卷答案一、单项选择题（共 15 题，每题 1.5 分，共计 22.5 分；每题有且仅有一个正确选项）1. 从( )年开始，NOIP 竞赛将不再支持 Pascal 语言。

A. 2020B. 2021C. 2022D. 20232.在 8 位二进制补码中，10101011 表示的数是十进制下的( )。

A. 43B. -85C. -43D.-843.分辨率为 1600x900、16 位色的位图，存储图像信息所需的空间为( )。

A. 2812.5KBB. 4218.75KBC. 4320KBD. 2880KB4. 2017年10月1日是星期日，1949年10月1日是( )。

A. 星期三B. 星期日C. 星期六D. 星期二5. 设 G 是有 n 个结点、m 条边(n ≤m)的连通图，必须删去 G 的( )条边，才能使得 G 变成一棵树。

A.m–n+1B. m-nC. m+n+1D.n–m+16. 若某算法的计算时间表示为递推关系式：T(N)=2T(N/2)+NlogNT(1)=1则该算法的时间复杂度为( )。

A.O(N)B.O(NlogN)C.O(N log2N)D.O(N2)7. 表达式a * (b + c) * d的后缀形式是()。

A. abcd*+*B. abc+*d*C. a*bc+*dD. b+c*a*d8. 由四个不同的点构成的简单无向连通图的个数是( )。

A. 32B. 35C. 38D. 419. 将7个名额分给4个不同的班级，允许有的班级没有名额，有( )种不同的分配方案。

A. 60B. 84C. 96D.12010. 若f[0]=0, f[1]=1, f[n+1]=(f[n]+f[n-1])/2，则随着i的增大，f[i]将接近与( )。

A. 1/2B. 2/3D. 111. 设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做( )次比较。

1第五届全国青少年信息学（计算机）奥林匹克分区联赛初赛（提高组） 参 考 答 案一、选择一个正确答案代码（A/B/C/D ），填入每题的括号内（每题1.5分，多选无分，共30分）二、回答问题：（5＋5＝10分） 当给n 后，写出的表达式为： L n =n(n+1)/2+1(n ≥0) Z n =L 2n -2n=2n 2-n+1三、阅读程序，并写出正确的程序运行结果（每题15分，共30分） 1．程序运行的结果：970 2．（PASCAL 语言作 5+5+5=15分） （1）调用该过程的语句为SORT1（N ） （2）调用该过程的语句为SORT2（N ）；比较运算的次数为：n(n-1)/2 （3）调用该过程的语句为SORT3（N ） （BASIC 语言作 15分）程序运行的结果是：7 13 24 24 36 38 39 63四、根据题意，将以下程序填写完善（共30分）PASCAL 语言 BASIC 语言 （1）共15分（2+2+3+2+2+2+2=15分） ① sp1<=sp2 100 sp1>sp2 ② p:=p+1 110 p=p+1 ③ g[sp1,j]<>0 120 g(sp1,j)=0 ④ sp2:=sp2+1; 130 sp2=sp2+1 ⑤ sp1:=sp1+1 200 sp1=sp1+1 ⑥ k=g[i,2] 530 k<>g(i,2) ⑦ j:=1; 580 j=1（2）共15分（每个点3分）① a[i]:=i; 20 a(i)=i ② 1 to s 70 1 to s③ a[j-1]>a[j] 90 a(j-1)>a(j)④ (a[i1]>a[j-1]) and (a[i1]<a[k]) 120 (a(L)>a(j-1)) and (a(L)<a(k)) ⑤ a[i1]>a[k] 170 a(L)>a(k)。

第三届全国青青年信息学（运算机）奥林匹克分区联赛初赛试题（高中组）（PASCAL 语言 竞赛历时：2小时）●●全数试题答案均要求写在答卷纸上，写在试卷纸上一概无效●●一、基础部份：<1> WPS 是属于________类的软件;FOXBASE 是属于_______类的软件。

用FOXBASE 的命令：“CREATE GZB ”，在磁盘中生成的是_______文件.<2>在MS DOS 的根目录中，有如下文件：试问：C:\>TIME < 回车 > 执行的是什么命令？<3> 已知ASCII 码表中的大写字母后有6个其它字符，接着即是小写字母。

现已知：A 字母的ASCII 码为（41）16{ 表示16进制数41 }，试写出如下字母用十进制表示的ASCII 码： G → （ ）10 B → ( )10 T → ( )10<4> 设数组A[10..100,20..100] 以行优先的方式顺序存储，每一个元素占4个字节，且已知A[10，20]的地址为1000，那么A[50，90]的地址是 。

<5>一个汉字的机内码目前通经常使用2个字节来表示：第一个字节是区位码的区号加（160）10；第二个字节是区位码的位码加（160）10 。

已知：汉字“却”的区位码是4020，试写出机内码两个字节的二进制的代码：<6> 以下图顶用点表示城市，点与点之间的联系表示城市间的道路：D CA B试问：① 可否找出一条从A 城市动身，通过图中所有道路一次后又回到起点的通路来？ ② 可否从A 动身，找出去每一个城市且只去一次的通路来？假设能，那么写出通路，不然说明理由。

<7> 为了便于处置表达式，常常将一般表达式（称为中缀表示）转换为前缀{运算符在前，如X/Y 写为/XY} 和后缀 { 运算符在后，如X/Y 写为XY/}的表达形式。

在如此的表示中能够不用括号即可确信求值的顺序，如：（P+Q）*（R-S）→*+PQ-RS 或→PQ + RS -*①试将下面的表达式改写成前缀与后缀的表示形式：<A> A+B*C/D <B> A-C*D+B∧E②试将下面的前缀表示还原成中缀的表示形式，同时写出后缀表示：+△A *B△C {前缀式中△表示一元运算符取负号，如△A表示（-A）}<8> 一个将角编了号的正三角形能够进行如下二种运动：(a) 沿过极点1的高H翻转1800，咱们将那个运动用字母a来表示：1 1a3图一图二(b) 沿过三角形的外心，垂直于三角形所在平面的有向轴L（注意：三角形翻转时L轴也随着翻转的），按右手法那么旋转1200（右手法那么是指用右手大拇指指向L轴的方向，由其余四指决定旋转方向的法那么），咱们将如此的运动用字母b2若是将a,b作为运算对象，并将两个运动持续进行看做是一种运算（那个地址不妨也称为乘法）那么对图一的三角形而言，aa的结果便成为：1 2hh aa2 3 3 1假设将运动前后的三角形状态简称为元素，那么三角形状态就可与运动的表达式关联。