NOI题库2.2括号匹配分析与题解(C++)

第十八届全国青少年信息学奥林匹克联赛初赛（普及组C++语言试题）竞赛时间：2012年10月13日14:30~16:30选手注意：●试题纸共有10页，答题纸共有2页，满分100分。

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

●不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料一、单项选择题（共20题，每题1.5分，共计30分；每题且仅有一个正确选项）1．计算机如果缺少（），将无法正常启动。

A．内存B．鼠标C．U盘D．摄像头2．（）是一种先进先出的线性表。

A．栈B．队列C．哈希表（散列表）D．二叉树3．目前计算机芯片（集成电路）制造的主要原料是（），它是一种可以在沙子中提炼出的物质。

A．硅B．铜C．锗D．铝4．十六进制数9A在（）进制下是232。

A．四B．八C．十D．十二5．（）不属于操作系统。

A．Windows B．DOS C．Photoshop D．NOI Linux6．如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是（）。

A．ABC B．CBA C．ACB D．BAC7．目前个人电脑的（）市场占有率最靠前的厂商包括Intel、AMD等公司。

A．显示器B．CPU C．内存D．鼠标8．使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少1个逆序对，因此序列5，4，3，2，1需要执行（）次操作，才能完成冒泡排序。

A．0 B．5 C．10 D．159．1946年诞生于美国宾夕法尼亚大学的ENIAC属于（）计算机。

A．电子管B．晶体管C．集成电路D．超大规模集成电路10．无论是TCP/IP模型还是OSI模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。

如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（）。

A．中国公司的经理与波兰公司的经理交互商业文件B．军队发布命令C．国际会议中，每个人都与他国地位对等的人直接进行会谈D．体育比赛中，每一级比赛的优胜者晋级上一级比赛11．矢量图（Vector Image）图形文件所占的贮存空间比较小，并且无论如何放大、缩小或旋转等都不会失真，是因为它（）。

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

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

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

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

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

A.P V （?P A Q） V （?P A ?Q）B.Q V （?P A Q） V （P A ?Q）C.P V QV （P A ?Q） V （?P A Q）D.P V?QV（P A ?Q） V （?P A ?Q）4．Linux 下可执行文件的默认扩展名为（）。

C.dllD. 以上都不是5．如果树根算第1 层，那么一棵n 层的二叉树最多有（）个结点。

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

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

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

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

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

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

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

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

2023第32届全国高中计算机科学奥林匹克竞赛试题及答案简介这份文档包含了2023年第32届全国高中计算机科学奥林匹克竞赛的试题及答案。

这是一项高中生参与的计算机科学竞赛，旨在挑选出在计算机科学领域具备才华和潜力的年轻人。

试题1. 请编写一个程序，输入两个整数并输出它们的和。

2. 编写一个程序，检查一个字符串是否是回文字符串。

3. 设计一个算法，在给定的数组中找到两个数的和等于给定目标数的索引。

4. 编写一个程序，实现二叉树的前序遍历。

5. 请编写一个函数，计算给定列表中的所有偶数的和。

答案1. 程序示例：a = int(input("请输入第一个整数："))b = int(input("请输入第二个整数："))sum = a + bprint("它们的和为：" + str(sum))2. 程序示例：def is_palindrome(s):return s == s[::-1]string = input("请输入一个字符串：") if is_palindrome(string):print("是回文字符串")else:print("不是回文字符串")3. 算法示例：def find_sum_indices(nums, target): seen = {}for i, num in enumerate(nums):seen[num] = ireturn []nums = [2, 7, 11, 15]target = 9indices = find_sum_indices(nums, target) print("满足条件的索引为：" + str(indices)) 4. 程序示例：class Node:def __init__(self, value):self.value = valueself.left = Noneself.right = Nonedef preorder_traversal(root):if root:print(root.value, end=" ")preorder_traversal(root.left)preorder_traversal(root.right)创建示例二叉树root = Node(1)root.left = Node(2)root.right = Node(3)root.left.left = Node(4)root.left.right = Node(5)print("前序遍历结果：", end="")preorder_traversal(root)5. 程序示例：def sum_even_numbers(numbers):total = 0for num in numbers:if num % 2 == 0:total += numreturn totalnums = [1, 2, 3, 4, 5, 6]sum_of_evens = sum_even_numbers(nums)print("偶数的和为：" + str(sum_of_evens))以上是2023年第32届全国高中计算机科学奥林匹克竞赛的试题及答案。

