计算机复试之数据结构

1.算法的定义

算法是对问题求解步骤的描述。

2.一个好的算法应该满足什么?

一个好的算法应该满足：正确性、可读性、健壮性、效率和低存储量需求

• 正确性：算法能够正确的解决问题
• 可读性：算法应该具有良好的可读性，从而帮助人们理解
• 健壮性：输入非法数据时，算法能够适当地做出反应，而不会产生莫名其
  妙的输出结果
• 效率和低存储量需求：效率是指算法执行的时间，存储量需求是指算法执
  行过程中所需要的最大存储空间

3.算法的5个特点

有穷性、确定性、可行性、输入、输出

• 有穷性：一个算法必须在执行有穷步之后结束，每一步在有穷时间内完成
• 确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得到相
  同的输出
• 可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来
  实现
• 输入：一个算法有零个或多个输入
• 输出：一个算法有一个或多个输出

4.算法效率的度量

通过时间复杂度和空间复杂度来描述算法的效率

5.数据结构的定义

数据结构是相互之间存在一种或多种特定关系的数据元素的集合

6.数据结构三要素

逻辑结构、存储结构、数据的运算

（1）数据的逻辑结构

是指数据元素之间的逻辑关系。数据的逻辑结构包括线性结构和非线性结构。

• 线性结构：是指数据元素之间的关系是一对一的。线性结构包括线性表、栈、队列、串、数组
• 非线性结构：是指数据元素之间的关系是一对多或多对多的。非线性结构包括集合、树、图。其中
  集合：是指数据元素之间的关系是属于同一个集合
  树：是指数据元素之间的关系是一对多的
  图：是指数据元素之间的关系是多对多的

（2）数据的存储结构：是指数据结构在计算机中的表示。存储结构包括：

1. 顺序存储：是指逻辑上相邻的元素存储的物理地址也相邻，顺序存储要求存储单元地址必须连续。顺序存储的优点是可以实现随机存取，缺点是可能产生外部碎片
2. 链式存储：是指逻辑上相邻的元素存储的物理地址不一定相邻，链式存储结点之间的存储单元地址可以不连续。链式存储的优点是不会出现碎片，缺点是指针占用额外的存储空间，并且不能随机存取，只能顺序存取
3. 索引存储：是存储信息的同时，还建立附加的索引表。优点是检索速度快，缺点是索引表额外占用空间，插入和删除慢
4. 散列存储：是根据元素的关键字直接计算出元素的存储地址。优点是检索速度快，插入和删除快，缺点是可能出现元素的存储地址冲突，解决冲突需要额外的时间和空间开销

（3）数据的运算

7.常见的数据结构：

数组、链表、栈、队列、树、图

8.时间复杂度

是用算法中基本运算的频度f(n)来分析算法的时间复杂度，算法时间复杂度记为T(n)=O( f(n) )

• 一个语句的频度：是指该语句在算法中被重复执行的次数
• 算法中的基本运算是最深层循环的语句
• f(n)：算法中基本运算的频度
• T(n)：算法中所有语句的频度之和
• 算法中基本运算的频度f(n)和算法中所有语句的频度之和T(n)是相同数量
  级

9. O

是算法中所有语句的频度之和T(n)的数量级

10.算法的空间复杂度S(n)

是算法所需要的存储空间

注：

• 算法的空间复杂度S(n)表示算法的问题规模是n
• 某算法的时间复杂度是O(n^2)，说明算法的执行时间和n^2成正比，问题规模是n

11.算法原地工作

是指算法所需要的辅助空间是常量O(1)

12.递归

就是函数里面自己调用自己。递归是把原问题分解成和原问题相似但是规模较小的若干个子问题，这些子问题可以用相同的解题思路来解决。递归的次数必须是有限的，递归需要定义一个临界条件作为递归的出口，当符合这个递归出口的时候递归结束。递归就是一种栈的应用，递归调用是入栈，输出结果是出栈。

13.递归和循环的比较

• 递归的优点：是代码简洁清晰，并且容易验证正确性
  递归的缺点：是递归调用次数过多容易造成栈溢出
