第九章 复习题.pdf

第九章 复习题 1 设有序顺序表中的元素依次为 017 094 154 170 275 503 509 512 553 612 677 765 897 908 试画出对其进行折半搜索时的判 定树 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索 长度 解答 2 若对有 n 个元素的有序顺序表和无序顺序表进行顺序搜索 试就 下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否 相同 1 搜索失败 2 搜索成功 且表中只有一个关键码等于给定值 k 的对象 3 搜索成功 且表中有若干个关键码等于给定值 k 的对象 要求 一次搜索找出所有对象 解答 1 不同 因为有序顺序表搜索到其关键字比要查找值大的对象 509 154 677 017 275 553 897 094 170 503 512 612 765 908 14 45 7 44 32 2 1 14 1 C 14 1 ASL 14 1i isucc 15 59 14 41 3 15 1 C 15 1 ASL 15 0i iunsucc 时就停止搜索 报告失败信息 不必搜索到表尾 而无序顺序表必须 搜索到表尾才能断定搜索失败 2 相同 搜索到表中对象的关键字等于给定值时就停止搜索 报告成功信息 3 不同 有序顺序表中关键字相等的对象相继排列在一起 只 要搜索到第一个就可以连续搜索到其它关键码相同的对象 而无序顺 序表必须搜索全部表中对象才能确定相同关键码的对象都找了出来 所需时间就不相同了 3 设有一个输入数据的序列是 46 25 78 62 12 37 70 29 试画 出从空树起 逐个输入各个数据而生成的二叉排序树 解答 4 将关键码 DEC FEB NOV OCT JUL SEP AUG APR MAR MAY JUN JAN 依次插入到一棵初始为空的 AVL 树中 画出每插入一 个关键码后的 AVL 树 并标明平衡旋转的类型 解答 46 46 25 46 25 78 46 25 78 62 46 25 78 62 12 46 25 78 62 12 37 46 25 78 62 12 37 70 46 25 78 62 12 37 70 29 空树 加46 加25 加78 加62 加12 加37 加70 加29 加 DEC 加 FEB 加 NOV 加 OCT 加 JUL 5 设散列表为 HT 13 散列函数为 H key key 13 用下列方法 解决冲突 对下列关键码序列 12 23 45 57 20 03 78 31 15 36 造表 1 采用线性探测再散列法寻找下一个空位 画出相应的散列表 DEC DEC FEB DEC FEB NOV 左单旋 FEB NOV DEC FEB NOV DEC OCT FEB NOVDEC OCT JUL FEB NOV DEC OCT JUL SEP 左单旋 NOV OCT JUL SEP DEC FEB NOV OCT JUL SEP DEC FEB AUG NOV OCT JUL SEP DEC FEB AUG APR 右单旋 NOV OCT JUL SEP FEB AUG APR DEC NOV OCT JUL SEP FEB AUG APR DEC MAR NOV OCT JUL SEP FEB AUG APR DEC MAR MAY 左单旋 NOV OCT SEP FEB AUG APR DEC MAR MAYJUL NOV OCT SEP FEB AUG APR DEC MAR MAY JUL JUN 左右双旋 NOV OCT FEB AUG APR DEC MAR MAY JUL JUN SEP NOV OCT FEB AUG APR DEC MAR MAY JUL JUN SEP JAN 加 JAN 加 JUN 加 MAY 加 MAR 加 APR 加 AUG 加 SEP 2 2 2 2 2 并计算等概率下搜索成功的平均搜索长度 2 采用再哈希法寻找下一个空位 再哈希函数为 RH key 7 key 10 1 寻找下一个空位的公式为 Hi Hi 1 RH key 13 H1 H key 画出相应的散列表 并计算等概率下搜索成功的平 均搜索长度 解答 使用散列函数 H key key mod 13 有 H 12 12 H 23 10 H 45 6 H 57 5 H 20 7 H 03 3 H 78 0 H 31 5 H 15 2 H 36 10 1 利用线性探测再散列法造表 H key key 13 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 23 36 12 1 1 1 1 1 1 4 1 2 1 搜索成功的平均搜索长度为 ASLsucc 1 10 1 1 1 1 1 1 4 1 2 1 14 10 2 利用再哈希法造表 Hi Hi 1 RH key 13 RH key 7 key 10 1 H1 H key 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 36 23 12 1 1 1 1 1 1 3 5 1 1 搜索成功的平均搜索长度为 ASLsucc 1 10 1 1 1 1 1 1 3 5 1 1 16 10 6 设有 150 个记录要存储到散列表中 要求利用线性探查法解决冲 突 同时要求找到所需记录的平均比较次数不超过 2 次 试问散 列表需要设计多大 设 是散列表的装载因子 则有 1 1 1 2 1 ASLsucc 解答 已知要存储的记录数为 n 150 查找成功的平均查找长度为 ASLsucc 2 则有 ASLsucc 1 2 1 1 1 2 解得 2 3 又有 n mm 150 2 3 则 m 225 7 设有 100 个数据元素 采用折半搜索时 最大比较次数为 见 P220 Log2100 1 A 6 B 7 C 8 D 10 8 设散列表的长度为 13 散列函数为 H k k 13 给定的关键字 序列为 19 14 23 01 68 20 84 27 试画出用线性探测再散列法 解决