【测试开发八股文】算法

1、栈和队列

1）栈：先进后出；队列：先进先出
2）如何用栈实现队列？
分析：两个栈，栈1负责入队，栈2负责出队
改进点：出队时，栈2出队后，可不把数据重新压回栈1
3）如何用队列实现栈？
进栈：把元素push进非空的队列，如果两者都是空的，则随意
出栈：把非空队列里面的前n-1个元素push到空队列里面，再把最后一个元素拿出来即可
循环以上步骤，即可得到实现目的
加分项：
空队列：对头front和队尾rear指针指向同一个位置
满队列：队列长度为数组长度减1，(rear + 1) % queueSize == front
队列长度：（rear - front + queueSize）% queueSize
对头 < 队尾：rear - front
对头 > 队尾：空闲长度 front - rear，因此队列长度 rear - front + queueSize
入队：先判是否满队列，后入队，队尾指针：rear = (rear + 1) % queueSize
出队：先判是否为空队列，后出队，对头指针：front = (front + 1) % queueSize
1）循环队列：队列使用顺序存储结构进行储存，即使用数组储存队列元素

2、链表

一系列节点组成的链，每一个节点保存了数据以及指向下一个节点的指针

1）如何反转一个单链表？
While cur->next != null:
Next = Cur->next
Cur->next = pre
Pre = cur
Cur = Next
递归：递归思想，从头结点递归遍历到最后一个结点，递归返回最后一个结点并修改指针，使指针指向前一个结点
移动指针（加分项）：定义当前结点指针cur，前一个结点指针pre，循环迭代，计算下一个结点指针next，每次将当前结点指针反转指向前一个结点
2）如何判断一个链表中是否有环？
设置两个指针互相追逐。一个指针每次前进一步，第二个指针每次前进两步，如果有相遇，则说明有环，其中空间和时间复杂度分别O(n)和O(1)
3）返回链表倒数中第N个元素？
遍历：遍历一遍单链表，将其中的元素压栈，然后再将元素一一出栈。那么， 第n个出栈
加分项：维护两个指针， 它们之间的距离为n。然后，将这两个指针同步地在这个单链表上移动，保持它们的距离 为n不变。那么，当第二个指针指到空时，第一个指针即为所求
4）约瑟夫环问题（加分项）：

3、树

1）概念：
假设按从上至下、从左至右对完全二叉树的节点进行编号（编号从1开始），则当一个节点编号为 i 时，则其左孩子节点的编号为 2i，右孩子编号为 2i + 1
满二叉树：所有叶子节点均在最后一层，且其它分支节点的度数均为2
完全二叉树：扣除最大层次一层后为满二叉树，且最后一层的所有节点均向左靠齐
平衡二叉查找树（AVL）：任何节点的两个子树的高度最大差别为1
2）二叉树性质：
非空二叉树第i层上至多有 2^(i-1)个节点（i>=1）
深度为h的二叉树至多有 2^h - 1 个节点(h>1)
任一二叉树，若终端节点数为 n0，度为2的节点数是n2，则 n0 = n2 + 1 (n0 + n1 + n2 = 2n2 + n1)
具有n个节点的完全二叉树的深度为 k = [log(2)n] + 1 （2^(k-1) <= n < 2^k）
3）树的遍历方式
先序遍历：
递归：先根节点，再左子树，最后右子树
非递归栈（加分项）

设R为当前访问的结点

1）若 R != NULL，访问输出R并入栈，调用 R = R->lchild

2）若 R == NULL，重新设 R = 栈顶元素，栈顶元素出栈，R = R->rchild，返回1）

反复执行1）2），直到当前结点R==NULL && 栈空

莫里斯遍历
中序遍历：
递归：先左子树，再根节点，最后右子树
非递归栈（加分项）
莫里斯遍历
后序遍历：
递归：先左子树，再右子树，最后根节点
非递归栈（加分项）：
层序遍历：每一层从左到右访问每一个节点
4）二叉树重构：
前序序列和中序序列
中序序列和后续序列
5）镜像二叉树：不断交换左右子数，直到结点的左右子树均未 null 时返回
6）AVL数：在AVL树中进行插入或删除节点后，可能导致AVL树失去平衡
LL：根节点k2右旋，k1变成根节点，k2变成k1的右子树，“k1的右子树"变成"k2的左子树”

RR：根节点k1右旋，k2变成根节点，k1变成k2的左子树，“k2的左子树"变成"k2的右子树”

RL：先左旋后右旋，即第一次旋转是围绕"k3"进行的"LL旋转"，第二次是围绕"k1"进行的"RR旋转"