• 循环的优点：是速度快，结构简单
  循环的缺点：是不能解决所有的问题，有的问题适合使用递归而不是循环

14.排序算法的稳定性

是指待排序的元素里面有两个相同的元素，经过排序之后，两个元素的前后次序没有发生改变

15.内部排序

是指在排序期间元素全部存放在内存中的排序

（1）冒泡排序（稳定）：时间复杂度为O(n^2),空间复杂度为O(1)

• 冒泡排序的算法思想：冒泡排序就是两两比较，如果是逆序就交换位置，直到所有记录都排好序。
  注：每一趟冒泡排序都会有一个元素到达正确的位置，所以n个元素冒泡排序要n-1趟

（2）直接插入排序（稳定）：时间复杂度为：O(n^2)，空间复杂度为O(1)

• 直接插入排序的算法思想：是把第一个元素作为已经排好序的子序列，每次把一个待排序的元素按值的大小插入到已排好序的子序列里面，直到所有的待排序元素都被插入到有序序列里面为止
• 直接插入排序的适用范围：顺序存储和链式存储的线性表

（3）归并排序（稳定）：时间复杂度为O(nlog2n),空间复杂度为O(n)

• 归并排序的算法思想：是把两个有序表组合成一个新的有序表。假设有n个元素，把 n 个元素看成 n 个长度为1的有序子表，然后子表两两归并，得到长度为 2 的有序子表，然后再把子表两两归并，一直重复这个操作，直到得到1个长度为n的有序表

（4）堆排序（不稳定）：时间复杂度为O(nlog2n),空间复杂度为O(1)

*堆排序的算法思想：是首先把待排序的元素建立成初始堆，然后把初始堆调整成大根堆，然后把堆顶元素和堆底元素交换，交换之后堆底元素就是待排序元素里面的最大值，输出堆底元素，然后把剩下的元素重新调整成大根堆，然后再把堆顶元素和堆底元素交换，输出堆底元素，再把剩下的元素重新调整成大根堆，一直重复这个操作，直到堆里面只剩下一个元素

注:

• 大根堆：结点值 ≥ 左、右孩子结点的值 （从小到大排序）
• 小根堆：结点值 ≤ 左、右孩子结点的值 （从大到小排序）
• 调整成大根堆：每次从下往上，从右往左，看结点的值是不是大于等于左右孩子结点的值，如果不满足大根堆的定义，就把这个结点和左右孩子结点的最大值交换
• 调整成小根堆：每次从下往上，从右往左，看结点的值是不是小于等于左右孩子结点的值，如果不满足小根堆的定义，就把这个结点和左右孩子结点的最小值交换

（5）快速排序（不稳定）：时间复杂度为O(nlog2n),空间复杂度为O（log2n）

• 快速排序的算法思想：快速排序的基本思想是基于分冶法，选择待排序序列里面的第一个元素作为枢轴，所有比枢轴小的元素放左边，所有比枢轴大的放右边，形成左右两个子序列，对子序列进行一样的操作，直到所有的子序列里面都只有一个元素的时候停止

（6）简单选择排序（不稳定）：时间复杂度为O(n^2),空间复杂度为O(1)

• 简单选择排序的算法思想：是每一趟把待排序的元素里面值最小的元素和待排序的元素里面第一个元素交换位置，需要经过n-1趟排序

（7）折半插入排序（稳定）：时间复杂度为O(n^2),空间复杂度为O(1)

• 折半插入排序的算法思想：是把第一个元素作为已经排好序的子序列，每次把一个待排序的元素按值的大小插入到已排好序的子序列里面，直到所有的待排序元素都被插入到有序序列里面为止。折半插入排序和直接插入排序不同的地方是，折半插入排序是用折半查找的方法在有序子序列里面查找待排序的元素应该被插入的位置
• 折半插入排序的适用范围：顺序存储的线性表

（8）希尔排序（不稳定）：空间复杂度为O(1)

