（403）程序设计与数据结构考试大纲
一、适用报考的专业：计算机及其相关专业
二、考试题型： 填空题、选择题、简答题、算法与程序设计
三、主要内容
线性表
² 线性表的基本概念
² 线性表的类型和应用
² 顺序型线性表、链式型顺序表的表示和实现
² 线性链表、循环链表、双向链表的概念
栈和队列
² 栈的基本概念
² 栈的表示和实现和应用
² 队列的基本概念
² 队列的表示和实现和应用
² 循环队列和链式队列
串
² 串的定义
² 串的表示和实现
² 串的操作和应用
数组和广义表
² 数组的定义
² 数组的表示和实现
² 矩阵的概念、特殊矩阵和稀疏矩阵
² 广义表的定义、存储结构和应用
树、二叉树
² 树、二叉树的的基本概念
² 二叉树的存储结构和二叉树的遍历
² 森林的概念、存储结构
² 森林与二叉树的转换
² 树和森林的遍历
² 哈夫曼树的概念和应用
图
² 图的定义和概念
² 图的存储结构、图的遍历
² 图的连通性问题
² 最短路径问题
查找和排序
² 静态查找表的基本概念、静态查找的基本方法
² 顺序表、有序表、静态树表、索引顺序表的查找
² 动态查找表的基本概念
² 二叉排序树和平衡二叉树的基本概念
² 哈希表的基本概念、哈希函数的构造方法、冲突处理的方法
² 内部排序的概念
² 插入排序、快速排序、选择排序归并排序、基数排序的概念和实现方法、几种内部排序方法的比较以及复杂度分析
² 外部排序的基本概念、外部排序的方法
文件
² 文件的基本概念
编程语言（C语言）
² 结构化程序设计，选择结构，循环结构
² 函数定义、调用方法
² 数组，字符串、字符串数组
² 指针的概念及基本使用方法
² 结构体类型数据的声明与引用
四、考试要求
² 掌握线性表的基本概念，能够熟练地运用线性表数据结构进行程序设计；熟练掌握链表、循环链表、双向链表的基概念，能够灵活运用链式存储结构；
² 掌握串的概念、存储和运算，掌握串的模式匹配算法；
² 熟练掌握栈的基本概念，掌握栈的存储结构和实现，能够熟练应用栈进行应用程序的设计；
² 理解队列的基本概念，掌握队列的存储和实现，能够运用队列进行应用程序设计；理解链式队列和循环队列的概念；
² 熟练掌握数组、二维数组、多位数组的概念，能够灵活运行数组进行应用程序开发；理解稀疏矩阵的概念；
² 理解树的概念和基本术语；熟练掌握二叉树的概念、存储结构和遍历；了解森林的概念与遍历；掌握哈夫曼树的概念和应用；
² 理解图的概念和术语，掌握图的存储、遍历、连通性和最短路径问题；
² 熟练掌握数据的不同查找方法，理解几种方法的特点；掌握哈希表的概念和应用方法；
² 熟练掌握内部排序的几种方法，以及不同方法的特点和复杂度的分析；理解外部排序的概念和方法；
² 了解文件的概念和特点
² 掌握C语言中选择结构程序设计和循环结构程序设计的基本用法。
² 掌握C语言中一、二维数组的定义和使用；掌握字符串的使用和字符串函数的应用。
² 掌握C语言中指针的基本用法；掌握指向一维数组和指向字符串指针的使用方法。
² 掌握C语言中函数定义和调用的方法。
² 掌握C语言中结构体类型的概念，掌握其定义的常用形式和应用方法。
² 要求考生具有基本的软件设计和程序编制能力；具有独立分析和解决问题的能力。
五、主要参考书目
《数据结构》（第二版），严蔚敏、吴伟民，清华大学出版社
《C语言程序设计》，谭浩强，清华大学出版社。
《C程序设计教程》，张莉，电子工业出版社
一、适用报考的专业：计算机及其相关专业
二、考试题型： 填空题、选择题、简答题、算法与程序设计
三、主要内容
线性表
² 线性表的基本概念
² 线性表的类型和应用
² 顺序型线性表、链式型顺序表的表示和实现
² 线性链表、循环链表、双向链表的概念
栈和队列
² 栈的基本概念
² 栈的表示和实现和应用
² 队列的基本概念
² 队列的表示和实现和应用
² 循环队列和链式队列
串
² 串的定义
² 串的表示和实现
² 串的操作和应用
数组和广义表
² 数组的定义
² 数组的表示和实现
² 矩阵的概念、特殊矩阵和稀疏矩阵
² 广义表的定义、存储结构和应用
树、二叉树
² 树、二叉树的的基本概念
² 二叉树的存储结构和二叉树的遍历
² 森林的概念、存储结构
² 森林与二叉树的转换
² 树和森林的遍历
² 哈夫曼树的概念和应用
图
² 图的定义和概念
² 图的存储结构、图的遍历
² 图的连通性问题
² 最短路径问题
查找和排序
² 静态查找表的基本概念、静态查找的基本方法
² 顺序表、有序表、静态树表、索引顺序表的查找
² 动态查找表的基本概念
² 二叉排序树和平衡二叉树的基本概念
² 哈希表的基本概念、哈希函数的构造方法、冲突处理的方法
² 内部排序的概念
² 插入排序、快速排序、选择排序归并排序、基数排序的概念和实现方法、几种内部排序方法的比较以及复杂度分析
² 外部排序的基本概念、外部排序的方法
文件
² 文件的基本概念
编程语言（C语言）
² 结构化程序设计，选择结构，循环结构
² 函数定义、调用方法
² 数组，字符串、字符串数组
² 指针的概念及基本使用方法
² 结构体类型数据的声明与引用
四、考试要求
² 掌握线性表的基本概念，能够熟练地运用线性表数据结构进行程序设计；熟练掌握链表、循环链表、双向链表的基概念，能够灵活运用链式存储结构；
² 掌握串的概念、存储和运算，掌握串的模式匹配算法；
² 熟练掌握栈的基本概念，掌握栈的存储结构和实现，能够熟练应用栈进行应用程序的设计；
² 理解队列的基本概念，掌握队列的存储和实现，能够运用队列进行应用程序设计；理解链式队列和循环队列的概念；
² 熟练掌握数组、二维数组、多位数组的概念，能够灵活运行数组进行应用程序开发；理解稀疏矩阵的概念；
² 理解树的概念和基本术语；熟练掌握二叉树的概念、存储结构和遍历；了解森林的概念与遍历；掌握哈夫曼树的概念和应用；
² 理解图的概念和术语，掌握图的存储、遍历、连通性和最短路径问题；
² 熟练掌握数据的不同查找方法，理解几种方法的特点；掌握哈希表的概念和应用方法；
² 熟练掌握内部排序的几种方法，以及不同方法的特点和复杂度的分析；理解外部排序的概念和方法；
² 了解文件的概念和特点
² 掌握C语言中选择结构程序设计和循环结构程序设计的基本用法。
² 掌握C语言中一、二维数组的定义和使用；掌握字符串的使用和字符串函数的应用。
² 掌握C语言中指针的基本用法；掌握指向一维数组和指向字符串指针的使用方法。
² 掌握C语言中函数定义和调用的方法。
² 掌握C语言中结构体类型的概念，掌握其定义的常用形式和应用方法。
² 要求考生具有基本的软件设计和程序编制能力；具有独立分析和解决问题的能力。
五、主要参考书目
《数据结构》（第二版），严蔚敏、吴伟民，清华大学出版社
《C语言程序设计》，谭浩强，清华大学出版社。
《C程序设计教程》，张莉，电子工业出版社