人人网研发试卷C-2015年

一、单项选择题

1、若12*25=311成立, 则用的是几进制()

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

2、某32位系统下, C++程序如下所示,sizeof 的值应为()

char str[] = “http://www.renren.com”  (长度为21)
char *p = str ; 

请计算

sizeof (str ) = ?(1)
sizeof ( p ) = ?(2)
void Foo ( char str[100]){
    sizeof( str ) = ?(3)
}
void *p = malloc( 100 );
sizeof ( p ) = ?(4)

A、22, 22, 100, 100        B、4, 4, 4, 4        C、22, 4, 4, 4        D、22, 4, 100, 4

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

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

4、关于排序算法的以下说法,正确的是()

A、快速排序的平均时间复杂度为O(nlogn),最坏时间复杂度为O(nlogn)

B、堆排序的平均时间复杂度为O(nlogn),最坏时间复杂度为O(n^2)

C、 冒泡排序的平均时间复杂度为O(n^2),最坏时间复杂度为O(n^2)

D、归并排序的平均时间复杂度为O(nlogn),最坏时间复杂度为O(n^2)

5、假设要存储一个数据集,数据维持有序,对其的操作只有插入、删除和顺序遍历,综合存储效率和运行速度,下列哪种数据结构是最适合的是()

A、数组        B、链表        C、哈希表        D、队列

6、设有n个关键字具有相同的Hash函数值,则用线性探测法把这n个关键字映射到Hash表中需要做几次线性探测()

A、n2        B、n*(n+1)        C、n*(n+1)/2        D、n*(n-1)/2

7、数据库事务正确执行的四个基本要素不包括()

A、隔离性        B、持久性        C、强制性        D、一致性

8、下列的进程状态变化中,哪些是不可能发生的()

A、运行→就绪        B、运行→等待        C、等待→运行        D、等待→就绪

9、以下哪些方式/命令不可以查看某IP是否可达()

A、telnet        B、ping        C、tracert        D、top

10、当用一台机器作为网络客户端时,该机器最多可以保持多少个到服务端的连接()

A、1        B、少于1024        C、少于65535        D、无限制

二、填空题

11、假设网络带宽是128MB/s,网络单向延时为100ms, 1000个客户端(单线程)同时向服务器传输64KB大小的文件,每个请求大小为64KB,服务器磁盘并发写入速度30MB/s,在传输过程中,服务器吞吐量为   (1)  MB/S ,单个请求响应时间为   (2) ms。

12、由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为              

三、问答题

13、给定一棵二叉树,求各个路径的最大和,路径可以以任意节点作为起点和终点。

14、有一个链表,其中每个对象包含两个指针p1, p2,其中指针p1指向下一个对象,指针p2也指向一个对象,沿p1可以像普通链表一样完成顺序遍历,沿p2则可能会有重复。 一种可能的例子如下,其中实线箭头是p1, 虚线箭头是p2:

问题:设计函数,翻转这个链表,并返回头指针。链表节点的数据结构如下:

struct Node{
    Node * p1;
    Node * p2;
    int data;
};

函数定义如下:

Node * revert(Node* head);

15、编辑距离,又称Levenshtein距离,是指两个子串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。请尝试写出一个算法来计算两个字符串的编辑距离,并计算其复杂度?在某些应用场景下,替换操作的代价比较高,假设替换操作的代价是插入和删除的两倍, 算法该如何调整?


参考答案

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

11、(1)30    (2)700

12、53

13、

最大和只有三条路径:

1)左边某点到根结点;2)右边某点到根结点;3)左边某点到根结点再到右边某点。

递归遍历,用一个全局的变量记录最大值。

代码如下:

// 获得包含该结点的最大和 
int help(TreeNode *root, int &m) {  
    if(root == 0) return 0;   
    int l = help(root->left, m); // 获得该结点左子树最大和   
    int r = help(root->right, m);// 获得该结点右子树最大和 
    // 取左右子树和中较大的那个,如果都小于0,则左右子树都舍弃  
    int ret = max(max(l, r), 0) + root->val;    
    // 列举三种结果并与最大值做比较
    m = max(m, max(ret, l + r + root->val));  
    return ret;
} 

intmaxPathSum(TreeNode *root) {
  int max = root->val; 
  // help中max参数为引用,可视为全局变量
  help(root, max);
  return max; 
}

14、

该题思路为:

1)首先利用p1进行指针的翻转,在这个顺序遍历的过程中,使用HashMap记录当前节点的p2指向关系,并以当前节点为key,将指向的那个节点为Value存入Map。由于每个节点只有一个p2,因此key唯一。

2)当p1全部翻转完之后,对Hashmap进行遍历,由于key和value直接表明了指向与被指向的关系,因此可以直接修改key的p2,进行反转即可。

class Node{
    Node p1,p2;
    int data;
}
public class Reverse_List {
    HashMap<Node, Node> hashMap = new HashMap<Node, Node>();
    public void reverse(Node head){
        Node pre = head;
        Node cur = head.p1;
        Node realTail = cur;
        while(cur!=null){
            Node next = cur.p1;
            cur.p1 = pre;
            pre = cur;
            if(cur.p2!=null)
                hashMap.put(cur,cur.p2);
            cur = next;
        }
        head.p1 = pre;
        realTail.p1 = null;
        Set<Map.Entry<Node, Node>> entry = hashMap.entrySet();
        for(Map.Entry<Node, Node> entry1:entry){
            Node a = entry1.getKey();
            Node b = entry1.getValue();
            b.p2 = a;
        }
    }
}

15、

第一问:

该问题可使用动态规划进行解决:定义二维数组W[i][j],记录第一串的第i个和第二个串的第j个字符进行判断时候的编辑距离。

转移方程为:W[i][j] = MIN{W[i-1][j]+1, W[i-1][j-1]+k, W[i][j-1]+1},其中k表示,如果A[i]==B[j],k=0,否则为1。

该算法复杂度为O(m*n),m、n分别为字符串A、B的长度。

第二问:

在上述转移方程中,W[i-1][j]+1和W[i][j-1]+1均代表了插入或删除的情况,而中间的W[i-1][j-1]+k代表了替换的情况。

因此将W[i][j]的值的意义进行一下修改,修改为代价的值即可,此时需要对k进行修改,因为插入删除的代价都可以当做1来看,那么,k可以进行乘以2的修改,即k可能等于0,也可能是2,而不是第一问中的1了。这样就可以避免替换操作的代价。



个人资料
Bingo
等级:9
文章:694篇
访问:38.9w
排名: 1
推荐
欢迎关注 “BAT笔试面试” 微信公众号
全栈面试题,你想要的都在这^_^
上一篇: 人人网研发试卷B-2015年
下一篇:人人网研发试卷D-2015年
猜你感兴趣的圈子:
人人网笔试面试圈
标签: node、p1、cur、p2、root、面试题