• 希尔排序的算法思想：是把待排序序列按相隔某个增量分割成若干个子序列，对各个子序列分别进行直接插入排序，逐渐缩小增量，重复上述步骤，直到序列基本有序，再对全体记录进行一次直接插入排序
• 希尔排序的适用范围：顺序存储的线性表
• 希尔排序的增量的选择：第一趟的增量是待排序元素个数的一半 n/2 ，第二趟的增量是第一趟增量的一半向下取整，一直到最后一趟增量是1

（9）基数排序（稳定）：时间复杂度为O(d(n+r)),空间复杂度为O(r)（ r是队列数量 ）

• 基数排序的算法思想：基数排序不需要比较和移动。基数排序是首先设置编号为0~9的十个桶，把待排序的元素先按照个位进行分配，然后收集，再按照十位进行分配，然后收集，然后按照百位进行分配，然后收集，依次类推，直到最后按照最高位进行分配，然后收集，整个排序结束

注:

1. 快速排序是内部排序算法里面平均性能最好的排序算法
2. 不稳定排序：堆排序、希尔排序、快速排序、简单选择排序 （口诀：堆希快简）
3. 稳定排序：冒泡排序、直接插入排序、基数排序、归并排序、折半插入排序 （口诀：冒直基归折）

16.顺序查找：

• 顺序查找的思想：是把要查找的值依次和线性表中的元素进行比较。
• 顺序查找的优点是对数据的存储方式没有要求，顺序存储和链式存储都可
  以。顺序查找的缺点是效率低

17.二分查找（折半查找）：时间复杂度是O(log2n)

• 二分查找的思想：首先把要查找的值和中间位置mid处的元素进行比较，如果相等，说明查找成功，返回该元素的位置，如果要查找的值小于中间位置mid处的元素，就往mid的左边找，high=mid-1，重新计算mid的值，如果要查找的值大于中间位置mid处的元素，就往mid的右边找，low=mid+1，重新计算mid的值，然后再把要查找的值和中间位置mid处的元素进行比较，重复上面的操作，直到查找成功或者确定表里面没有要查找的元素，查找失败
• 二分查找的优点是比顺序查找的效率高，二分查找的缺点是只适用于有序的顺序表

18.分块查找

是把查找表分成若干个子块，块与块之间是有序的，再建立一个索引表，索引表里面的每个元素含有各块的最大关键字和各块第一个元素的地址。第一步是确定待查找元素在索引表里面所在的块，第二步是在块内顺序查找

19.矩阵的压缩存储

是针对像对称矩阵、三角矩阵、稀疏矩阵这样的特殊矩阵，矩阵里面的相同元素只存储一个，从而达到节省存储空间的目的

20.面向对象编程和面向过程编程的比较

1. 面向过程就是分析出解决问题的步骤，然后用函数把这些步骤一步一步实现，使用的时候依次调用函数就可以了。
2. 面向对象是把构成问题的事物抽象成各个对象，建立对象的目的不是为了完成一个步骤，而是为了描叙某个事物在解决问题的步骤里面的行为。
   就拿小明上学这件事情举例：
   面向过程：孩子起床→孩子洗漱→孩子出门→孩子去学校，
   面向对象：孩子{起床、洗漱、出门、去学校}
3. 面向过程的性能比面向对象高，但是面向对象容易维护、容易复用、容易扩展。面向对象有封装、继承、多态的特征。

注:

1.对象：是描述客观事物的实体

2.类：具有相同属性和行为的对象的集合，类里面定义属性和行为。

• 封装：将类的某些信息隐藏在类的内部，只能通过该类提供的公共方法来
  对隐藏的信息进行操作和访问。一般是把属性限制为private私有，封装在一个类里面， 对每个私有属性提供public公共的setter和getter方法
• 继承：子类通过extends关键字可以继承父类的所有非私有属性和方法
• 多态：同一个行为具有多个不同的表现形式
• 重载：在同一个类里面方法的名称相同，但是参数类型或者参数个数不同
• 重写：子类继承父类的时候重写了父类的方法，在子类里面定义了和父类
  方法名称、参数类型、返回值类型一样的方法

21.线性表

是由n个相同数据类型的数据元素构成的有限序列。线性表分为顺序表和链表。线性表除了第一个元素，每个元素都有一个直接前驱，除了最后一个元素，每个元素都有一个直接后继

