微软的半个小时面试，一个问题把我问蒙了~~~~

 
    DataType   *   Linklist  
  {  
        Interger   data;  
        Interger   *   p;  
  }  
   
  1)对一个链表，输入头指针，和要删除的节点指针，写一个Delete方法  
  2）对一个链表，输入要删除的节点指针，写一个Delete方法  
   
  对第二个问题，把我问蒙了。如果面试是问你，你做什么回答呢？大家说说吧。 问题点数：20、回复次数：51Top

1 楼xiaoyetao08（人尚未成为人）回复于 2006-10-12 17:19:56 得分 0

我的妈呀  
  够狠的微软Top

2 楼chenmaosheng（）回复于 2006-10-12 17:45:02 得分 0

DataType   *   Linklist  
  {  
  Interger   data;  
  Interger   *   p;  
  }  
   
  老实说我被你搞蒙了。  
   
  如果告诉你链表中的一个要你把它删了，这会很难吗？Top

3 楼yyaoyu（）回复于 2006-10-12 18:26:32 得分 0

?不明白  
   
  如果告诉你链表中的一个要你把它删了，这会很难吗？   对呀？  
  Top

4 楼RMB_9999999999999999（爱生活·爱青岛)(www.iQingdao.com）回复于 2006-10-12 19:27:45 得分 20

struct   linkItem  
  {  
  int   data;  
  struct   linkItem   *pNext;  
  };  
   
  linkItem   head;  
  linkItem   *pTarget;  
   
  bool   linkListDel(struct   linkItem   *pItem)  
  {  
  if(!pItem)  
  return   false;  
  if(!pItem->pNext)  
  {  
  pItem   =   0;  
  return   true;  
  }  
   
  int   dataTmp;  
  dataTmp   =   pItem->pNext->data;  
  pItem->data   =   dataTmp;  
  pItem->pNext   =   pItem->pNext->pNext;  
  return   true;  
  }Top

5 楼RMB_9999999999999999（爱生活·爱青岛)(www.iQingdao.com）回复于 2006-10-12 19:29:04 得分 0

CSDN现在的字体不好看了。代码字体是(Courier   New,   9)才好。Top

6 楼RMB_9999999999999999（爱生活·爱青岛)(www.iQingdao.com）回复于 2006-10-12 19:33:13 得分 0

刚才写得不对，现在更正：  
   
  struct   linkItem  
  {  
  int   data;  
  struct   linkItem   *pNext;  
  };  
   
  linkItem   *pTarget;  
   
  bool   linkListDel(struct   linkItem   *&pItem)  
  {  
  if(!pItem)  
  return   false;  
  if(!pItem->pNext)  
  {  
  pItem   =   0;  
  return   true;  
  }  
   
  int   dataTmp;  
  dataTmp   =   pItem->pNext->data;  
  pItem->data   =   dataTmp;  
  pItem   =   pItem->pNext;  
  return   true;  
  }Top

7 楼kingmax54212008（www.jscribe.com.cn/bbs- 一颗心，一生爱我所爱的人~）回复于 2006-10-12 21:04:23 得分 0

楼上的答得很好。  
   
  还有一题：如何防止内存泄露（memory   leak）？如果让你做一个系统防止内容泄露,你怎么做？Top

8 楼jlu3389（激情的89）回复于 2006-10-12 21:37:39 得分 0

模拟JAVA做一个垃圾回收。啊哈Top

9 楼Westhandsome（西帅）回复于 2006-10-12 21:49:25 得分 0

按lz的意思,第二个问题,没有给出头指针咯?这个没办法做的吧Top

10 楼Westhandsome（西帅）回复于 2006-10-12 21:52:21 得分 0

哦,知道了,原来如此....Top

11 楼RMB_9999999999999999（爱生活·爱青岛)(www.iQingdao.com）回复于 2006-10-12 22:02:53 得分 0

LZ,   Memory   Leak题，也是你面试的时候他们问的？Top

12 楼kingmax54212008（www.jscribe.com.cn/bbs- 一颗心，一生爱我所爱的人~）回复于 2006-10-12 22:22:29 得分 0

嗯,Memory   Leak题,面试的时候问了。Top

13 楼spirit_sheng（老盛）回复于 2006-10-12 22:40:20 得分 0

对于第二个问题,   如果是链表中的最后一个元互,   那是没法删除的Top

14 楼kingmax54212008（www.jscribe.com.cn/bbs- 一颗心，一生爱我所爱的人~）回复于 2006-10-13 09:44:57 得分 0

对.看样子这个题还是有缺陷啊。Top

15 楼forenrol（★CSDN/技能每天百练★）回复于 2006-10-13 14:54:49 得分 0

这道题很经常看到啊。。  
  思路如下：  
  把当前节点的后一个节点往前拷贝到当前节点，然后free掉当前节点就可以。  
  q   =   p->next;  
  p->data   =   q->data;  
  p->next   =   q->next;  
  以上方法即可。Top

16 楼ahone（l或许说的不对，一起学习。）回复于 2006-10-13 15:04:13 得分 0

你是怎么混进微软面试的?Top

17 楼wood542344（人生就是比当归大条）回复于 2006-10-13 15:14:37 得分 0

这个问题不难吧，链表删除是数据结构基本吧。Top

18 楼sunbird69（太阳鸟）回复于 2006-10-13 15:18:26 得分 0

微软呀     出的题哦Top

19 楼umbrella1984（雨伞(KEN)）回复于 2006-10-13 15:18:39 得分 0

把当前节点的后一节点拷贝到当前节点，然后再释放掉当前节点。  
   
  这句话怎么听起来很别扭？不等于没拷贝吗？Top

20 楼bianchenglangzi_110（）回复于 2006-10-13 15:22:02 得分 0

楼主你是工作了，还是在类似软件学院那样的学校推荐去微软面试的呀  
  Top

21 楼gxj1680（）回复于 2006-10-13 15:24:13 得分 0

这道题很经常看到啊。。  
  思路如下：  
  把当前节点的后一个节点往前拷贝到当前节点，然后free掉当前节点就可以。  
  q   =   p->next;  
  p->data   =   q->data;  
  p->next   =   q->next;  
  以上方法即可。  
   
   
  这个方法很好啊,不必管头节点,只要要删除的节点后面的每一个都向前走一个就完了Top

22 楼gxj1680（）回复于 2006-10-13 15:25:42 得分 0

我说的是每一个     循环到最后一个   都向前走一位就O了     补充下Top

23 楼gxj1680（）回复于 2006-10-13 15:27:56 得分 0

让没一个节点的value等于后面的邻接点,循环         (刚才太...失误)Top

24 楼huaxiaoxi（）回复于 2006-10-13 15:35:49 得分 0

还是看功底啊Top

25 楼yiyiemma（）回复于 2006-10-13 15:42:10 得分 0

是这样面试的啊Top

26 楼gameboy999（-'_'-）回复于 2006-10-13 15:47:56 得分 0

第二个问题要看链表示不是双向链表Top

27 楼xshsoft（internet）回复于 2006-10-13 15:51:49 得分 0

这是微软出的题吗？Top

28 楼Nowish（看我能忍耐多久）回复于 2006-10-13 15:53:35 得分 0

mark~Top

29 楼shrinerain（圣影雨）回复于 2006-10-13 15:55:56 得分 0

依次把后一个节点cp到当前节点，删除最后一个节点  
   
  这个方法很经典的啊。。。  
   
  楼主这个忘了实在不应该Top

30 楼gxj1680（）回复于 2006-10-13 15:57:33 得分 0

想想   其实只要从要删除多的节点开始,每个节点的值等于后面链接点的值(也就是将后面的节点值赋给前面的一个),这样就相当于删除了所要删除的节点了啊,  
  (补:值向前送,节点指针不变,最后一个节点指针指向的值为NULL)  
  不用管链表头和是否是双向链表的Top

31 楼goodbee（采蜂）回复于 2006-10-13 16:05:56 得分 0

不需要双向链表  
  单向链表,让当前节点的next指针指向next->next,当前节点值=next节点值.于是next节点就没有存在的必要了,而前一节点的指针指向当前节点,相当于原来的next节点.  
   
  这时,free掉next就可以了.Top

32 楼goodbee（采蜂）回复于 2006-10-13 16:07:48 得分 0

我看到这里有很多人要依次往前cp,但是这样,那链表还有什么意义呢?  
  如果学过数据结构的话,就应该知道,用链表最重要的就是为了防止增加删除节点的时候要cp后面所有的值.Top

33 楼goodbee（采蜂）回复于 2006-10-13 16:10:38 得分 0

如果当前节点是最后一个,由于不能修改前一个节点的next指针,所以是没法删除的.Top

34 楼littleXX（游鱼）回复于 2006-10-13 16:17:29 得分 0

怎么不行？！乱说，看就是不喜欢读书的。  
  老高花老些篇幅来写这个问题哟，很简单嘛，把链尾listnext.p   指向链头，一个简单的while   语句就可以找到前一个链  
  Top

35 楼goodbee（采蜂）回复于 2006-10-13 16:18:14 得分 0

人家说的是不知道链头,知道链头还讨论个屁~~~Top

36 楼goodbee（采蜂）回复于 2006-10-13 16:18:35 得分 0

littleXX(游鱼)   学过数据结构么?Top

37 楼ceci6（）回复于 2006-10-13 16:23:37 得分 0

不明白,居然还有这样的面试题.Top

38 楼rongkun06（）回复于 2006-10-13 16:58:18 得分 0

面试有这么难吗？Top

39 楼Stefine（CSDN最菜滴猩猩）回复于 2006-10-13 17:10:21 得分 0

哈哈,已经分析得挺清楚了啦  
  不难了吧Top

40 楼littleXX（游鱼）回复于 2006-10-13 17:19:21 得分 0

回   goodbee(采蜂)    
   
  数据结构没怎么学过，有时候看看人家怎么做而已  
   
  如果你看过老高的书书，其实蛮容易，照你的想法来构造链表根本不可能删除，但是真不能做到吗？其实随便一本讨论链表的书都会写，在你构造链表的时候，尾指向头成为单向的循环链表，对这个表来说每个结点都是头，呵呵，难道不能删除吗？Top

41 楼Glomb（）回复于 2006-10-13 17:28:58 得分 0

防止内存泄露的题目呢？怎么没有人回答？Top

42 楼index4（皮皮）回复于 2006-10-13 17:32:29 得分 0

好象是比较基本的嘛，链表是不需要循环的吧。楼上有位兄弟好象画蛇添足了Top

43 楼left_zxp（专逃课的左手）回复于 2006-10-13 18:02:48 得分 0

不用循环到最后，把后一个节点的内容移到要删除的节点，在删除后一个节点就可以了。Top

44 楼NowCan（城市浪人）回复于 2006-10-13 18:23:33 得分 0

被你们说晕了，到底是删一个节点还是删整个链表？Top

45 楼chaircat（chaircat）回复于 2006-10-13 19:00:16 得分 0

倒啊...这不是很明显么...  
  既然告诉你链表,意思就是知道他的一个节点...往上找头不就行了.....Top

46 楼spirit_sheng（老盛）回复于 2006-10-13 19:07:05 得分 0

楼上搞清楚没,   这是单向链表,   不是双向的,   也不是环Top

47 楼kingmax54212008（www.jscribe.com.cn/bbs- 一颗心，一生爱我所爱的人~）回复于 2006-10-14 09:51:18 得分 0

It's   totally   out   of   my   surprise.   So   many   one   focus   on   my   question.  
    Thanks   all   you   guys.   Appreciated.  
    I   apply   the   SDET   tittle   position   in   the   MS.  
    This   is   the   my   third   round   arithmetic   questions.Share   them   with   all   you   guys.Wish   it   can   be   useful   for   you.Thanks   a   lot.  
    Cheers.  
   
    1)What's   the   purpose   of   the   Binary   Tree?  
    2)How   to   avoid   the   "momery   leak"?   how   to   desgin   a   system   to   prevent   the   "momery   leak"?    
    3)Given   the   header   and   the   node   of   a   Linklist,give   the   meathod   to   delete   this   node?  
        Given   the   node   of   a   Linklist,also   the   data   filed   of   the   node   is   integer,give   the   meathod   to   delete   this   node?  
   
  Top

