浙江工商大学 2019 自命题考试大纲 845 计算机基础综合一、考试目的计算机基础综合是全日制计算机类专业学位研究生入学考试的专业课考试科目，其目的是科学、公平、有效地测试考生掌握计算机类专业大学本科阶段专业知识、基本理论、基本方法的水平和分析问题、解决问题的能力。 二、考试性质及范围本考试是为招收计算机类硕士研究生而设置的具有选拔性质的科目，评价考生是否达到高等院校计算机类专业优秀本科毕业生所能达到的及格或及格以上水平，以利于择优选拔，确保硕士研究生的招生质量。考试的范围涵盖计算机类专业的主要基础课程，包括数据结构、操作系统等课程。三、考试基本要求1. 要求考生系统地掌握数据结构、操作系统等课程的基本概念、基本原理和基本方法。2. 能综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题及实际问题。四、考试形式本考试采取闭卷、笔试形式。试题题型参见“考试内容一览表 ”。五、考试内容本考试包括两部分：数据结构和操作系统，总分 150 分。I. 数据结构1. 要求掌握数据结构的基本概念、基本原理和基本方法；掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间及空间复杂度的分析；能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用 C、C+或相关语言设计与实现算法的能力。主要内容：（一）线性表1、线性表的定义和基本操作2、单链表、循环链表和双向链表的定义及实现3、线性表的应用（二）堆栈、队列1、堆栈和队列的基本概念2、堆栈和队列的存储结构、基本操作及实现3、堆栈和队列的典型应用（三）数组和串1、数组及串的定义2、数组的存储结构及稀疏矩阵的压缩存储3、串的存储结构及模式匹配算法（四）树与二叉树1、树的基本概念、表示及存储结构2、二叉树（1）二叉树的定义及主要特性（2）二叉树的顺存储结构、基本操作及实现（3）二叉树的遍历及各种操作（4）线索二叉树的基本概念和构造3、二叉树、树和森林之间的相关转换4、树及二叉树的应用（1）哈夫曼树的定义、构造及哈夫曼编码（五）图1、图的基本概念2、图的存储及基本操作（1）邻接矩阵（2）邻接表3、图的遍历（1）深度优先搜索（2）广度优先搜索4、图的基本应用（1）最小生成树（2）最短路径（3）拓扑排序（4）关键路径（六）查找1、查找的基本概念2、顺序表、有序表和索引顺序表的查找3、二叉查找树(排序树/搜索树)、平衡二叉树4、哈希表查找（七）排序1、排序的基本概念2、插入排序3、希尔排序4、选择排序5、堆排序6、冒泡排序7、快速排序8、归并排序9、基数排序10、各种排序算法的性能2. 题型题型包括简答题和综合题，其中简答题包括算法应用，程序阅读等，共 45 分；算法和程序设计，共 30 分，合计 75 分。 II. 操作系统1.要求了解操作系统在计算机系统中的作用、地位、发展和特点；理解操作系统的基本概念、原理，掌握操作系统设计方法与实现技术；能够运用所学的操作系统原理、方法与技术分析问题和解决问题。主要内容：（一）操作系统概述1、操作系统的概念、特征、功能和提供的服务2、操作系统的发展与分类（二）进程管理1、进程与线程的基本概念2、进程调度的基本概念、调度方式、调度算法3、进程同步的基本概念、临界区、信号量、经典同步问题4、死锁的基本概念、处理策略、死锁预防和死锁避免的算法、死锁检测（三）内存管理1、内存管理基本概念2、内存交换及分页、分段、段页式内存分配管理3、虚拟内存（1）虚拟内存的基本概念（2）页面置换算法（3）页面分配策略（四）文件管理1、文件系统基础（1）文件概念（2）文件的逻辑结构：顺序文件、索引文件和索引顺序文件（3）目录结构（4）文件的访问类型及访问控制2、文件系统实现（1）文件系统层次结构（2）目录实现（3）文件实现3、磁盘组织与管理（1）磁盘的结构（2）磁盘的调度算法（五）输入输出（I/O）管理1、I/O 管理概述（1）I/O 设备（2）I/O 管理功能（3）I/O 应用接口（4）I/O 控制方式2、I/O 调度（1）I/O 调度基本概念（2）高速缓存与缓冲区（3）设备分配与回收2. 题型题型包括简答题和综合题，其中简答题包括基本概念、名词解释，共 30 分；综合题包括计算、综合分析，共 45 分，合计 75 分。 计算机基础综合考试内容一览表序号 题 型 题 量 分值 时间（分钟）简答题 算法应用，程序阅读等， 4-6 题 45 分1 数据结构程序设计 算法和程序设计，2-3 题 30 分简答题 基本概念、名词解释，共 6题 302 操作系统综合题 计算、综合分析，共 3 题 45180合计 150 180