22.顺序表和链表的比较

顺序表：线性表的顺序存储

链表：线性表的链式存储

1. 顺序表可以随机存取，链表只能顺序存取，不能随机存取
2. 顺序表插入和删除需要移动大量的元素，链表插入和删除操作不需要移动元
   素，只需要修改指针
3. 顺序表的存储单元地址必须连续，链表的存储单元地址可以不连续
4. 顺序表的存储空间是一次性分配的，链表的存储空间是多次分配的，需要的
   时候申请就可以了

23.头指针和头结点的区别

头指针是指向链表的第一个结点，头结点是放在第一个元素结点之前，头结点的数据域通常不存储信息。如果有头结点，那么头指针指向头结点，如果没有头结点，那么头指针指向第一个元素结点。

24.增加头结点的优点：

1. 有了头结点，链表的第一个元素结点的插入和删除操作就和其它位置的结点一样了，不需要特殊处理
2. 有了头结点，无论链表是不是为空链表，头指针都指向头结点，所以空表和非空表的处理得到了统一

25.循环单链表

是链表中最后一个结点的指针域不是空，而是指向头结点

26.循环单链表的优点

是可以从链表的任何一个结点开始遍历整个链表

27.双链表

是链表的每个结点有两个指针域，分别指向前驱结点和后继结点

28.双链表的优点

是可以方便地找到前驱结点

29.静态链表

静态链表的指针表示的是下一个元素在数组中的位置

30.栈和队列的区别

1. 栈和队列有相同的逻辑结构，都是线性结构，栈和队列都是操作受限的线性表
2. 栈和队列都可以采用顺序存储和链式存储
3. 栈是先进后出，在栈顶插入和删除元素，有栈顶指针top。
   队列是先进先出，在队尾插入元素，队头删除元素，有队头指针front和队尾指针rear

注:

• 队列插入元素是入队，删除元素是出队，所以队列在队尾入队，队头出队
• 队列删除元素（出队）修改队头指针front，插入元素（入队）修改队尾指针 rear

31.共享栈

是利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数组空间，将两个栈的栈底设在共享空间的两端，两个栈顶向共享空间的中间延伸，这样能够更有效的利用存储空间

32.顺序队列

• 判断顺序队列队空：队头指针=队尾指针=0
• 顺序队列入队（插入元素）：队尾指针加1
• 顺序队列出队（删除元素）：队头指针加1

33.循环队列

是把存储队列元素的表看成一个环，采用牺牲一个单元来区分队空和队满

注：% 是取余数

• 判断循环队列队空：队头指针 = 队尾指针
• 判断循环队列队满：队头指针 =（队尾指针 + 1）% 数组的容量
• 判断循环队列中的元素个数：(队尾指针-队头指针+数组的容量)%数组的容量
• 循环队列入队（插入元素）：队尾指针 =（队尾指针 + 1） % 数组的容量
• 循环队列出队（删除元素）：队头指针 =（队头指针 + 1） % 数组的容量

34.双端队列

两端都可以进行入队和出队操作的队列

35.队列的应用

层次遍历、缓冲区、页面替换算法

36.栈的应用

括号匹配、递归、表达式求值

37.栈在括号匹配中的算法思想

• 出现左括号，都进栈；
• 出现右括号，和栈顶元素比较，如果括号匹配，就把栈顶元素出栈，如果括号不匹配，就返回不匹配信息直接结束程序
• 算法结束的时候，如果栈空，就说明括号匹配

38.栈在后缀表达式求值的算法思想

顺序扫描表达式的每一项，如果该项是操作数，就入栈，若该项是操作符，则连续从栈中退出两个操作数Y和X，形成运算指令X操作符Y，并将计算结果重新压入栈中。当表达式的所有项都扫描并处理后，栈顶存放的就是最后的计算结果。

39.空串

空串长度是0

40.空格串

空格串长度是空格字符的个数

41.KMP算法思想

从主串和模式串的第一个字符开始比较，当出现字符不匹配的时候，模式串向右移动的位数等于已匹配字符数-模式串对应的部分匹配

