准算法工程师从30+场秋招中总结出的超强面经—C、Python与算法篇篇（含答案）.pdfVIP

文档来源网络 侵权联系删除 算法 1.数组和链表的区别 数组 是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标 迅速访问数组中任何元素。 链表 是一种上一个元素的引用指向下一个元素的存储结构，链表通过指针来连 接元素与元素； （1）数组是连续存储的，链表是散列存储的。数组随机访问性强（通过下标 进行快速定位），所以数组的查询比链表要快，链表不能随机查找，必须从第 一个开始遍历，查找效率低。（ 2）数组插入和删除效率低（插入和删除需要 移动数据），链表插入删除速度快（因为有 next 指针指向其下一个节点，通 过改变指针的指向可以方便的增加删除元素） 2.堆 ,栈 ,堆栈 ,队列 堆 (heap) ：堆是一种经过排序的树形数据结构，每个结点都有一个值。堆通常 是一个可以被看做一棵树的数组对象。堆总是满足下列性质：堆中某个节点的 值总是不大于或不小于其父节点的值 ,堆总是一棵完全二叉树。 栈 (stack):它是一种具有后进先出性质的数据结构，也就是说后存放的先取， 先存放的后取。 堆栈本身就是栈 . 队列是先进先出，有出口和入口。 3.堆和栈的区别： 1 文档来源网络 侵权联系删除 ①堆栈空间分配区别： 1）、栈（操作系统）：由操作系统自动分配释放，存 放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈； 2）、堆（操作系统）：一般由程序员分配释放，若程序员不释放，程序结束 时可能由 OS 回收，分配方式倒是类似于链表。 ②堆栈缓存方式区别： 1）、栈使用的是一级缓存，他们通常都是被调用时处 于存储空间中，调用完毕立即释放； 2）、堆是存放在二级缓存中，生命周期 由虚拟机的垃圾回收算法来决定（并不是一旦成为孤儿对象就能被回收）。所 以调用这些对象的速度要相对来得低一些。 堆：内存中，存储的是引用数据类型，引用数据类型无法确定大小，堆实际上 是一个在内存中使用到内存中零散空间的链表结构的存储空间，堆的大小由引 用类型的大小直接决定，引用类型的大小的变化直接影响到堆的变化 栈：是内存中存储值类型的，大小为 2M ，超出则会报错，内存溢出 ③堆栈数据结构区别：堆（数据结构）：堆可以被看成是一棵树，如：堆排 序；栈（数据结构）：一种先进后出的数据结构。特点：先进后出 4.堆和栈的访问哪个更快 栈是编译时分配空间，而堆是动态分配（运行时分配空间），所以栈的速度 快。 5.快排和堆排 快速排序：最常用的排序算法，速度通常也是最快的。时间复杂度： O （nlog n） 最坏： O （n^2）空间复杂度：O （nlgn）不稳定（比如 53343891011 这个 序列，在中枢元素 5 和 3 交换就会把元素 3 的稳定性打乱） 2 文档来源网络 侵权联系删除 实现原理：快排主要是通过选择一个关键值作为基准值。比基准值小的都在左 边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。依此递 归，达到总体待排序序列都有序。 堆排序：堆排序是指利用堆这种数据结构进行设计的一种排序算法。堆排序利 用了大根堆 (或小根堆 )堆顶记录的关键字最大 (或最小 )这一特征，使得在当前 无序区中选取最大 (或最小 )关键字的记录变得简单。 时间复杂度： O （n*logn）特别适用于数据量很大的场合（百万级数据）。因 为快排和归并排序都是基于递归的，数据量很大的情况下容易发生堆栈溢出。 排序速度略低于快排。也是一种不稳定的排序算法。 6.介绍快排，描述一下最坏的情况 时间复杂度：最好情况 O(nlogn)——Partition 函数每次恰好能均分序列，其 递归树的深度就为 .log2n.+1 （.x.表示不大于 x 的最