三、栈和队列
【考试内容】
1、栈的抽象数据类型的定义。
2、栈的表示和实现。
3、栈的简单应用。
4、抽象数据类型队列的定义。
5、队列的链式表示和实现。
6、队列的顺序表示和实现。
【考试要求】
1、栈的逻辑结构、存储结构及其相关算法(综合应用)
(1)栈的逻辑结构特点,栈与线性表的异同。
(2)顺序栈和链栈上实现的进栈、退栈等基本算法。
(3)栈的“上溢”和“下溢”的概念及其判别条件。
(4)利用栈设计算法解决简单的应用问题。
2、队列的逻辑结构、存储结构及其相关算法(综合应用)
(1)队列的逻辑结构特点,队列与线性表的异同。
(2)顺序队列(主要是循环队列)和链队列上实现的入队、出队等基本算法。
(3)队列的“上溢”和“下溢”的概念及其判别条件。
(4)使用数组实现的循环队列取代普通的顺序队列的原因。
(5)循环队列中对边界条件的处理方法。
(6)利用队列设计算法解决简单的应用问题。
3、栈和队列的应用(领会)
栈和队列的特点,什么样的情况下能够使用栈或队列。
四、串
【考试内容】
1、串的定义、空串、空格串、子串、主串、串相等。
2、串的基本操作。
3、串的顺序存储结构及在顺序存储结构下基本操作的实现。
4、串的堆分配存储表示及其在堆分配存储结构下基本操作的实现。
5、串的链式存储表示。
【考试要求】
1、串的有关概念及其基本运算(领会)。
2、串的简单应用:使用串解决与串相关的简单的应用问题。
五、数组和广义表
【考试内容】
1、数组的顺序存储结构。
2、二维数组的按行存储及按列存储和计算数组元素的地址计算公式。
3、矩阵的压缩存储、特殊矩阵的表示。
4、广义表的定义和操作(HEAD和TAIL)。
5、广义表的2种存储结构。
【考试要求】
1、多维数组(领会)
(1)多维数组的逻辑结构特征。
(2)多维数组的顺序存储结构及地址计算方式。
(3)数组是一种随机存取结构的原因。
2、矩阵的压缩存储(领会)
(1)特殊矩阵和疏稀矩阵的概念。
(2)特殊矩阵和压缩存储时的下标变换方法。
(3)稀疏矩阵的三元组表表示方法及有关算法。
3、广义表(领会)
(1)广义表的概念、广义表和线性表的联系。
(2)广义表表头和表尾的概念及广义表两个特殊的基本运算,取表头和取表尾。
(3)广义表的两种存储结构。
六、树和二叉树
【考试内容】
1、树的定义和术语。
2、二叉树(完全二叉树、满二叉树)的定义和性质(结论)、二叉树的存储结构——顺序表示法和链表表示法。
3、二叉树的三种遍历方法及相应的递归算法。
4、树的存储表示法——孩子表示法、双亲表示法、孩子兄弟表示法。
5、树和森林及二叉树的转换方法。
6、树和森林的遍历。
7、树的路径长度、树的带权路径长度、Huffman树(最优二叉树)的构造方法。
8、Huffman编码方法。
【考试要求】
1、领会
(1)树的逻辑结构特征。
(2)树的不同表示方法。
(3)树的常用术语及含义。
(4)树和森林与二叉树之间的转换方法。
(5)树的各种存储结构及其特点。
(6)树的遍历方法。
2、简单应用
(1)二叉树的定义及树与二叉树的差别。
(2)二叉树的性质,了解相应的证明方法。
(3)二叉树的两种存储结构、特点及适用范围。
(4)最优二叉树和前缀编码的概念及特点。
(5)Huffman算法的思想。
(6)根据给定的叶结点及其权值构造出相应的最优二叉树。
(7)根据最优二叉树构造对应的Huffman编码。
3、综合应用
(1)二叉树的三种遍历算法,理解其执行过程。
(2)根据不同的遍历方法,应能得出其相应的结点访问次序。
(3)以遍历算法为基础,设计有关算法解决简单的应用问题。
免责声明:本站所提供试题均来源于网友提供或网络搜集,由本站编辑整理,仅供个人研究、交流学习使用,不涉及商业盈利目的。如涉及版权问题,请联系本站管理员予以更改或删除。
12-06
11-24
11-18
11-15
11-15
11-12