相关知识点与参考答案一.单项选择题1、操作系统是系统软件的核心,是有效利用计算机的硬件、软件、数据等各种资源的好管家,它还向用户提供一套容易学习使用的操作命令。

常用的操作系统有:MS-DOS、PC-DOS、WINDOWS、UNIX、LINUX、OS/2等。

WORD、WPS是字处理软件,FOXBASE是数据库管理软件。

2、字长表示一个存储单元由多少位二进制数组成,八位机一个字长就是一个字节,十六位机一个字长可以表示两个字节。

字长位的多少,表明可访问存储器的地址多少。

3、操作系统一般存放在系统盘,计算机启动引导系统后,系统中的常用命令就驻留在内存中,方便用户使用计算机。

所以启动计算机引导系统就是把操作系统从系统盘中调入内存储器。

4、我们要清楚,快存实质是高速缓存,主存即内存,辅存也就是外存。

在这三种存储器中,以高速缓存最快,故此,通常常用的程序都是存放在高速缓存区里。

而主存的速度当然是比辅存要快了。

5、一般,对计算机工作有较大影响的有尘土、温度、湿度。

6、计算机的指令系统是由操作码与操作数组成。

7、通用寄存器的位数跟机器有关,取决于计算机的字长。

8、计算机能实现的全部指令的集合合称为指令系统。

执行各条指令所规定的操作是由指挥工作的控制器和执行运算的部件共同完成。

而控制器与运算器合起来称为CPU。

9、RAM(random access memory)随时读写存储器,供计算机工作时随机写入,计算机一旦断电后,其中的信息就会消失。

10、WINDOWS 9X是一种多任务的可视化的操作系统,它可以同时打开多个窗口,执行多个任务,而这些操作无论是应用程序还是文档编辑窗口,都可以利用图标、菜单或工具进行操作,即所见即所得。

所以称之为多任务图形方式的操作系统。

1-10参考答案:BBDCBBCABD11、常用的操作系统有:MS-DOS、PC-DOS、WINDOWS、UNIX、LINUX、OS/2等。

PASCAL是程序设计的语言系统软件。

NOIP初赛练习之二(解答题)前言：如何做解答题解答题一般是根据要求写出表达式或画出图等，涉及的知识点主要有数学方面的基本知识、数据结构方面的如树和图等、逻辑推理等，难点主要在写出递推公式。

写出公式之前要先从起始值开始进行摸索，写出若干个结果之后再观察其中的规律，再写出公式，一般是F （N）=……，省略号部分可能是F（N-1）、F（N-2）……等的数学表达式。

最后再验证公式的正确性，时间允许的话可从数学等方面加以证明（当然不要写出证明过程，除非要求你说明其正确性）。

有时是图形的变换，如正方形、三角形、圆等的旋转，先前给出了几个点相应的坐标，求旋转若干周后的各点坐标，这种情况一般用到求余的运算，当以N为一个周期时往往是用对N求余（mod n）的运算；如果是正反两种情况可以使用（-1）的若干次方的形式来转换两种状态，即用某一表达式乘以-1的若干次方。

有时是有关组合数学的知识，如排列或组合，确定是(分步)乘法原理还是（分类）加法原理。

对于排列分次序，而组合不分各元素的次序：组合：C（m, n）=n*(n-1)*….*(n-m+1)/m!排列：P (m, n)= n*(n-1)*….*(n-m+1)数据结构方面要对堆栈的先进后出原理、队列的先进先出原理、二叉树(结点)的遍历、图的邻接矩阵表示法熟悉。

至于逻辑推理方面的要将各个条件（描述）一一列出，排除矛盾情况，列举出可能的情况，写出符合条件的结果。

练习：1.公式推导（10分）1999年初中组初赛题根据Nocomachns定理，任何一个正整数n的立方一定可以表示成n个连续的奇数的和。

如：13＝ 123＝3＋ 533＝7＋9 ＋1143=13十15+17+19在这里，若将每一个式中的最小奇数称为X，那么当给出n之后，请写出X与n之间的关系表达式：＿＿＿2、问题解答：（每题7分，共14分）2000初中组(1).已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。

