|
|
2008年硕士研究生入学考试数据结构复习重点
参考书目：金远平编著，《数据结构（C++描述）》，清华大学出版社
第1章
基本概念和方法
数据结构与软件系统，数据抽象与封装，递归算法，性能分析，时间复杂性，O表示法，性能测量。
第2章 线性表
线性表与数组，字符串模式匹配的简单算法，KMP算法，失败函数f的计算，栈，队列。
第3章
链表
单链表，单链表的表示，链表操作，环链表，双链表，广义表，广义表的概念及表示，广义表的递归算法。
第4章
树
树和森林的概念及其表示，二叉树，二叉树性质，二叉树表示，二叉树遍历， LVR, LRV, VLR，选择树，胜者树，败者树，集合表示，并查集。
第5章
堆结构
最大堆（最小堆情况对称，也应该掌握），优先队列与最大堆，插入操作，删除操作。
第6章
图
图的表示，邻接矩阵，邻接表，邻接多表，连通图的遍历，最小代价生成树，克鲁斯卡尔算法，最短路径和传递闭包，AOV网络，AOE网络。
第7章
排序
插入排序，快速排序，归并排序，堆排序。
第8章
查找结构
二叉查找树，AVL树，高度平衡，AVL树的插入算法，AVL树的时间复杂性分析，m叉查找树，m叉查找树的查找，B树的定义和性质，B树的插入操作，B树的删除操作。
《计算机操作系统原理》课程
考试大纲
一、课程基本情况
授课对象：计算机专业本科
讲课学时：64
实验学时：16
教材名称：实用操作系统概念（西尔伯莎茨编著 英文版） 高教出版社
2000
现代操作体统教程（滕至阳编著） 高教出版社
2000
二、课程地位、作用及任务
地位：是计算机专业的主干课程。该课程下接计算机硬件结构，上接多种实用软件和应用软件，包括数据库系统、网络与分布式系统。课程中提出的若干概念如进程、线程、虚拟、同步与互斥等是计算机科学与技术领域中最重要的基础性概念。可见该课程的地位是非常重要的。
作用：课程的内容不仅使学生具备实际操纵计算机的能力，而且培养学生在操作系统平台上二次开发能力。
任务：使学生了解和掌握现代操作系统中的基本概念和操作系统本身采用的主要实现技术，为今后参与计算机科学研究打好基础。
三、考试目的、内容及方法
目的：检查学生对操作系统基本概念的掌握情况，特别是了解学生利用基本概念阐明实际问题的能力，以及利用已学过的某些技术手段如何编写同步、互斥、通信等具备操作系统明显特征的程序段落的能力。
内容：考试内容分基础部分和提高部分。基本部分是必须掌握的，提高部分要求学生在理解的基础上有某种程度的应用。
●
基本部分包括如下内容：
1．
引言部分（OS定义、功能、特征、类型、启动过程）
2．
作业管理（用户界面，系统调用，批处理，Spooling，作业调度）
3．
存储管理（虚存，地址变换，请求页式，页面置换算法）
4．
进程管理（进程定义、状态及变迁，PCB，同步与互斥，PV操作，进程间通信
各算法，死锁概念，优先级抢夺调度）
5．
线程管理（线程概念、状态，多线程实例）
6．
文件管理（文件概念，卷，目录，i结点，逻辑/物理地址，文件表）
7．
设备管理（特别文件，I/O进程，设备入口表，字符/块设备驱动）
●
提高部分包括如下内容：
8．
并发程序设计（进程/子进程，并发PASCAL，CSP）
9．
操作系统的设计与实现（设计方法，实现语言）
10．
多处理操作系统，网络/分布式操作系统，操作系统的安全机制
方法：紧扣课程内容，以基本部分为主。试题类型一般为：概念题，简答题、计算题、编程题。 |
|
IP卡
狗仔卡
发表于 2007-11-13 09:42:54
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
楼主
发表于 2007-12-7 19:45:31
