笔试题 (一)

1.下列说法不正确的是：
A.SATA硬盘的速度速度大约为500Mbps/s
B.读取18XDVD光盘数据的速度为1Gbps
C.千兆以太网的数据读取速度为1Gpbs
D.读取DDR3内存数据的速度为100Gbps

千兆以太网 1000Mbps

SATA 硬盘速度大约 50 MB/S

DDR3 速度在 XXGB/S

2. 如果把传输速率定义为单位时间内传送的信息量（以字节计算）多少。关于一下几种典型的数据传输速率：

1.使用USB2.0闪存盘，往USB闪存盘上拷贝文件的数据传输速率

2.使用100M以太网，在局域网内拷贝大文件时网络上的数据传输速率

3.使用一辆卡车拉1000块单块1TB装满数据的硬盘，以100km/h的速度从上海到天津（100km）一趟所等价的数据传输带宽

4.使用电脑播放MP3，电脑的PCI总线到声卡的数据传输速率

在通常情况下，关于这几个传输速率的排序正确的是：

A.4<1<2<3 B.1<4<2<3 C.4<1<3<2 D.1<4<3<2

PCI 最大速度为 100+MB/S, 但这里听歌的话, 很小的

USB 2.0 30MB/S (我的体会是 2MB/S)

卡车那个 100+GB/S

100M 以太网速度 100MBits/s

应该选 B

3. 设在内存中有P1,P2,P3三道程序，并按照P1,P2,P3的优先级次序运行，其中内部计算和IO操作时间由下表给出（CPU计算和IO资源都只能同时由一个程序占用）：

P1:计算60ms—》IO 80ms—》计算20ms

P2:计算120ms—》IO 40ms—》计算40ms

P3:计算40ms—》IO 80ms—》计算40ms

完成三道程序比单道运行节省的时间是（）
A.80ms
B.120ms
C.160ms
D.200ms

画出图, 答案是 160

4. 两个等价线程并发的执行下列程序，a为全局变量，初始为0，假设printf、++、–操作都是原子性的，则输出不肯哪个是（）

void foo() {
	if(a <= 0) 
		a ++;
	else
		a --;
	printf("%d
", a);
}

A.01
B.10
C.12
D.22

不可能是 01.

5.在c++程序中，如果一个整型变量频繁使用，最好将他定义为（）
A.auto
B.extern
C.static
D.register

search 了下, register 专门修饰频繁使用的变量

6. KMP 算法时间复杂度 o(m+n)

7. 判断一包含n个整数a[]中是否存在i、j、k满足a[i] + a[j] = a[k]的时间复杂度为（）

A.O(n) B.O(n^2) C.O(nlog(n)) D.O(n^2log(n))

先对 a 排序, O(n*logn), 然后枚举 a[k], 平移求解, 时间复杂度为 o(n*n)

不知道有没有更好的解法

8. 以下哪些进程状态转换是正确的()

A.就绪到运行 B.运行到就绪 C.运行到阻塞 D.阻塞到运行 E.阻塞到就绪

根据状态转换图, 阻塞是不能直接到运行态的.

另外, 运行到就绪, 时间片到了. 运行到阻塞, 等待资源(锁), 等待 IO

9. A和B晚上无聊就开始数星星。每次只能数K个（20<=k<=30）A和B轮流数。最后谁把星星数完谁就获胜，那么当星星数量为多少时候A必胜？（选项不记得）

A、2013   B、2888  C、4062 D、***    E、***

对于上述答案，A有必胜的策略，A、B、C、D、E都应该选择。首先，A先取，使剩余的星星为50的倍数。然后数星星的顺序为B、A、B、A……。B数k个星星，则A就数50-k个，使剩余星星始终为50的倍数，最后，一定是A数最后的星星。A必胜。

10. 有个苦逼的上班族，他每天忘记定闹钟的概率为0.2，上班堵车的概率为0.5，如果他既没定闹钟上班又堵车那他迟到的概率为1.0，如果他定了闹钟但是上班堵车那他迟到的概率为0.9，如果他没定闹钟但是上班不堵车他迟到的概率为0.8，如果他既定了闹钟上班又不堵车那他迟到的概率为0.0，那么求出他在60天里上班迟到的期望。

全概率公司, 大致算了下, 是 27 天

11. 战报交流：战场上不同的位置有N个战士（n>4），每个战士知道当前的一些战况，现在需要这n个战士通过通话交流，互相传达自己知道的战况信息，每次通话，可以让通话的双方知道对方的所有情报，设计算法，使用最少的通话次数，是的战场上的n个士兵知道所有的战况信息，不需要写程序代码，得出最少的通话次数。

12. 有一个淘宝商户，在某城市有n个仓库，每个仓库的储货量不同，现在要通过货物运输，将每次仓库的储货量变成一致的，n个仓库之间的运输线路围城一个圈，即1->2->3->4->…->n->1->…，货物只能通过连接的仓库运输，设计最小的运送成本（运货量*路程）达到淘宝商户的要求，并写出代码。

http://blog.csdn.net/qiuchenl/article/details/8895459

14. 有N个人，其中一个明星和n-1个群众，群众都认识明星，明星不认识任何群众，群众和群众之间的认识关系不知道，现在如果你是机器人R2T2，你每次问一个人是否认识另外一个人的代价为O(1)，试设计一种算法找出明星，并给出时间复杂度（没有复杂度不得分）。

o(n) 复杂度算法. 将所有的人放到一个集合中

<1> 拿出一个人a, 问他是不是认识集合中的另一个人 b

<2> 若认识, 则踢出 a, 对 b 重复步骤 <1>, 否则踢出 b, 对 a 重复步骤 <1>

实现的话, 可采用求解数组中最小值的框架

int finds(S,N)
{
    int flag=0;//用于判定是否有明星，即当前最小数另外出现几次
    int temp=0;//存放最小数在S中的位置
    for(i=1;i<N;i++)
   ｛
      if(!reg(S[i],S[temp])//如果temp标号的数小于i标号的数
     ｛
         temp=i;
         flag=0;//更换怀疑对象（最小数）时，标记清零
      ｝
      elseif(reg(S[temp]，S[i])//如果temp里存放的确实是唯一最小数是不会跑进这里来的
      {
           flag++;
`     }
    ｝
    if(flag>0) return -1;//表示没有明星,例如所有的数都相等
    return temp;//返回明星在S中的位置
}