v1.0 可编辑可修改 (1) 采用线性探查法寻找下一个空位, 画出相应的散列表, 并计算等概率下查找成功的平均查
找长度和查找所查找不成功的平均查找长度。
(2) 采用双散列法寻找下一个空位, 再散列函数为 RH (key) = (7*key) mod 10 + 1, 寻找下一
个空位的公式为 Hi = (Hi-1 + RH (key)) mod 13, H1 = H (key)。画出相应的散列表, 并计算等概率下查找成功的平均查找长度。 【解答】
使用散列函数 H(key) = key mod 13，有
H(12) = 12, H(23) = 10, H(20) = 7, H(15) = 2,
H(03) = 3, H(36) = 10.
H(45) = 6, H(78) = 0,
H(57) = 5, H(31) = 5,
(1) 利用线性探查法造表： 0 1 2 3 4 5 6 7 8 9 10 11 12 23 36 12 (1) (2) (1)
78 (1)
15 03 (1) (1)
57 45 20 31 (1) (1) (1) (4)
查找成功的平均查找长度为
ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) = 14
查找不成功的平均查找长度为
ASLunsucc = (2 + 1 + 3 + 2 + 1 + 5 + 4 + 3 + 2 + 1 + 5 + 4 + 3) =36
(2) 利用双散列法造表： 0 Hi = (Hi-1 + RH (key)) mod 13, H1 = H (key)
1 2 3 4 5 6 7 8 9 10 11 12 12 (1)
78 (1)
15 03 (1) (1)
57 45 20 31 36 23 (1) (1) (1) (3) (5) (1)
查找成功的平均查找长度为
ASLsucc = (1 + 1 + 1 + 1 + 1 + 1 + 3 + 5 + 1 + 1) =16
第九章 排序
一、填空
1．在一个堆的顺序存储中，若一个元素的下标为i(0≤i≤n-1)，则它的左孩子元素的下标为_ 2i+1 ，右孩子元素的下标为_2i+2_。
4141
v1.0 可编辑可修改 2．在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_ O(log2n)_，整个堆排序过程的时间复杂度为_ O(nlog2n)_。
3. 快速排序在平均情况下的时间复杂度为 O(nlog2n)_，在最坏情况下的时间复杂度为_ O(n)_。
2
4.假定一组记录的排序码为(46,79,56,38,40,80,25,34)，则对其进行快速排序的第一次划分的结果为[40 34 25 38] 46 [80 56 79] 。
5.用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：
20，15，21，25，47，27，68，35，84
15，20，21，25，35，27，47，68，84
15，20，21，25，27，35，47，68，84
则所采用的排序方法是 快速排序 。
二、解答题
1． 已知序列{ 503，87，512，61，908，170，897，275，653，462}，采用快速排序方法对该序列作
升序排序时的每一趟的结果。
答：初始：503，87，512，61，908，170，897，275，653，462
1趟：[462，87，275，61，170] 503 [897，908，653，512] 2趟：[170，87，275，61] 462，503 [897，908，653，512] 3趟：[61，87] 170 [275] 462，503 [897，908，653，512] 4趟：61 [87] 170 [275] 462，503 [897，908，653，512] 5趟：61，87，170 [275] 462，503 [897，908，653，512] 6趟：61，87，170，275，462，503 [897，908，653，512] 7趟：61，87，170，275，462，503 [512，653] 897 [908]
4242
v1.0 可编辑可修改 8趟：61，87，170，275，462，503，512 [653] 897 [908] 9趟：61，87，170，275，462，503，512，653，897 [908] 10趟：61，87，170，275，462，503，512，653，897 ，908
2. 已知序列{ 503，87，512，61，908，170，897，275，653，462}，采用堆排序方法对该序列作降序排序时的每一趟的结果。
答：初始化为极大堆：908，653，897，503，462，170，512，275，61，87
（1） 908（897，653，512，503，462，170，87，275，61） （2） 908，897（653，503，512，275，462，170，87，61） （3） 908，897，653（512，503，170，275，462，61，87） （4） 908，897，653，512（503，462，170，275，87，61） （5） 908，897，653，512，503（462，275，170，61，87） （6） 908，897，653，512，503，462（275，87，170，61） （7） 908，897，653，512，503，462，275（170，87，61） （8） 908，897，653，512，503，462，275，170（87，61） （9） 908，897，653，512，503，462，275，170，87（61） （10） 908，897，653，512，503，462，275，170，87，61
3.写出下列算法的功能：
void AA（Heap&HBT，const Elem type item） 序源代码： /*creat a list*/ #include \#include \struct list { int data; struct list *next; };
typedef struct list node;
4343
v1.0 可编辑可修改 typedef node *link; void main() { link ptr,head; int num,i;
ptr=(link)malloc(sizeof(node)); ptr=head;
printf(\for(i=0;i<=4;i++) {
scanf(\ ptr->data=num;
ptr->next=(link)malloc(sizeof(node)); if(i==4) ptr->next=NULL; else ptr=ptr->next; } ptr=head; while(ptr!=NULL)
{ printf(\ ptr=ptr->next; } }
3、反向输出一个链表。 程序源代码：
/*reverse output a list*/ #include \#include \struct list
4444
v1.0 可编辑可修改 { int data;
struct list *next; };
typedef struct list node; typedef node *link; void main()
{ link ptr,head,tail; int num,i;
tail=(link)malloc(sizeof(node)); tail->next=NULL; ptr=tail;
printf(\ for(i=0;i<=4;i++) {
scanf(\ ptr->data=num;
head=(link)malloc(sizeof(node)); head->next=ptr; ptr=head; }
ptr=ptr->next; while(ptr!=NULL)
{ printf(\ ptr=ptr->next; }}
4、连接两个链表。 程序源代码： #include \
4545
数据结构习题集与实验指导
