数据结构自编教材-答案.doc

目录 第一章 数据结构与算法 1 1.1 数据结构的概念 1 1.2 数据的逻辑结构与存储结构 3 1.3 算法及算法分析 5 一、算法及其特性 5 二、算法分析 5 习题1 10 一、选择题 10 二、解答题 11 第二章 线性表 13 2.1 线性表及其逻辑结构 13 一、线性表的定义 13 二、线性表的逻辑特征 13 三、线性表的特性 13 四、线性表的基本操作 14 2.2 顺序表及其基本操作 15 一、顺序表 15 二、顺序表中数据元素存储地址的计算 15 三、顺序表的描述 15 四、顺序表的基本操作的实现 16 2.3 单链表及其基本操作 22 一、链表的有关概念 22 二、链表的基本操作 23 2.4 双向链表及操作 33 一、循环链表 33 二、双向链表 33 2.5 线性表的应用 37 习题2 40 一、选择题 40 二、解答题 44 三、算法设计题 46 第三章 栈和队列 48 3.1 栈 48 一、栈的定义及基本操作 48 二、顺序栈及基本操作的实现 49 三、链栈及基本操作的实现 51 3.2 队列 54 一、队列的定义及基本操作 54 二、顺序队列及基本操作 54 三、循环队列 55 四、链队列及基本操作的实现 58 3.3 栈和队列的应用 62 习题3 67 一、选择题 67 二、填空题 68 三、算法设计题 69 *第四章 串和数组 70 4.1 串及其存储结构 70 一、串的基本概念 70 二、串的基本运算 70 三、 串的存储结构 70 4.2 串的基本操作 73 一、子串定位运算 73 二、目标（串）和模式（串） 73 三、串匹配 73 四、朴素的串匹配算法 73 五、链串上的子串定位运算 74 4.3 多维数组 76 一、一维数组 76 二、多维数组 76 三、数组的顺序存储表示 77 四、数组元素的地址计算公式 77 4.4 矩阵的压缩存储 78 一、常用矩阵的压缩存储 78 二、稀疏矩阵的压缩存储 79 4.5 广义表的概念 81 一、广义表定义 81 二、广义表表示 81 三、广义表运算 83 习题4 84 一、解答题 84 二、算法设计题 84 第五章 树和二叉树 85 5.1 树的概念 85 一、树的递归定义 85 二、树结构的基本术语 86 三、树型结构的逻辑特征 88 5.2 二叉树及其性质 89 一、二叉树的定义 89 二、二叉树的性质 89 5.3 二叉树的存储结构 93 一、二叉树的顺序存储结构 93 二、二叉树的链式存储结构 95 5.4 二叉树的遍历 98 一、遍历方案 98 二、遍历序列 99 5.5 二叉树的基本操作 102 一、二叉链表的构造 102 二、二叉链表的基本操作 102 5.6 树和森林 105 一、树、森林到二叉树的转换 105 二、树的存储结构 108 三、树的遍历 111 5.7 哈夫曼树及其应用 113 一、哈夫曼树的有关概念 113 二、哈夫曼树的构造 114 *三、哈夫曼算法的实现 116 四、哈夫曼编码 119 习题5 123 一、选择题 123 二、解答题 125 三、算法设计题 127 第六章 图 128 6.1 图的概念 128 一、图的二元组定义 128 二、无向图和有向图 128 三、图的边和顶点的关系 129 四、子图 130 五、路径 130 六、连通图和连通分量 131 七、强连通图和强连通分量 131 八、网络 132 6.2 图的存储结构 133 一、图的邻接矩阵表示法 133 二、图的邻接表表示法 134 6.3 图的遍历 138 一、图的深度优先遍历 138 二、图的广度优先遍历 140 6.4 最小生成树 143 一、生成树 143 二、最小生成树 143 *6.5 最短路径 147 一、带权图的最短路径问题 147 二、最短路径问题 147 三、迪杰斯特拉(Dijkstra)算法求单源最短路径 147 *6.6 拓扑排序 150 一、无前趋的顶点优先 151 二、无后继的顶点优先 152 习题6 153 一、选择题 153 二、解答题 154 三、算法设计题 155 第七章 排序 156 7.1 排序的基本概念 156 7.2 插入排序 158 一、直接插入排序 158 二、希尔排序（Shell Sort） 160 7.3 交换排序 162 一、冒泡排序 162 二、快速排序 163 7.4 选择排序 168 一、直接选择排序 168 二、堆排序 169 7.5 归并排序 179 一、两路归并排序 179 二、归并排序 179 7.6 分配排序 183 一、箱排序(Bin Sort) 183 二、桶排序 183 三、基数排序 185 习题7 188 一、选择题 188 二、解答题 189 三、算法设计题