湖南城市学院2025年“专升本”招生考试 计算机科学与技术专业《数据结构》科目考试要求

I．考试内容与要求

本科目考试内容涵盖数据结构绪论、线性表、栈和队列、串和数组与广义表、树和二叉树、图、查找、内排序等方面的内容，主要考察考生对数据结构基本知识和基本方法的理解、掌握程度，在领会的基础上，能用所学的知识点解决问题，掌握数据组织、存储和运算的基本原理和方法，具备数据结构和相关算法的分析和设计的能力。

一、数据结构绪论

考试内容：

数据结构绪论考试内容主要包括数据、数据元素、数据结构的基本概念，以及算法和抽象数据类型的理解，对数据结构绪论中相关术语和概念的理解和应用，以及对算法时间复杂度分析的掌握程度‌。

考核要求：

1.识记：考试内容主要包括数据、数据元素、数据结构的基本概念。

2.了解：算法和抽象数据类型的理解。

3.简单应用：对算法时间复杂度分析的掌握程度。

二、线性表

考试内容：

‌线性表考试内容主要包括线性表的定义、逻辑结构、存储结构以及基本操作‌。

考核要求：

1.识记：线性表的定义、逻辑结构。

2.了解：线性表的基本操作。

3.简单应用：线性表实例操作

三、栈和队列

考试内容：

‌栈和队列的考试内容主要包括栈和队列的基本概念、存储结构、基本操作以及应用‌。

考核要求：

1.识记：栈：一类受限的线性表，只允许在一端（栈顶）进行插入和删除操作，具有先进后出（FILO）的特点。

队列：也是一种操作受限的线性表，限制其在表的一端（队尾）进行插入而在另一端（队头）进行删除操作，具有先进先出（FIFO）的特点。

‌存储结构‌：

栈的存储结构包括顺序栈和链栈。顺序栈使用数组实现，链栈使用链表实现。

队列的存储结构同样包括顺序队列和链队列。顺序队列使用数组实现，链队列使用链表实现‌

2.了解：栈的基本操作包括初始化栈、判断栈是否为空、入栈、出栈、获取栈顶元素等。

队列的基本操作包括初始化队列、判断队列是否为空、队尾入队列、队头出队列、获取队列头部元素、获取队列队尾元素等‌。

3.简单应用：

栈和队列在解决实际问题中有广泛应用，如括号匹配问题、用队列实现栈、用栈实现队列、设计循环队列等‌2。

栈还可以用于表达式求值、递归函数调用等场景；队列则常用于广度优先搜索（BFS）、任务调度等场景。

四、串和数组与广义表

考试内容：

‌串和数组与广义表考试内容主要包括串的定义、表示和实现，数组的定义、存储和特殊矩阵的压缩存储，以及广义表的定义、存储结构和基本运算‌。。

考核要求：

1.识记：‌串和数组与广义表的定义。

2.了解：‌串和数组与广义表的表示。

3.简单应用：‌串和数组与广义表的操作，涉及串、数组和广义表在实际问题中的应用，如字符串处理、矩阵运算、数据结构设计场景。

五、树和二叉树

考试内容：

树和二叉树的考试内容主要包括树的基本概念、二叉树的概念与性质、二叉树的遍历、特殊二叉树、树与二叉树的转换，以及树与二叉树的应用‌。

考核要求：

1.识记：树和二叉树的基本概念与性质。

2.了解：二叉树的遍历、特殊二叉树、树与二叉树的转换。

3.简单应用：树与二叉树的应用，如哈夫曼编码，构造哈夫曼树。

六、图

考试内容：

