教学大纲教案进度计划通信工程专业算法与数据结构期末复习.doc

《教学大纲教案进度计划通信工程专业算法与数据结构期末复习.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、通信工程专业《数据结构》期末复习题型：一、单项选择题（5小题，10%）二、判断题（5小题，10%）三、填空题（8小题，16%）四、简答题（3小题，只要结果，15％）五、应用题（给出解题过程和结果，32%）六、算法设计题（17%）1.算法填空（7-8%）2.设计分析（9-10%）复习要点：第一章1.相关基本概念：数据、数据元素（基本单位）、数据项（最小单位）、数据对象（数据元素集合）数据结构、数据类型、抽象数据类型、算法及其特征等；2.逻辑结构、存储结构（物理结构）及其类型；3.算法分析：语句频度（执行次数）计算、时间和空间复杂度分

2、析。第二章1.顺序表（数组）插入、删除算法及其移动次数计算；2.链表（有无头节点、单双、循环）插入(前、后)、删除（前、本身、后）的指针挂接、建立（正向、逆向、就地逆置）算法。第三章1.栈的进出序列、栈、队列、循环队列的满/空条件;2.栈、队列的存储结构、基本操作算法（取顶/头、入、出）;3.递归的基本思想和简单应用。第四章1.字符串模式匹配的简单算法；第五章1.二维数组的地址（下标）换算；2.特殊矩阵（三角、其他有规律）压缩为一维的下标计算；3.稀疏矩阵的三元组表示。第六章1.二叉树的先序、中序、后序、层次遍历过程；树的先序、后

3、序、层次遍历过程；2.二叉树的性质；3.前/后序列、中序序列转换二叉树；4．二叉树与树相互转换；5.哈夫曼树和编码过程、带权路径长度计算。第七章1.邻接矩阵、邻接表存储结构及其特征；2.深度、广度优先遍历过程；3.最小生成树过程（Prim、Kruskal）；4.拓扑排序、工期计算与求关键路径过程；5、最短路径（Dijkstra、Floyd）过程。第九章1.以下所有查找成功、不成功平均查找长度2.顺序查找（数组、链表）算法；折半查找算法；3.二叉排序树的插入（建立）、删除；4.哈希表构造、冲突解决方法；除留余数法、线性探测或链地址法

4、下的存储过程。第十章1.简单排序（直接插入、选择、冒泡）的算法及其过程；2.先进排序（希尔、快速、堆、归并、基数）过程；3.各种排序的特点、稳定性、时间复杂度（包括平均、最好、最坏）。算法描述：1.顺序表（数组）插入、删除算法；2.链表（有头节点、单双、循环）插入(前、后)、删除（前、本身、后）、建立（正向、逆向、就地逆置）算法；3.栈、队列基本操作算法（取顶/头、入、出）；4.字符串模式匹配的简单算法；5.顺序查找（数组、链表）算法；折半查找算法；6.简单排序（直接插入、选择、冒泡）的算法。7.实验算法