人人网研发试卷D-2015年

一、单项选择题

1、有字符序列（Q,H,C,Y,P,A,M,S,R,D,F,X）,新序列（F,H,C,D,A,M,P,S,R,Y,Q,X）是下列（）排序算法一趟扫描结果。

A、堆排序        B、快速排序        C、希尔排序        D、冒泡排序

2、当一个二叉排序树左右子树都不为空时，二叉排序树中的最大值在二叉排序树的何处（）

A、根节点        B、叶子节点        C、父节点        D、兄弟节点

3、以下哪种排序是稳定的（）

A、希尔排序        B、堆排序        C、冒泡排序        D、快速排序

4、使用 char* p = new char[100]申请一段内存，然后使用delete p释放，有什么问题（）

A、会有内存泄露        B、不会有内存泄露，但不建议用

C、编译就会报错，必须使用delete []p;        D、编译没问题，运行会直接崩溃

5、设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为哪一项（）

A、s->next=p->next；p->next=s；        B、q->next=s； s->next=p；

C、p->next=s->next；s->next=p；        D、p->next=s；s->next=q；

6、下列选项中，会导致用户进程从用户态切换到内核的操作是（）

A、仅 I、II        B、仅 I、III        C、仅 II 、III        D、I、II和III

7、用ls –al 命令列出下面的文件列表，哪个文件是符号连接文件（）

A、-rw-rw-rw- 2 hel-s users 56 Sep 09 11:05 hello 

B、-rwxrwxrwx 2 hel-s users 56 Sep 09 11:05 goodbye

C、drwxr--r-- 1 hel users 1024 Sep 10 08:10 zhang

D、lrwxr--r-- 1 hel users 2024 Sep 12 08:12 cheng > peng.yan1

8、一次期末考试，“学弱”面对两道单选题(四个选项)，完全不知所云，只得靠随机猜测。考后对答案，学霸告诉他那两道选择题至少对了一题，那么请问聪明的你，在知道至少对一题的前提下，他两道单选题全对的概率是（）

A、1/4        B、1/3        C、1/7        D、1/8

9、Linux中，一个端口能够接受tcp链接数量的理论上限是（）

A、1024        B、65535        C、65535 * 65535        D、无上限

10、定义网络传输数据包为

class packet{
     int size;
     void data[0];
}

其中data的作用是（）

A、维护数据包空间的连续性        B、数据分割位        C、指向独立的数据空间        D、无任何作用

二、填空题

11、x为整型，请用位运算实现x%8             。

12、符号-、*、$分别代表减法、乘法和指数运算，且a)三个运算符优先级顺序为：-最高，*其次，$最低；
b)运算符运算时为左结合。则5-3*2$2*4-3$2的结果为             。

三、问答题

13、删除字符串中指定的字符，如字符串”abcdeas"，需要删除的字符为“ade",则得到的结果为”bcs”。

14、有一排台阶，每个台阶上有一个非负整数，代表在该台阶上时能最多向前跳几个台阶。从第0个台阶开始跳，实现一个函数，判断是否能到达最后一个台阶。
例如： 4 2 2 1 0 2 返回 false
           2 1 3 1 1 0 返回 true

bool jump(int array[], int size)
{                 
}

15、下图所示，server接收调用方发送的请求（request）并转发给handler处理。每个调用方有名称（name）和优先级（weight），所有调用方发送同一种请求，而且有可能短时间内发送大量请求（请求尖峰）。Handler每秒最多能够处理N个请求。现在需要为server设计一个请求控制模块，要求：
        a)    调用方weight值越高的请求，平均等待时间越低
        b)    减小请求尖峰的冲击

参考答案

1、B    2、B    3、C    4、B    5、B    6、B    7、D    8、C    9、D    10、A

11、x&7

12、256

13、参考代码：

char *Delete(char str1[],char str2[]) 
{ 
    int i=0; 
    char *p1=str1; 
    while(*p1 !='\0') 
    {        
        char *p2=str2; 
        while(*p2 !=*p1 && *p2!='\0') 
        { 
            p2++; 
        }    
        if(*p2 =='\0') 
        str1[i++]=*p1; 
        p1++; 
    } 
    str1[i]='\0'; 
    return str1; 
} 

14、参考代码：

bool jump(vector<int> &array, int size,vector<bool>& considered)
{
    if (size == 1)return true;
    if (considered[size - 1])return false;
    considered[size - 1] = true;
    for (int i = 1;i<size;i++)
    {
        if (!considered[size - 1 - i] && array[size - 1 - i] == i && jump(array, size - i,considered))return true;
    }
    return false;
}

15、

a)：可使用优先级队列进行辅助，weight越大的优先级越高。由于所有请求都是同一种请求，所以可以将其统一封装管理。

在Java中可以使用 PriorityQueue<T> 进行处理，队列中存放待执行的请求。该优先级队列的元素需要继承Comparable接口用来实现比较，实现的时候用weight进行比较。

b)：为减小尖峰的冲击，可以使用线程池，即运用线程池，将可执行的线程的最大值规定下来，当尖峰来临时，线程池可根据待执行的队列中的任务数量调用线程，当线程池中的所有线程都处于busy状态的时候，剩下的任务在队列中等待。直到有空余线程的时候，再从队列中取出任务进行操作。

c)：该方法也可用于c)问题中，避免handler压力过大，对请求处理的线程数量进行限制，使得handler的处理能力高于最大任务量即可。