阿里2015客户端实习生笔试：Base64与图论解析

"这篇文档是关于阿里2015年实习生客户端笔试题目的解析，主要涉及Base64编码和有向图的相关知识。" 在阿里2015年的实习生客户端笔试中，涉及到两个核心知识点： 1. **Base64编码**： Base64是一种用于将二进制数据转换为可打印ASCII字符的编码方式，通常用于在网络上传输非文本数据，如图像或加密信息。Base64编码使用64个字符（包括大小写字母、数字、加号`+`和斜线`/`，以及在URL编码中常替换为`-`和`_`的两个字符），每个字符代表6位二进制数。由于8位字节无法被6整除，所以Base64编码时会在末尾添加额外的填充字符，通常是等号`=`，以确保编码后的字符串长度是6的倍数。 - 对于长度为12的char数组，由于每个char占8位，总共是96位。Base64每6位表示一个字符，所以需要16个字符来表示。 - 而长度为20的char数组，共160位。160除以6等于26余4，因此需要26个字符表示数据部分，加上1个字符作为填充，总计27个字符。但由于Base64编码总是以完整字符组结束，所以实际需要28个字符。 2. **有向图和图的遍历**： 这道题目是关于用有向图表示人与人之间的关系，其中每个人都可能成为另一个人的“国王”或“天使”。在抽签过程中，如果抽到自己，则需要重抽，直到抽到他人为止。这个问题可以抽象为有向图的连接结构，其中每个节点代表一个人，边表示“国王-天使”的关系。 - 题目中提到的错误结论是关于有向图的性质和算法。选项1和3指出可能存在多个联通分支（或强联通分支），这是正确的，因为每个人至少会与一个人形成连接，形成了至少一个联通分支。在偶数人数情况下，可能存在所有节点两两成环的情况，形成多个联通分支。 - 选项2错误地限制了联通分支的最大数量，实际上它可能等于人数减一，例如每个人与另外一个人形成一对一的关系。 - 选项4提到使用深度优先搜索（DFS）求联通数是可行的，因为DFS可以用来识别连通分量。 - 选项5指出可以使用双向链表存储有向图的结构，这也是合理的，因为每个节点可以包含指向其“国王”的指针，以及一个反向指针指向它的“天使”。 - 选项6关于遍历复杂度的描述是正确的，遍历整个图的时间复杂度大致为O(N)。 题目中错误的结论是选项4，即“可以用深度优先算法求得联通数”。实际上，DFS可以找到所有的连通分量，但不能直接求出联通数，需要进一步的处理。此外，题目在表述上存在一些问题，如对“联通分支”定义的不严谨和人数为奇数时的特殊情况没有明确说明。