2012.9.15 搜狐笔试

来源：http://blog.csdn.net/mishifangxiangdefeng/article/details/7982883

 

一、不定项选择题

1.C/C++语言：以下打印结果为（）。

#include <iostream>
using namespace std;

void swap_int(int a, int b)
{
    int temp = a;
    a = b;
    b = temp;
}
void swap_str(char *a, char *b)
{
    char *temp = a;
    a = b;
    b = temp;
}

int main()
{
    int a = 10;
    int b = 5;
    char *str_a = "hello world";
    char *str_b = "world hello";
    swap_int(a, b);
    swap_str(str_a, str_b);
    printf("%d, %d, %s, %s", a, b, str_a, str_b);
    return 0;
}

A. 10, 5, hello world, world hello

B. 10, 5, world hello, hello world

C. 5, 10, hello world, world hello

D. 5, 10, world hello, hello world

答：A。都是按值传递，不改变原值

2. C/C++语言：请问打印的两个字符分别是（）。

#include <iostream>
using namespace std;

typedef struct object object;
struct object
{
    char data[3];
};

object obj_array[3] = {{'a', 'b', 'c'},
                        {'d', 'e', 'f'},
                        {'g', 'h', 'i'},
                        };

int main()
{
    object *cur = obj_array;
    printf("%c, %c", *(char*)((char*)(cur)+2), *(char*)(cur+2));
    return 0;
}

A.c, g

B. b, d

C. g, g

D. g, c

答：A

cur中存储的是'a‘的地址，当cur是object指针时，cur+1后cur存储是数组下一个元素的首地址，即'd'的地址。当cur是char指针时，cur+1是'a'的下一个字符的地址，即'b'的地址

3. C/C++语言：请问在64位平台机器下，以下程序的输出结果（）

char *string_a = (char*)malloc(100*sizeof(char));
char string_b[100];
printf("%d, %d",sizeof(string_a), sizeof(string_b));

A. 8, 100

B. 100, 8

C. 100, 100

D. 8, 8

答：A

string_a是一个指针，不管它指向的空间有多大，它本身的空间 是固定的。在64位平台机器下，一个指针的大小是8。

答：B

要是得到的序列为递增，应先访问左子树，再访问根结点，最后访问右子树，根据定义知为中序遍历

5. 往一个栈顺序push下列元素：ABCDE，其pop可能的顺序，下列不正确的是（）

A. BACDE

B. ACDBE

C. AEBCD

D. AEDCB

答：C。

6. 1100|1010， 1001^1001， 1001&1100分别为（）

A. 1110， 0000， 1000

B. 1000， 1001， 1000

C. 1110， 1001， 0101

D. 1000， 1001， 1000

答：A

1 | 1 = 1， 1 | 0 = 1， 0 | 0 = 0

1 ^ 1 = 0， 1 ^ 0 = 1， 0 ^ 0 = 0

1 & 1 = 1， 1 & 0 = 0， 0 & 0 = 0

7.二叉树是一种树形结构，每个节点至多有两颗子树，下列一定是二叉树的是（）

A. 红黑树

B. B树

C. AVL树

D. B+树

答：AC

8.int A[2][3] = {1, 2, 3, 4, 5, 6}, A[1][0]和*(*(A+1)+1)的值分别是（）。

A. 4， 5

B. 4， 3

C.3， 5

D.3， 4

答：A

数组是A[2][3] = {{1, 2, 3}, {4, 5, 6}}，数组下标从0开始计数。前者是第1行第0列，后者是第1行第1列

9.序列16， 14， 10， 8， 7， 9， 3， 2， 4， 1的说法下面哪一个正确（）

A. 是大顶堆

B. 是小顶堆

C. 不是堆

D. 是二叉排序树

答：A

10. 输入若已经是排好序的，下列排序算法最快的是（）

A. 插入排序

B. Shell排序

C. 合并排序

D. 快速排序

答：A

插入排序一遍扫描即可

Shell排序虽不需要交换数据，但也要进行几次插入排序

合并排序虽不需要交换数据，但也要进行lgn次合并

快速排序在数列有序的情况下效率是最低的

11.一种既有利于短作业又兼顾长期作业的调度方法是（）。

A. 先来先服务

B. 均衡调度

C. 最短作业优先

D. 最高响应比优先

答：B

12.同一进程下的线程可以共享（）

A. stack

B. data section

C. register set

D. thread ID

答：B

A是栈区。同一个进程的线程共享堆区，但是各自维护自己的栈区

B是数据区。

C是寄存器

D线程ID。同一进程的线程共享一进程ID，各自拥有自己的线程ID

