测试开发面试必知算法

测试开发的技能之一就是需要掌握一些开发的语言，而针对于考察开发语言，业界内比较容易采用的方式就是考察各种算法。在此做一个简单的总结（最近比较喜欢玩Python，所以都是以Python为例子，其它的语言类推。）

• 冒泡排序
• 递归
• 二叉树遍历算法
• 字符串的倒序输出

---

冒泡排序

冒泡排序算法的运作如下：（从后往前）
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

实例：对列表 [2, 8, 4, 7, 5, 9, 0]进行冒泡排序

def bubble(bubbleList):
    listLength = len(bubbleList)
    while listLength > 0:
        for i in range(listLength - 1):
            if bubbleList[i] > bubbleList[i + 1]:
                bubbleList[i] = bubbleList[i] + bubbleList[i + 1]
                bubbleList[i + 1] = bubbleList[i] - bubbleList[i + 1]
                bubbleList[i] = bubbleList[i] - bubbleList[i + 1]
        listLength -= 1
    print(bubbleList)


if __name__ == '__main__':
    bubbleList = [2, 8, 4, 7, 5, 9, 0]
    bubble(bubbleList)

---

递归

递归过程一般通过函数或子过程来实现。递归方法：在函数或子过程的内部，直接或者间接地调用自己的算法。

递归算法流程 递归算法流程

实例：要计算1-10的10位数字的乘积，直观的算法是123456789，利用递归则思路是循环执行n*n-1,直到n=1时

def recursion(n):
    if n == 1:
        return 1        
    else:
        return n * recursion(n-1)

print(recursion(10))

---

二叉树遍历算法
从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：
⑴访问结点本身（N），
⑵遍历该结点的左子树（L），
⑶遍历该结点的右子树（R）。
以上三种操作有六种执行次序：
NLR、LNR、LRN、NRL、RNL、RLN。

二叉树.png

二叉树的节点表示可以使用

class Node:  
    def __init__(self,value=None,left=None,right=None):  
        self.value=value  
        self.left=left  
        self.right=right  

前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点

def preTraverse(root):  
    if root==None:  
        return  
    print(root.value)  
    preTraverse(root.left)  
    preTraverse(root.right)  
  
def midTraverse(root):  
    if root==None:  
        return  
    midTraverse(root.left)  
    print(root.value)  
    midTraverse(root.right)  
  
def afterTraverse(root):  
    if root==None:  
        return  
    afterTraverse(root.left)  
    afterTraverse(root.right)  
    print(root.value) 

实例：求二叉树深度和宽度
求深度用递归；求宽度用队列，然后把每层的宽度求出来，找出最大的就是二叉树的宽度

import queue  
  
class Node:  
    def __init__(self,value=None,left=None,right=None):  
        self.value=value  
        self.left=left  
        self.right=right  
  
def treeDepth(tree):  
    if tree==None:  
        return 0  
    leftDepth=treeDepth(tree.left)  
    rightDepth=treeDepth(tree.right)  
    if leftDepth>rightDepth:  
        return leftDepth+1  
    if rightDepth>=leftDepth:  
        return rightDepth+1  
  
def treeWidth(tree):  
    curwidth=1  
    maxwidth=0  
    q=queue.Queue()  
    q.put(tree)  
    while not q.empty():  
        n=curwidth  
        for i in range(n):  
            tmp=q.get()  
            curwidth-=1  
            if tmp.left:  
                q.put(tmp.left)  
                curwidth+=1  
            if tmp.right:  
                q.put(tmp.right)  
                curwidth+=1  
        if curwidth>maxwidth:  
            maxwidth=curwidth  
    return maxwidth  
  
if __name__=='__main__':  
    root=Node('D',Node('B',Node('A'),Node('C')),Node('E',right=Node('G',Node('F'))))  
    depth=treeDepth(root)  
    width=treeWidth(root)  
    print('depth:',depth)  
    print('width:',width)  

---

字符串倒序输出

思路一：索引的方法

strA = input("请输入需要翻转的字符串：")
print (strA[::-1])

思路二：借组列表进行翻转

strA = input("请输入需要翻转的字符串：")
order = []
for i in strA:
  order.append(i)
order.reverse()   #将列表反转

print (''.join(order))   #将list转换成字符串

后续还有的话会继续添加的。