960《计算机专业知识》考试大纲.pdf

复旦大学 2019 年硕士研究生招生考试自命题科目考试大纲 科目代码 960 科目名称 计算机专业知识 一、考试内容范围 《计算机专业知识》科目涵盖数据结构、操作系统、计算机网络三门学科的专业基础 知识。要求考生掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用 所学的基本原理、方法和技术来分析、解决有关理论问题和实际问题。 （一）数据结构 1. 数组、顺序表、特殊矩阵；单链表、循环链表、双向链表、静态链表。 2. 串的基本操作、串的穷举模式匹配算法、串的 KMP 模式匹配算法。 3. 栈、队列；递归转化为非递归；广义表。 4. 树、森林、树的存储结构、树的遍历；二叉树、二叉树的存储表示、二叉树的各 种遍历；线索化二叉树、堆；二叉树计数、哈夫曼树和哈夫曼编码。 5. 顺序查找、折半查找；二叉查找树、AVL 树；Hash 查找。 6. 图的基本概念、图的存储结构、图的遍历；最小生成树、最短路径；拓扑排序、 关键路径。 7. 内排序方法、内排序方法的比较。 （二）操作系统： 1. 系统调用、进程、线程概念、多线程模型、用户级/内核级线程，调度的原理，典 型的调度算法。 2. 互斥、同步、死锁概念、临界区、互斥方法、经典同步问题、死锁预防、死锁避 免、安全状态，银行家算法。 3. 内存分配管理方式、逻辑地址与物理地址、虚拟内存、典型页面置换算法、工作 集、页面抖动。 4. 文件逻辑结构、目录、文件实现、磁盘组织与管理、磁盘调度算法。 （三）计算机网络 1. 计算机网络体系结构，概念、组成、功能、分类与标准，网络结构的参考模型； 2. 物理层与数据链路层，通信基础、传输介质、物理层与链路层设备、帧结构与介 质访问控制； 3. 网络层与传输层，路由算法与协议、IPv4/IPv6/移动 IP、IP 组播、网络层设备、 TCP 协议与 UDP 协议； 4. 应用层，网络应用模型、DNS、HTTP、电子邮件、FTP、WWW。 二、试卷结构 本试卷满分 150 分，各部分的分值如下： 数据结构 90 分：填空题 20 分、单选题 10 分、问答题 30 分、算法题 30 分。 操作系统 30 分：单项选择题 10 分、综合应用题 20 分。 计算机网络 30 分：填空题 15 分、问答题 6 分、设计与计算题 9 分。 三、参考书目 作者 书名 出版社 出版时间 版次 殷人昆等 数据结构（用 清华大学出 2007 年 第二版 面向对象方 版社 法 和 C++ 描 述） 施伯乐等 数据结构教 复旦大学出 程 版社 Silberschatz 操作系统概 高等教育出 等 念 版社 高传善、 曹袖、 计 算 机 网 络 高等教育出 毛迪林、王雪 版社 平 教程 2011 年 2010 第七版 2013 年 第二版 备注