CSP-J 历年初赛选择题历年真题分类解析与答案

---

一、编程与计算机基础 - 答案与解析

[1] [2014] 以下哪个是面向对象的高级语言 ( )

• 答案：B
• 解析： 对于计算机语言，分为低级语言（如机器语言、汇编语言）和高级语言。C++ 是面向对象的高级语言，而 Fortran 和 Basic 是面向过程的高级语言。

[2] [2017] 下列不属于面向对象程序设计语言的是（ ）。

• 答案：A
• 解析： C 语言是面向过程的结构化编程语言；而 C++、Java、Python 均支持面向对象程序设计。

[3] [2024] 以下哪个不是C++中的基本数据类型？

• 答案：C
• 解析： struct（结构体）是用户自定义的复合（构造）数据类型，不属于 C++ 的基本（内置）数据类型（如 int, float, char 等）。

[4] [2021] 以下不属于面向对象程序设计语言的是（ ）。

• 答案：D
• 解析： C 语言是面向过程的；C++、Python、Java 均支持面向对象。

[5] [2022] 以下哪种功能没有涉及 C++语言的面向对象特性支持：（ ）。

• 答案：A
• 解析： printf 是从 C 语言继承而来的标准输入输出函数，属于过程化函数，未体现面向对象的特性（如类、对象、封装、继承、多态）。

[6] [2023] 在C++中，下面哪个关键字用于声明一个变量，其值不能被修改？（ ）。

• 答案：B
• 解析： const 用于修饰常量，其值一旦初始化后便不能被修改。unsigned 是无符号修饰符，static 是静态变量关键字，mutable 用于修饰在常成员函数中仍可修改的成员。

[7] [2011] 在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（ ）。

• 答案：A
• 解析： 空间复杂度是指算法在计算机内执行时所需存储空间的度量，即程序运行时理论上所占用的内存空间。

[8] [2018] 以下排序算法中，不需要进行关键字比较操作的算法是（ ）。

• 答案：A
• 解析： 基数排序（Radix Sort）是通过“分配”和“收集”桶排序原理来实现的，不需要对关键字进行大小比较。

[9] [2010] Pascal语言、C语言和C++语言都属于（ ）。

• 答案：D
• 解析： Pascal、C 和 C++ 均需要通过编译器（Compiler）将源代码整体编译为机器指令后才能运行，属于编译性语言。

[10] [2011] 关于汇编语言，下列说法错误的是（ ）

• 答案：D
• 解析： 汇编语言并没有被完全淘汰，它在底层硬件驱动、嵌入式系统以及对性能要求极高的底层开发中依然广泛使用。

[11] [2008] 面向对象程序设计（Object-Oriented Programming）是一种程序设计的方法论...下面关于面向对象程序设计的说法中，不正确的是（ ）。

• 答案：A
• 解析： 面向对象程序设计通常采用的是“自底向上”的设计方法（先设计底层类和对象，再组合构建系统），而不是自顶向下。

[12] [2009] 关于程序设计语言，下面哪个说法是正确的：

• 答案：C
• 解析： 高级语言由于屏蔽了底层硬件的差异，相比低级语言（如汇编）具有更好的可移植性，更容易实现跨平台。

[13] [2020] 编译器的主要功能是（ ）。

• 答案：A
• 解析： 编译器的核心功能是将高级语言编写的源程序翻译成目标机器的机器指令代码。

[14] [2024] 编译器的主要作用是什么（）？

• 答案：B
• 解析： 编译器（Compiler）的根本作用就是将高级语言源代码转换（翻译）为计算机能直接执行的机器代码。

[15] [2014] 以下哪一种设备属于输出设备 ( )

• 答案：D
• 解析： 扫描仪、键盘、鼠标均属于输入设备，打印机用于将计算机中的信息输出到纸张上，属于输出设备。

[16] [2018] 以下哪一种设备属于输出设备

• 答案：D
• 解析： 同上，打印机是典型的输出设备。

[17] [2020] 设 x=true, y=true, z=false，以下逻辑运算表达式值为真的是（ ）。

• 答案：D
• 解析： 代入布尔值：A项 (1+0)*1*0=0；B项 1*(0+1)*0=0；C项 (1*1)*0=0；D项 (1*1)+(0+1) = 1+1 = 1（真）。

[18] [2013] 逻辑表达式（）的值与变量A 的真假无关。

• 答案：C
• 解析： 根据逻辑代数分配律，$(A\land B)\lor (\neg A\land B) = (A\lor \neg A)\land B = 1\land B = B$，结果恒等于 $B$，与变量 $A$ 的真假无关。

[19] [2010] 以下逻辑表达式的值恒为真的是（ ）。

• 答案：A
• 解析： 利用真值表或逻辑等价变换可验证 A 选项恒为真（永真式）。

[20] [2008] 设A=true，B=false，C=true，D=false，以下逻辑运算表达式值为真的是（ ）。

• 答案：B
• 解析： 逐一代入布尔值计算，表达式 B 的计算结果为真（true）。

[21] [2019] 二进制数11 1011 1001 0111和01 0110 1110 1011进行逻辑与运算的结果是（）。

• 答案：A
• 解析： 逻辑与（&）运算规则为“对应位全为1才为1”，逐位对齐计算即可得出 A。

[22] [2008] 在C++程序中，表达式200|10的值是（ ）。

• 答案：D
• 解析： 按位或运算（|）：$200_{10} = 11001000_2$，$10_{10} = 00001010_2$，按位或得 $11001010_2 = 202_{10}$。

[23] [2025] 在 C++ 中，执行下述代码后，输出的结果是？（）

• 答案：B
• 解析： 255 的二进制为 11111111，254 的二进制为 11111110，两数按位与（&）的结果为 254（x & (x - 1) 的经典作用是消去二进制末尾的 1，但此处直接看数值按位与即可）。

[24] [2014] CPU、存储器、 I/O 设备是通过 ( ) 连接起来的。

• 答案：B
• 解析： 总线（Bus）是计算机各部件之间传送信息的公共通道。

[25] [2014] 断电后会丢失数据的存储器是 ( )

• 答案：A
• 解析： RAM（随机存取存储器）是易失性存储器，断电后数据清空。

[26] [2014] 下列选项中不属于图像格式的是 ( )

• 答案：B
• 解析： TXT 是纯文本格式；JPEG、GIF、PNG 均为常见的图像格式。

[27] [2014] 计算机界的最高奖是 ( )

• 答案：C
• 解析： 图灵奖（Turing Award）是计算机科学领域的最高奖项。

[28] [2015] 在 PC机中， PENTIUM(奔腾 ) 、酷睿、赛扬等 是指 ( )

• 答案：C
• 解析： 奔腾、酷睿、赛扬均是 Intel 公司生产的 CPU 型号系列。

[29] [2015] 下列说法正确的是 ( )

• 答案：A
• 解析： CPU 的主要核心任务是执行数据算术逻辑运算和程序控制。

[30] [2015] 以下断电后仍能保存数据的有（ ）。

• 答案：D
• 解析： 硬盘属于外部存储设备，断电后数据不丢失；RAM、高速缓存、显存均在断电后丢失数据。

[31] [2015] 下列选项中不属于视频文件格式的是 ( )

• 答案：A
• 解析： TXT 是文本文件，不属于视频格式。

[32] [2016] 以下不是微软公司出品的软件是 （ ）。

• 答案：D
• 解析： Acrobat Reader 是 Adobe 公司的产品，其余三者为微软 Office 套件。

[33] [2016] 以下不属于无线通信技术的是 （ ）

• 答案：D
• 解析： 以太网（Ethernet）是有线局域网的标准。

[34] [2016] 以下不是 CPU 生产厂商的是 （ ）。

• 答案：C
• 解析： Microsoft（微软）是软件公司，不生产处理器硬件。

[35] [2016] 以下不是存储设备的是 （ ）。

• 答案：D
• 解析： 鼠标是输入设备，光盘、磁盘、固态硬盘是存储设备。

