全国青少年信息学奥赛联赛初赛提高组试题选编

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

每题有且仅有一个正确选项）1.与十六进制数A1. 2等值的十进制数是（）。

A．101.2 B. 111.4 C. 161.125 D. 177.252.一个字节（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. dllD. 以上都不是5.如果在某个进制下等式7*7=41成立，那么在该进制下等式12*12=( )也成立。

A. 100B. 144C. 164D. 1966.提出“存储程序”的计算机工作原理的是（）。

A. 克劳德·香农B. 戈登·摩尔C. 查尔斯·巴比奇D. 冯·诺伊曼7.前缀表达式“+3 * 2 +5 12”的值是（）。

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

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

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

A. 寄存器B. 高速缓存C. 闪存D. 外存9.完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右，依次存放到一个顺序结构的数组中。

假定根结点存放在数组的1号位置，则第k号结点的父结点如果存在话，应当存放在数组的（）号位置。

A. 2kB. 2k+1C. k/2下取整D. (k+1)/2下取整10.以下竞赛活动中历史最悠久的是（）。

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

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

1. 在以下各项中，（）不是操作系统软件。

A. SolarisB. LinuxC. SybaseD. Windows VistaE.Symbian2．微型计算机中，控制器的基本功能是（）。

A. 控制机器各个部件协调工作B. 实现算术运算和逻辑运算C.存储各种控制信息D. 获取外部信息E. 存放程序和数据3. 设字符串S=”Olympic”，S的非空子串的数目是（）。

A. 29B. 28C. 16D. 17E. 74．完全二叉树共有2*N-1个结点，则它的叶节点数是（）。

A. N-1B. 2*NC. ND. 2N-1E. N/25．将数组{8, 23, 4, 16, 77, -5, 53, 100}中的元素按从大到小的顺序排列，每次可以交换任意两个元素，最少需要交换（）次。

A. 4B. 5C. 6D. 7E. 86．设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，c，f，e，a，则栈S的容量至少应该是（）。

A. 6B. 5C. 4D. 3E. 27. 与十进制数28.5625相等的四进制数是（）。

A. 123.21B. 131.22C. 130.22D. 130.21E.130.208．递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（）的数据结构。

A. 队列B. 多维数组C. 线性表D. 链表E. 栈9. TCP/IP是一组构成互联网基础的网络协议，字面上包括两组协议：传输控制协议（TCP）和网际协议（IP）。

第十七届全国青少年信息学奥林匹克联赛初赛试题（提高组 C++语言两小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共20题，每题1.5分，共计30分，每题有且仅有一个正确选项）1.在二进制下，1100011+（）=1110000。

A. 1011B. 1101C. 1010D. 11112.字符”A”的ASCII码为十六进制41，则字符”Z”的ASCII码为十六进制的（）。

A. 66B. 5AC. 50D. 视具体的计算机而定3.右图是一棵二叉树，它的先序遍历是（）。

A. ABDEFCB. DBEFACC. DFEBCAD. ABCDEF4.寄存器是（）的重要组成部分。

A. 硬盘B. 高速缓存C. 内存D. 中央处理器(CPU)5.广度优先搜索时，需要用到的数据结构是（）。

A. 链表B. 队列C. 栈D. 散列表6.在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（）。

A. 程序运行时理论上所占的内存空间B. 程序运行时理论上所占的数组空间C. 程序运行时理论上所占的硬盘空间D. 程序源文件理论上所占的硬盘空间7.应用快速排序的分治思想，可以实现一个求第K大数的程序。

假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（）。

A. O(n2)B. O(nlogn)C. O(n)D. O(1)8.为解决Web应用中的不兼容问题，保障信息的顺利流通，（）制订了一系列标准，涉及HTML、XML、CSS等，并建议开发者遵循。

A. 微软B. 美国计算机协会(ACM)C. 联合国教科文组织D. 万维网联盟(W3C)9.体育课的上课铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。

每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。

这种站队的方法类似于（）算法。

A. 快速排序B. 插入排序C. 冒泡排序D. 归并排序10.1956年（）授予肖克利(William Shockley)、巴丁(John Bardeen)和布拉顿(Walter Brattain)，以表彰他们对半导体的研究和晶体管效应的发现。

第二十四届全国青少年信息学奥林匹克联赛初赛——提高组C++语言试题一、单项选择题（共10 题，每题2 分，共计20 分；每题有且仅有一个正确选项）1. 下列四个不同进制的数中，与其它三项数值上不相等的是（）。

A. (269)16B. (617)10C. (1151)8D. (1001101011)22. 下列属于解释执行的程序设计语言是（）。

A. CB. C++C. PascalD. Python3. 中国计算机学会于（）年创办全国青少年计算机程序设计竞赛。

A. 1983B. 1984C. 1985D. 19864. 设根节点深度为0，一棵深度为h 的满k（k>1）叉树，即除最后一层无任何子节点外，每一层上的所有结点都有k 个子结点的树，共有（）个结点。

