2026年自学考试数据结构(本科)真题单套试卷

2026年自学考试数据结构(本科)真题单套试卷考试时长：120分钟满分：100分班级：__________姓名：__________学号：__________得分：__________一、单选题（总共10题，每题2分，总分20分）1.在数据结构中，下列哪一种结构是线性结构？A.树形结构B.图结构C.双向链表D.图形结构2.快速排序的平均时间复杂度为？A.O(n)B.O(n²)C.O(nlogn)D.O(logn)3.在二叉搜索树中，任意节点的左子树中的所有节点的值均小于该节点的值，这一性质称为？A.完全二叉树性质B.二叉搜索树性质C.平衡二叉树性质D.哈夫曼树性质4.下列哪种算法适用于求解图中单源最短路径问题？A.Dijkstra算法B.Floyd-Warshall算法C.Kruskal算法D.Prim算法5.在栈中，元素的进出遵循的原则是？A.先进先出（FIFO）B.后进先出（LIFO）C.随机进出D.无序进出6.下列哪种数据结构适合实现LRU（最近最少使用）缓存？A.队列B.哈希表C.双向链表+哈希表D.堆7.在稀疏矩阵的存储中，通常采用哪种方法以减少存储空间？A.三元组表B.稀疏矩阵压缩存储C.二维数组D.哈希表8.堆排序的时间复杂度在最好、最坏和平均情况下均为？A.O(n)B.O(n²)C.O(nlogn)D.O(logn)9.下列哪种数据结构是递归算法的典型应用？A.栈B.队列C.链表D.树10.在图的遍历中，深度优先搜索（DFS）和广度优先搜索（BFS）的主要区别在于？A.存储结构不同B.遍历顺序不同C.时间复杂度不同D.空间复杂度不同二、填空题（总共10题，每题2分，总分20分）1.在队列中，插入元素的操作称为______，删除元素的操作称为______。2.哈希表通过______将键映射到表中一个位置。3.二叉树的深度为h，则其最多有______个结点。4.在快速排序中，选择一个基准元素，将数组分为两部分，使得左边的所有元素都小于基准，右边的所有元素都大于基准，这一过程称为______。5.图的邻接矩阵表示法中，若两个顶点之间有边，则对应的矩阵元素为______，否则为______。6.栈是一种______的数据结构，只允许在栈顶进行插入和删除操作。7.堆是一种特殊的______，满足堆性质。8.在二叉搜索树中，查找一个元素的时间复杂度在最坏情况下为______。9.稀疏矩阵的压缩存储中，通常使用三元组表来表示非零元素及其位置。10.图的遍历算法包括______和______。三、判断题（总共10题，每题2分，总分20分）1.队列是一种先进先出（FIFO）的数据结构。2.哈希表的时间复杂度总是O(1)。3.完全二叉树中，若一个节点有右子节点，则一定有左子节点。4.快速排序在最坏情况下的时间复杂度为O(n²)。5.图的邻接表表示法比邻接矩阵表示法更节省空间。6.栈和队列都是线性数据结构。7.堆排序是一种稳定的排序算法。8.在二叉搜索树中，删除节点后，树仍然保持二叉搜索树的性质。9.稀疏矩阵的压缩存储会丢失矩阵的原始信息。10.深度优先搜索（DFS）和广度优先搜索（BFS）都能遍历图中的所有顶点。四、简答题（总共4题，每题4分，总分16分）1.简述栈和队列的主要区别。2.解释什么是二叉搜索树，并说明其性质。3.描述Dijkstra算法的基本思想及其适用条件。4.什么是图的遍历？简述深度优先搜索（DFS）和广度优先搜索（BFS）的异同。五、应用题（总共4题，每题6分，总分24分）1.给定一个无向图，其邻接矩阵如下：\[\begin{matrix}0&1&0&1&0\\1&0&1&1&0\\0&1&0&0&1\\1&1&0&0&1\\0&0&1&1&0\end{matrix}\]请用深度优先搜索（DFS）遍历该图，假设起始顶点为顶点1，并给出遍历顺序。2.编写一个算法，实现快速排序，并说明其工作原理。3.给定一个二叉搜索树，其结构如下：```5/\37/\\248```请删除节点4，并画出删除后的二叉搜索树。4.设计一个哈希表，用于存储学生信息（学号、姓名、成绩），假设哈希函数为H(key)=key%10，解决哈希冲突的方法为链地址法。请插入以下学生信息：-学号：1001，姓名：张三，成绩：85-学号：1002，姓名：李四，成绩：90-学号：1003，姓名：王五，成绩：78画出插入后的哈希表。【标准答案及解析】一、单选题1.C解析：双向链表是线性结构，其他选项均为非线性结构。2.C解析：快速排序的平均时间复杂度为O(nlogn)，最坏情况为O(n²)。3.B解析：二叉搜索树的性质是指左子树所有节点值小于根节点，右子树所有节点值大于根节点。4.A解析：Dijkstra算法适用于求解单源最短路径问题，Floyd-Warshall算法适用于求解所有顶点对之间的最短路径。5.B解析：栈的进出原则是后进先出（LIFO）。6.C解析：双向链表+哈希表可以高效实现LRU缓存，链表维护顺序，哈希表实现快速查找。7.B解析：稀疏矩阵压缩存储可以大幅减少存储空间，如三元组表。8.C解析：堆排序的时间复杂度在最好、最坏和平均情况下均为O(nlogn)。9.A解析：栈是递归算法的典型应用，如函数调用栈。10.B解析：DFS按深度遍历，BFS按广度遍历，遍历顺序不同。二、填空题1.入队，出队解析：队列的插入和删除操作分别称为入队和出队。2.哈希函数解析：哈希表通过哈希函数将键映射到表中位置。3.2^h-1解析：二叉树的深度为h时，最多有2^h-1个节点。4.分区解析：快速排序的分区过程将数组分为小于和大于基准的两部分。5.1，0解析：邻接矩阵中，有边为1，无边为0。6.栈解析：栈是后进先出（LIFO）的数据结构。7.完全二叉树解析：堆是特殊的完全二叉树，满足堆性质。8.O(n)解析：二叉搜索树最坏情况下为O(n)。9.稀疏矩阵解析：三元组表用于表示稀疏矩阵的非零元素。10.深度优先搜索，广度优先搜索解析：图的遍历算法包括DFS和BFS。三、判断题1.√解析：队列是先进先出（FIFO）的数据结构。2.×解析：哈希表的平均时间复杂度为O(1)，但最坏情况下为O(n)。3.√解析：完全二叉树中，若一个节点有右子节点，则一定有左子节点。4.√解析：快速排序最坏情况为O(n²)，如数组已排序。5.√解析：邻接表比邻接矩阵更节省空间，尤其稀疏图。6.√解析：栈和队列都是线性数据结构。7.×解析：堆排序是不稳定的排序算法。8.√解析：删除节点后，二叉搜索树仍保持性质。9.×解析：稀疏矩阵压缩存储不丢失原始信息。10.√解析：DFS和BFS都能遍历图中的所有顶点。四、简答题1.简述栈和队列的主要区别。答：栈是后进先出（LIFO）的数据结构，只允许在栈顶进行插入和删除操作；队列是先进先出（FIFO）的数据结构，允许在队头插入，队尾删除。2.解释什么是二叉搜索树，并说明其性质。答：二叉搜索树（BST）是左子树所有节点值小于根节点，右子树所有节点值大于根节点的二叉树。性质包括：-每个节点至多有两个子节点。-左子树所有节点值小于根节点。-右子树所有节点值大于根节点。3.描述Dijkstra算法的基本思想及其适用条件。答：Dijkstra算法用于求解单源最短路径问题，基本思想是：-初始化：将起点到自身的距离为0，其他顶点为无穷大。-更新：每次选择未处理顶点中距离最小的顶点，更新其邻接顶点的距离。-适用条件：适用于带权无向图或带权有向图，且边权非负。4.什么是图的遍历？简述深度优先搜索（DFS）和广度优先搜索（BFS）的异同。答：图的遍历是指按某种顺序访问图中的所有顶点，且每个顶点只访问一次。-DFS按深度遍历，使用栈，可能较深。-BFS按广度遍历，使用队列，可能较宽。异同：-都能遍历所有顶点。-存储结构不同（DFS用栈，BFS用队列）。五、应用题1.给定一个无向图，其邻接矩阵如下：\[\begin{matrix}0&1&0&1&0\\1&0&1&1&0\\0&1&0&0&1\\1&1&0&0&1\\0&0&1&1&0\end{matrix}\]请用深度优先搜索（DFS）遍历该图，假设起始顶点为顶点1，并给出遍历顺序。解：-初始化：访问顺序为空，未访问顶点为{1,2,3,4,5}。-访问顶点1，标记为已访问，访问顺序：{1}。-顶点1的邻接顶点为2和4，选择顶点2，访问顺序：{1,2}。-顶点2的邻接顶点为1和3，顶点1已访问，选择顶点3，访问顺序：{1,2,3}。-顶点3的邻接顶点为2和5，顶点2已访问，选择顶点5，访问顺序：{1,2,3,5}。-顶点5的邻接顶点为3和4，顶点3已访问，选择顶点4，访问顺序：{1,2,3,5,4}。-顶点4的邻接顶点为1、2和5，均已访问，结束。遍历顺序：1,2,3,5,4。2.编写一个算法，实现快速排序，并说明其工作原理。答：快速排序算法：```voidquickSort(intarr[],intleft,intright){if(left<right){intpivot=partition(arr,left,right);quickSort(arr,left,pivot-1);quickSort(arr,pivot+1,right);}}intpartition(intarr[],intleft,intright){intpivot=arr[right];inti=left-1;for(intj=left;j<right;j++){if(arr[j]<pivot){i++;swap(arr[i],arr[j]);}}swap(arr[i+1],arr[right]);returni+1;}```工作原理：-选择基准元素（通常为最后一个元素）。-分区：将数组分为小于和大于基准的两部分。-递归排序左右两部分。3.给定一个二叉搜索树，其结构如下：```5/\37/\\248```请删除节点4，并画出删除后的二叉搜索树。解：-节点4的左子节点为空，右子节点为空，直接删除。-删除后，二叉搜索树结构：```5/\37/\28```4.设计一个哈希表，用于存储学生信息（学号、姓名、成绩），假设哈希函数为H(key)=key%10，解决哈希冲突的方法为链地址法。请插入以下学生信息：-学号：1001，姓名：张三，成绩：85-学号：1002，姓名：李四，成绩