2026年信息学习题及答案

2026年信息学习题及答案一、单项选择题（每题2分，共20分）1.已知某二叉树的中序遍历序列为DBAECF，后序遍历序列为DBEFCA，则该二叉树的根节点是（）。A.AB.BC.CD.D2.下列排序算法中，平均时间复杂度为O(nlogn)且不稳定的是（）。A.冒泡排序B.归并排序C.快速排序D.插入排序3.操作系统中，当一个进程等待的I/O操作完成后，该进程的状态会从（）。A.就绪态转为执行态B.阻塞态转为就绪态C.执行态转为阻塞态D.阻塞态转为执行态4.在TCP/IP协议栈中，HTTP协议属于（）。A.网络接口层B.网际层C.传输层D.应用层5.若一个栈的输入序列是1,2,3,4,5，不可能的输出序列是（）。A.5,4,3,2,1B.3,4,1,5,2C.2,3,4,5,1D.1,2,3,4,56.对于长度为n的无序数组，使用冒泡排序进行升序排列，最好情况下的比较次数是（）。A.n-1B.n(n-1)/2C.log2nD.n7.关系数据库中，满足第二范式（2NF）的关系模式需消除（）。A.非主属性对候选键的部分函数依赖B.非主属性对候选键的传递函数依赖C.主属性对候选键的部分函数依赖D.主属性对候选键的传递函数依赖8.编译过程中，词法分析的主要任务是（）。A.分析语法结构是否正确B.将源程序转换为目标代码C.识别并输出单词符号D.优化中间代码9.以下加密算法中，属于非对称加密的是（）。A.AESB.DESC.RSAD.SHA-25610.若一个有向图的拓扑排序序列唯一，则该图（）。A.一定不存在环B.一定是完全图C.所有顶点入度均为1D.边数等于顶点数-1二、填空题（每空2分，共20分）11.Dijkstra算法适用于求解________（无负权边/有负权边）的单源最短路径问题。12.关系模型的三类完整性约束是实体完整性、参照完整性和________。13.编译过程中，词法分析阶段的输出是________。14.AES加密算法的分组长度为________位。15.进程的三种基本状态是就绪态、执行态和________。16.快速排序的平均时间复杂度为________。17.TCP协议通过________、滑动窗口和校验和机制实现可靠数据传输。18.具有n个节点的完全二叉树的高度为________（结果用对数表示）。19.哈希表的负载因子定义为________与桶的数量之比。20.死锁产生的四个必要条件是互斥条件、请求与保持条件、不可抢占条件和________。三、简答题（每题8分，共40分）21.比较归并排序与快速排序的异同点（从稳定性、空间复杂度、最坏时间复杂度、适用场景四方面分析）。22.简述虚拟内存的作用及其实现原理。23.描述TCP三次握手的具体过程，并说明其目的。24.哈希冲突是如何产生的？列举两种解决哈希冲突的方法，并说明其核心思想。25.数据库索引的作用是什么？简述聚集索引与非聚集索引的区别。四、编程题（每题10分，共20分）26.动态规划算法常用于解决最优化问题。请设计一个动态规划算法，计算两个字符串X和Y的最长公共子序列（LCS）的长度，并给出状态定义、转移方程及伪代码实现。27.给定一个带权有向图（边权均为非负数），使用Dijkstra算法求从指定起点到所有其他顶点的最短路径。要求：（1）给出图的存储方式（如邻接表）；（2）描述算法的核心步骤；（3）写出伪代码（或Python代码）。答案一、单项选择题1.A后序遍历的最后一个节点是根节点，即A。2.C快速排序平均O(nlogn)且不稳定；归并排序稳定，冒泡和插入排序平均O(n²)。3.BI/O完成后，进程从阻塞态转为就绪态，等待CPU调度。4.DHTTP是应用层协议，基于TCP传输。5.B输出序列3,4,1,5,2中，1在4之后弹出，但此时栈中1必须在2之前入栈，无法在4弹出后直接弹出1（此时栈顶应为2）。6.A最好情况是数组已有序，只需n-1次比较（每趟仅比较一次）。7.A2NF要求消除非主属性对候选键的部分函数依赖。8.C词法分析识别单词（如标识符、关键字）并输出。9.CRSA是非对称加密（公钥加密，私钥解密），AES、DES是对称加密，SHA-256是哈希算法。10.A拓扑排序存在说明无环，唯一不代表完全图或边数特定。二、填空题11.无负权边12.用户定义完整性13.单词符号14.12815.阻塞态16.O(nlogn)17.确认重传18.⎣log₂n⎦+119.哈希表中元素数量20.循环等待条件三、简答题21.异同点：稳定性：归并排序稳定（相等元素顺序不变），快速排序不稳定（分区可能打乱顺序）。空间复杂度：归并排序需要O(n)辅助空间；快速排序平均O(logn)（递归栈空间），最坏O(n)。最坏时间复杂度：归并排序为O(nlogn)（与输入无关）；快速排序为O(n²)（如已序数组）。适用场景：归并排序适合外排序（数据量大）；快速排序适合内存排序（平均效率高）。22.虚拟内存作用：扩展物理内存，允许程序使用比物理内存更大的地址空间；实现进程地址隔离，提高多道程序度。实现原理：基于局部性原理，仅将部分常用页面装入内存，其余存于磁盘；通过页表记录虚拟页与物理页的映射，缺页时触发中断，将目标页调入内存（可能置换淘汰页）。23.三次握手过程：（1）客户端发送SYN=1，seq=x（初始序列号），请求建立连接；（2）服务器回复SYN=1，ACK=1，seq=y，ack=x+1（确认客户端请求）；（3）客户端发送ACK=1，seq=x+1，ack=y+1（确认服务器响应）。目的：同步双方初始序列号，防止失效的连接请求干扰新连接，确保双方通信能力正常。24.哈希冲突产生：不同键值通过哈希函数计算得到相同哈希地址。解决方法：①开放定址法：冲突时按某种策略（如线性探测：h(k)+i，i=1,2,…）寻找下一个空闲桶；核心是在哈希表内部解决冲突。②链地址法：每个桶存储一个链表，冲突元素加入链表；核心是通过链表存储冲突元素，空间动态扩展。25.索引作用：加速数据查询（减少全表扫描），维护数据唯一性（如主键索引）。区别：聚集索引决定数据在磁盘上的物理存储顺序（一个表仅一个）；非聚集索引不影响物理顺序（可多个），需回表查询获取完整数据。四、编程题26.动态规划求解LCS长度：状态定义：dp[i][j]表示X前i个字符（X[0..i-1]）和Y前j个字符（Y[0..j-1]）的LCS长度。转移方程：若X[i-1]==Y[j-1]，则dp[i][j]=dp[i-1][j-1]+1；否则，dp[i][j]=max(dp[i-1][j],dp[i][j-1])。伪代码：functionLCS_length(X,Y):m=len(X);n=len(Y)创建(m+1)×(n+1)的二维数组dpforifrom0tom:forjfrom0ton:ifi==0orj==0:dp[i][j]=0elifX[i-1]==Y[j-1]:dp[i][j]=dp[i-1][j-1]+1else:dp[i][j]=max(dp[i-1][j],dp[i][j-1])returndp[m][n]27.Dijkstra算法实现：（1）图的存储：邻接表（字典或列表，每个顶点对应一个列表，存储相邻顶点及边权）。（2）核心步骤：①初始化距离数组dist（起点距离为0，其他为无穷大），优先队列（按距离排序）。②每次从队列中取出距离最小的顶点u，遍历其邻接顶点v。③若通过u到v的路径更短（dist[v]>dist[u]+边权），则更新dist[v]并将v加入队列。④重复直到队列为空。（3）Python伪代码：importheapqdefdijkstra(graph,start):n=len(graph)dist=[float('inf')]ndist=[float('inf')]ndist[start]=0heap=[(0,start)]visited=[False]nvisited=[False]nwhileheap:current_dist,u=heapq.heappop(heap)ifvisited[u]:continuevisited[u]