A. (k h+1 - 1) / (k - 1)B. k h-1C. k hD. (k h-1) / (k - 1)5. 设某算法的时间复杂度函数的递推方程是T(n) = T(n - 1) + n（n 为正整数）及T(0) = 1，则该算法的时间复杂度为（）。

A. O(log n)B. O(n log n)C. O(n)D. O(n2)6. 表达式a * d - b * c 的前缀形式是（）。

A. a d * b c * -B. - * a d * b cC. a * d - b * cD. - * * a d b c7. 在一条长度为1 的线段上随机取两个点，则以这两个点为端点的线段的期望长度是（）。

A. 1 / 2B. 1 / 3C. 2 / 3D. 3 / 58. 关于Catalan 数Cn = (2n)! / (n + 1)! / n！，下列说法中错误的是（）。

A. Cn 表示有n + 1 个结点的不同形态的二叉树的个数。

B. Cn 表示含n 对括号的合法括号序列的个数。

C. Cn 表示长度为n 的入栈序列对应的合法出栈序列个数。

D. Cn 表示通过连接顶点而将n + 2 边的凸多边形分成三角形的方法个数。

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

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

1. 在以下各项中。

（）不是CPU 的组成部分。

A. 控制器B. 运算器C. 寄存器D. 主板E. 算术逻辑单元(ALU)2. 在关系数据库中, 存放在数据库中的数据的逻辑结构以( )为主。

A. 二叉树B. 多叉树C. 哈希表D. B+树E. 二维表3.在下列各项中，只有（）不是计算机存储容量的常用单位。

A. ByteB. KBC. MBD. UBE. TB4．ASCII码的含义是（）。

A. 二—十进制转换码B. 美国信息交换标准代码C. 数字的二进制数码D. 计算机可处理字符的唯一编码E. 常用字符的二进制编码5．在Pascal 语言中，表达式 (23 or 2 xor 5)的值是（）A. 18B. 1C.23D.32E.246．在Pascal 语言中，判断整数a 等于0 或b等于0或c等于0 的正确的条件表达式是（）A. not ((a<>0) or (b<>0) or (c<>0))B. not ((a<>0) and (b<>0) and (c<>0))C. not ((a=0) and (b=0)) or (c=0)D.(a=0) and (b=0) and (c=0)E. not ((a=0) or (b=0) or (c=0))7. 地面上有标号为A、B、C的3根细柱, 在A柱上放有10个直径相同中间有孔的圆盘, 从上到下次依次编号为1, 2, 3, ……，将A柱上的部分盘子经过B柱移入C柱, 也可以在B柱上暂存。

如果B柱上的操作记录为：“进，进，出，进，进，出，出，进，进，出，进，出，出”。

NOIP提高组初赛试题汇编(2002-2022)第八届全国青少年信息学奥林匹克联赛（第八届全国青少年信息学奥林匹克联赛（NOIP2002）初赛试题（提高组PASCAL语言二小时完成）一．选择一个正确答案代码（A/B/C/D）填入每题的括号内（选择一个正确答案代码（A/B/C/D），填入每题的括号内（每题1.5分，多选无分，多选无分，共30分）1．微型计算机的问世是由于（）的出现。

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

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

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

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

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

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

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

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

A）POP3B）SMTPC）DNSD）FTP10．多媒体计算机是指（）计算机。

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

第二十届全国青少年信息学奥林匹克竞赛初赛提高组C语言试题一、单项选择题（每题1.5分，共22.5分）。

1. 以下哪个是面向对象的高级语言( ).A. 汇编语言B. C++C. FORTRAND. Basic2. 1TB代表的字节数量是( ).A. 2的10次方B. 2的20次方C. 2的30次方D. 2的40次方3. 二进制数00100100和00010101的和是( ).A. 00101000B. 001010100C. 01000101D. 001110014. TCP协议属于哪一层协议( ).A. 应用层B. 传输层C. 网络层D. 数据链路层5. 下列几个32位IP地址中，书写错误的是( ).A. 162.105.128.27B. 192.168.0.1C. 256.256.129.1D. 10.0.0.16. 在无向图中，所有定点的度数之和是边数的( )倍.A. 0.5B. 1C. 2D. 47. 对长度位n的有序单链表，若检索每个元素的概率相等，则顺序检索到表中任一元素的平均检索长度为( ).A. n/2B. (n+1)/2C. (n-1)/2D. n/48. 编译器的主要功能是( ).A. 将一种高级语言翻译成另一种高级语言B. 将源程序翻译成指令C. 将低级语言翻译成高级语言D. 将源程序重新组合9. 二进制数111.101所对应的十进制数是( ).A. 5.625B. 5.5C. 6.125D. 7.62510. 若有变量int a, float x, y, 且a=7, x=2.5, y=4.7, 则表达式x+a%3*(int)(x+y)%2/4的值大约是( ).A. 2.500000B. 2.750000C. 3.500000D. 0.00000011. 有以下结构体说明和变量定义，如图所示，指针p、q、r分别指向一个链表中的三个续结点。

