清华大学公布的代码谁看得懂！！关于数据结构的预插值方法

时间:2006年8月-65438+6月时间阅读:447

数据结构与操作系统——复旦大学2007年研究生入学考试大纲

复旦大学2007年招收研究生。

数据结构与操作系统专业课程考试大纲

第一部分数据结构

试题:简答题、编程题

参考书目:《数据结构》(用面向对象方法C++描述)尹仁坤，清华大学出版社。

总分:100分

考试的基本要求

要求考生系统了解数据结构的基本概念和理论，掌握各种数据结构的特点和基本方法，强调考生应具备综合运用所学知识分析和解决问题的能力。

对编程语言的要求

数据结构测试中的所有算法都要求用C或C++语言描述。

一.阵列

考试内容

数据；序列表；字符串匹配。

考试要求

1.了解数组的存储结构，掌握顺序存储情况下数组元素与存储单元的对应关系。

2.了解序列表的结构和特点，掌握序列表上基本操作的实现算法。

3.掌握字符串比较的基本算法(包括KMP算法)。

4.具备用数组结构解决实际问题的能力。

第二，链表

考试内容

单链表；双向链表；循环链表；稀疏矩阵。

考试要求

1.了解单链表、双链表、循环链表的存储结构和特点，掌握其基本操作的实现算法。

2.了解稀疏矩阵的存储结构和特点，掌握稀疏矩阵基本运算的实现算法。

3.具备用链表结构解决实际问题(如用链表实现的多项式运算)的能力。

第三，堆栈和队列

考试内容

堆栈；排队。

考试要求

1.了解栈的定义和结构特征，掌握其存储方式(顺序存储和链接存储)和基本操作的实现算法。

2.了解队列的结构和特点，掌握其存储方式(顺序存储和链接存储)和基本操作的实现算法。

3.用队列和栈结构解决实际问题(如表达式计算、优先级队列)的能力。

第四，递归

考试内容

递归。

考试要求

1.了解递归的基本概念和实现原理，掌握用递归描述问题和编写算法的方法。

2.掌握汉诺塔和迷宫等问题的递归解法。

3.用栈掌握递归问题的非递归解法。

动词 （verb的缩写）树木和森林

考试内容

树，二叉树，森林，堆。

考试要求

1.了解树的结构，掌握树的主要概念。

2.了解各种二叉树的结构，掌握它们的特点，有运用二叉树解决实际问题的能力。

3.掌握二叉树的三种遍历方法的原理和性质，应用二叉树的遍历方法解决二叉树的叶节点数和计数等问题，掌握遍历的非递归实现方法。

4.掌握线索二叉树的结构和基本操作。

5.了解堆的原理，掌握基本操作的实现方法。

6.了解树和森林的定义和存储结构，掌握树和森林的遍历等方法的实现。

7.了解霍夫曼编码的基本原理，掌握基于霍夫曼树生成霍夫曼编码的方法。

不及物动词收集和搜索

考试内容

组装；等价类；静态搜索结构；二叉查找树；最佳二叉查找树；AVL树。

考试要求

1.了解集合的基本概念，掌握集合的各种存储方法。

2.掌握等价类的生成算法。

3.掌握有序表的对折搜索、斐波那契等搜索方法。

4.了解AVL树的定义和特点，掌握AVL树调整操作的实现原理。

5.掌握最优二叉树的构造原理和相关算法。

七。数字

考试内容

图；连通分量；最小图；最短路径；活跃的网络。

考试要求

1.了解与图形相关的各种基本概念，掌握图形的各种存储方法。

2.掌握图的两种搜索方法和连通分量的生成方法。

3.掌握生成最小生成树的两种方法。

4.掌握各种求最短路径的方法。

5.掌握用顶点表示活动和用边表示活动两种网络结构的特点，以及相关操作的实现算法。

八、排序

考试内容

插入排序；交换排序；选择排序；合并排序；基数排序；外部排序。

考试要求

了解各种排序方法的实现，掌握各种排序算法的时间复杂度和特点，能够横向比较。

九。索引结构和散列

考试内容

静态索引结构；动态索引结构；哈希。

考试要求

1.了解线性索引结构、倒排表和静态搜索树的结构和特点。

2.了解B树的结构，掌握各种运算的实现算法。

3.了解哈希的实现原理，掌握各种运算的实现算法。

操作系统的第二部分

考试内容包括流程、存储管理、输入输出和文件系统四个基本组件的设计原理和实现方法。内容还涉及分布式操作系统、集群系统、操作系统安全的基础知识。

要求考生系统理解和掌握操作系统的基本概念、主要功能、主要组件以及各主要组件的不同实现方法；从资源管理和应用程序与硬件系统接口的角度掌握操作系统设计的基本思想，掌握现代计算机系统对各种软硬资源的管理技术。要求考生具备综合运用所学知识分析和解决问题的能力。

