《数据结构研究生入学考试学习大纲》由会员分享，可在线阅读，更多相关《数据结构研究生入学考试学习大纲（20页珍藏版）》请在金锄头文库上搜索。
1、数据结构研究生入学考试学习大纲摘要：1.2 数据结构发展概况 1.3关于算法及算法的分析 1.3.1算法. 2. 1 线性表的逻辑结构 2. 2 线性表的顺序存储结构及运算实现.关键词：数据结构,算法类别：专题技术来源：牛档搜索（Niudown.COM）本文系牛档搜索（Niudown.COM）根据用户的指令自动搜索的结果，文中内涉及到的资料均来自互联网，用于学习交流经验，作品其著作权归原作者所有。不代表牛档搜索（Niudown.COM）赞成本文的内容或立场，牛档搜索（Niudown.COM）不对其付相应的法律责任！18数据结构研究生入学考试学习大纲一、课程的地位与作用 数据结构课程是计算机专业
2、的核心课程之一，是一门综合性的专业基础课，它介于数学，计算机硬件，计算机软件之间。是高级程序设计语言，编译原理，操作系统，数据库，人工智能等课程的基础。同时，数据结构的技术也广泛应用于信息科学、系统工程，应用数学，以及各种工程技术领域。二、课程的教学目标与基本要求 课程目的是使学生了解计算机应用中数据对象的特性，学会在应用中, 根据现实世界中的问题选择适当的数据逻辑结构和存储结构以及相应算法, 并且培养基本的、良好的程序设计技能。三、课程内容（重点，难点）1 绪论 11 数据结构的有关概念 12 数据结构发展概况 13关于算法及算法的分析 131算法 132 算法设计要求 133 时间复杂度2
3、线性表 2. 1 线性表的逻辑结构 2. 2 线性表的顺序存储结构及运算实现 2. 3 线性表的链式存储结构及运算 2. 3. 1 线性链表 2. 3. 2 循环链表 2. 3. 3 双向链表 2. 3. 4 静态链表 2. 4 一元多项式的表示及相加3 栈和队列31 栈的定义及运算 32 栈的存储结构及运算实现 33栈应用举例 34 队的定义及运算 35 队的存储结构及运算实现 351 队的链式存储和运算 352 循环队-队的顺序存储和运算4 数组 41 数组的定义 42 稀疏矩阵的三元组表示及有关算法43 稀疏矩阵的十字链表表示及相加5 树和二叉树 51 树的定义及有关术语 52 二叉树
4、521 二叉树的定义 522 二叉树的性质 523 二叉树的存储结构 53 二叉树的遍历算法及线索二叉树 531 二叉树的遍历 532 线索二叉树 54 树和森林 541 树的存储结构 542森林与二叉树的转换 543树和森林的遍历 55 哈夫曼树及其应用 551 哈夫曼树 552 哈夫曼编码6 图 61 图的定义及逻辑结构、存储方法 62 图的遍历算法 621 图的深度优先搜索 622 图的广度优先搜索 63 无向图的连通性 631 无向图的连通分量 632 无向图的生成树 633 最小生成树 64 有向无环图及其应用 641 拓扑排序; 642 关键路径 65 单源点最短路径7 查找 71
5、 静态查找表 711 顺序表的查找 712 有序表的折半查找 713 索引顺序表的查找 72 动态查找表 721 二叉排序树 722 平衡二叉树 723 B-树 73 哈希表 7. 3. 1 哈希表的定义 7. 3. 2 哈希函数 7. 3. 3 冲突处理方法 7. 3. 4 哈希表的查找8 内部排序81 排序的概念 82 插入排序 821 直接插入排序 822 插入排序 823 希尔排序 83 快速排序 84 选择排序 841 简单选择排序 842 堆排序 85各种内部排序方法的比较 四、时间分配课程分段标识序号教 学 内 容教学环节（学时）讲课习题实验上机课外小计1绪论222线性表5373
6、栈和队列4 74数组445树和二叉树73106图777查找7278内部排序44910111213141516171819202122232425262728 总 计40848五、课程说明课程英文名称Data Structure主要先修课程C+程序设计适用专业类别计算机科学与技术主要教材（作者、教材名称、出版社）“数据结构” 严蔚敏、吴伟民 清华大学出版社 考核方式考试课程简介各种类型的数据结构和查找，排序的各种方法必 开实 验项 目序号项 目 名 称学时1线性表链式存储结构的应用32二叉树23Hash表应用24 5678计算机组成原理研究生入学考试学习大纲一、课程的地位与作用本课是计算机专业的
7、核心主干课之一，也是学习计算机的其它后续课（如微机系统与接口、计算机系统结构、操作系统等）的重要的专业基础课。它在先导与后续课程之间起着承上启下和继往开来的作用。也是从事计算机设计、开发、应用与维护等工作的基础。二、课程的教学目标与基本要求本课程主要讨论计算机单机系统的组成原理及其内部工作机制，包括各大部件的工作原理、逻辑实现、设计方法及其互连构成整机的技术。主要强调计算机的基本原理、基本知识和基本技巧的训练。通过学习，学生掌握计算机硬件的设计与分析方法，建立整机工作概念。三、课程内容（重点，难点）1 概 论1.1 计算机的发展历史1.1.1 计算机硬件更新换代 1.1.2 计算机软件日臻完善
8、 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 计算机的分类 1.6.2 计算机的应用 2 计算机中数据信息的表示 2.1 进位计数制与数制转换 2.2 带符号数的表示 2.2.1 机器数与真值 2.2.2 原码表示 2.2
9、.3 补码表示 2.2.4 反码表示 2.2.5 移码表示 2.3 数的定点表示与浮点表示 2.3.1 定点表示 2.3.2 浮点表示 2.3.3 定点表示与浮点表示的比较 2.4 非数值型数据的表示 2.4.1 逻辑数二进制串 2.4.2 字符与字符串 2.4.3 汉字信息的表示 2.5 十进制数串的表示 2.6 数据校验码 2.6.1 码距与数据校验码 2.6.2 奇偶校验码 2.6.3 海明校验码 2.6.4 循环冗余校验码 3 运算方法与运算器 3.1 运算器的设计方法 3.2 定点补码加减运算 3.2.1 补码加减运算的基础 3.2.2 溢出判断与变形补码 3.2.3 算术逻辑运算部
10、件 3.3定点乘法运算 3.3.1原码乘法运算 3.3.2补码乘法运算 3.3.3快速乘法运算 3.4定点除法运算 3.4.1原码除法运算 3.4.2补码除法运算 3.4.3快速除法运算方法 3.5浮点四则运算 3.5.1 浮点加减运算 3.5.2 浮点乘除运算 3.6运算器的组成 3.6.1 定点运算器 3.6.2 浮点运算器 3.7十进制数的加减运算方法 3.7.1 一位十进制加法器的设计 3.7.2 多位十进制整数的加减运算 3.8逻辑运算和移位操作 3.8.1 逻辑运算 3.8.2 移位操作 4 存储器系统 4.1存储器概述 4.1.1存储器的分类 4.1.2主存储器的组成和基本操作 4.1.3存储器的主要技术指标 4.1.4存储器系统的层次结构 4.2半导体存储器 4.2.1半导体存储器的分类 4.2.2随机存取存储器的结构及工作原理 4.2.3只读存储器的结构及工作原理 4.2.4半导体存储器的组成 4.3辅助存储器 4.3.1磁表面存储器的基本原理 4.3.2磁记录方式 4.3.3磁盘存储器 4.3.4光盘存储器 4.4高速缓冲存储器（Cache） 4.4.1 Cache在存储体系中的地位和作用 4.4.2 Cache的结构及工作原理 4.5并行存储系统 4.5.1单体多字并行主存系统 4.5.2多体交叉存取方式的并行主存系统
