《数据结构》考试大纲.docx

《《数据结构》考试大纲.docx》由会员分享，可在线阅读，更多相关《《数据结构》考试大纲.docx（3页珍藏版）》请在优知文库上搜索。

1、数据结构考试大纲一、考试科目：数据结构二、适用专业：计算机科学与技术专业，计算机技术，软件工程三、参考书目：数据结构（C语言版），严蔚敏，清华大学出版社，2007四、考试内容要求1、了解数据结构及其分类、数据结构与算法的密切关系。2、熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。3、掌握设计算法的步骤和算法分析方法。4、掌握数据结构在排序和查找等常用算法中的应用。5、初步掌握文件组织方法和索引技术。五、考试内容：1、数据结构基本概念及简单的算法分析1）什么是数据结构2）抽象数据类型及面向对象概念：数据类型；数据抽象与抽象数据类型；面向对象的概念；用于描述数据结构的语言3）数

2、据结构的抽象层次4）算法定义5）性能分析与度量：算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；渐进的空间复杂.2、数组D作为抽象数据类型的数组：数组的定义和初始化；作为抽象数据类型的数组；数组的顺序存储方式2）顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查找、插入和删除；使用顺序表的事例3）字符串：字符串的抽象数据类型；字符串操作的实现；字符串的模式匹配3、链表1）单链表：单链表的结构；单链表的类定义；单链表中的插入与删除；带表头结点的单链表；用模板定义的单链表类；单链表的游标类；静态链表2）循环链表：循环链表的类定义；用循环链

3、表解约瑟夫问题；多项式及其相加：多项式的类定义；多项式的加法3）双向链表4、栈和队列1）栈：栈的抽象数据类型；栈的顺序存储表示；栈的链接存储表示2）队列：队列的抽象数据类型；队列的顺序存储表示；队列的链接存储表示；3）队列的应用举例4）优先级队列：优先级队列的定义；优先级队列的存储表示5、递归1）递归的概念2）迷宫问题3）递归过程与递归工作栈4）利用栈实现的迷宫问题非递归解法5）广义表：广义表的概念；广义表的表示及操作；广义表存储结构的实现；广6）义表的访问算法；广义表的递归算法6、树与森林D树和森林的概念：树的定义；树的术语；树的抽象数据类型2）二叉树：二叉树的定义；二叉树的性质；二叉树的抽

4、象数据类型3）二叉树的表示：数组表示；链表存储表示4）二叉树遍历：中序遍历；前序遍历；后序遍历；应用二叉树遍历的事例；二叉树遍历的游标类；不用栈的二叉树中序遍历算法5）线索化二叉树：线索；中序线索化二叉树；前序与后序的线索化6）堆：堆的定义；堆的建立；堆的插入与删除7）树与森林：树的存储表示；森林与二叉树的转换；树的遍历；森林的遍历二叉树的计数8）霍夫曼树：路径长度；霍夫曼树；霍夫曼编码7、集合与搜索D集合及其表示：集合基本概念；以集合为基础的抽象数据类型；用位向量实现集合抽象据类型；用有序链表实现集合的抽象数据类型2）等价类：等价关系与等价类；确定等价类的链表方法；并查集3）简单的搜索结构：

5、搜索的概念；静态搜索结构；顺序搜索；基于有序顺序表的对分搜索4）二叉搜索树：定义；二叉搜索树上的搜索；二叉搜索树的插入；二叉搜索树的删除;与二叉搜索树相关的中序游标类5）AVl树：AVl树的定义；平衡化旋转；AVl树的插入和删除；AVl树的高度8、图D图的基本概念：图的基本概念；图的抽象数据类型2）图的存储表示：邻接矩阵；邻接表；邻接多重表3）图的遍历与连通性：深度优先搜索；广度优先搜索；连通分量；重连通分量4）最小生成树：克鲁斯卡尔算法；普里姆算法5）活动网络：用顶点表示活动的网络；用边表示活动的网络9、排序D插入排序：直接插入排序；对分插入排序；链表插入排序；希尔排序2）交换排序：起泡排序；快速排序3）选择排序：直接选择排序；锦标赛排序；堆排序4）归并排序：归并；迭代的归并排序算法；递归的表归并排序5）基数排序：多关键码排序；链式基数排序6）外排序：外排序的基本过程；k路平衡归并；初始归并段的生成；最佳归并树10、索引与散列结构D静态索引结构：线性索引；倒排表；m路静态查找树2）动态索引结构：动态的m路查找树；bj;b_树的插入；b_树的删除；b+树3）散列：词典的抽象数据类型；散列表与散列方法；散列函数；处理溢出的闭散列方法；处理溢出的开散列方法；散列表分析