有赞2019校招前端笔试题目解析

本资源是一份针对有赞2019年校招前端笔试的文档，包含了一些编程和理论问题，旨在测试应聘者的计算机基础知识和算法理解能力。 1. **问题一：有序数组查找元素出现次数** 题目询问在一个长度为n的有序整数数组中，判断一个元素是否出现超过n/2次所需的最少比较次数。由于数组已排序，我们可以利用二分查找的思想，每次比较都可以排除一半的元素，直到找到答案或者确定不存在。因此，最坏情况下需要进行logn次比较，答案是Θ(logn)。 2. **问题二：栈操作的出栈序列** 考察栈的特性。根据栈的后进先出（LIFO）原则，选项中只有"decba"是不可能的出栈序列，因为这不符合先进后出的规则。 3. **问题三：递归函数计算** 提供了一个递归函数，用于计算一个正整数n的阶乘。函数`f(n)`的基本情况是当n小于等于1时返回1，然后递归地计算n/2和n/2+1的阶乘并相加。最终结果是`f(11)`，计算过程中会形成递归调用栈，当n为11时，递归深度较大可能导致栈溢出，因此选项是“运行出错，栈溢出”。 4. **问题四：文本编辑器的undo/redo功能** undo/redo功能通常使用栈来实现，因为它们遵循撤销和恢复的逻辑，即最近的操作会被添加到栈顶，撤销时弹出栈顶，恢复则推入栈顶，这符合栈的后进先出特性。 5. **问题五：加密算法** 公钥密码学中，Alice使用Bob的公钥对信息进行加密，而Bob使用Alice的私钥解密。所以正确选项是"Alice使用Bob的公钥对信息做了加密"。 6. **问题六：RESTful接口和HTTPS** RESTful接口通过HTTP方法描述操作，如GET、POST、PUT、DELETE。HTTPS使用SSL/TLS协议提供安全连接，HTTP是无状态协议，HTTPS默认使用443端口，而不是80。 7. **问题七：二叉查找树填充方式** 要求计算将n个不同整数填充到n个节点的二叉查找树的不同方式数量。对于完全二叉树，每层都尽可能满，最后一层尽可能左填充，这种情况下，有n!种填充方式使得它成为二叉查找树。 8. **问题八：进程和线程** 错误的说法包括： - 父进程创建的线程可以与子进程创建的线程共享内存，这与操作系统支持线程间通信有关。 - 线程的执行顺序并非由创建顺序决定，而是受系统调度影响。 - 父进程和子进程各自独立，杀死子进程不会影响父进程，反之亦然。 9. **问题九：链表排序算法** 对于单向链表，插入排序在链表中具有很好的性能，因为插入操作可以在O(1)时间内完成，所以时间复杂度最低的是插入排序。 10. **问题十：递归函数的时间复杂度** 函数`fn(n)`的递归形式表明每次递归调用都会增加两个n-1的递归调用，这类似于斐波那契数列的递归定义，其时间复杂度是指数级的，即O(2^n)。但题目中给出了假设n>0，所以实际计算是O(n)，因为每次递归调用减少1，直到n=1。所以答案是`O(n)`。 这份文档涉及到了前端开发的基础知识、算法分析、数据结构应用、网络通信原理、加密算法、进程和线程管理、链表排序以及递归函数分析等多个方面。对于准备参加有赞2019年校招前端笔试的应聘者来说，这些题目都是重要的复习材料。