人人网研发试卷B-2015年

一、单项选择题

1、下面的排序算法中，初始数据集的排列顺序对算法的性能无影响的是（）

A、插入排序        B、堆排序        C、冒泡排序        D、快速排序

2、在以下哪个操作中， 数组比链表更快（）

A、原地逆序        B、头部插入        C、返回头节点        D、返回随机节点

3、假设某个广告展现后被点击的概率是1/3（实际远小于这个数，只是为方便计算），那该广告3次展现，被点击次数少于2次的概率是（）

A、0.74        B、0.30        C、0.26        D、0.70

4、式子7*15=133成立，则用的是几进制（）

A、7        B、8        C、9        D、11

5、若系统中有5个同类资源，有多个进程均需要使用2个，规定每个进程一次仅允许申请1个，则至多允许几个进程参于竞争，而不会发生死锁（）

A、5        B、2        C、3        D、4

6、在支持多线程的系统中，进程P创建的若干线程不能共享的是（）

A、进程P的代码段        B、进程P中打开的文件        C、进程P的全局变量        D、进程P中某线程的栈指针

7、crontab文件由6个域组成，每个域之间用空格分隔，下列哪个排列方式是正确的（）

A、MIN HOUR DAY MONTH YEAR COMMAND        B、MIN HOUR DAY MONTH DAYOFWEEK COMMAND

C、COMMAND HOUR DAY MONTH DAYOFWEEK        D、COMMAND YEAR MONTH DAY HOUR MIN

8、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（）

A、CBEFDA        B、FEDCBA        C、CBEDFA        D、不定

9、以下哪个功能比较适合使用UDP协议（）

A、数据多播        B、可靠连接        C、流量控制        D、拥塞控制

10、调用recv(int sockfd, void *buf, size_t len, int flags)的过程中，一共进行了几次内存复制操作（）

A、1        B、2        C、3        D、4

二、填空题

11、在一个请求页式存储管理系统中，进程P共有5页，访问序列为3，2，1，0，3，2，4，3，2，1，0，4，当分配给该进程的页帧数为3时，使用FIFO置换算法访问过程中缺页率为   （1）  ，使用LRU算法的缺页率为   （2）  。(小数点后保留三位)

12、2014! 的末尾有            个0。

三、问答题

13、给定一个包含大小写字母，数字，运算符的字符串，要求设计一次遍历，空间复杂度为o(1) 的算法，使得大写字母在一起，小写字母在一起，数字在一起，运算符在一起。

14、反螺旋矩阵：随机给定N*M个数（无重复），先将这N*M个数排序，然后升序放置到螺旋矩阵当中：
如，给定3*5共15个数1-15，则螺旋矩阵输出如下：        

        1   2  3  4  5

        14 15 16 17 6

        13 20 19 18 7

        12 11 10 9 8

15、对一个unsigned int32型数组a进行排序，记ni为a[i]的二进制表示中"1"的数量，指定排序策略如下：
        a)    如果ni < nj，则a[i]排在a[j]前面
        b)    如果ni == nj，按值从小到大排序

参考答案

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

11、（1）0.750    （2）0.833

12、501

13、

var str = "ABCdeaadsa12348dA D/+";
var reUp = new RegExp(/^[A-Z]+$/);
var reDown = new RegExp(/^[a-z]+$/);
var reNum =  new RegExp(/^[0-9]+$/);
var strUpperCase = new Array();
var strDownCase  = new Array();
var strNum =  new Array();
var strOther = new Array();
var newStr = new Array();
for(var i = 0; i < str.length; i++) {
    if(reUp.test(str[i])) { 
    strUpperCase.push(str[i]);
    console.log(strUpperCase);
    } 
    else if(reDown.test(str[i])) {  
        strDownCase.push(str[i]);
        console.log(strDownCase);
    } 
    else if(reNum.test(str[i])) { 
        strNum.push(str[i]);
        console.log(strNum);
    } 
    else {
        strOther.push(str[i]);
    }
}
strOther.concat(strUpperCase, strDownCase, strNum);

14、

N = 4
M = 5
l = []
for i in xrange(1, 1 + N*M):
    l.append(i)
 
m = [[None]*M for i in xrange(N)]
step = [(0, 1), (1, 0), (0, -1), (-1, 0)]
d = 0
s = (0, 0)
 
for num in l:
    m[s[0]][s[1]] = num
    ns = (step[d][0] + s[0], step[d][1] + s[1])
    if ns[0] >= N or ns[1] >= M or m[ns[0]][ns[1]] is not None:
    d = (d + 1) % 4
    ns = (step[d][0] + s[0], step[d][1] + s[1])
    s = ns
 
for i in m:
    print i

15、

#include <string.h>
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
int fun1(int x)
{
    int count  = 0;
    while(x)
    {
        count++;
        x=x&(x-1);
    }
    return count;
}
void swap(int *i,int *j)
{
    *i = *i^*j;
    *j = *i^*j;
    *i = *i^*j;
}
int main()
{
    int n =5;
    int a[n];
    int x;
    int count1,count2;
    for (int i = 0; i < n; ++i)
    {
        printf("please input the number:\n");
        std::cin>>x;
        a[i] = x;
    }
    for (int i = 1; i < n; ++i)
    {
        for (int j = n-1; j >=i; --j)
        {
            count1 = fun1(a[j]);
            count2 = fun1(a[j-1]);
            if(count1 == count2) 
            {
                if(a[j]<a[j-1])   swap(&a[j],&a[j-1]);
                else continue;
            }
            else if(count1 < count2)   swap(&a[j],&a[j-1]);
            else continue;
        }
        for (int i = 0; i < n; ++i)
        {
            std::cout<<a[i]<<"  ";
        }
        printf("\n");
    }
}