第二十一届全国青少年信息学奥林匹克联赛初赛普及组C++语言试题竞赛时间：2015年10月11日14:30~16:30选手注意：●试题纸共有7页，答题纸共有2页，满分100分。

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

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

一、单项选择题（共20题，每题1.5分，共计30分；每题有且仅有一个正确选项）1.1MB等于（）。

A. 1000字节B. 1024字节C. 1000 X 1000字节D. 1024 X 1024字节2.在PC机中，PENTIUM（奔腾）、酷睿、赛扬等是指（）。

A. 生产厂家名称B. 硬盘的型号C. CPU的型号D. 显示器的型号3.操作系统的作用是（）。

A. 把源程序译成目标程序B. 便于进行数据管理C. 控制和管理系统资源D. 实现硬件之间的连接4.在计算机内部用来传送、存贮、加工处理的数据或指令都是以（）形式进行的。

A. 二进制码B. 八进制码C. 十进制码D. 智能拼音码5.下列说法正确的是（）。

A. CPU的主要任务是执行数据运算和程序控制B. 存储器具有记忆能力，其中信息任何时候都不会丢失C. 两个显示器屏幕尺寸相同，则它们的分辨率必定相同D. 个人用户只能使用Wifi的方式连接到Internet6.二进制数00100100和00010100的和是（）。

A. 00101000B. 01110011C. 01000100D. 001110007.与二进制小数0.1相等的十六进制数是（）。

A. 0.8B. 0.4C. 0.2D. 0.18.所谓的“中断”是指（）。

A. 操作系统随意停止一个程序的运行B. 当出现需要时，CPU暂时停止当前程序的执行转而执行处理新情况的过程C. 因停机而停止一个程序的运行D. 电脑死机9.计算机病毒是（）。

A. 通过计算机传播的危害人体健康的一种病毒B. 人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合C. 一种由于计算机元器件老化而产生的对生态环境有害的物质D. 利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒10.FTP可以用于（）。

noi竞赛练习题NOI（National Olympiad in Informatics，全国信息学奥林匹克竞赛）是由中国计算机学会主办，是中国最具影响力的计算机竞赛之一。

NOI 的目标是选拔和培养高中生的计算机科学和算法设计能力，培养具有国际竞争力的优秀人才。

竞赛设置了一系列挑战性的编程题目，考察参赛者的算法思维、编程实践和问题解决能力。

下面是一道NOI竞赛练习题，希望能帮助读者更好地理解NOI竞赛的题型和要求。

【题目描述】小明是一名NOI竞赛的参赛选手，最近他参加了一场练习赛，其中一道题目让他颇费思量。

题目要求如下：给定一个长度为N的整数序列A，小明需要将序列A分成两个非空的子序列B和C。

子序列B和C的长度可以不相等，但是B和C的元素之和必须相等。

小明希望分割后的B序列的元素尽可能多。

请你帮助小明计算B序列的最大长度。

【输入格式】输入的第一行包含一个整数N，表示序列A的长度。

接下来一行包含N个整数，表示序列A中的元素。

【输出格式】输出一个整数，表示B序列的最大长度。

【样例输入】51 2 3 4 6【样例输出】3【样例解释】序列A为[1, 2, 3, 4, 6]，B序列可以为[1, 2, 3]，C序列为[4, 6]，它们的元素之和均为6，且B序列的长度为3，是可以通过分割得到的最大长度。

【数据范围】对于30%的数据，2 ≤ N ≤ 10，序列A中的元素均为正整数。

对于60%的数据，2 ≤ N ≤ 100，序列A中的元素均为正整数。

对于100%的数据，2 ≤ N ≤ 10^5，序列A中的元素均为正整数。

【解题思路】要求分割后B序列的最大长度，可以使用动态规划的方法进行求解。

令dp[i]表示序列A中前i个数字的和的奇偶性。

在状态转移方程中，我们可以考虑第i个数字A[i]是属于序列B还是序列C。

当A[i]属于序列B时，dp[i]的奇偶性与dp[i-1]相同。

即dp[i] = dp[i-1]；当A[i]属于序列C时，dp[i]的奇偶性与dp[i-1]相反。

问题描述：指针式钟表的历史可追溯到1386年，在这个问题中，需要你求出一般的指针式钟表的时针和分针之间的角度，我们假设如果有秒针的话，其始终指向12：00。

