镇海区住房建设网站怎么查,网站推广优化服务,站长推荐跳转,上海免费推广网站有哪些2013阿里巴巴暑期实习笔试 答题说明#xff1a; 1.答题时间90分钟#xff0c;请注意把握时间; 2.试题分为四个部分#xff1a;单项选择题(10题#xff0c;20分)、不定向选择题(4题#xff0c;20分)、填空问答(5题#xff0c;40分)、综合体(1题#xff0c;20分); 3.其他一…2013阿里巴巴暑期实习笔试 答题说明 1.答题时间90分钟请注意把握时间; 2.试题分为四个部分单项选择题(10题20分)、不定向选择题(4题20分)、填空问答(5题40分)、综合体(1题20分); 3.其他一些乱七八糟的考试说明。 一、单项选择题 1.下列说法不正确的是(D) A.SATA硬盘的速度速度大约为500Mbps/s B.读取18XDVD光盘数据的速度为1Gbps C.前兆以太网的数据读取速度为1Gpbs D.读取DDR3内存数据的速度为100Gbps 解析DVD的1x是1350KB16x是21600KB就算是21.6MB好了160Mbps 这图明显说明是20GB/s160Gbps; 感觉内存还没有硬盘快呢 2.(D)不能用于Linux中的进程通信 A.共享内存 B.命名管道 C.信号量 D.临界区 所谓的临界区critical section实际上指的是一段代码。选D在《Windows核心编程第五版》中对临界区的解释是它是一小段代码它在执行之前需要独占对一些共享资源的访问权。这种方式可以让多行代码以“原子方式”来对资源进行操控。这里的原子方式指的是代码知道除了当前线程之外没有其他任何线程会同时访问该资源。当然系统仍然可以暂停当前线程去调度其他线程。但是在当前线程离开临界区之前系统是不会去调度任何想要访问同一资源的其他线程。 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 完成三道程序比单道运行节省的时间是(C) A.80ms B.120ms C.160ms D.200ms 4.两个等价线程并发的执行下列程序a为全局变量初始为0假设printf、、--操作都是原子性的则输出不肯哪个是(A) void foo() { if(a 0) { a; } else { a--; } printf(%d, a); } A.01 B.10 C.12 D.22 5.给定fun函数如下那么fun(10)的输出结果是(C) int fun(int x) { return (x1) ? 1 : (x fun(x-1)); } A.0 B.10 C.55 D.3628800 6.在c程序中如果一个整型变量频繁使用最好将他定义为(D) A.auto B.extern C.static D.register 7.长为n的字符串中匹配长度为m的子串的复杂度为(B) A.O(N) B.O(MN) C.O(NLOGM) D.O(MLOGN) 解析 KMP算法不懂 8.判断一包含n个整数a[]中是否存在i、j、k满足a[i] a[j] a[k]的时间复杂度为() A.O(n3) B.O(n2lgn) C.O(n2) D.O(nlgn) 解析O(N2)的算法能想一大堆虽然最终我选的C比如说用hash的话三维遍历可以轻松编程二维遍历但是总感觉是不是应该有nlgn的算法。 9.三次射击能中一次的概率是0.95请问一次射击能中的概率是多少?(A) A.0.63 B.0.5 C.** D.0.85 10.下列序排算法中最坏复杂度不是n(n-1)/2的是_(D) A.快速序排 B.冒泡序排 C.直接插入序排 D.堆序排 二、不定向选择题 1.阻塞、就绪、运行的三态转换 2.一个栈的入栈数列为1、2、3、4、5、6;下列哪个是可能的出栈顺序。(选项不记得) 3.下列哪些代码可以使得a和b交换数值。(选项不记得) 4.A和B晚上无聊就开始数星星。每次只能数K个(20k30)A和B轮流数。最后谁把星星数完谁就获胜那么当星星数量为多少时候A必胜? A.2013 B.2886 C.4026 D......E.....(选项不记得) 三、填空问答题 1.给你一个整型数组A[N]完成一个小程序代码(20行之内)使得A[N]逆向即原数组为1234逆向之后为4321 void revense(int * a,int n) { } 2.自选调度方面的问题题目很长就是给你三个线程分别采用先来先分配的策略和最短执行之间的调度策略然后计算每个线程从提交到执行完成的时间。题目实在太长还有几个表格。考察的是操作系统里面作业调度算法先进先出和最短作业优先。 3.有个苦逼的上班族他每天忘记定闹钟的概率为0.2上班堵车的概率为0.5如果他既没定闹钟上班又堵车那他迟到的概率为1.0如果他定了闹钟但是上班堵车那他迟到的概率为0.9如果他没定闹钟但是上班不堵车他迟到的概率为0.8如果他既定了闹钟上班又不堵车那他迟到的概率为0.0那么求出他在60天里上班迟到的期望。 4.战报交流战场上不同的位置有N个战士(n4)每个战士知道当前的一些战况现在需要这n个战士通过通话交流互相传达自己知道的战况信息每次通话可以让通话的双方知道对方的所有情报设计算法使用最少的通话次数是的战场上的n个士兵知道所有的战况信息不需要写程序代码得出最少的通话次数。 先一遍遍历然后在回去 5.有N个人其中一个明星和n-1个群众群众都认识明星明星不认识任何群众群众和群众之间的认识关系不知道现在如果你是机器人R2T2你每次问一个人是否认识另外一个人的代价为O(1)试设计一种算法找出明星并给出时间复杂度(没有复杂度不得分)。 解答这个问题等价于找未知序列数中的最小数我们将reg这个函数等价为以下过程如果i认识j记作i大于等于j,同样j不一定大于等于i,满足要求i不认识j记作i int finds(S,N) { int flag0;//用于判定是否有明星即当前最小数另外出现几次 int temp0;//存放最小数在S中的位置 for(i1;i { if(!reg(S[i],S[temp])//如果temp标号的数小于i标号的数 { tempi; flag0;//更换怀疑对象(最小数)时标记清零 elseif(reg(S[temp]S[i])//如果temp里存放的确实是唯一最小数是不会跑进这里来的 { flag; } if(flag0) return -1;//表示没有明星,例如所有的数都相等 return temp;//返回明星在S中的位置 } int cha() { int i1;jN; while(iN) { if(know(i,j)) i;//认识就问下一个人 else j--;//不认识就问是否认识前一个人 if(0j) return I; break; } } 思路就是从第一个人开始问是否认识最后一个人 若认识说明肯定不是明星放弃他去问第二个人 若不认识再问是否认识第n-1个人若认识说明还不是明星不认识继续问是否认识第n-2个人 当找到明星时肯定把所有人问遍了设每个人不问自己j此时为0 跳出循环返回明星的位置 最快是第一个位置是明星问了n-1次 最差是最后一个是明星而且剩余的人都互相认识这样就问了n-1*n-1次最后一个肯定是明星了不用再问。 这种方式跟明星位置和剩余人之间认识度有关。。。。。 四、综合题 皇冠用户仓库开销有一个淘宝商户在某城市有n个仓库每个仓库的储货量不同现在要通过货物运输将每次仓库的储货量变成一致的n个仓库之间的运输线路围城一个圈即1-2-3-4-...-n-1-...货物只能通过连接的仓库运输设计最小的运送成本(运货量*路程)达到淘宝商户的要求并写出代码。 思路这个在各种online-judge平台上都有答案纯粹的数学问题 如图这是一个仓库分布的模拟假设从第i个仓库向第i1个仓库转移的物品为Pi个单位其中Pi为负表示思是从i1个仓库转移到第i个仓库第n个仓库转移到第一个仓库即为Pn设最后每个仓库平均后的货物为ave个单位则有要最小化|P1||P2|…|Pi|…|Pn| ave[i]aveA[i]-PiPi-1//平均就是每个点收到前一个节点发出的和本节点发出的加上本节点原有的 ave[1]A[1]-P1Pn//第一个节点的平均 然后设W[i]ave[i]-A[i]-PiPi-1//每个节点发出和收到的差值 于是S[i]W[1]W[2]….W[i]Pn-Pi//所有前i个节点发出收到的差值之和 即PiPn-S[i] 所以问题归结到最小化|Pn-S[1]||Pn-S[2]|…|Pn-S[n]| 所以Pn是S中位数的时候最小//pn是最后一个节点发给节点1的。 实现了但是出不来结果、、、 #include cstdlib #include iostream #include math.h #include algorithm using namespace std; const int N100; //定义数组大小 int input[N]; //输入的每个仓库原始的货物量 int sum0; //所有仓库总货物量 int s[N]; //前i个节点得到和发出只差的和这个差就是原有-平均 int avg; int n; void sort(int data[],int len) { for(int i0;ilen;i) { for(int j0;jlen-i;j) { if(data[j]data[j1]) data[j]data[j]^data[j1]; data[j1]data[j]^data[j1]; data[j]data[j]^data[j1]; } } } int main(int argc, char *argv[]) { while(cinn) { //n个仓库 for(int i1;in;i) { cininput[i]; sumsuminput[i]; avgsum/n; //平均值 } avgsum/n; } for(int i1;in;i) { s[i]input[i]s[i-1]-avg;//前i个节点的差值之和 } sort(s,5);//对数组值从小到大排序 int mids[n/2];//取中值 midabs(mid); int res0; for(int i1;in;i) { resabs(mid-s[i]); } cout最小代价是 res; system(PAUSE); return EXIT_SUCCESS; }
