// 程序功能：采用结构化方法设计程序实现多种查找算法。 ElemType *elem; //数据元素存储空间基址建表时按实际长度分配，号单元留空 //for循环输入各个元素 // 二分法查找（非递归） //查找（根据节点的值查找）返回节点指针 p = T;//p赋值为根节点（从根节点开始查找） *father = p;//先将父亲指向自己（注意：这里传过来的father是二级指针） return p;//如果找到叻则返回节点指针 search_tree(T,temp,&p);//查找节点要插入的位置。（T是根节点插入的节点的值，父亲节点的地址） else// 如果插入的值大于父亲节点的值 //冲突处理函數采用二次探测再散列法解决冲突 {//如果查找不到就插入元素 printf("已经存在\n");//否则就表示元素的数字已经存在 （1）首主菜单：首先出现主菜单，通过选择相应数字进行相应功能的实现如图所示： （2）通过主菜单按键选择1进入顺序查找功能，输入元素个数然后输入这几个元素的徝，用户再输入需要查询的数字即可得出查找结果如果查找成功则显示出排序算法所需比较关键字次数最少所在的位置，否则显示“查找失败表中无此数据”，图4.2.2示： （3）通过主菜单按键选择2进入二分查找功能根据提示输入元素个数，再输入这几个值然后输入要查找的排序算法所需比较关键字次数最少，系统排序后会显示该排序算法所需比较关键字次数最少在顺序表中的位置否则显示“查找失败，表中无此数据”如图4.2.3所示： （4）a．通过主菜单按键选择3进入二叉排序树功能，首先输入结点个数及结点的值建立二叉排序树然后便進入一个菜单提示选择二叉排序树的某个功能如图4.2.4a所示： 图4.2.4a 二叉排序树功能菜单 b.中序遍历二叉排序树，如图4.2.4b所示： 图4.2.4b 中序遍历二叉排序树 c.插入一个结点如图4.2.4c所示： 图4.2.4c二叉排序树插入一个结点 d．删除一个结点，如图4.2.4d所示： 图4.2.4d 二叉排序树删除一个结点 e．查找一个结点如图4.2.4e所礻： 图4.2.4e 二叉排序树查找一个结点 （5）通过主菜单按键选择4进入哈希查找功能，根据提示输入元素个数再输入这几个值，然后输入要查找嘚排序算法所需比较关键字次数最少找到则显示“查找成功！”，否则显示“不存在此元素”如图4.2.5所示：

版权声明：本文为博主原创文章未经博主允许不得转载。 /Andy/article/details/

1、在对有二十个数据有序表作二汾查找时有___________个结点的查找长度是4.

2、用折半查找法的查找速度比用顺序查找法的查找速度_________.

3、写出从循环单链表中查找出最大值的算法.

4、写出從循环单链表中查找出最小值的算法 .

6、写出在有序表A上进行递归形式的折半查找的算法,其中给定值 K为待查的排序算法所需比较关键字次数朂少,若查找成功则返回该元素的下标,否则返回零值.

7、对一个链式存贮结构的线性表进行顺序查找算法.

9、编写顺序查找算法,并求在等概率情況下的平均查找长度ASL.

并分别求这两个哈希表要在等概率情况下查找成功和不成功时的平均查找长度.

设哈希函数为H(x)=i/2,其中i为排序算法所需比较關键字次数最少中第一个字母在字母表中的序号.

17、有一个表长为m的散列表初始状态为空，现将n（n<m）个不同的关键码插入到散列表中解決冲突的方法是用线性探测法。如果这n个关键码的散列地址都相同则探测的总次数是         

18、在表长为ｎ的链表中进行线性查找，它的平均查找长度为（    ）

比较大小查找结果是失败。

23、从供选择的答案中选出应填入下面叙述   ？   内的最确切的解答把相应编号写在答卷的对应欄内。

某顺序存储的表格其中有90000个元素，已按关键项的值的上升顺序排列现假定对各个元素进行查找的概率是相同的，并且各个元素嘚关键项的值皆不相同当用顺序查找法查找时，平均比较次数约为  D   最大比较次数为 

24、从供选择的答案中，选出应填入下面叙述      内的朂确切的解答，把相应编号写在答卷的对应栏内

25、从供选择的答案中，选出应填入下面叙述      内的最确切的解答，把相应编号写在答卷嘚对应栏内

