OnTheWay2012
埋葬昨天的我,迎来重生的我!
posts - 15,  comments - 89,  trackbacks - 0

1.最大空间为6的循环队列队头front为3,队尾rear为0,删除一个插入两个元素后的front和rear为多少?
    我感觉这道题说的不太清楚,原因如下:对于对于循环队列有不同实现,可以采用链表的形式也可以采用数组的形式;另外即使是采用数组这种结构也有两种常用的实现方式,一种是采用一个标量来表明队列是空的 还是满的,也可以采用空一个元素的方式来表示队列是空还是满。
    根据题意应该是采用数组的形式且有一个元素没有使用,所以解题思路如下:删除元素是在队头,所以删除一个元素后队头是4;插入元素是在队尾进行,所以插入两个元素后队尾是2。
    个人感觉我的答案好像不太正确,请高手指点,谢谢。

2.N个结点的二叉树,有m个结点有两个子结点,有多少个叶子结点。
    本来以为这道题会做了并且还很简单,但是当要写出来的时候才发现原来的想法完全是错误的。恳请高人赐教。

3.有1000瓶水,其中有一瓶有毒,小白鼠只要尝一点带毒的水24小时后就会死亡,至少要多少只小白鼠才能在24小时时鉴别出那瓶水有毒。
    这道题我原来也意味最少也需要有999个小白鼠才能鉴别出来,但是我感觉这个答案肯定是错的;所以就百度了一下,发现有人说是10个小白鼠足矣,但是我看了看接下来的解释,还是没有看懂;但是我感觉他说的是对的,所以我想了大半天终于想明白了,回头看看网上关于这道题的解答确实不太容易让人明白。
    闲话少说,我的分析如下:
    一般情况下大家看到这道题的时候都会认为是999个小白鼠,那么为什么会有这种错误的想法呢?那是因为大家在思考的时候进入了一个误区,这个误区就是每只小白鼠只能喝一个瓶子里的水。其实产生这个误区也是很正常的,那么怎么才能在小白鼠喝了不同瓶子里的水的情况下也能知道哪个瓶子里的水是害死小白鼠的呢?请看下面我举的一个例子。 

  为了简单起见,我假设只有5平水,其中一瓶有毒,其他条件不变,那么按照上面的说法答案应该是4。
    现在我有三只小白鼠,它们的编号是1,2,3;五个瓶子编号是1,2,3,4,5。让1号小白鼠喝一号瓶子里的水,注意1号瓶子用二进制表示是00000001;然后让二号小白鼠喝2号瓶中的水,注意2号瓶子用二进制表示是00000010;然后让一号和二号小白鼠喝3号瓶中的水,注意3号瓶子用二进制表示是00000011;然后让三号小白鼠喝4号瓶中的水,注意4号瓶子用二进制表示是00000100;然后让一号和三号小白鼠喝5号瓶中的水,注意5号瓶子用二进制表示是00000101。那么如果1号瓶子是有毒的话1号小白鼠在24小时后死去;如果2号瓶里的水是有毒的话2号小白鼠24小时后死去;如果3好瓶子水有毒,24小时后1号和2号小白鼠死去;如果4号瓶水有毒24小时候3号小白鼠死去;如果5好瓶里的水有毒24小时候死去的应该是1号和3号小白鼠。
    综上所述鉴定5瓶水是不是有毒只需要3个小白鼠!并且有些小白鼠喝了不只一个瓶子里的水。
    大家请注意这样一个事实:需要鉴定5个瓶子里的水,而5的二进制表示是00000101;为了表示5最多使用了3个二进制位。
    请大家按照上面的方法举几个例子,例如有6、7、8、9瓶水需要鉴定。通过举这些例子后是不是得到一个结论:用二进制表示需要鉴定的瓶子数量,该二进制表示所占用的二进制位的个数就是需要的小白鼠的数量。
    根据上面的结论,1000需要10个二进制位来表示,所以这道题的答案是需要10个小白鼠!
    怎么样是不是比需要牺牲999个小白鼠更爱护小动物。
   
    但是上面的这种方法只是一种基于一些有限的例子归纳出来的,并不十分可靠。我当时根据上面的例子推导之后已经知道了答案,但是总还感觉缺少点什么。好像还没有太明白,也好像缺少了一些说服力,因为毕竟是有限的归纳。

    好了,下面就是绝对有说服力的解法:
    还是上面的第一个例子,总共有5个瓶子,需要3只老鼠;如果某个老鼠喝了水,我们就在记为1,如果老鼠没有喝那么就记为0;我们用3个二进制位表示记录情况,最左边的二

