2010年数据结构408
41题．(10分)
将关键字序列(7，8，30，11，18，9，14)散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组，散列函数为：H(key)=(key×3)MOD 7，处理冲突采用线性探测再散列法，要求装填(载)因子为0.7。
(1)请画出所构造的散列表。
(2)分别计算等概率情况下查找成功和查找不成功的平均查找长度。
41．【答案要点】
(1) 装载因子
=表中记录数 / 散列表长度
=数据总数 / 存储空间长度
=7 / 10
所以，构造的散列表为：
H(7)=(7×3)MOD 7=0
H(8)=(8×3)MOD 7=3
H(11)=(11×3)MOD 7=5
H(18)=(18×3)MOD 7=5
H(9)=(9×3)MOD 7=6
H(14)=(14×3)MOD 7=0
H(30)=(30×3)MOD 7=6
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 关键字 | 7 | 14 | 0 | 8 | 0 | 11 | 30 | 18 | 9 | 0 |
(2)
查找失败，是根据查找失败位置计算平均次数，散列函数 MOD 7，初始只需在 0~6 位置
查找成功的平均查找长度：ASL成功 = (1+1+1+1+2+3+3) / 7=12 / 7。
查找不成功的平均查找长度：AsL不成功 = (3+2+1+2+1+5+4) / 7=18 / 7
42 解答
(13分)设将n(n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法，将R中保存的序列循环左移p(0<p<n)个位置，即将R中的数据由(x0，x1…，xn-1)变换为(xp，xp+1，…，xn-1，x0，x1，…，xp-1)。要求：
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或c++或Java语言描述算法，关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
1) 算法的基本设计思想：
设Reverse函数执行将数组元素逆置的操作，对abcdefgh向左循环移动3 (p = 3)
个位置的过程如下：
Reverse(0,p-1) 得到cbadefgh;
Reverse(p,n-1) 得到cbahgfed;
Reverse(O,n-1) 得到defghabc。
注： Reverse中， 两个参数分别表示数组中待转换元素的始末位置。
注：这题直接最优解不比暴力解差
2) 使用 C 语言描述算法如下：
最优解：
#include <stdio.h>#include <stdlib.h>void reverse(int R[], int left, int right){int k = left, j = right, tmp;while(k < j){//交换 R[k]与 R[j]tmp = R[k];R[k] = R[j];R[j] = tmp;k++;//k 右移一个位置j--;//j 左移一个位置}}void LeftShift(intR[],intn,intp){//循环左移 p 个元素if(p > 0 && p < n) {reverse(R,0,n-1);//将全部元素逆置reverse(R,0,n-p-1);//将前 n-p 个元素逆置reverse(R,n-p,n-1);//将后 p 个元素逆置}}int main(){int A[8] = {1,2,3,4,5,6,7,8};printf("原数组元素分别为： ");for(int i = 0; i < 8; i++ ){printf("%d ",A[i]);}printf("\n");int p = 2;printf("循环前移 p = %d 个元素\n",p);LeftShift(A,8,p);printf("前移后数组元素分别为：");for(inti = 0; i < 8;i++){printf("%d ",A[i]);}return 0;}
暴力解：
- 先将标号为1的部分全部移动到新建数组A中
- 然后将标号2的内容移动到1的位置
- 随后将A数组元素移动到2的位置即可
//创建一个tmp数组存储[p，n-1]和[0，p-1] 空间复杂度o(p)void Remove(int A[], int p, int n) {int tmp[n], k = 0;//0(n-p)for (int i = p;i < n; i++) {tmp[k++] = A[i];}//0(p)for (int i = 0;i < p; i++) {tmp[k++] = A[i];}for (int i = 0; i < n;i++){A[i] = tmp[i];}
}//写法2
void Remove(Sqlist &L,int p){int *array = (int *)malloc(sizeof(int)*p);//移动第一部分p个元素for(int i=0;i<p;++i){array[i] = L.data[i];}//将第二个部分内容往前for(int i=p;i<L.length;++i){L.data[i-p]=1.data[i];}//将A数组中的元素移动到2的位置for(int i=L.length-p;j=0;j<p;++i;++j){L.data[i]=array[j];}free(array);
}