测试开发基础Python算法与数据结构面试题系列一（附答案）.docxVIP

关注@霍格沃兹测试学院公众号，回复「?试」，领取BAT??测试?试真题专辑。

??复制“下?链接”，提升测试核?竞争?！

更多技术?章分享和免费资料领取

1.时间复杂度问题

已知AList=[1,2,3]，BSet={1,2,3}(1)从AList和BSet中查找4，最坏时间复杂度哪个?？(2)从AList和BSet中插?

4，最坏时间复杂度哪个?？

答:

1.对于查找，列表和集合的最坏时间复杂度都是O(n)，所以?样的。

2.列表操作插?的最坏时间复杂度为o(n),集合为o(1)，所以Alist?。set是哈希表所以操作的复杂度基本上都是o(1)。

2.?Python实现?个?分查找的函数

答:

n=len(arr)

left=0

right=n-1

whileleft=right:

mid=(left+right)//2

ifarr[mid]target:

left=mid+1

elifarr[mid]target:

right=mid-1

else:

print(findex:{mid},value:{arr[mid]})

returnTrue

returnFalse

if__name__==__main__:

l=[1,3,4,5,6,7,8]

binary_search(l,8)

3.Python单例模式的实现?法

3.Python单例模式的实现?法 公众号【大学百科资料】整理，有超百科复习资料

答:

实现单例模式的?法有多种，之前再说元类的时候?call?法实现了?个单例模式，另外Python的模块就是?个天然

的单例模式，这?我们使?new关键字来实现?个单例模式。

通过new函数实现简单的单例模式。

classBook:

def__new__(cls,title):

ifnothasattr(cls,_ins):

cls._ins=super().__new__(cls)

print(in__new__)

returncls._ins

def__init__(self,title):

print(in__init__)

super().__init__()

self.title=title

if__name__==__main__:

b=Book(TheSpiderBook)

b2=Book(TheFlaskBook)

print(id(b))

print(id(b2))

print(b.title)

print(b2.title)

4.使?Python实现?个斐波那契数列

答:

斐波那契数列:数列从第3项开始，每?项都等于前两项之和。

deffibonacci(num):

a,b=0,1

l=[a,b]

a,b=b,a+b

l.append(b)

returnl

if__name__==__main__:

print(fibonacci(10))

5.找出列表中的重复数字

答:

思路：从头扫到尾，只要当前元素值与下标不同，就做?次判断，numbers[i]与numbers[numbers[i]]相等就认为找到

了重复元素，返回true；否则就交换两者，继续循环。直到最后还没找到认为没找到重复元素。

#-*-coding:utf-8-*-

classSolution:

defduplicate(self,numbers):

ifnumbersisNoneorlen(numbers)=1:

returnFalse

use_set=set()

duplication={}

forindex,valueinenumerate(numbers):

ifvaluenotinuse_set:

use_set.add(value)

else:

duplication[index]=value

returnduplication

if__name__==__main__:

s=Solution()

d=s.duplicate([1,2,-3,4,4,95,95,5,2,2,-3,7,7,5])

print(d)

答:

deffind_single(l:list):

result=0

forvinl:

result^=v

ifresult==0:

print(没有落单元素)

else:

print(落单元素,result)

if__