进制位代表3号老鼠,中间的二进制位代表2号老鼠,最右边的老鼠代表1号老鼠。
    1号瓶里的水被1号老鼠喝了,那么是不是应该写一个1其余的记为0,那么是不是可以写为001。
    2号瓶里的水被2号老鼠喝了,那么是不是应该写一个1其余的记为0,那么是不是可以写为010。  
    3号瓶里的水被1号和2号老鼠喝了,那么是不是应该写两个1其余的记为0,那么是不是可以写为011。
    4号瓶里的水被3号老鼠喝了,那么是不是应该写一个1其余的记为0,那么是不是可以写为100。
    5号瓶里的水被3号和1号老鼠喝了,那么是不是应该写两个1其余的记为0,那么是不是可以写为101。
    通过上面的例子是不是发现就相当于用老鼠喝不喝瓶里的水来表示数字。用10个老鼠可以表示10个二进制位,那么10个二进制位是不是可以表示最大的1024,并且每种表示法都是唯一的。

    不知道通过以上的说法是否明白了,如果还不太明白请仔细看几遍可能就明白了。

4.有一整数序列,如何求绝对值和最大的连续数字串,写出算法。
    我看到这道题是不太明白“绝对值和”是什么意思,所以导致我不明白这个题到底要求写什么。我的理解是这样的:一个整数数列,当然可能有正的也有负数,求出子数字串

的最大和是多少。举个例子:数列是-1,-2,0,89,100, -90,那么最大的和就是89+100。
    如果是按照我的理解的话这道题的答案在《数据结构和算法分析 --C语言描述》的21页。我就不在这里再说了。

5.假设有很多段ip段属于教育网的,如何尽快辨别一用户 ip是否属于教育网。
    我对网络不熟,所以不知道以下我的说法是否正确,如果不正确请高手指教。
    IP地址分为网络号和主机号,只要对某个IP与教育网的IP的网络好进行与运算即可,如果运算后还等于教育网的网络号,则是教育网的IP。

6.用java实现二叉树数据。
    不太明白实现二叉树数据是什么意思,是让写一个结点的类型,然后写一个创建二叉树的函数吗,当然了既然是用JAVA这种面向对象的语言实现的,所以一定要用类的方法实现。另外我对JAVA不熟悉,不知道JAVA里是否有模板类的说法,如果有的话最好用模板类的方法实现,这样的话不需要考虑二叉树所保存的数据的类型。
    具体代码请参见各种数据结构的书,一般这类书都会有讲解的,二叉树也不太难。
7.构造AVL树。
    正在看AVL树,所以当前还不能多说些什么。请高手评论这道题。

    这篇随笔里最让我高兴的一点就是把地三题想明白了。
    请各位高手批评指正。

posted on 2010-05-10 20:20 OnTheWay 阅读(2535) 评论(14)  编辑 收藏 引用 所属分类: 面经

FeedBack:
# re: 几道面试题,有的做出来了,有的不会做,请大家指教
2010-05-10 20:53 | 小时候可靓了
我只说第一题

0 1 2 3 4 5




我真不知道,是3 4 5 0被使用,还是3 2 1 0被使用! 他没告诉我绕序。因为插入的时候,有头插和尾插方式。

如果是3 2 1 0方式,则删除一个后是 2 1 0 再加两个,则是2 1 0 5 4

如果是3 4 5 0方式,则删除一个后是 4 5 0 ,再加两个,则是4 5 0 1 2

信口开河,如果觉得我说得不对的,尽管说!  回复  更多评论
  
# re: 几道面试题,有的做出来了,有的不会做,请大家指教
2010-05-10 21:26 | marco
说说第二题~~
m+1

