本来想去参加北大的笔试，结果去了说不给霸笔，尼玛，好吧，哥又乖乖的回来了，现在有网上有题目了，拿过来做做，好好准备下参加19号的笔试！ -------------------------------------------------------------------------------------------------------------- 答题说明： 1.答题时间90分钟，请注意把握时间； 2.试题分为四个部分：单项选择题（10题，20分）、不定向选择题（4题，20分）、填空问答（5题，40分）、综合体（1题，20分）； -------------------------------------------------------------------------------------------------------------- 一、单项选择题1.下列说法错误的是： A.SATA硬盘的速度大约为500Mbps/s B.读取18XDVD光盘数据的速度为1Gbps C.千兆以太网的数据读取速度为1Gpbs D.读取DDR3内存数据的速度为100Gbps 分析：A和B相比，怎么光盘的速度比硬盘还快？B必错无疑啊。千兆以太网的速度是1000Mbps，也可以写成1Gbps。DDR3-1600的极限传输速度是12.8GBp/s 2.（）不能用于Linux中的进程通信 A.共享内存 B.命名管道 C.信号量 D.临界区 分析：Linux中的进程通信方式有：管道，消息队列，共享内存，套接字Socket 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、++、--操作都是原子性的，则输出不可能是（）
A.01 B.10 C.12 D.22 5.给定fun函数如下，那么fun(10)的输出结果是（）
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，请问发射一次能击中目标的概率是多少？ A0.63 B0.50 C.0.32 D.0.86 二、不定向选择题 1.不记得 2.一个栈的入栈数列为：1、2、3、4、5、6；下列哪个是可能的出栈顺序。（选项不记得） 3.下列哪些代码可以使得a和b交换数值。（选项不记得） 4.A和B晚上无聊就开始数星星。每次只能数K个（20<=k<=30）A和B轮流数。最后谁把星星数完谁就获胜，那么当星星数量为多少时候A必胜？（选项不记得） 三、填空问答题 1.给你一个整型数组A[N]，完成一个小程序代码（20行之内），使得A[N]逆向，即原数组为1，2，3，4，逆向之后为4，3，2，1
2.自选调度方面的问题，题目很长，就是给你三个线程，分别采用先来先分配的策略和最短执行之间的调度策略，然后计算每个线程从提交到执行完成的时间。题目实在太长，还有几个表格。考察的是操作系统里面作业调度算法先进先出和最短作业优先。 3.有个苦逼的上班族，他每天忘记定闹钟的概率为0.2，上班堵车的概率为0.5，如果他既没定闹钟上班又堵车那他迟到的概率为1.0，如果他定了闹钟但是上班堵车那他迟到的概率为0.8，如果他没定闹钟但是上班不堵车他迟到的概率为0.9，如果他既定了闹钟上班又不堵车那他迟到的概率为0.0，那么求出他在60天里上班迟到的期望。 答案：30.6天 4.战报交流：战场上不同的位置有N个战士（n>4），每个战士知道当前的一些战况，现在需要这n个战士通过通话交流，互相传达自己知道的战况信息，每次通话，可以让通话的双方知道对方的所有情报，设计算法，使用最少的通话次数，是的战场上的n个士兵知道所有的战况信息，不需要写程序代码，得出最少的通话次数。 5.有N个人，其中一个明星和n-1个群众，群众都认识明星，明星不认识任何群众，群众和群众之间的认识关系不知道，现在如果你是机器人R2T2，你每次问一个人是否认识另外一个人的代价为O(1)，试设计一种算法找出明星，并给出时间复杂度（没有复杂度不得分）。 答案： 四、综合题 有一个淘宝商户，在某城市有n个仓库，每个仓库的储货量不同，现在要通过货物运输，将每次仓库的储货量变成一致的，n个仓库之间的运输线路围城一个圈，即1->2->3->4->...->n->1->...，货物只能通过连接的仓库运输，设计最小的运送成本（运货量*路程）达到淘宝商户的要求，并写出代码。 解答：这个题目类似的题目有： 题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1045 代码转载于网络：
|
