Loading... ## 习题2 * 题目: > 设某字典组成: > $D = \{016,087,154,170,275,426,503,509,512,612,653,677,703,765,897,908\}$ > 依次顺序表示在内存中,现用二分法的方法检索字典中是否有元素612,问需要进行多少次比较才能得到结论?每次选择的对象是什么元素? * 解析: 字典中共有$16$个元素,以下标为$0$开始的话,即为$ D_0,\dots ,D_{15} $ 在初始的二分中,我们最左边的索引$l = 0$,最右边的索引$r = 15$. 若以向下取整的方式进行二分,我们分别会检索到: $$ \begin{array}\ \lfloor \frac {l+r}{2} \rfloor = \lfloor \frac {0+15}{2} \rfloor = 7 \\ D_7 = 509 < 612 \rightarrow l = 7+1 = 8 &(第一次)\\ \\ \lfloor \frac {l+r}{2} \rfloor = \lfloor \frac {8+15}{2} \rfloor = 11 \\ D_{11} = 677 > 612 \rightarrow r = 11 - 1 = 10 &(第二次)\\ \\ \lfloor \frac {l+r}{2} \rfloor = \lfloor \frac {8+10}{2} \rfloor = 9\\ D_9 = 612 == 612 &(第三次) \end{array} $$ 若以向上取整的方式进行二分,检索过程为: $$ \begin{array}\ \lceil \frac {l+r}{2} \rceil = \lceil \frac {0+15}{2} \rceil = 8 \\ D_8 = 512 < 612 \rightarrow l = 8+1 = 9 &(第一次)\\ \\ \lceil \frac {l+r}{2} \rceil = \lceil \frac {9+15}{2} \rceil = 12 \\ D_{12} = 703 > 612 \rightarrow r = 12 - 1 = 11 &(第二次)\\ \\ \lceil \frac {l+r}{2} \rceil = \lceil \frac {9+11}{2} \rceil = 10\\ D_{10} = 653 > 612 \rightarrow r = 10 - 1 = 9&(第三次)\\ \\ \lceil \frac {l+r}{2} \rceil = \lceil \frac {9+9}{2} \rceil = 9\\ D_9 = 612 == 612 &(第四次) \end{array} $$ ## 习题3 * 题目： > 对题2所给的字典使用除余法散列表示,取$\alpha = 0.5$,根据除余法的散列函数计算出对应的地址,并统计出碰撞发生的次数. * 解析: 因为有: $$ \alpha = \frac {字典中元素的数目}{基本区域的总容量} = 0.5 $$ 所以可以得到: $$ 总容量 = \frac {字典中元素的数目}{\alpha} = 32 $$ > 小于等于$32$的最大质数为$31$,所以我们$p = 31$. * 参考计算代码: ```cpp #include <bits/stdc++.h> using namespace std; int D[] = {16,87,154,170,275,426,503,509,512,612,653,677,703,765,897,908}; int main() { const int mod = 31; map<int,vector<int> > mp; for(int i = 0;i < 16;++i){ cout << D[i] << " mod 31 = " << D[i]%mod << endl; mp[D[i]%mod].push_back(D[i]); } cout << endl << "************************" << endl; cout << "************************" << endl << endl; for(auto x:mp){ cout << x.first << " have:"; for(auto y:x.second){ cout << y << ' '; } cout << endl; } return 0; } ``` * 输出结果: ```text 16 mod 31 = 16 87 mod 31 = 25 154 mod 31 = 30 170 mod 31 = 15 275 mod 31 = 27 426 mod 31 = 23 503 mod 31 = 7 509 mod 31 = 13 512 mod 31 = 16 612 mod 31 = 23 653 mod 31 = 2 677 mod 31 = 26 703 mod 31 = 21 765 mod 31 = 21 897 mod 31 = 29 908 mod 31 = 9 ************************ ************************ 2 have:653 7 have:503 9 have:908 13 have:509 15 have:170 16 have:16 512 21 have:703 765 23 have:426 612 25 have:87 26 have:677 27 have:275 29 have:897 30 have:154 ``` **元素的地址可以参考上方代码的输出结果.** **碰撞次数根据下方输出结果可以看到共碰撞了$3$次** ## 习题4 * 题目: > 用上题设计的散列函数对题2的字典进行存储,用开地址线性探查法解决碰撞问题,将所有元素都进入散列表后的存储状况画出来. * 解析: > 根据题3下方输出的结果,碰撞后的元素向后找空位置即可: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | | | 653 | | | | | 503 | | 908 | | | | 509 | | 170 | | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | 16 | 512 | | | | 703 | 765 | 426 | 612 | 87 | 677 | 275 | | 897 | 154 | | ## 习题7 * (1) ```graphviz digraph G{ rankdir=LR; node [shape=record,height = 6]; node0 [label = "{0|<f0> }|{1|<f1> ^}|{2|<f2> }|{3|<f3> }|{4|<f4> ^}|{5|<f5> }|{6|<f6> }|{7|<f7> ^}|{8|<f8> }|{9|<f9> }|{10|<f10> }"]; node [height = .25,widt = 1]; node1 [label = "{<n>110,143|<p>}"]; node2 [label = "{<n>99,121|^}"]; node3 [label = "{<n>255,167|<p>}"]; node4 [label = "{<n>57|^}"]; node5 [label = "{<n>69|^}"]; node6 [label = "{<n>115,137|^}"]; node7 [label = "{<n>160,171|<p>}"]; node8 [label = "{<n>149,204|<p>}"]; node9 [label = "{<n>127,1040|^}"]; node10 [label = "{<n>96,63|<p>}"]; node11 [label = "{<n>52|^}"]; node12 [label = "{<n>185,229|^}"]; node13 [label = "{<n>208,175|^}"]; node0:f0 -> node1:n; node1:p -> node2:n; node0:f2 -> node3:n; node3:p -> node4:n; node0:f3 -> node5:n; node0:f5 -> node6:n; node0:f6 -> node7:n; node7:p -> node8:n; node8:p -> node9:n; node0:f8 -> node10:n; node10:p -> node11:n; node0:f9 -> node12:n; node0:f10 -> node13:n; } ``` * (2) ```graphviz digraph G{ rankdir = LR; node [shape = record,height = 12]; node0 [label = "{0|<f0>}|{1|^}|{2|^}|{3|<f3>}|{4|^}|{5|<f5>}|{6|<f6>}|{7|^}|{8|<f8>}|{9|<f9>}|{10|<f10>}|{11|<f11>}|{12|^}|{13|<f13>}|{14|^}|{15|^}|{16|^}|{17|<f17>}|{18|^}|{19|<f19>}|{20|^}|{21|<f21>}"]; node [height = .2] node00 [label = "{<n>110|^}"]; node30 [label = "{<n>69|^}"]; node50 [label = "{<n>115,137|^}"]; node60 [label = "{<n>160,204|<p>}"]; node61 [label = "{<n>1040|^}"]; node80 [label = "{<n>96,52|^}"]; node90 [label = "{<n>185,229|^}"]; node100 [label = "{<n>208|^}"]; node110 [label = "{<n>143,99|<p>}"]; node111 [label = "{<n>121|^}"]; node130 [label = "{<n>255,167|<p>}"]; node131 [label = "{<n>57|^}"]; node170 [label = "{<n>171,149|<p>}"]; node171 [label = "{<n>127|^}"]; node190 [label = "{<n>63|^}"]; node210 [label = "{<n>175|^}"]; node0:f0 -> node00:n; node0:f3 -> node30:n; node0:f5 -> node50:n; node0:f6 -> node60:n; node60:p -> node61:p; node0:f8 -> node80:n; node0:f9 -> node90:n; node0:f10 -> node100:n; node0:f11 -> node110:n; node110:p -> node111:n; node0:f13 -> node130:n; node130:p -> node131:n; node0:f17 -> node170:n; node170:p -> node171:n; node0:f19 -> node190:n; node0:f21 -> node210:n; } ``` * (3) > 根据(1)和(2)的比较,我们可以发现,在加倍后,我们的(1)表中仅仅是一部分的内容从$x$ 迁移到了 $x+11$,另一部分的内容不变. > 而如果将$p$设置为$19$的话(1)表中的内容的迁移将更加混乱. > 因此,加倍的扩充的效率更高. Last modification：May 24, 2022 © Reprint prohibited Support Appreciate the author Like 3 如果觉得我的文章对你有用，请随意赞赏
3 comments
你的文章充满了欢乐，让人忍不住一笑。 https://www.yonboz.com/video/60679.html
你的文章让我感受到了快乐，每天都要来看一看。 https://www.yonboz.com/video/10271.html
你的文章内容非常用心，让人感动。 http://www.55baobei.com/fTGU9b7fKb.html