4. 给定一个关键字序列{24，19，32，43，38，6，13，22}，请写出快速排序第一趟的结果；堆排序时所建的初始堆；归并排序的全过程。然后回答上述三中排序方法中那一种方法使用的辅助空间最少？在最坏情况下那种方法的时间复杂度最差？
作业题（五）
一、单项选择题
1. 一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。 A．(38,40,46,56,79,84) B．(40,38,46,79,56,84) C．（40,38,46,56,79,84) D．(40,38,46,84,56,79)
2．广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为
（
）
。
GetHead(GetTail(GetHead(GetTail(GetTail(A)))))
A. (g) B. (d) C. c D. d 3．对于有n 个结点的二叉树, 其高度为（ ）
A．nlog2n B．log2n C．?log2n?+1 D．不确定
4. 如图所示，给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先搜索得到的顶点序列是（ ）。 A．1 3 5 4 2 6 7 B．1 3 4 7 6 2 5 C．1 5 3 4 2 7 6 D．1 2 4 7 6 5 3
5. 采用邻接表存储的图，其深度优先遍历类似于二叉树的（ ）。
A．中序遍历 B．先序遍历 C．后序遍历 D．按层次遍历
6. 已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={
A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7 C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7
7. 顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（ ）。在此假定N为线性表中结点数，且每次查找都是成功的。 A．N+1 B．2log2N C．log2N D．N
8. 下面关于m阶B树说法正确的是（ ）。 ①每个结点至少有两棵非空子树； ②树中每个结点至多有m一1个关键字；
③所有叶子在同一层上； ④当插入一个数据项引起B树结点分裂后，树长高一层。 A．①②③ B．②③ C．②③④ D．③
9. 已知一个线性表（38，25，74，63，52，48），假定采用h(k)=k%7计算Hash地址进行散列存储，若利用链地址法处理冲突，则在该Hash表上进行查找的平均查找长度为（ ）。
A．1.0 B．7/6 C．4/3 D．3/2
10. 在排序算法的实施过程中，使用辅助存储空间为O（1）的有（ ）。
A．简单排序法 B.快速排序法 C．归并排序法 D.基数排序法 二、填空题
1. n（n大于1）个结点的各棵树中，其中深度最大的那棵树的深度是n，它共有________个叶子结点和________个非叶子结点。
2.设一棵后序线索树的高是50，结点x是树中的一个结点，其双亲是结点y,y的右子树高度是60，x是y的左孩子。则确定x的后继最多需经过________中间结点（不含后继及x本身）
3.高度为2（第2层为叶子）的3阶B-树中，最多有________个关键字。
4.分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为无序的表，则平均情况下最省时间的是________算法。
5.简单选择排序和起泡排序中比较次数与序列初态无关的算法有________。
6. 串的链式存储结构是将存储区域分成一系列大小相