struct node { data next data next data next int data;struct node *next; ↑p ↑q ↑r} *p,*q,*r;现要将q和r所指结点的先后位置交换，同时要保持链表的连续，以下程序段中错误的是( ).A. q->next = r->next; p-> next = r; r->next = q;B. p->next = r; q->next = r->next; r->next = q;C. q->next = r->next; r->next = q; p->next = r;D. r->next = q; q->next = r->next; p->next = r;12. 同时查找2n 个数中的最大值和最小值，最少比较次数为( ).A. 3(n-2)/2B. 4n-2C. 3n-2D. 2n-213. 设G是有6个结点的完全图，要得到一颗生成树，需要从G中删去( )条边.A. 6B. 9C. 10D. 1514. 以下时间复杂度不是O(n2)的排序方法是( ).A. 插入排序B. 归并排序C. 冒泡排序D. 选择排序15. 以下程序实现了找第二小元素的算法。

2023年CSP-S组（提高组）初赛真题（文末附答案）一、单项选择题（共15题，每题2分，共计30分：每题有且仅有一个正确选项）1.在Linux系统终端中，以下那个命令用于创建一个新的目录( )。

A. newdirB. mkdirC. createD. mkfold2.由0,1,2,3,4中选取4个数字，能组成( )个不同四位数注:最小的四位数是1000最大的四位数是9999。

A 96B 18C 120D 843.假设n 是图的顶点的个数,m 是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法对于m=O(n)的稀疏图而言下面的四个选项，哪一项的渐近时间复杂度最小。

A、O(m*sqrt(logn)*loglogn)B、O(n^2+m)C、O(n^2/logm+mlogn)D、O(m+nlogn)4.假设有n 根柱子，需要按照以下规则依次放置编号为1、2、3、...的圆环:每根柱子的底部固定，顶部可以放入圆环，每次从柱子顶部放入圆环时，需要保证任何两个相邻圆环的编号之和是一个完全平方数。

请计算当有4根柱子时，最多可以放置( )个圆环。

A 7B 9C 11D 55.以下对数据结构的表述不恰当的一项是。

A 队列是一种先进先出(FIFO)的线性结构B 哈夫曼树的构造过程主要是为了实现图的深度优先搜索C 散列表是一种通过散列函数将关键字映射到存储位置的数据结构D 二又树是一种每个结点最多有两个子结点的树结构6.以下连通无向图中，( )一定可以用不超过两种颜色进行染色A 完全三叉树B 平面图C 边双连通图D 欧拉图7.最长公共子序列长度常常用来衡量两个序列的相似度。

其定义如下:给定两个序列X= {x1,x2,x3,...xm}和Y={y1,y2,y3...yn},最长公共子序列(LCS)问题的目标是找到一个最长的新序列Z= {z1,z2,z3...zk},使得序列既是序列X 的子序列，又是序列Y的子序列，且序列Z的长度k 在满足上述条件的序列里是最大的。

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯最新料介绍⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯2013 第十九届全国青少年信息学奥林匹克联赛初赛提升组 C++语言试题比赛时间：2013年10月13日14:30~16:30选手注意：试题纸共有 12 页，答题纸共有 2 页，满分 100 分。

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

不得使用任何电子设施（如计算器、手机、电子字典等）或查阅任何书本资料。

一、单项选择题（共 15 题，每题 1.5 分，合计 22.5 分；每题有且仅有一个正确选项）1. 一个 32 位整型变量占用（）个字节。

2.二进制数 11.01 在十进制下是（）。

3.下边的故事与（）算法有着异曲同工之妙。

以前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：?以前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘以前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事 .... ’ ?A. 列举B.递归C.贪婪D.分治4.1948 年，（）将热力学中的熵引入信息通讯领域，标记着信息论研究的初步。

A. 冯·诺伊曼（ John von Neumann）B.图灵（Alan Turing）C. 欧拉（Leonhard Euler ）D.克劳德·香农（Claude Shannon）5. 已知一棵二叉树有2013 个节点，则此中至多有（）个节点有 2 个子节点。

6.在一个无向图中，假如随意两点之间都存在路径相连，则称其为连通图。

右图是一个有 5 个极点、 8 条边的连通图。

若要使它不再是连通图，起码要删去此中的（）条边。

7.斐波那契数列的定义以下： F1=1,F2=1,Fn=Fn–1+Fn–2(n ≥3) 。

假如用下边的函数计算斐波那契数列的第 n 项，则其时间复杂度为（）。

int F(int n){if(n<=2)return 1;elsereturn F(n-1)+F(n-2);}A.O(1)B.O(n)C.O(n2)D.O(F n )8.二叉查找树拥有以下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。