数据结构研究生入学考试学习大纲

《数据结构研究生入学考试学习大纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》研究生入学考试学习大纲一、课程的地位与作用《数据结构》课程是计算机专业的核心课程之一，是一门综合性的专业基础课，它介于数学，计算机硬件，计算机软件之间。是高级程序设计语言，编译原理，操作系统，数据库，人工智能等课程的基础。同时，数据结构的技术也广泛应用于信息科学、系统工程，应用数学，以及各种工程技术领域。二、课程的教学目标与基本要求课程目的是使学生了解计算机应用中数据对象的特性，学会在应用中,根据现实世界中的问题选择适当的数据逻辑结构和存储结构以及相应算法,并且培养基本的、良好的程序设计技能。三、课程内容（重点△，难点★）1绪论1．1数据结构的有关概念1．

2、2数据结构发展概况1．3△关于算法及算法的分析1．3．1算法1．3．2算法设计要求1．3．3★时间复杂度2线性表2.1线性表的逻辑结构2.2△线性表的顺序存储结构及运算实现2.3△线性表的链式存储结构及运算2.3.1线性链表2.3.2循环链表2.3.3双向链表2.3.4静态链表2.4★一元多项式的表示及相加3栈和队列3．1栈的定义及运算3．2△栈的存储结构及运算实现3．3栈应用举例3．4队的定义及运算3．5△队的存储结构及运算实现3．5．1队的链式存储和运算3．5．2循环队---队的顺序存储和运算·18·4数组4．1数组的定义4．2★稀疏矩阵的三元组表示及有关算

3、法4．3稀疏矩阵的十字链表表示及相加5树和二叉树5．1树的定义及有关术语5．2△二叉树5．2．1二叉树的定义5．2．2二叉树的性质5．2．3二叉树的存储结构5．3△二叉树的遍历算法及线索二叉树5．3．1二叉树的遍历5．3．2★线索二叉树5．4树和森林5．4．1树的存储结构5．4．2森林与二叉树的转换5．4．3树和森林的遍历5．5哈夫曼树及其应用5．5．1哈夫曼树5．5．2哈夫曼编码6图6．1图的定义及逻辑结构、存储方法6．2△图的遍历算法6．2．1图的深度优先搜索6．2．2图的广度优先搜索6．3△无向图的连通性6．3．1无向图的连通分量6．3．2无向图的生成树6．3

4、．3★最小生成树6．4△有向无环图及其应用6．4．1拓扑排序;6．4．2★关键路径6．5△★单源点最短路径7查找7．1△静态查找表7．1．1顺序表的查找·18·7．1．2有序表的折半查找7．1．3索引顺序表的查找7．2△动态查找表7．2．1二叉排序树7．2．2★平衡二叉树7．2．3★B-树7．3△哈希表7.3.1哈希表的定义7.3.2哈希函数7.3.3冲突处理方法7.3.4哈希表的查找8△内部排序8．1排序的概念8．2插入排序8．2．1直接插入排序8．2．2插入排序8．2．3希尔排序8．3快速排序8．4选择排序8．4．1简单选择排序8．4．2堆排序8．5各种内部

5、排序方法的比较四、时间分配课程分段标识序号教学内容教学环节（学时）讲课习题实验上机课外小计1绪论222线性表5373栈和队列474数组445树和二叉树7310·18·6图777查找7278内部排序44910111213141516171819202122232425262728总计40848五、课程说明课程英文名称DataStructure主要先修课程C++程序设计适用专业类别计算机科学与技术主要教材（作者、教材名称、出版社）“数据结构”严蔚敏、吴伟民清华大学出版社考核方式考试·18·课程简介各种类型的数据结构和查找，排序的各种方法必开实验项目序号项目名称学时1线性表

6、链式存储结构的应用32二叉树23Hash表应用245678·18·《计算机组成原理》研究生入学考试学习大纲一、课程的地位与作用本课是计算机专业的核心主干课之一，也是学习计算机的其它后续课（如微机系统与接口、计算机系统结构、操作系统等）的重要的专业基础课。它在先导与后续课程之间起着承上启下和继往开来的作用。也是从事计算机设计、开发、应用与维护等工作的基础。二、课程的教学目标与基本要求本课程主要讨论计算机单机系统的组成原理及其内部工作机制，包括各大部件的工作原理、逻辑实现、设计方法及其互连构成整机的技术。主要强调计算机的基本原理、基本知识和基本技巧的训练。通过学习，学生掌握

7、计算机硬件的设计与分析方法，建立整机工作概念。三、课程内容（重点△，难点★）1概论1.1计算机的发展历史1.1.1计算机硬件—更新换代1.1.2计算机软件—日臻完善1.2△计算机系统的硬件组成1.2.1计算机的功能部件1.2.2冯·诺依曼计算机1.3计算机的软件系统1.3.1系统软件1.3.2应用软件1.4计算机系统的组织结构1.4.1硬件与软件的关系1.4.2计算机系统的多级层次结构1.4.3计算机硬件系统的组织1.5计算机的特点和性能指标1.5.1计算机的工作特点1.5.2计算机的性能指标1.6计算机的分类与应用1.6.1计算机的分类