数据结构,第九章,查找.doc

《数据结构,第九章,查找.doc》由会员分享，可在线阅读，更多相关《数据结构,第九章,查找.doc（3页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构,第九章,查找数据结构 第九章 查找 一、简答题 1.折半查找是否适合链表结构的序列为什么？用二分查找的查找速度必然比线性查找的速度快这种说法对吗？ 2.假定对有序表：（34572430425463728795）进行折半查找试回答下列问题： (1) 画出描述折半查找过程的判定树； (2) 若查找元素54需依次与哪些元素比较？ (3) 若查找元素90需依次与哪些元素比较？ (4) 假定每个元素的查找概率相等求查找成功时的平均查找长度。 3.用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么? 如果要求时间复杂度更小,你采用什么方法？此方法的时间复杂度是多少? 二

2、、分析题 1.设哈希（Hash）表的地址范围为017哈希函数为：H（K）K MOD 16。 K为关键字用线性探测法再散列法处理冲突输入关键字序列： （1024321731304647406349） 造出Hash表试回答下列问题： （1） 画出哈希表的示意图； （2） 若查找关键字63需要依次与哪些关键字进行比较？ （3） 若查找关键字60需要依次与哪些关键字比较？ （4） 假定每个关键字的查找概率相等求查找成功时的平均查找长度。 2.画出对长度为10的有序表进行折半查找的判定树并求其等概率时查找成功的平均查找长度。 3.在一棵空的二叉查找树中依次插入关键字序列为1271711162139214

3、请画出所得到的二叉查找树。 4.已知如下所示长度为12的表： （Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec） (1) 试按表中元素的顺序依次插入一棵初始为空的二叉排序树画出插入完成之后的二叉排序树并求其在等概率的情况下查找成功的平均查找长度。 (2) 若对表中元素先进行排序构成有序表求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。 (3) 按表中元素顺序构造一棵平衡二叉排序树并求其在等概率的情况下查找成功的平均查找长度。 三、算法设计题 1. 已知11个元素的有序表为（05 13 19 21 37 56 64 75 80 88 92）, 请写出折半查找的算法程序查找关键字为key的数据元素 (建议上机调试)。 2.试写一个判别给定二叉树是否为二叉排序树的算法设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。 第 3 页 共 3 页