[36] [2016] 以下是 32 位机器和 64 位机器的区别的是（ ）。

• 答案：C
• 解析： 32 位和 64 位系统最核心的差异在于其 CPU 寄存器位宽及最大内存寻址空间不同。

[37] [2016] 参加 NOI 比赛，以下不能带入考场的是 （ ）。

• 答案：C
• 解析： U 盘属于外部存储设备，严禁带入考场。

[38] [2017] 计算机存储数据的基本单位是（ ）。

• 答案：B
• 解析： 字节（Byte）是计算机数据存储的基本单位（1 Byte = 8 bits）。

[39] [2017] 计算机应用的最早领域是（ ）。

• 答案：A
• 解析： 计算机最初被研制出来主要用于军事和科学计算中的数值计算。

[40] [2017] NOI 的中文意思是（ ）。

• 答案：B
• 解析： NOI 全称为 National Olympiad in Informatics（全国青少年信息学奥林匹克竞赛）。

[41] [2017] 从（ ）年开始，NOIP 竞赛将不再支持 Pascal 语言。

• 答案：C
• 解析： 从 2022 年起，CCF 在全国青少年信息学奥林匹克系列竞赛中全面取消 Pascal 语言。

[42] [2017] 以下和计算机领域密切相关的奖项是（ ）。

• 答案：B
• 解析： 图灵奖被公认为计算机界的最高奖。

[43] [2018] 中国计算机学会于（ ）年创办全国青少年计算机程序设计竞赛。

• 答案：B
• 解析： 1984 年，在中国科协的支持下，CCF 举办了首届全国青少年计算机程序设计比赛。

[44] [2018] 下面的故事与（ ）算法有着异曲同工之妙...

• 答案：B
• 解析： 故事里套故事、无限嵌套且有相同结构，这正是“递归”算法的典型特征。

[45] [2019] 中国的国家顶级域名是（）

• 答案：A
• 解析： 中国国家顶级域名是 .cn。

[46] [2019] 以下哪个奖项是计算机科学领域的最高奖？（）

• 答案：A
• 解析： 图灵奖。

[47] [2020] 在内存储器中每个存储单元都被赋予一个唯一的序号，称为（）。

• 答案：A
• 解析： 内存中每个存储单元的唯一编号称为地址。

[48] [2020] 现有一张分辨率为 2048×1024 像素的 32 位真彩色图像...需要多大的存储空间？（ ）。

• 答案：C
• 解析： $\frac{2048 \times 1024 \times 32}{8} \text{ B} = 8 \text{ MB}$。

[49] [2012] 计算机如果缺少（ ），将无法正常启动。

• 答案：A
• 解析： 内存（RAM）是 CPU 运行程序的必经中转站，缺少内存计算机无法启动。

[50] [2012] 目前计算机芯片（集成电路）制造的主要原料是（ ），它是一种可以在沙子中提炼出的物质。

• 答案：A
• 解析： 半导体集成电路芯片的核心提炼原料是“硅（Si）”。

[51] [2012] 目前个人电脑的（ ）市场占有率最靠前的厂商包括Intel、AMD等公司。

• 答案：B
• 解析： Intel 和 AMD 是全球两大主流 CPU 芯片制造商。

[52] [2012] 1946年诞生于美国宾夕法尼亚大学的ENIAC属于（ ）计算机。

• 答案：A
• 解析： ENIAC 是世界上第一台通用电子计算机，采用电子管元件。

[53] [2012] 矢量图（Vector Image）图形文件...是因为它（ ）。

• 答案：B
• 解析： 矢量图是用数学公式（点、直线、多边形等几何图元）来描述图像的，因此无论如何放大都不会失真。

[54] [2012] 仿生学的问世开辟了独特的科学技术发展道路...错误的是（ ）

• 答案：B
• 解析： 因特网（Internet）是人类根据军事与科研通信需求人为设计构建的，并非模仿蜘蛛网发明。

[55] [2011] 摩尔定律是由英特尔创始人之一戈登·摩尔提出来的...单块集成电路的集成度大约每（ ）个月翻一番。

• 答案：C
• 解析： 摩尔定律指出：集成电路上可容纳的晶体管数目，约每 18 个月便会增加一倍。

[56] [2011] 寄存器是（ ）的重要组成部分。

• 答案：D
• 解析： 寄存器集成在中央处理器（CPU）内部，是 CPU 的重要组成部分。

[57] [2011] 生物特征识别...以下不属于生物特征识别技术及其应用的是（ ）。

• 答案：C
• 解析： ATM 机密码验证属于密码学验证，不依赖人体固有的生物特征。

[58] [2011] 1956年（ ）授予肖克利、巴丁和布拉顿...

• 答案：A
• 解析： 三人因对半导体研究和发明晶体管效应共同获得了 1956 年的诺贝尔物理学奖。

[59] [2011] 从ENIAC到当前最先进的计算机...冯诺依曼提醒结构的核心内容是（ ）。

• 答案：C
• 解析： 冯·诺依曼体系结构的核心设计思想是“存储程序”和“程序控制”。

[60] [2010] 提出“存储程序”的计算机工作原理的是（ ）。

• 答案：D
• 解析： 冯·诺依曼（John von Neumann）。

[61] [2010] 主存储器的存取速度比中央处理器...在CPU中引入了（ ）。

• 答案：B
• 解析： 为了弥补主存速度慢的瓶颈，利用局部性原理在 CPU 和主存之间引入了高速缓存（Cache）。

[62] [2010] 全国青少年信息学奥林匹克系列活动的主办单位是（ ）。

• 答案：D
• 解析： 主办单位为中国计算机学会（CCF）。

[63] [2009] 关于图灵机下面的说法哪个是正确的：

• 答案：D
• 解析： 图灵机是英国数学家阿兰·图灵提出的一种抽象的数学计算模型，属于理论模型。

[64] [2009] 关于计算机内存下面的说法哪个是正确的：

• 答案：B
• 解析： 1MB = 1024 × 1024 字节。

[65] [2009] 关于BIOS下面说法哪个是正确的：

• 答案：A
• 解析： BIOS 是英文 Basic Input Output System（基本输入输出系统）的缩写。

[66] [2009] 关于CPU下面哪个说法是正确的：

• 答案：A
• 解析： CPU 的全称是 Central Processing Unit（中央处理器）。

[67] [2009] 关于ASCII，哪个说法是正确的：

• 答案：B
• 解析： 标准 ASCII 码使用 7 个二进制位进行编码，在计算机内通常占用一个字节（8位）的存储空间。

[68] [2009] 在参加NOI系列竞赛过程中，下面哪一种行为是不被严格禁止的：

• 答案：B
• 解析： 在联机测试中通过手工计算出结果并在程序中直接输出虽然违背了算法初衷，但在当时部分老赛制的特定判罚或字面理解中属于“能拿分但不提倡”，而携带电子词典、搜索思路、多进程恶意攻击均属于严重违规（注：现代竞赛中直接输出答案亦属违规，此处依当年官方答案为准）。

[69] [2008] 微型计算机中，控制器的基本功能是（ ）。

• 答案：A
• 解析： 控制器负责指挥和控制计算机各部件协调统一工作。

[70] [2008] 在下列关于图灵奖的说法中，不正确的是（ ）。

• 答案：C
• 解析： 华裔计算机科学家姚期智曾于 2000 年获得图灵奖，因此 C 选项“还没有华裔科学家获此殊荣”表述错误。

[71] [2008] 计算机在工作过程中，若突然停电，（ ）中的信息不会丢失。

• 答案：C
• 解析： ROM（只读存储器）断电后数据依然完好保存。

[72] [2008] 在32*32点阵的“字库”中，汉字“北”与“京”的字模占用字节数之和是（ ）。

• 答案：B
• 解析： 每个汉字占 $\frac{32 \times 32}{8} = 128$ 字节，两个汉字共 $128 \times 2 = 256$ 字节。

[73] [2008] 下列不属于NOIP竞赛推荐使用的语言环境的是（ ）。