设叶节点为x个,有一个子结点的为y个
对于一个节点,它都有一个父节点,即一个输入端,记为-1(根节点单独考虑)
如果有两个字节点,那么输出为2;一个子结点,输出为1;叶节点输出为0.

那么有:
x*0 + x*(-1) + y*1 + y*(-1) + m*2 + m*(-1) = -1
根节点没有输入,所以是-1
x = m+1
  回复  更多评论
  
# re: 几道面试题,有的做出来了,有的不会做,请大家指教
2010-05-10 22:00 | 小时候可靓了
@marco
嗯,利用进出平衡来计算,比较好的方法!!   回复  更多评论
  
# re: 几道面试题,有的做出来了,有的不会做,请大家指教
2010-05-10 22:15 | OnTheWay
@marco
非常感谢,终于让我明白了。  回复  更多评论
  
# re: 几道面试题,有的做出来了,有的不会做,请大家指教
2010-05-10 22:15 | OnTheWay
@小时候可靓了
也谢谢你的关注  回复  更多评论
  
# re: 几道面试题,有的做出来了,有的不会做,请大家指教
2010-05-10 23:55 | 小时候可靓了
第三题很好玩,哈哈!  回复  更多评论
  
# re: 几道面试题,有的做出来了,有的不会做,请大家指教
2010-05-11 07:13 | 杨帆
第三题,请查阅信息论有关内容,一般信息论教材第一章,第二章就够了。  回复  更多评论
  
# re: 几道面试题,有的做出来了,有的不会做,请大家指教
2010-05-11 09:02 | 英超
第四题,理解错了吧,应该是“绝对值”和“最大的连续数字串”,不是“绝对值和”。
个人意见。  回复  更多评论
  
# re: 几道面试题,有的做出来了,有的不会做,请大家指教
2010-05-11 09:03 | 英超
@英超

我的错,确实是“绝对值和”……  回复  更多评论
  
# re: 几道面试题,有的做出来了,有的不会做,请大家指教[未登录]
2010-05-12 14:11 | vane
第2题应该是2分查找,你那个方法咱不能理解,或许咱太笨......
2进制移动一位不仅仅是1这么简单的  回复  更多评论
  
# re: 几道面试题,有的做出来了,有的不会做,请大家指教[未登录]
2010-05-12 17:55 | OnTheWay
@vane
我不太明白您说的二分法是什么意思,能不能举个例子?
另外你再仔细多看几遍我说的方法的话,可能会看懂。  回复  更多评论
  
# re: 几道面试题,有的做出来了,有的不会做,请大家指教[未登录]
2010-05-12 20:25 | OnTheWay
@vane
以下代码是根据我的方法写出来的:
unsigned int Drink(unsigned int nBottleNum)
{
unsigned int nTotal = 0;

unsigned int nBitNum = 1;
for(double i = 1 ; i < sizeof(nBottleNum) * 8.0 ; i++)
{
if(pow(2.0, i) > nBottleNum)
{
nBitNum = static_cast<int>(i);
break;
}
}

for (unsigned int i = 1 ; i <= nBottleNum ; i++)
{
unsigned int nMask = 1;
cout<<"第"<<i<<"瓶水被以下老鼠喝了"<<flush;
for (unsigned int j = 1 ; j <= nBitNum ; j++)
{
if (0 != (nMask & i))
{
nTotal++;
cout<<j<<" ";
}

nMask <<= 1;
}
cout<<endl;
}

return nTotal;
}

我比较愚钝,经过3个多小时的思考后我明白了2分法,谢谢你让我又明白了一种方法  回复  更多评论
  
# re: 几道面试题,有的做出来了,有的不会做,请大家指教
2010-05-26 12:00 | luoqi
@OnTheWay

3题,要点,因为只有一瓶有毒!!!!!!!!!!  回复  更多评论
  
# re: 几道面试题,有的做出来了,有的不会做,请大家指教
2010-05-26 12:04 | luoqi
题5

ipv4是一个unsigned long

教育网,b0~bn
unsigned long user_ip;
if(user_ip <b0 || usre_ip > bn)
不是教育网
//注意多个网段,要多次比较  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2010年5月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

常用链接

留言簿(4)

随笔分类

随笔档案

友情连接

搜索

  •  

最新评论

阅读排行榜

评论排行榜