风行网2012年10月17笔试题

1、给定一个字符串A和字符串B，写一函数实现在字符串A中查找字符串B首次出现的位置，如果查找不成功，则返回-1（蛮力法、KMP算法）。
解：
    （1）函数strstr()的实现

char sstrstr(const char *haystack, const char *needle)
{
    assert(needle != NULL && haystack != NULL);

    while(*haystack != '\0')
    {
        int i = 0;
        while(true)
        {
            char an = *(haystack + i);
            char bm = *(needle + i);
            if(bm == '\0')
            {
                return haystack;
            }
            if(an == bm)
            {
                i++;
            }
            else
            {
                break;
            }
        }
        haystack++;
    }
    //若needle == '\0'，则返回haystack；反之，则查找失败
    return *needle == '\0' ? haystack : NULL;
}

    （2）kmp算法的实现

//获取next数组
void get_next(cosnt char *ptn, int *next)
{
    assert(ptn != NULL && next != NULL);

    int i = 0;
    int j = -1;
    next[0] = -1;
    int plen = strlen(ptn);

    while(i < plen)
    {
        if(j == -1 || ptn[i] == ptn[j])
        {
            i++;
            j++;
            if(ptn[i] != ptn[j])
            {
                next[i] = j;
            }
            else
            {
                next[i] = next[j];
            }
        }
        else
        {
            j = next[j];
        }
    }
}
//kmp匹配
int kmp_search(const char *src, const char *ptn, int *next, int pos)
{
    int i = pos;
    int j = 0;
    if(src == NULL || ptn == NULL)
    {
        return -1;
    }
    int slen = strlen(src);
    int plen = strlen(ptn);
    if(pos < 0 || pos > slen)
    {
        return -1;
    }

    while(i < slen && j < plen)
    {
        if(j == -1 || src[i] == ptn[j])
        {
            i++;
            j++;
        }
        else
        {
            //当匹配失效时，直接用p[j_next]与s[i]比较
            j = next[j];
        }
    }
    if(j >= plen)
    {
        return i - plen;    //返回下标，从0开始
    }
    else
    {
        return -1;
    }
}

2、给定两个有序链表，将这两个有序链表合并成一个有序链表.（归并排序的思想，但是需注意的时此处为链表，指针操作稍微复杂些）
解：
    具体代码如下所示。

ListNode *mergeTwoLists(ListNode *first, ListNode *second)
{
    ListNode *node = NULL;
    ListNode **p = &node;

    while(first && second)
    {
        if(first->value <= second->value)
        {
            *p = first;
            first = first->next;
        }
        else
        {
            *p = second;
            second = second->next;
        }
        p = &((*p)->next);
    }
    if(first)
    {
        *p = first;
    }
    if(second)
    {
        *p = second;
    }
    return node;
}

3、给定两个长度相同的有序的数组，求这两个数组的中位数（使用递归实现，比较数组A和B的中位数大小，若A的中位数大于B的中位数，则这来两个数组的中位数必定在A的前半部分和在B的后半部分，反之则在A的后半部分和B的前半部分，依次而推即可得到最终的整个中位数，注意细节）
解：
    （1）将两个数组进行合并，然后取其中位数，代码略。
    （2）二分的思想。

4、面向程序设计的五个基本原则。
解：
    略。

5、TCP是如何实现流量控制的？（使用了窗口对流量实现控制）
解：
    （1）TCP利用滑动窗口实现流量控制。
　　如果发送方把数据发送的太快，接收方可能会来不及接收，这就会造成数据的丢失。
　　所谓流量控制就是让发送方的发送速率不要太快，要让接收方来得及接收。
　　利用滑动窗口机制可以很方便地在TCP连接上实现对发送方的流量控制。
　　设A向B发送数据，在连接建立时，B告诉A：“我的接收窗口是rwnd=400”（这里的rwnd表示receive window）。因此，发送方的发送窗口不能超过接收方给出的接收窗口的数值。请注意，TCP的窗口单位是字节，不是报文段。
    
    
    从图中可以看出，B进行了三次流量控制。第一次把窗口减少到了rwnd = 300，第二次又减少到了rwnd=100，最后减少到rwnd=0，即不允许发送方再发送数据了。这种使发送方暂停发送的状态将持续到主机B重新发送一个新的窗口值为止。
