首页 / 软件开发 / 数据结构与算法 / 阿里巴巴2013笔试题 算法/研发岗

阿里巴巴2013笔试题 算法/研发岗2015-02-151.-7的二进制补码 （D）

（1）-7的原码   1000 0111

（2）符号位不变 1000 0111

（3）数值位取反 1111 1000

（4）加1        1111 1001

注意：

（1）正整数的补码与原码相同

（2）补码转化为原码  

补码的符号位为‘0’，原码就补码

补码的符号位为‘1’，原码就是补码的补码

2.四种介质，带宽最大：（C）

A 同轴电缆 B 双绞线 C 光纤 D 同步线

注：

（1）双绞线也称为双扭线，是最古老但又最常用的传输媒体。把两根互相绝缘的铜导线并排放在一起，然后用规则的方法绞合起来（这样做是为了减少相邻的导线的电磁干扰）而构成双绞线.

双绞线分为1类到5类，局域网中常用的为3类，4类和5类双绞线。 3类线用于语音传输及最高传输速率为 10Mbps的数据传输；4类线用于语音传输和最高传输速率为 16Mbps的数据传输；5类线用于语音传输和最高传输速率为 100Mbps的数据传输

（2）同轴电缆由内导体铜质芯线，绝缘层，网状编制的外导体屏蔽层及保护塑料外层组成 ,内导体和外导体构成一组线对。由于外导体屏蔽层的作用，同轴电缆具有很好的抗干扰性。

同轴电缆可以将 10Mb/S的基带数字信号传送1千米到 1.2千米，因此被广泛用于局域网中

（3）光纤通信就是利用光导纤维传递光脉冲来进行通信，而光导纤维是光纤通信的媒体。光纤在任何时间都只能单向传输，因此，要实行双向通信，它必须成对出现，一个用于输入，一个用于输出，光纤两端接到光学接口上。

光纤的传输系统比同轴电缆大的多，一般小同轴电缆的最大传输带宽为 20MHz左右，中同轴电缆的最大传输带宽为 60MHz左右。单根光导纤维的数据传输速率能达几Gbps，在不使用中继器的情况下，传输距离能达几十公里。

3. 进程阻塞原因 （A）

A.时间片切换   B.等待I/O  C.进程sleep   D.等待解锁

如果没有时间片轮转，那么进程就没法切换了，一个进程将独享CPU。但是不能称时间片切换导致进程阻塞。

注：

（1）进程,概念主要有两点：

第一，进程是一个实体。每一个进程都有它自己的地址空间，一般情况下，包括文本区域（text region）、数据区域（data region）和堆栈（stack region）。

文本区域存储处理器执行的代码；

数据区域存储变量和进程执行期间使用的动态分配的内存；

堆栈区域存储着活动过程调用的指令和本地变量。

第二，进程是一个“执行中的程序”。程序是一个没有生命的实体，只有处理器赋予程序生命时，它才能成为一个活动的实体，我们称其为进程。

（2）进程的三种基本状态

进程在运行中不断地改变其运行状态。通常，一个运行进程必须具有以下三种基本状态。

就绪（Ready）状态  当进程已分配到除CPU以外的所有必要的资源，只要获得处理机便可立即执行，这时的进程状态称为就绪状态。

执行（Running）状态当进程已获得处理机，其程序正在处理机上执行，此时的进程状态称为执行状态。

阻塞（Blocked）状态  正在执行的进程，由于等待某个事件发生而无法执行时，便放弃处理机而处于阻塞状态。引起进程阻塞的事件可有多种，例如，等待I/O完成、申请缓冲区不能满足、等待信件（信号）等。

进程三种状态间的转换

一个进程在运行期间，不断地从一种状态转换到另一种状态，它可以多次处于就绪状态和执行状态，也可以多次处于阻塞状态。图3_4描述了进程的三种基本状态及其转换。

（1） 就绪→执行   处于就绪状态的进程，当进程调度程序为之分配了处理机后，该进程便由就绪状态转变成执行状态。

（2） 执行→就绪   处于执行状态的进程在其执行过程中，因分配给它的一个时间片已用完而不得不让出处理机，于是进程从执行状态转变成就绪状态。

（3） 执行→阻塞   正在执行的进程因等待某种事件发生而无法继续执行时，便从执行状态变成阻塞状态。

（4） 阻塞→就绪   处于阻塞状态的进程，若其等待的事件已经发生，于是进程由阻塞状态转变为就绪状态。

关于进程的一些介绍 http://oa.gdut.edu.cn/os/multimedia/oscai/chapter2/pages/ch22.htm#页头

4.设只含根节点的二叉树高度为1，现有一颗高度为h（h>1）的二叉树上只有出度为0和出度为2的节点，那么这颗二叉树节点最少为：

A.2^h-1  B.2h-1  C.2h  D.2h+1

取H=1 则可以排除C和D

有个讨巧的方法：直接取h=3，画个图看下，显然是5，所以答案为B。

下面来分析下：如果每个节点出度要么为0要么为2，那么也就是要么自己为叶子，要么自己拥有左右儿子。那么什么情况下节点最少呢？直接沿着一条路下去保持出度为2，直到高度达到h，那么此时节点总数：2h-1。

5.给定下面程序，那么执行printf（"%d ",foo（20,13））;结果是多少：

int foo（int x,int y）  

{  

if（x <= 0 || y <= 0）return 1;  

return 3*foo（x-6,y/2）;  

}  

A.3  B.9   C.27   D.81

解：foo（20,13）->3*foo（14,6）->9*foo（8,3）->27*foo（2,1）->81foo（-4,0）=81

6.对于以下说法错误的是：

A.Dijkstra是求两点间最短路径的，复杂度：O（n^2）。

B.Floyd-Warshall是求所有点对之间最短路径的，复杂度：O（n^3）。

C.求n个数中的中位数复杂度最低为：O（n*logn）。

D.基于比较的排序算法复杂度下界为：O（n*logn）。

注：

（1）Dijkstra

http://jpkc.xaau.edu.cn/sjjg/datastru/zxxx/View/6.5.html

http://jpkc.xaau.edu.cn/sjjg/datastru/zxxx/six%20lesson/642.html

一个按路径长度递增的次序产生最短路径的算法。

该算法的基本思想是：

设置两个顶点的集合S和T＝V－S，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点v0，然后不断从集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中，集合S每加入一个新的顶点u，都要修改顶点v0到集合T中剩余顶点的最短路径长度值，集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。此过程不断重复，直到集合T的顶点全部加入到S中为止。

伪代码：

1  function Dijkstra（G, w, s）

2     for each vertex v in V[G]                        // 初始化

3           d[v] := infinity

4           previous[v] := undefined

5     d[s] := 0

6     S := empty set

7     Q := set of all vertices

8     while Q is not an empty set                      // Dijstra算法主体

9           u := Extract_Min（Q）

10           S := S union {u}

11           for each edge （u,v） outgoing from u

12                  if d[v] > d[u] + w（u,v）             // 拓展边（u,v）

13                        d[v] := d[u] + w（u,v）

14                        previous[v] := u