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

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