‌图的考试内容通常涵盖图的基本概念、图的表示方法、图的遍历算法以及图的应用等多个方面‌。‌首先，图的基本概念是考试的基础‌。这包括图的定义、图的分类（如有向图、无向图、加权图等）、顶点（节点）和边的概念，以及图的一些基本术语，如图的度、路径、连通性、环等。‌其次，图的表示方法是考试的重点之一‌。图的表示方法有多种，包括邻接矩阵、邻接表和十字链表等。考生需要理解并掌握这些表示方法的特点、适用场景以及构建方法。‌再次，图的遍历算法是考试的难点和核心‌。图的遍历算法主要包括深度优先搜索（DFS）和广度优先搜索（BFS）。考生需要理解这两种算法的原理、实现步骤以及时间复杂度和空间复杂度等特性，并能够灵活运用这些算法解决实际问题。‌最后，图的应用也是考试的重要内容‌。图的应用非常广泛，包括最短路径问题、最小生成树问题、拓扑排序、关键路径问题等。考生需要理解这些应用问题的背景、求解方法以及算法实现，并能够根据具体问题选择合适的算法进行求解。

考核要求：

1.识记：‌图的考试内容通常涵盖图的基本概念、图的表示方法。

2.了解：图的遍历算法是考试的难点和核心。

3.简单应用：图的应用非常广泛，包括最短路径问题、最小生成树问题、拓扑排序、关键路径问题等。

七、查找

考试内容：

一、查找的基本概念‌

查找的定义：根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。

查找表的概念：由同一类型的数据元素构成的集合，它是一种以查找为核心，同时包括其他运算的非常灵活的数据结构。

静态查找表与动态查找表的区别：静态查找表只进行查找和读取操作，而动态查找表还包括插入和删除操作。

‌二、线性结构的查找

顺序查找：线性表上的查找，按照顺序逐个比较，直到找到目标元素或遍历完整个表。

折半查找（二分查找）：在有序表中，通过不断将查找范围减半来快速定位目标元素。

分块查找：将表分成若干块，每块内元素无序但块间有序，先通过索引确定块，再在块内顺序查找。

‌三、树形结构的查找

二叉排序树（BST）：一种特殊的二叉树，左子树所有节点关键字小于根节点，右子树所有节点关键字大于根节点，支持快速查找、插入和删除‌13。

平衡二叉树（AVL）：在二叉排序树的基础上，通过旋转操作保持树的平衡，使得查找效率更高。

‌四、散列结构的查找

散列表（哈希表）：通过哈希函数将关键字映射到表中的一个位置，实现快速查找。需要掌握散列表的构造方法、冲突处理方法以及性能分析。查找的定义、查找表的概念。

考核要求：

1.识记：查找的定义、概念

2.了解：线性结构的查找。

3.简单应用：哈希表、与哈希函数构造

八、内排序

考试内容：

‌内排序考试内容主要包括排序的基本概念、各种常用的排序方法以及它们的性能分析‌。首先，排序的基本概念是考试的基础，包括排序的定义、排序方法的稳定性、内部排序与外部排序的区别，以及排序方法的分类依据等。排序是将一组杂乱无章的记录序列调整为按其关键字的顺序排列起来的有序记录序列，稳定性则是指排序算法在排序过程中是否保持相同关键字的记录之间的相对顺序不变。其次，各种常用的排序方法是考试的重点。这包括直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序和基数排序等。考生需要理解每种排序算法的原理、实现步骤，以及它们的时间复杂度和空间复杂度等特性。例如，直接插入排序是将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度；快速排序则是通过递归的方式将序列划分为左右两个子序列，再分别对子序列进行排序。最后，性能分析也是考试的重要内容之一。考生需要了解各种排序算法在不同情况下的性能表现，包括最好情况、最坏情况和平均情况下的时间复杂度和空间复杂度。同时，还需要掌握如何根据具体问题的特点选择合适的排序算法进行求解，以及如何对排序算法进行优化以提高性能。

考核要求：

1.识记：‌内排序考试内容主要包括排序的基本概念。

2.了解：各种常用的排序方法。直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序和基数排序。

3.应用：排序具体应用与性能分析。

 

Ⅱ．考试形式与试卷结构

一、考试形式

考试采用闭卷、笔试形式。试卷满分 200分，考试时间 150 分钟。可使用不带存储功能的计算器，不得携带任何纸张、教材、笔记本、作业本、参考资料、电子读物、电子器具和工具书等进入考场。

二、试卷结构

试卷包括判断题、单选题、填空题、简答题、综合题。其中，判断题20分；单选题60分；填空题20分；简答题60分；综合题40分。