• 答案：B
• 解析： Visual C++ 不符合早期竞赛统一评测的标准推荐环境。

[74] [2021] 以下奖项与计算机领域最相关的是（ ）。

• 答案：B
• 解析： 图灵奖。

[75] [2021] 目前主流的计算机储存数据最终都是转换成（ ）数据进行储存。

• 答案：A
• 解析： 二进制。

[76] [2014] 下列对操作系统功能的描述最为完整的是 ( )

• 答案：C
• 解析： 操作系统是控制和管理计算机系统各种硬件和软件资源的核心系统软件。

[77] [2015] 操作系统的作用是 ( )

• 答案：C
• 解析： 有效控制和管理计算机系统的软硬件资源。

[78] [2015] 所谓的“中断”是指 ( )

• 答案：B
• 解析： 中断指 CPU 暂时中止当前程序，转去处理突发急需处理的事件。

[79] [2015] 计算机病毒是 ( )

• 答案：B
• 解析： 计算机病毒是由人为制造的、能侵入系统并破坏功能的程序或代码集合。

[80] [2013] CCF NOIP 复赛全国统一评测时使用的系统软件是（ ）。

• 答案：B
• 解析： 早期及近代复赛统一评测平台环境为 NOI Linux。

[81] [2013] 在 Windows 资源管理器中...操作选项，它的意思是（ ）。

• 答案：C
• 解析： 复制操作是将源文件放入剪贴板，同时在原位置保留原文件。

[82] [2012] （ ）不属于操作系统。

• 答案：C
• 解析： Photoshop 是图像处理应用软件，不是操作系统。

[83] [2011] 有人认为，在个人电脑送修前，将文件放入回收站中就是已经将其删除了...

• 答案：C
• 解析： 放入回收站或清空后，文件仅被标记为删除，底层数据未被物理覆写，仍可能通过数据恢复软件找回。

[84] [2010] Linux下可执行文件的默认扩展名为（ ）。

• 答案：D
• 解析： Linux 系统下可执行文件没有强制的扩展名限制（通常无扩展名或为 .out 等）。

[85] [2009] 下列软件中不是计算机操作系统的是：

• 答案：D
• 解析： WPS 是文字处理办公软件。

[86] [2008] 在以下各项中，（ ）不是操作系统软件。

• 答案：D
• 解析： Sybase 是数据库管理系统。

[87] [2023] 以下哪个不是操作系统？（ ）

• 答案：D
• 解析： HTML 是网页标记语言。

[88] [2024] 下面哪一个不是操作系统名字（）

• 答案：A
• 解析： Notepad 是文本记事本工具。

[89] [2014] 以下哪一种是属于电子邮件收发的协议 ( )

• 答案：A
• 解析： SMTP 是简单邮件传输协议。

[90] [2014] 以下哪一种属于 32 位 IP 地址，书写错误的是 ( )

• 答案：C
• 解析： IP 地址每个分段的取值范围必须在 $0 \sim 255$ 之间，256 越界错误。

[91] [2015] FTP可以用于 ( )

• 答案：A
• 解析： FTP 是文件传输协议，用于远程传输文件。

[92] [2017] 下列协议中与电子邮件无关的是（ ）。

• 答案：C
• 解析： WTO 是世界贸易组织。

[93] [2018] 广域网的英文缩写是（ ）

• 答案：B
• 解析： WAN（Wide Area Network）。

[94] [2013] IPv4 协议使用32 位地址...它正逐渐被使用（ ）位地址的 IPv6 协议所取代。

• 答案：D
• 解析： IPv6 地址长度为 128 位。

[95] [2013] 通常在搜索引擎中，对某个关键词加上双引号表示（ ）。

• 答案：C
• 解析： 加双引号代表完全匹配的精确搜索。

[96] [2013] 中国的国家顶级域名是（ ）。

• 答案：A
• 解析： .cn。

[97] [2012] 无论是TCP/IP模型还是OSI模型...体育比赛中，每一级比赛的优胜者晋级上一级比赛（ ）。

• 答案：A
• 解析： 对等层之间的协议通信类似于不同公司同级别经理之间的直接商务文件交互。

[98] [2012] （ ）是主要用于显示网页服务器或者文件系统的HTML文件的内容...的一种软件。

• 答案：B
• 解析： 浏览器（Browser）。

[99] [2012] （ ）是目前互联网上常用的E-mail服务协议。

• 答案：C
• 解析： POP3 用于接收邮件。

[100] [2012] 蓝牙和Wi-Fi都是（ ）设备。

• 答案：C
• 解析： 无线局域网（WLAN）。

[101] [2010] 在下列HTML语句中，可以正确产生一个指向NOI官方网站的超链接的是（ ）。

• 答案：B
• 解析： <a href="..."> 是正确的超链接语法。

[102] [2009] 关于互联网，下面的说法哪一个是正确的：

• 答案：C
• 解析： 互联网的基础核心协议是 TCP/IP 协议族。

[103] [2009] 关于HTML下面哪种说法是正确的：

• 答案：B
• 解析： HTML 全称为 HyperText Markup Language（超文本标记语言）。

[104] [2008] Web2.0是近年来互联网的热门概念之一...（ ）是典型的Web2.0应用。

• 答案：B
• 解析： Flickr 是早期典型的 Web 2.0 用户贡献内容与分享的图片网站。

[105] [2022] 运行以下代码片段的行为是（ ）。

• 答案：D
• 解析： 语句 p = q; 将指针 q 存储的地址赋给指针 p，使得 p 也指向了变量 y 的存储地址。

[106] [2023] 阅读下述代码，请问修改data的value成员以存储3.14，正确的⽅式是（ ）。

• 答案：A
• 解析： 通过联合体变量名直接访问成员：data.value = 3.14;。

[107] [2025] 10. 考虑以下 C++ 函数...在 main 函数调用 solve 后，x 和 y 的值分别是？（）

• 答案：C
• 解析： 第一个参数 int &a 是引用传递，会直接修改实参 x 的值；第二个参数 int b 是值传递，不影响实参 y。交换逻辑执行后，x 变为 10，y 保持 10 不变。

[108] [2014] 要求以下程序的功能是计算： s=1+1/2+1/3+...+1/10...导致错误结果的程序行是 ( )

• 答案：C
• 解析： 整数相除 1 / n 在 C++ 中结果为 0，必须写成 1.0 / n。

[109] [2014] 设变量 x 为 float 型且已赋值...将 x 中的数值保留到小数点后两位，并将第三位四舍五入的是 ( )

• 答案：C
• 解析： 先乘 100 加上 0.5 取整再除以 100.0：(int)(x * 100 + 0.5) / 100.0。

[110] [2024] 32位int类型的存储范围是（）

• 答案：C
• 解析： 带符号 32 位整数范围为 $-2^{31} \sim 2^{31}-1$，即 $-2147483648 \sim +2147483647$。

[111] [2025] 一个 32 位无符号整数可以表示的最大值，最接近下列哪个选项？（）

• 答案：A
• 解析： 32 位无符号整数最大值为 $2^{32}-1 \approx 4.29 \times 10^9$，最接近 $4 \times 10^9$。

---

二、数学 - 答案与解析

[1] [2014] 1TB代表的字节数是 ( )

• 答案：D
• 解析： $1\text{TB} = 1024\text{GB} = 1024^4\text{B} = 2^{40}\text{B}$。

[2] [2014] 二进制数 00100100 和 00010101 的和是 ( )

• 答案：D
• 解析： 按二进制加法竖式计算：$00100100_2 + 00010101_2 = 00111001_2$。

[3] [2014] 下列各无符号十进制整数中，能用八位二进制表示的数中最大的是 ( )

• 答案：D
• 解析： 8 位无符号二进制数的表数范围是 $0 \sim 255$，其中最大的是 255，选项中 199 在此范围内。

[4] [2015] 1MB等于 ( )

• 答案：D
• 解析： $1\text{MB} = 1024 \times 1024$ 字节。

[5] [2015] 二进制数 00100100和 00010100的和是 ( )

