数组面试试题及答案

数组面试试题及答案一、单选题（每题2分，共20分）1.以下哪个不是数组的特性？（）A.动态可变B.存储相同类型元素C.通过索引访问D.内存连续分配【答案】A【解析】数组的大小在创建后通常是固定的，虽然有些语言提供了动态数组，但其本质仍是预分配一块连续内存并在需要时扩展，并非真正的动态可变。2.在Java中，声明数组`int[]arr=newint[5];`后，`arr[2]`的初始值是（）。A.0B.5C.nullD.抛出异常【答案】A【解析】Java中数组的元素默认初始化为其类型的默认值，基本类型`int`的默认值是0。3.以下哪个操作的平均时间复杂度是O(1)？（）A.在数组末尾添加元素B.在数组中间插入元素C.获取数组中第i个元素D.删除数组中的元素【答案】C【解析】获取数组中第i个元素只需直接通过索引访问，时间复杂度为O(1)。4.动态数组（如Java的ArrayList）在扩容时通常会增加多少倍容量？（）A.1倍B.1.5倍C.2倍D.0.5倍【答案】C【解析】常见实现中，动态数组在扩容时会将容量加倍。5.以下哪个方法用于在数组中查找特定元素的位置？（）A.`add()`B.`remove()`C.`indexOf()`D.`contains()`【答案】C【解析】`indexOf()`方法返回数组中特定元素的位置索引。6.在Python中，创建数组`arr=[1,2,3]`后，执行`arr.append(4)`后，`arr`的内容是（）。A.[1,2,3]B.[1,2,3,4]C.[4,3,2,1]D.抛出异常【答案】B【解析】`append()`方法在列表末尾添加元素。7.以下哪个不是多维数组的特性？（）A.可以有多个索引维度B.每个维度的大小必须相同C.可以存储不同类型元素D.通过嵌套索引访问【答案】C【解析】多维数组的所有元素必须属于同一类型。8.在C++中，声明数组`intarr[3][4];`的内存布局是（）。A.3行4列B.4行3列C.12个连续的intD.3个指向4个int的指针【答案】A【解析】二维数组在内存中是按行连续存储的。9.以下哪个数据结构是数组的直接扩展？（）A.链表B.栈C.队列D.哈希表【答案】A【解析】链表可以看作是动态数组的一种改进，通过节点指针实现动态内存分配。10.在数组中删除元素后，通常会发生什么？（）A.数组大小不变B.被删除元素变为nullC.后续元素前移D.内存被释放【答案】C【解析】删除元素后，通常需要将后续元素向前移动填补空位。二、多选题（每题4分，共20分）1.以下哪些是数组的优缺点？（）A.随机访问快B.插入删除慢C.内存连续D.动态可变E.内存碎片【答案】A、B、C【解析】数组优点是随机访问快、内存连续；缺点是插入删除慢（需要移动元素），且通常不是动态可变的（除非特殊实现），内存连续可能导致碎片。2.以下哪些语言支持数组？（）A.JavaB.PythonC.C++D.JavaScriptE.SQL【答案】A、B、C、D【解析】Java、Python、C++、JavaScript都支持数组，SQL是数据库查询语言，不直接支持数组类型。3.数组在哪些场景下适用？（）A.元素数量固定B.需要频繁随机访问C.需要频繁插入删除D.元素类型统一E.需要排序【答案】A、B、D【解析】数组适用于元素数量固定、频繁随机访问且类型统一的场景，不适用于频繁插入删除。4.动态数组的扩容策略有哪些？（）A.增加固定大小B.增加当前大小的一半C.增加当前大小的两倍D.增加当前大小的1.5倍E.保持不变【答案】C、D【解析】常见的扩容策略是增加当前容量的两倍或1.5倍。5.数组有哪些常见的操作？（）A.获取元素B.设置元素C.添加元素D.删除元素E.排序元素【答案】A、B、C、D、E【解析】数组支持获取、设置、添加、删除和排序等操作。三、填空题（每题4分，共16分）1.数组通过________和________来访问元素。【答案】索引，地址【解析】数组元素通过索引（下标）和内存地址来访问。2.在Java中，声明数组`String[]names;`后，通过`names[0]="Alice";`为________赋值。【答案】names[0]【解析】`names[0]`是数组`names`的第一个元素。3.动态数组的扩容通常涉及到________和________两个步骤。【答案】分配新内存，复制旧数据【解析】扩容需要先分配更大的内存空间，然后将旧数据复制到新空间。4.二维数组可以看作是________的数组。【答案】一维【解析】二维数组可以看作是由多个一维数组组成的。四、判断题（每题2分，共10分）1.数组的大小在创建后不能改变。（）【答案】（√）【解析】普通数组的大小在创建后是固定的。2.数组的元素可以是不同类型。（）【答案】（×）【解析】通常数组要求所有元素类型相同。3.数组的随机访问时间复杂度是O(n)。（）【答案】（×）【解析】数组的随机访问时间复杂度是O(1)。4.删除数组中的元素会改变数组的大小。（）【答案】（×）【解析】删除元素通常只是移动后续元素，不改变数组容量。5.数组在内存中一定是连续分配的。（）【答案】（×）【解析】只有普通数组（非动态数组）在内存中是连续分配的。五、简答题（每题5分，共15分）1.简述数组的优缺点。【答案】优点：-随机访问快：通过索引可以O(1)时间访问任意元素。-内存连续：连续存储提高缓存命中率，访问效率高。-实现简单：数据结构直观，操作直接。缺点：-插入删除慢：需要移动后续元素，时间复杂度O(n)。-大小固定：普通数组大小在创建后不变，动态数组也有扩容开销。-内存碎片：频繁扩容可能导致内存碎片。2.如何实现数组的动态扩容？【答案】动态扩容通常通过以下步骤实现：1.当数组达到容量上限时，分配一个更大的新数组（通常是当前容量的1.5倍或2倍）。2.将旧数组中的所有元素复制到新数组中。3.释放旧数组的内存。4.将引用指向新数组。这种方式虽然扩容时需要O(n)时间，但日常使用中随机访问效率高。3.数组和链表有什么区别？【答案】区别：-内存布局：数组内存连续，链表内存不连续（通过指针连接）。-访问方式：数组通过索引随机访问O(1)，链表需要从头遍历O(n)。-插入删除：数组插入删除O(n)，链表插入删除O(1)（如果知道位置）。-大小：数组大小通常固定或需要扩容，链表可以动态增长。-内存开销：数组每个元素类型固定，链表每个节点有额外指针开销。六、分析题（每题10分，共20分）1.分析数组排序算法的时间复杂度和适用场景。【答案】常见排序算法：-冒泡排序：时间复杂度O(n²)，适用于小规模数据或几乎已排序的数据。-选择排序：时间复杂度O(n²)，适用于小规模数据。-插入排序：时间复杂度O(n²)，适用于小规模或几乎已排序的数据。-快速排序：平均时间复杂度O(nlogn)，适用于大规模数据，但最坏情况O(n²)。-归并排序：时间复杂度O(nlogn)，稳定排序，适用于大规模数据。-堆排序：时间复杂度O(nlogn)，适用于大规模数据，非稳定排序。适用场景：-数据规模：小规模数据适合简单排序如插入排序；大规模数据适合高效排序如快速排序、归并排序。-数据特性：几乎已排序数据适合插入排序；数据随机分布适合快速排序；需要稳定排序时选择归并排序。-内存限制：堆排序不需要额外内存；归并排序需要O(n)额外内存。2.设计一个动态数组类，说明其关键方法和实现思路。【答案】动态数组类设计：-数据成员：-`array`：存储元素的数组-`capacity`：数组的容量-`size`：数组当前大小-关键方法：1.构造函数：-初始化`capacity`（如初始容量为10）-分配`array`内存-`size`设为02.`add(element)`：-检查是否需要扩容：如果`size==capacity`，则扩容（如容量加倍）-将`element`添加到`array[size]`-`size++`3.`get(index)`：-检查`index`是否有效（0<=index<size）-返回`array[index]`4.`remove(index)`：-检查`index`是否有效-将`array[index+1..size-1]`前移一位-`size--`5.`size()`：-返回当前数组大小-实现思路：-使用`ArrayList`（Java）或类似机制实现-扩容时复制元素到新数组，避免内存泄漏-提供高效访问和修改接口-保持容量和大小同步更新七、综合应用题（每题25分，共50分）1.设计一个函数，实现将一个二维数组按行展开成一维数组。【答案】函数设计：-输入：二维数组`matrix`和行数`rows`、列数`cols`-输出：一维数组`flattened`实现步骤：1.初始化`flattened`数组，大小为`rowscols`2.遍历`matrix`的每一行，将每一行的元素按顺序放入`flattened`中3.返回`flattened`伪代码：```functionflatten(matrix,rows,cols):flattened=newarray[rowscols]forifrom0torows-1:forjfrom0tocols-1:flattened[icols+j]=matrix[i][j]returnflattened```示例：输入：`matrix=[[1,2],[3,4]]`输出：`[1,2,3,4]`2.设计一个函数，实现查找数组中和为特定值的最长子数组。【答案】函数设计：-输入：一维数组`nums`和目标值`target`-输出：和为`target`的最长子数组的起始和结束索引（如果不存在则返回-1）实现思路：-使用哈希表记录前缀和及其对应的索引-初始化哈希表`prefixSumIndex`，加入`{0:-1}`（前缀和为0时索引为-1）-初始化变量`maxLen`为0，`currentSum`为0-遍历数组：-`currentSum+=nums[i]`-如果`currentSum-target`在`prefixSumIndex`中：-计算子数组长度`len=i-prefixSumIndex[currentSum-target]`-如果`len>maxLen`，更新`maxLen`和起始索引-如果`currentSum`不在`prefixSumIndex`中：-加入`{currentSum:i}`伪代码：```functionfindLongestSubarray(nums,target):prefixSumIndex={0:-1}maxLen=0currentSum=0start=-1forifrom0tolen(nums)-1:currentSum+=nums[i]ifcurrentSum-targetinprefixSumIndex:len=i-prefixSumIndex[currentSum-target]iflen>maxLen:maxLen=lenstart=prefixSumIndex[currentSum-target]+1ifcurrentSumnotinprefixSumIndex:prefixSumIndex[currentSum]=iifmaxLen>0:return(start,start+maxLen-1)else:return(-1,-1)```示例：输入：`nums=[1,2,3,4,5],target=9`输出：`(1,3)`（子数组`[2,3,4]`和为9，长度为3）---标准答案一、单选题1.A2.A3.C4.C5.C6.B7.C8.A9.A10.C二、多选题1.A、B、C2.A、B、C、D3.A、B、D4.C、D5.A、B、C、D、E三、填空题1.索引，地址2.names[0]3.分配新内存，复制旧数据4.一维四、判断题1.√2.×3.×4.×5.×五、简答题1.数组的优缺点：优点：-随机访问快：通过索引可以O(1)时间访问任意元素。-内存连续：连续存储提高缓存命中率，访问效率高。-实现简单：数据结构直观，操作直接。缺点：-插入删除慢：需要移动后续元素，时间复杂度O(n)。-大小固定：普通数组大小在创建后不变，动态数组也有扩容开销。-内存碎片：频繁扩容可能导致内存碎片。2.如何实现数组的动态扩容？动态扩容通常通过以下步骤实现：1.当数组达到容量上限时，分配一个更大的新数组（通常是当前容量的1.5倍或2倍）。2.将旧数组中的所有元素复制到新数组中。3.释放旧数组的内存。4.将引用指向新数组。这种方式虽然扩容时需要O(n)时间，但日常使用中随机访问效率高。3.数组和链表有什么区别？区别：-内存布局：数组内存连续，链表内存不连续（通过指针连接）。-访问方式：数组通过索引随机访问O(1)，链表需要从头遍历O(n)。-插入删除：数组插入删除O(n)，链表插入删除O(1)（如果知道位置）。-大小：数组大小通常固定或需要扩容，链表可以动态增长。-内存开销：数组每个元素类型固定，链表每个节点有额外指针开销。六、分析题1.分析数组排序算法的时间复杂度和适用场景。常见排序算法：-冒泡排序：时间复杂度O(n²)，适用于小规模数据或几乎已排序的数据。-选择排序：时间复杂度O(n²)，适用于小规模数据。-插入排序：时间复杂度O(n²)，适用于小规模或几乎已排序的数据。-快速排序：平均时间复杂度O(nlogn)，适用于大规模数据，但最坏情况O(n²)。-归并排序：时间复杂度O(nlogn)，稳定排序，适用于大规模数据。-堆排序：时间复杂度O(nlogn)，适用于大规模数据，非稳定排序。适用场景：-数据规模：小规模数据适合简单排序如插入排序；大规模数据适合高效排序如快速排序、归并排序。-数据特性：几乎已排序数据适合插入排序；数据随机分布适合快速排序；需要稳定排序时选择归并排序。-内存限制：堆排序不需要额外内存；归并排序需要O(n)额外内存。2.设计一个动态数组类，说明其关键方法和实现思路。动态数组类设计：-数据成员：-`array`：存储元素的数组-`capacity`：数组的容量-`size`：数组当前大小-关键方法：1.构造函数：-初始化`capacity`（如初始容量为10）-分配`array`内存-`size`设为02.`add(element)`：-检查是否需要扩容：如果`size==capacity`，则扩容（如容量加倍）-将`element`添加到`array[size]`-`size++`3.`get(index)`：-检查`index`是否有效（0<=index<size）-返回`array[index]`4.`remove(index)`：-检查`index`是否有效-将`array[index+1..size-1]`前移一位-`size--`5.`size()`：-返回当前数组大小-实现思路：-使用`ArrayList`（Java）或类似机制实现-扩容时复制元素到新数组，避免内存泄漏-提供高效访问和修改接口-保持容量和大小同步更新七、综合应用题1.设计一个函数，实现将一个二维数组按行展开成一维数组。函数设计：-输入：二维数组`matrix`和行数`rows`、列数`cols`-输出：一维数组`flattened`实现步骤：1.初始化`flattened`数组，大小为`rowscols`2.遍历`matrix`的每一行，将每一行的元素按顺序放入`flattened`中3.返回`flattened`伪代码：```functionflatten(matrix,rows,cols):flattened=newarray[rowscols]forifrom0torows-1:forjfrom0tocols-1:flattened[icols+j]=matrix[i][j]returnflattened```示例：输入：`matrix=[[1,2],[3,4]]`输出：`[1,2,3,4]`2.设计一个函数，实现查找数组中和为特定值的最长子数组。函数设计：-输入：一维数组`nums`和目标值`target`-输出：和为`target`的最长子数组的起始和结束索引（如果不存在则返回-1）实现思路：-使用哈希表记录前