2014年3月29日阿里巴巴暑假实习生笔试题

20142014 年年 3 3 月月 2929 日阿里巴巴暑假实习生笔试题日阿里巴巴暑假实习生笔试题 1 设栈 S 初始状态为空 元素 a b c d e f 依次通过栈 S 若出栈的顺序为 c f e d b a 则栈 S 的容量至少应该为 3 4 5 6 2 10 个相同的糖果 分给三个人 每个人至少要得一个 有 种不同分法 33 34 35 36 3 小数值 1 5625 的二进制表示是 101 1001 0 001 101 111 1 1001 4 某二叉树的先序遍历是 12453 中序遍历是 42513 那么其后续遍历是 45231 42351 12345 54321 5 主机甲和主机乙间已建立一个 TCP 连接 主机甲向主机乙发送了两个连续 的 TCP 段 分别包含 300 字节和 500 字节的有效载荷 第一个段的序列号为 200 主机乙正确接收到两个段后 发送给主机甲的确认序列号是 500 700 800 1000 6 在 N 个乱序数字中查找第 k 大的数字 时间复杂度可以减小至 O N logN O N O 1 O N 2 7 平均速度最快的排序算法是 Shell 排序 快速排序 冒泡排序 插入排序 8 以下指令集架构属于复杂指令集架构的是 ARM MIPS SPARC 以上皆不是 9 有两个 N N 的矩阵 A 和 B 想要在 PC 上按矩阵乘法基本算法编程实现计 算 A B 假设 N 较大 本机内存也很大 可以存下 A B 和结果矩阵 那么 为了计算速度 A 和 B 在内存中应该如何存储 按行存指先存储第一行 再第 二行 直到最后一行 按列存指先存储第一列 再第二列 直到最后一列 A 按行存 B 按行存 A 按行存 B 按列存 A 按列存 B 按行存 A 按列存 B 按列存 10 设一棵二叉树中有 3 个叶子节点 有 8 个度为 1 的节点 则该二叉树中总 的节点数为 12 13 14 15 11 IP 数据报头采用 字节序 在此字节序下从低地址到高地址 0 x1234 的表示形式为 big endian 0 x12 0 x34 0 0 little endian 0 x34 0 x12 0 0 big endian 0 0 0 x12 0 x34 little endian 0 0 0 x34 0 x12 12 下列叙述中正确的是 循环队列有队头和队尾两个指针 因此 循环队列是非线性结构 在循环队列中 只需要队头指针就能反映队列中元素的动态变化情况 在循环队列中 只需要队尾指针就能反映队列中元素的动态变化情况 循环队列中元素的个数是由队头指针和队尾指针共同决定 13 将一个从大到小的数组 用以下排序方法排序成从小到大的 最快 插入排序 冒泡排序 快速排序 堆排序 14 在一个元素个数为 N 的数组里 找到升序排在 N 5 位置的元素的最优算法 时间复杂度是 O n O n log n O n log n 2 O n 3 2 15 已有变量定义和函数调用语句 编程 代码 int a 25 print value 则下面函数的正确输出结果是 void print value int x printf xn x 25 26 19 1a 16 在二进制数据中 小数点向右移一位 则数据 除以 10 除以 2 乘以 2 乘以 10 17 设集合 A 1 2 3 A 上的关系 R 1 1 2 2 2 3 3 2 3 3 则 R 不具 备 自反性 传递性 对称性 反对称性 18 下列叙述中正确的是 循环队列有队头和队尾两个指针 因此 循环队列是非线性结构 在循环队列中 只需要队头指针就能反映队列中元素的动态变化情况 在循环队列中 只需要队尾指针就能反映队列中元素的动态变化情况 循环队列中元素的个数是由队头指针和队尾指针共同决定 19 假定 x 500 求下面函数的返回值 int fun int x int countx 0 while x countx x x return countx 2 3 5 6 20 有一台带一个千兆网卡的服务器 A 会把接收到的消息转发给另外两台带 一个千兆网卡的服务器 B 和 C B 和 C 上面的一个服务进程处理一条 10K 字节 的消息需要 2 毫秒 如果在 B 和 C 上面各跑 80 个服务进程 在不考虑 CPU 负载和进程切换 内存占用 传输损耗和交互损耗的情况下 B 和 C 服务器每 秒一共大约可以处理 条 10K 字节的消息 50000 60000 70000 80000 21 以下措施中 有可能改进分布式系统读写 IO 性能的有 网络从千兆网升级为万兆网 优化调度系统 尽量做到任务与数据相近 Locality 数据预取机制 实现异步读写机制 22 无锁化编程有哪些常见方法 针对计数器 可以使用原子加 只有一个生产者和一个消费者 那么就可以做到免锁访问环形缓冲区 Ring Buffer RCU Read Copy Update 新旧副本切换机制 对于旧副本可以采用延迟释放 的做法 CAS Compare and Swap 如无锁栈 无锁队列等待 23 程序 struct T char a int d int b int c 16 double e T p 在 64 位系统上以下描述正确的是 sizeof p 8 sizeof p 32 sizeof p a 1 sizeof p e 4 24 下面所述步骤中 是创建进程所必须的步骤是 由调度程序为进程分配 CPU 建立一个进程控制块 为进程分配内存 为进程分配文件描述符 25 有一种用左右值表示树形结构的存储格式 其中左右值有一些相当有用的场景 但是每个节点 的左右值需要遍历树形结构计算出来 一个示例 N 1 12 N 2 7 N 3 4 N 5 6 N 8 11 N 9 10 请完成遍历算法给节点赋左右值 typedef struct node t int left int right int n children 1 children NODE int visit NODE node int value node left value int i 0 for i 0 in children i 2 3 return value int initLR NODE root return visit root 1 26 我们需要在淘宝的商品中提取一批优质商品 有特色 质量好 服务好等 比如 需要提取 100 万件 准确率要求是 95 我们有 n 个不同的方法可以提取这些商品 但 每个方法在保持准确率满足要求的情况下都不能做到提取完整的 100 万件商品 因此可 以把这 n 个方法得到的满足要求的商品集按如下方法合并起来 如果一个商品被 k 个方 法选为优质商品 则将它的分数设为 k 按照 k 从大到小排序选取前 100 万件 但实际 中发现这样选出的 100 万件商品不符合精度要求 请解释可能的原因 还可以向哪个方 向努力 27 有个学校的 15 个女生一直 3 个一群上学 请问该如何安排才能使这些女生每周 7 天每天都和两个不同的同伴结伴同行呢 例如 用 A 到 O 来标识这些女孩 7 天 A 正好 和 B 到 O 这 14 个女孩各同行一次 而 B 到 O 每个人和都和其他 14 个女孩各同行一次 28 长度为 100 的环形双向链表 A 指针顺时针方向每次走 3 步 B 指针逆时针方向每 次走 5 步 每次走完判断是否相遇 初始状态 B 在 A 逆时针方