A Q S R Q Y X ____。
作业题
1．下面的排序算法的思想是：第一趟比较将最小的元素放在r[1]中，最大的元素放在r[n]中，第二趟比较将次小的放在r[2]中，将次大的放在r[n-1]中，?,依次下去，直到待排序列为递增序。（注：<-->）代表两个变量的数据交换）。
void sort(SqList &r,int n) { i=1;
while((1) i< n/2__) { min=max=1;
for (j=i+1;(2)_ j<=n-i+1____ ;++j)
{if((3)_ r[j].key
max=j; }
if((4)_ min!=j_____) r[min] < ---- >r[j];
if(max!=n-i+1){if ((5)_ max==j __) r[min] < ---- > r[n-i+1]; else ((6) r[max]<->r[m-i+1]___); } i++; }
}//sort
2．快速排序是在所有情况下，排序速度最快吗？为什么？在何种情况下使用此排序法最好？
解：不是，已经有序情况下不适用，适用于基本无序的情况。
3、以上所列的排序方法，哪些是稳定的？哪些是不稳定的？对不稳定的方法举出反例。 4、设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取负值关键字之前。
快速排序的一趟排序：把关键字改成跟零比较
5、以单链表为存储结构实现直接选择排序，写出它的算法。 6、判别以下序列是否为堆？若不是，则把它调整为堆 1）100，86，48，73，35，39，42，57，66，21 2）12，70，33，65，24，56，48，92，86，33
3）103，97，56，38，66，23，42，12，30，52，06，20 4）05，56，20，23，40，38，29，61，35，76，28，100
16
第九章
选择题
1、 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为(A )
A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2 2. 下面关于二分查找的叙述正确的是 ( D )
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列
B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储
3. 二叉查找树的查找效率与二叉树的( （1）C )有关, 在 (（2）C)时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 4. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）A) 个链表。
这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）C) （1） A．17 B. 13 C. 16 D. 任意 （2） A．0至17 B. 1至17 C. 0至16 D. 1至16 判断题
1．Hash表的平均查找长度与处理冲突的方法无关。 × 2. 若散列表的负载因子α<1，则可避免碰撞的产生。×
3. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。× 填空题
1. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为__4____. 作业题
1. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=12,22,32,?,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。
解：14/8＝1.75
0 1 2 3 4 5 6 7 8 9 14 1 9 23 84 27 55 20 1 1 1 2 3 3 1 2
2. 已知散列表的地址空间为A[0..11]，散列函数H（k）=k mod 11，采用线性探测法处理冲突。请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在等概率情况下查找成功时的平均查找长度。 解：
0 1 2 3 4 5 6 7 8 9 10 11
231 89 79 25 47 16 38 82 51 39 151 1 1 1 1 2 1 2 3 2 4 3 17
21/11
3、对长度为20 的有序表进行二分查找，试画出它的一棵判定树，并求等概率情况下的平均查找长度。
随机的给出20个有序数据
4、试编写一个用拉链法解决冲突的散列表上删除一个指定结点的算法。（不做要求）
5、设散列表的长度为15，散列函数H（K）=K，给定的关键字序列为20，16，29，82，37，02，06，28，55，39，23，10，试写出分别用拉链法和线性探测法解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功时的平均查找长度。
18
19
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库期末数据结构复习习题(含答案)(4)在线全文阅读。
相关推荐：