2026年全国信息竞赛试题

2026年全国信息竞赛试题

一、选择题1.在二叉树中，若某节点的深度为k，则该层最多包含的节点数为（）[单选题]*A.2^kB.2^(k-1)C.k^2D.2k-1答案：A解析：二叉树的第k层最多有2^(k-1)个节点（根节点为第1层），但题目描述“深度为k”可能指层数为k+1，故需明确约定。通常以根节点深度为0时，第k层最多有2^k个节点。2.以下排序算法中，最坏时间复杂度为O(nlogn)的是（）[单选题]*A.冒泡排序B.快速排序C.插入排序D.希尔排序答案：B解析：快速排序最坏时间复杂度为O(n^2)，但平均为O(nlogn)。题目可能存在歧义，更准确的答案是堆排序或归并排序（严格O(nlogn)）。3.TCP协议通过哪种机制保证可靠传输？（）[多选题]*A.三次握手B.滑动窗口C.超时重传D.数据分片答案：B、C解析：滑动窗口控制流量和顺序，超时重传确保丢失数据重发；三次握手建立连接，不直接涉及传输可靠性。4.若哈希表的负载因子超过默认值，通常采取的操作是（）[单选题]*A.线性探测B.再哈希C.链地址法D.扩容重组答案：D解析：Java的HashMap等实现会在负载因子超阈值时扩容（如容量翻倍），重组哈希桶以减少冲突。5.以下不属于NP完全问题的是（）[单选题]*A.旅行商问题B.背包问题C.最大流问题D.布尔可满足性问题答案：C解析：最大流问题存在多项式时间算法（如Ford-Fulkerson），属于P问题；其余均为NP完全问题。6.IPv6地址长度为多少位？（）[单选题]*A.32B.64C.128D.256答案：C解析：IPv6采用128位地址，是IPv4（32位）的扩展，以解决地址耗尽问题。7.在数据库中，事务的ACID特性不包括（）[单选题]*A.原子性B.一致性C.隔离性D.持久性E.可扩展性答案：E解析：ACID指原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）、持久性（Durability）。8.以下哪种加密算法是非对称加密？（）[单选题]*A.AESB.RSAC.DESD.SHA-256答案：B解析：RSA为非对称加密，AES和DES为对称加密，SHA-256为哈希算法。9.深度优先搜索（DFS）使用的数据结构通常是（）[单选题]*A.队列B.栈C.堆D.优先队列答案：B解析：DFS通过栈实现递归或迭代的后进先出访问顺序，BFS才使用队列。10.以下编程语言中，编译型语言是（）[多选题]*A.PythonB.C++C.JavaD.Go答案：B、D解析：C++和Go直接编译为机器码；Java编译为字节码后解释执行；Python为解释型语言。11.在操作系统中，死锁的必要条件不包括（）[单选题]*A.互斥条件B.请求与保持C.非抢占分配D.循环等待E.资源无限答案：E解析：死锁需互斥、持有并等待、非抢占、循环等待四个条件，资源无限时不会死锁。12.以下网络设备中，工作在OSI模型数据链路层的是（）[单选题]*A.路由器B.交换机C.网关D.集线器答案：B解析：交换机基于MAC地址转发数据，属于数据链路层；路由器工作在网络层。13.红黑树的最长路径不超过最短路径的几倍？（）[单选题]*A.1B.2C.3D.4答案：B解析：红黑树通过平衡约束确保最长路径（红黑交替）不超过最短路径（全黑）的两倍。14.以下哪种设计模式用于创建对象？（）[单选题]*A.观察者模式B.工厂模式C.适配器模式D.装饰器模式答案：B解析：工厂模式封装对象创建逻辑；其余为行为型或结构型模式。15.在SQL中，以下聚合函数忽略NULL值的是（）[多选题]*A.COUNT(*)B.SUM()C.AVG()D.MAX()答案：B、C、D解析：COUNT(*)计数所有行，其余聚合函数默认忽略NULL值。16.若二叉树的中序遍历为DBEAC，后序遍历为DEBCA，其前序遍历为（）[单选题]*A.ABDECB.ABDCEC.ABCDED.ADBEC答案：A解析：根据后序确定根节点A，中序划分左右子树（DBE左，C右），递归推导前序为ABDEC。17.HTTP/2相比HTTP/1.1的改进不包括（）[单选题]*A.多路复用B.头部压缩C.二进制分帧D.状态码优化答案：D解析：HTTP/2通过多路复用、头部压缩和二进制分帧提升性能，状态码语义与HTTP/1.1一致。18.以下算法中，无法解决单源最短路径问题的是（）[单选题]*A.Dijkstra算法B.