复试第一章

1.数据结构的基本概念

1.数据的基本单位：数据元素，一个数据元素可由多个数据项组成**（数据元素相当于一条数据，包括name，age等；数据项相当于一个类中的属性）**
2.数据元素不可分割的最小单位： 数据项
3.数据对象： 数据对象是具有相同性质的数据元素的集合
4.数据类型： 一个值的集合，和定义在这个集合上的一组操作的总称

1.1数据结构

数据结构指的是相互之间存在一种或多种特定关系的数据元素的集合。数据元素他们之间的关系叫为结构——>(1.逻辑结构 2.存储结构 3.数据的运算)

1.1.1数据的逻辑结构

分为线性结构和非线性结构，线性结构：线性表，栈和队列；非线性结构：一般树，二叉树，图

1.1.2存储结构

存储结构指的是：数据结构在计算机中的表示（称为映像或者物理结构），包括数据元素的表示和关系的表示，
主要有：顺序存储，链式存储，索引存储，散列存储

1.顺序存储：
把逻辑相邻的元素存储在物理位置相邻的存储单元上，元素之间的关系由存储单元的邻接关系来体现；
优点：实现了随机存取，每个元素占用了最少的存储空间，缺点是只能使用相邻的一块存储单元，可能会产生相邻的外部碎片，插入删除效率低，因为需要重新分配内存，内存地址发生了改变
想到了几个垃圾回收的算法和内存的分代
2.链式存储：
不要求逻辑相邻元素在存储单元上位置也相邻，而是利用指示元素存储地址的指针来实现元素之间的逻辑关系；
缺点:访问效率为0(n)，插入和删除效率高，但是指针会占用多余的内存空间
3.索引存储：
在存储信息时候，会建立附加的索引表，索引表中的每一项为索引项（关键字，地址），优点：检索速度快，缺点：需要额外的空间去维护索引表
Mysql索引
索引八股
索引优化
4.散列存储
本质就是hash运算
HashMap介绍
CurrentHashMap

3.例题

D.栈。

栈是一种抽象的数据类型，表示具有后进先出（LIFO）特点的数据结构。它与数据的存储结构无关，可以用数组实现，也可以用链表实现。而循环队列、链表和哈希表都是具体的数据结构，与存储结构有关。

D. 数据结构仅由其逻辑结构和存储结构决定。

数据结构包括逻辑结构和存储结构两个方面。逻辑结构描述了数据元素之间的关系，不考虑具体的存储方式。而存储结构则决定了数据在计算机内存中的实际存储方式。因此，数据结构是由其逻辑结构和存储结构共同决定的，选项 D 是正确的说法。选项 A 和 B 都是错误的，因为逻辑结构和存储结构是相互影响的。选项 C 也是错误的，因为逻辑结构并不唯一决定存储结构，不同的存储结构可以用于实现相同的逻辑结构。
3.

C

4.算法分析

1.五大特性： 有穷性，确定性，可行性，输入，输出

2.时间复杂度：

1.
2.

该算法中，while 循环的条件是 iii <= n。每次循环，i 的值递增1，直到满足条件。因此，循环的次数取决于 i 的值，而 i 的值是从 0 开始逐渐增加，直到 i^3 大于 n 为止。可以得出结论，当 i^3 等于或超过 n 时，循环终止。

假设最后一次循环时，i 的值为 m，即 m^3 <= n 且 (m+1)^3 > n。则可以推导出 m 约等于 n^(1/3)。因此，该算法的时间复杂度为 O(n^(1/3))

O(n^2)。

在最坏情况下，第一个循环的执行次数为 n - 1，第二个循环的执行次数为 1 + 2 + … + (n - 1) = n(n - 1)/2。内层循环中 if 语句的执行次数最多为每次循环两次，因此 if 语句的频度最多为 n(n-1)。最后一行语句是一个元素交换的操作，执行次数和 if 语句的频度相同，即最多为 n(n-1)。

因此，最后一行语句的频度为 O(n(n-1))，即 O(n^2)
4.

**(外层到顶2的k次等于n，k为log2n，内层为1+2+4+2的n=k次方-1，带入得n)**在这个算法中，外层循环的迭代次数是通过将 i 乘以 2 来逐步递增的，直到 i >= n。内层循环的迭代次数是从 0 到 i-1，即每次内层循环都会执行 i 次。

因此，总迭代次数可以表示为：
1 + 2 + 4 + 8 + … + n/2 + n

这是一个等比数列求和，可以化简为：
n - 1 + n/2 + n/4 + n/8 + … + 1

当 n 趋近于无穷大时，可以近似表示为 n + n/2 + n/4 + n/8 + … + 1，即一个常数倍的 n。因此，时间复杂度为 O(n)。
5.

1.这段代码的时间复杂度为 O(n)。循环条件为 i < n - 1，每次循环 i 增加 1，因此循环执行次数与 n 相关，时间复杂度为 O(n)。
2.这段代码的时间复杂度为 O(sqrt(n))。循环条件为 (y + 1) * (y + 1) <= n，每次循环 y 增加 1，循环的次数大约是 sqrt(n)，因此时间复杂度为 O(sqrt(n))。
3.这段代码的时间复杂度为 O(n * m)。外层循环执行 n 次，内层循环执行 m 次，因此总的执行次数为 n * m，时间复杂度为 O(n * m)。