数据结构各章学习目标及重难点

《数据结构各章学习目标及重难点》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章概论学习目标1.理解学习数据结构的目的和目标。2.理解数据的逻辑结构和存储结构。3.理解抽象数据类型。4.重点掌握算法的概念，以及算法的执行效率及其度量。重点难点1.数据的逻辑结构和存储结构。2.抽象数据类型3.算法的时间效率，及其分析规则。第二章线性表、栈和队列学习目标1.通过对线性表的学习，对数据结构有一个初步的认识。2.掌握线性表、栈和队列的概念、存储表示、基本运算。3.能够比较评价各种线性表的实现方法，从而能够根据具体情况选择最合适的实现方法。重点难点1.各种线性结构的概念和操作。2.衡量各种线性表

2、的实现方法。3.栈和队列的应用。第三章字符串学习目标1.掌握字符串的概念、存储表示、基本运算。2.掌握字符串的模式匹配算法。重点难点1.字符串的存储结构和类定义。2.字符串的各种运算函数。3.字符串的匹配算法，如KMP的模式匹配算法。第四章二叉树学习目标1.理解二叉树的主要概念与相关性质。2.掌握二叉树的抽象数据类型、存储表示与实现效率。3.熟练掌握二叉树的遍历策略。4.掌握穿线树的概念和中序周游穿线二叉树的方法。5.掌握二叉搜索树及其应用。6.理解堆的概念、性质，重点掌握堆的构造。7.理解Huffman树的主要

3、思想与具体应用。重点难点1.二叉树的各种存储方法及效率分析。2.二叉树的遍历策略。3.堆的建立与Huffman编码树的基本思想。4.二叉树的非递归遍历算法。5.线索二叉树的建立和遍历算法。.第五章树学习目标1.理解树和森林的基本概念。2.掌握树与二叉树的联系、区别与转换。3.掌握树的链式存储方法，重点掌握“左子结点/右兄弟结点”二叉链表和父指针表示法，理解各种算法的优缺点。4.掌握树的顺序存储方法。5.理解K叉树的概念和性质。重点难点1.掌握树与二叉树的联系、区别与转换。2.掌握树的链式存储方法和顺序存储方法，及

4、各自的优缺点。第六章图学习目标1.理解并掌握图的基本概念。2.能写出图的抽象数据类型。3.理解图的各种存储结构，并能设计基于图的存储结构的算法。4.重点掌握图的周游、最短路径和最小支撑树的相关算法。5.了解图的相关知识。重点难点1.图的存储结构以及各种存储结构的优缺点。2.图的周游算法。3.解决图的最短路径问题的各种算法。4.图的最小支撑树的两种典型算法：Prim算法和Kruskal算法。第七章内排序学习目标1.理解内排序的基本概念，熟练掌握各种主要排序算法。2.能比较各种排序算法的优缺点，比较他们在最坏、最好、

5、平均情况下的复杂度。3.能够根据不同的实际情况，选择最合适的排序算法。4.能够判断排序算法是否稳定。5.对各种排序算法，能够画出它的判定树。重点难点1.各种排序算法的实现2.shell排序，快速排序，归并排序，堆排序的算法主要思想，缺点，瓶颈3.各种排序算法的复杂性比较第八章文件管理和外排序学习目标1.理解为什么需要研究外排序算法。2.理解磁盘访问的步骤和磁盘访问时间的估算。3.理解文件在外存储器中的组织方式。4.掌握缓冲区替换的3种策略。5.重点掌握置换选择排序和多路归并算法。重点难点1.磁盘访问时间的估算。2

6、.2、3种缓冲区替换策略。3.置换选择算法和多路归并算法。第九章检索学习目标1.理解检索的基本概念，熟练掌握各种主要检索算法。2.能根据概率知识衡量检索算法的效率，理解各种算法的优缺点。3.理解分治算法的思想，会设计一般的分治算法。4.重点掌握基于散列的检索算法，掌握各种散列函数、散列探查方法。5.了解集合检索相关知识。重点难点1.衡量检索算法的效率，评价各种算法的优缺点。2.分治算法的思想3.基于散列的检索算法，各种散列函数、散列探查方法。第十章索引技术学习目标1.了解索引的基本概念，如主码、辅码、索引等。2.

7、了解索引技术的简单分类。3.掌握线性索引的概念和特点。4.重点掌握B树和B+树的概念、插入和删除操作。重点难点1.线性索引的检索，尤其带有二级索引的检索，以及线性索引的缺点2.B树和B+树的插入和删除操作第十一章高级线性结构学习目标1.掌握高级线性结构的概念。2.掌握多维数组的概念、存储表示、基本运算。3.掌握广义表的概念、存储表示、基本运算。4.掌握存储管理技术。重点难点1.特殊矩阵和稀疏矩阵的运算。2.广义表的存储结构和周游算法。第十二章高级树结构学习目标1.理解Trie树结构和Patricia树结构原理及其

8、应用。2.理解二叉搜索树的几个变体，掌握平衡的二叉搜索树的几种变换。3.掌握k-d树和PR四分树的变换。4.理解R*树结构。5.理解决策树和博弈树及其应用。重点难点1.Trie树和Patricia树的原理及应用。2.平衡的二叉搜索树及其各种变换。3.决策树和博弈树的原理。习题：1(1,2,3);2(1,5,8,10,19);3(1,2);4(5,11,15,19);5(3