数据结构 用c++语言描述 习题答案02.pdf

第七章第七章 集合与搜索树集合与搜索树 1 第 137 页 第 5 建立 37 45 91 25 14 76 56 65 为输入时的二叉搜索树 再从该树上依此删除 76 45 则树形分别如何 2 第137页 第 6 试写一个判定任意给定的二叉树是否二叉搜索树算法 int k bool fail false template void BTree IsBiTree BTNode p int if kelement k p element elsefail true IsBiTree p rchild k fail 3 第137页 第 8 以下列序列为输入 从空树开始构造AVL搜索树 1 A Z B Y C X 2 A V L T R E I S O K 4 第137页 第 12 5阶B 树的高度为2时 树中元素个数最少为多少 答 5 5 第137页 第 13 题 从空树开始 以关键字序列 a g f b k d h m j e s i r x 建立 1 4阶B 树 课后答案网 2 5阶B 树 1 4阶B 树 2 5阶B 树 6 第137页 第 14 题 从上题的4阶B 树上依次删除a e f h 第八章第八章 散列与跳表散列与跳表 1 第154页 第 3 题 设散列表ht 11 散列函数h key key 11 采用线性探查法解决冲突 试用关键字值序 列 70 25 80 35 60 45 50 55 建立散列表 2 第154页 第 6 题 给出用拉链方法解决冲突的散列表搜索操作的C 函数实现 template bool LinkedHashTable Search const K 课后答案网 HNode p ht i 元素结点类型 Hnode while p if p element k return true p p nextsynonym return false 3 第154页 第 3 题 设散列表ht 11 散列函数h key key 11 采用二次探查法解决冲突 试用关键字值 序列 70 25 80 35 60 45 50 55 建立散列表 4 第154页 第 4 题 对上题的例子 若采用双散列法 试以散列函数h1 key key 11 h2 key key 9 1 建立散列表 第九章第九章 图图 1 第188页 第 1 题 对下面的有向图求 1 每个顶点的入度和出度 2 强连通分量 3 邻接矩阵 课后答案网 2 第188页 第 2 题 当以边 1 0 1 3 2 1 2 4 3 2 3 4 4 0 4 1 4 5 5 0 的次序从只有 6 个顶点没有边的图开始 通过依此插入这些边 建立邻接表结构 画出该邻接表 3 第188页 第 4 题 已知有向图的邻接表 试写出计算各顶点的入度的算法 template void LinkedGraph Degree int d new int n int i ENode p for i 0 i n i d i 0 for i 0 iadjvex p p nextarc for i 0 i n i cout d i d i 4 第188页 第 6 题 在题 2 所建立的邻接表上进行以顶点 2 为起始顶点的深度优先搜索和广度优先搜索 分别 画出遍历所得到的深度优先搜索和广度优先搜索的生成森林 或生成树 课后答案网 5 第188页 第 8 题 分别设计算法 在邻接矩阵上实现有向图的深度优先搜索 template void MGraph DFS int v bool visited visited v true cout v for int j 0 j n j if a v j 6 第188页 第 10 题 设某项工程由图题 9 3 所示的工序组成 若各工序以流水方式进行 即串行进行 1 画出给工程的 AOV 网络 2 给出该工程的全部合理的工程流程 课后答案网 7 第188页 第 11 题 设有边集合 0 1 1 2 4 1 4 5 5 3 2 3 1 求此图的所有可能的拓扑序列 2 若以此顺序通过加入边的方式建立邻接表 则在该邻接表上执行拓扑排序算法 TopoSort 则得到的拓扑序列是其中哪一种 8 第188页 第 13 题 使用普里姆算法以 1 为源点 画出图题 9 5 的无向图的最小代价生成树 9 第188页 第 16 题 用迪杰斯特拉算法求图题9 6的有向图中以顶点A为源点的单源最短路径 写出一维数组d 和 path在执行该算法的过程中各步的状态 课后答案网 10 第188页 第 17 题 用弗洛伊德算法求图题9 6的有向图的所有顶点之间的最短路径 写出二维数组d和path在 执行该算法的过程中各步的状态 dpath 1 初始状态 源点终点最短路径路径长度 AB A B 3 C A B C 4 D A D 4 E A B E 4 G Sd A path A d B path B d C path C d D path D d E path E d G path G A0 13 A 14 A5 A 1 B0 13 A4 B4 A4 B 1 C0 13 A4 B4 A4 B 1 D0 13 A4 B4 A4 B 1 E0 13 A4 B4 A4 B 1 1A 1AA 1 1 1B 1B 1 1 1 1C 1 1 1D 1 1 1 1 1 1 1E 1 1 1 1 1GG 1 03 45 01 1 02 3 0 20 320 课后答案网 dApathA dBpathB dCpathC 1A 1AA 1 1 1B 1B 1 1 1 1C 1 1 1D 1 1 1 1 1 1 1E 1 1 1 1 1GG 1 1ABAB 1 1 1B 1B 1 1 1 1C 1 1 1DB 1B 1 1 1 1E 1 1 1 1 1GG 1 1ABAB 1 1 1BCB 1 1 1 1C 1 1 1DB 1B 1 1 1 1E 1 1 03 54 01 1 02 3 0 20 320 03444 01 1 02 3404 20 320 03444 0131 02 3404 20 320 课后答案网 dDpathD dE dGpathE pathG 21 第200页 第 1 题 元素序列 61 87 12 03 08 70 97 75 53 26 按下列算法排序 给出各趟排序结果 1 简单选择排序 2 冒泡排序 3 直接插入排序 4 快速排序 5 两路合并排序 1 简单选择排序 初始序列 61871203087097755326 第 1 趟 03 871261087097755326 第 2 趟 0308 1261877097755326 第 3 趟 030812 61877097755326 第 4 趟 03081226 877097755361 第 5 趟 0308122653 7097758761 第 6 趟 030812265361 97758770 1 1 1GG 1 1ABAB 1 1 1BCB 1 1D 1CB 1 1DB 1B 1 1DBE 1 1 1DBGG 1 1ABAB 1 1 1BCB 1 1D 1CB 1 1DB 1B 1 1DBE 1 1 1DBGG 1 03444 0131 5026 3404 5620 67320 03444 0131 5026 3404 5620 67320 课后答案网 第 7 趟 03081226536170 758797 第 8 趟 0308122653617075 8797 第 9 趟 030812265361707587 97 2 冒泡排序 初始序列 61871203087097755326 第 1 趟61120308708775532697 第 2 趟12030861707553268797 第 3 趟03081261705326758797 第 4 趟03081261532670758797 第 5 趟03081253266170758797 第 6 趟03081226536170758797 第 7 趟03081226536170758797 第 8 趟03081226536170758797 第 9 趟03081226536170758797 3 直接插入排序 初始序列 61 871203087097755326 第 1 趟 6187 1203087097755326 第 2 趟 126187 03087097755326 第 3 趟 03126187 087097755326 第 4 趟 0308126187 7097755326 第 5 趟 030812617087 97755326 第 6 趟 03081261708797 755326 第 7 趟 0308126170758797 5326 第 8 趟 030812536170758797 26 第 9 趟 03081226536170758797 22 第200页 第 3 题 在带表头结点的单链表上实现简单选择排序 template void SingleList select sort Node p r small p first link if p for p link p p link for small p r p link r r r link if small data r data small r if small p swap p data small data 直接插入排序 template 用带表头节点的单链表存储 void SingleList DirInsert Node head q p1 p2 if first link 课后答案网 head first link link head 是待插入元素的链表头 first link link NULL first 是只有一个节点的有序链表 while head q head head head link 从待插入链中取下一个节点 p1 first p2 first link p1 是 p2 的直接前驱节点 while p2p2 p2 link if p2 q 插入在 p1 和 p2 之间 q link p2 p1 link q else q 插入在 p2 之后 即有序链的最后 q link NULL p1 link q 10 4 template void sort T a int n int i j k 0 m 1 s t T x while k m s k for i k ia i 1 x a i a i a i 1 a i 1 x s i m s t m for j m j k j 从下向上冒泡 if a j a j 1 x a j a j a j 1 a j 1 x t j k t 10 6 证明 快速排序算法的基本思想时 每次把一个集合划分成大于和小于某个基准值的两个子集 合 最坏情况是两个子集合中总有一个是空集合 即将一个集合分成了一个子集合和一个作为 基准值的元素 即最坏情况下划分的自己和比原集合的元素只少一个 故要划分 n 1 次才能使 得子集合中的元素少于 2 而每次划分子集合都要扫描整个集合 所以时间复杂度是 O n2 10 7 template 方法一 void sort T a int n int i 0 j n 1 T x a 0 while i 0 找负数 课后答案网 if j i a i a j while a i 0 找正数if i j a j a i a j x 10 8 template void Merge T A T Temp int i1 int j1 int i2 int j2 int else if A i1 A i2 Temp k A i1 Merge A Temp i1 1 j1 i2 j2 k else Temp k A