数算第三次作业-第四次小测讲评

1、作业小测讲解1101213949 吴良 1. 设有磁盘文件中记录的关键字分别是 10,20,15,25,12,13,21,30,8,16,10. 要求从小到大排序，采用置换选择算法可以产生几个初始顺串？每个初始顺串包含哪些记录？（注：工作区可以容纳4个记录） a) 10 12 13 15 20 21 25 30b) 8 10 16 2. 假设有4个初始归并段如下： 15,16,25,32 3,22,28,45 1,12,30,42 33,60 采用败者树进行4路归并，结果怎么样？请具体写出过程 初始化： 3. 设散列表为HT19,请对10 100 32 45 58 126 3 29 200 4

2、00 0造表 散列函数为直接对19取余，给出此时的散列表和冲突次数 (3) 散列函数为将各个位置上数字相加后对19求余，给出此时的散列表和冲突次数 (2) 请设计一个不会造成冲突的散列函数 拉格朗日插值函数 YiLi (x), 其中Yi =i , Li (x)=1, 当且仅当X=Xi 的时候 (0=i=10) X0-X10为10 100 32 45 58 126 3 29 200 400 0 (只要结果对即可) 4 请将35 20 33 48 59 填入长度m=13的散列表，其散列函数为h1(key) = key%m, 处理冲突的方法为双重散列法，探查序列探查序列为：p(key,i) = (k

3、ey % (m-2) + i*h1(key) % m, i=0,1,m-1. 并回答下列问题： 对表中关键字35 20 33 48查找时，所需进行的比较次数各是多少？ 该该散列表在等概率查找时散列表在等概率查找时查找成功的平均查找长度是多少？解：a) 1 1 2 2 b) (1+1+2+2+3)/5 = 1.801234567891011123348203559 5. 假定一个文件有一兆（1000000）个记录，每个记录占200 字节，其中关键码占50 字节。一个磁盘页块（结点）有1000 字节，页块指针为5 字节。若用B+B+树树组织索引，并假定所有页块（结点）都尽可能装满，则需要多少索引页

4、块（即B+树中有多少个非叶结点）？在上述文件组织中存取一个记录需要多少次外存访问？并解释你的答案。 关键码占50字节，页 块 指针占5字节，那么一个磁盘 页 块 最多可以有ceil(1000/55)=18个，m=18，又由于1841 000000185，所以最多需要B+树五层， 第五层是floor(1000000/18)=55556， 第四层需要floor(55556/18)=3087, 第三层需要floor(3087/18)=172, 第二层需要floor(172/18)=10, 第一层需要floor(10/18)=1; 一共需要 非 叶 节点3087+172+1=+1=3270个。 每次取一个记录需要读索引5次，读 记录1次，读盘5+1=6次；每次存一个记录如果不引起节点的分裂，那么存一个记录就需要访问外存7次，5次读盘，1次索引的写盘，一次记录的写盘；如果引起了节点的分裂，那么沿着跟的路径，每次写盘2次，根写盘3次，所以需要4*2+3=11次索引的写盘和1次记录的写入。 6. 分别画出在右图所示的 3 阶B 树中，进行下列操作后的B 树。(1) 插入关键码 75。分析插入操作的访外次数。(2) 删除关键码 156。分析删除操作的访外次数。 7. 已知一组关键码为(20, 30, 50, 52, 60, 68, 70)，试依次插入关键码