二、综合应用题：41-47小题，共计70分
41.（10分）将关键字序列（7、8、11、18、9、14）散列存储到散列列表中，散列表的存储空间是一个下标从0开始的一个一维数组散列函数维：H（key）=（key×3）MODT，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7
问题：
（1）请画出所构造的散列表；
（2）分别计算等概率情况下，查找成功和查找不成功的平均查找长度。
解答：
（1）由装载因子0.7，数据总数7个→存储空间长度为10→P=10
所以，构造的散列表为：
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| 30 |
7 |
14 |
11 |
8 |
18 |
. |
9 |
. |
. |
H（7）=（7×3）MOD10=1
（2）查找成功的ASL=(1+1+1+1+2+1+1)/7=8/7
查找不成功的ASL=(7+6+5+4+3+2+1+2+1+1)/10=3.2
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）前P个数依次进队，while（1﹤n-p）A{i}-{i+p}：p个数依次出对，进入数组末尾
（2）详细程序略
（3）时间复杂度O（N）;空间复杂度o(p)
[本文共有 6 页，当前是第 4 页] <<上一页 下一页>>
