数据结构课后习题答案讲解ppt课件.ppt

23 03 2020 1 第一章习题讲解 1 19 确定下列各程序段的程序步 确定划线语句的执行次数 计算它们的渐近时间复杂度 1 i 1 k 0 do k k 10 i i while i n 1 划线语句的执行次数为n 1 渐近时间复杂度为O n 2 i 1 x 0 do x i 2 i while i n 划线语句的执行次数为 log2n 渐近时间复杂度为O log2n 23 03 2020 2 3 for inti 1 i y 1 y 1 y 划线语句的执行次数为 n1 2 渐近时间复杂度为O n1 2 23 03 2020 3 2 4 Loc A i j k 134 i n p j p k 2 第二章习题讲解 23 03 2020 4 2 9 设有长度为n的一维整型数组A 设计一个算法 将原数组中的元素以逆序排列voidInvert Telements intlength length数组长度 elements 为需要逆序的数组 Te for inti 1 i length 2 i e elements i 1 elements i 1 elements length i elements length i e 23 03 2020 5 2 12 设计一个算法 将单链表中结点以逆序排列 逆序的单链表中的结点均为原表中的结点 Node pInvert Node first Node p first q first NULL while p q p Link p Link first first p p q returnfirst 23 03 2020 6 3 1 设A B C D E五个元素依次进栈 进栈后可立即出栈 问能否得到下列序列 若能得到 则给出相应的push和pop序列 若不能 则说明理由 1 A B C D E 1 能得到该序列 相应的push和pop序列为 push A pop push B pop push C pop push D pop push E pop 第三章习题讲解 23 03 2020 7 3 1 设A B C D E五个元素依次进栈 进栈后可立即出栈 问能否得到下列序列 若能得到 则给出相应的push和pop序列 若不能 则说明理由 2 A C E B D 2 不能得到该序列 在E出栈时 B和D在栈中 B比D先进栈 所以D应比B先出栈 第三章习题讲解 23 03 2020 8 3 不能得到该序列 在C出栈时 A和B在栈中 A比B先进栈 所以B应比A先出栈 3 1 设A B C D E五个元素依次进栈 进栈后可立即出栈 问能否得到下列序列 若能得到 则给出相应的push和pop序列 若不能 则说明理由 3 C A B D E 23 03 2020 9 4 能得到该序列 相应的push和pop序列为 push A push B push C push D push E pop pop pop pop pop 3 1 设A B C D E五个元素依次进栈 进栈后可立即出栈 问能否得到下列序列 若能得到 则给出相应的push和pop序列 若不能 则说明理由 4 E D C B A 23 03 2020 10 第四章习题讲解 4 1 设线性表采用顺序表示方式 并假定顺序表是有序的 设表中元素已按非递减次序排列 编写函数 实现线性表的如下运算 1 intSearch Insert List lst Tx 后置条件 在有序的顺序表中搜索元素x 若x在表中 则返回x在表中的位置 否则 若表未满 则在表中插入新元素x 并且插入后 线性表仍然是有序的 返回新元素x的位置 若表已满 无法插入新元素 则返回 1 23 03 2020 11 intSearch Insert List lst Tx inti j for i 0 x lst Elements i 插入新元素并返回该元素的位置 23 03 2020 12 4 1 设线性表采用顺序表示方式 并假定顺序表是有序的 设表中元素已按非递减次序排列 编写函数 实现线性表的如下运算 2 voidSearch Delete List lst Tx Ty 前置条件 x y后置条件 删除有序表中元素值在x和y之间 含x和y 的所有元素 23 03 2020 13 voidSearch Delete List lst Tx Ty if lst Size 0 printf Thelistisempty return 1 inti j sum 0 for i 0 temp i n 1 return 没有符合条件的元素for j i lst j y for j i jy 大于y的元素前移lst i lst j else 小于等于y的元素删除 j n 23 03 2020 14 4 6给出下列稀疏矩阵的行优先和列优先顺序存储的行三元组和列三元组表示 列三元组 4 7求对题图4 1的稀疏矩阵执行矩阵转置时数组num 和k 的值 行三元组 23 03 2020 15 6 2 对于三个结点A B和C 可分别组成多少不同的无序树 有序树和二叉树 1 无序树 9棵 2 有序树 12棵 3 二叉树 30棵 3棵 6棵 6棵 6棵 各6棵 第六章习题讲解 23 03 2020 16 6 3 设在度为m的树中 度为1 2 m的节点个数分别为n1 n2 nm 求叶子节点的数目 设度为0的节点个数为n0则 树的总度数 节点总个数 1即 1 n1 2 n2 m nm n0 n1 n2 n3 nm 1因此叶子节点数目为 n0 n2 2 n3 m 1 nm 1 23 03 2020 17 6 5 找出所有二叉树 其节点在下列两种次序下恰好都以同样的次序出现 1 先序和中序 2 先序和后序 3 中序和后序 1 或者为空二叉树 或者所有结点的左子树都是空的单支树 2 或者为空二叉树 或者只有根结点的二叉树 3 或者为空二叉树 或者所有结点的右子树都是空的单支树 23 03 2020 18 6 6 设对一棵二叉树进行中序遍历和后序遍历的结果分别为 1 中序遍历 BDCE A FHG 2 后序遍历 DECB HGF A画出该二叉树 23 03 2020 19 6 7写出下图中二叉树的先序 中序和后序遍历结果 先序 DEHFJGCKAB中序 HEJFGKCDAB后序 HJKCGFEBAD 23 03 2020 20 intSizeL BTreeBt returnSizeofLeaf Bt Root intSizeofLeaf BTNode p if p return0 if p RChild 6 8 设二叉树以二叉链表存储 试编写求解下列问题的递归算法 3 求一棵二叉树中的叶结点个数 23 03 2020 21 4 设计算法 交换一棵二叉树中每个结点的左 右子树 voidExchBt BTreeBt Exch Bt Root voidExch BTNode p if p BTNode q p LChild p LChild p RChild p RChild q Exch p LChild Exch p RChild 23 03 2020 22 6 13 将上图中的树转换成二叉树 并将下图中的二叉树转换成森林 23 03 2020 23 6 18 设S A B C D E F W 2 3 5 7 9 12 对字符集合进行哈夫曼编码 W为各字符的频率 1 画出哈夫曼树 2 计算带权路径长度 3 求各字符的编码 A 1010B 1011C 100D 00E 01F 11 加权路径长度 WPL 2 3 4 5 3 7 9 12 2 91 23 03 2020 24 7 4为什么说对半搜索算法只适用于顺序有序表的情况 为什么说顺序搜索可用于顺序表和链表 也不受表的有序性限制 解 1 对半搜索算法必须针对顺序存储的有序表 要求满足两个条件 1 顺序存储 只有顺序存储才可以根据元素下标 地址 随机存取元素 2 有序存储 只有有序存储才可以其实现对半查找 2 顺序搜索从头到尾逐个查找 所以可用于顺序表和链表 也不受表的有序性限制 23 03 2020 25 补充 已知 1 2 3 4 5 6 7 8 9 10 11 找到9比较几次 解 第一次比较 M 1 11 2 6 6 9 找 7 11 第2次比较 M 7 11 2 9 9 9 成功 所以一共比较2次成功 23 03 2020 26 8 1建立37 45 91 25 14 76 56 65为输入时的二叉搜索树 再从该树上依次删除76 45 则树形分别如何 建成的二叉树 23 03 2020 27 8 1建立37 45 91 25 14 76 56 65为输入时的二叉搜索树 再从该树上依次删除76 45 则树形分别如何 删除76后 23 03 2020 28 8 1建立37 45 91 25 14 76 56 65为输入时的二叉搜索树 再从该树上依次删除76 45 则树形分别如何 删除45后 23 03 2020 29 8 3已知对一棵二叉搜索树进行先序遍历的结果是 28 25 36 33 35 34 43 请画出此二叉搜索树 23 03 2020 30 9 3设散列表ht 11 散列函数h key key 11 采用线性探查法 二次探查法解决冲突 试用关键字值序列 70 25 80 35 60 45 50 55分别建立散列表 线性探查法 23 03 2020 31 9 3设散列表ht 11 散列函数h key key 11 采用线性探查法 二次探查法解决冲突 试用关键字值序列 70 25 80 35 60 45 50 55分别建立散列表 二次探查法 0 45 35 80 25 70 60 50 55 1 2 3 4 5 6 7 8 9 10 23 03 2020 32 9 4对上题的例子 若采用双散列法 试以散列函数h1 key key 11 h2 key key 9 1建立散列表 对80 3 1 9 11 1对45 1 1 1 11 2 1 2 1 11 3 1 3 1 11 4 1 4 1 11 5 1 5 1 11 6对50 6 1 6 11 1 6 2 6 11 7 23 03 2020 33 10 1对如图所示的有向图 求 1 每个顶点的入度和出度 2 强连通分量 3 邻接矩阵 1 各个顶点的入度和出度 顶点入度出度030122212312423511 2 强连通分量 3 邻接矩阵 000000100100010010001010110001100000 23 03 2020 34 10 2从只有6个顶点没有边的图开始 以边 的次序 通过使用程序10 4的Add函数插入这些边 建立该图的邻接表结构 请画出所建成的邻接表结构 23 03 2020 35 10 4已知有向图的邻接表 写出计算各个顶点的入度的算法 voidDegree Graphg int d inti intn g Vertices Enode p for i 0 inextArc d p adjVex for i 0 i n i cout d i d i 23 03 2020 36 10 6在题10 2所建立的邻接表上进行以顶点2为起点顶点的深度优先搜索和宽度优先搜索 分别画出遍历所得到的深度优先搜索和宽度优先搜索的生成森林 或生成树 题10 2所建立的邻接表对应的图为 23 03 2020 37 以顶点2为起点顶点的深度优先搜索所得到深度优先搜索生成树 深度优先遍历 2 4 5 0 1 3 23 03 2020 38 以顶点2为起点顶点的宽度优先搜索所得到宽度优先搜索生成树 宽度优先遍历 2 4 1 5 0 3 23 03 2020 39 10 14使用普里姆算法以1为源点 画出图10 27的无向图的最小代价生成树 4 2 5 0 3 1 1 7 2 1 5 Prim算法以1为源点 生成的最小代价生成树为 23 03 2020 40 11 2设有记录序列 61 87 12 03 08 70 97 75 53 26 现按下列算法对它分别进行排序 请手工模拟算法的执行过程 给出每趟排序结果 1 直接插入排序 3 冒泡排序 4 快速排序 5 简单选择排序 23 03 2020 41 1 直接插入排序初始序列 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 23 03 2020 42 3 冒泡排序 注意冒泡排序只排了7趟 初始序列 61871203087097755326 第1趟61120308708775532697第2趟12030861707553268797第3趟03081261705326758797第4趟03081261532670758797第5趟03081253266170758797第6趟03081226536170758797第7趟03081226536170758797 23 03 2020 43 4 快速排序初始序列61871203087097755326第1趟 53261238 61 97757087 第2趟 826123 5361 97757087 第3趟 3 8 1226 5361 97757087 第4趟3812 26 5361 97757087 第5趟3812265361 877570 97第6趟3812265361 7075 8797第7趟381226536170 75 8797 23 03 2020 44 5 简单选择排序初始序列61871203087097755326第1趟 03 871261087097755326第2趟 0308 1261877097755326第3趟 03