大学数据结构.pptVIP

１.８.３ 选择类排序法 （1）简单选择排序法最坏情况需要n(n-1)/2次比较； （2）堆排序法 最坏情况需要O(nlog2n)次比较。 在深度为7的满二叉树中，叶子结点的个数为______。 A）32 　　B）31 　　C）64 　　D）63 对下列二叉树： 进行中序遍历的结果是______。 A）ACBDFEG 　　 B）ACBDFGE 　　 C）ABDCGEF 　　 D）FCADBEG F C E A D G B 某二叉树中有n个度为2的结点,则该二叉树中的叶子结点数为_______。 A）n+1 B）n-1 C）2n 　D）n/2 一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为_______。 A）219 B）221 C）229 D）231 一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为 。 设一棵完全二叉树共有839个结点，则该二叉树中有 个叶子结点。 对于长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为_______。 A）log2n B） n/2 C） n D） n+1 下列叙述中正确的是______。 A）对长度为n的有序链表进行查找，最坏的情况需要比较次数为n。 B）对长度为n的有序链序表进行对分查找，最坏的情况需要比较次数为（n/2）。 C）对长度为n的有序链序表进行对分查找，最坏的情况需要比较次数为（log2n）。 D）对长度为n的有序链序表进行对分查找，最坏的情况需要比较次数为（nlog2n）。 对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为 。 栈顶指针和栈中元素之间的关系 base A B C D E top top 指向栈顶元素 栈的顺序存储及运算 栈的链式存储 若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。如图所示。 由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。 队列及其基本运算 队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。 例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。 下图是队列的示意图： 　　　　　 　　　　　　 a1　a2　…　an 　　 　　　　　 插入端和删除端都是浮动的。通常我们将插入端称为队尾，用一个“队尾指针”指示；而删除端被称为队头，用一个“队头指针”指示。 结论：先进先出（First In First Out），简称为FIFO线性表。 出队 入队 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。 队列是“先进行出”（FIFO）或“后进后出”（LILO）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。 队列基本运算 队列的顺序存储结构 实现：用一维数组实现sq[M] front=-1 rear=-1 1 2 3 4 5 0 队空 1 2 3 4 5 0 front J1,J1,J3入队 J1 J2 J3 rear rear 1 2 3 4 5 0 J4,J5,J6入队 J4 J5 J6 front 设两个指针front,rear,约定： rear指示队尾元素； front指示队头元素前一位置 初值front=rear=-1 空队列条件：front==rear 入队列：sq[++rear]=x; 出队列：x=sq[++front]; rear rear front rear 1 2 3 4 5 0 J1,J2,J3出队 J1 J2 J3 front front front 存在问题 设数组维数为M，则： 当f