问题求解：输入一些时间的列表，输出时针和分针之间的最小的正角。

输入文件（HOROLOGE.IN）：每行输入一个时间，时间是以“小时：分钟”的格式输入。

小时H的范围是1≤H≤12，分钟M的范围是00≤M≤59。

应该注意的是H输入的是1或2位数字，M必须有两位数字，中间用“：”分隔，即输入时间的格式与你在数字表上看到的是一样的。

若输入0：00，则表示输入完毕。

输出文件（HOROLOGE.OUT）：输出各行与输入各行相对应，对于任何一个输入的时间来说，输出的角度都应当在0到180度之间。

输出的数字应四舍五入，精确到千分之一，即精确到小数点后第三位。

输入输出示例：HOROLOGE .IN12:009:008:100:00HOROLOGE .OUT0.00090.000175.000vari,h,m,l : integer;s : string;procedure solve;var a,ah,am : real;beginah := (h mod 12 + m/60)*30;am := m*6;a := abs(ah-am);if a > 180 then a := 360-a;writeln(a:0:3);end;beginassign(input,'horologe.in'); reset(input);assign(output,'horologe.out'); rewrite(output);repeatreadln(s);while pos(' ',s) > 0 do delete(s,pos(' ',s),1);if s = '0:00' then break;l := pos(':',s);val(copy(s,1,l-1),h,i);val(copy(s,l+1,255),m,i);solve;until false;close(input); close(output);end.问题描述：如果一个字符串是以一个或者一个以上的长度为k的重复字符串所连接成的，那么这个字符串就被称为周期为k的字符串。

NOIP部份试题分析和解答南宁三中孙国强QQ： 393936008竞赛试题名称算法N01P2004津津的储蓄计划模拟合并果子排序+二分杏找合唱队形动态规划虫食算搜索N01P2005谁拿了最多奖学金模拟过河数学或动态规划篝火晚会图论或数学等价表达式分治NOIP2006能量项链动态规划金明的预算方案动态规划作业调度方案模拟2”k进制数数学+高精N01P2007统计数字排序字符串的展开模拟知阵取数游戏动态规划+高精树网的核图论N01P2008笨小猴模拟火柴棒等式搜索或数学传纸条动态规划双栈排序图论一、枚举：I 1 1 e ! 11 It I H It 1 LJ n. -i "i JIJ iri j注意：1.加号与等号各自需要两根火柴棍2.如果A,B,则A+B=C与B+A=C视为不同的等式（A、B、0=0）3.n根火柴棍必须全部用上【输入】输入文件matches.in共一行，乂一个整数n （nv=24）。

【输出】输出文件matches.out共一行，表示能拼成的不同等式的数目。

【输入输出样例1 ]matches, in matches, out142【输入输出样例1解释】2个等式为0+1=1和1+0=1 □【输入输出样例2】matches, in matches, out189【输入输出样例2解释】9个等式为: 0+4=4 0+11=11 1+10=112+2=42+7=94+0=47+2=9 10+1=11 11+0=11既然我们用枚举的方法，就要确定枚举什么？枚举的数量（范）有多少，估算时间和空间复杂度。

2.举例：一-年一度的高一YL杯超级篮球赛开赛了。

当然，所谓超级，意思是参赛人数可能多余5人。

小三对这项篮球非常感兴趣，所以一场都没有落下。

每个中午都准时守侯在篮球场看比赛。

经过一个星期的研究，小三终于对篮球的技战术找到了一丝丝感觉了。

他发现打YL 杯的每个班都有一奁相似的进攻战术：1:控球后卫带球到前场，找到一个最佳攻击点（x,y）2:所有除控卫以外的队员都从各自的当前位置迅速向（x,y）移动3:控球后卫根据场上情况组织进攻这个战术对于一般情况是非常奏效的，但是每个队员毕竞不像小三一样每天精力过剩, 每个队员都有一个疲劳指数W,显然对于每个队员的移动需要消耗一些能量。

NOI92 试题第一题：文章排版把一段文章按要求排版文章的输入方式为：由键盘输入一个以回车符结束的文章（最大长度2000个字符）。

排版时以单词为基本单位。

单词由不含空格的任意字符组成，是长度小于20 个字符的串。

空格符是分隔单词的唯一字符，在输入时连续的空格符在处理时应首先化简为单个空格。

在排版前应先输入排版后每行的字符数N，排版后将整理好的文章按行输出。

输出时应保证不将一个完整的单词截断，并且要求输出的总行数最小。

将每个不足N个字符的行用空格符补足，填充空格符的方式有以下3种：1.将填充的空格符置于每行的末尾，并要求每行的起始为单词。

2.将填充的空格符置于每行的起始，并要求每行的末尾为单词。

3.将填充的空格符尽可能平均分配在每行中，并保证每行的起始和末尾均为单词。

试编程对输入的一段文阐分别完成上述三个要求。

第二题：逻辑表达式由英文字符和符号和符号～、*、＋、（）组成逻辑表达式，英文字母表示变量，变量有两种可能的取值，False或True；～、*、＋。

括号（）可改变表达式的运算次序，且可以嵌套。

两个逻辑表达式等价，当且仅当两个公式中相同名字的变量取任何一种值时两个公式的值都相同。

如：A*(B+C) 与 A*B+A*C 等价A*(～A+B) 与 A*B 等价(～A+A)*BC 与 B+C 等价A*B+A*～B 与 A 等价而：A+B 与 A*B 不等价A*B+～C 与 A*E+～F 不等价现要求你编程解决下列问题：任务1用键盘输入一个逻辑表达式，判断这个表达式的合法性；任务2 将键盘输入的表达式化简，化简的表达式为a1*a2*...*aN+b1**b2*...*bM+...+x1*x2* (x)其中ai、bj、…xk(i=1,2,…n; j=1,2,…m; k=1,2,…1)表示一个变量或一个变量的逻辑非；任务3将任务2中的化简的表达式化为最简形式。

所谓最简有如下两个条件：(1)表达式中的＂＋＂号最少；(2)满足的条件下＂＋＂号最少。

noi 2.2波兰表达式波兰表达式，也称逆波兰表达式（Reverse Polish Notation，简称RPN）是一种数学表达式的形式，其中运算符位于与之相关的操作数之后。

波兰表达式的优势在于没有括号，并且对于计算机来说更容易解析和计算。

下面将详细介绍波兰表达式的原理和应用。

波兰表达式的特点是将运算符放在操作数的后面。

例如，常见的中缀表达式“3 + 4”在波兰表达式中表示为“3 4 +”。

更复杂的例子，中缀表达式“(5 - 3) * 4”在波兰表达式中表示为“5 3 - 4 *”。

波兰表达式的计算方法相对简单，只需遵循以下步骤：1. 从左到右扫描表达式，直到遇到运算符或者操作数。

2. 如果遇到操作数，将其推入栈中。

3. 如果遇到运算符，从栈顶弹出两个操作数，并进行运算。

将结果推入栈中。

4. 重复步骤2和3，直到表达式被扫描完毕。

5. 最后，栈中的唯一元素即为计算结果。

波兰表达式的一个重要应用是在计算机科学中的计算器和编译器中。

因为波兰表达式不需要括号，所以对于计算机来说更容易解析和计算，可以减少解析表达式的复杂性。

此外，波兰表达式的计算过程也可以通过栈数据结构来实现，使得计算过程更加高效。

波兰表达式还可以用于计算机领域的其他方面，例如表达式解析、逻辑运算等。

在逻辑运算中，波兰表达式可以更直观地表示多个条件的组合，并对其进行计算。

与传统的中缀表达式相比，波兰表达式不需要考虑运算符的优先级和括号的匹配，使得计算过程更加简单和直观。

总结一下，波兰表达式是一种将运算符放在操作数后面的数学表达式形式。

波兰表达式的优点在于没有括号，并且对于计算机来说更易于解析和计算。

波兰表达式在计算器、编译器和其他计算机领域中有广泛的应用。

通过栈数据结构实现波兰表达式的计算过程也使得计算更加高效。

在逻辑运算中，波兰表达式可以更直观地表示多个条件的组合，并对其进行计算。

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

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

1．微型计算机中，控制器的基本功能是（）。

A. 控制机器各个部件协调工作B. 实现算术运算和逻辑运算C. 获取外部信息D. 存放程序和数据2. 设A=true，B=false，C=true，D=false，以下逻辑运算表达式值为真的是（）。

