23 May 2013
答题说明:1.答题时间90分钟,请注意把握时间;2.试题分为四个部分:单项选择题(10题,20分)、不定向选择题(4题,20分)、填空问答(5题,40分)、综合体(1题,20分)。

###一、单项选择题

#####1.下列说法错误的是:

A.SATA硬盘的速度大约为500Mbps/s

B.读取18XDVD光盘数据的速度为1Gbps

C.千兆以太网的数据读取速度为1Gpbs

D.读取DDR3内存数据的速度为100Gbps

#####2.()不能用于Linux中的进程通信

A.共享内存

B.命名管道

C.信号量

D.临界区

#####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

#####4.两个等价线程并发的执行下列程序,a为全局变量,初始为0,假设printf、++、–操作都是原子性的,则输出不可能是()

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

A.01

B.10

C.12

D.22

#####5.给定fun函数如下,那么fun(10)的输出结果是()

int fun(intx)
{
    return(x==1)? 1 : (x + fun(x-1));
}

A.0

B.10

C.55

D.3628800

#####6.在c++程序中,如果一个整型变量频繁使用,最好将他定义为()

A.auto

B.extern

C.static

D.register

#####7.长为n的字符串中匹配长度为m的子串的复杂度为()
A.O(N)

B.O(M+N)

C.O(N+logM)

D.O(M+logN)

#####8.判断一包含n个整数a[]中是否存在i、j、k满足a[i] + a[j] = a[k]的时间复杂度最小值是()
A.O(n^2) B. O(n^2*logn) C. O(n^3) D. O(nlogn)

#####9.下列序排算法中最坏情况下的时间复杂度不是n(n-1)/2的是
A.快速排序 B.冒泡排序 C.直接插入排序 D.堆排序

#####10.发射三次炮弹,射中目标的概率是0.95,请问发射一次能击中目标的概率是多少?

A.0.63

B.0.50

C.0.32

D.0.86

###二、不定向选择题

#####1.进程状态转换,下列转换会发生的有() A就绪 运行 B运行 就绪 C运行 阻塞 D阻塞 运行

#####2.一个栈的入栈数列为:1、2、3、4、5、6;下列哪个是可能的出栈顺序。
A 123465 B 154623 C 312546 D 325641

#####3.下列哪些代码可以使得a和b交换数值
A b=a+b; a=a+b; b=b-a; B a=a|b; b=b+a; a=b-a; C a=a-b; b=a+b; a=b-a; D a=a+b;b=a-b;a=b|a;

#####4.两人数星星,每回数k个(20<=k<=30),设定数完最后一批的人获胜。当A先数,则星星总数为多少时,A才胜出 A 2013 B 2888 C 3935 D 4026 E 25051

###三、填空问答题

#####1.给你一个整型数组A[N],完成一个小程序代码(20行之内),使得A[N]逆向,即原数组为1,2,3,4,逆向之后为4,3,2,1

	void revense(int * a,int n) {
        int begin = 0, end = n-1;
        int tmp;
        while(begin &lt; end)
        {
                tmp = a[begin];
                a[begin] = a[end];
                a[end] = tmp;
                ++begin;
                --end;
        }
	}

#####2.自选调度方面的问题,题目很长,就是给你三个线程,分别采用先来先分配的策略和最短执行之间的调度策略,然后计算每个线程从提交到执行完成的时间。题目实在太长,还有几个表格。考察的是操作系统里面作业调度算法先进先出和最短作业优先。

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

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

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

###四、综合题

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

原文链接:阿里巴巴2013年实习生笔试题,转载请注明来源!

EOF

欢迎加微信交流与吐槽



本站总访问量次; 本站访客数人次; 本文总阅读量次;