笔试题 (四)

1. 宿舍内有五个童鞋一起玩对战游戏，每场比赛有一些人作为红方，另外一些人作为蓝方，请问至少需要多少场比赛才能使得任意两个人之间有一场红方对蓝方和一场蓝方对红方的比赛，请写出思路

分析: 将 5 人分成两队, 最多能有 6 对对抗, 比如分成 3+2, 或 2+3. 5个同学任意两人之间有一场对抗, 那么至少需要 20 个对抗.

ceil(20/3) = 4.

2. 当存储数据量超出单节点数据管理能力的时候，可以采用的办法是数据库
sharding的解决方案，也就是按照一定的规律把数据分散存储在多个
数据管理节点N中（节点编号为0,1,2，，，，N-1）。
假设存储的数据时a  请完成为数据a计算存储节点的程序。

#define N 5
int hash(int element){
   return element*2654435761;
}
int shardingIndex(int a){
    int p = hash(a);
    _________________________; //这里是空格
    return p;
}

直接填 p mod N 就 OK 了

3. 已知某国家每年出生人口数每年递增3%，且男女比例为1:1。如果每个男性都希望找比自己小0.5到 3 岁的女性结婚，且每个女性都希望找比自己大0.5到3岁的男性结婚，适婚年龄为20到30岁，那么对该国适婚男女婚配方面的说法正确的是

A. 男女会比较均衡

B. 会产生较多剩女

C. 会产生较多剩男

D. 信息不足，无法判断

4. 下列哪两个数据结构，同时具有较高的查找和删除性能？（CD）

A．有序数组     B．有序链表      C．AVL树        D．Hash表

 

5.下列排序算法中，哪些时间复杂度不会超过nlogn？（BC）

A．快速排序     B．堆排序        C．归并排序      D．冒泡排序

解析：几种常见的排序算法对比：

排序法	平均时间	最差情形	稳定度	额外空间	备注
冒泡	O(n2)	O(n2)	稳定	O(1)	n小时较好
交换	O(n2)	O(n2)	不稳定	O(1)	n小时较好
选择	O(n2)	O(n2)	不稳定	O(1)	n小时较好
插入	O(n2)	O(n2)	稳定	O(1)	大部分已排序时较好
基数	O(logRB)	O(logRB)	稳定	O(n)	B是真数(0-9)， R是基数(个十百)
Shell	O(nlogn)	O(ns) 1<s<2	不稳定	O(1)	s是所选分组
快速	O(nlogn)	O(n2)	不稳定	O(nlogn)	n大时较好
归并	O(nlogn)	O(nlogn)	稳定	O(1)	n大时较好
堆	O(nlogn)	O(nlogn)	不稳定	O(1)	n大时较好

稳定的排序：冒泡，插入，基数，归并

 

6. 

4 初始序列为1 8 6 2 5 4 7 3一组数采用堆排序，当建堆（小根堆）完毕时，堆所对应的二叉树中序遍历序列为：（A）

A．8 3 2 5 1 6 4 7

B．3 2 8 5 1 4 6 7

C．3 8 2 5 1 6 7 4 

D．8 2 3 5 1 4 7 6

7. S市A，B共有两个区，人口比例为3：5，据历史统计A的犯罪率为0.01%，B区为0.015%，现有一起新案件发生在S市，那么案件发生在A区的可能性有多大？（）

A．37.5%       B．32.5%          C．28.6%          D．26.1%

8. Unix系统中，哪些可以用于进程间的通信？（）

A．Socket       B．共享内存       C．消息队列       D．信号量

9.  查询性能（B）

A． 在Name字段上添加主键

B． 在Name字段上添加索引

C． 在Age字段上添加主键

D． 在Age字段上添加索引

解析：

    索引：对数据库表中一列或多列的值进行排序（或构成特定的数据结构，如树或哈希表）的一种结构，使用索引可快速访问数据库表中的特定信息。

10. 下列程序的输出是：（）

#define add(a+b) a+b  

int main()  

{  

    printf(“%d ”,5*add(3+4));  

    return 0;  

}  

A．23           B．35            C．16              D．19

解析：

    宏是完全的文本替换，宏替换时容易犯的错误。使用宏时，带上括号是安全的做法。

    答案：D

11. 同一进程下的线程可以共享以下？（BD）

A． stack           B．data section        C．register set     D．file fd

解析：

    线程共享的内容包括：

1. 进程代码段
2. 进程的公有数据(利用这些共享的数据，线程很容易的实现相互之间的通讯)、
3. 进程打开的文件描述符、
4. 信号的处理器、
5. 进程的当前目录和
6. 进程用户ID与进程组ID   

    线程独有的内容包括：

1. 线程ID
2. 寄存器组的值
3. 线程的堆栈
4. 错误返回码
5. 线程的信号屏蔽码

12. 如何减少换页错误？（BD）

A  进程倾向于占用CPU

B  访问局部性（locality of reference）满足进程要求

C  进程倾向于占用I/O

D  使用基于最短剩余时间（shortest remaining time）的调度机制

AC对于减少换页错误是没有影响的.  B 不用说, 肯定有效.

D 每次选择剩余时间最少的进程执行, 这样可以减少进程切换的频率, 减少换页错误

13. 递归函数最终会结束，那么这个函数一定？（）

A 使用了局部变量

B 有一个分支不调用自身

C 使用了全局变量或者使用了一个或多个参数

D 没有循环调用

B 正确. C 可能会使递归函数结束, 但不是必须的.

14. 同步机制应该遵循哪些基本准则？（ABCD）

A．空闲让进        B．忙则等待        C．有限等待        D．让权等待

当年学习操作系统时书上没有写 D 项.

让权等待: 当进程不能进入临界区时, 进程应该放弃处理机, 避免忙等.

15. 进程进入等待状态有哪几种方式？（D）

A CPU调度给优先级更高的线程

B 阻塞的线程获得资源或者信号

C 在时间片轮转的情况下，如果时间片到了

D 获得spinlock未果

A 运行进入就绪. B 阻塞进入就绪 C. 运行到就绪 D. 运行到等待 (等待资源)

16. 关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X)，要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell的排序法，则一趟扫描的结果是(  )；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是( )。

答案：QACS QDFX RHMY

           FHCDQAMQRSYX

SHELL 排序时, 可参考 http://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F

计算快排的时候需要注意, 序列中存在两个 Q, 相等时, 不需要动, 直接跳过即可.

17. 请设计一个排队系统，能够让每个进入队伍的用户都能看到自己在队列中所处的位置和变化，队伍可能随时有人加入和退出；当有人退出影响到用户的位置排名时需要及时反馈到用户

观察者模式变形题. 关键字是 "反馈"

观察者: 用户

观察主题: 进入, 退出

当有用户退出时, 系统更新该用户之后的所有用户的位置. 用户只能从尾部进入, 因此系统只需要提供新加入队列用户的序列即可.

参考: http://blog.csdn.net/anger_coder/article/details/12756821

18. A，B两个整数集合，设计一个算法求他们的交集，尽可能的高效。

排序, 二分查找

时间复杂度为 o(max(m,n)*log(max(n, m))