数据结构课程考核说明.doc

数据结构课程考核说明与综合练习第一部分考核说明《数据结构》课程是计算机科学与技术专业统设的一门重要的必修专业基础课,它主要研究数据的各种逻辑结构和在计算机中的存储结构,还研究对数据进行的插入、查找、删除、排序、遍历等基本运算或操作以及这些运算在各种存储结构上具体实现的算法。考试的题型有:单选题、填空题、运算题、阅读算法、填写算法和编写算法等。下面按照主教材中各章次序给出每章的具体复习要求。第一章绪论【重点掌握】,对应的图形表示,序偶和边之间的对应关系。、线性结构、树结构和图结构的特点。。、计算方法、数量级表示。、最差和平均这三种情况的时间复杂度的计算。对于本章的其余内容均作一般掌握。第二章线性表【重点掌握】,线性表中每一种操作的功能,对应的函数名、返回值类型和参数表中每个参数的作用。,即List类型的定义和每个域的定义及作用。,及相应的时间复杂度。,线性表的单链接和双链接存储的结构,向单链表中一个结点之后插入新结点或从单链表中删除一个结点的后继结点的指针链接过程。,每个域的定义及作用,即LNode类型的定义及结构。、循环链表、双向链表的结构特点。。。对于本章的其余内容均作一般掌握。第三章栈和队列【重点掌握】,栈中每一种操作的功能,对应的函数名、返回值类型和参数表中每个参数的作用。,即Stack类型的定义和每个域的定义及作用。,及相应的时间复杂度。。,以及相互转换的规则,后缀表达式求值的方法。,队列中每一种操作的功能,对应的函数名、返回值类型和参数表中每个参数的作用。,即Queue类型的定义和每个域的定义及作用。。。【一般掌握】,把中缀表达式转换为后缀表达式的算法。,以及实现每一种队列运算的算法和相应的时间复杂度。对于本章的其余内容均作一般了解。第四章串【重点掌握】;(定长顺序存储表示;堆分配存储表示;块链存储表示)【一般掌握】其他内容第五章稀疏矩阵和广义表【重点掌握】。、带行指针向量的链接存储,在每一种存储中非零元素结点的结构。。,广义表长度和深度的计算。,分别求广义表长度和深度的递归算法,它们对应的时间复杂度。,元素地址和数组地址的计算,元素占用存储空间大小和数组占用存储空间大小的计算。【一般掌握】稀疏矩阵转置的算法描述。对于本章的其余内容均作一般了解。第六章树和二叉树【重点掌握】,对于一棵具体树和二叉树的二元组表示及广义表表示。,如结点的度、树的度、树的层数、树的深度等。,如已知树或二叉树的深度h可求出相应的最多结点数,已知结点数n可求出对应树或二叉树的最大和最小高度。。,即BTreeNode类型的定义和每个域的定义及作用。、中序、后序遍历的递归过程和递归算法,中序遍历的非递归算法,按层遍历的过程和算法,每种算法的时间复杂度。。,相应的时间复杂度,查找一个元素的查找长度,即从树根结点到该结点的路径上的结点数。,树的带权路径长度的计算,根据若干个叶子结点的权构造哈夫曼树的过程。【一般掌握】对于本章的其余内容均作一般了解。第七章图【重点掌握】。,如顶点、边、度、完全图、子图、路径、路径长度、连通图、权、网等。、邻接表、十字链表和邻接