　　TCP为每一个连接设有一个持续计时器。只要TCP连接的一方收到对方的零窗口通知，就启动持续计时器。若持续计时器设置的时间到期，就发送一个零窗口探测报文段（携1字节数据），那么收到这个报文段的一方就重新设置持续计时器。
　　必须考虑传输速率
　　可以用不同的机制来控制TCP报文段的发送时机。如TCP维持一个变量，它等于最大报文段长度MSS。只要缓存中存放的数据达到MSS字节时，就组装成一个TCP报文段发送出去；由发送方的应用进程指明要求发送报文段，即TCP支持的推送操作；发送方的一个计时器到期，这时就把已有的缓存数据装入报文段发送出去。
　　Nagle算法：若发送应用进程把要发送的数据逐个字节地送到TCP的发送缓存，则发送方就把第一个数据字节先发送出去，把后面到达的数据字节都缓存起来。当发送方接收到第一个数据字符的确认后，再把发送缓存中的所有数据组成一个报文段发送出去，同时继续对随后到达的数据进程缓存。只有在收到对前一个报文段的确认后才继续发送下一个报文段。当数据到达较快而网络速率较慢时，用这样的方法可明显地减少所用的网络带宽。
　　TCP的拥塞控制
　　拥塞：即对资源的需要超过了可用的资源。
　　拥塞控制：防止过多的数据注入到网络中，这样可以使网络中的路由器或链路不致过载。拥塞控制所要做的都有一个前提：网络能够承受现有的网络负荷。拥塞控制是一个全局性的过程。
　　流量控制：指点对点通信量的控制，是端到端的问题。流量控制所要做的就是抑制发送端法发送数据的速率，以便使接收端来不及接收。
　　几种拥塞控制方法
　　慢启动、拥塞避免、快速重传、快速恢复。
　　慢启动和拥塞避免
　　发送方维持一个拥塞窗口的状态变量。拥塞窗口的大小取决于网络的拥塞程度，并且动态地变化。发送方让自己的发送窗口等于拥塞窗口。
　　发送方控制拥塞窗口的原则是：只要网络没有出现拥塞，拥塞窗口就再增大一些，以便把更多的分组发送出去。但只要网络出现拥塞，拥塞窗口就减少一些，以减少注入到网络中的分组数。
慢启动算法：当主机开始发送数据时，如果立即把所有的数据注入到网络，那么就有可能引起网络拥塞，因为现在并不清楚网络的负荷情况。因此，较好的方法是先探测下，即由小到大逐渐增大发送窗口，也就是说，由小到大逐渐增大拥塞窗口的数值。通常在刚刚开始发送报文段的时候，先把拥塞窗口cwnd设置为一个最大报文段MSS的数值。而在每收到一个对新的报文段的确认后，把拥塞窗口增加至多一个MSS的数值。用这样的方法逐步增大发送方的拥塞窗口cwnd，可以使分组注入到网络的速率更加合理。
    

    每经过一个传输过程，拥塞窗口cwnd就加倍。一个传输轮次所经历过的时间就是往返时间RTT。
　　另外，慢启动的“慢”并不是指cwnd的增长速率慢，而是指在TCP开始发送报文段时先设置cwnd=1，使得发送方再开始时只发送一个报文段，然后在逐渐增大cwnd。
　　为了防止拥塞窗口cwnd增长过大引起网络拥塞，还需要设置一个慢启动阈值ssthresh状态变量。慢启动阈值ssthresh的用法如下：
    

    拥塞避免算法：让拥塞窗口cwnd缓慢地增长，即每经过一个往返时间RTT就把发送方的拥塞窗口cwnd加1，而不是加倍。这样拥塞窗口cwnd按现行规律缓慢增长，比慢启动算法的拥塞窗口增长速率缓慢得多。
　　无论是慢启动阶段还是拥塞避免阶段，只要发送方判断网络出现拥塞（其根据是没有收到确认），就要把慢启动阈值ssthresh设置为出现拥塞时的发送方窗口值的一半。然后把拥塞窗口cwnd重新设置为1，执行慢启动算法。
    
 
   强调：拥塞避免并非指完全能够避免了拥塞。只是使网络比较不容易出现拥塞。
    另外还有快速重传和快速恢复机制。

6、进程和线程之间的区别。
解：　　
    （1）进程是程序的一次执行，是系统资源分配的基本单位。而线程是系统调度的基本单位。
　　（2）进程消耗的系统资源比较多，而线程基本不消耗系统资源，进程有自己的地址空间，不共享存储区域，而线程则共享其属主进程的地址空间，共享同一存储区域。
    （3）一个程序至少有一个进程，而一个进程至少有一个线程。线程是轻量型进程。

7、大量电影播放日志文件统计出前100个播放次数最多的电影名称
解：
    分而治之的思想。
　　（1）将大的日志文件hash(电影名称)%n（n根据实际情况而定），这样产生了n个小文件，这n个小文件的每一个都可以放入内存的；
　　（2）对每一个小文件进行统计其所包含的每部电影出现的次数，同时求出每个小文件中播放次数最多的100部电影；
    （3）对这n个小文件取出的n个100部电影进行统计，可以用最大堆，从而求出整个大的日志文件中前100次播放次数最多的电影名称。