2026年湖南省计算机考研408专业基础习题

2026年湖南省计算机考研408专业基础习题考核对象：报考计算机科学与技术专业硕士研究生（408考试科目）的考生题型分值分布：-单项选择题（10题，每题2分，共20分）-填空题（10题，每题2分，共20分）-判断题（10题，每题2分，共20分）-简答题（8题，每题2分，共16分）-应用题（8题，每题4分，共24分）一、单项选择题（每题2分，共20分）1.在数据结构中，线性表、栈和队列都是线性结构，下列关于它们的描述中，错误的是（）。A.线性表可以是顺序存储也可以是链式存储B.栈是一种先进后出（LIFO）的数据结构C.队列是一种先进先出（FIFO）的数据结构D.线性表和栈都可以通过数组实现随机访问2.假设有n个元素需要插入到一个有序链表中，如果采用头插法，则插入操作的时间复杂度为（）。A.O(1)B.O(n)C.O(n²)D.O(logn)3.在快速排序算法中，如果每次划分都能将序列均匀分成两部分，那么其时间复杂度为（）。A.O(n)B.O(nlogn)C.O(n²)D.O(n³)4.下列关于二叉树的叙述中，正确的是（）。A.完全二叉树一定是满二叉树B.满二叉树一定是完全二叉树C.完全二叉树的叶子节点只能出现在最下面两层D.二叉搜索树的任何节点都没有重复值5.在图的遍历算法中，深度优先搜索（DFS）和广度优先搜索（BFS）的主要区别在于（）。A.DFS使用栈而BFS使用队列B.DFS可以处理带权图而BFS不能C.DFS的时间复杂度总是低于BFSD.BFS可以找到最短路径而DFS不能6.哈希表解决冲突的两种主要方法是链地址法和（）。A.线性探测法B.二叉搜索树法C.跳表法D.哈希函数法7.在树形结构中，根节点的特点是（）。A.没有父节点B.有多个子节点C.是叶节点D.有且仅有一个父节点8.下列关于数据库事务的叙述中，错误的是（）。A.事务的ACID特性包括原子性、一致性、隔离性和持久性B.并发事务可能导致脏读、不可重复读和幻读C.隔离级别越高，事务的并发性能越好D.事务日志用于保证事务的持久性9.在关系数据库中，主键的作用是（）。A.确保表中所有记录的唯一性B.约束表中的外键值C.提高查询效率D.允许表中存在重复记录10.下列关于操作系统进程管理的叙述中，正确的是（）。A.进程和程序是同一个概念B.进程切换一定会导致上下文切换C.进程的状态只有运行和等待两种D.进程的优先级越高，执行速度越快二、填空题（每空2分，共20分）1.在二叉树的遍历中，前序遍历的顺序是根节点→左子树→右子树。2.快速排序算法的平均时间复杂度是O(nlogn)，最坏情况下的时间复杂度是O(n²)。3.在图的存储结构中，邻接矩阵适用于表示稠密图，而邻接表适用于表示稀疏图。4.哈希表的平均查找长度取决于哈希函数的冲突解决方法和负载因子。5.数据库的规范化是为了减少数据冗余和提高数据一致性。6.操作系统的内存管理包括连续分配和非连续分配两种方式。7.在关系代数中，选择操作用符号σ表示，投影操作用符号π表示。8.死锁是指多个进程因争夺资源而陷入相互等待的状态。9.线程是操作系统能够进行运算调度的最小单位，比进程更轻量级。10.TCP协议是一种面向连接的、可靠的传输层协议，而UDP协议是无连接的、不可靠的传输层协议。三、判断题（每题2分，共20分）1.在链式栈中，栈顶指针始终指向栈顶元素。（√）2.堆排序是一种稳定的排序算法。（×）3.在完全二叉树中，如果某个节点的编号为i，则其左子节点的编号为2i，右子节点的编号为2i+1。（√）4.图的拓扑排序适用于有向无环图（DAG）。（√）5.哈希表的冲突解决方法只有链地址法一种。（×）6.数据库的主键可以重复。（×）7.操作系统的进程调度算法可以是非抢占式或抢占式。（√）8.并发控制的主要目的是防止数据不一致。（√）9.TCP协议可以保证数据包的顺序性，而UDP协议不能。（√）10.死锁和饥饿是同一个概念。（×）四、简答题（每题2分，共16分）1.简述栈和队列的主要区别。答：栈是先进后出（LIFO）的数据结构，而队列是先进先出（FIFO）的数据结构。栈的操作受限，只能在栈顶进行插入和删除，而队列可以在队头和队尾进行插入和删除。2.解释二叉搜索树的性质。答：二叉搜索树的性质包括：左子树上所有节点的值均小于根节点的值；右子树上所有节点的值均大于根节点的值；左、右子树也都是二叉搜索树。3.描述数据库规范化的第三范式（3NF）要求。答：第三范式要求关系数据库中不存在非主属性对非传递依赖的依赖关系，即所有非主属性都必须直接依赖于主键。4.解释操作系统的内存分配方式。答：内存分配方式包括连续分配（如固定分区、动态分区）和非连续分配（如分页、分段）。连续分配要求进程的地址空间在内存中是连续的，而非连续分配将地址空间分成多个片段，可以分散存储。5.简述事务的隔离性含义。答：隔离性是指一个事务的执行不能被其他事务干扰，即一个事务内部的操作及使用的数据对并发的其他事务是隔离的，并发执行的事务之间不会相互影响。6.解释哈希表的负载因子概念。答：负载因子是指哈希表中已存储的元素数量与哈希表总容量的比值。负载因子越大，冲突概率越高，反之则越低。7.描述进程和线程的区别。答：进程是资源分配的基本单位，而线程是CPU调度的基本单位。进程拥有独立的地址空间，线程共享进程的地址空间。线程的创建和销毁比进程更轻量级。8.解释TCP协议的三次握手过程。答：三次握手过程包括：①客户端发送SYN报文请求连接；②服务器回复SYN+ACK报文确认连接；③客户端发送ACK报文完成连接。五、应用题（每题4分，共24分）1.案例背景：某公司需要设计一个图书管理系统，其中图书信息包括书号、书名、作者、出版社等。假设图书表（Books）的主键是书号（BookID），且存在一个读者表（Readers），记录读者信息。现要求实现以下功能：（1）插入一本新书；（2）查询某位读者的借阅记录；（3）删除一本已停用的图书。请用SQL语句实现上述功能。参考答案：（1）INSERTINTOBooks(BookID,Title,Author,Publisher)VALUES('B001','数据结构','王明','计算机出版社');（2）SELECTFROMBorrowRecordsWHEREReaderID='R001';（3）DELETEFROMBooksWHEREBookID='B001';2.案例背景：假设有一个无向图G，顶点集V={A,B,C,D,E}，边集E={AB,AC,AD,BC,BD,CE}。请分别用邻接矩阵和邻接表表示该图。参考答案：（1）邻接矩阵：```ABCDEA01110B10110C11001D11001E00110```（2）邻接表：```A:B,C,DB:A,C,DC:A,B,ED:A,B,EE:C,D```3.案例背景：假设有一个栈S，初始状态为[1,2,3,4,5]。请用栈操作模拟将栈中的元素逆序排列。参考答案：（1）将栈中的元素依次出栈，得到逆序排列的队列：[5,4,3,2,1]。（2）将队列中的元素依次入栈，得到逆序排列的栈：[5,4,3,2,1]。4.案例背景：假设有一个数组A=[12,34,5,2,45]，请用快速排序算法对数组进行排序。参考答案：（1）选择基准值（如A[0]=12），划分后数组变为[5,2,12,34,45]。（2）对左子数组[5,2]和右子数组[34,45]递归排序，最终得到[2,5,12,34,45]。5.案例背景：假设有一个数据库表Students（StudentID,Name,Major），其中主键是StudentID。现要求查询所有计算机科学专业的学生，并按姓名降序排列。参考答案：SELECTFROMStudentsWHEREMajor='计算机科学'ORDERBYNameDESC;6.案例背景：假设有一个进程P正在执行，其状态转换图如下：```新建→就绪→运行→等待→运行→终止```请解释该进程的状态转换过程。参考答案：（1）进程从“新建”状态变为“就绪”状态，等待CPU分配；（2）进程从“就绪”状态变为“运行”状态，开始执行；（3）进程从“运行”状态变为“等待”状态，因资源不足而暂停；（4）进程从“等待”状态变为“运行”状态，资源满足后继续执行；（5）进程从“运行”状态变为“终止”状态，执行完毕。---标准答案及解析一、单项选择题1.D解析：线性表可以通过数组实现随机访问，但栈和队列只能通过顺序访问。2.B解析：头插法每次插入都需要遍历链表到头部，时间复杂度为O(n)。3.B解析：快速排序在平均情况下时间复杂度为O(nlogn)，但最坏情况下为O(n²)。4.D解析：二叉搜索树的任何节点都没有重复值，这是其定义性质。5.A解析：DFS使用栈，BFS使用队列，这是两种算法的核心区别。6.A解析：哈希表解决冲突的两种主要方法是链地址法和线性探测法。7.A解析：根节点没有父节点，是树的起始节点。8.C解析：隔离级别越高，事务的并发性能越低，因为需要更多锁机制。9.A解析：主键用于确保表中所有记录的唯一性。10.B解析：进程切换一定会导致上下文切换，但上下文切换不一定是进程切换。二、填空题1.根节点→左子树→右子树2.O(nlogn),O(n²)3.稠密图,稀疏图4.哈希函数的冲突解决方法,负载因子5.减少数据冗余,提高数据一致性6.连续分配,非连续分配7.σ,π8.死锁9.线程10.TCP协议,UDP协议三、判断题1.√解析：链式栈的栈顶指针始终指向栈顶元素。2.×解析：堆排序是不稳定的排序算法。3.√解析：完全二叉树的节点编号满足左子节点为2i，右子节点为2i+1。4.√解析：拓扑排序适用于有向无环图（DAG）。5.×解析：哈希表的冲突解决方法包括链地址法和线性探测法等。6.×解析：主键的唯一性约束不允许重复值。7.√解析：进程调度算法可以是非抢占式（如时间片轮转）或抢占式（如优先级调度）。8.√解析：并发控制的主要目的是防止数据不一致。9.√解析：TCP协议保证数据包的顺序性，而UDP协议不保证。10.×解析：死锁是指多个进程因资源争夺而陷入相互等待的状态，而饥饿是指进程因资源分配不当而无法获得所需资源。四、简答题1.栈是先进后出（LIFO）的数据结构，只能在栈顶进行插入和删除操作；而队列是先进先出（FIFO）的数据结构，可以在队头和队尾进行插入和删除操作。2.二叉搜索树的性质包括：左子树上所有节点的值均小于根节点的值；右子树上所有节点的值均大于根节点的值；左、右子树也都是二叉搜索树。3.第三范式（3NF）要求关系数据库中不存在非主属性对非传递依赖的依赖关系，即所有非主属性都必须直接依赖于主键。4.内存分配方式包括连续分配（如固定分区、动态分区）和非连续分配（如分页、分段）。连续分配要求进程的地址空间在内存中是连续的，而非连续分配将地址空间分成多个片段，可以分散存储。5.隔离性是指一个事务的执行不能被其他事务干扰，即一个事务内部的操作及使用的数据对并发的其他事务是隔离的，并发执行的事务之间不会相互影响。6.负载因子是指哈希表中已存储的元素数量与哈希表总容量的比值。负载因子越大，冲突概率越高，反之则越低。7.进程是资源分配的基本单位，拥有独立的地址空间；而线程是CPU调度的基本单位，共享进程的地址空间，创建和销毁更轻量级。8.TCP协议的三次握手过程包括：①客户端发送SYN报文请求连接；②服务器回复SYN+ACK报文确认连接；③客户端发送ACK报文完成连接。五、应用题1.参考答案：（1）INSERTINTOBooks(BookID,Title,Author,Publisher)VALUES('B001','数据结构','王明','计算机出版社');（2）SELECTFROMBorrowRecordsWHEREReaderID='R001';（3）DELETEFROMBooksWHEREBookID='B001';解析：-插入操作使用INSERT语句，插入新书信息；-查询操作使用SELECT语句，根据读者ID查询借阅记录；-删除操作使用DELETE语句，根据书号删除图书。2.参考答案：（1）邻接矩阵：```ABCDEA01110B10110C11001D11001E00110```（2）邻接表：```A:B,C,DB:A,C,DC:A,B,ED:A,B,EE:C,D```解析：-邻接