跪求一道数据结构题的答案！！急！！
.对一个由n个关键字不同的记录构成的序列,能否用比2n-3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏情况下至少进行多少次比较?清华大...
.对一个由n个关键字不同的记录构成的序列,能否用比2n-3少的次数选出该序列中
关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏情况下至少进行
多少次比较?
清华大学出版社出版的《数据结构习题（C语言版）》10.15题。我们的数据结构作业。周二要交。
在线等！
谢谢各位了！！！ 展开
关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏情况下至少进行
多少次比较?
清华大学出版社出版的《数据结构习题（C语言版）》10.15题。我们的数据结构作业。周二要交。
在线等！
谢谢各位了！！！ 展开
展开全部
算法：
1. 首先2个一组比较一轮，较大的加入序列A，较小的加入序列B，若剩下一个则同时加入序列A和B；
2. 然后在A中求最大值，在B中求最小值。
分析：
若n为偶数，设n=2k，则第一步需要k次比较，第二步取最大值和最小值各需k-1次比较，
共 k+(k-1)+(k-1) = 3k-2 = (3n-4)/2次；
若n为奇数，设n=2k+1，则第一步需要k次比较，第二步取最大值和最小值各需k次比较，
共 k+k+k = 3k = (3n-3)/2次；
1. 首先2个一组比较一轮，较大的加入序列A，较小的加入序列B，若剩下一个则同时加入序列A和B；
2. 然后在A中求最大值，在B中求最小值。
分析：
若n为偶数，设n=2k，则第一步需要k次比较，第二步取最大值和最小值各需k-1次比较，
共 k+(k-1)+(k-1) = 3k-2 = (3n-4)/2次；
若n为奇数，设n=2k+1，则第一步需要k次比较，第二步取最大值和最小值各需k次比较，
共 k+k+k = 3k = (3n-3)/2次；
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
|
广告 您可能关注的内容 |
