2026年17年noip普及组初赛试题答案

2026年17年noip普及组初赛试题答案

一、单项选择题，(总共10题，每题2分)1.以下关于计算机硬件的描述中，错误的是（）。A.CPU是计算机的核心部件，负责执行指令B.内存的读写速度比硬盘快C.显卡的主要功能是处理图像数据D.键盘和鼠标都属于输出设备2.二进制数110101转换为十进制数的结果是（）。A.53B.54C.55D.563.操作系统属于计算机系统中的（）。A.应用软件B.系统软件C.工具软件D.数据库软件4.以下哪个不是常见的计算机操作系统（）。A.Windows10B.macOSC.LinuxD.Android5.在C++语言中，以下哪个是合法的变量名（）。A.2nd_bB._nameC.intD.if6.执行语句“for(i=1;i<=5;i++)”后，变量i的值是（）。A.4B.5C.6D.不确定7.以下算法中，时间复杂度为O(logn)的是（）。A.冒泡排序B.二分查找C.快速排序D.选择排序8.十进制数255转换为二进制数是（）。A.11111111B.11111110C.11111100D.111110009.一个栈的入栈序列是1,2,3,4，则不可能的出栈序列是（）。A.4,3,2,1B.1,2,3,4C.1,3,2,4D.3,4,2,110.以下关于算法的描述，正确的是（）。A.算法必须有输入和输出B.算法的步骤必须是有限的C.算法的每个步骤都有明确的执行顺序D.算法的时间复杂度越低越好二、填空题，(总共10题，每题2分)1.计算机中的最小数据单位是______。2.十进制数89转换为十六进制数是______。3.在Python中，列表的append方法的作用是______。4.执行代码x=5,y=3,x=x+y,y=x-y,x=x-y后，x的值是______。5.数组arr=[1,3,5,7,9]，arr[2]的值是______（数组下标从0开始）。6.斐波那契数列F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)，则F(6)=______。7.IP地址192.168.1.100/24的网络地址是______。8.执行循环“foriinrange(1,5):print(i,end="")”后，输出结果是______。9.n边形的内角和公式是______度。10.在排序算法中，稳定排序是指相等元素相对顺序不变，______排序是稳定的（填“冒泡”或“快速”）。三、判断题，(总共10题，每题2分)1.计算机的主频越高，执行程序的速度一定越快。（）2.所有程序都可以在不同操作系统上运行。（）3.操作系统可以管理计算机的硬件和软件资源。（）4.变量是程序中存储数据的容器，其值可以被修改。（）5.递归函数一定比非递归函数效率低。（）6.有序数组的二分查找时间复杂度为O(logn)。（）7.计算机中的字符都是用ASCII码表示的。（）8.冒泡排序的时间复杂度在最好情况下为O(n²)。（）9.计算机系统包括硬件和软件两部分。（）10.数组的大小在定义后可以动态改变。（）四、简答题，(总共4题，每题5分)1.请简述算法的五个基本特性。2.解释递归算法的概念，并举例说明其优势和可能的缺点。3.描述快速排序算法的基本思想和时间复杂度。4.给出Python代码“s="HelloWorld";print(s[::-1])”，说明其功能并写出输出结果。五、讨论题，(总共4题，每题5分)1.设计找出数组中最大值和最小值的算法，分析时间复杂度。2.分析“for(inti=0;i<5;i++){for(intj=i+1;j<5;j++){if(a[i]>a[j]){swap(a[i],a[j]);}}}”代码的功能和可能的错误。3.从(0,0)到(9,9)只能右或下移动，计算路径数并描述算法。4.比较DFS和BFS在解决最短路径问题中的应用场景和优缺点。答案和解析：一、单项选择题1.D（键盘鼠标是输入设备）2.A（110101=32+16+4+1=53）3.B（操作系统是系统软件）4.D（Android是移动系统，非PC端）5.B（变量名不能以数字开头或为关键字）6.C（循环结束后i=5+1=6）7.B（二分查找时间复杂度O(logn)）8.A（255=2^8-1=11111111）9.D（栈是后进先出，3,4,2,1无法实现）10.B（算法必须有有限步骤）二、填空题1.位（bit）2.59（89=5×16+9）3.在列表末尾添加元素4.3（x=8,y=5,x=8-5=3）5.5（下标0:1,1:3,2:5）6.8（F(3)=2,F(4)=3,F(5)=5,F(6)=8）7.192.168.1.0（/24表示24位网络位）8.1234（range(1,5)生成1-4）9.(n-2)×18010.冒泡（快速排序不稳定）三、判断题1.×（影响速度的因素不止主频）2.×（需跨平台适配）3.√（操作系统管理软硬件资源）4.√（变量值可修改）5.×（递归优化后效率可提升）6.√（二分查找复杂度O(logn)）7.×（还可用Unicode）8.×（最好情况已排序时为O(n)）9.√（系统=硬件+软件）10.×（静态数组大小固定）四、简答题1.算法五个特性：①有穷性：步骤有限且终止；②确定性：每步无歧义；③可行性：可执行；④输入：0或多输入；⑤输出：1或多输出。如计算斐波那契数列的循环算法满足所有特性。2.递归算法指函数直接/间接调用自身。优势：逻辑简洁（如汉诺塔问题），适合递归结构；缺点：递归深度过大易栈溢出，重复计算（如斐波那契递归）。优化：尾递归优化、记忆化搜索。3.快速排序：选基准元素，分区（小于放左，大于放右），递归处理子数组。时间复杂度：平均O(nlogn)，最坏O(n²)（如已排序数组），通过随机选基准可避免最坏情况。4.功能：Python切片s[::-1]反转字符串，“HelloWorld”反转后为“dlroWolleH”。输出结果：dlroWolleH。五、讨论题1.算法：初始化max/min为第一个元素，遍历数组更新。时间复杂度O(n)，空间O(1)。如数组arr，i从1到n-1，比较更新max/min，最终输出。2.功能：冒泡排序（相邻元素比较交换），将数组升序排列。无错误，但优化可加标志位提前终止。3.路径数：C(18,9)=48620。算法：