961数字图象处理技术基础考试大纲（2011版）
一、考试组成
961数字图象处理技术基础共包括三门课程的内容：数据结构、数据库、图像处理。各占50分。
二、数据结构部分的考试大纲
（一）、指定参考书
《数据结构教程（第二版）》 唐发根编著 北京航空航天大学出版社
（建议选用第3次印刷的书）
（二）、考试内容
1．线性表
（1）线性关系，线性表的定义，线性表的基本操作；
（2）线性表的顺序存储结构与链式存储结构(单链表、循环链表和双向链表)的构造原理；
（3）在以上两种存储结构的基础上对线性表实施的基本操作对应的算法设计(含基本的算法分析)。
2．数组
特殊矩阵压缩存储的基本思想、目的与方法。
3．堆栈与队列
（1）堆栈与队列(含循环队列)的基本概念、基本操作；
（2）堆栈与队列的顺序存储结构与链式存储结构的构造原理；
（3）在以上两种储结构的基础上对堆栈与队列实施插入与删除等基本操作的算法设计(含基本的算法分析)。
4．二叉树
（1）二叉树的基本概念与名词术语；
（2）完全二叉树与满二叉树，二叉树的基本性质；
（3）二叉树的顺序存储结构与二叉链表存储结构的基本构造原理，二叉树的前序遍历、中序遍历和后序遍历以及对应算法的设计(非递归算法)，由遍历序列恢复二叉树；
（4）线索二叉树的基本概念与基本构造原理；
（5）二叉排序树的基本概念，二叉排序树的建立(插入)和查找(含平均查找长度ASL)。
5．图
（1）图的基本概念，基本名词术语；
（2）图的邻接矩阵存储方法、邻接表存储方法的基本构造原理；
（3）图的深度优先遍历与广度优先遍历，图的遍历的基本用途；
（4）最小生成树与最短路径的基本概念和构造过程，AOV网与拓扑排序。
6．文件及查找
（1）顺序查找法与折半查找法，折半查找法对应的“判定树”的构造；
（2）B-树的基本概念，B-树的插入；
（3）散列(Hash)表的构造、散列函数、散列冲突以及处理散列冲突的方法。
7．内排序
（1）插入排序法(含折半插入排序法)、选择排序法、泡排序法、快速排序法、(大顶)堆积排序法；
（2）各种内排序方法排序的基本原理和特点。
三、数据库部分考试大纲
（一）指定参考书
数据库系统概论（第四版），高等教育出版社，王珊，萨师煊著
（二）复习内容
1．数据库系统概述
数据库系统的一般概念、原理和技术。要求学生掌握数据库系统的概念、体系结构、组成和特点，掌握数据模型的概念。
2．关系数据库及其标准语言SQL
关系的数学定义及其特性，关系数据模型的基本概念，关系代数、关系演算、SQL语言的基本概念、特点、语法格式和使用方法，查询优化。要求清楚了解基本概念，能够运用关系运算和SQL语言实现对数据库系统的操作，并初步了解查询优化的一般准则和算法。
3．数据库设计与关系数据理论
数据库系统设计的基本概念，数据库设计的步骤及各阶段应完成的任务和实现方法。规范化的基本概念和方法，数据依赖的公理系统。要求能够进行数据库的概念和逻辑设计，了解物理设计的基本概念和方法。熟练掌握规范化的基本概念和方法。
4．数据控制
事务的概念和特性，数据库系统并发控制、数据库恢复、数据库系统安全性、完整性的概念及其方法。要求掌握数据控制的基本概念和相关技术。
5．分布式数据库系统
了解分布式数据库系统的基本概念，分布式数据库系统的体系结构以及分布式查询处理和数据控制的相关概念和技术。
四、图象处理部分考试大纲
（一）参考书图像工程(上册) 图像处理 章毓晋, 清华大学出版社, 2006年3月第二版
（二）复习内容
1、数字图像的基本概念及基本运算
（1）数字图像的概念和表达、采样和量化、空间和灰度分辨率。
（2）图像直方图的定义和计算。
（3）数字图像的基本运算:加、减、直方图均衡、分段线性变换。
2、基本图像变换与频域图像增强
（1）二维离散傅立叶变换和反变换；
（2）频率域滤波的概念和计算步骤；空间域滤波和频率域滤波的对应关系；高斯低通滤波器；高斯高通滤波器；
（3）傅立叶变换的性质；卷积和相关定理；快速傅立叶变换
3、图像编码
相关性与冗余度；
编码效率与压缩比；
（3） 预测编码；
（4） 正交变换编码
