2013阿里巴巴笔试题.pdf

一 单项选择题 1 下列说法不正确的是 B A SATA 硬盘的速度速度大约为 500Mbps s B 读取 18XDVD 光盘数据的速度为 1Gbps C 前兆以太网的数据读取速度为 1Gpbs D 读取 DDR3 内存数据的速度为 100Gbps 解析 有说 B 的 有说 D 的 B 肯定是不对的吧 关于 B 选项 理论上讲 DVD 的 1 倍速是 1350KB s CD 是 150KB s DVD 的 1 倍速等于 CD 的 9 倍速 因为 CD 容量是 700MB 左右 DVD 单面单层 DVD 5 是 4 7GB 实际为 4 37GB DVD 单面单 层的容量是 CD 的 6 4 倍左右 所以 1 倍速的播放器在 80 分钟内把一张 700MB 的 CD 读取出来 700MB 1024 150KB s 60 79 6min 1 倍速的播放器在 60 分钟内把一张 4 7GB 的 DVD 读出来 4 37GB 1024 1024 1350KB s 60 56 6min DVD 的倍速 1x 1 倍速 基本传输速率为 1350KB s 2x 2 倍速 基本传输速率为 2700KB s 4x 4 倍速 基本传输速率为 5400KB s 18x 18 倍速 基本传输速率为 24300KB s 23M CD 的倍速 1x 1 倍速 基本传输速率为 150KB s 2x 2 倍速 基本传输速率为 300KB s 4x 4 倍速 基本传输速率为 600KB s 8x 8 倍速 基本传输速率为 1200KB s 2 D 不能用于 Linux 中的进程通信 A 共享内存 B 命名管道 C 信号量 D 临界区 每个进程访问临界资源的那段代码称为临界区 临界资源就是每次只允许一个进程访问的共 享资源 解析 Linux 进程间通信的几种主要手段简介 1 管道及有名管道 管道可用于具有亲缘关系的进程间通信 有名管道克服了管道没有名字的限制 因此 除了具有管道所具有的功能外 它还允许无亲缘关系进程间通信 2 信号 信号是比较复杂的通信方式 用于通知接收有某种事件发生 除了用于进程间通信外 进 程还可以发送信号给进程本身 linux 除了支持 Unix 早期信号语义函数 signal 外 还支持语义符合 Posix 标准的信号函数 sigaction 实际上 该函数是基于 BSD 的 BSD 为了实现可靠信号机制 又能够统一对 外接口 用 sigaction 函数重新实现了 signal 函数 3 消息队列 消息队列是消息的链接表 包括 Posix 消息队列和 system V 消息队列 有足够权限 的进程可以向队列中添加消息 被赋予读权限的进程则可以读走队列中的消息 消息队列客服了信号承载 信息量少 管道只能承载无格式字节流以及缓冲区大小受限等缺点 4 共享内存 使得多个进程可以访问同一块内存空间 是最快的可用 IPC 形式 是针对其他通信 机制运行效率较低而设计的 往往与其他通信机制 如信息量结合使用 来达到进程间的同步及互斥 5 信息量 主要作为进程间以及同一进程不同线程之间的同步手段 6 套接口 更为一般的进程间通信机制 可用于不同机器之间的进程间通信 Linux 线程间通信几种主要通信手段简介 1 锁机制 包括互斥锁 条件变量 读写锁 互斥锁提供了以排他方式防止数据结构被并发修改的 方法 使用条件变量可以以原子的方式阻塞线程 直到某个特定条件为真为止 对条件的测试是在互斥锁 的保护下进行的 条件变量始终与互斥锁一起使用 读写锁运行多个线程同时读共享数据 而对写操作是 互斥的 2 信号量机制 包括无名线程信号量和命名线程信号量 3 信号机制 类似于进程间的信号处理 进程与线程的区别 进程概念 进程是表示资源分配的基本单位 又是调度运行的基本单位 例如 用户运行自己的程序 系统就创 建一个进程 并为它分配资源 然后 把该进程放入进程的就绪队列 进程调度程序选中它 为它分配 CPU 以及其他有关子亚 U 年 该进程才真正运行 所以 进程是系统中并发执行的单位 线程的概念 线程是进程中执行运算的最小单位 亦即执行处理机调度的基本单位 如果把进程理解为在逻辑上操 作系统所完成的任务 那么线程表示完成该任务的许多子任务之一 线程可以在处理器上独立调度执行 这样 在多处理器环境下就允许几个线程各自在单独处理器上进行 引入线程的好处 1 易于调度 2 提高并发性 通过线程可方便有效地实现并发性 进程可创建多个线程来执行同一程序的不同部 分 3 开销少 创建线程比创建进程要快 所需开销很少 4 利于充分发挥多处理器的功能 通过创建多线程进程 即一个进程可具有两个或更多个线程 每个线程在一个处理器上运行 从而实现应用程序的并发性 使每个处理器都得到充分运行 进程和线程的关系 1 一个线程只能属于一个进程 而一个进程可以有多个线程 但至少有一个线程 2 资源分配给进程 同一进程的所有线程共享该进程的所有资源 3 处理机分给线程 即真正在处理机上运行的是线程 4 线程在执行过程中 需要协作同步 不同进程的线程间要利用消息通信的办法实现同步 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 解析 单道运行的总时间为 60 80 20 120 40 40 40 80 40 520ms 4 两个等价线程并发的执行下列程序 a 为全局变量 初始为 0 假设 printf 操作都是原子性的 则输出不肯哪个是 A 1 void foo 2 3 if a 执行 执行 阻塞 阻塞 就绪 执行 就绪 1 进程的三种基本状态 进程在运行中不断地改变其运行状态 通常 一个进程必须具有以下三种基本状态 就绪状态 当进程已分配到除 CPU 以外的所有必要的资源 只要获得处理机便可立即执行 这时的进程状态就称 为就绪状态 执行状态 当进程已获得处理机 其程序正在处理机上执行 此时的进程状态称为执行状态 阻塞状态 正在执行的进程 由于等待某个事件发生而无法执行时 便放弃处理机而进入阻塞状态 引起进程阻 塞的事件有很多种 例如 等待 I O 完成 申请缓冲区不能满足 等待信号等 2 进程三种状态间的转换 一个进程在运行期间 不断地从一种状态转换到另一种状态 它可以多次处于就绪状态和执行状态 也可以多次处于阻塞状态 A 就绪 执行 处于就绪状态的进程 当进程调度程序为之分配好了处理机后 该进程便由就绪状态转换为执行状态 B 执行 就绪 处于执行状态的进程在其执行过程中 因分配给它的一个时间片已经用完而不得不让出处理机 于是 进程从执行状态转换为就绪状态 C 执行 阻塞 正在执行的进程因等待某种事件发生而无法继续执行时 便从执行状态变成阻塞状态 D 阻塞 就绪 处于阻塞状态的进程 若其等待的事件已经发生 于是进程便从阻塞状态转变为就绪状态 4 A 和 B 晚上无聊就开始数星星 每次只能数 K 个 20 k4 每个战士知道当前的一些战况 现在需要这 n 个战 士通过通话交流 互相传达自己知道的战况信息 每次通话 可以让通话的双方知道对方的所有情报 设 计算法 使用最少的通话次数 是的战场上的 n 个士兵知道所有的战况信息 不需要写程序代码 得出最 少的通话次数 解析 笔试的时候是这样想的 N 1 个人围成一个环 将知道的消息都告诉第 N 个人 需要 N 1 次 同时第 N 1 个人与第 N 个人交流时 两人互相交流消息 这样子第 N 1 个人与第 N 个人都知道了所有人的信息 接下来第 N 1 人沿着环将消息传递下去 需要 N 2 次 所以需要 N 1 N 2 2N 3 但是实际上这个问题有着更优的解法 扩展的一类问题 题目 假如我们班有 n 个 MM 每一个 MM 都有一个独家的八卦消息 两个 MM 可以通过电话联系 一通电话将使得双方都获知对方目前已经知道的全部消息 要想所有 n 个 MM 都知道所有 n 条八卦消息 最少需要多少通电话 请给出通话方案 来自 解答 1 分析情况 当 n 很小时我们很容易通过枚举的方法找出最佳通话方案 A1 0 A2 1 A3 3 A4 4 A5 6 A6 8 2 基于中间消息传递人的思想建模 可以先把所有消息集中于一个或几个人 然后再由这些消息汇总人把消息传给所有人 设 n 个 MM 中 有 m 个消息汇总人 她们共享所有消息需要打 An 通电话 通话方案如下 第一 剩下的 n m 个 MM 每个人从 m 个消息汇总人中随机选择一个通话 这样一来 m 个消息汇总人 就掌握所有 n 条八卦消息 并且她们每个人所掌握的消息互不重叠 是互补的 第二 m 个消息汇总人通过打电话共享所有八卦消息 第三 作为消息汇总人的 m 个 MM再通过电话将自己新得到八卦新闻告知最开始打电话给自己的 MM 使得她们也掌握所有 n 条消息 模型如下 3 模型分析 按照上面的通话方案 第一步需要 n m 通电话 第二步需要 Am 通电话 第三步需要 n m 通电话 故 有 An 2 n m Am 进一步化简得 An 2 n 2 m Am 即当 MM 的个数为 n 时 共享所有八卦消息共需要 2 n 2 m Am 通电话 若要使得通话次数最 小 就要求 2 m Am 最大 因此 取多少个 MM 作为消息汇总人使得 2 m Am 最大成为了解决这 个问题的关键 它反映了 MM 们之间通话的效率 记 Em 2 m Am 当有一个消息汇总人即 m 1 时 E1 2 1 A1 2 当有两个消息汇总人即 m 2 时 E2 2 2 A2 3 m 3 时 E3 2 3 A3 3 m 4 时 E4 2 4 A4 4 m 5 时 E5 2 5 A5 4 m 6 时 E6 2 6 A6 4 由归纳法可知 当 m 4 时 Em 有最大值 4 An 有最小值 2 n 4 即当有大于或等于 4 个消息汇总 人时可通过上述通话方案使得 n 个 MM 通过最小的电话数共享所有八卦消息 此时共需要 2 n 4 次电话 4 模型证明 5 模型结果 题目中如果告诉 n 大于 4 那么结果就是 2n 4 5 有 N 个人 其中一个明星和 n 1 个群众 群众都认识明星 明星不认识任何群众 群众和群众之间的认 识关系不知道 现在如果你是机器人 R2T2 你每次问一个人是否认识另外一个人的代价为 O 1 试设计 一种算法找出明星 并给出时间复杂度 没有复杂度不得分 解答 这个问题等价于找未知序列数中的最小数 我们将 reg 这个函数等价为以下过程 如果 i 认识 j 记作 i 大于等于 j 同样 j 不一定大于等于 i 满足要求 i 不认识 j 记作 i 另外一种思路 四 综合题 有一个淘宝商户 在某城市有 n 个仓库 每个仓库的储货量不同 现在要通过货物运输 将每次仓库的储 货量变成一致的 n 个仓库之间的运输线路围城一个圈 即 1 2 3 4 n 1 货物只能通过连接 的仓库运输 设计最小的运送成本 运货量 路程 达到淘宝商户的要求 并写出代码 解答 这个题目类似的题目有 题目 有 n 个小朋友坐成一圈 每人有 ai 个糖果 每人只能给左右两人传递糖果 每人每次传递一个糖果代 价为 1 求使所有人获得均等