2025年信息与计算机科学基础考试试卷及答案

2025年信息与计算机科学基础考试试卷及答案一、单项选择题（每题2分，共30分）1.冯·诺依曼体系结构的核心特征是（）。A.采用二进制表示数据和指令B.存储程序并按地址顺序执行C.运算器与控制器分离D.输入输出设备独立于主机2.若某32位浮点数遵循IEEE754单精度标准，其中符号位1位，阶码8位（偏移量127），尾数23位（隐含最高位1），则数值-12.5的二进制表示中，阶码的十六进制形式为（）。A.41HB.C1HC.42HD.C2H3.以下关于二叉树的描述中，正确的是（）。A.完全二叉树的叶子节点只能出现在最后两层B.平衡二叉树的左右子树高度差不超过2C.线索二叉树的线索指针仅用于遍历D.哈夫曼树中权值最小的节点一定是叶子节点4.某进程在运行中需要访问内存地址0x3A5B，若页大小为4KB（12位页内偏移），则页号为（）。A.0x3AB.0x3A5C.0x3A5B>>12D.0x3A5B&0xFFF5.以下协议中，工作在OSI参考模型传输层的是（）。A.ICMPB.UDPC.ARPD.DNS6.已知某排序算法的时间复杂度为O(nlogn)，空间复杂度为O(n)，且是稳定排序，则该算法最可能是（）。A.快速排序B.堆排序C.归并排序D.希尔排序7.若某哈希表的负载因子为0.75，采用链地址法处理冲突，当插入新元素时，以下说法正确的是（）。A.必须扩容哈希表B.冲突概率与负载因子正相关C.所有链表的长度均不超过1D.查找成功的平均长度与负载因子无关8.以下关于操作系统进程的描述中，错误的是（）。A.进程控制块（PCB）是进程存在的唯一标志B.线程的切换开销通常小于进程切换C.临界资源的访问需要通过信号量实现互斥D.死锁的四个必要条件中，“循环等待”可以通过银行家算法预防9.在IPv6协议中，单播地址的长度为（）。A.32位B.64位C.128位D.256位10.若用递归方式计算斐波那契数列F(n)=F(n-1)+F(n-2)（F(0)=0,F(1)=1），则计算F(5)时需要调用递归函数的次数为（）。A.5次B.9次C.15次D.21次11.以下关于数据库事务ACID特性的描述中，“隔离性”指的是（）。A.事务执行结果与串行执行结果一致B.事务一旦提交，其结果不可撤销C.事务中的操作要么全做，要么全不做D.事务处理过程中数据处于一致状态12.某计算机的主存地址空间为4GB，按字节编址，若采用32位虚拟地址，页表项大小为4字节，页大小为4KB，则二级页表的页目录项数为（）。A.1024B.2048C.4096D.819213.以下关于TCP三次握手的描述中，正确的是（）。A.第一次握手客户端发送SYN=1，ACK=1B.第二次握手服务器发送SYN=1，ACK=客户端seq+1C.第三次握手客户端发送SYN=0，ACK=服务器seqD.三次握手完成后，客户端和服务器的序列号均从0开始14.若对序列{5,3,8,4,1,7,2,6}进行快速排序（以第一个元素为基准），第一次划分后的序列为（）。A.{2,3,1,4,5,7,8,6}B.{3,1,4,2,5,8,7,6}C.{1,3,2,4,5,7,8,6}D.{4,3,2,1,5,7,8,6}15.以下关于人工智能基础概念的描述中，错误的是（）。A.监督学习需要标注的训练数据B.卷积神经网络（CNN）适合处理图像数据C.强化学习的核心是奖励机制D.决策树模型的可解释性低于神经网络二、填空题（每空2分，共20分）1.计算机中，补码表示的8位有符号整数范围是______。2.深度为5的满二叉树（根节点深度为1），其叶子节点数为______。3.操作系统中，______调度算法能够保证每个进程的等待时间不会无限增长（饥饿问题）。4.在TCP协议中，若接收方窗口大小为64KB（65536字节），MSS（最大段长度）为1460字节，则接收窗口可容纳的最大报文段数为______（取整）。5.若某二叉树的前序遍历序列为ABDECFG，中序遍历序列为DBEAFCG，则后序遍历序列为______。6.数据库的关系模型中，候选键的最小子集称为______。7.某程序访问数组元素的局部性主要表现为______局部性（时间/空间）。8.在RSA加密算法中，已知公钥(e,n)=(7,33)，私钥(d,n)=(d,33)，则d的值为______（提示：φ(33)=20）。9.若一个任务的执行需要依次访问CPU、I/O设备、CPU，其执行时间分别为10ms、20ms、10ms，则单道程序系统中总耗时为______ms；多道程序系统（假设无切换开销）中总耗时为______ms（假设两个相同任务并发执行）。三、简答题（每题8分，共40分）1.简述虚拟内存的作用及其实现的关键技术。2.比较快速排序与归并排序的异同点（至少列出4点）。3.说明TCP协议中“流量控制”与“拥塞控制”的区别与联系。4.给定一个无序整数数组，设计一个时间复杂度为O(n)的算法找出其中出现次数超过n/2的元素（摩尔投票法），并简述其原理。5.分析冯·诺依曼结构与哈佛结构的主要区别，并说明各自的适用场景。四、综合题（每题15分，共30分）1.设计一个基于哈希表的学生信息管理系统，要求支持以下操作：插入学生（学号唯一）、删除学生（根据学号）、查询学生（根据学号）。（1）说明哈希表的构造方式（哈希函数、冲突处理方法）；（2）分析各操作的时间复杂度（平均情况与最坏情况）；（3）给出插入操作的伪代码。2.某网络拓扑如下：主机A（IP：192.168.1.2，子网掩码255.255.255.0）→路由器R1（接口1：192.168.1.1，接口2：10.0.0.1）→路由器R2（接口1：10.0.0.2，接口2：172.16.0.1）→主机B（IP：172.16.0.100，子网掩码255.255.0.0）。（1）判断主机A与主机B是否属于同一网络，说明理由；（2）当主机A向主机B发送数据包时，写出数据包在各节点的源IP、目的IP、源MAC、目的MAC的变化过程（假设ARP缓存已填充）；（3）若R1的接口2发生故障，简述R1的路由表更新机制（基于RIP协议）。答案一、单项选择题1.B2.A3.D4.C5.B6.C7.B8.D9.C10.B11.A12.A13.B14.A15.D二、填空题1.-128~+1272.163.轮转（时间片轮转）4.45（65536/1460≈44.89，取整45）5.DEBFGCA6.主码（主键）7.空间8.3（因ed≡1modφ(n)，即7d≡1mod20，解得d=3）9.40；50（第一个任务：10+20+10=40ms；第二个任务在第一个任务执行I/O时开始执行CPU，总耗时：10（任务1CPU）+20（任务1I/O并行任务2CPU）+10（任务1CPU并行任务2I/O）+10（任务2CPU）=50ms）三、简答题1.虚拟内存的作用：将物理内存与外存结合，为进程提供比物理内存更大的地址空间，解决内存容量限制问题；实现进程间内存隔离，提高系统安全性。关键技术：分页（将虚拟地址划分为页，物理内存划分为页框）、请求调页（仅在需要时加载页面到内存）、页面置换（当内存不足时替换不常用页面，如LRU算法）。2.相同点：均为分治算法，时间复杂度均为O(nlogn)（平均情况）；均需要递归或迭代实现。不同点：快速排序是原地排序（空间O(logn)），归并排序需要额外空间O(n)；快速排序不稳定，归并排序稳定；快速排序的最坏时间复杂度为O(n²)（如有序序列），归并排序最坏仍为O(nlogn)；快速排序的性能依赖于基准选择，归并排序性能稳定但需要更多内存。3.区别：流量控制针对发送方与接收方的速率匹配（通过接收窗口通知），防止接收方缓冲区溢出；拥塞控制针对网络整体负载，防止网络因过载导致丢包（通过拥塞窗口调整）。联系：均通过调整发送方的发送速率实现；拥塞控制的结果可能影响接收窗口的可用空间，流量控制的限制可能触发拥塞控制机制。4.算法步骤：初始化候选元素为第一个元素，计数器为1；遍历数组，若当前元素等于候选元素，计数器+1，否则-1；若计数器为0，更新候选元素为当前元素，计数器重置为1。遍历结束后，候选元素即为可能的主元素（需再次验证是否超过n/2）。原理：主元素出现次数超过半数，与其他元素两两抵消后仍剩余。5.冯·诺依曼结构：程序与数据共享同一存储空间和总线，结构简单，成本低；适用于通用计算机（如PC）。哈佛结构：程序存储器与数据存储器分离，独立总线，可并行取指令和数据；适用于实时性要求高的嵌入式系统（如DSP、单片机）。四、综合题1.（1）构造方式：哈希函数采用学号取模（如学号为整数，哈希表大小为质数m，h(key)=key%m）；冲突处理用链地址法（每个槽位维护一个链表）。（2）时间复杂度：平均情况（负载因子α较低）下，插入、删除、查询均为O(1)；最坏情况（所有元素冲突到同一链表）为O(n)。（3）插入伪代码：functioninsert(student):key=student.idindex=hash(key)fornodeinhash_table[index]:ifnode.id==key:return学号已存在createnewnodewithstudentinfoaddnodetohash_table[index]的头部2.（1）不属于同一网络。主机A的网络地址：192.168.1.0（192.168.1.2&255.255.255.0）；主机B的网络地址：172.16.0.0（172.16.0.100&255.255.0.0），二者不同。（2）变化过程：主机A发送：源IP=192.168.1.2，目的IP=172.16.0.100；源MAC=A的MAC，目的MAC=R1接口1的MAC。R1接收后转发：源IP=10.0.0.1（R