17.2.1 顺序查找
查找概率不等时怎样降低ASL？
考研计算机 408 全程课 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 章9第 2 章8第 3 章14第 4 章20第 5 章7第 6 章21第 7 章20第 8 章21第 9 章25第 10 章9第 11 章8第 12 章12第 13 章16第 14 章23第 15 章15第 16 章21第 17 章9第 18 章10第 19 章8第 20 章1第 21 章4第 22 章4第 23 章6第 24 章2第 25 章1第 26 章3第 27 章14第 28 章14第 29 章18第 30 章8第 31 章19第 32 章13第 33 章16第 34 章3第 35 章6第 36 章8第 37 章8第 38 章9第 39 章7第 40 章8第 41 章8第 42 章19第 43 章19第 44 章9第 45 章10第 46 章4第 47 章4第 48 章4第 49 章4第 50 章16第 51 章20第 52 章16第 53 章12第 54 章14第 55 章25第 56 章14第 57 章10第 58 章4第 59 章6
第 1 页 · 正面（题目）
27.2.2 折半查找
在6项数组查失败最多比较几次？
37.2.3 分块查找
n=100，索引与块内都顺序查，块数约取多少？
47.2 顺序查找、折半查找·选择题讲评
有序表长度7且形态满，等概率成功ASL是多少？
57.2 顺序查找、折半查找·综合题讲评
[1,3,3,6]查0、3、7分别返回什么？
67.3.1 二叉排序树
插入1,2,3,4后树高多少？
77.3.2 平衡二叉树、平衡二叉树的删除
插入10,30,20是什么类型？
87.3.3 红黑树的定义和性质、红黑树的插入、红黑树的删除
红结点能有红父亲吗？
97.3 二叉排序树、平衡二叉树·选择题讲评
BST中序为1,2,3能确定唯一形态吗？
107.3 二叉排序树、平衡二叉树·综合题讲评
若允许重复键只放右侧，范围开闭应怎样？
第 1 页 · 背面（答案）
答案3，可由判定树高度或实际边界推演。
答案把高频记录置前，若允许自组织还可命中后前移。
答案(1+4+12)/7=17/7。
答案约10。
答案4，说明需平衡树避免退化。
答案0、1、4。
答案不能；否则违反红结点孩子必须黑。
答案RL：先右旋30，再左旋10，20为根。
答案左严格小于，右允许大于等于。
答案不能，多种形态有相同中序。
第 2 页 · 正面（题目）
117.4.1 B树、B树的插入删除
5阶B树非根结点最少几个孩子和关键字？
127.4.2 B+树
为何B+树比B树更适合范围查询？
137.4 B树、B树的插入删除·选择题讲评
4阶B树含3个关键字的结点再插一个会怎样？
147.4 B树、B树的插入删除·综合题讲评
4阶B树三层最多多少关键字？
157.5.1 散列表的基本概念
表长10存7项，装填因子多少？
167.5.2 散列函数的构造
键[20,30,40,50]，模10和模11哪个更均匀？
177.5.3 处理冲突的方法_拉链法、处理冲突的方法_开放定址法
上述表删除17后查24会检查哪些槽？
187.5.4 散列查找的性能分析
为何开放定址表不能等到完全满再扩容？
197.5 散列表的基本概念、散列函数的构造·选择题讲评
上例成功ASL是多少？
207.5 散列表的基本概念、散列函数的构造·综合题讲评
上述状态插17后各槽如何？
第 2 页 · 背面（答案）
答案数据集中在有序叶链，可定位起点后顺扫。
答案3个孩子、2个关键字。
答案(1+4+16)×3=63。
答案溢出并分裂，向父提升分隔键。
答案模11。
答案0.7。
答案失败查找趋近扫描全表，插入可能无空槽。
答案3、4墓碑、5命中。
答案3:10,4:17,5:24；查24仍经3,4,5命中。
答案(1+2+3)/3=2。
第 3 页 · 正面（题目）
217.1 查找的基本概念
某表3项，访问概率0.6,0.3,0.1，如何排列使顺序查找ASL最小？
第 3 页 · 背面（答案）
答案按概率降序，ASL=1.5。