阿里笔试题记录（Android客户端部分）

选择题

结果应该是选择 80,8

思路：
- 指针的值都是一个个地址，而地址是用无符号整型值来表示的，也就是unsigned int。因此一个指针类型变量的大小就是unsigned int类型的大小。
- 64位系统，一个地址占用的二进制位数为64（8字节），32位系统，地址的二进制位数32（4字节）。参考64位操作系统的指针不都是64位吗

32位cpu和64位cpu，这个位数指的是数据字长，而不是地址字长。两者没有必然的数值上的联系。处理器字长是指处理器能同时处理的位数。 而处理器的寻址范围是要看处理器的地址总线的位数，32位地址总线能够访问0~2^32-1，也就是2^32个存储单元（4GB）,因此32位cpu的指针大小就是4个字节（32bit）。64位处理器的数据总线为64位，而地址总线大都是32位(当然也有的64位处理器的数据总线和地址总线都是64位的)。参考文章32位机指针为什么是4个字节 64位与32位的区别

• char*p[10]表示声明一个能够盛放10个char指针元素的数组，命名为p；char(*p)[10]表示声明一个指针，指向一个长度为10的char数组。
• sizeof()函数，以字节的形式返回其操作数的存储大小。当操作数是指针时，该函数依赖于编译器…当操作数是数组类型时候，返回值是数组的总字节数。所以，sizeof(p)是计算的元素类型为char指针，元素数量为10的数组的大小，计算方式为元素类型占用内存的字节数*数组元素个数，sizeof(p1)是计算一个指针的大小。参考文章解析c语言的sizeof
• 在编译器为GNU GCC Compiler下，结果为40,4。
• 由于题干说是在64位系统下，所以地址长度应该是8字节。

我的结果是 1111110

思路：
- 数字组合，看题可得出每位数字的选择应该是0~9,10个数字。
- 从合法的口令的最低位数开始算起，当口令为1位时，有10种（10^1）；口令为2位，有100种（10^2）…口令为6位时，有1000000（10^6）种。加起来为1111110种。

我的答案 以上都不是最优解

思路：
- 路人先选择袋子，每个袋子的被选中的几率是1/2。
- 在选择完袋子之后（假设选择了袋A，里面有红球r个，蓝球b个），拿到红球的概率是 r/(r+b)。
- 那么选择红球的概率是 1/2 * (50-r)/(100-r-b) + 1/2 * r/(r+b)
- 当r=49，b=50时，上式为 1/2 + 49/99 结果都大于选项的结果。

…这个谁会？没思路看不懂

同样没思路啊啊啊，想必不是用穷举…

我的答案是瞎蒙的..
分析：
- 由题干知道，可以构建一个有向图。每个人都抽象为图的一个顶点，方向指向为纸条上的人名。不允许指向自己；图的每个顶点拥有两条边（一条指向自己，一条指向别的顶点）。

强联通 ：在有向图G中，如果任意两个不同的顶点相互可达，则称该有向图是强连通的。有向图G的极大强连通子图称为G的强连通分支。
在图论中，连通图基于连通的概念。在一个无向图 G 中，若从顶点vi到顶点vj有路径相连（当然从vj到vi也一定有路径），则称vi和vj是连通的。如果 G 是有向图，那么连接vi和vj的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。
连通分量：无向图 G的一个极大连通子图称为 G的一个连通分量（或连通分支）。连通图只有一个连通分量，即其自身；非连通的无向图有多个连通分量。

• 这么一判断，纸上画个图，对于选项可以用双向链表存储其结构，感觉应该是错的，应该是可以用循环单向链表存储其结构。
• 感觉遍历的复杂度是O（n）好像是对的。。

我的答案是 31
思路：
- 就是算最少多少位二进制数可以容纳20亿。2^10 约做10^3，那么2^30约为10^9（10亿，当然2^30比10亿大，比20亿小）。于是31是最小值。

我的答案：FTP
思路（刚好最近在复习计算机网络，大概看了下5层模型里面常用的协议）：
- DNS:域名系统，用于域名和ip地址之间的相互映射。在地址栏内输入天猫的域名，通过dns将域名转换为ip地址，属于应用层协议。
- TCP:传输控制协议，应用层的http、https协议都是基于传输层的TCP协议的，属于运输层协议。
- IP:网际协议，通过IP进行网络之间设备的互联，相当于快递的地址，属于网络层协议。
- ARP:地址解析协议，根据ip地址获取物理地址（Mac地址），位于五层模型的数据链路层。
- ICMP:英特网控制报文协议，用于在ip主机、路由器之间传送控制消息，不用于传输数据，但对于用户数据传输有着重要的作用。属于网络层协议。
- FTP:文件传输协议，属于应用层协议，也是一个应用程序。

我的答案是 6
思路：

笨办法，算… 7-3+4-2+3-3+4-4+7-7=6
求个聪明的办法。。

我的答案：第三个
对c++不太熟，更别说相关的库了。

STL = Standard Template Library:标准模板库，是一些“容器”的集合。
std:sort不是稳定排序算法，std:stable_sort来保证这一点。

…于是出现了对数函数，我还能说什么?

思路：

- 于是g(x) = ax^2-8x+a-6，包含所有正数。
- 当a=0，-8x-6 可以取得所有正数。
- 当a<0，二次函数图象开口向下，取不到所有正数。
- 当a>0，二次函数图象开口向上，当a=8时，有一个零点（x=1/2），当a取10时，没有零点，区不到所有正数。
- 因此答案为[0,8]

概率题，这个不大会…

我的答案：a=10,x=2
- 很简单的三元运算符操作

当时笔试的时候我没做出来。。不过第一道题琢磨懂了之后再看这个还是不难的。。只不过不知道特地支出在Linux系统下是什么梗..

• 如果sizeof操作数是函数中的数组形参火函数类型的形参，sizeof给出其指针的大小。参考文章解析c语言的sizeof
• 在头文件stdint.h中有如下声明typedef int int32_t;在int为4字节的系统typedef int int32_t不用变,使用int32_t则为4字节；在int为2字节的系统typedef long int32_t 改变int为long，使用int32_t还是4字节。总的来说，移植到2字系统只改变typedef long int32_t中的int，而不需要全部改变int32_t。
• 所以上面的64位Linux系统应该是烟雾弹，答案应该是40,4。

当时学数据结构的时候，哈希表那块老师没细讲，再加上也没认真听（现在回想起来，之前上的课几乎都后悔没有认真听讲了…），现在的了解都是零零碎碎的…
- 题目不会
- 附上一篇文章哈希表及处理冲突的方法

正好前一段时间复习排序算法的时候，特意重点看了快排。
- 根据分析，一轮排序后，主元的所在位置前的所有元素应该小于主元的值，主元之后的所有元素应该大于主元的值，因此14、17、24都有可能是主元（划分基数）.
- 附上我之前写的关于快排的博客 快速排序的学习中遇到的问题（java）

当时记录下来的选择题就是这些了…附加题是Android相关的主观题，一共三道。花了四个小时重新看了一遍这些题，感觉收获还是挺大的。

我一同学是报前端的…参加十场前端的笔试，把笔试中不懂的题都搞懂了，也应该就差不多了hahaha