数据结构课程内容与典型题型分析

《数据结构课程内容与典型题型分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、江西省高等学校精品课程数据结构课程内容与典型题型分析《数据结构》课程组江西师范大学计算机信息工程学院www.jxnucie.com/course/index.asp课程主要内容——考核大纲《数据结构》课程组江西师范大学计算机信息工程学院第1章概论1、数据结构定义2、数据的逻辑结构与存储结构分类3、算法的时间复杂度与空间复杂度分析,大O记法。第2章线性表及其顺序存储1、了解线性结构的特点2、顺序表定义3、栈的特点4、栈的顺序实现5、了解中缀表达式转后缀表达式的方法6、队列的特点7、队列的顺序实现方法8、循环队列（重点）9、掌握基于顺序表的基本操作实现方法10、基于顺

2、序表的综合算法如：¾顺序表倒置¾顺序表查找¾有序表合并第3章线性表的链式存储1、单链表的插入、删除、查找运算注意区分带头结点与不带头结点的单链表2、链式栈的进出栈操作3、链式队列的进出队操作4、循环链表的特点5、双链表的插入与删除6、单链表的插入、删除、查找的综合应用，掌握基于单链表的算法设计（程序设计与编程）例如：¾单链表的遍历¾查找单链表中指定结点¾单链表倒置¾删除单链表中某类结点¾单链表排序¾有序单链表合并第4章字符串、数组和特殊矩阵1、了解字符串的存储方法顺序存储（顺序表）链式存储（链表）2、了解字符串基本操作的实现本质是线性表的编程3、了解朴素的模式匹配

3、算法思想*4、了解快速模式匹配算法（next[]求法）5、了解二维数组的线性存储6、了解特殊矩阵的压缩存储7、了解稀疏矩阵的三元组存储及其快速转置思想第5章递归1、掌握递归程序的执行情况分析2、掌握简单递归程序设计方法3、了解递归程序到非递归程序的转换方法递推与栈4、掌握基于线性表与二叉树的常用递归程序的编写方法。第6章树型结构1、树型结构的特点2、树的表示方法3、树的存储结构P123双亲表示法、孩子表示法、孩子兄弟表示法要求：给定一树，能够画出以上三种表示法。4、树的遍历前序遍历、后序遍历、层次遍历要求：写出结果，掌握递归程序，层次非递归P130第7章二叉树1、

4、二叉树的基本概念（对比与树的区别）二叉树是有序树，而二度树可能是无序树，也可能是有序树；二叉树的度可以是0、1、2，而二度树的度只能是2；二叉树可以使空树，二度树不能是空树。2、掌握二叉树的4个性质P1383、二叉树的存储结构定义4、掌握二叉树的遍历方法前序遍历特点，中序遍历特点，后序遍历特点要求：（1）给定二叉树，写出遍历结果；（2）根据中序与前序，画出二叉树；根据中序与后序，画出二叉树。（3）熟练掌握三种遍历的递归与非递归程序4、掌握基于二叉树的递归程序例：二叉树的高度；二叉树叶子结点个数；二叉树结点个数；5、掌握穿线二叉树的定义能够画出一棵二叉树的中序穿线二

5、叉树；画出一棵树的后序穿线二叉树；画出一棵二叉树的前序穿线二叉树；能够查找穿线树中的前驱与后续结点。6、树、森林和二叉树的转换要求：能够画出树（森林）转换二叉树的结果；画出二叉树转换成树（森林）的结果。第8章图1、图的基本概念有向图，无向图，度，入度，出度，度与边的关系，连通分量，强连通分量2、图的存储结构要求：给定一个图，能画出它的三种存储结构3、图的遍历要求：写出BFS与DFS遍历结果，掌握种遍历程序。4、掌握PRIM与KRUSKAL算法求解最小生成树的过程。5、掌握单源最短路径求解步骤。6、掌握任意顶点对之间的最短路径求解方法。7、掌握拓扑排序的方法（写出结

6、果）第9章检索1、了解检索算法效率的评价2、掌握顺序检索、二分检索算法（效率分析）3、了解分块检索思想4、二叉排序树（重点）¾二叉排序树定义；¾二叉排序树查找算法（递归与非递归）¾二叉排序树结点插入运算算法（递归与非递归）¾二叉排序树结点的删除方法（写出结果）5、平衡二叉排序树(AVL)的概念*6、平衡二叉排序树调整方法7、掌握Huffman树的建立，Huffman的编码方法8、散列存储了解常见的散列函数了解解决冲突的方法第10章内排序1、掌握插入排序的基本思想2、掌握选择排序的基本思想3、掌握交换排序的基本思想4、掌握归并排序的基本思想5、直接插入排序、折半插入

7、排序、希尔排序掌握算法程序，过程，时间复杂度，稳定性6、掌握简单选择排序算法程序，时间复杂度，稳定性；过程；7、堆排序（重点）掌握小根堆（最小堆），大根堆（最大堆）建立的过程；掌握算法程序；稳定性，时间复杂度8、冒泡排序掌握算法程序；时间复杂度，稳定性；过程；9、快速排序（重点）一次划分的过程；掌握快速排序程序；时间复杂度；10、理解归并排序思想，了解时间复杂度，空间复杂度。11、了解基数排序思想。数据结构题型解析《数据结构》课程组江西师范大学计算机信息工程学院一、选择题：1、下面哪个术语与数据的存储结构无关（）（A）顺序表（B）链表（C）散列表（D）队列2、算法

8、的每一步，