A. (A∧B)∨(C∧D∨⌝A)B. ((⌝A∧B)∨C)∧⌝DC. (B∨C∨D)∧D∧AD. A∧(D∨⌝C)∧B3. 在下列关于图灵奖的说法中，不正确的是（）。

A. 图灵奖是美国计算机协会于1966年设立的，专门奖励那些对计算机事业作出重要贡献的个人B. 图灵奖有“计算机界诺贝尔奖”之称C. 迄今为止，还没有华裔计算机科学家获此殊荣D. 图灵奖的名称取自计算机科学的先驱、英国科学家阿兰·图灵4．计算机在工作过程中，若突然停电，（）中的信息不会丢失。

A. ROM和RAMB. CPUC.ROMD. RAM5．完全二叉树共有2*N-1个结点，则它的叶节点数是（）。

A. N-1B. NC. 2*ND. 2N-16. 在以下各项中，（）不是操作系统软件。

A. SolarisB. LinuxC. Windows VistaD. Sybase7．设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，f，e，c，a，则栈S的容量至少应该是（）。

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

A. 123.21B. 131.22C. 130.22D. 130.219. 设字符串S=”Olympic”，S的非空子串的数目是（）。

A. 28B. 29C. 16D. 1710．Web2.0是近年来互联网的热门概念之一，其核心思想是互动与分享。

NOIP2020（第二十届）初赛普及组C语言试题及答案NOIP2020（第二十届）初赛普及组C语言试题及答案第二十届全国青少年信息学奥林匹克联赛初赛普及组C语言试题竞赛l 不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。

一、单项选择题（共20题，每题1.5分，共计30分；每题有且仅有一个正确选项）1. 以下哪个是面向对象的高级语言（）。

A. 汇编语言B. C++C. FortranD. Basic 2. 1TB代表的字节数量是（）。

A. 2的10次方B. 2的20次方C. 2的30次方D. 2的40次方3. 二进制数00100100和00010101的和是（）。

A. 00101000B. 001010100C. 01000101D. 00111001 4. 以下哪一种设备属于输出设备（）。

A. 扫描仪B. 键盘C. 鼠标D. 打印机5. 下列对操作系统功能的描述最为完整的是（）。

A. 负责外设与主机之间的信息交换B. 负责诊断机器的故障C. 控制和管理计算机系统的各种硬件和软件资源的使用D. 将源程序编译成目标程序 6. CPU、存储器、I/O设备是通过（）连接起来的。

A. 接口B. 总线C. 控制线D. 系统文件7. 断电后会丢失数据的存储器是（）。

A. RAMB. ROMC. 硬盘D. 光盘8. 以下哪一种是属于电子邮件收发的协议（）。

A. SMTPB. UDPC. P2PD. FTP 9. 下列选项中不属于图像格式的是（）。

A. JPEG格式B. TXT格式C. GIF格式D. PNG格式10. 链表不具有的特点是（）。

A. 不必事先估计存储空间B. 可随机访问任一元素C. 插入删除不需要移动元素D. 所需空间与线性表长度成正比11. 下列各无符号十进制整数中，能用八位二进制表示的数中最大的是（）。

A. 296B. 133C. 256D. 199 12. 下列几个32位IP地址中，书写错误的是（）。

NOI题库简介NOI（全国青少年信息学奥林匹克竞赛）是中国面向中学生的最高级别的计算机竞赛，也是全国范围内最有影响力的信息学竞赛之一。

由中国计算机学会主办，自2002年起每年举办一次。

NOI题库是为了帮助参加NOI竞赛的学生进行练习和备考而创建的。

这个题库包含了历年来全国青少年信息学奥林匹克竞赛以及一些相关比赛的题目，涵盖了各个难度级别的问题。

使用说明题目类型•选择题：提供多个选项，选出正确答案。

•填空题：给出一个问题或不完整的代码，需要填写正确的答案或代码。

•编程题：给出一个问题或完整的代码，需要按要求进行编程实现。

练习方式你可以选择按照难度或者年份来练习。

每个题目都有对应的题目编号，你可以按照编号进行练习。

Markdown支持为了便于学习和整理，我们将题库以Markdown格式提供。

Markdown是一种轻量级标记语言，通过简单的文本格式可以方便地输出富文本内容。

