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

1.时间复杂度问题

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

答:

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

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

2. 用 Python 实现一个二分查找的函数

答:

3. Python 单例模式的实现方法
答:

实现单例模式的方法有多种，之前再说元类的时候用 call 方法实现了一个单例模式，另外 Python 的模块就是一个天然的单例模式，这里我们使用 new 关键字来实现一个单例模式。

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

4. 使用 Python 实现一个斐波那契数列
答:

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

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

思路：从头扫到尾，只要当前元素值与下标不同，就做一次判断，numbers[i] 与 numbers[numbers[i]] 相等就认为找到了重复元素，返回 true；否则就交换两者，继续循环。直到最后还没找到认为没找到重复元素。

6. 找出列表中的单个数字
答:

7. 写一个冒泡排序
答:

8. 写一个快速排序
答:

9. 写一个拓扑排序
答:

对应于该图的拓扑排序。每一个有向无环图都至少存在一种拓扑排序。

10. Python 实现一个二进制计算
答:

二进制加法

更多 Python 编程常见面试题，我们后续继续分享，敬请关注。