注:

部分匹配值是字符串的前缀和后缀的最长相等前后缀长度

42.散列函数

一个把查找表中关键字映射成为该关键字对应的地址的函数

43.散列表（哈希hash表）

根据关键字而直接进行访问的数据结构，散列表建立了关键字和存储地址之间的一种直接映射关系

44.散列函数（哈希hash函数）的构造方法

1. 直接定址法：直接取关键字的某个线性函数值作为散列地址
2. 除留余数法：取一个不大于但是最接近散列表表长的质数p，利用公式
   把关键字转换成散列地址（公式：H(key) = key % p ）
3. 数字分析法：设关键字是r进制数，选取数码分布比较均匀的若干位作为散列地址
4. 平方取中法：选择关键字的平方值的中间几位作为散列地址

45.解决哈希（hash）冲突的方法

1. 线性探测法：是发生冲突的时候，顺序地查看表中下一个单元，直到找到一个空闲单元或者查遍全表。线性探测的缺点是可能会造成大量元素在相邻的散列地址上堆积，降低了查找效率
2. 链地址法（拉链法）：是发生冲突的时候，把具有相同散列地址的关键字存放到同一个单链表里面
3. 平方探测法：是发生冲突的时候，探测地址的增量序列是1^2、-1^2、2^2、-2^2，……k^2，-k^2，直到找到一个空闲单元或者查遍全表。平方探测法的优点是可以避免出现元素堆积，缺点是不能探测到散列表上的所有单元
4. 再散列法：是发生冲突的时候，使用另外一个散列函数
5. 伪随机序列法

注:

散列表查找成功的平均查找长度 = 所有关键字成功找到的比较次数之和 / 关键字个数

46.散列表的装填因子α

是表示一个表的装满程度。

装填因子α = 关键字个数 / 散列表的长度

47.散列表的查找效率的取决因素

散列函数、处理冲突的方法、装填因子

48.结点的度

是该结点的孩子结点的个数

49.树的度

是树里面结点的最大度数

50.树的存储结构

双亲表示法、孩子表示法、孩子兄弟表示法

51.二叉树

是指树里面的结点最多有两个孩子结点

52.满二叉树

是指除了最后一层的叶子结点，其它层的每个结点都有两个孩子结点的二叉树

53.完全二叉树

是指最后一层缺最右边的一些叶子结点，其它层的每个结点都有两个孩子结点的二叉树

54.二叉排序树

• 二叉树的定义：二叉排序树左子树的结点值 < 根结点值 < 右子树的结点值
• 二叉排序树的插入步骤：如果二叉排序树是空树，就把关键字当作根结点插入到空树里面，如果二叉排序树不是空树，如果关键字的值小于当前根结点的值，就把关键字插入到左子树，如果关键字的值大于当前根节点的值，就把关键字插入到右子树

55.线索二叉树

是把二叉链表中的空指针改成指向前驱结点或者后继结点的线索

56.平衡二叉树

是所有结点的左子树和右子树高度差的绝对值小于等于1的二叉树

57.平衡因子

结点左子树和右子树的高度差

58.哈夫曼树

是带权路径长度最小的二叉树

59.构造哈夫曼树的步骤

把给定的权集里面的每个结点看成只有一个结点的二叉树，构成森林。每次从森林里面选择两棵根节点权值最小的二叉树构成新的二叉树，新的二叉树的根节点的权值是左、右子树的根节点的权值之和，从森林里面删除刚刚被选择的两棵二叉树，同时将新的二叉树加入到森林里面，重复上面的步骤，直到森林里面只剩下一棵树为止

60.哈夫曼编码

统计每个字符出现的次数作为字符的权值，构造出哈夫曼树，从根节点出发，左分支是0，右分支是1

61.连通图

是指无向图里面任意两个顶点之间都是连通的

62.图的存储结构

邻接矩阵法、邻接表法、十字链表法、邻接多重表法

63.邻接矩阵与邻接表的比较

