二级Access数据结构与算法.ppt

在深度为5的满二叉树中，叶子结点的个数为 A) 32 B) 31 C) 16 D) 15 若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是 A) bdgcefha B) gdbecfha C) bdgaechf D) gdbehfca 在树结构中，树根结点没有 【1】 。 下列叙述中正确的是 A) 线性表是线性结构 B) 栈与队列是非线性结构 C) 线性链表是非线性结构 D) 二叉树是线性结构 * 具有3个结点的二叉树有 A) 2种形态 B) 4种形态 C) 7种形态 D) 5种形态 设有下列二叉树： 对此二叉树前序遍历的结果为 A) ZBTTCPXA B) ATBZXCTP C) ZBTACTXP D) ATBZXCPT * 设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为 A) 12 B) 13 C) 14 D) 15 设有下列二叉树： 对此二叉树的中序遍历的结果为 A) ABCDEF B) DBEAFC C) ABDECF D) DEBFCA * 设树T的深度为4,其中度为1、2、3、4的结点个数分别为4、2、1、1。则T中的叶子结点数为 A）8 B）7 C）6 D）5 设一棵完全二叉树共有700个结点，则该二叉树中有（ ）个叶子结点。 在一个容量为15的循环队列中，若头指针front=6，尾指针rear=9，则该循环队列中共有（ ）个元素。 设一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为（ ）。 * 1.7 查找和排序 顺序查找与二分查找算法 基本排序算法（交换类排序、选择类排序、插入类排序） * 1.7.1 查找 查找是在一个给定的数据结构中，根据给定的条件查找满足条件的结点。不同的数据结构采用不同的查找方法。查找的效率直接影响数据处理的效率。 查找的结果： 查找成功：找到满足条件的结点 查找失败：找不到满足条件的结点。 * 1.7.1.1 顺序查找（线性查找） 查找过程： 对给定的一关键字K，从线性表的一端开始，逐个进行记录的关键字和K的比较，直到找到关键字等于K的记录或到达表的另一端。 可以采用从前向后查，也可采用从后向前查的方法。 · 在平均情况下，大约要与表中一半以上元素进行比较，效率较低。平均查找长度较大。 · 在下面两种情况下只能采取顺序查找： a. 线性表为无序表（元素排列是无序的）； b. 即使是有序线性表，但采用的是链式存储结构。 * 1.7.1.2 折半查找（二分法查找） 思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。 前提：必须在具有顺序存储结构的有序表中进行。 分三种情况： 1）若中间项的值等于x,则说明已查到。 2）若x小于中间项的值，则在线性表的前半部分查找； 3）若x大于中间项的值，则在线性表的后半部分查找。 特点：比顺序查找方法效率高。最坏的情况下，需要比较 log2n次。 * 查找23和79的过程如下图： mid=(low+high)/2不进位取整 ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) low high mid ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) low high=mid-1 mid ( 08, 14, 23, 37, 46, 55, 68, 79, 91 ) low=mid+1 high mid ( 08, 14, 23, 37, 46, 55,