**篇 学习提要和习题解答 第 1 章 绪论.............1 1.1 重点难点指导.. 1 1.1.1 相关术语............................................ 1 1.1.2 算法的描述和分析 ............................. 3 1.2 典型例题解析.. 4 1.2.1 选择题.. 4 1.2.2 判断题.. 5 1.2.3 填空题.. 6 1.2.4 简答题.. 6 1.3 主教材习题解答............................................ 7 1.3.1 选择题.. 7 1.3.2 简答题.. 8 第 2 章 线性表....... 122.1 重点难点指导.12 2.1.1 相关术语...........................................12 2.1.2 线性表的顺序存储 ............................13 2.1.3 链表 ....15 2.1.4 线性表的基本运算 ............................17 2.2 典型例题解析.20 2.2.1 选择题.20 2.2.2 判断题.23 2.2.3 简答题.24 2.2.4 算法设计题 .......................................26 2.3 主教材习题解答...........................................29 2.3.1 选择题.29 2.3.2 判断题.30 2.3.3 算法设计题 .......................................31 第 3章 栈和队列.... 36 3.1 重点难点指导.36 3.1.1 相关术语...........................................36 3.1.2 栈........37 3.1.3 队列 ....39 3.1.4 栈的应用...........................................43 3.1.5 队列的应用 .......................................43 3.2 典型例题解析.44 3.2.1 选择题.44 3.2.2 填空题.45 3.2.3 简答题.46 3.2.4 算法设计题 .......................................47 3.3 主教材习题解答...........................................52 3.3.1 选择题.52 3.3.2 简答题.53 3.3.3 算法设计题 .......................................53 第 4 章 串..............56 4.1 重点难点指导.56 4.1.1 相关术语...........................................56 4.1.2 串的基本运算....................................57 4.1.3 串的存储结构....................................57 4.1.4 字符串匹配算法实现.........................59 4.2 典型例题解析.60 4.2.1 选择题.60 4.2.2 填空题.60 4.2.3 基本运算题 .......................................61 4.2.4 算法设计题 .......................................61 4.3 主教材习题解答...........................................64 4.3.1 选择题.64 4.3.2 算法设计题 .......................................65 第 5章 数组和广义表...........................................67 5.1 重点难点指导.67 5.1.1 相关术语...........................................67 5.1.2 多维数组...........................................68 5.1.3 特殊矩阵...........................................68 5.1.4 稀疏矩阵...........................................70 5.1.5 广义表.72 5.2 典型例题解析.74 5.2.1 选择题.74 5.2.2 填空题.75 5.2.3 简答题.76 5.2.4 算法设计题 .......................................77 5.3 主教材习题解答...........................................81 5.3.1 选择题.81 5.3.2 简答题.82 5.3.3 算法设计题 .......................................84 第 6 章 二叉树....... 876.1 重点难点指导.87 6.1.1 相关术语...........................................87 6.1.2 二叉树的存储结构 ............................89 6.1.3 二叉树的遍历运算 ............................90 6.1.4 二叉树的基本应用 ............................91 6.2 典型例题解析.92 6.2.1 选择题.92 6.2.2 判断题.93 6.2.3 填空题.94 6.2.4 简答题.95 6.2.5 算法设计题 .......................................97 6.3 主教材习题解答.........................................101 6.3.1 选择题.............................................101 6.3.2 简答题.............................................103 6.3.3 算法设计题 .....................................104 第 7章 树与森林.. 108 7.1 重点难点指导.............................................1087.1.1 相关术语.........................................108 7.1.2 树的存储结构..................................109 7.1.3 树的基本运算..................................110 7.1.4 树、森林和二叉树的相互转换........ 111 7.2 典型例题解析.............................................111 7.2.1 选择题............................................. 111 7.2.2 判断题.............................................112 7.2.3 填空题.............................................113 7.2.4 简答题.............................................113 7.2.5 算法设计题 .....................................114 7.3 主教材习题解答.........................................116 7.3.1 选择题.............................................116 7.3.2 简答题.............................................116 7.3.3 算法设计题 .....................................118 第 8 章 图............120 8.1 重点难点指导.............................................1208.1.1 相关术语.........................................120 8.1.2 图的基本操作..................................122 8.1.3 图的存储表示..................................122 8.1.4 图的遍历.........................................125 8.1.5 图的应用.........................................126 8.2 典型例题解析.............................................1298.2.1 选择题.............................................129 8.2.2 判断题.............................................130 8.2.3 填空题.............................................132 8.2.4 简答题.............................................132 8.2.5 算法设计题 .....................................134 8.3 主教材习题解答.........................................139 8.3.1 选择题.............................................139 8.3.2 简答题.............................................141 8.3.3 算法设计.........................................144 第 9 章 查找.........151 9.1 重点难点指导.............................................1519.1.1 相关术语.........................................151 9.1.2 线性表查找 .....................................152 9.1.3 排序树上的查找..............................153 9.1.4 哈希表.............................................156 9.2 典型例题解析.............................................1579.2.1 选择题.............................................157 9.2.2 判断题.............................................158 9.2.3 简答题.............................................159 9.2.4 算法设计题 .....................................160 9.3 主教材习题解答.........................................165 9.3.1 选择题.............................................165 9.3.2 简答题.............................................166 9.3.3 算法设计题 .....................................169 第 10 章 排序....... 17310.1 重点难点指导...........................................17310.1.1 相关术语 .......................................173 10.1.2 插入排序 .......................................174 10.1.3 交换排序 .......................................175 10.1.4 选择排序 .......................................176 10.1.5 归并排序 .......................................177 10.1.6 基数排序 .......................................177 10.1.7 外部排序 .......................................178 10.2 典型例题解析...........................................17810.2.1 选择题...........................................178 10.2.2 判断题...........................................179 10.2.3 填空题...........................................180 10.2.4 算法设计题 ...................................182 10.3 主教材习题解答 .......................................18510.3.1 选择题...........................................185 10.3.2 简答题...........................................187 10.3.3 算法设计题 ...................................190 第二篇 课程实验与设计指导 第 11章 课程实验与设计的一般步骤..................194 11.1 概述............194 11.2 课程实验与设计步骤................................195 第 12章 课程实验与设计安排............................197 12.1 线性结构 ....197 实验 1 约瑟夫环问题...............................197实验 2 一元多项式运算...........................199 实验 3 模拟停车场管理...........................201 12.2 树形结构 ....206 实验 1 哈夫曼编码/译码器......................206 实验 2 二叉树遍历...................................20812.3 图形结构 ....208 实验 1 校园导游程序...............................208实验 2 教学计划编排...............................21012.4 查找和排序.210 实验 1 职工信息检索系统........................210实验 2 各种内部排序的性能比较.............211参考文献 ...........................212