第一章数据结构与算法题库.ppt

2．中序遍历（LDR） 　　中序遍历是指首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。 　　例如，对图 中的二叉树进行中序遍历，则遍历结果为DGBAHEICF。 第一章　数据结构与算法 3．后序遍历（LRD） 　　后序遍历是指首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。 　　例如，对图 中的二叉树进行后序遍历，则遍历结果为GDBHIEFCA。 第一章　数据结构与算法 考题（2005_4） 1.某二叉树中度为2的结点有18个，则该二叉树中有__[1]__个叶子结点。 答案：19 第一章　数据结构与算法 考题（2011_3） 某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为(假设根结点在第1层) A)3 B)4 C)6 D)7 答案：D 第一章　数据结构与算法 查找与排序技术 顺序查找 　　顺序查找又称为顺序有哪些信誉好的足球投注网站。 　　顺序查找一般是指在线性表中查找指定的元素，基本方法如下：从线性表的第一个元素开始，依次将线性表中的元素与被查找元素进行比较，若相等则表示找到（即查找成功）；若线性表中所有的元素都与被查元素进行了比较，但都不相等，则表示线性表中没有要查找的元素（即查找失败）。 第一章　数据结构与算法 二分法查找 　　二分法查找只适用于顺序存储的有序表，即要求线性表中的元素按元素值的大小排列（递减排列或递增排列）。假设有序线性表是按元素值递增排列的，并设表的长度为n，被查元素为x，则二分法查找过程如下： 第一章　数据结构与算法 将x与线性表的中间元素进行比较： 　　若中间元素的值等于x，则说明查成功，查找结束； 　　若x小于中间元素的值，则在线性表的前半部分以相同的方法查找； 　　若x大于中间元素的值，则在线性表的后半部分以相同的方法查找。 　　这个过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）为止。 　 第一章　数据结构与算法 第一章　数据结构与算法 　　可以看出，当有序的线性表为顺序存储时才能采用二分查找。可以证明，对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次，顺序查找需要比较n次。可见，二分查找的效率要比顺序查找高得多。 第一章　数据结构与算法 交换类排序法 1．冒泡排序法 　　冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序的。冒泡排序法的操作过程如下： 　　首先，从表头开始往后扫描线性表，在扫描过程中依次比较相邻两元素的大小，若前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后。 第一章　数据结构与算法 　　然后，按相反的方向扫描剩下的线性表，在扫描过程中依次比较相邻两个元素的大小，若后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。 　　显然，在扫描过程中，不断地将两相邻元素中的小者往前移动,最后就将剩下的线性表中的最小者换到了表的最前面。 　　此时，线性表的第一个元素就是最小者，最后一个元素就是最大者。 　　对剩下的元素构成的线性表重复上述过程，直到剩下的元素为空或者在扫描过程中没有交换任何元素，此时，线性表变为有序。 第一章　数据结构与算法 　　图 是冒泡排序法的示意图。图中有下划线的 元素表示扫描过程中的第一个和最后一个元素的位置。 　　从冒泡排序法的操作过程可以看出，对长度为 n的线性表，在最坏的情况下需要进行 （n-1）+（n-2）+…+2+1=n（n-1）/2次比较。 第一章　数据结构与算法 原序列 6 2 8 1 3 1 9 5 7 第1遍（从前往后） 2 6 1 3 1 8 5 7 9 （从后往前） 1 2 6 1 3 5 8 7 9 第2遍（从前往后） 1 2 1 3 5 6 7 8 9 （从后往前） 1 1 2 3 5 6 7 8 9 第3遍（从前往后） 1 1 2 3 5 6 7 8 9 最后结果 1 1 2 3 5 6 7 8 9 第一章　数据结构与算法 2．快速排序法 快速排序法是对冒泡排序法的改进，又叫作分区交换排序法。快速排序法的基本思想如下： 从线性表中任意选取一个元素（通常选第一个元素），设为T，将线性表中小于T的元素移到T的前面，而大于T的元素移到T的后面，结果就将线性表分成了两部分（称为两个子表），T处于分界线的位置处，这个过程称为线性表的分割。通过对线性表的一次分割，就以T为分界线，将线性表分成了前后两个子表，且前面子表中的所有