（4）按照“后进先出”原则组织数据的数据结构是（064)A）队列R栈1D）二叉树C）双向链表I1111111(5)下列叙述中正确的是(064)I111线性链表是线性表的链式存储结构1B)栈与队列是非线性结构1IAC)1双向链表是非线性结D)只有根结点的二又树是线性结构CB(6))对如下二叉树(064)11111FDE11进行后序遍历的结果为1A)ABCDEFDB)DBEAFCCC）ABDECFDEBFCA1（7）在深度为7的满二叉树中，叶子结点的个数为（064)1V) 64D) 63A)32B) 311第26页
第26页 （4）按照“后进先出”原则组织数据的数据结构是 (064) A）队列 B）栈 C）双向链表 D）二叉树 √ （5）下列叙述中正确的是 (064) A）线性链表是线性表的链式存储结构 B）栈与队列是非线性结构 C）双向链表是非线性结构 D）只有根结点的二叉树是线性结构 （6）对如下二叉树 (064) 进行后序遍历的结果为 A）ABCDEF B）DBEAFC C）ABDECF D）DEBFCA （7）在深度为7的满二叉树中，叶子结点的个数为 (064) A）32 B）31 C）64 D）63 √ √ √
四、查找技术与排序技术（1）顺序查找：无序表或链式存储结构线性表。方法：从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到。若线性表中所有元素都与被查元素进行比较但都不相等，则表示线性表中没有要找的元素。顺序查找的效率是很低的。对于长度为n的线性表，在最坏的情况下，需要比较n次；在平均情况下，需要比较n/2次。第27页
第27页 四、 查找技术与排序技术 （1） 顺序查找：无序表或链式存储结构线性表。 方法：从线性表的第一个元素开始，依次将线 性表中的元素与被查元素进行比较，若相等则表示 找到。若线性表中所有元素都与被查元素进行比较 但都不相等，则表示线性表中没有要找的元素。 顺序查找的效率是很低的。对于长度为n的线 性表，在最坏的情况下，需要比较n次；在平均情 况下，需要比较n/2次
1(2)二分法香找：必须是有序表方法：将被查元素X与线性表的中间项的值进行比较，若相等则表示找到。若X小于中间项的值，则在线性表的前半部分以相同的方法进行查找：若X大于中间项的值，则在线性表的后半部分以相同的方法进行查找。1二分法的效率要比顺序查找高的多。对于长度为n的有序线性表，在最坏的情况下，只需要比较log2n次。景1第28页
第28页 （2）二分法查找：必须是有序表。 方法：将被查元素X与线性表的中间项的值进行 比较，若相等则表示找到。若X小于中间项的值，则 在线性表的前半部分以相同的方法进行查找；若X大 于中间项的值，则在线性表的后半部分以相同的方法 进行查找。 二分法的效率要比顺序查找高的多。对于长度为n 的有序线性表，在最坏的情况下，只需要比较log2n次
吉祥（3）交换类排序它泡排序法是一种最简单的交换类排序方法，是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为n，则在最坏的情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2次。快速排序法也是一种交换类的排序方法。它是从线性表中选取一个元素工，将表中元素与工比较，小者在前，大者在后，分成两个子表；然后在不断地进行同样的分割。直到所有子表为空。在最坏的情况下，需要的比较次数为n次。第29页
第29页 （3）交换类排序： 冒泡排序法是一种最简单的交换类排序方法，它 是通过相邻数据元素的交换逐步将线性表变成有序。 假设线性表的长度为n，则在最坏的情况下，冒 泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从 后往前的扫描，需要的比较次数为n(n-1)/2次。 快速排序法也是一种交换类的排序方法。它是从 线性表中选取一个元素T，将表中元素与T比较，小 者在前，大者在后，分成两个子表；然后在不断地进 行同样的分割。直到所有子表为空。在最坏的情况下， 需要的比较次数为n次
吉祥（4）插入类排序：所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。简单插入排序法是从线性表的第2个元素开始直到最后一个元素，逐次将其中的每个元素插入到前面已经有序的子表中。在最坏的情况下，需要的比较次数为n(n-1)/2次。希尔排序法属于插入类排序，但它对简单插入排序做了较大的改进。它是将整个无序序列分割成若于小的子序列分别进行插入排序。在最坏的情况下，需要的比较次数为n1.5次。第30页
第30页 （4）插入类排序： 所谓插入排序，是指将无序序列中的各元素依次插 入到已经有序的线性表中。 简单插入排序法是从线性表的第2个元素开始直到 最后一个元素，逐次将其中的每个元素插入到前面已经 有序的子表中。在最坏的情况下，需要的比较次数为 n(n-1)/2次。 希尔排序法属于插入类排序，但它对简单插入排序 做了较大的改进。它是将整个无序序列分割成若干小的 子序列分别进行插入排序。在最坏的情况下，需要的比 较次数为n1.5次