邻接矩阵是用二维数组存储各顶点之间的邻接关系，邻接表是图中每个顶点建立一个单链表，单链表的结点是和该顶点有邻接关系的顶点。对于稀疏图，邻接表比邻接矩阵节省存储空间

64.深度优先搜索

是首先访问图里面的一个起始顶点，然后访问和该起始顶点邻接但是没有被访问过的任意一个顶点，然后再访问和这个顶点邻接但是没有被访问过的任意一个顶点，重复上面的过程，直到一个顶点所有的邻接顶点都被访问过，然后依次退回到最近被访问的顶点，如果该顶点还有邻接顶点没有被访问过，就从这个顶点开始重复上面的过程，直到所有顶点都被访问过为止

65.广度优先搜索

是首先访问图里面的一个起始顶点，然后访问和该起始顶点邻接但是没有被访问过的所有顶点，再按这些邻接顶点的先后次序依次访问和它邻接但是没有被访问过的所有顶点，重复这个过程，直到所有顶点都被访问过为止

66.最小生成树

是包含图中所有的顶点，含有最少的边，并且不能有回路

67.普里姆Prim算法构造最小生成树（针对顶点）

从图中任选一个顶点加入到集合里面，从和集合里面的顶点相连的边里面选择权值最小的边，把这条边的顶点加入到集合里面，重复上面的过程，直到所有的顶点都加入集合为止。

普里姆算法的时间复杂度是O(N^2)

68.克鲁斯卡尔Kruskal算法构造最小生成树（针对边）

每次从没有被选择的边里面选择权值最小并且不构成回路的边，把这条边加入生成树里面，重复这个过程，直到所有的顶点都加入到生成树里面为止。

克鲁斯卡尔算法的时间复杂度是O（ElogE） E：是边数

注:

克鲁斯卡尔Kruskal算法适合边少但是顶点多的图

69.最短路径

是指从一个顶点到图中任意一个顶点的路径所经过的边的权值之和最小的路径

70.迪杰斯特拉Dijkstra算法求最短路径

• 迪杰斯特拉算法是求单源最短路径。
• 迪杰斯特拉的算法思想： 首先把起始顶点加入到集合里面，更新起始顶点到其它各个顶点的距离，找到距离最小的路径，然后把这个路径的顶点加入到集合里面，然后把这个顶点作为中心，看起始顶点到其它各个顶点的距离是不是比原来小，如果小的话就更新，然后找到距离最小的路径，把这个路径的顶点加入到集合里面，重复上面的步骤，直到所有的顶点都加入到集合里面。
• 迪杰斯特拉算法要求边的权值不能是负值，时间复杂度是O(n^2)

71.弗洛伊德Floyd算法是求最短路径

• 弗洛伊德Floyd算法是求任意顶点之间的最短路径
• 弗洛伊德Floyd算法里面边的权值可以是负值，时间复杂度是O(n^3)

72.拓扑排序

是从AOV网中选择一个没有前驱的顶点，输出该顶点，然后删除该顶点和以该顶点为起点的所有边，重复上面的过程，直到当前的AOV网为空或者当前AOV网不存在没有前驱的顶点为止

73.关键路径

是AOE网里面从源点到汇点的路径长度最大的路径

74.AOV网与AOE网的区别

AOV网的顶点表示活动，有向边表示活动之间的前后关系，AOV网的边没有权值。AOE网的顶点表示事件，有向边表示活动，边上的权值表示完成活动的开销。AOV网和AOE网都是有向无环图，但是它们的边和顶点代表的意思不一样。

75.贪心算法、动态规划、分治法的比较

• 贪心算法：是每次都选择当前状态下最好的选择，也就是局部的最优解，而不考虑这个局部最优解对全局的影响。贪心算法是自顶向下的方式进行，例如迪杰斯特拉Dijkstra算法采用了贪心算法
• 动态规划：是把原问题分解成若干个有重叠的子问题，保存已经解决的子问题的结果防止后面重复计算。动态规划算法是自底向上的方式进行。动态规划分为背包问题（01背包、完全背包、多重背包）、区间dp
• 分治法：是把原问题分解成若干个独立的子问题，递归地解决这些子问题，然后再合并子问题的解从而得到原问题的解。例如归并排序