你可以使用任何支持Markdown格式的编辑器或者在线平台进行查看和编辑题目。

题库内容难度级别•初级：适合刚入门的学生，难度较低。

•中级：比初级稍难，适合已经掌握基本知识的学生。

•高级：最难的级别，适合拥有较高编程水平的学生。

题目分类题库中的题目按照不同的分类进行分组，目前包括以下分类：•数学•字符串处理•图论•动态规划•数据结构•搜索算法•模拟•高级算法示例题目题目1-选择题问题：下列哪个不属于基本的数据类型？A. intB. floatC. stringD. bool答案：C题目2-填空题问题：请将下面代码中的缺失部分补充完整，使得程序可以输出。

括号匹配-算法详细题解LeetCode 题⽬:有效的括号给定⼀个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满⾜：左括号必须⽤相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

⽰例 1:输⼊: "()"输出: true⽰例 2:输⼊: "()[]{}"输出: true⽰例 3:输⼊: "(]"输出: false/*** @author cosefy* @date 2020/6/8*/public class ValidParenthesis {public static void main(String[] args) {String s = "";System.out.println(s);boolean b = isValid_Test1(s);boolean b = isValid_Test2(s);System.out.println("结果是： " + b);}//解法⼀：采⽤栈的辅助/*思路：循环遍历字符串，遇到左括号就压栈，否则就出栈，出栈时判断栈是否为空，遍历结束后，记得判断栈空。

分析：⼀趟遍历，时间复杂度为O（n）易错点：注意栈空的判断思考：-执⾏⽤时很少，但内存消耗有点多，考虑是否有办法节约内存。

-可以判断字符串的长度是否为0或者为奇数，直接返回结果*/public static boolean isValid_Test1(String s) {if (s.length() == 0)return true;if (s.length() % 2 != 0)return false;Stack<Character> stack = new Stack<>();for (char c : s.toCharArray()) {if (c == '(' || c == '{' || c == '[') {stack.push(c);} else {if (stack.isEmpty())return false;char cc = stack.pop();if ((cc == '(' && c != ')') || (cc == '{' && c != '}') || (cc == '[' && c != ']'))//上述判断语句也可⽤HashMap存储三对括号来查询实现。

noi 基础知识题库【原创实用版】目录1.noi 基础知识题库的概述2.noi 基础知识题库的内容3.noi 基础知识题库的应用4.如何有效地使用 noi 基础知识题库正文一、noi 基础知识题库的概述oi 基础知识题库，是指全国青少年信息学奥林匹克竞赛（National Olympiad in Informatics，简称 NOI）所涉及的知识点及其相关题目的集合。

它旨在为参赛选手提供丰富的学习资源，帮助他们在比赛中取得优异成绩。

作为我国青少年信息学领域的顶级赛事，NOI 一直以来都备受关注，选拔出的优秀选手还将代表我国参加国际信息学奥林匹克竞赛（IOI）。

二、noi 基础知识题库的内容oi 基础知识题库的内容涵盖了计算机科学、程序设计、数据结构和算法等多个方面。

根据题目的难度和知识点，题库可以分为以下几个部分：1.计算机基础知识：包括计算机系统的组成、操作系统、计算机网络等。

2.程序设计语言：主要涉及 C++、Pascal 等编程语言。

3.数据结构：如数组、链表、栈、队列、树、图等。

4.算法设计与分析：涉及贪心、分治、动态规划、回溯、分支界限等常用算法。

5.竞赛技巧与实战：包括题目分析、算法实现、编程调试等。

三、noi 基础知识题库的应用对于参加 NOI 的选手来说，基础知识题库是必备的学习资料。

选手可以通过学习和练习题库中的题目，提高自己的编程能力和解决问题的能力。

此外，题库还可以作为教练员培训、教学参考以及学术研究等用途。

四、如何有效地使用 noi 基础知识题库要充分发挥 noi 基础知识题库的作用，需要做到以下几点：1.系统学习：按照题库的知识点体系进行学习，从基础到高级，逐步提高自己的水平。

2.动手实践：对于每一个知识点，都要亲自编写代码实现，加深对知识点的理解。

3.总结反思：在做题过程中，要注重总结和反思，掌握题目的解题思路和方法。

4.交流分享：多与同学、教练进行交流和讨论，分享学习心得和经验。