试题:填空题和选择题，解题和计算题。

参考书目:William Stalling S .操作系统:内部和设计原则。第四版，Prentice Hall.2001。

总分:50分

考试内容和要求的细节

一、操作系统概述

考试内容

1.计算机的基本结构，处理器的内部结构，缓存；记忆；

2.操作系统的概念、演变、特征、分类、运行环境和功能。

3.记忆的层次结构

考试要求

1.复习计算机的基本原理，了解操作系统所管辖的软硬件资源；

2.了解操作系统的关键概念，从整体上把握操作系统的特点和功能；

3.对记忆的层次结构进行案例研究。

4.建立操作系统的资源管理和应用程序接口的功能概念。

第二，流程

考试内容

过程、过程描述和过程状态转换

考试要求

抓住流程的本质特征，明确流程的动态特征，熟悉流程状态之间转换的原因，建立流程是资源分配单元和运行实体的基本概念。

线程、对称多处理SMP和微内核

考试内容

1.线程的概念定义了线程的必要性和可能性；

2.线程的功能特征和实现；

3.对称多处理SMP体系结构:

4.操作系统的体系结构(微内核和单片内核)及其性能分析。

考试要求

1.理解引入线程作为基本运行实体的必要性和可能性；

2.掌握线程的各种实现方法和特点；

3.熟悉SMP架构和操作系统架构(微内核和单片内核)。

第四，并发

考试内容

1.并发及相关概念，如临界区、互斥、信号量和管道等。

2.进程互斥、同步和通信的各种算法；

3.死锁的概念、原因和条件。

4.死锁预防、避免和检测算法。

考试要求

1.可以使用信号量、管道等技术解决互斥契约步骤的问题；

2.理解死锁的概念和死锁的充要条件；

3.掌握死锁预防、避免和检测算法；

4.了解在处理死锁时如何避免饥饿。

动词 （verb的缩写）内存管理

考试内容

1.分区存储管理、覆盖和交换；

2.页面管理和段管理；

3.段和页存储的管理方法和实现技术；

4.虚拟内存的原理以及相关的算法和数据结构。

考试要求

1.了解存储管理的功能及其对多道程序设计的支持；

2.掌握段和页存储的管理方法和实现技术；

3.重点掌握虚拟内存的原理以及相关的算法和数据结构。

六、单处理器调度

考试内容

1.处理器的三种调度类型；

2.进程调度的各种算法及其特点。

考试要求

1.了解三种调度类型:远程、中程和短程；

2.重点掌握进程调度的各种算法及其适用环境。

七、多处理器调度和实时调度

考试内容

1.多处理器对进程调度的影响

2.多处理器环境下的进程和线程调度算法:

3.实时过程的特征；

4.截止期调度和单调速率调度方法。

考试要求

1.理解调度粒度的概念；

2.熟悉多处理器环境下的进程和线程调度算法；

3.了解实时过程的本质，掌握截止期调度和单调速率调度的方法。

八、设备管理和磁盘调度

考试内容

1.操作系统中输入输出功能的组织；

2.中断处理；

3.设备驱动程序、独立于设备的软件接口和假脱机技术；

4.缓冲策略；

5.磁盘调度算法；

6.磁盘阵列。

考试要求

1.了解输入输出设备和操作系统中输入输出功能的组织；

2.掌握中断处理、设备驱动程序、设备独立软件接口和假脱机技术；

3.重点掌握用于提升性能的各种缓冲策略和磁盘调度算法；

4.了解可以提高性能和可靠性的各种磁盘阵列配置。

九、文件系统

考试内容

1.文件系统特征和文件组织；

2.文件系统的数据结构；

3.目录的基本性质及其实现方法；

4.磁盘空间的管理。

考试要求

1.了解文件系统特征和文件组织；

2.掌握文件系统的基本数据结构；

3.了解文件和目录的基本性质及其实现方法；

4.重点研究了磁盘空间的管理、文件系统的性能和可靠性、文件系统的安全和保护机制。

X.分布式的计算机系统

考试内容

1.分布式处理的特征和类型；

2.多层体系结构和中间件技术；

3.集群系统；

4.与分布式进程管理相关的操作系统设计问题。

考试要求

1.了解分布式处理的特点和类型；

2.掌握多层架构、中间件技术和集群系统的基本概念和特点；

3.重点研究进程迁移、分布式全局状态的识别、分布式互斥和死锁预防。

XI。可信计算机系统

考试内容

1.计算机系统面临的安全问题及其应对机制:

2.可信系统的基本概念。

考试要求

1.了解计算机系统面临的安全问题及其应对机制；

2.掌握计算机安全设计的一种综合方法——可信系统。

最近怎么样？值得参考啊