研究生入学考试《数据结构》考试大纲
一、考试科目：数据结构考试科目二、适用专业：计算机科学与技术专业适用专业三、参考书目：参考书目：数据结构（第二版），陈明主编，2008，清华大学出版社。四、考试内容要求1、了解数据结构及其分类、数据结构与算法的密切关系。2、熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。3、掌握设计算法的步骤和算法分析方法。4、掌握数据结构在排序和查找等常用算法中的应用。5、初步掌握文件组织方法和索引技术。
五、试卷结构：试卷结构试题总分150分，试题类型及试卷结构包括：选择题（20分）；问答题（30）；计算题（40）综合应用题（60分）。六、考试内容：考试内容：1、数据结构基本概念及简单的算法分析1什么是数据结构2抽象数据类型及面向对象概念：数据类型；数据抽象与抽象数据类型；面向对象的概念；用于描述数据结构的语言3数据结构的抽象层次4算法定义5性能分析与度量：算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；渐进的空间复杂
2、数组
1作为抽象数据类型的数组：数组的定义和初始化；作为抽象数据类型的数组；数组的顺序存储方式2顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查找、插入和删除；使用顺序表的事例3字符串：字符串的抽象数据类型；字符串操作的实现；字符串的模式匹配
3、链表
1单链表：单链表的结构；单链表的类定义；单链表中的插入与删除；带表头结点的单链表；用模板定义的单链表类；单链表的游标类；静态链表2循环链表：循环链表的类定义；用循环链表解约瑟夫问题；多项式及其相加：多项式的类定义；多项式的加法3双向链表
f4、栈和队列1栈：栈的抽象数据类型；栈的顺序存储表示；栈的链接存储表示2队列：队列的抽象数据类型；队列的顺序存储表示；队列的链接存储表示；3队列的应用举例4优先级队列：优先级队列的定义；优先级队列的存储表示
5、递归
1递归的概念2迷宫问题3递归过程与递归工作栈4利用栈实现的迷宫问题非递归解法5广义表：广义表的概念；广义表的表示及操作；广义表存储结构的实现；广6义表的访问算法；广义表的递归算法
6、树与森林
1树和森林的概念：树的定义；树的术语；树的抽象数据类型2二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型3二叉树的表示：数组表示；链表存储表示4二叉树遍r