数据结构实验实训指导

目 录 **篇 习题与实验 **章 绪论 3 1.1 学习指导 3 1.1.1 基本概念 3 1.1.2 抽象数据类型 5 1.1.3 算法及其分析 6 1.2 习题 9 1.2.1 单项选择题 9 1.2.2 填空题 10 1.2.3 判断题 11 1.2.4 简答题 11 第二章 线性表 12 2.1 学习指导 12 2.1.1 线性表的定义及抽象数据类型 12 2.1.2 顺序表的实现 13 2.1.3 线性链表的实现 15 2.1.4 分析讨论 18 2.1.5 线性表的应用 18 2.2 习题 18 2.2.1 单项选择题 18 2.2.2 填空题 21 2.2.3 判断题 22 2.2.4 简答题 23 2.2.5 算法设计题 23 2.3 实验 24 2.3.1 线性表(验证性实验) 24 2.3.2 线性表(设计性实验) 30 第三章 栈与队列 37 3.1 学习指导 37 3.1.1 栈的类型定义 37 3.1.2 顺序栈的实现 38 3.1.3 栈的应用 39 3.1.4 队列 39 3.2 习题 41 3.2.1 单项选择题 41 3.2.2 填空题 43 3.2.3 判断题 43 3.2.4 简答题 44 3.2.5 算法设计题 44 3.3 实验 44 3.3.1 栈和队列的应用(验证性实验) 44 3.3.2 栈和队列(设计性实验) 50 第四章 串 54 4.1 学习指导 54 4.1.1 串的定义 54 4.1.2 串的表示和实现 55 4.2 习题 59 4.2.1 单项选择题 59 4.2.2 填空题 59 4.2.3 判断题 59 4.2.4 算法设计题 60 4.3 实验 60 4.3.1 串的基本运算(验证性实验) 60 4.3.2 串的应用(设计性实验) 63 第五章 数组和广义表 65 5.1 学习指导 65 5.1.1 数组的定义 65 5.1.2 数组顺序存储的表示和实现 66 5.1.3 稀疏矩阵的压缩存储 67 5.1.4 广义表 69 5.2 习题 71 5.2.1 单项选择题 71 5.2.2 填空题 72 5.3 实验 73 数组的存储表示和实现方法(验证性实验) 73 第六章 树和二叉树 77 6.1 学习指导 77 6.1.1 树的概念 77 6.1.2 二叉树 78 6.1.3 遍历二叉树和线索二叉树 80 6.1.4 树和森林 84 6.1.5 哈夫曼树 85 6.2 习题 86 6.2.1 单项选择题 86 6.2.2 填空题 88 6.2.3 简答题 90 6.3 实验 90 6.3.1 二叉树的建立及遍历(验证性实验) 90 6.3.2 哈夫曼树(设计性实验) 94 第七章 图 96 7.1 学习指导 96 7.1.1 图的基本概念 96 7.1.2 图的存储结构 98 7.1.3 图的遍历 99 7.1.4 图的连通性 100 7.1.5 有向无环图及其应用 101 7.1.6 *短路径 102 7.2 习题 102 7.2.1 单项选择题 102 7.2.2 填空题 106 7.2.3 判断题 106 7.2.4 简答题 107 7.2.5 算法设计题 108 7.3 实验 108 7.3.1 图的遍历(验证性实验) 108 7.3.2 *小生成树问题(设计性实验) 113 第八章 查找 116 8.1 学习指导 116 8.1.1 查找的基本概念 116 8.1.2 静态查找表 117 8.1.3 动态查找表 119 8.1.4 哈希表 124 8.2 习题 127 8.2.1 单项选择题 127 8.2.2 填空题 130 8.2.3 判断题 131 8.2.4 简答题 131 8.2.5 算法设计题 132 8.3 实验 133 8.3.1 线性表的查找(验证性实验) 133 8.3.2 散列查找(设计性实验) 137 第九章 排序 140 9.1 学习指导 140 9.1.1 排序的基本概念 140 9.1.2 插入排序 141 9.1.3 交换排序 144 9.1.4 选择排序 147 9.1.5 归并排序 149 9.1.6 各种排序方法的综合比较 149 9.2 习题 150 9.2.1 单项选择题 150 9.2.2 填空题 153 9.2.3 判断题 154 9.2.4 简答题 154 9.2.5 算法设计题 155 9.3 实验 155 9.3.1 简单排序的应用(验证性实验) 155 9.3.2 复杂排序的应用(设计性实验) 159 第二篇 实训案例 实训案例一 通信录查找系统 165 实训案例二 双向约瑟夫环 169 实训案例三 算术表达式求值程序 173 实训案例四 校园导游咨询系统 178 实训案例五 实现闭散列表的建立和查找 185 实训案例六 排序 187 实训案例七 运动会成绩统计系统 194 实训案例八 地图染色问题 199 实训案例九 哈夫曼树的构建与展示 204 实训案例十 图的深度和广度优先搜索遍历 211 实训案例十一 餐馆消费问题 217 实训案例十二 二叉树的基本操作管理系统 221 附录A 数据结构模拟试卷 数据结构模拟试卷(一) 229 数据结构模拟试卷(二) 233 数据结构模拟试卷(三) 236 数据结构模拟试卷(四) 239 数据结构模拟试卷(五) 242 数据结构模拟试卷(六) 245 数据结构模拟试卷(七) 248 数据结构模拟试卷(八) 251 数据结构模拟试卷(九) 254 数据结构模拟试卷(十) 257 数据结构模拟试卷(十一) 260 数据结构模拟试卷(十二) 264 数据结构模拟试卷(十三) 268 数据结构模拟试卷(十四) 271 数据结构模拟试卷(十五) 275 数据结构模拟试卷(十六) 279 数据结构模拟试卷(十七) 283 数据结构模拟试卷(一)参考答案 287 数据结构模拟试卷(二)参考答案 289 数据结构模拟试卷(三)参考答案 291 数据结构模拟试卷(四)参考答案 293 数据结构模拟试卷(五)参考答案 295 数据结构模拟试卷(六)参考答案 296 数据结构模拟试卷(七)参考答案 298 数据结构模拟试卷(八)参考答案 300 数据结构模拟试卷(九)参考答案 301 数据结构模拟试卷(十)参考答案 302 数据结构模拟试卷(十一)参考答案 304 数据结构模拟试卷(十二)参考答案 306 数据结构模拟试卷(十三)参考答案 308 数据结构模拟试卷(十四)参考答案 311 数据结构模拟试卷(十五)参考答案 314 数据结构模拟试卷(十六)参考答案 316 数据结构模拟试卷(十七)参考答案 318