参考http://blog.csdn.net/yang201240/article/details/7243991

13.系统中的“颠簸”是由（）引起的。

A. 内存容量不足

B. 缺页率高

C.交换信息量大

D. 缺页率反馈模型不正确

答：D

“颠簸”是《计算机操作系统》中的“抖动”，A和B会造成抖动，但不是主要原因。主要原因是由于每个进程的页面数没有很好地计算，导致某些页面反复地进出。

14.8瓶酒一瓶有毒，用人测试。每次测试结果8小时后才会得到，而你只有8小时的时间，最少需要（）人测试

A. 2

B. 3

D. 4

D. 6

答：B。类似不带差错控制的海明码。淘宝出过这种题。

答：ABD

TCP的关闭连接是四次握手

UDP提供的是面向无连接的不可靠服务

C参考http://blog.csdn.net/zhangjay/article/details/6403076

客户端不可以调用bind()

16. 进程间的通讯有哪几种形式（）

A. Socket

B. Pipe

C. Shared memory

D. Signal

答：ABCD

参考4-16笔试

答：AC

答：ABCDE

19.10个不同的球，放入3个不同的桶内，共有（）种方法

A. 1000

B. 720

C. 59049

D. 360

答：C

3^10

20.87的100次幂除以7的余数是多少（）

A. 1

B. 2

C. 3

D. 4

答：D

由公式(a*b)%c == (a%c)*(b%c)可知(87^100)%7=(87%7)^100=(3^100)%7

对于任意n(n>=0)，(3^n)%7只能6种可能，依次为1，3，2，6，4，5……

二、简答题

1. （1）请描述进程和线程的区别？

见4-16笔试第七题和Linux2.6进程

（2）多线程程序有什么优点，缺点？

（3）多进程程序有什么优点，缺点？与多线程相比，有何区别。

2.写代码：反转一个单链表，分别以迭代和递归形式实现

typedef struct node LinkNode;
struct node
{
    int data;
    LinkNode *Next;
};
//@ret 返回新链表头节点
LinkNode *reverse_link(LinkNode *head);
LinkNode *reverse_link_recursive(LinkNode *head);

答：

#include <iostream>
using namespace std;

typedef struct node LinkNode;
struct node
{
    int data;
    LinkNode *Next;
};
//@ret 返回新链表头节点
LinkNode *reverse_link(LinkNode *head);
LinkNode *reverse_link_recursive(LinkNode *head);
//非递归方法
LinkNode *reverse_link(LinkNode *head)
{
    LinkNode *p = head;
    while(p->Next != NULL)
        p = p->Next;
    LinkNode *ret = p;
    LinkNode *q = head;
    while(1)
    {
        while(q->Next != p)
            q = q->Next;
        p->Next = q;
        p = q;
        if(q == head)
        {
            q->Next = NULL;
            break;
        }
        q = head;
    }
    return ret;
}
//递归方法
LinkNode *reverse_link_recursive(LinkNode *head)
{
    if(head->Next == NULL)
        return head;
    LinkNode *ret = reverse_link_recursive(head->Next);
    head->Next->Next = head;
    head->Next = NULL;
    return ret;
}
//输出结果，用于测试
void Print(LinkNode *head)
{
    LinkNode *p = head;
    while(p)
    {
        cout<<p->data<<' ';
        p = p->Next;
    }
    cout<<endl;
}
//不是题目要求，用于测试
int main()
{
    int i;
    LinkNode *p = NULL;
    for(i = 0; i < 10; i++)
    {
        LinkNode *q = new LinkNode;
        q->data = i;
        q->Next = p;
        p = q;
    }
    Print(p);
    p = reverse_link(p);
    Print(p);
    p = reverse_link_recursive(p);
    Print(p);
    return 0;
}

答：最大和子序列，HDOJ1003

http://acm.hdu.edu.cn/showproblem.php?pid=1003

#include <iostream>
using namespace std;
int main()
{
    int n,m,i,j,num,start,end,start1;
    long max,temp;
    while(cin>>n)
    {
        for(j=1;j<=n;j++)
        {
            cin>>m;
            cin>>num;
            max=temp=num;
            start=start1=end=1;
            for(i=2;i<=m;i++)
            {
                cin>>num;
                if(temp>=0) {temp=num+temp;}
                else
                {
                    temp=num;
                    start1=i;
                }
                if(temp>max)
                {
                    max=temp;
                    start=start1;
                    end=i;
                }
            }
            cout<<"Case "<<j<<':'<<endl;
            cout<<max<<' '<<start<<' '<<end<<endl;
            if(j!=n) cout<<endl;
        }
    }
    return 0;
}

三、设计题