测试开发的技能之一就是需要掌握一些开发的语言,而针对于考察开发语言,业界内比较容易采用的方式就是考察各种算法。在此做一个简单的总结(最近比较喜欢玩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。
二叉树的节点表示可以使用
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转换成字符串
后续还有的话会继续添加的。