1.字符串交换位置
时间复杂度O(n) 空间复杂度O(1)

2.数组找最大值、最小值

定义了一个数组a = [1,3,4,55,29] 查找数组中最大值
定义一个for循环对数组所有元素遍历一遍时间复杂度为O(n)

4.栈：后进先出 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

5.为支持浏览器前进和后退功能，利用栈记录历史访问信息 后进先出

7.数组 数组在内存中是连续存放的，数组内的数据，可以通过索引值直接取出得到
数组 [1,4,3,5,2] 去掉一个最大值和最小值求平均数 要求不允许开辟O(n)空间复杂度的数据结构

8.字符串 操作都是On

11.二叉树 树的遍历方法：前序遍历、中序遍历、后序遍历

# 递归的核心思想是把规模大的问题转换为规模小的相似的子问题
 

12.分治法、二分查找

13.在一个有序数组里面，查找出第一个大于9的数字，假设一定存在

14.排序 -- 二分查找必须为有序 常见4种排序：冒泡排序、插入排序、归并排序、以及快速排序

　　冒泡排序：空间复杂度为O(1) 时间复杂度O(n*n)

插入排序空间复杂度是O(1) 最好的时间复杂度O（n） 最坏的时间复杂度O（n*n）

归并排序
归并排序采用二分的迭代方式，复杂度是logn
合并两列表

def merge(a, b): # a,b是待合并的两个列表,两个列表分别都是有序的，合并后才会有序
 

快速排序法 稳定性较差
左小右大函数，获取一个中值，左放小右放大函数

15.动态规划是一种运筹学方法，是在多轮决策过程中的最优方法

16.在一个数组 a = [1, 3, 4, 3, 4, 1, 3] 中，找到出现次数最多的那个数字。如果并列存在多个，随机输出一个。

17.这个问题是力扣的经典问题，two sums。给定一个整数数组 arr 和一个目标值 target，请你在该数组中找出加和等于目标值的两个整数，并返回它们在原数组中的下标。

你会发现，这个数列中元素的性质是，某个数等于它前面两个数的和；
也就是 a[n+2] = a[n+1] + a[n]。至于起始两个元素，则分别为 0 和 1。在这个数列中的数字，就被称为斐波那契数。
【题目】写一个函数，输入 x，输出斐波那契数列中第 x 位的元素。
例如，输入 4，输出 2；输入 9，输出 21。要求：需要用递归的方式来实现。

19.给定一个字符串，逐个翻转字符串中的每个单词。

【题目】 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，

返回移除后的数组和新的长度，你不需要考虑数组中超出新长度后面的元素。
要求：空间复杂度为 O(1)，即不要使用额外的数组空间。
例如，给定数组 nums = [1,1,2]，函数应该返回新的长度2，并且原数组 nums 的前两个元素被修改为 1, 2。
又如，给定 nums = [0,0,1,1,1,2,2,3,3,4]，函数应该返回新的长度 5，并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

21.例题 1：判断数组中所有的数字是否只出现一次

22.找出数组中出现次数超过数组长度一半的元素你可以假设一定存在这个出现次数超过数组长度的一半的数字，即不用考虑输入不合法的情况。

2021九年级信息技术试卷08

一、单选题(总分：100分本大题共40小题，共100分)

33.(本题2.5分)关于 Python 程序格式框架的描述，以下选项中错误的是（ ）

A.Python 语言的缩进可以采用 Tab 键实现B.Python单层缩进代码属于之前最邻近的一行非缩进代码，多层缩进代码根据缩进关系决定所属范围C.判断、循环、函数等语法形式能够通过缩进包含一批Python 代码，进而表达对应的语义D.Python 语言不采用严格的“缩进”来表明程序的格式框架

36.(本题2.5分)顺序结构程序设计的一般过程为，请选择正确的排序：（）① 调试运行 ②设计算法  ③问题分析  ④编写代码

A.①②③④B.③②④①C.③②①④D.②③④①

38.(本题2.5分)整型变量x中存放一个两位数，要将这个两位数的个位数字和十位数字交换位置，例如：54变成45，正确的表达式是（  ）。

39.(本题2.5分)以下变量名中，不符合Python语言变量命名规则的是（ ）。