? ? ? ? ? ? ? ? ? ? ? ? ? ? 1.2 [单选] [对] 用折半查找对长度为12的有序表进行查找，则等概率下查找成功时的平均查找长度为＿＿＿＿＿＿＿。
1.3 [单选] [对] 用链地址法处理冲突构造的散列表中，每个地址单元所链接的同义词表的＿＿＿＿＿＿＿相同。
1.4 [单选] [对] 如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用＿＿＿＿＿＿＿查找方法。
1.5 [单选] [对] 高度为5的二叉平衡树至少有＿＿＿＿＿＿＿个结点。 2.1 [多选] [对] 平衡二叉树上结点的平衡因子可以为＿＿＿＿＿＿＿。 2.2 [多选] [对] 构造散列函数时通常考虑的因素有＿＿＿＿＿＿＿。 2.3 [多选] [对] 构造散列表时解决冲突常用的方法有＿＿＿＿＿＿＿。 2.4 [多选] [对] 对于10个元素的有序表进行折半查找，须比较3次方可查找成功的元素在表中的位置有＿＿＿＿＿＿＿。
2.5 [多选] [对] 在顺序表的顺序查找算法中，监视哨的位置＿＿＿＿＿＿＿。 3.1 [判断] [对] 折半查找和二叉排序树查找的时间性能相同。
3.2 [判断] [对] 在散列函数H(key)＝key mod p中，函数的好坏与p的选择没有任何关系。
3.3 [判断] [对] 平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉树。
3.4 [判断] [对] 在分块查找中，对索引表的查找既可用顺序查找法，也可用折半查找法。
3.5 [判断] [对] 若散列表的装填因子小于1，则可避免冲突的产生
《数据结构》第08章在线测试
《数据结构》第08章在线测试 剩余时间：5 6:05 答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。 第一题、单项选择题（每题1分，5道题共5分） 1、下列方法中，＿＿＿＿＿＿＿＿是稳定的排序方法。 A、折半插入排序 C、快速排序 B、希尔排序 D、堆排序 2、在待排序的元素序列基本有序的前提下，效率最高的排序方法是＿＿＿＿＿＿＿。 A、直接插入排序 C、快速排序 B、起泡排序 D、堆排序 3、一组记录的关键字序列为{46，79，56，38，40，84}，则利用快速排序方法，以第一个记录为枢轴得到的一次划分结果是＿＿＿＿＿＿＿。 A、{38，40，46，56，79，84} C、{40，38，46，56，79，84}
B、{40，38，46，79，56，84} D、{40，38，46，84，56，79}
4、在下列排序方法中，平均情况下占用内存量最大的是＿＿＿＿＿＿＿方法。
A、快速排序 C、冒泡排序
B、插入排序 D、堆排序
5、对n个记录的序列进行堆排序，最坏情况下的时间复杂度为＿＿＿＿＿＿。
A、O(logn) C、O(n)
B、O(nlogn) D、O(n^2)
第二题、多项选择题（每题2分，5道题共10分）
1、下列方法中，＿＿＿＿＿＿＿＿算法的时间复杂度为O(nlogn)。
A、希尔排序 B、堆排序 C、快速排序 D、简单选择排序 E、直接插入排序
2、下列序列中，＿＿＿＿＿＿＿＿是堆。
A、{15,30,22,93,52,71} B、{15,22,30,52,71,93} C、{15,52,22,93,30,71} D、{15,52,22,71,30,93}
3、在下列排序方法中，每一趟排序结束后都能选出一个元素放在其最终位置上的是＿＿＿＿＿＿＿。
A、简单选择排序 B、起泡排序 C、快速排序
D、直接插入排序 E、堆排序
4、下列排序方法中，在最坏情况下算法的时间复杂度为O(n^2)的有＿＿＿＿＿＿＿＿。
A、堆排序 B、快速排序 C、希尔排序 D、冒泡排序
5、下列序列中，＿＿＿＿＿＿＿＿不是堆。
A、{96,83,27,38,11,9} B、{12,36,24,85,47,30,53,91} C、{49,38,65,97,76,13,27} D、{38，24，15，20，30，46}
第三题、判断题（每题1分，5道题共5分） 1、在一个大顶堆中，最小元素不一定在最后。
正确
错误
2、对一个堆按层次遍历，一定能得到一个有序序列。
正确
错误
3、在数据表基本有序时，冒泡排序方法的时间复杂度一定接近O(n)。
正确
错误
4、由于希尔排序的最后一趟与直接插入排序过程相同，所以前者一定比后者花费的时间多。
正确
错误
5、快速排序算法在每趟排序结束时都能找到一个元素放到其最终位置上。
正确
错误
测试结果如下：
? ?
1.1 [单选] [对] 下列方法中，＿＿＿＿＿＿＿＿是稳定的排序方法。
1.2 [单选] [对] 在待排序的元素序列基本有序的前提下，效率最高的排序方法是＿＿＿＿＿＿＿。
? ? ? ? ? ? ? ? ? ? ? ? ?
1.3 [单选] [对] 一组记录的关键字序列为{46，79，56，38，40，84}，则利用快速排序方法，以第一个记录为枢轴得到的一次划分结果是＿＿＿＿＿＿＿。
1.4 [单选] [对] 在下列排序方法中，平均情况下占用内存量最大的是＿＿＿＿＿＿＿方法。
1.5 [单选] [对] 对n个记录的序列进行堆排序，最坏情况下的时间复杂度为＿＿＿＿＿＿。
2.1 [多选] [对] 下列方法中，＿＿＿＿＿＿＿＿算法的时间复杂度为O(nlogn)。
2.2 [多选] [对] 下列序列中，＿＿＿＿＿＿＿＿是堆。
2.3 [多选] [对] 在下列排序方法中，每一趟排序结束后都能选出一个元素放在其最终位置上的是＿＿＿＿＿＿＿。
2.4 [多选] [对] 下列排序方法中，在最坏情况下算法的时间复杂度为O(n^2)的有＿＿＿＿＿＿＿＿。
2.5 [多选] [对] 下列序列中，＿＿＿＿＿＿＿＿不是堆。 3.1 [判断] [对] 在一个大顶堆中，最小元素不一定在最后。
3.2 [判断] [对] 对一个堆按层次遍历，一定能得到一个有序序列。
3.3 [判断] [对] 在数据表基本有序时，冒泡排序方法的时间复杂度一定接近O(n)。
3.4 [判断] [对] 由于希尔排序的最后一趟与直接插入排序过程相同，所以前者一定比后者花费的时间多。
3.5 [判断] [对] 快速排序算法在每趟排序结束时都能找到一个元素放到其最终位置上。