以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  北大曾考题，DS算法技巧。。。  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=39083)

--  作者：borlong
--  发布时间：10/19/2006 12:25:00 PM

--  北大曾考题，DS算法技巧。。。
（1）设可用内存单元可以处理4个纪录，采用置换选择排序的方法创建关键码有小到大
的初始顺串，对有12个纪录的文件，产生的初始顺串最少为（），最多为（）。
（2）当序列关键码依次为{61，12，72，18，79，3，48，25，65，22，90，58}时，
产生的初始顺串为（）。
============================
我的解法：（1）内存单元可以处理4个纪录，于是将12个纪录分为3（=12/4）组即可。
          可是我不知道这到底是最少还是最多？什么是最少又什么是最多呢？？？

（2）先对{61，12，72，18，79，3，48，25，65，22，90，58}写出对应的完全
二叉树，然后对其进行置换选择排序！可是我得出的结果不是答案！！

==================
希望牛人点拔小弟哦......拜谢 ^___^

--  作者：mailhzw
--  发布时间：10/19/2006 8:50:00 PM

--  
俺的梦想
--  作者：carroty
--  发布时间：10/19/2006 10:51:00 PM

--  
第一问是4,12,考虑置换的极端情况.我觉得你应该先把置换选择的概念弄清楚.

第2问按照算法一个一个往外写就好了.

串1:12,18,69,72,79
串2:3,22,25,48,58,65,90


--  作者：borlong
--  发布时间：10/20/2006 1:57:00 PM

--  
以下是引用carroty在2006-10-19 22:51:00的发言：
第一问是4,12,考虑置换的极端情况.我觉得你应该先把置换选择的概念弄清楚.

[/quote]

可是，答案是1 ，和 3。

置换选择排序，我的理解是：
先是 堆 排序， 然后再往里面填补。。。 ^___^

[quote]以下是引用carroty在2006-10-19 22:51:00的发言：

第2问按照算法一个一个往外写就好了.

串1:12,18,69,72,79
串2:3,22,25,48,58,65,90


从哪里往外写？？？？从堆里面？？？？是吗？？？？？？

--  作者：mxf3306
--  发布时间：10/20/2006 2:33:00 PM

--  
最少应该是1，即已经全部有序的状态
--  作者：mxf3306
--  发布时间：10/20/2006 2:35:00 PM

--  
具体排序过程有点模糊了。大概是一次读入四个记录，建堆，输出一个，读入一个，进行判断后决定是否加入堆中。这样考虑的话，最多的确是3。

--  作者：carroty
--  发布时间：10/20/2006 5:08:00 PM

--  
奥,我理解错了,是1和3,我理解为一个串最多有多少个元素了,现在的思维跟人不一样....
--  作者：Smilingface
--  发布时间：10/20/2006 7:13:00 PM

--  
第一问    1,3
第二问    串1:  12,18,61,72,79
             串2:   3,22,25,48,58,65,90
--  作者：borlong
--  发布时间：10/21/2006 3:05:00 PM

--  
以下是引用Smilingface在2006-10-20 19:13:00的发言：
第二问    串1:  12,18,61,72,79
              串2:   3,22,25,48,58,65,90


，小弟需要的是，这个答案的思路哦。也就是说，你的这个串是怎么得出来的啊？？？？？？？？？？？

--  作者：borlong
--  发布时间：10/21/2006 3:10:00 PM

--  
大家对《Ds》教材上，page286-287 上面对于 败者树 的算法，都能明白他的每一部思路吗？？？？？？？

尤其是page287 中 replay()中的一个函数  winner(L,i,B[i])等，这个函数的具体实现，他没有给出，这是怎么回事啊？  难道这个函数很简单？？？？？？？

也许小弟的疑问很是可爱，让牛人见笑拉。。。
可是小弟急切期待牛人的指点阿。。。。。。拜谢！！！！！

--  作者：borlong
--  发布时间：10/21/2006 3:32:00 PM

--  
以下是引用Smilingface在2006-10-20 19:13:00的发言：
第二问    串1:  12,18,61,72,79
              串2:   3,22,25,48,58,65,90



该串的得出过程是否是：（1）先建堆，堆的大小是多少呢？
                       （2）然后进行置换选择排序，就是按照page274,的图8.7所示的案例。
如果不是这样，又是怎么样的呢？

请牛人指点阿。。。。

--  作者：borlong
--  发布时间：10/21/2006 3:36:00 PM

--  
以下是引用Smilingface在2006-10-20 19:13:00的发言：

第二问    串1:  12,18,61,72,79
              串2:   3,22,25,48,58,65,90


该串的得出过程是否是：（1）先建堆，堆的大小是多少呢？
                       （2）然后进行置换选择排序，就是按照page274,的图8.7所示的案例。
如果不是这样，又是怎么样的呢？

请牛人指点阿。。。。

--  作者：Smilingface
--  发布时间：10/24/2006 6:31:00 PM

--  
设可用内存单元可以处理4个纪录
初始堆的大小当然是4啊。
以下是引用borlong在2006-10-21 15:36:00的发言：
[quote]以下是引用Smilingface在2006-10-20 19:13:00的发言：

  第二问    串1:  12,18,61,72,79
               串2:   3,22,25,48,58,65,90
  
[/quote]

该串的得出过程是否是：（1）先建堆，堆的大小是多少呢？
                        （2）然后进行置换选择排序，就是按照page274,的图8.7所示的案例。
  如果不是这样，又是怎么样的呢？

请牛人指点阿。。。。


--  作者：borlong
--  发布时间：10/24/2006 8:40:00 PM

--  
设可用内存单元可以处理4个纪录
初始堆的大小当然是4啊!!!!!!!!!!!!!!!!


也就是说，堆所对应完全二叉树的叶子数目是4，对吗？？？？？？？
还是。。。。。。^__^

--  作者：Smilingface
--  发布时间：10/25/2006 5:43:00 PM

--  
觉得你看一下书就明白了。

堆中元素是存储在内存中的，内存可以处理的最大数目的堆的大小是4，因为只有4个记录大小的内存单元啊，当然是4啦。开始在内存中建好堆之后，然后输出，检查欲进堆的元素，必须是大于才出堆的元素才能入堆，否则堆的大小减小为3（进来的这个元素要占一个记录的内存单元），然后继续照这样做下去，直到堆的大小减小为0，重建4个记录大小的堆。。。。。。。。。。。做下去就可以了。

看书，看书。。。。。:-)

以下是引用borlong在2006-10-24 20:40:00的发言：
设可用内存单元可以处理4个纪录
初始堆的大小当然是4啊!!!!!!!!!!!!!!!!


也就是说，堆所对应完全二叉树的叶子数目是4，对吗？？？？？？？
还是。。。。。。^__^


--  作者：borlong
--  发布时间：10/25/2006 6:27:00 PM

--  
感谢smilingface.

对于败者树  和胜者树 ，你有何建议啊？你能看懂吗？
您能“简单的”否说出败者树算法的思路呢？？？？？
我看的不大懂啊！还是网络上有好的资料呢？

拜谢！！！

还有，对于归并法时间复杂度：T(n)=2T(n/2)+cn
就是这个cn是什么意思啊？有什么用呢？难道是分裂的时间？？？？

W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 93.750ms