数据结构习题课7ppt课件.ppt

数据结构习题第7章 吉林大学计算机科学与技术学院谷方明 1 第7章作业 247页 每组的第1题是必交的 即7 2 7 5 7 18 7 24 7 497 2 7 3 7 5 7 8 7 10 7 18 7 24 7 26 7 30 7 31 7 35 7 367 49 7 50 2 7 2 若对序列 7 3 1 8 6 2 4 5 按从小到大排序 请写出冒泡排序的第一趟结果 3 参考答案3 1 7 6 2 4 5 8 4 7 3 设文件 R1 R2 Rn 以单链表方式表示 指针变量FIRST指向表头结点 且表中的结点结构为 其中KEY为该结点的关键词域 LINK为链接域 请给出这种线性表的直接插入排序算法 并要求算法的时间复杂度为O n2 且算法是稳定的 5 算法InsertSort FIRST FIRST 对单链表直接插入排序 FIRST指向表头结点 IS1 边界 IF LINK FIRST NULLORLINK LINK FIRST NULL THENRETRUN IS2 插入排序 q LINK FIRST q0 LINK q WHILE qNULL p LINK FIRST p0 FIRST WHILE KEY p q DO p0 p p LINK p IF KEY p KEY q THEN LINK q0 LINK q LINK p0 q LINK q p q LINK q0 ESLE q0 q q LINK q0 6 7 5 设计一算法 在尽可能少的时间内重排数组 使所有取负值的关键词放在所有取非负值的关键词之前 并分析算法的时间复杂度 7 基本思想 以0为基准记录 使用快速排序的一次分划过程即可 时间复杂度为O n 8 算法Part A n A 以0为基准元素一次分划 P1 初始化 i 1 j n P2 以0分划 WHILEi0ANDi jDOj j 1 IFi jTHENRi Rj 9 7 8 讨论冒泡排序算法的稳定性 10 参考答案 冒泡排序中 每一趟冒泡 相邻的关键词只有满足 Rj Rj 1 时才会发生交换 关键词相同的记录不会发生交换 即相同位置不变 因此是冒泡排序算法是稳定的 11 7 10 类似于冒泡过程 从下到上 与之对应的是下沉过程 从上到下 如果排序是冒泡和下沉的交替过程 证明如果经过一趟冒泡和一次下沉后发现Rj和Rj 1 1 j n 1 没有交换 则它们已经进入最终排序位置 12 参考答案 证明 如果经过一趟冒泡和一次下沉后发现Rj和Rj 1 1 j n 1 没有交换 那么有R1 R2 R3 Rn即所有记录已经进入最终排序位置 13 7 18 奇偶交换排序算法的基本思想描述如下 排序过程通过对文件x i l i n 的若干次扫描来完成 第奇数次扫描 对所有下标为奇数的记录x i 与其后面的记录x i 1 l i n 1 相比较 若x i KEY x i 1 KEY 则交换x i 和x i 1 的内容 第偶数次扫描 对所有下标为偶数的记录x i 与其后面的记录x i 1 2 i n 1 相比较 若x i KEY x i 1 KEY 则交换x i 和x i 1 之内容 重复上述过程直到排序完成为止 14 1 排序的终止条件是什么 2 完成该算法的具体设计 3 分析该算法的平均运行时间 15 算法Sort X n S1 一趟扫描过程中 均没有记录交换则算法终止 change 1 while change change 0 fori 1ton 1step2 奇交换if X i key X i 1 key X i X i 1 change 1 fori 2ton 1step2 偶交换if X i key X i 1 key X i X i 1 change 1 16 1 最好情况下 比较一趟 每趟中奇交换偶交换比较次数共 n 1 次 无记录交换 正序 2 最坏情况下比较 n 2 1趟 总比较次数为 n 1 n 2 1 次 每次比较都交换 总交换次数为 n 1 n 2或 n 1 3n 2 逆序 3 最好时间O n 最坏时间O n2 平均时间O n2 书上P201反序对的平均数 17 正确性证明 数学归纳法 对元素个数n进行归纳当n 1是 算法正确假设当n k时 算法能对n个元素的数组进行排序 则当n k 1时 进行一趟分划后 轴心元素R s 进入了最终排序应在的位置R i 即R i 之前的元素R s R i 1 都小于等于R i R i 之后的元素R i 1 R e 都大于等于R i 由于R s R i 1 R i 1 R e 任意一部分最多为k个 按照假设 都能正确排序 因此 该算法能对全部k 1个元素正确排序 18 7 24 填充如下排序算法中的方框 并证明该算法的正确性 实质是一趟快速排序算法 算法PartA R s e 分划文件 Rs Rs 1 Re 且Ks 1 Ke 1 PA1 初始化 i s j K Ks R Rs e 1 19 PA2 分划过程 whilei jdo j j 1 while doj j 1 if i j thenj i else Ri Rj i i 1 whileKi Kdoi i 1 if thenRj Ri PA3 Kj K i j Rj R 20 7 26 分析算法HSort中的堆栈S可能包含的最大元素个数 表示成M和n的函数 21 参考答案 当n 2 M 才会在辅助堆栈中压入第1个元素当n 22 M 才会在辅助堆栈中压入第2个元素 依此类推 当n 2k M 才会在辅助堆栈中压入第k个元素则2k n M k log2 n M 因此最多为floor log2 n M 个 22 7 30 证明 用淘汰赛找n个元素的最大元素正好需要n 1次元素比较 23 参考答案 证明 在淘汰赛中 每进行一场比赛 即进行依次比较 都恰淘汰1个元素 找到最大元素需要淘汰n 1个元素 因此需要n 1比较 24 7 31 证明 用淘汰赛找n个元素的最大元素所形成的树高为 log2n 25 参考答案 证明 当n 2K时 第1轮后剩下n 2 2K 1 第二轮后剩下n 4 2K 2 依次类推 第k轮淘汰赛后就剩下1个选手 就是最大元素 每一轮淘汰赛都对应比赛树中的一层 因此当n 2K时 比赛树的最大层数是k 比赛树的高度是log2n当n为任意数时 总可以找到一个k 使得2K 1 n 2k 只需要k轮淘汰赛就可以最大元素 对应的比赛树高为k 由2K 1 n 2k 得log2n k log2n 1 即形成的树高为 log2n 26 7 35 设文件 R1 R2 Rn 是一个堆 Rn 1是任意一个结点 请设计一个算法 该算法把Rn 1添加到堆 R1 R2 Rn 中 并使 R1 R2 Rn Rn 1 成为一个堆 要求算法的时间复杂度为O log2n 分析 堆有大根堆和小根堆 教材上用的是大根堆 27 参考答案 算法Insert R n x R n 在堆中插入元素x 从下往上调整堆 U1 x放入R n 1 n n 1 R n x U2 从下往上调整 称上浮 i n WHILE i 1ANDR i 2 R i DOi i 2 28 C inth MAXN intn 0 voidinsert x h n x for intj n j 1 j 1 上浮if a j a j 1 swap a j a j 1 29 7 36 文件 R1 R2 Rn 是一个堆 1 i n 请给出一个算法 该算法从 R1 R2 Rn 中删除Ri 并使删除后的文件仍然是堆 要求算法的时间复杂度为O log2n 30 参考答案 算法Delete R n i R n 在堆中删除元素R i 从上往下调整堆 D1 R i 与R n 交换 R i R n n n 1 D2 从上往下调整 称下沉 j i WHILE 2 jR j OR2 j 1R j DO y 2 j IF 2 j 1R 2 j THENy y 1 R j R y j y 31 C inth MAXN intn 0 voiddelete inti h i h n while 2 ih i 2 i 1h i inty 2 i if y 1h y y swap h i h y i y 32 7 49 填充如下排序算法中的方框 并讨论该算法的稳定性 算法C R n 比较计数 本算法按关键词K1 K2 Kn排序记录R1 R2 Rn 一维数组COUNT 1 n 用来记录各个记录的排序位置 33 C1 FORi 1TOnDO C2 FORi nTO2 DOFORj i 1TO1STEP 1DOIF THENCOUNT j COUNT j 1ELSE STEP 1 Kj Ki count i count i 1 count i 1 34 稳定性讨论 该算法是稳定的 35 7 50 有一种简单的排序算法 叫做计数排序 CountSorting 这种排序算法对一个待排序的表 用数组表示 进行排序 并将排序结果存放到另一个新的表中 必须注意的是 表中所有待排序的关键词互不相同 计数排序算法针对表中的每个记录 扫描待排序的表一趟 统计表中有多少个记录的关键词比该记录的关键词小 假设针对某一个记录 统计出的计数值为c 那么 这个记录在新的有序表中的合适的存放位置即为c 1 给出适用于计数排序的数据表定义