2019陇东学院专升本计算机科学与技术专业考试大纲历年真题录取分数线(二)

第4章串

1、掌握串的有关概念及基本运算。

2、理解串与线性表的关系。

3、掌握串的两种存储表示。

4、掌握使用C语言提供的串操作函数构造与串相关的算法解决简单的应用问题。

第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、掌握要求对给定