2020陇东学院专升本计算机科学与技术专业考试大纲(2)

【导读】华图甘肃医疗人才网提供以下社会招聘考试信息：陇东学院招生就业处发布：2020陇东学院专升本计算机科学与技术专业考试大纲(2),关注公众号：甘肃华图(gshtjy),获取更多资讯！

　　第5章 数组和广义表

　　1、掌握数组的逻辑结构特征。

　　2、掌握数组的顺序存储结构及地址计算方式。

　　3、掌握数组是一种随机存取结构的原因。

　　4、理解特殊矩阵和稀疏矩阵的概念。

　　5、理解特殊矩阵和压缩存储时的下标变换方法。

　　6、理解稀疏矩阵的三元组表表示方法及有关算法。

　　7、掌握广义表的有关概念及其与线性表的关系。

　　8、掌握广义表的括号表示和图形表示之间的转换。

　　第6章树

　　1、掌握树的逻辑结构特征。

　　2、掌握树的不同表示方法。

　　3、掌握树的常用术语及含义。

　　4、二叉树的递归定义及树与二叉树的差别。

　　5、掌握二叉树的性质，了解相应的证明方法。

　　6、掌握二叉树的两种存储方法、特点及适用范围。

　　7、掌握二叉树的三种遍历算法，理解其执行过程。

　　8、掌握确定三种遍历所得到的相应的结点访问序列。

　　9、理解以遍历算法为基础，设计有关算法解决简单的应用问题。

　　10、理解二叉树线索化的目的及实质。

　　11、理解在中序线索树中查找给定结点的中序前趋和中序后继的方法。

　　12、掌握树和森林与二叉树之间的转换方法。

　　13、掌握树的各种存储结构及其特点。

　　14、掌握树的两种遍历方法。

　　15、掌握最优二叉树和最优前缀码的概念及特点。

　　16、掌握哈夫曼算法的思想。

　　17、掌握根据给定的叶结点及其权值构造出相应的最优二叉树。

　　18、掌握根据最优二叉树构造对应的哈夫曼编码。

　　第7章图

　　1、理解图的逻辑结构特征。

　　2、理解图的常用术语及含义。

　　3、掌握邻接矩阵和邻接表这两种存储结构的特点及适用范围。

　　4、掌握根据应用问题的特点和要求选择合适的存储结构。

　　5、理解连通图及非连通图的深度优先搜索和广度优先搜索两种遍历算法,其执行过程以及时间分析。

　　6、掌握确定两种遍历所得到的顶点访问序列。

　　7、掌握图的两种遍历与树的遍历之间的关系。

　　8、理解两种遍历所使用的辅助数据结构(栈或队列)在遍历过程中所起的作用。

　　9、理解利用图的两种遍历设计算法解决简单的应用问题。

　　10、掌握生成树和最小生成树的概念。

　　11、掌握对遍历给定的图，画出深度优先和广度优先生成树或生成森林。

　　12、掌握Prim和Kruskal算法的基本思想、时间性能及这两种算法各自的特点。

　　13、掌握要求对给定的连通图，根据Prim和Kruskal算法构造出最小生成树。

　　14、了解最短路径的含义。

　　15、了解求单源最短路径的Dijkstra算法的基本思想和时间性能。

　　16、掌握对于给定的有向图，根据Dijkstra算法画出求单源最短路径的过程示意图。

　　17、掌握拓扑排序的基本思想和步骤。

　　18、理解拓扑排序不成功的原因。

　　19、了解对给定的有向图，若拓扑序列存在，则要求写出一个或多个拓扑序列。

　　 （编辑：华图_潇潇）