函数会递归地调用自身 n 次。每次调用的工作量是常数时间（仅包括一次乘法和一次减法），所以总体的时间复杂度为 n 次调用乘以每次调用的常数时间，即 O(n)。

哈希线性探测ASL 1. 构造散列表 根据散列函数 H(key) = key %7 以及线性再探测，构造出散列表，如下图 2. 计算失败的平均查找长度 计算失败，可以转换理解，就是在已经构造好的散列表上，我们再去插入一个新的值需要比较多少次。 比如，现在我再插入一个数 21，那么理论上...

我们需要选择前k个关键字最小的元素，而且k可能远小于n。这与对整个数组进行排序的目标不同。由于我们并不需要对整个数组进行排序，选择一种可以在部分排序后立即获取结果的排序算法将更有效。 快速选择算法（QuickSelect）。快速选择算法是由快速排序算法派生出来的，用于在未排序的列表中找到第k...

们需要在队尾进行插入操作，并在队头进行删除操作。如果只有头结点指针，那么每次在队尾进行插入操作时，我们都需要从头结点开始遍历到队尾，这样的时间复杂度是O(n)，这是不可接受的

错因：错以为快速排序最快的时候是左右指针各自扫描到中间就好了。——不是啊  得分块   快速排序硬性条件 low < high；第一趟选择一个pivot，和剩余的七个元素作比较--七次。其他趟数同理。

行优先+下三角：数组下标：i(i-1)/2 + j - 1 (8*7)/2 + 5 - 1

错因：做成了中缀表达式求值。————题目要求做后缀表达式求值   注意区分几个过程： ①中缀表达式求值：操 作数栈+操作符栈  ==>  中缀表达式直接模拟  结果是中缀表达式的计算结...

错因：以为求的是将最小元素冒出来需要移动的次数 ——问的是排好序总共要比较多少趟

按行+上三角：数组下标：(n+(n-1)+...+(n-i+2))+j-i i=5  j=8 (10+9+8+7)+8-3=37

直接插入排序， 最坏情况下，需比较n(n-1)/2 次关键字 最好情况下，需要比较n-1次关键字 

三对角矩阵就是梭型矩阵   三对角矩阵除了第一行和最后一行两个元素，其他行都是3个元素  

直接插入排序：每次插入都可能需要移动大量元素。 冒泡排序：每次交换都需要三次移动（一个用于备份，一个用于交换，一个用于将备份值放到正确的位置）。 简单选择排序：每一趟排序最多只需要交换一次，也就是说，每次选出最小（或最大）的元素后，只需要将这个元素与其应在的位置上的元素交换一次。 ...

当一个稀疏矩阵被压缩后，它会失去随机存取的特性。这是因为在压缩的稀疏矩阵中，元素的物理存储顺序不再与其在矩阵中的逻辑位置一一对应。因此，我们不能像在二维数组中那样直接通过索引来访问元素。

快速排序最好情况下 每次分的一个小组n个元素，比较次 数为n-1 一组偶数个，基准位置放到中间偏 右的第一个位置。

二叉排序树的中序遍历得到的是递增序列 所以不管构建二叉排序树序列是什么，中序遍历结果都是递增序列。   错因：没理解题意这句话的意思：“由关键字集合{18，43，27，44，36，39}中的某个关键字序列构建的” >>> ...

第一个维度的元素个数为：2 - (-2) + 1 = 5 第二个维度的元素个数为：5 - (-4) + 1 = 10 第三个维度的元素 个数 为：6 - 2 + 1 = 5将这三个维度的元素个数相乘，我们可以得到整个三维数组的元素个数：5 * 10 * 5 = 250 &...

对于元素a[i][j]，在它之前已经存储了j列的所有元素和第j+1列的前i个元素，总共有j×m+i个元素。   为什么是前边是存储了j列： j=5; a[5] ||<-5个 ->||  ↓ 0  1 ...

时间复杂度： A. 折半查找 O(log n) B. 顺序查找 O(n) C. 分块查找 O(√n) D. 二叉排序树查找 O(log n) 本题认为折半查找要快于二叉排序树 ——数据如果无序，则二叉排序树最快

做题的时候看错图了，少数了一行 5*5+3=28

装填因  子  = 表中记录数 / 哈希表长度  >>> 因此，拉链法装填因子可以大于1  >>>  拉链法查找时间和装填因子没有关系 ——可能装填因...