中国科技大学笔试真题2025年完整版

中国科技大学笔试真题2025年完整版

一、单项选择题（总共10题，每题2分）1.关于快速排序的时间复杂度，正确的描述是？A.最坏情况O(n²)，平均O(nlogn)B.最坏情况O(nlogn)，平均O(n²)C.最坏和平均都是O(nlogn)D.最坏和平均都是O(n²)2.以下哪个协议属于应用层？A.TCPB.IPC.HTTPD.ARP3.数据库中，消除了非主属性对候选键的部分依赖的是？A.1NFB.2NFC.3NFD.BCNF4.操作系统中，进程的状态不包括？A.运行态B.就绪态C.阻塞态D.挂起态5.以下哪种数据结构适合实现优先队列？A.栈B.队列C.二叉堆D.哈希表6.算法的时间复杂度主要衡量的是？A.算法执行的具体时间B.算法中基本操作的执行次数随输入规模增长的趋势C.算法占用的内存空间D.算法的代码长度7.TCP建立连接时采用的握手次数是？A.一次B.两次C.三次D.四次8.以下排序算法中，稳定的是？A.快速排序B.堆排序C.归并排序D.希尔排序9.操作系统中，文件系统的主要目的是？A.管理内存B.管理外部存储设备上的数据C.管理进程D.提供用户接口10.在二叉树中，若某节点有左子树，则左子树中所有节点的值都小于该节点的值，这样的二叉树是？A.满二叉树B.完全二叉树C.二叉搜索树D.平衡二叉树二、填空题（总共10题，每题2分）1.操作系统中，进程调度的主要任务是从______队列中选择一个进程分配CPU。2.TCP/IP协议栈的传输层主要有TCP和______两种协议。3.数据库的完整性约束包括实体完整性、参照完整性和______完整性。4.数据结构中，栈的基本操作包括入栈和______。5.算法的时间复杂度通常用______符号来表示。6.计算机网络中，______层负责将网络地址转换为物理地址（如MAC地址）。7.操作系统中，虚拟内存的实现主要依赖于______技术。8.排序算法中，______排序的时间复杂度在最好情况下为O(n)。9.数据库中，______索引可以加速对表中记录的查找，但会增加插入、删除的开销。10.数据结构中，图的遍历方法主要有深度优先搜索和______。三、判断题（总共10题，每题2分）1.快速排序是一种稳定的排序算法。（）2.TCP协议提供无连接的不可靠服务。（）3.数据库的第三范式（3NF）要求消除非主属性对候选键的传递依赖。（）4.进程是操作系统进行资源分配的基本单位，线程是CPU调度的基本单位。（）5.哈希表的查找时间复杂度一定是O(1)。（）6.计算机网络的OSI模型中，传输层负责端到端的可靠通信。（）7.二叉树的前序遍历顺序是根-左-右，后序遍历是左-右-根。（）8.操作系统的临界资源是指一次仅允许一个进程访问的资源。（）9.数据库事务的原子性是指事务一旦提交，其对数据库的修改是永久的。（）10.算法的空间复杂度是指算法执行过程中临时占用的存储空间大小。（）四、简答题（总共4题，每题5分）1.简述进程与线程的主要区别。2.说明TCP三次握手的过程。3.什么是二叉搜索树（BST）？简述其主要性质。4.解释数据库事务的ACID特性。五、讨论题（总共4题，每题5分）1.讨论快速排序与归并排序的优缺点及适用场景。2.分析TCP与UDP的区别及各自的应用场景。3.讨论数据库索引的作用及设计时需考虑的因素。4.分析操作系统中虚拟内存的实现机制及意义。答案一、单项选择题1.A2.C3.B4.D5.C6.B7.C8.C9.B10.C二、填空题1.就绪2.UDP3.用户定义4.出栈（或弹栈）5.大O（或O）6.网络接口（或数据链路）7.分页（或请求分页）8.冒泡（或插入）9.辅助（或非聚集）10.广度优先搜索（或BFS）三、判断题1.×2.×3.√4.√5.×6.√7.√8.√9.×10.√四、简答题1.进程是资源分配的基本单位，拥有独立内存和资源；线程是CPU调度的基本单位，共享进程资源。进程间通信复杂（需IPC），线程间通信简单（共享内存）；线程创建和切换开销小于进程。2.第一次握手：客户端发送SYN包请求连接；第二次握手：服务器返回SYN+ACK包确认；第三次握手：客户端发送ACK包完成连接。通过三次握手确认双方通信能力，避免过时连接请求。3.二叉搜索树是满足左子树所有节点值小于根、右子树所有节点值大于根的二叉树。性质：左子树和右子树也是二叉搜索树；支持高效查找、插入、删除，平均时间复杂度O(logn)。4.ACID特性：原子性（事务不可分割，全做或全不做）、一致性（执行前后状态一致）、隔离性（并发事务互不干扰）、持久性（提交后修改永久保存）。五、讨论题1.快速排序平均O(nlogn)，空间O(logn)，但最坏O(n²)，不稳定，适合内存排序；归并排序稳定，时间O(nlogn)，空间O(n)，适合外排序或需要稳定性的场景（如对象排序）。2.TCP面向连接、可靠、开销大，用于HTTP等；UDP无连接、不可靠、开销小，用于视频流、游戏通信等实时场景。TCP保证顺序，UDP可能乱序。3.索引加速查询（如WHERE、JOIN），设计需考虑：查询频率（高频字段建索引）、字段区分度、更新开销（