5、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用＿＿＿＿＿＿＿查找方法。D
A、折半 C、分块
B、顺序 D、散列
第二题、多项选择题（每题2分，5道题共10分） 1、构造散列函数时通常考虑的因素有＿＿＿＿＿＿＿。
A、计算函数的工作量 B、关键字的长度 C、散列表长 D、关键字的分布情况
2、下列关于n个结点的m阶B树的说法中，正确的是＿＿＿＿＿＿＿。BCDE
A、树中每个结点最多有m个关键字 B、树中叶子结点的个数为n+1
C、在B树上进行查找的过程是顺指针找结点和在结点内找关键字交叉进行的过程。 D、树中所有叶子结点都在同一层，并且不带任何信息 E、树中每个结点最多有m-1个关键字 F、树中每个结点最多有m+1个关键字
3、在顺序表的顺序查找算法中，监视哨的位置＿＿＿＿＿＿＿。
A、只能在表头 B、只能在表尾 C、可以在表头 D、可以在表尾
4、对序列{50，72，43，85，75，20，35，45，30}按顺序建二叉排序树，则在树中须比较3次方可查找成功的元素有＿＿＿＿＿＿＿。
A、50CDE F 还是不对 B、43
C、85 D、75 E、20 F、35 G、45 H、30
5、在下列各种查找方法中，平均查找长度与表长有关的查找方法是＿＿＿＿＿＿＿。
A、散列表查找 B、顺序查找 C、折半查找 D、排序树查找
第三题、判断题（每题1分，5道题共5分）
1、散列表的装填因子越小，发生冲突的可能性越大。
正确
错误
2、平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉树。
正确
错误
3、二叉树为二叉排序树的充要条件是，其任意结点的值均大于其左孩子的值且小于其右孩子的值。
正确
错误
4、9阶B树中，除根以外的任意非终端结点中的关键字个数不少于4。
正确
错误
5、若散列表的装填因子小于1，则可避免冲突的产生
正确
错误
数据结构》第08章在线测试
《数据结构》第08章在线测试 剩余时间：5 9:36 答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。 第一题、单项选择题（每题1分，5道题共5分） 1、下列方法中，＿＿＿＿＿＿＿＿算法的时间复杂度为O(n^2)。 A、直接插入排序 C、快速排序 B、希尔排序 D、堆排序 2、对于关键字序列{12，13，10，18，60，15，7，20，25，100}用筛选法建堆，必须从关键字为＿＿＿＿＿＿＿的结点开始。 A、18 C、15 B、60 D、7 3、下列序列中，＿＿＿＿＿＿＿＿是堆。A A、{12，35，20，60，40，30} C、{1，5，6，24，7，3，4 } B、{100，85，120，38，10，9，36} D、{38，24，15，20，30，46} 4、在下列排序方法中，在待排序的数据有序时, 花费时间反而最多的是＿＿＿＿＿＿＿。C A、堆排序 C、快速排序 B、起泡排序 D、插入排序 5、对n个记录的序列进行堆排序，最坏情况下的时间复杂度为＿＿＿＿＿＿。 A、O(logn) C、O(n) B、O(nlogn) D、O(n^2) 第二题、多项选择题（每题2分，5道题共10分） 1、下列方法中，＿＿＿＿＿＿＿＿算法的时间复杂度为O(n^2)。 A、希尔排序 B、冒泡排序 C、快速排序 D、直接插入排序
2、下列方法中，＿＿＿＿＿＿＿＿算法的时间复杂度为O(nlogn)。
A、希尔排序 B、堆排序 C、快速排序 D、简单选择排序 E、直接插入排序
3、下列排序方法中，在最坏情况下算法的时间复杂度为O(n^2)的有＿＿＿＿＿＿＿＿。
A、堆排序 B、快速排序 C、希尔排序 D、冒泡排序
4、下列序列中，＿＿＿＿＿＿＿＿不是堆。CD
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}
5、下列排序方法中，不稳定的排序方法有＿＿＿＿＿＿＿＿。
A、希尔排序 B、快速排序 C、堆排序 D、直接插入排序
第三题、判断题（每题1分，5道题共5分）
1、快速排序算法在待排序数据有序时最不利于发挥其长处。
正确 错误 2、对一个堆按层次遍历，一定能得到一个有序序列。 正确 错误 3、由于希尔排序的最后一趟与直接插入排序过程相同，所以前者一定比后者花费的时间多。 正确 错误 4、快速排序算法在每趟排序结束时都能找到一个元素放到其最终位置上。 正确 错误 5、在堆排序过程中，在输出一个根之后的调整过程中，“临时根”结点的值将会最终被放到“叶子结点”上。 正确 错误