以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 计算机考研交流 』 (http://bbs.xml.org.cn/list.asp?boardid=67) ---- [原创]北大06年试卷中的编程题(凭印象) (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=32182) |
-- 作者:dwchang -- 发布时间:5/12/2006 11:41:00 AM -- [原创]北大06年试卷中的编程题(凭印象) 有两个已排好序(从小到大)的数组A和B,长度均为n,把它们合并为一个数组,要求时间代价为O(logn),请给出算法。 ps:个人认为需要建堆,然后调整。欢迎大家讨论。 ![]() |
-- 作者:Logician -- 发布时间:5/12/2006 11:59:00 AM -- 这个不可能吧? 时间代价为O(logn),连扫描一遍数据都不够……… |
-- 作者:Logician -- 发布时间:5/12/2006 12:02:00 PM -- 会不会是“空间代价为O(logn)”? |
-- 作者:holmesyj -- 发布时间:5/19/2006 12:52:00 PM -- 倒,建议楼主发贴前先动动脑子。 首先说明一下,不是编程题,是算法设计题,不要求写具体算法,只要写思路。 题目是这样的:有两个已排好序的数组A和B,长度均为n,找出这两个数组的中间元素。要求时间代价为O(logn)。 然后再论证平均时间复杂度(要不就是最坏时间复杂度)为O(logn)。 |
-- 作者:Logician -- 发布时间:5/19/2006 3:54:00 PM --
什么叫“找出这两个数组的中间元素”呀?@_@ 是说想像他们已经合并成了一个长度为2n的数组C,然后取C的中数,是这样吗?:) [此贴子已经被作者于2006-5-19 17:45:07编辑过]
|
-- 作者:teng_t1986 -- 发布时间:5/19/2006 8:54:00 PM -- 我认为不要建堆,可以先比较两个数组的中间位置的值,根据比较结果把一个指针右移另一个左移(即始终保证一个指针右半边长度加另一个指针左半边长度和为n),直到两指针值相等或与前一次寻找位置相邻是算法结束。 因为过程为binary search,所以时间代价为O(logN),对吗? |
-- 作者:Logician -- 发布时间:5/20/2006 9:45:00 AM -- 中间有几个细节问题,我还没想明白。 比如,先取i=j=n/2,那么当A[i]<B[j]时,将i和j分别改成多少呢?是改成3n/4和n/4吗?如果这样的话,如何保证i和j的取值范围“收敛”于一点呢?如果只是i++,j--的话,就不是“二分搜索”了。 不知道你是怎么考虑的?
|
-- 作者:Supremgoooo -- 发布时间:5/21/2006 11:16:00 PM -- 这道题是学习指导与习题解析224页的7.13题,也是去年的一道家庭作业,我已经做了3个月了,之间问过许多老师或同学,所有答案都是:不会 有那个超级超级超级牛人能给个程序? |
-- 作者:Logician -- 发布时间:5/22/2006 4:42:00 AM -- 下面的是phoenixinter牛人给的算法: Say the two arrays are sorted and increasing, namely A and B. Time complexity: O(logn) |
-- 作者:Logician -- 发布时间:5/22/2006 9:44:00 AM -- 实现了一下。 蛮有意思的一道题。 呵呵。 void insertionSort(int X[], int start, int end) void main() //下面将A、B归并到数组C中,并直接输出C[k-1],作为对照。 [此贴子已经被作者于2006-5-22 12:07:32编辑过]
|
-- 作者:Supremgoooo -- 发布时间:5/22/2006 12:53:00 PM -- 对!....看来我还很渺小.... Run the algorithm on the two new arrays. 这道题10分,这句话值5分吧 btw:考试时,我这道题做了1个多小时,当时急得满头大汗。我一直在寻找while中mid,right,left的关系,却从未想过用递归。而且因为这道题,我的整个考试时间全乱了,后面的os部分写的飞快,最后也没有检查....其实今年就两道难题——还有os那道作业题,我记得题目说“CPU可以抢占”,不知道是当时太紧张看错了还是确实如此,如果CPU可以抢占,那么最高相应比就需要列很多方程,也会产生抖动——除此之外,都是中等或以下的题,可是今年能考130左右的很少,估计都是背着两道题折腾的吧。 |
-- 作者:Logician -- 发布时间:5/22/2006 1:14:00 PM -- 能回忆一下那道OS题吗?@_@ |
-- 作者:Supremgoooo -- 发布时间:5/22/2006 9:45:00 PM -- 那道题大概有10个作业,现在已经无法回忆,但是我回忆的题干大概如下: 以北大教材66页表3-3为例: 有4个作业,分别为: 作业 进入时间 估计运行时间(分钟) JOB1 8:00 120 JOB2 8:50 30 JOB3 9:00 10 JOB4 9:50 20 系统采用最高响应比优先(HRN)调度算法,采用多道程序设计思想,CPU可以抢占,问执行结果。
|
-- 作者:Logician -- 发布时间:5/22/2006 9:49:00 PM -- 作业调度不同于进程调度,作业一旦调入系统,在执行完之前是不会被换出的。抢占只是针对进程而言的吧? [此贴子已经被作者于2006-5-22 22:34:35编辑过]
|
-- 作者:Supremgoooo -- 发布时间:5/23/2006 10:59:00 AM -- 本题说采用多道程序设计,意思是说一个作业一旦收容后,如果满足调度算法,就立刻进入内存,然后就主要是进程在内存中的调度了。整个过程按HRN算法进行。在进程的执行过程中,不涉及与外存的交换,一个进程只有被全部执行完后才被转入输出井中。 这里对收容一词作一点解释:北大的教材对收容的观点是作业的提交过程所需的时间是可以忽略不计的,一个作业到达时间即表示其被收容完毕的时间,处于收容态的某个作业一旦满足调度算法,就可以被调度,即一个作业被不被调度只于其是否被收容有关。(而其他教材,如清华的教材对收容的理解为:一批作业中的最后一个到达后之前的作业才全部收容完毕,即调度算法与所有作业的到达时间都有关系。这两种思想在做题时有时候会得到完全不同的答案) 对本题,就是说一个作业被调度取决于它到达的时间和是否满足调度算法。可以认为到达的作业都在输入井中,可以随时被调度。
[此贴子已经被作者于2006-5-23 14:45:33编辑过]
|
-- 作者:teng_t1986 -- 发布时间:5/27/2006 10:36:00 AM -- 不好意思许久没来了 下面那个算法思想就是我说的…… 一开始取i=j=n/2,另设一个变量dist存储步长值,初始时dist为n/4,然后每次循环dist/=2,当A[i]<B[j]时,i+=dist,j-=dist。算法结束时dist==1或A[i]==B[j]。 应该是这样…… 我也看了下那本习题集,就是这题,花了我15分钟哦 |
-- 作者:teng_t1986 -- 发布时间:5/27/2006 11:04:00 AM -- 应该可以用非递归吧…… 看看这个程序: int find_pivot(int *A,int *B,int n){ int pa,pb; pa=pb=n/2; int dist=n/4; while(dist>1){ if(A[pa]==B[pb]){ if(A[pa]<B[pb]){ dist/=2; 望高人指教!! |
-- 作者:teng_t1986 -- 发布时间:5/27/2006 11:14:00 AM --
|
-- 作者:Logician -- 发布时间:5/27/2006 12:07:00 PM -- 嗯。了解。谢谢!:) |
-- 作者:Logician -- 发布时间:5/27/2006 12:08:00 PM -- 强! |
-- 作者:pkucyh -- 发布时间:5/27/2006 12:52:00 PM -- 厉害啊 |
-- 作者:teng_t1986 -- 发布时间:5/27/2006 6:22:00 PM -- Logician你是斑竹吧?我很想要一份pkucs06的考题(我07考),可惜现在没有权限访问你们的ftp server……,可以传一份到我的邮箱terran_lucker@sohu.com吗?谢谢你啊! |
-- 作者:Logician -- 发布时间:5/27/2006 6:57:00 PM -- 北京大学2006年计算机软件基础考研试题(回忆版) 06年没有官方的完整题(北大还开始没有卖今年的真题)。 版上有一些今年考过的研友发的回忆题和解答,如:http://www.ieee.org.cn/dispbbs.asp?boardID=67&ID=33097 今年的“数学基础”试题我没有见到过系统的回忆和整理。 再等两、三个月,应该北大就会开始卖了。
|
-- 作者:teng_t1986 -- 发布时间:5/27/2006 7:14:00 PM -- 下下来了,谢谢你啊! |
-- 作者:Logician -- 发布时间:5/27/2006 7:15:00 PM -- 不客气。:) 有空多发点原创啊。^_^ |
-- 作者:Supremgoooo -- 发布时间:5/28/2006 4:49:00 PM -- 不对。。想法不错
|
-- 作者:Supremgoooo -- 发布时间:5/28/2006 4:52:00 PM --
|
-- 作者:teng_t1986 -- 发布时间:5/28/2006 4:57:00 PM --
哪儿错了啊?望指出。 |
-- 作者:Supremgoooo -- 发布时间:5/28/2006 5:12:00 PM -- 假如while不执行,一般不对; 假如while执行,那么在没有执行if(相等)的情况下,有两种跳出的情况,而这两种情况不一定总是a被返回吧。 本想修改一下,但我的vc又坏了,你先自己改一下吧!
[此贴子已经被作者于2006-5-28 17:32:56编辑过]
|
-- 作者:teng_t1986 -- 发布时间:5/28/2006 6:01:00 PM --
对……我dist变量用的太草率了,边界没处理好……sigh,谢谢高人! |
-- 作者:teng_t1986 -- 发布时间:5/28/2006 6:31:00 PM -- 又改了一下,可以处理n=3了: int find_pivot(int *A,int *B,int n){ int pa,pb; pa=pb=n/2; int dist=n/4; while(dist>=1){ if(A[pa]==B[pb]){ if(A[pa]<B[pb]){ dist/=2; return A[pa]; 不过n=2是还是不行(还没习惯在电脑面前思考:<),比如说A=1,3,B=2,3,一上来pa==pb==A[1],于是便返回3…………55555555555555555
|
-- 作者:Supremgoooo -- 发布时间:5/28/2006 10:11:00 PM -- 不仅仅是n=1,2,3时,你的dist是可能的答案所在范围的半长,当它跳出while时——如果不是从if(相等)这个条件,那么也有好几种情况,不能一概的返回a的值。你可以看一下前面逻辑员版主写的返回条件,要分子数列1,2长度讨论。你这里要分1,2,3讨论。 没关系,你已经写的不错了,今年那些考上的同学多数也没有作出这道题 |
-- 作者:teng_t1986 -- 发布时间:5/28/2006 10:23:00 PM -- ……真的要做硬性讨论阿…… 另外,n==1时好像无论如何都是正确的吧? 不过我刚刚找了一下,题目好像是只要求写出算法思想,不要写代码吗? 我会努力找出不要硬性讨论的算法的…… |
-- 作者:cozy1984 -- 发布时间:5/29/2006 -- 我认为可以不用什么递归,也行啊! int i,j,k; int c[2*n-1] i=j=k=0; while(i<n and j<n) { if (a[i]<b[j]) c[k++]=a[i++]; else c[k++]=b[j++]; } 大家讨论讨论,我认为这个也可以实现把. |
-- 作者:Logician -- 发布时间:5/29/2006 12:16:00 AM -- 这个的时间复杂度就不是O(log n)了吧?而且还需要Θ(n)的辅助空间。 |
-- 作者:cozy1984 -- 发布时间:5/29/2006 12:21:00 AM -- 哦,我错了. 头脑发热去了,题目要求没看清. 惭愧啊! |
-- 作者:Logician -- 发布时间:5/29/2006 12:29:00 AM -- :) |
-- 作者:leeweui -- 发布时间:5/29/2006 11:12:00 PM -- 真的假的啊 怎么北大的数据结构教材上说排序算法的时间代价上限是O(nlogn)呢? |
-- 作者:Logician -- 发布时间:5/29/2006 11:28:00 PM -- 倒……… 麻烦楼上的看帖和看书都仔细一点啊…… 1、楼主的题目说的是两个已经排好序的数列(这种情况下,有O(n)复杂度的算法将其合并为一个),而不是两个无序数列。 2、楼主的回忆确实是有问题,后面holmesyj已经给出了正确的版本。 3、“北大的数据结构教材上说排序算法的时间代价上限是O(nlogn)”。首先,应该叫“渐进时间复杂度下限”,不是“上限”。其次,这个下限只对“基于比较的排序”有效,对于其它基于数值的排序(如基数排序、桶排序等)无效。再次,这个下限是最坏情况下的,前面已经说了,当A和B都是已排序数列时,显然有O(n)时间的算法(如MergeSort中用的Merge过程)。 |
-- 作者:teng_t1986 -- 发布时间:5/31/2006 9:23:00 AM -- 唉,真是没办法了,我后来又想在原来那个算法基础上改一下:从保存两个值改为保存4个值,再在算法结束时求那四个值的中值(这样一般n==2的情况就解决了,且最后返回值也不是从单一数组中选择了),可惜还是碰到了特殊情况…………事到如今,我只能庆幸自己不是06考的了……………… 另外,指定习题集的7.17题,已知数组中只有0,1,2三个值,要求在O(logn)时间内排序,这题正确吗?我觉得就是荷兰国旗问题,至少也要用O(n)一次遍历呀,还望高人指教(最好能给出O(logn)的代码)。 |
-- 作者:Supremgoooo -- 发布时间:5/31/2006 2:38:00 PM -- 二分查找有O(logn)的时间效率,因为它避开了近一半的内容。对于这道排序来说,哪怕数组中就剩了1个数,也要先看一下它是几,所以任何一个单元都是不能不看的(个人认为),于是得出结论:下限至少是O(n),即看一遍 基于比较的排序算法上面已经给出了时间下限,若这道题有解,肯定不是基于比较的排序 不基于比较的排序比较适于这题的是桶排序,时间复杂为O(n+3)=.O(n) 看起来不像是出错了,而只有不看一些单元才能满足条件,但是究竟满足什么样条件的单元可以不看呢??我感觉题目少条件,例如n=3时,若0,1,2都出现1次,则第三个单元是可以不看的。一般的情况就不知道了。。 |
-- 作者:chenminyi -- 发布时间:7/29/2006 10:16:00 PM -- 这个答案如何:因为A,B两数组皆已经排好序,很容易知道median[A]和median[B],比较之。 case1:median[A]>=median[B],去掉A的后半部分和B的前半部分,因为A的后半部分>=median[A]>=median[B]>=B的前半部分,整个序列的median肯定不在这被去掉的元素中。 case2:median[A]<median[B],去掉A的前班部分和B的后半部分,与case1中同样的道理。 这样算法规模N->N/2,每次规模减半。 所以算法复杂度是log(N) 这是《算法导论》上的课后习题,我当时看了就想出这么个算法。 |
-- 作者:淘客 -- 发布时间:7/30/2006 9:08:00 PM -- 领教领教! |
-- 作者:jingmouren -- 发布时间:7/31/2006 10:27:00 AM -- 设A,B 是长为n 的数表,已经按照非降顺序排好。如果将这2n 个数全体排序,处于第n 个位置的数称为中位数。设计一个最坏情况下O(logn)时间的算法求A 和B 的中位数。 1.描述算法的设计思想; 2.证明算法的时间复杂性。 |
-- 作者:freeask -- 发布时间:8/3/2006 11:30:00 AM -- 牛人》》》》》》》!!! |
-- 作者:NeverExist -- 发布时间:8/6/2006 5:59:00 PM -- hehe ,遇上数组要求logn的算法,直接就想到二分了~ 这个题很经典,很多地方都出现过,挺好想出来的~ |
-- 作者:Szeus -- 发布时间:11/26/2007 5:00:00 PM -- 不错,学习中 |
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
207.031ms |