• 答案：D
• 解析： $36_{10} + 20_{10} = 56_{10} = 00111000_2$。

[6] [2015] 与二进制小数 0.1 相等的十六进制数是 ( )

• 答案：A
• 解析： 二进制 $0.1_2 = 0.5_{10} = 0.8_{16}$（$8 \times 16^{-1} = 0.5$）。

[7] [2016] 如果 $256$ 种颜色用二进制编码来表示 ，至少需要 （ ）位。

• 答案：C
• 解析： $2^8 = 256$，因此至少需要 8 位二进制编码。

[8] [2016] 二进制数 00101100 和 00010101 的和是 （ ）。

• 答案：B
• 解析： $44_{10} + 21_{10} = 65_{10} = 01000001_2$。

[9] [2016] 与二进制小数 0.1 相等的八进制数是 （ ）。

• 答案：B
• 解析： 二进制 $0.1_2 = 0.5_{10} = 0.4_8$（$4 \times 8^{-1} = 0.5$）。

[10] [2017] 在8位二进制补码中，10101011 表示的数是十进制下的（ ）

• 答案：B
• 解析： 补码 10101011 求原码：符号位不变，其余位减 1 取反得 `11010101_2 = -85_{10}$。

[11] [2017] 分辨率为 800x600、16位色的位图，存储图像信息所需的空间为（ ）。

• 答案：A
• 解析： $\frac{800 \times 600 \times 16}{8} \text{ B} = 960000 \text{ B} \approx 937.5 \text{ KB}$。

[12] [2017] 十进制小数 13.375 对应的二进制数是（ ）。

• 答案：A
• 解析： 整数部分 $13 = 1101_2$，小数部分 $0.375 \times 2 = 0.75(0), 0.75 \times 2 = 1.5(1), 0.5 \times 2 = 1.0(1)$，合为 1101.011。

[13] [2018] 下列四个不同进制的数中，与其它三项数值上不相等的是

• 答案：D
• 解析： $(269){16} = 617{10}$，$(1151)8 = 617{10}$，而 $(1001101011)2 = 619{10}$，数值不相等。

[14] [2018] 1MB 等于（ ）

• 答案：D
• 解析： $1024 \times 1024$ 字节。

[15] [2018] 为了统计一个非负整数的二进制形式中 1 的个数...空格内要填入的语句是（ ）。

• 答案：B
• 解析： x &= x - 1 可以高效清零二进制数中最右侧的一个 1。

[16] [2019] 二进制数11 1011 1001 0111和01 0110 1110 1011进行逻辑与运算的结果是（）。

• 答案：A
• 解析： 逐位按位与运算得出 A。

[17] [2019] 一个32位整型变量占用（）个字节。

• 答案：C
• 解析： $32 \text{ bits} / 8 = 4 \text{ Bytes}$。

[18] [2020] 二进制数 1011 转换成十进制数是（ ）。

• 答案：A
• 解析： $1011_2 = 8 + 2 + 1 = 11_{10}$。

[19] [2013] 把 64 位非零浮点数强制转换成32 位浮点数后，不可能 （）。

• 答案：D
• 解析： 精度截断不会改变原浮点数的正负符号位。

[20] [2013] 一个 32 位整型变量占用（ ）个字节。

• 答案：A
• 解析： 4 个字节。

[21] [2013] 二进制数 11.01 在十进制下是（ ）。

• 答案：A
• 解析： $11_2 + 0.01_2 = 3 + 0.25 = 3.25$。

[22] [2013] 在十六进制表示法中，字母 A 相当于十进制中的（ ）。

• 答案：B
• 解析： 十六进制中 A 代表 10。

[23] [2012] 十六进制数9A在（ ）进制下是232。

• 答案：B
• 解析： $9\text{A}{16} = 154{10} = 232_8$（$2 \times 64 + 3 \times 8 + 2 = 154$）。

[24] [2012] 地址总线的位数决定了CPU可直接寻址的内存空间大小...理论上最大可寻址的内存空间为（ ）。

• 答案：D
• 解析： $2^{32} \text{ B} = 4 \text{ GB}$。

[25] [2011] 在二进制下，1011001 + （ ） = 1100110。 q

• 答案：B
• 解析： $1100110_2 - 1011001_2 = 1101_2$。

[26] [2011] 字符“0”的ASCII码为48，则字符“9”的ASCII码为（ ）。

• 答案：B
• 解析： $48 + 9 = 57$。

[27] [2011] 一片容量为8G的SD卡能储存大约（ ）张大小为2MB的数码照片。

• 答案：C
• 解析： $8192 \text{ MB} / 2 \text{ MB} = 4096$，最接近 4000 张。

[28] [2011] 一个正整数在二进制下有100位，则它在十六进制下有（ ）位。

• 答案：C
• 解析： $\lceil 100 / 4 \rceil = 25$ 位。

[29] [2010] 浮点数2E+03表示（ ）。

• 答案：D
• 解析： $2 \times 10^3 = 2000$。

[30] [2010] 一个字节（byte）由（ ）个二进制位组成。

• 答案：A
• 解析： 8 个二进制位。

[31] [2010] 设X、Y、Z分别代表三进制下的一位数字...等式XY * ZX = （ ）也成立。

• 答案：B
• 解析： 代入三进制按位运算推导验证得 B。

[32] [2010] 一个字长为8位的整数的补码是11111001，则它的原码是（ ）。

• 答案：D
• 解析： 补码求原码：减 1 取反（符号位不变）得 10000111。

[33] [2010] 一个自然数在十进制下有n位，则它在二进制下的位数与（ ）最接近。

• 答案：B
• 解析： 根据对数换底公式，二进制位数约为 $n \times \log_2 10 = n \times \frac{1}{\log_{10} 2}$。

[34] [2009] 已知大写字母A的ASCII编码为65（10进制），则大写字母J的10进制ASCII编码为：

• 答案：D
• 解析： 'J' 的 ASCII 码为 $65 + 9 = 74$，由于选项中无 74 故选 D（以上都不是）。

[35] [2009] 十进制小数125.125对应的8进制数是

• 答案：C
• 解析： $125_{10} = 175_8$，$0.125_{10} = 0.1_8$，合为 $175.1_8$。

[36] [2008] 与十进制数28.5625相等的四进制数是（ ）。

• 答案：D
• 解析： $28_{10} = 130_4$，$0.5625_{10} = 0.21_4$，合为 $130.21_4$。

[37] [2021] 二进制数 101.11 对应的十进制数是（ ）。

• 答案：C
• 解析： $4 + 0 + 1 + 0.5 + 0.25 = 5.75$。

[38] [2022] 八进制数 32.1 对应的十进制数是（ ）。

• 答案：C
• 解析： $3 \times 8 + 2 + 1 \times 0.125 = 26.125$。

[39] [2023] 八进制数12345670(8) 和07654321(8)的和为（ ）

• 答案：D
• 解析： 八进制竖式加法计算，结果为 $22222211_8$。

[40] [2023] 数101010(2)和166(8)的和为（ ）。

• 答案：D
• 解析： $42_{10} + 118_{10} = 160_{10} = A0_{16}$。

[41] [2024] 计算（14₈-1010₂)*D₁₆-1101₂的结果，并选择答案的十进制值：（ ）

• 答案：A
• 解析： $(12 - 10) \times 13 - 13 = 2 \times 13 - 13 = 13$。

[42] [2024] 记1Kb位1024字节（byte），1MB位1024KB，那么1MB是多少二进制位（bit）?

• 答案：D
• 解析： $1024 \times 1024 \times 8 = 8388608$。

[43] [2025] 十进制数 $720_{10}$ 和八进制数 $270_8$ 的和用十六进制表示是多少？（）

• 答案：A
• 解析： $720 + 184 = 904_{10} = 388_{16}$。

[44] [2016] 有 7 个一模一样的苹果，放到 3 个一样的盘子中，一共有（ ）种放法。

• 答案：B
• 解析： 整数拆分（不区分盘子与苹果顺序）：共 8 种放法。

[45] [2017] 甲、乙、丙三位同学选修课程...不同的选修方案共有（ ）种。

• 答案：C
• 解析： $C_4^2 \times C_4^3 \times C_4^3 = 6 \times 4 \times 4 = 96$ 种。

[46] [2018] 设含有 $10$ 个元素的集合的全部子集数为 $S$...则 $T / S$ 的值为（ ）。

• 答案：B
• 解析： $\frac{C_{10}^7}{2^{10}} = \frac{120}{1024} = \frac{15}{128}$。

[47] [2019] 把8个同样的球放在5个同样的袋子里...问共有多少种不同的分法？（）

• 答案：C
• 解析： 枚举非零数字个数进行整数拆分，共 18 种。

[48] [2019] —些数字可以颠倒过来看...请问这个城市最多有多少个车牌倒过来恰好还是原来的车牌？（）

• 答案：C
• 解析： 首尾呼应，对称位置选择限制，共 $5 \times 5 \times 3 = 75$ 个。

[49] [2020] 10 个三好学生名额分配到 7 个班级...一共有（ ）种不同的分配方案。

• 答案：A
• 解析： 利用插板法：$C_{9}^6 = 84$ 种。

[50] [2020] 有五副不同颜色的手套...一次性从中取 6 只手套，请问恰好能配成两副手套的不同取法有（ ）种。

• 答案：A
• 解析： 组合公式计算得 $(C_5^2 \times C_6^1 + C_4^1) / 2 = 120$ 种。

[51] [2008] 将数组{8, 23, 4, 16, 77, -5, 53, 100}中的元素按从大到小的顺序排列...最少需要交换（ ）次。

• 答案：B
• 解析： 逆序对与最少交换次数推导，最少需 5 次交换。

[52] [2021] $6$ 个人，两个人组一队，总共组成三队，不区分队伍的编号。不同的组队情况有( )种。

• 答案：B
• 解析： $\frac{C_6^2 \times C_4^2 \times C_2^2}{3!} = 15$ 种。

[53] [2021] 由 $1，1，2，2，3$ 这五个数字组成不同的三位数有（ ）种。

• 答案：A
• 解析： 分类（全不同、两个1、两个2）求和共 18 种。

[54] [2023] 一个班级有10个男生和12个女生...小组中必须至少包含1个女生，那么有多少种可能的组合？（ ）

• 答案：A
• 解析： 总组合数减去全为男生的组合数：$C_{22}^3 - C_{10}^3 = 1540 - 120 = 1420$。

[55] [2024] 某公司有10名员工...现需要从这10名员工中选出4名组成一个工作组，且每个部门至少要有1人。问有多少种选择方式？（ ）

• 答案：B
• 解析： 多部门名额分配组合计算得 126 种。

[56] [2024] 有5个男生和3个女生站成一排，规定3个女生必须相邻，问有多少种不同的排列方式？

• 答案：A
• 解析： 捆绑法：$A_3^3 \times A_6^6 = 6 \times 720 = 4320$。

[57] [2025] 从 5 位男生和 4 位女生中选出 4 人组成一个学习小组...有多少种不同的选举方法？（）

• 答案：C
• 解析： $C_5^1C_4^3 + C_5^2C_4^2 + C_5^3C_4^1 = 20 + 60 + 40 = 120$。

[58] [2025] 一个 ( 8×8 ) 的棋盘...机器人从 ( (1,1) ) 出发...要到达 ( (4,5) )...有多少种不同的路径？（）

• 答案：B
• 解析： 总步数 7 步，其中向下 3 步，组合数 $C_7^3 = 35$。

[59] [2017] 一家四口人，至少两个人生日属于同一月份的概率是（ ）...

• 答案：C
• 解析： 对立事件（四人生日各不相同）概率为 $1 - \frac{A_{12}^4}{12^4} = 1 - \frac{55}{96} = \frac{41}{96}$。

[60] [2019] 100以内最大的素数是（）。

• 答案：B
• 解析： 97 是 100 以内最大的质数。

[61] [2019] 319和377的最大公约数是（）。

• 答案：C
• 解析： 辗转相除法：$\text{gcd}(377, 319) = \text{gcd}(319, 58) = \text{gcd}(58, 29) = 29$。

[62] [2013] 下面是根据欧几里得算法编写的函数，它所计算的是a 和 b 的（ ）。

• 答案：C
• 解析： 欧几里得算法（辗转相除法）专门用于计算两个整数的最大公约数。

[63] [2024] 以下哪个序列对应数组0至7的4位二进制格雷码（Gray code）？

• 答案：D
• 解析： 根据格雷码“相邻两位只有一位二进制数不同”的生成规则可得 D。

---

三、数据结构 - 答案与解析

[1] [2014] 链表不具有的特点是 ( )

• 答案：B
• 解析： 链表采用链式存储结构，节点在内存中不连续，无法像数组那样通过下标随机访问任一元素。

[2] [2015] 链表不具备的特点是 ( )。

• 答案：A
• 解析： 同上，链表不支持随机访问。

[3] [2015] 线性表若采用链表存储结构，要求内存中可用存储单元地址 ( )

• 答案：D
• 解析： 链表通过指针域链接各结点，因此其在物理内存中可以连续，也可以不连续。

[4] [2019] 链表不具有的特点是（）

• 答案：D
• 解析： 链表不支持随机访问任一元素。

[5] [2020] 链表不具有的特点是（）。

• 答案：A
• 解析： 链表不具备随机访问特性。

[6] [2011] 在含有n个元素的双向链表中查询是否存在关键字为k的元素，最快情况下运行的时间复杂度是（ ）。

• 答案：C
• 解析： 在无序链表中查找指定关键字的最坏时间复杂度为 $O(n)$。

[7] [2010] 双向链表中有两个指针域 llink 和 rlink...现要求删除结点 $p$，则下面语句序列中错误的是（ ）。

• 答案：A
• 解析： A 选项中指针赋值顺序错误，会导致链表断链或野指针错误。

[8] [2022] 链表和数组的区别包括（ ）。

• 答案：C
• 解析： 数组在声明时必须指定大小且静态固定，而链表可动态申请和释放、大小可动态调整。

[9] [2022] 以下哪组操作能完成在双向循环链表结点 p 之后插入结点 s 的效果...：（ ）。

• 答案：D
• 解析： 正确的双向链表插入步骤需要先处理新结点的指针，防止原后继指针丢失。

[10] [2023] 假设有一个链表的节点定义如下...如果要使新节点成为链表的第一个节点，下面哪个操作是正确的？（ ）

• 答案：A
• 解析： 先让 newNode->next = head;，再让 head = newNode;。

[11] [2015] 今有一空栈 S，对下列待进栈的数据元素序列 a，b，c，d，e，f 依次进行进栈，进栈，出栈，进栈，进栈，出栈的操作...栈 S 的栈顶元素为

• 答案：B
• 解析： 严格按照栈的进出规则模拟，操作完成后栈顶元素为 c。

[12] [2017] 向一个栈顶指针为 hs 的链式栈中插入一个指针 s 指向的结点时，应执行（ ）。

• 答案：B
• 解析： 链表头部入栈：s->next = hs; hs = s;。

[13] [2017] 对于入栈顺序为 a, b, c, d, e, f, g 的序列，下列（ ）不可能是合法的出栈序列。

• 答案：C
• 解析： C 选项的弹出顺序在栈逻辑上无法通过进出栈顺序实现。

[14] [2018] 下图中所使用的数据结构是（ ）。

• 答案：B
• 解析： 图示体现后进先出（LIFO）特性，为栈。

[15] [2020] 下图中所使用的数据结构是（ )。

• 答案：A
• 解析： 表现形式为栈。

[16] [2013] 下图中所使用的数据结构是（ ）。

• 答案：B
• 解析： 栈。

[17] [2012] 如果一个栈初始时为空...另有元素d已经出栈，则可能的入栈顺序是（ ）。

• 答案：D
• 解析： 模拟验证可知 D 选项合法。

[18] [2010] 前缀表达式+ 3 * 2 + 5 12的值是（ ）。

• 答案：C
• 解析： 从后向前扫描前缀表达式计算，结果为 37。

[19] [2010] 元素R1、R2、R3、R4、R5入栈的顺序为R1...如果第1个出栈的是R3，那么第5个出栈的不可能是（ ）。

• 答案：A
• 解析： R3 先出时 R1、R2 在栈中，R2 在栈顶必须先于 R1 出栈，因此 R1 不可能最后（第5个）出栈。

[20] [2009] 有六个元素FEDCBA 从左至右依次顺序进栈...问下列哪一个不可能是合法的出栈序列？

• 答案：C
• 解析： 模拟进出栈验证，C 选项序列非法。

[21] [2009] 表达式a*(b+c)-d的后缀表达式是：

• 答案：B
• 解析： 转换为后缀表达式为 abc+*d-。

[22] [2008] 设栈S的初始状态为空...出栈的序列为b，d，f，e，c，a，则栈S的容量至少应该是（ ）。

• 答案：C
• 解析： 模拟该出栈序列对应的最大同时在栈内的元素个数为 4。

[23] [2008] 递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（ ）的数据结构。

• 答案：D
• 解析： 函数调用及返回地址管理天然依赖系统栈（Stack）。

[24] [2021] 对于入栈顺序为 a, b, c, d, e 的序列，下列（ ）不是合法的出栈序列。

• 答案：D
• 解析： D 选项中 c、d 先出，导致位于其底下的 a、b 顺序错乱。

[25] [2021] 表达式 a\\*(b+c)\\*d 的后缀表达式为( )，其中*和+是运算符。

• 答案：B
• 解析： 后缀表达式为 abc+*d*。

[26] [2022] 有 6 个元素，按照 6、5、4、3、2、1 的顺序进入栈 S，请问下列哪个出栈序列是非法的 （ ）。

• 答案：C
• 解析： 模拟验证可知 C 选项序列无法通过栈还原。

[27] [2022] 对假设栈 S 和队列 Q 的初始状态为空...栈 S 的容量至少是（ ）个数据。

• 答案：B
• 解析： 分析进出栈交错过程，栈中最多同时存在 3 个元素。

[28] [2022] 对表达式 a+(b-c)\d 的前缀表达式为（ ），其中+、-、是运算符。

• 答案：B
• 解析： 前缀表达式（波兰表达式）为 +a*-bcd。

[29] [2022] 以下对数据结构的表述不恰当的一项为：（ ）。

• 答案：D
• 解析： D 选项“无法用栈实现队列”是错误的，完全可以使用两个栈来实现队列的先进先出功能。

[30] [2023] 后缀表达式“6 2 3 + - 3 8 2 / + * 2 ^ 3 +”对应的中缀表达式是（ ）

• 答案：A
• 解析： 根据后缀表达式还原带括号的中缀表达式为 A。

[31] [2024] 给定一个空栈...若入栈操作的元素依次是1 2 3 4 5 6...下面哪种出栈顺序是不可能的（ ）

• 答案：D
• 解析： D 选项顺序违背了栈的弹出规律。

[32] [2025] 给定一个初始为空的整数栈 ( S ) 和一个空的队列 ( P )...当队列 ( A ) 中的所有数都处理完毕后，队列 ( P ) 的内容是什么？（）

• 答案：A
• 解析： 严格按照奇数入栈、偶数触发栈顶弹出至队列的规则模拟，最终队列 P 为 5, 1, 3。

[33] [2012] （ ）是一种先进先出的线性表。

• 答案：B
• 解析： 队列（Queue）是先进先出（FIFO）的线性表。

[34] [2011] 广度优先搜索时，需要用到的数据结构是（ ）。

• 答案：B
• 解析： 广度优先搜索（BFS）利用队列（Queue）实现逐层扩展。

[35] [2014] 一棵具有 $5$ 层的满二叉树中结点数为 ( )

• 答案：A
• 解析： 满二叉树结点数 $2^5 - 1 = 31$。

[36] [2015] 如果根的高度为 $1$, 具有 $61$ 个结点的完全二叉树的高度为 ( )

• 答案：B
• 解析： 61 个结点的完全二叉树高度为 6（$2^5-1 = 31 < 61 \le 2^6-1 = 63$）。

[37] [2018] 根节点深度为 $0$，一棵深度为 $h$ 的满 $k（k>1）$ 叉树...共有（ ）个结点。

• 答案：A
• 解析： 等比数列求和公式：$\frac{k^{h+1}-1}{k-1}$。

[38] [2019] 一棵二叉树如右图所示...则该数组的最大下标至少为（）。

• 答案：C
• 解析： 完全二叉树最大深度对应的满编号计算可得最大下标为 15。

[39] [2019] 假设一棵二叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF,则其前序遍历序列为（）。

• 答案：B
• 解析： 结合后序与中序递归还原树结构，再求前序遍历得 B。

[40] [2020] 独根树的高度为 1。具有 61 个结点的完全二叉树的高度为（ ）。

• 答案：D
• 解析： 高度为 6。

[41] [2013] 已知一棵二叉树有10 个节点，则其中至多有（ ）个节点有 2 个子节点。

• 答案：A
• 解析： 10 个节点的二叉树最多有 4 个度为 2 的节点（退化为完全二叉树形态或平衡状态推导）。

[42] [2013] 二叉树的（ ）第一个访问的节点是根节点。

• 答案：A
• 解析： 先序遍历（根左右）最先访问根节点。

[43] [2012] 如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是（ ）。

• 答案：C
• 解析： 中序为 BAC，说明 A 是根。若先序为 ACB，则 C 是先序第一个即根，矛盾。

[44] [2011] 如果根结点的深度记为1，则一棵恰有2011个叶结点的二叉树的深度最少是（ ）。

• 答案：C
• 解析： 叶子最多时为完全二叉树，深度最少为 12。

[45] [2010] 如果树根算第1层，那么一棵n层的二叉树最多有（ ）个结点。

• 答案：A
• 解析： $2^n - 1$ 个结点。

[46] [2009] 一个包含n个分支结点（非叶结点）的非空二叉树，它的叶结点数目最多为：

• 答案：D
• 解析： 对于任意二叉树，叶子数 $n_0 = n_2 + 1$，在分支结点全为 2 个孩子的完全二叉树中叶子最多为 $n + 1$。

[47] [2008] 完全二叉树共有2N-1个结点，则它的叶节点数是（ ）。

• 答案：A
• 解析： 完全二叉树结点数为 $2N-1$ 时，其叶子数为 $N$（注：原选项对应公式变形，此处叶节点数为 $N$）。

[48] [2008] 二叉树T，已知其先根遍历是1 2 4 3 5 7 6...则该二叉树的后根遍历是（ ）。

• 答案：B
• 解析： 还原二叉树后得出后根遍历序列为 4 2 7 5 6 3 1。

[49] [2021] 如果一棵二叉树只有根结点...高度为 5 的完全二叉树有 （ ）种不同的形态？

• 答案：A
• 解析： 第 5 层叶子数可以在 $1 \sim 16$ 之间变化，共 16 种形态。

[50] [2022] 一棵有 n 个结点的完全二叉树...若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子 结点的位置分别是（ ）。

• 答案：C
• 解析： 编号 9 的兄弟为 8，右孩子为 $9 \times 2 + 1 = 19$。

[51] [2023] 根节点的高度为1，一根拥有2023个节点的三叉树高度至少为（ ）

• 答案：C
• 解析： 根据三叉树满节点等比求和估算，高度至少为 8。

[52] [2023] 给定一棵二叉树，其前序遍历结果为：ABDECFG，中序遍历结果为：DEBACFG...正确后序遍历结果是什么？（ ）

• 答案：A
• 解析： 还原树结构后得出后序遍历为 EDBGFCA。

[53] [2024] 已知二叉树的前序遍历为［A，B，D，E，C，F，G］，中序遍历为［D，B，E，A，F，C，G］...后序遍历的结果是（ ）

• 答案：A
• 解析： 还原得后序遍历结果为 [D,E,B,F,G,C,A]。

[54] [2025] 用 5 个权值 10，12，15，20，25 构造哈夫曼树，该树的带权路径长度是多少？（）

• 答案：B
• 解析： 逐步合并最小权值，计算 WPL = $30 + 36 + 30 + 40 + 50 = 186$。

[55] [2025] 一棵包含 1000 个结点的完全二叉树，其叶子结点的数量是多少？（）

• 答案：C
• 解析： 总结点数为偶数时，完全二叉树的叶子结点数为 $n / 2 = 500$。

[56] [2011] 现有一段文言文，要通过二进制哈夫曼编码进行压缩...次数分别为700、600、300、200。“也”字的编码长度是（ ）。

• 答案：C
• 解析： 构造哈夫曼树后计算最低频字符的路径长度为 3。

[57] [2021] 在数据压缩编码中的哈夫曼编码方法，在本质上是一种（ ）的策略。

• 答案：B
• 解析： 哈夫曼树构建每次挑选最小权值合并，属于经典的贪心算法策略。

[58] [2022] 假设字母表 {a, b, c, d, e} 频率分别为...字母 d 的编码长度为 （ ）位。

• 答案：B
• 解析： 对应哈夫曼编码长度为 2 位。

[59] [2023] 假设有一组字符{a,b,c,d,e,f}...哪一个选项是分别对应的一组哈夫曼编码？（ ）

• 答案：A
• 解析： 验证各字符频率与编码长短匹配关系，A 选项正确。

[60] [2013] 将（2, 6, 10, 17）分别存储到某个地址区间为0~10 的哈希表中，如果哈希函数h(x) = （ ），将不会产生冲突...

• 答案：D
• 解析： 代入检验 D 选项：$\lfloor \sqrt{2} \rfloor \bmod 11 = 1$，$\lfloor \sqrt{6} \rfloor \bmod 11 = 2$，$\lfloor \sqrt{10} \rfloor \bmod 11 = 3$，$\lfloor \sqrt{17} \rfloor \bmod 11 = 4$，输出各不相同，无冲突。

---

四、算法与复杂度 - 答案与解析

[1] [2014] 设有 100 个数据元素，采用折半搜索时，最大比较次数为 ( )

• 答案：B
• 解析： $\lceil \log_2(100 + 1) \rceil = 7$ 次。

[2] [2015] 设有 100 个数据元素，采用折半搜索时，最大比较次数为 ( )

• 答案：B
• 解析： 同上，最大比较次数为 7。

[3] [2016] 给定含有 n 个不同的数的数组 L...请把 a,b,c三行代码补全到算法中使得算法正确找到 L 的峰顶。

• 答案：A
• 解析： 依据单峰数组二分查找模板，峰顶直接返回，递增往右找，递减往左找，填空顺序为 c, a, b。

[4] [2019] 设有100个已排好序的数据元素，采用折半查找时，最大比较次数为（）

• 答案：A
• 解析： 最大比较次数为 7。

[5] [2009] 有一个由4000个整数构成的顺序表...采用二分查找定位一个元素。则最多需要几次比较就能确定是否存在所查找的元素：

• 答案：B
• 解析： $\lceil \log_2 4000 \rceil = 12$ 次（因为 $2^{11} = 2048 < 4000 \le 2^{12} = 4096$）。

[6] [2008] 对有序数组进行二分查找，成功查找元素19的查找长度（比较次数）是（ ）。

• 答案：B
• 解析： 模拟二分过程：先比中间元素 37，再比左半段中间 13，最后找到 19，共比较 3 次（注：原参考答案计为2或3次，实际按标准二分轨迹为3次，此处依标准索引为B）。

[7] [2024] 假设有序表中有1000个元素，则用二分法查找元素x最多需要比较（）次

• 答案：B
• 解析： $\lceil \log_2 1000 \rceil = 10$ 次（$2^{10} = 1024 > 1000$）。

[8] [2020] 冒泡排序算法的伪代码如下...最少需要比较多少次?（ ）。

• 答案：C
• 解析： 当输入数组本来就是有序的时，第一轮扫描完发现没有发生交换即退出，此时比较次数最少，为 $n-1$ 次。

[9] [2012] 使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少 $1$ 个逆序对，因此序列 $5，4，3，2，1$ ，需要执行（ ）次操作，才能完成冒泡排序。

• 答案：C
• 解析： 完全逆序的 5 个元素初始逆序对数为 $\frac{5 \times 4}{2} = 10$ 个，每次交换减少 1 个逆序对，故需交换 10 次。

[10] [2025] 某同学用冒泡排序对数组 ( {6, 1, 5, 2, 4} ) 进行升序排序，请问需要进行多少次元素交换？（）

• 答案：B
• 解析： 计算该数组中的逆序对总数：$(6,1), (6,5), (6,2), (6,4), (5,2), (5,4)$ 共 6 个逆序对，需交换 6 次。

[11] [2017] 设 A 和 B 是两个长为 n 的有序数组...任何以元素比较作为基本运算的归并算法在最坏情况下至少要做（ ）次比较。

• 答案：D
• 解析： 归并两个长度为 $n$ 的有序数组，最坏情况下需要比较 $2n - 1$ 次。

[12] [2013] （ ）的 平均时间复杂度为 $O(nlogn)$，其中 $n$ 是待排序的元素个数。

• 答案：A
• 解析： 快速排序的平均时间复杂度为 $O(n \log n)$。

[13] [2009] 快速排序，最坏情况下，算法时间复杂度为：

• 答案：D
• 解析： 当每次选取的基准极度不均衡（如已序数组每次选首元）时，快排退化为 $O(n^2)$。

[14] [2009] 排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪种排序算法是不稳定的：

• 答案：D
• 解析： 快速排序、选择排序、希尔排序和堆排序是不稳定排序。

[15] [2022] 以下排序算法的常见实现中，哪个选项的说法是错误的：（ ）。

• 答案：B
• 解析： 简单选择排序是不稳定的排序算法。

[16] [2020] 设A是这个实数的数组，考虑下面的递归算法：请问算法XYZ的输出是什么？（）。

• 答案：B
• 解析： 该递归函数通过前后比较不断返回较小值，最终输出的是数组 $A$ 中的最小值。

[17] [2012] 在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。

• 答案：A
• 解析： 递归过深会无限制消耗系统为函数调用分配的栈内存空间，导致栈溢出（Stack Overflow）。

[18] [2011] （ ）是一种选优搜索法...当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。

• 答案：A
• 解析： 回溯法（Backtracking）是一种系统搜索法，具有“试探与纠错（回退）”的特点。

[19] [2021] 考虑如下递归算法，则调用 solve(7) 得到的返回结果为（ ）。

• 答案：C
• 解析： 逐步展开：solve(7) = 7 * solve(5) = 7 * 5 * solve(3) = 7 * 5 * 3 * solve(2) = 7 * 5 * 3 * 2 = 210。

[20] [2022] 以下对递归方法的描述中，正确：（ ）。

• 答案：B
• 解析： 递归的核心定义就是函数直接或间接调用自身来求解规模更小子问题的编程技术。

[21] [2019] 新学期开学了，小胖想减肥...每周最多通过跑步消耗多少千卡？（）

• 答案：C
• 解析： 设方案一跑 $x$ 天，方案二跑 $y$ 天，满足 $x \le 4, y \le 3, 3x+5y \le 21$，当 $x=2, y=3$ 时消耗热量最大，为 $300 \times 2 + 600 \times 3 = 2400$ 千卡。

[22] [2021] 有四个人要从 A 点坐一条船过河...最短（ ）时间可以让四个人都过河到 B 点。

• 答案：B
• 解析： 经典过河贪心策略：1和2先过(2)，1回(1)，4和8过(8)，2回(2)，最后1和2再过(2)，总时间 $2 + 1 + 8 + 2 + 2 = 15$。

[23] [2023] 以下关于高精度运算的说法错误的是（ ）。

• 答案：C
• 解析： 高精度乘法的时间复杂度与两个参与运算的整数长度之积有关，而不是只与较长者有关。

[24] [2016] 如果开始时计算机处于小写输入状态...屏幕上输出的第 81 个字符是字母 （ ）。

• 答案：C
• 解析： 周期性按键模拟，输入周期为 6 步，$81 \pmod 6 = 3$，对应字母 D。

[25] [2016] 下图表示一个果园灌溉系统...以下设置阀门的方法中 ，可以让果树浇上水的是（ ）。

• 答案：A
• 解析： 打开 B 阀门并关闭 A 阀门（防止水从高处主管流失）可使水流向果树。

[26] [2016] 周末小明和爸爸妈妈三个人一起想动手做三道菜...那么做完三道菜的最短时间需要 （ ）分钟。

• 答案：C
• 解析： 流水线并行优化安排，最短总耗时为 50 分钟。

[27] [2017] 2017年10月1日是星期日，1999年10月1日是（ ）。

• 答案：C
• 解析： 1999年到2017年共经历18年（含5个闰年），总天数合 23 天，模 7 余 2，星期日往前推 2 天为星期五。

[28] [2018] 如果开始时计算机处于小写输入状态...屏幕上输出的第 81 个字符是字母 （ ）

• 答案：A
• 解析： 周期为 8，计算 $81 \pmod 8 = 1$，对应大写字母 A。

[29] [2020] 干支纪年法是中国传统的纪年方法...请问 1949 年的天干地支是（ ）

• 答案：C
• 解析： 1949 除以 10 余 9 对应“己”，除以 12 余 1 对应“丑”，即己丑年。

[30] [2017] 对于给定的序列，我们把 $(i, j)$ 称为逆序对当且仅当 $i < j$ 且 $a_i > a_j$。那么序列 1, 7, 2, 3, 5, 4 的逆序对数为（ ）个。

• 答案：B
• 解析： 逆序对有 (7,2), (7,3), (7,5), (7,4), (5,4) 共 5 对。

[31] [2025] 已知 f[0] = 1，f[1] = 1...那么 f[2025] 的值是多少？

• 答案：D
• 解析： 递推数列模 7 具有周期性，循环节长度为 16，$2025 \pmod{16} = 9$，对应项 $f[9] \equiv 6 \pmod 7$。

---

五、图论 - 答案与解析

[1] [2014] 有向图中每个顶点的度等于该顶点的 ( )

• 答案：C
• 解析： 在图论中，有向图某个顶点的度定义为其入度与出度之和。

[2] [2015] 6 个顶点的连通图的最小生成树，其边数为 ( )

• 答案：B
• 解析： 任意包含 $n$ 个顶点的连通图其生成树的边数恒为 $n - 1$，即 $6 - 1 = 5$ 条边。

[3] [2016] 在一个有向图中所有顶点的入度之和等于出度之和的（）倍

• 答案：B
• 解析： 有向图的每条边都有一个起点（贡献一个出度）和一个终点（贡献一个入度），因此所有顶点的总入度必然等于总出度，倍数为 1。

[4] [2016] 设简单无向图 G 有 16 条边且每个顶点的度数都是 2，则图 G 有（ ）个顶点。

• 答案：D
• 解析： 根据手握定理（欧拉定理推论），度数之和 = $2 \times \text{边数} = 2 \times 16 = 32$。因为每个顶点度数为 2，所以顶点数 = $32 / 2 = 16$ 个。

[5] [2016] Lucia 和她的朋友以及朋友的朋友都在某社交网站上注册了账号...那么她可以向以下朋友（ ）分享该照片。

• 答案：A
• 解析： 根据题意及社交关系图谱进行图的连通可达性排除分析，可选 A。

[6] [2017] 设 $G$ 是有 $n$ 个结点、$m$ 条边（$n ≤ m$）的连通图，必须删去 $G$ 的（ ）条边，才能使得 $G$ 变成一棵树。

• 答案：A
• 解析： 树是无环连通图且有 $n-1$ 条边。现图有 $m$ 条边，需保留 $n-1$ 条边，因此必须删去 $m - (n - 1) = m - n + 1$ 条边。

[7] [2018] 由四个没有区别的点构成的简单无向连通图的个数是（ ）。

• 答案：A
• 解析： 4个顶点的非同构简单无向连通图总共有 6 种。

[8] [2020] 有 10 个顶点的无向图至少应该有（ ）条边才能确保是一个连通图。

• 答案：A
• 解析： 要保证图连通且边数最少，最极端的情况是其中 9 个顶点连成一棵树（需 8 条边），第 10 个顶点只需与其余任一顶点连 1 条边即可，共需 $9$ 条边。

[9] [2013] 在一个无向图中，如果任意两点之间都存在路径相连...若要使它不再是连通图，至少要删去其中的（ ）条边。

• 答案：C
• 解析： 该图为 4 个顶点的完全图（共 6 条边）。若要隔离出一个顶点使其不连通，必须删去与该顶点相连的所有边，即 3 条边。

[10] [2011] 无向完全图是图中每对顶点之间都恰好有一条边的简单图。已知无向完全图G有7个顶点，则它共有（ ）条边。

• 答案：B
• 解析： $n$ 阶无向完全图的边数公式为 $\frac{n(n-1)}{2} = \frac{7 \times 6}{2} = 21$ 条。

[11] [2021] 对于有 n 个顶点、m 条边的无向连通图 (m>n)，需要删掉（ ）条边才能使其成为一棵树。

• 答案：D
• 解析： 同第 6 题，保留 $n-1$ 条边，需删去 $m - n + 1$ 条边。

[12] [2022] 考虑由 $N$ 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在 （ ）个非零元素。

• 答案：B
• 解析： 有向连通图最少边的情况是构成一个有向环或单向长链，至少包含 $N$ 条有向边，对应邻接矩阵中至少有 $N$ 个非零元素。

[13] [2024] 在无向图中，所有顶点的度数之和等于（）

• 答案：B
• 解析： 无向图的每一条边连接两个顶点，因此在计算度数时每条边被统计两次，总度数等于边数的两倍。

[14] [2015] 已知一个无向图 $G=(V，E)$...对该图进行深度优先遍历，得到的顶点序列正确的是( )

• 答案：D
• 解析： 严格按照 DFS 遍历邻接点顺序进行模拟可得 D。

[15] [2013] 以 A0 作为起点，对下面的无向图进行深度优先遍历时，遍历顺序不可能是（ ）。

• 答案：A
• 解析： 根据图的邻接连通关系，A0 无法直接一步到达 A2（中间隔着 A1 或无直连边），因此 A 序列不可能。

[16] [2021] 以 a 为起点，对右边的无向图进行深度优先遍历，则 b、 c、 d、 e 四个点中有可能作 为最后一个遍历到的点的个数为：

• 答案：B
• 解析： 顺着图的拓扑结构与 DFS 穷尽回溯路径分析，只有 b 和 e 两个点可能作为最后一个被访问的叶子/终点。

[17] [2011] 对一个有向图而言，如果每个节点都存在到达其他任何节点的路径...事实上，在删掉边（ ）后，它依然是强连通的。

• 答案：A
• 解析： 结合原图结构分析，删去边 a 之后，其余路径依然能保证任意两点间相互可达。

[18] [2009] 已知n个顶点的有向图，若该图是强连通的...则该图中最少有多少条有向边？

• 答案：A
• 解析： $n$ 个顶点的强连通有向图最少需要 $n$ 条边（即首尾相接构成一个大有向环）。

[19] [2010] 关于拓扑排序，下面说法正确的是（ ）。

• 答案：D
• 解析： 拓扑排序针对有向无环图，其结果序列中的第一个结点入度必定为 0。

[20] [2023] 考虑一个有向无环图...以下哪个选项是这个有向无环图的一个有效的拓扑排序？（ ）

• 答案：B
• 解析： 依据边依赖关系 $(1,2), (1,3), (2,4), (3,4)$，序列 1, 2, 3, 4 符合拓扑前驱约束。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com