下列排序方法中（）方法是不稳定的。

单项选择题下列排序方法中（）方法是不稳定的。

A.冒泡排序
B.基数排序法
C.堆排序
D.直接插入排序

1.单项选择题若需要在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。

A.快速排序
B.堆排序
C.归并排序
D.直接插入排序

2.问答题设有一组关键字（19，1，23，14，55，20，84，27，68，11，10，77），采用哈希函数H（key）=key%13，采用二次探测再散列的方法解决冲突，试在0-18的散列地址空间中对该关键字序列构造哈希表。

3.问答题 已知下面二叉排序树的各结点的值依次为1－9，请标出各结点的值。

4.问答题设散列表容量为7（散列地址空间0..6），给定表（30，36，47，52，34），散列函数H（K）=Kmod6，采用线性探测法解决冲突，要求：（1）构造散列表；（2）求查找数34需要比较的次数。

（1）表形态：

(2)查找34 的比较次数：3

5.问答题设哈希表HT表长m为13，哈希函数为H（k）=kMODm，给定的关键值序列为{19，14，23，10，68，20，84，27，55，11}。试求出用线性探测法解决冲突时所构造的哈希表，并求出在等概率的情况下查找成功的平均查找长度ASL。

（1）表形态：

(2)平均查找长度：ASL(10)=(1*5+2*4+3*1)/10=1.6

6.问答题设哈希函数H（key）=key MOD13，用线性探测再散列法解决冲突.对关键字序列{55，19，01，68，23，27，20，84}在地址空间为0-10的散列区中建哈希表，画出此表，并求等概率情况下查找成功时的平均查找长度.

ASLsucc = (1 + 2 + 1 + 2 + 1 + 1 + 3 + 1) / 8 = 1.5

7.填空题在散列存储中，装填因子α的值越大，则存取元素时发生冲突的可能性就越（）；α值越小，则存取元素发生冲突的可能性就越（）。

8.填空题已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半查找90时，需进行（）次查找可确定成功。

9.单项选择题对线性表进行折半查找时，要求线性表必须（）。

A.以顺序方式存储
B.以顺序方式存储，且结点按关键字有序排列
C.以链式方式存储
D.以链式方式存储，且结点按关键字有序排列

10.单项选择题解决散列法中出现的冲突问题常采用的方法是（）。

A.数字分析法、除余法、平方取中法
B.数字分析法、除余法、线性探测法
C.数字分析法、线性探测法、多重散列法
D.线性探测法、多重散列法、链地址法