（5）试对图7.7所示的AOE-网：
① 求这个工程最早可能在什么时间结束； ② 求每个活动的最早开始时间和最迟开始时间；
③ 确定哪些活动是关键活动
图7.7 AOE-网
第9章 查找
1．选择题
（1）对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）。 A．(n-1)/2 B． n/2 C．(n+1)/2 D．n （2）适用于折半查找的表的存储方式及元素排列要求为（ ）。
A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序
（3）当在一个有序的顺序表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（ ）。
A．必定快 B．不一定
C．在大部分情况下要快 D．取决于表递增还是递减 （4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（ ）比较大小，查找结果是失败。
A．20，70，30，50 B．30，88，70，50
C．20，50 D．30，88，50
（5）对22个记录的有序表作折半查找，当查找失败时，至少需要比较（ ）次关键字。 A．3 B．4 C．5 D．6 （6）折半搜索与二叉排序树的时间性能（ ）。
A．相同 B．完全不同
C．有时不相同 D．数量级都是O(log2n)
（7）分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（ ）。 A．（100，80， 90， 60， 120，110，130） B．（100，120，110，130，80， 60， 90） C．（100，60， 80， 90， 120，110，130） D．(100，80， 60， 90， 120，130，110)
（8）在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0右孩子的平衡因子为1，则应作（ ）型调整以使其平衡。
A．LL B．LR C．RL D．RR （9）下列关于m阶B-树的说法错误的是（ ）。 A．根结点至多有m棵子树 B．所有叶子都在同一层次上
C．非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树 D．根结点中的数据是有序的
（10）下面关于B-和B+树的叙述中，不正确的是（ ）。
A．B-树和B+树都是平衡的多叉树 B．B-树和B+树都可用于文件的索引结构 C．B-树和B+树都能有效地支持顺序检索 D．B-树和B+树都能有效地支持随机检索 （11）m阶B-树是一棵（ ）。
A．m叉排序树 B．m叉平衡排序树 C．m-1叉平衡排序树 D．m+1叉平衡排序树 （12）下面关于哈希查找的说法，正确的是（ ）。
A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B．除留余数法是所有哈希函数中最好的
C．不存在特别好与坏的哈希函数，要视情况而定 D．哈希表的平均查找长度有时也和记录总数有关 （13）下面关于哈希查找的说法，不正确的是（ ）。 A．采用链地址法处理冲突时，查找一个元素的时间是相同的
B．采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的
C．用链地址法处理冲突，不会引起二次聚集现象 D．用链地址法处理冲突，适合表长不确定的情况
（14）设哈希表长为14，哈希函数是H(key)=key，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（ ）。 A．8 B．3 C．5 D．9
（15）采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字 ( )。
A．不一定都是同义词 B．一定都是同义词 C．一定都不是同义词 D．都相同
2．应用题
（1）假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
① 画出描述折半查找过程的判定树； ② 若查找元素54，需依次与哪些元素比较？ ③ 若查找元素90，需依次与哪些元素比较？
④ 假定每个元素的查找概率相等，求查找成功时的平均查找长度。
（2）在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。
（3）已知如下所示长度为12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）
① 试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
② 若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。
③ 按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
（4）对下面的3阶B-树，依次执行下列操作，画出各步操作的结果。 ① 插入90 ② 插入25 ③ 插入45 ④ 删除60 50308 20
806010035 40 （5）设哈希表的地址范围为0～17，哈希函数为：H（key）=key。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：
① 画出哈希表的示意图；
② 若查找关键字63，需要依次与哪些关键字进行比较？ ③ 若查找关键字60，需要依次与哪些关键字比较？
④ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
（6）设有一组关键字（9，01，23，14，55，20，84，27），采用哈希函数：H（key）=key %7 ，表长为
10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。
（7）设哈希函数H（K）=3 K mod 11，哈希地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，12），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。
① 线性探测法； ② 链地址法。
第10章 排序
1．选择题
（1）从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（ ）。
A．归并排序 B．冒泡排序 C．插入排序 D．选择排序
（2）从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（ ）。 A．归并排序 B．冒泡排序 C．插入排序 D．选择排序
（3）对n个不同的关键字由小到大进行冒泡排序，在下列（ ）情况下比较的次数最多。 A．从小到大排列好的 B．从大到小排列好的 C．元素无序 D．元素基本有序
（4）对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（ ）。 A．n+1 B．n C．n-1 D．n(n-1)/2 （5）快速排序在下列（ ）情况下最易发挥其长处。 A．被排序的数据中含有多个相同排序码 B．被排序的数据已基本有序 C．被排序的数据完全无序
D．被排序的数据中的最大值和最小值相差悬殊
（6）对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（ ）。 A．O(n) B．O(n2) C．O(nlog2n) D．O(n3)
（7）若一组记录的排序码为（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 （8）下列关键字序列中，（ ）是堆。
A．16，72，31，23，94，53 B．94，23，31，72，16，53 C．16，53，23，94，31，72 D．16，23，53，31，94，72 （9）堆是一种（ ）排序。
A．插入 B．选择 C．交换 D．归并 （10）堆的形状是一棵（ ）。
A．二叉排序树 B．满二叉树 C．完全二叉树 D．平衡二叉树
（11）若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（ ）。 A．79，46，56，38，40，84 B．84，79，56，38，40，46 C．84，79，56，46，40，38 D．84，56，79，40，46，38 （12）下述几种排序方法中，要求内存最大的是（ ）。
A．希尔排序 B．快速排序 C．归并排序 D．堆排序 （13）下述几种排序方法中，（ ）是稳定的排序方法。
A．希尔排序 B．快速排序 C．归并排序 D．堆排序
（14）数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用( )算法最节省时间。
A．冒泡排序 B．快速排序 C．简单选择排序 D．堆排序
（15）下列排序算法中，（ ）不能保证每趟排序至少能将一个元素放到其最终的位置上。 A．希尔排序 B．快速排序 C．冒泡排序 D．堆排序 2．应用题
（1）设待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18}，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。
① 直接插入排序 ② 折半插入排序
③ 希尔排序（增量选取5，3，1） ④ 冒泡排序 ⑤ 快速排序 ⑥ 简单选择排序 ⑦ 堆排序 ⑧ 二路归并排序
（2）给出如下关键字序列｛321，156，57，46，28，7，331，33，34，63｝，试按链式基数排序方法，列出每一趟分配和收集的过程。