数据结构考研分类复习真题 第九章 集合[39]

设有n个值不同的元素存于顺序结构中试问你能否用比(n)少的比较次数选出这n个元素中的最大值和最小值？若能请说明是如何实现的;在最坏情况下至少要进行多少次比较【西安电子科技大学 四 (分)】

对有个元素的有序表A[…]作折半查找当比较到A[]时算法结束被比较元素除A[]外还有哪几个？【燕山大学 一 (分)】

解答下面的问题

()画出在递增有序表A[]中进行折半查找的判定树

()当实现插入排序过程时可以用折半查找来确定第I个元素在前I个元素中的可能插入位置这样做能否改善插入排序的时间复杂度？为什么？

()折半查找的平均查找长度是多少？【西安电子科技大学计应用 八 (分)】

设有一组数据blackbluegreenpurpleredwhiteyellow它们的查找概率分别为 试以它们的查找概率为权值构造一棵次优查找树并计算其查找成功的平均查找长度【清华大学 七 (分)】

假定对有序表()进行折半查找试回答下列问题

()画出描述折半查找过程的判定树;

()若查找元素需依次与那些元素比较?

()若查找元素需依次与那些元素比较?

()假定每个元素的查找概率相等求查找成功时的平均查找长度【华中理工大学 二 (分)】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []