浙江大学2004年软件工程硕士数据结构入学考试大纲

　　（一） 算法和算法分析

　　1. 算法的概念

　　2. 算法效率的度量：时-空复杂度分析

　　（二）数组结构

　　1. 多项式的数组表示

　　2. 稀疏矩阵的数组表示

　　（三）栈与队列

　　1. 栈与队列的数组表示

　　2. 栈的应用：

　　（1）数制转换；（2）括号匹配；（3）迷宫；（4）表达式求值。

　　（四）线性链表

　　1. 单链表的表示与实现

　　2. 栈与队列的动态链接表示

　　3. 多项式的链表表示与循环链表

　　（五）树

　　1. 树的定义与表示方法

　　2. 二叉树的定义与基本性质

　　3. 遍历二叉树和线索二叉树

　　4. 堆的定义与性质

　　5. 二叉搜索树

　　6. 二叉树和森林的转换

　　（六）图

　　1. 图的定义和术语

　　2. 图的存储结构

　　3. 深度优先、广度优先搜索

　　4. 最小生成树

　　5. 最短路径问题

　　（七）内部排序

　　1. 简单选择排序

　　2. 插入排序

　　3. 快速排序

　　4. 归并排序

　　5. 基数排序

　　（八）哈希表

　　1. 哈希表的定义

　　2. 哈希函数的构造

　　3. 冲突处理

　　《数据库系统》入学考试大纲

　　一、数据库基本概念

　　1.数据库系统的特点

　　2. 数据库系统三级模式结构

　　二、概念模型与E-R图

　　1.实体与联系

　　2. ER图向关系模式的转换

　　三、关系数据模型

　　1.数据模型三要素

　　2. 关系模型（包括实体完整性和参照完整性）

　　3.关系代数基本运算（选择， 投影，笛卡尔积，联接，集合运算）

　　四、关系数据库标准语言SQL

　　1.表定义（包括primary key、foreign key、check ）

　　2. 索引定义

　　3. 视图的定义与作用

　　4.表的查询和更改

　　5.嵌入式SQL（静态SQL部分）

　　五、关系规范化

　　1.函数依赖的概念

　　2. 范式（1NF、2NF、3NF、BCNF）

　　3.关系规范化方法

　　六、数据库保护

　　1. 事务的概念

　　2.并发事务的潜在问题

　　3.事务的可串性化调度

　　4. 锁机制（共享锁和排它锁）

　　5. 二阶段锁协议

　　6.数据库系统的故障类型

　　7.数据库备份

　　8.日志的作用及“先写日志文件原则”

　　主要参考书

　　<数据库系统原理>， 王珊，陈红， 清华大学出版社

　　《操作系统》入学考试大纲

　　一、导论

　　1. 对操作系统定义的理解

　　2. 对操作系统目标的理解

　　3. 操作系统主要功能

　　二、进程管理

　　多道程序设计

　　分时系统

　　进程概念和线程概念

　　进程调度时机和进程调度算法（FCFS，SJF，RR，优先权法等）

　　抢占式和非抢占式

　　临界区问题

　　临界区算法正确性判断（互斥，有限等待，空闲让进）

　　临界区算法（面包房算法等）

　　wait/signal操作和信号量

　　经典同步问题（生产者－消费者，读者－写者，哲学家就餐问题等）

　　死锁和死锁条件

　　解决死锁的方法（死锁预防，死锁避免，死锁检测，死锁恢复）

　　银行家算法

　　三、存储管理

　　地址映射

　　逻辑地址和物理地址

　　交换

　　连续地址分配算法

　　页式存储管理

　　段式存储管理

　　虚拟存储管理（按需调页式）

　　缺页中断服务

　　页面置换概念和算法（FIFO，LRU等）

　　工作集

　　抖动

　　四、文件系统管理

　　文件、目录和文件系统

　　文件系统界面（文件操作，目录操作，目录结构，文件系统安装等）

　　文件系统实现（连续式，链表式，索引式）

　　空闲空间管理

　　五、外存设备

　　磁盘调度算法（FCFS，SSTF，SCAN，LOOK等）

　　SPOOLING

　　RAID

　　主要参考书

　　汤子瀛、哲凤屏、汤小丹：《计算机操作系统》，西安电子科技大学出版社。