陇东学院2013年专升本计算机科学与技术考试大纲

《陇东学院2013年专升本计算机科学与技术考试大纲》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、陇东学院2013年专升本招生考试计算机科学与技术专业专业课考试大纲I《数据结构》一、考试目的考核普通高等学校专科（含高职）应届毕业生对于《数据结构》课程基本知识掌握是否达到教学大纲所规定的要求。二、考试要求及内容第1章绪论1、掌握数据、数据元素、数据项、数据结构等基本概念。2、掌握数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。3、掌握数据结构的两大类逻辑结构和四种常用的存储表示方法。4、理解算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念。5、掌握算法描述和算法分析的方法，

2、对于一般算法能分析出时间复杂度。   第2章线性表1、理解线性表的逻辑结构特征。2、理解线性表上定义的基本运算，并能利用基本运算构造出较复杂的运算。线性表的顺序存储结构，要求达到“综合利用”层次。　3、理解顺序表的含义及特点，即顺序表如何反映线性表中元素之间的逻辑关系。4、掌握顺序表上的插入、删除操作及其平均时间性能分析。　5、理解利用顺序表设计算法解决简单的应用问题。　　6、掌握链表如何表示线性表中元素之间的逻辑关系。　　7、掌握链表中头指针和头结点的使用。　8、理解单链表、双链表、循环链表链接方式上

3、的区别。　9、掌握单链表上实现的建表、查找、插入和删除等基本算法，并分析其时间复杂度。   10、理解循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。   11、理解双链表的定义及其相关的算法。　　12、掌握利用链表设计算法解决简单的应用问题。　13、理解顺序表和链表的主要优缺点。14、掌握针对线性表上所需要执行的主要操作，知道选择顺序表还是链表作为其存储结构才能取得较优的时空性能。第3章栈和队列1、理解栈的逻辑结构特点，栈与线性表的异同。2、掌握顺序栈和链栈上实现的

4、进栈、退栈等基本算法。3、理解栈的“上溢”和“下溢”的概念及其判别条件。4、掌握利用栈设计算法解决简单的应用问题。5、理解队列的逻辑结构特点，队列与线性表的异同。6、掌握顺序队列（主要是循环队列）和链队列上实现的入队、出队等基本算法。7、理解队列的“上溢”和“下溢”的概念及其判别条件。8、了解使用数组实现的循环队列取代普通的顺序队列的原因。9、掌握循环队列中对边界条件的处理方法。10、掌握利用队列设计算法解决简单的应用问题。第4章串1、掌握串的有关概念及基本运算。2、理解串与线性表的关系。3、掌握串的两

5、种存储表示。4、掌握使用C语言提供的串操作函数构造与串相关的算法解决简单的应用问题。第5章数组和广义表。1、掌握数组的逻辑结构特征。2、掌握数组的顺序存储结构及地址计算方式。3、掌握数组是一种随机存取结构的原因。4、理解特殊矩阵和稀疏矩阵的概念。5、理解特殊矩阵和压缩存储时的下标变换方法。6、理解稀疏矩阵的三元组表表示方法及有关算法。7、掌握广义表的有关概念及其与线性表的关系。8、掌握广义表的括号表示和图形表示之间的转换。第6章 树1、掌握树的逻辑结构特征。2、掌握树的不同表示方法。3、掌握树的常用术语

6、及含义。4、二叉树的递归定义及树与二叉树的差别。5、掌握二叉树的性质，了解相应的证明方法。6、掌握二叉树的两种存储方法、特点及适用范围。7、掌握二叉树的三种遍历算法，理解其执行过程。8、掌握确定三种遍历所得到的相应的结点访问序列。9、理解以遍历算法为基础，设计有关算法解决简单的应用问题。10、理解二叉树线索化的目的及实质。11、理解在中序线索树中查找给定结点的中序前趋和中序后继的方法。12、掌握树和森林与二叉树之间的转换方法。13、掌握树的各种存储结构及其特点。14、掌握树的两种遍历方法。15、掌握最优

7、二叉树和最优前缀码的概念及特点。16、掌握哈夫曼算法的思想。17、掌握根据给定的叶结点及其权值构造出相应的最优二叉树。18、掌握根据最优二叉树构造对应的哈夫曼编码。第7章 图1、理解图的逻辑结构特征。2、理解图的常用术语及含义。3、掌握邻接矩阵和邻接表这两种存储结构的特点及适用范围。4、掌握根据应用问题的特点和要求选择合适的存储结构。5、理解连通图及非连通图的深度优先搜索和广度优先搜索两种遍历算法,其执行过程以及时间分析。6、掌握确定两种遍历所得到的顶点访问序列。7、掌握图的两种遍历与树的遍历之间的关系

8、。8、理解两种遍历所使用的辅助数据结构（栈或队列）在遍历过程中所起的作用。9、理解利用图的两种遍历设计算法解决简单的应用问题。10、掌握生成树和最小生成树的概念。11、掌握对遍历给定的图，画出深度优先和广度优先生成树或生成森林。12、掌握Prim和Kruskal算法的基本思想、时间性能及这两种算法各自的特点。13、掌握要求对给定的连通图，根据Prim和Kruskal算法构造出最小生成树。14、了解最短路径的含义。15、了解求单源最短路径的D