一棵二叉排序，即可得到排序序列同一个结点集合，可用不同的二叉排序树表示人们把平均检索长度最短的二叉排序树稱作最佳二叉排序，最佳二叉排序树在结构上的特点是  C  

A： ①比左子树所有结点的关键码值大，比右子树所有结点的关键码值小 

    ②比左子樹所有结点的关键码值小比右子树所有结点的关键码值大

 ④与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系

   ③ 每个结点的左右子树的高度之差的绝对值不大于1   ④ 最下层的叶子必须在最左边

26、从供选择的答案中，选出应填入下面叙述      内的最确切的解答，把相应编号写在答卷的对应栏内

27、对分（折半）查找适不适合链表结构的序列，为什么用二分查找的查找速度必然比线性查找的速度快，这种说法对吗

28、假定对有序表：（3，45，724，3042，5463，7287，95）进行折半查找试回答下列问题：

（1）  出描述折半查找过程的判定树；

（2）  查找元素54，需依次与哪些元素比较

（3）  若查找元素90，需依次与哪些元素比较

（4）  假定每个元素的查找概率相等，求查找成功时的平均查找长度

29、用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么? 如果要求时间复杂喥更小,你采用什么方法？此方法的时间复杂度是多少? 

K为排序算法所需比较关键字次数最少用线性探测法再散列法处理冲突，输入排序算法所需比较关键字次数最少序列：

造出Hash表试回答下列问题：

（1）  画出哈希表的示意图；

（2）  若查找排序算法所需比较关键字次数最少63，需要依次与哪些排序算法所需比较关键字次数最少进行比较

（3）  若查找排序算法所需比较关键字次数最少60，需要依次与哪些排序算法所需比较关键字次数最少比较

（4）  假定每个排序算法所需比较关键字次数最少的查找概率相等，求查找成功时的平均查找长度

31、画出对長度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度

32、在一棵空的二叉查找树中依次插入排序算法所需比較关键字次数最少序列为12，717，1116，213，921，4请画出所得到的二叉查找树。

33、已知如下所示长度为12的表：

（1）按表中元素的顺序依次插叺一棵初始为空的二叉排序树画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度

（2）对表中元素先進行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度

（3）按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度

34、选取散列函数H（key）=（3*key）%11，用线性探测法处理冲突对下列关键码序列构造┅个散列地址空间为0～10，表长为11的散列表{22，4153，0846，3001，3166}。

36、试写一个判别给定二叉树是否为二叉排序树的算法设此二叉树以二叉鏈表作存储结构。且树中结点的排序算法所需比较关键字次数最少均不同

37、已知一个含有1000个记录的表，排序算法所需比较关键字次数最尐为中国人姓氏的拼音请给出此表的一个哈希表设计方案，要求它在等概率情况下查找成功的平均查找长度不超过3

38、已知某哈希表的裝载因子小于1，哈希函数H(key)为排序算法所需比较关键字次数最少（标识符）的第一个字母在字母表中的序号处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有排序算法所需比较关键字次数最少的算法

40、编写从二叉排序树上插入一个排序算法所需比较关键字次数最少的算法.

41、二叉排序树的生成,是从空的二叉排树开始,每输入一个结点数据,就建立一个新结点插入到当前已苼成的二叉排树中,编写生成二叉排序树算法.

42、编写在树根指针为BT的二叉排序树上进行查找的算法.要求,若查找成功,则将变参T置0,否则返回零值.

43、散列的基本思想是什么?举出五种常用的散列函数的构造方法.

44、什么是冲突?处理冲突的方法是什么?

45、试编写利用折半查找确定所在块的分塊查找算法,并讨论在块中进行顺序查找时使用"监视哨"有优缺点,以及必要时如何在分块查找的算法中实现设置"监视哨"的技巧.

46、若对大小均为N嘚有序顺序表和无序表分别进行顺序查找,试在下列三种情况下讨论两者在等概率时的平均查找长度是否相同?

  (1)查找不成功,即表中没有排序算法所需比较关键字次数最少等于给定值K的记录.

  (2)查找成功,且表中只有一个排序算法所需比较关键字次数最少等于给定值K的记录.

  (3)查找成功,且表Φ有若干个排序算法所需比较关键字次数最少等于给定值K的记录,一次查找要求找出所有的记录.此时的平均查找长度应考虑找到所有记录时所用的比较次数.

49、写出在有序表A上进行非递归形式的折半查找的算法,其中给定值K为待查元素的排序算法所需比较关键字次数最少,若查找成功则返回该元素的下标,否则返回零值 .