您现在的位置：统招专升本频道 > 教材大纲 > 湖南 > 张家界学院2024年专升本《软件工程专业课》考试大纲

张家界学院2024年专升本《软件工程专业课》考试大纲

来源：诚为径教育时间：2024年03月25日

分享：

　　(四)串

　　1. 识记：(1)串的定义;(2)串的相关概念：长度、子串、空串、位置等。

　　2. 理解：(1)串与线性表的区别;(2)串的抽象数据类型;(3)串的定长顺序存储方式的算法实现;(4)串的模式匹配算法，特别是KMP算法。

　　3. 运用：改进的KMP算法。

　　(五)树和二叉树

　　1. 识记：(1)树的定义和相关术语;(2)树的逻辑结构特征;(3)二叉树的定义;(4)最优二叉树(赫夫曼树)的相关概念。

　　2. 理解：(1)树的三种表示法;(2)二叉树的性质;(3)二叉树的顺序存储结构和链式存储结构;(4)二叉树的三种遍历算法及其实现：先序遍历、中序遍历、后序遍历，并确定三种遍历所得到的相应的结点访问序列;(5)二叉树线索化的目的及实质;(6)树和森林与二叉树之间的转换;(7)赫夫曼树算法的思想。

　　3. 运用：(1)根据给定的叶子结点及其权值构造出相应的赫夫曼树;(2)根据赫夫曼树构造对应的赫夫曼编码。

　　(六)图

　　1. 识记：(1)图的定义与术语;(2)图的逻辑结构特征;(3)生成树和最小生成树的相关概念;(4)最短路径的含义;(5)关键路径的含义。

　　2. 理解：(1)图的邻接矩阵和邻接表两种存储结构算法的实现;(2)根据应用问题的特点和要求选择合适的存储结构;(3)连通图及非连通图的深度优先搜索和广度优先搜索算法的实现及时间分析;(4)最小生成树的两种算法：Prim算法和Dijkstra算法的基本思想、时间性能及其各自的特点;(5)拓扑排序的基本思想和步骤;(6)关键路径算法的实现;(7)求单源最短路径的Dijkstra算法的基本思想和时间性能。

　　3. 运用：(1)对给定的连通图，根据Prim和Kruskal算法构造出最小生成树;(2)对给定的有向图，若拓扑序列存在，则写出一个或多个拓扑序列;(3)在AOE网中，求出活动的最早开始时间和最晚开始时间，得到关键活动，求出关键路径;(4)对于给定的有向图，根据Dijkstra算法构造出单源最短路径。

　　(七)查找

　　1. 识记：(1)查找表以及相关概念;(2)二叉排序树的相关概念;(3)哈希表的相关概念。

　　2. 理解：(1)顺序查找、二分查找的算法实现和查找效率分析;(2)二叉排序树的插入、删除、建立和查找算法的实现及效率分析;(3)哈希表的构造方法和处理冲突的方法。

　　3. 运用：哈希表查找方法的应用。

　　五、课程考核实施要求