腾讯2012实习生笔试题+答案解析

<a name="top" target="_blank"></a>
<div id="home">
<div id="header">
  <div id="blogTitle">
<div class="title">
<a class="headermaintitle" href="http://www.cnblogs.com/jerry19880126/" id="Header1_HeaderTitle" rel="noopener noreferrer" target="_blank">Jerry19880126</a>
</div>
<div class="subtitle"></div>
  </div>
  <div id="navigator">
<ul id="navList"><li id="nav_sitehome"><a class="menu" href="http://www.cnblogs.com/" id="MyLinks1_HomeLink" rel="noopener noreferrer" target="_blank">博客园</a></li><li id="nav_myhome"><a class="menu" href="http://www.cnblogs.com/jerry19880126/" id="MyLinks1_MyHomeLink" rel="noopener noreferrer" target="_blank">首页</a></li><li id="nav_q"><a class="menu" href="http://q.cnblogs.com/" rel="noopener noreferrer" target="_blank">博问</a></li><li id="nav_ing"><a class="menu" href="http://home.cnblogs.com/ing/" rel="noopener noreferrer" target="_blank">闪存</a></li><li id="nav_newpost"><a class="menu" href="http://i.cnblogs.com/EditPosts.aspx?opt=1" id="MyLinks1_NewPostLink" rel="noopener noreferrer" target="_blank">新随笔</a></li><li id="nav_contact"></li><li id="nav_rss"><a class="menu" href="http://www.cnblogs.com/jerry19880126/rss" id="MyLinks1_Syndication" rel="noopener noreferrer" target="_blank">订阅</a> 随笔-83  文章-4  评论-115  </li></ul>
  </div>
</div>
</div>
<div id="main">
<div id="mainContent">
  <div class="forFlow">
<div id="topics">
<div class="post">
   <h1 class="postTitle"><a class="postTitle2" href="http://www.cnblogs.com/jerry19880126/archive/2012/08/04/2623309.html" id="cb_post_title_url" rel="noopener noreferrer" target="_blank">腾讯2012实习生笔试题+答案解析</a> </h1>
   <div class="clear"></div>
   <div class="postBody">
   <div id="cnblogs_post_body">
   <p><img alt="" height="1049" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-b027500bb12a7e505df785194ca04f6e.png" width="700"></p>
   <p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-ba25276ed13576d44ca638f381ef0add.png" width="700"></p>
   <p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-fba36d41f8149c05be0346d17db29d8f.png" width="700"></p>
   <p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-813b66b908df1817b87a532d0b1cffc6.png" width="700"></p>
   <p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-880c2575824936e8fbf6fcc78e9db60d.png" width="700"></p>
   <p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-92c78190953b6c361f08235d8e827486.png" width="700"></p>
   <p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-43b83f6dacacffc7ccbafa11ed5c5781.png" width="700"></p>
   <p><img alt="" src="https://beijingoptbbs.oss-cn-beijing.aliyuncs.com/cs/5606289-38e7aa8695aaddee1ffa2120dcf25fcb.png" width="700"></p>
   <p style="text-align:center">解答（欢迎共同讨论）转载请注明来源<a href="http://www.cnblogs.com/jerry19880126/" rel="noopener noreferrer" target="_blank">http://www.cnblogs.com/jerry19880126/</a></p>
   <p>选择</p>
   <ol><li>D。循环队列的front和rear必有一个不指向实质元素，不然无法判断队列满或空。</li><li>C。是这样的原理，磁盘会一直朝某个方向旋转，不会因为处理数据而停止。本题要求顺序处理R1到R10，起始位置在R1，一周是20ms，共10个记录，所以每个记录的读取时间为2ms。首先读R1并处理R1，读R1花2ms，读好后磁盘处于R1的末尾或R2的开头，此时处理R1，需要4ms，因为磁盘一直旋转，所以R1处理好了后磁盘已经转到R4的开始了，这时花的时间为2+4=6ms。这时候要处理R2，需要等待磁盘从R5一直转到R2的开始才行，磁盘转动不可反向，所以要经过8*2ms才能转到R1的末尾，读取R2需要2ms，再处理R2需要4ms，处理结束后磁盘已经转到R5的开头了，这时花的时间为2*8+2+4=22ms。等待磁盘再转到R3又要8*2ms，加上R3自身2ms的读取时间和4ms的处理时间，花的时间也为22ms，此时磁盘已经转到R6的开头了，写到这里，大家已经可以看到规律了，读取并处理后序记录都为22ms，所以总时间为6+22*9=204ms。</li><li>A。线性表的插入和删除，只要不是针对最后一个元素，都需要元素的搬家，最坏情况是O(n)，排序用归并排序也要O(nlogn)的复杂度，其他基本排序算法最坏O(n^2)。</li><li>A。（20+10+10+10+10+10）/100=70%，耐心点就能算出。</li><li>C。操作系统，好比上地铁，旧的人先下来，新的人才能上去，所以页面调出为先，再是页面调入。页面调出之前又必须决定哪些页面需要调用。</li><li>C。类似于哈夫曼编码，最上面根结点权值为23，它的某个孩子权值为14，另一个权值为9（实质结点），权值为14的又分出两个孩子，一个权值为7，另一个权值也为7，有一个是实质结点，另一个分