48 楼huyanqing（王虎）回复于 2006-10-14 21:12:16 得分 0

这个问题是这样的，把待删除的指针的下一个指针的数据域覆盖改指针数据域，然后带删除指针的链接指针指向下一个指针的下一个指针，然后将待删除指针的下一个指针删除即可Top

49 楼louisming（）回复于 2006-10-14 22:00:17 得分 0

真乱七八糟的，很上面的那个完整的程序似乎也有问题，用语言描述一下吧：  
   
  题目：已知指向该待删除节点的指针pDelete，删除该节点。  
   
  答：1、若pDelete->next空，则，pDelete   =   空   //如果待删节点最后一个的处理  
          2、若...同上...不空，则，temp   =   pDelete->next,copy   temp所有东西给pDelete，free掉temp  
   
  上面很多人已经说得很清楚了，经典问题啊，怎么还会争执这么半天？？  
   
  垃圾搜集器那个，应该是考你垃圾搜集的算法吧？说个火车算法应该就能混过去了吧？？^_^Top

50 楼ciahi（爪哇乞丐）回复于 2006-10-15 13:47:28 得分 0

把当前节点的后一个节点往前拷贝到当前节点，然后free掉当前节点就可以。  
   
  这个方法确实不错啊  
   
  偶想了半天，终于明白了，本来一直想怎么把当前结点直接删除  
  呵呵Top

51 楼LovedFox（）回复于 2006-10-15 14:20:04 得分 0

面试会出这样的题目？  
  值得怀疑）：Top

相关问题

• 帖主：kingmax54212008
• RMB_9999999999999999

• CSDN Blog
• 技术文档
• 代码下载
• 第二书店
• 读书频道