76.程序设计语言的发展历史，每一类的特点

1. 机器语言：是计算机能够直接识别的二进制代码的集合。机器语言难学难写
2. 汇编语言：是把符号语言的指令转换为机器指令。汇编语言不能通用
3. 面向过程：是分析出解决问题的步骤，然后用函数把这些步骤实现，使用的时候依次调用函数就可以了
4. 面向对象：是把客观存在的事物抽象成对象，用对象去描述事物的行为。

注:

• 面向过程的性能比面向对象高，但是面向对象容易维护、容易复用。
• 面向对象有封装、继承、多态的特征

77.函数调用传参的方式

有值传递和地址传递

• 值传递：是把变量、常量、数组元素作为函数参数，形参值的变化不会影响到实参
• 地址传递：是把数组名或者指针作为函数参数，形参值的变化就是实参的变化

78.函数调用的返回方法

用return返回函数的值，返回值的类型根据函数类型决定，如果没有返回值，函数就要定义成void类型

79.有哪些控制结构

有顺序结构、选择结构（if、switch）、循环结构（while型循环、util型循环）

80.一维数组和顺序表的异同

顺序表和数组都可以随机存取，插入和和删除都要移动大量的元素，顺序表的位序从1开始，数组下标从0开始

81.带头结点的单链表删除数据为x的元素

定义两个指针变量，一个指针变量pre指向头结点，一个指针变量p指向第一个元素结点，指针一个指针变量指向头结点，另一个指针变量指向第一个元素结点，开始，依次比较每个结点的值，如果等于数据x，就把这个结点的

82.顺序表、单链表怎么插入元素

• 顺序表插入元素：在第i个位置插入元素，首先判断i是不是合法，如果i合法，把第i个元素和第i个元素后面的所有元素右移一个位置，然后把元素插入到第i个空位置
• 单链表插入元素：先检查插入位置的合法性，然后找到待插入位置的前驱结点，然后让新结点就指向了这个前驱结点的后继结点，前驱结点指向新结点

83.顺序结构怎么存储二叉树

是用一组连续的存储单元从上往下、从左往右存储二叉树的结点。

注:

链式存储是结点里面有数据域，左指针域，右指针域

84.怎么找前K个最大元素

先把元素用快速排序进行排序，然后取出前K个元素，时间复杂度是O（NlogN)

85.如何判断哈希函数的优劣

哈希函数计算出来的存储地址应该能等概率、均匀地分布在整个地址空间里面，从而减少冲突的发生，哈希函数应该尽量简单，能够在较短时间内计算出关键字的存储地址

86.KMP算法和朴素算法的比较

• 朴素算法：从主串和模式串的第一个字符开始比较，当出现字符不匹配的时候，把模式串向右移动一位然后从头开始比较。时间复杂度O（m*n）
• KMP算法思想：从主串和模式串的第一个字符开始比较，当出现字符不匹配的时候，模式串向右移动的位数等于已匹配字符数-模式串对应的部分匹配值。时间复杂度是O（m+n）

注:

部分匹配值：是前缀和后缀的最长相等长度

87.n！怎么算

第一种方法是用循环求阶乘，设循环变量i为从 1 变化到 n，变量sum的初始值定义为1，循环里面让循环变量i和 sum 相乘，把结果赋给 sum

第二种方法是用递归求阶乘，递归出口是n等于1的时候直接返回1，结束递归

88.阶乘较大数据溢出怎么处理

用数组来保存阶乘的结果，每个位置存放1个数字，数组的第一个位置存放个位，第二个位置存放十位，依次类推

89.二维矩阵相乘需要几层循环

需要三层循环，第一层循环控制左边矩阵的行，第二层循环控制右边矩阵的列，第三层循环控制左边矩阵的列，也是右边矩阵的行，比如说前2层循环确定了是左边矩阵第一行和右边矩阵第一列，那么第三层循环就是让左边第一行第一列的元素和右边第一行第一列元素相乘，然后加上左边第一行第二列的元素和右边第二行第一列的元素相乘，依次类推