2026武汉科技大学计算机科学与技术复试题库

2026武汉科技大学计算机科学与技术复试题库一、单选题（每题3分，共30分）1.以下哪种排序算法的平均时间复杂度为O(nlogn)且空间复杂度为O(1)？（）A.快速排序B.归并排序C.堆排序D.冒泡排序答案：C解析：堆排序平均时间复杂度为O(nlogn)，并且在排序过程中只需要常数级别的额外空间，空间复杂度为O(1)。快速排序平均时间复杂度为O(nlogn)，但最坏情况是O(n^2)，且空间复杂度平均为O(logn)，最坏为O(n)；归并排序平均时间复杂度为O(nlogn)，空间复杂度为O(n)；冒泡排序平均时间复杂度为O(n^2)。2.设一棵完全二叉树共有700个结点，则在该二叉树中有（）个叶子结点。A.349B.350C.351D.352答案：B解析：完全二叉树中，度为1的结点要么为0个，要么为1个。设叶子结点数为n0，度为2的结点数为n2，根据二叉树的性质n0=n2+1，以及总结点数n=n0+n1+n2=700。当n1=0时，可得n0=(700+1)/2=350.5，向下取整为350；当n1=1时，可得n0=(700-1+1)/2=350，所以叶子结点数为350个。3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表答案：A解析：顺序表可以随机存取，时间复杂度为O(1)，在最后进行插入和删除运算时间复杂度为O(1)；双链表、带头结点的双循环链表、单循环链表在最后进行插入和删除运算时间复杂度为O(1)，但存取指定序号元素时间复杂度为O(n)。4.下列关于哈希表的说法，正确的是（）。A.哈希表的平均查找长度与哈希函数无关B.哈希表的平均查找长度与处理冲突的方法无关C.哈希表的平均查找长度与装填因子无关D.哈希表的平均查找长度与哈希表的大小有关答案：D解析：哈希表的平均查找长度与哈希函数、处理冲突的方法、装填因子以及哈希表的大小都有关系。哈希函数影响关键字的分布，处理冲突的方法影响冲突发生后的查找次数，装填因子影响哈希表的空间利用率和冲突概率，哈希表大小不同，这些因素综合起来对平均查找长度都会产生影响。5.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）。A.nB.(n-1)×(n-1)C.n×nD.(n+1)×(n+1)答案：C解析：邻接矩阵是用一个n×n的矩阵来表示图，矩阵中元素的值表示对应顶点之间是否有边相连。6.深度为5的满二叉树有（）个叶子结点。A.16B.15C.32D.31答案：A解析：深度为k的满二叉树叶子结点数为2^(k-1)，深度为5的满二叉树叶子结点数为2^(5-1)=16个。7.以下关于操作系统的描述，错误的是（）。A.操作系统是计算机系统中的一种系统软件B.操作系统管理计算机系统的资源C.操作系统为用户提供了操作界面D.操作系统只负责管理CPU和内存答案：D解析：操作系统负责管理计算机系统的所有硬件和软件资源，包括CPU、内存、外存、设备等，不仅仅是CPU和内存。8.进程与程序的本质区别是（）。A.顺序和非顺序执行机器指令B.存储在内存和外存C.分时使用和独占使用计算机资源D.动态和静态特征答案：D解析：进程是程序在操作系统中的一次执行过程，是系统进行资源分配和调度的基本单位，具有动态性；程序是一组指令的集合，是静态的。9.数据库系统的核心是（）。A.数据库B.数据库管理系统C.数据模型D.软件工具答案：B解析：数据库管理系统是数据库系统的核心软件，负责数据库的建立、使用和维护。10.关系数据库管理系统能实现的专门关系运算包括（）。A.排序、索引、统计B.选择、投影、连接C.关联、更新、排序D.显示、打印、制表答案：B解析：选择、投影、连接是关系数据库管理系统能实现的专门关系运算。选择是从关系中找出满足给定条件的元组；投影是从关系中选取若干属性列组成新的关系；连接是将两个或多个关系组合成一个新的关系。二、多选题（每题5分，共25分）1.以下哪些算法属于贪心算法？（）A.迪杰斯特拉算法B.普里姆算法C.克鲁斯卡尔算法D.哈夫曼编码算法答案：ABCD解析：迪杰斯特拉算法用于求解带权有向图中从一个顶点到其他各顶点的最短路径，采用贪心策略；普里姆算法用于求连通网的最小生成树，是贪心算法；克鲁斯卡尔算法用于求连通网的最小生成树，也是贪心算法；哈夫曼编码算法通过构造哈夫曼树，采用贪心策略选择频率最小的两个节点合并，从而得到最优编码。2.下列关于二叉树遍历的说法，正确的有（）。A.前序遍历的顺序是根、左子树、右子树B.中序遍历的顺序是左子树、根、右子树C.后序遍历的顺序是左子树、右子树、根D.层次遍历是按照层次依次访问节点答案：ABCD解析：这是二叉树遍历的基本定义。前序遍历先访问根节点，再递归访问左子树和右子树；中序遍历先递归访问左子树，再访问根节点，最后递归访问右子树；后序遍历先递归访问左子树和右子树，最后访问根节点；层次遍历是从根节点开始，按照层次依次访问节点。3.下列哪些数据结构是线性结构？（）A.顺序表B.栈C.队列D.链表答案：ABCD解析：顺序表是线性表的顺序存储结构，栈和队列是特殊的线性表，链表是线性表的链式存储结构，它们都属于线性结构。4.下列关于操作系统进程调度算法的说法，正确的有（）。A.先来先服务调度算法有利于长作业B.短作业优先调度算法有利于短作业C.时间片轮转调度算法适用于分时系统D.优先级调度算法可以根据进程的优先级进行调度答案：BCD解析：先来先服务调度算法有利于长作业，因为长作业会先占用CPU资源，导致短作业等待时间过长；短作业优先调度算法优先调度短作业，能提高系统吞吐量；时间片轮转调度算法适用于分时系统，每个进程轮流使用CPU一个时间片；优先级调度算法根据进程的优先级来调度，优先级高的进程优先获得CPU资源。5.数据库设计的步骤包括（）。A.需求分析B.概念结构设计C.逻辑结构设计D.物理结构设计答案：ABCD解析：数据库设计一般分为需求分析、概念结构设计、逻辑结构设计、物理结构设计、数据库实施、数据库运行和维护等步骤，这里选项包含了主要的前期设计步骤。三、判断题（每题3分，共15分）1.快速排序在最坏情况下的时间复杂度为O(n^2)。（）答案：√解析：快速排序在最坏情况下，如每次选择的基准元素都是当前序列中的最大或最小元素，会导致划分后的子序列一个为空，另一个包含n-1个元素，此时时间复杂度为O(n^2)。2.二叉排序树的中序遍历序列是一个有序序列。（）答案：√解析：二叉排序树的定义是左子树的所有节点值小于根节点值，右子树的所有节点值大于根节点值，所以中序遍历二叉排序树得到的序列是一个有序序列。3.顺序存储结构比链式存储结构更节省存储空间。（）答案：×解析：顺序存储结构需要连续的存储空间，可能会存在存储空间浪费的情况；链式存储结构不需要连续存储空间，更灵活，但会额外存储指针信息，所以不能简单说顺序存储结构就比链式存储结构更节省存储空间，要根据具体情况而定。4.进程之间的同步和互斥是为了协调进程之间的竞争关系。（）答案：×解析：进程之间的同步是为了协调进程之间的合作关系，使进程之间按照一定的顺序执行；互斥是为了协调进程之间的竞争关系，避免多个进程同时访问共享资源导致数据不一致等问题。5.数据库的三级模式结构中，外模式是用户与数据库系统的接口。（）答案：√解析：外模式是数据库用户能够看见和使用的局部数据的逻辑结构和特征的描述，是用户与数据库系统的接口。四、简答题（每题10分，共30分）1.简述图的深度优先搜索和广度优先搜索算法的基本思想，并比较它们的优缺点。深度优先搜索基本思想：从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到。广度优先搜索基本思想：从图中某个顶点v出发，访问此顶点，然后依次访问v的各个未被访问的邻接点，再分别从这些邻接点出发依次访问它们的未被访问的邻接点，直到所有顶点都被访问到。优点：深度优先搜索：适合用于搜索图的连通性、寻找图的环等问题，实现相对简单，不需要额外的队列或栈来辅助，空间复杂度较低。广度优先搜索：能保证找到从起始顶点到其他顶点的最短路径（如果边权值相同），对于层次遍历相关问题很适用。缺点：深度优先搜索：可能会陷入死胡同，导致搜索效率低下，而且对于复杂图可能会出现回溯过多的情况。广度优先搜索：需要较多的存储空间来存储队列，空间复杂度较高，对于大规模图可能不适用。2.什么是操作系统的虚拟内存？它有什么作用？虚拟内存是操作系统为每个进程提供的一个假象，每个进程都认为自己拥有连续的、足够大的内存空间。它通过将部分暂时不用的数据和程序存放在外存上，当需要时再调入内存，从而在逻辑上扩充了内存容量。作用：提高内存利用率：允许程序运行时可以使用比实际物理内存更大的地址空间，避免了因为物理内存不足而导致程序无法运行的情况。方便多道程序设计：多个进程可以同时运行，每个进程都可以拥有自己的虚拟内存空间，互不干扰。提供内存保护：不同进程的虚拟内存空间相互隔离，一个进程的错误或恶意操作不会影响其他进程。3.简述数据库中事务的概念及其特性。事务是用户定义的一个数据库操作序