湖南工业大学科技学院《计算机科学》27年考试重点

一、（必考，分值占比约70%~80%）

1. 算法分析的方法与算法的基本特征（绪论）

• 可能题型：选择题、填空题、判断题。

• 具体考点：时间复杂度的计算（如循环嵌套O(n²)、二分查找O(log n)）、空间复杂度概念；算法的五大特征（有穷性、确定性、可行性、输入、输出）。

• 原因：这是数据结构的“第一课”，是评价算法优劣的基本工具，必以小题形式出现。

2. 线性表、栈、队列的顺序与链式存储，插入/删除操作，循环队列，递归应用（第2章）

• 可能题型：编程题（25分）、应用题、填空题。

• 具体考点：

• 单链表的插入、删除（给定头指针和位置）；

• 顺序栈和链栈的入栈/出栈操作；

• 循环队列的队空/队满判断、入队/出队（使用取模运算）；

• 递归应用：如递归计算阶乘、斐波那契，或汉诺塔问题。

• 原因：这部分是数据结构“动手能力”的根基。专升本编程题几乎必考链表操作或栈/队列模拟（如括号匹配、迷宫路径）。循环队列是常考难点，容易出填空或应用。

3. 树与二叉树（第3章）

• 可能题型：应用题（构造哈夫曼树）、编程题（遍历）、填空题（树转二叉树）。

• 具体考点：

• 二叉树的前序、中序、后序遍历（递归和非递归思想，重点考递归代码或遍历序列推导）；

• 树与二叉树的转换（孩子兄弟表示法，常给出树求对应的二叉树）；

• 哈夫曼树的构造（给定权值，画出哈夫曼树，计算WPL）；

• 二叉树的性质（如叶子数与度为2的关系）。

• 原因：二叉树是数据结构的分水岭，考试必占大头。哈夫曼树是应用题高频题（计算题），遍历序列推导也是填空/选择经典题。

4. 图（第4章）——聚焦三个算法

• 可能题型：应用题（最小生成树、拓扑排序、最短路径）、选择/填空（存储结构）。

• 具体考点：

• 最小生成树：Prim或Kruskal算法步骤，画出选边过程；

• 拓扑排序：给出有向图写出一个拓扑序列；

• 最短路径：Dijkstra算法（单源）的手工推演；

• 图的存储结构：邻接矩阵和邻接表的特点、适用场景。

• 原因：这三个算法是图的核心应用，非常适宜出成“应用题”（25分中的大部分）。深度/广度优先遍历虽然列为“一般熟悉”，也可能结合填空或简答。

5. 查找（第5章）——三种基本查找

• 可能题型：填空、应用、编程（顺序/折半查找）。

• 具体考点：

• 顺序查找：平均查找长度（ASL），哨兵法；

• 折半查找：判定树构造，ASL计算，给定有序表查找某元素的过程；

• 分块查找：索引表结构，查找步骤。

• 原因：折半查找的判定树是应用题常见题型，分块查找体现“索引思想”，也容易出小题。编程题若出查找，一般是折半查找的完整代码或顺序查找的变式。

6. 排序（第6章）——常考排序算法

• 可能题型：填空、选择、应用（排序过程）、编程（快速排序或冒泡排序）。

• 具体考点：

• 直接插入排序：手工模拟每趟结果；

• 希尔排序：给定增量序列，写出每趟结果；

• 冒泡排序：改进后的冒泡（是否交换标志）；

• 快速排序：一次划分过程（枢轴选取，左右交换），递归思想；

• 算法比较：稳定性、时间复杂度、空间复杂度。

• 原因：排序是必考大模块。快速排序的分治思想和“一趟划分”极易出应用题，编程题也喜欢考快排或冒泡的实现。希尔排序作为“重点掌握”中唯一的高级插入排序，常以填空形式考察增量序列。

二、“一般熟悉”部分（可能会考，占比约20%）

这些内容虽然不在“重点掌握”中，但作为知识体系的必要组成，常出现在小题或应用题的某一小问中。

• 串的简单模式匹配（BF算法）：可能考一趟匹配的过程（填空或选择）。

• 数组存储地址计算：给定行优先或列优先，求某元素地址（填空）。

• 稀疏矩阵的三元组表示：转置或简单读取（填空）。

• 二叉树的遍历算法思想（非递归）：可能让你简述思路，或与递归做对比（判断题）。

• 图的深度/广度优先遍历：给图写出DFS/BFS序列（填空或应用小问）。

• 二叉排序树：构造、查找、插入（可能考应用，但不是最高频）。

• 简单选择排序、堆排序：堆排序的建堆过程（小题），选择排序的每趟结果（填空）。

• 哈希表：哈希函数构造、解决冲突（线性探测），ASL计算（应用或填空）。

三、“一般了解”部分（基本不考或最多1~2道判断/选择）

内容如：数据结构研究的内容、哈夫曼树特性、归并排序/基数排序细节、图的基本术语等。这些只需要知道基本概念，不会单独出大题。