笔试题（多重继承）

1. 写一个在一个字符串(n)中寻找一个子串(m)第一个位置的函数。

KMP算法效率最好，时间复杂度是Ｏ(n+m)。

2. 多重继承的内存分配问题：

   比如有class A : public class B, public class C {}

   那么A的内存结构大致是怎么样的？

这个是compiler-dependent的, 不同的实现其细节可能不同。

如果不考虑有虚函数、虚继承的话就相当简单；否则的话，相当复杂。

可以参考《深入探索C++对象模型》，或者：

3. 如何判断一个单链表是有环的？（注意不能用标志位，最多只能用两个额外指针）

   struct node { char val; node* next;}

    bool check(const node* head) {} //return false : 无环；true: 有环

一种O（n）的办法就是（搞两个指针，一个每次递增一步，一个每次递增两步，如果有环的话两者必然重合，反之亦然）：

bool check(const node* head)

{

    if(head==NULL) return false;

    node *low=head, *fast=head->next;

    while(fast!=NULL && fast->next!=NULL)

    {

        low=low->next;

        fast=fast->next->next;

        if(low==fast) return true;

    }

    return false;

}