《数据结构》考试大纲

第一章 绪论
    1、理解什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构等基本术语以及逻辑结构与物理结构之间的关系。
    2、熟悉用C++语言描述算法，能够用C++语言编写程序。
    3、理解算法的定义、算法的特性、算法的时间代价和空间代价。

第二章 线性表
    1、理解线性表的逻辑结构特性。
    2、熟练掌握线性表的顺序存储的定义和基本算法（搜索、插入、删除）的实现。
    3、理解线性表的链接存储的定义。
    4、熟练掌握线性表的基本算法（搜索、插入、删除）在单链表上的实现。
    重点：熟练掌握线性表的基本算法。

第三章 稀疏矩阵和广义表
    1、了解稀疏矩阵的两种存储方式和基本算法（输入、建立、转置、相加等）的实现。
    2、了解广义表的概念、定义、表示及存储结构的实现。
    3、了解广义表的的访问算法和递归（求长度、深度、建立、输出等）算法。

第四章 栈和队列
    1、理解栈的定义、特性。
    2、掌握栈的两种存储结构。
    3、熟练掌握栈的基本（入/出栈）算法，特别注意栈空、栈满的条件。
    4、理解队列的定义、特性。
    5、掌握队列的两种存储结构。
    6、熟练掌握队列的基本（进/出队）算法，特别注意队首、队尾的指针的变化。
    重点：熟练掌握栈的出入栈算法和队列的出入队算法。

第五章 树
    1、理解树的定义、树的术语和树的性质。
    2、深刻理解二*树的定义、性质、存储结构。
    3、掌握二*树的中序遍历、前序遍历和后序遍历的算法。
    4、掌握二*树的典型运算，如求二*树的深度，建立、清除、输出二*树等。
    5、了解线索二*树的特性，理解中序线索二*树中寻找某节点的前驱和后继的方法。
    6、理解二*树排序树的定义、特性。
    7、熟练掌握二*树排序树的基本算法（插入、删除、查找、更新）。
    8、掌握哈夫曼树的实现方法、构造哈夫曼编码的方法及带权路径长度的计算。
    重点：掌握二*树的定义、基本性质，熟练掌握二*树排序树的基本算法。

第六章 图
    1、理解图的基本概念、术语。
    2、熟练掌握图的存储表示邻接矩阵、邻接表。
    3、了解图的深度和广度优先算法及非连通图的遍历算法思想。
    4、了解构造最小生成树的普里姆算法和克鲁斯卡尔算法思想。
    5、了解求最短路径的Dijkstra算法思想。
    6、了解求解关键路径的方法。
    重点：熟练掌握图的存储表示并了解图的各种应用的算法思想。

第七章 查找
    1、理解查找的基本概念。
    2、熟练掌握顺序表查找的基本方法（顺序查找、二分查找）。
    3、掌握静态索引结构以及查找、构造的基本算法。
    4、理解散列的概念，了解散列函数的构造、解决冲突的方法。
    5、掌握动态索引结构（包括平衡树、B-树）的基本思想。
    6、了解B-树的查找、插入和删除的算法思想。
    重点：熟练掌握顺序表查找的算法并理解静态/动态索引结构的特点。

第八章 排序
    1、理解排序的基本概念和性能分析方法。
    2、掌握插入排序（直接插入排序）、选择排序（直接选择排序、堆排序）、交换排序（气泡排序、快速排序）、归并排序等典型的排序算法及性能分析。
    3、了解多路平衡归并等外排序方法及构造败者树的基本方法。
    重点：熟练掌握内排序的典型算法及其性能分析。

《C++语言程序设计》考试大纲

    作为计算机专业的一门重要的专业基础课，《C++语言程序与设计》课程的特点表现为：一是支持面向对象的程序设计；二是支持传统的面向过程的程序设计。

考试要求：
    在理解和掌握C++ 语言的基本语法和语义、理解面向对象的思想、掌握计算机程序设计概念体系的基础上，必须：
    1. 掌握面向过程的程序设计方法。
    2. 掌握面向对象程序设计的方法。
    3. 具有较强的编程能力、分析问题能力以及解决实际问题的能力。

考试内容：程序设计
    包括：面向过程的程序设计和面向对象的程序设计。
    涉及的概念和具体内容有：运算符、表达式、过程化语句、函数、类与对象（构造与析构函数、拷贝构造函数）、继承与多态性、引用、指针、数组、顺序表、链表、 模板（类模板与函数模板）、I/O流。

《计算机操作系统》考试大纲

一、教材名称：现代操作系统教程（滕至阳编著） 高教出版社 2000年

二、课程地位、作用及任务
    地位：是计算机专业的主干课程。该课程下接计算机硬件结构，上接多种实用软件和应用软件，包括数据库系统、网络与分布式系统。课程中提出的若干概念如进程、线程、虚拟、同步与互斥等是计算机科学与技术领域中最重要的基础性概念。可见该课程的地位是非常重要的。
    作用：课程的内容不仅使学生具备实际操纵计算机的能力，而且培养学生在操作系统平台上二次开发能力。
    任务：使学生了解和掌握现代操作系统中的基本概念和操作系统本身采用的主要实现技术，为今后参与计算机科学研究打好基础。

三、考试目的、内容及方法
    目的：检查学生对操作系统基本概念的掌握情况，特别是了解学生利用基本概念阐明实际问题的能力，以及利用已学过的某些技术手段如何编写同步、互斥、通信等具备操作系统明显特征的程序段落的能力。
    内容：考试内容分基础部分和提高部分。基本部分是必须掌握的，提高部分要求学生在理解的基础上有某种程度的应用。
    ● 基本部分包括如下内容：
    1．引言部分（OS定义、功能、特征、类型、启动过程）
    2．作业管理（用户界面，系统调用，批处理，Spooling，作业调度）
    3．存储管理（虚存，地址变换，请求页式，页面置换算法）
    4．进程管理（进程定义、状态及变迁，PCB，同步与互斥，PV操作，进程间通信算法，死锁概念，优先级抢夺调度）
    5．线程管理（线程概念、状态，多线程实例）
    6．文件管理（文件概念，卷，目录，i结点，逻辑/物理地址，文件表）
    7．设备管理（特别文件，I/O进程，设备入口表，字符/块设备驱动）
    ● 提高部分包括如下内容：
    8．并发程序设计（进程/子进程，并发PASCAL，CSP）
    9．操作系统的设计与实现（设计方法，实现语言）
    10．多处理操作系统，网络/分布式操作系统，操作系统的安全机制
    方法：紧扣课程内容，以基本部分为主。试题类型一般为：概念题，简答题、计算题、编程题。