阿里笔试题.docx

1、 假设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f依次通过S和Q，即每一个元素必须先进栈，之后再出栈进入队列。若这6个元素出队的顺序是b、d、c、f、e、a，则栈S的容量至少应该为_。2、 在一个元素个数为N的数组里，找到升序排在N/5位置的元素的最优算法时间复杂度是_。3、 已知一棵有2014个结点的树,其叶结点个数为116,该树对应的二叉树中无左孩子结点或右孩子结点的结点个数是_。4、下述描述中，正确的是_。 char const * pointer表示pointer指向的内存区域的内容不能修改 const char *pointer表示pointer不能指向别的内存地址 char * const pointer 表示pointer指向的内存区域的内容不能修改 const char * const pointer在C+语言中不合法5、你有一个3X3X3的立方体。你现在在正面左上的顶点，需要移动到对角线的背面右下的顶点中。每次移动不限距离，但只能从前至后、从左至右、从上至下运动，即不允许斜向或后退。有_种方法。6、在设计一个离线的大数据处理系统，下面哪个性能指标不是系统追求的？ 健壮性 高吞吐 低延迟 处理的数据规模7、需要频繁的插入删除操作使用什么结构比较合适_。 数组 队列 链表 栈8、在unix系统下执行chmod(/usr/test/sample,0753)之后该文件sample的访问权限为_。 拥有者可读写执行，同组用户可写可执行，其他用户可读可执行 拥有者可读写执行，同组用户可读写，其他用户可读可执行 拥有者可读写执行，同组用户可读可执行，其他用户可写可执行 拥有者可读写执行，同组用户可读可执行，其他用户可读写9、关于sizeof和strlen的区别不正确的是。 数组做sizeof的参数不退化，传递给strlen就退化为指针了。 sizeof的参数可以是数据的类型，也可以是变量，而strlen只能以结尾为0的字符串作参数。 sizeof和strlen都是在编译后运行才能计算出来结果。 sizeof计算的是数据类型占内存的大小，而strlen计算的是字符串实际的长度。10、下列代码的输出结果是int i=-1;unsigned j=1; if (ij) printf(ij)成立n); else printf(ii) printf(ji)成立n); else printf(ji)不成立n); (ii)成立 (ii)不成立 (ii)成立 (ii)不成立11、下面序列中，哪一种序列不可能是一个二叉搜索树的后序遍历结果？ 1,2,3,4,5 1,2,5,4,3 5,4,3,2,1 3,5,1,4,212、对于A、B两种排队方式，说法正确的是_。 方式A效率更高 方式B效率更高 当排队的任务中有长耗时任务且比例较低时，方式B更具优势 都不正确13、某二叉树有如下特性,每一个结点要么是叶子结点，要么有2个子树。如果有一个这样的树有m个叶子结点，则这棵树的总结点数是_。 2m+1 2m-1 2(m-1) 2m14、对于二分查找算法下面描述正确的是。 只能用于数组 只能用于链表 只能在已经排序的数据上进行查找 最坏情况下时间复杂度是O(N*logN)15、某二叉树的先序遍历是12453，中序遍历是42513，那么其后续遍历是_。 45231 42351 12345 5432116、小数值1.5625的二进制表示是_。 101.1001 0.001 101.111 1.100117设集合A=1,2,3,A上的关系R(1,1),(2,2),(2,3),(3,2),(3,3)，则R不具备。 自反性 传递性 对称性 反对称性18、一多核系统上，某进程中n个独立的资源需要被m个线程访问（n，m50），在保证数据读写安全的前提下，为实现最大的并发性其需要的锁的数目为_。 max(n, m) n m min(n, m)19以下访问速度最快的设备是。 寄存器 内存 磁盘 L1 Cache20、平均速度最快的排序算法是_。 Shell排序 快速排序 冒泡排序 插入排序21、一个二进制网络通信协议的报文，包头定长，除了包头以外，可以携带长度和内容都不定的负载，设计报文格式时，可以用_，确保协议处理程序能够正确识别每一个报文。 在包头中第一个定长字段中写明报文全长 在包头中某个定长字段中写明负载长度 在报文头尾加固定长度的边界符 使用定长报文，如负载超长，则分片22、下面属性中，是事物(Transaction)属性的有_。 原子性(Atomic) 并发性(Concurrency) 一致性(Consistent) 隔离性(Isolated) 持久性(Durable)23、堆数据结构可以应用于以下哪些场景：_ 排序 优先级队列 从大量数字中找出最大的10个数字 动态内存分配24、二叉树的广度优先遍历序列为A B C D E F G H I，已知A是C的父结点，D是G的父结点，F是I的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知E的父结点可能是_。 A B C D F25、以下C语言程序片段用于估测CPU的cache参数（容量，延迟等）：#define MAX_SIZE (64*1024*1024L)#define STRIDE (128)#define STEP (4096)#define REPEAT (1000*1000L)double tMAX_SIZE/STEP;int dMAX_SIZE/sizeof(int);t0 = 0;long foot_print;for (foot_print = STEP; foot_print MAX_SIZE; foot_print += STEP)long i;for (i = 0; i foot_print; i += STRIDE)long next = (i + STRIDE) % foot_print;di/sizeof(int) = next/sizeof(int);int m = 0;double t1 = get_time_second();for (i = 0; i REPEAT; +i); / *double t2 = get_time_second();tfoot_print/STEP = t2 t1;printf(“%dt”, x); / avoid compiler optimization/ record t 假设CPU具有L1/L2/L3三层cache，cache line长度小于128B，硬件预取已经关闭。请补全标记*的行，完成其功能；26、如果让你来测试淘宝站内的搜索系统，请问你能想到哪些方法来进行测试？我们假设淘宝网的搜索入口页面如下图所示：27、长度为100的环形双向链表，A指针顺时针方向每次走3步，B指针逆时针方向每次走5步，每次走完判断是否相遇，初始状态B在A逆时针方向相距20，走100次，AB指针能相遇几次？28、C语言