大学计算机科学数据结构测试试卷及答案

大学计算机科学数据结构测试试卷及答案一、选择题（共20分，每题1分）1.在长度为n的顺序表中，删除第i个元素的时间复杂度为（）A.O(1)B.O(n)C.O(logn)D.O(i)2.以下哪种数据结构是非线性结构？（）A.栈B.队列C.树D.数组3.在双向链表中，删除一个已知结点p，需要执行的操作是（）A.p->prior->next=p->next;p->next->prior=p->prior;B.p->prior->next=p->next;C.p->next->prior=p->prior;D.p->prior->next=p->next;free(p);4.二叉树的先序遍历序列为ABDEC，中序遍历序列为DBEAC，后序遍历序列为（）A.DEBCAB.DEABCC.DBECAD.DEACB5.对于包含n个结点的二叉树，其最小高度为（）A.⌈log₂n⌉B.⌊log₂n⌋C.nD.n/26.在二叉排序树中，查找一个元素的平均时间复杂度为（）A.O(1)B.O(n)C.O(logn)D.O(n²)7.以下哪种排序算法的平均时间复杂度为O(nlogn)？（）A.冒泡排序B.选择排序C.快速排序D.插入排序8.在哈希表中，处理冲突的方法不包括（）A.开放定址法B.链地址法C.二次探测法D.二分查找法9.以下哪种数据结构适合实现表达式求值？（）A.队列B.栈C.树D.图10.广度优先遍历算法通常使用的数据结构是（）A.栈B.队列C.树D.图11.在长度为n的有序表中，使用二分查找一个元素的最坏情况时间复杂度为（）A.O(1)B.O(n)C.O(logn)D.O(n²)12.以下哪种排序算法是不稳定的？（）A.冒泡排序B.插入排序C.选择排序D.归并排序13.在邻接矩阵表示的图中，判断两个顶点之间是否有边需要的时间复杂度为（）A.O(1)B.O(n)C.O(logn)D.O(n²)14.以下哪种数据结构适合实现LRU缓存淘汰算法？（）A.数组B.链表C.哈希表D.双向链表+哈希表15.在字符串匹配中，KMP算法的时间复杂度为（）A.O(m+n)B.O(mn)C.O(m²)D.O(n²)16.以下哪种排序算法是外部排序？（）A.快速排序B.归并排序C.堆排序D.基数排序17.在平衡二叉树（AVL树）中，插入一个结点后，树的高度最多增加（）A.1B.2C.3D.018.以下哪种数据结构适合实现文件系统的目录结构？（）A.栈B.队列C.树D.图19.在并查集中，路径压缩操作的时间复杂度为（）A.O(1)B.O(n)C.O(logn)D.O(α(n))，其中α(n)是阿克曼函数的反函数20.在B树中，查找一个元素的时间复杂度为（）A.O(1)B.O(n)C.O(logn)D.O(n²)1.答案：B解析：在顺序表中删除第i个元素需要将其后的所有元素前移一位，时间复杂度为O(n)。易错警示：误认为删除操作只需修改指针即可，实际上顺序表需要移动元素。2.答案：C解析：树是一种非线性结构，因为元素之间存在一对多的关系。而栈、队列和数组都是线性结构，元素之间是一对一的关系。3.答案：A解析：删除双向链表中的结点p需要修改其前驱结点的next指针和后继结点的prior指针，使它们相互指向。定义：双向链表是每个结点包含数据域和两个指针域（分别指向直接前驱和直接后继）的链表。4.答案：A解析：根据先序遍历序列ABDEC和中序遍历序列DBEAC，可以构造出二叉树结构，然后进行后序遍历得到DEBCA。计算过程：先序遍历的第一个元素A是根，在中序序列中A左边是DBE（左子树），右边是C（右子树）；然后对左子树DBE，先序序列中B是根，中序序列中DBE左边是D（左子树），右边是E（右子树）；最终构造的二叉树结构为A为根，左子树为B，B的左子树为D，B的右子树为E，A的右子树为C，后序遍历为DEBCA。5.答案：A解析：包含n个结点的二叉树的最小高度为⌈log₂(n+1)⌉-1，但通常简化为⌈log₂n⌉。公式：高度h满足2^h≥n+1，因此h≥⌈log₂(n+1)⌉-1。6.答案：C解析：在二叉排序树中，查找一个元素的平均时间复杂度为O(logn)，但在最坏情况下（树退化为链表）为O(n)。易错警示：忽略了二叉排序树平衡性的影响，只有在平衡二叉排序树中才能保证O(logn)的时间复杂度。7.答案：C解析：快速排序的平均时间复杂度为O(nlogn)，而冒泡排序、选择排序和插入排序的平均时间复杂度均为O(n²)。定义：快速排序是一种分治排序算法，通过选择一个基准元素将数组分为两部分，然后递归地对两部分进行排序。8.答案：D解析：处理哈希冲突的方法包括开放定址法、链地址法、二次探测法等，而二分查找法是一种查找方法，不是处理哈希冲突的方法。易错警示：混淆了查找方法和哈希冲突处理方法的概念。9.答案：B解析：栈适合实现表达式求值，因为表达式求值需要处理运算符的优先级和结合性，这可以通过栈的后进先出特性来实现。例如，在将中缀表达式转换为后缀表达式或直接计算表达式时，栈可以用来存储操作数和运算符。10.答案：B解析：广度优先遍历算法通常使用队列来实现，因为队列的先进先出特性符合广度优先遍历的层级访问顺序。定义：广度优先遍历是从图的某个顶点出发，访问所有相邻的顶点，然后再访问这些顶点的相邻顶点，依此类推。11.答案：C解析：在长度为n的有序表中，使用二分查找一个元素的最坏情况时间复杂度为O(logn)。公式：二分查找每次都将搜索范围减半，因此最多需要⌈log₂n⌉次比较。12.答案：C解析：选择排序是不稳定的排序算法，因为在选择最小元素的过程中，可能会改变相等元素的相对顺序。而冒泡排序、插入排序和归并排序都是稳定的排序算法。易错警示：误认为所有常见的排序算法都是稳定的，实际上选择排序和堆排序是不稳定的。13.答案：A解析：在邻接矩阵表示的图中，判断两个顶点之间是否有边只需访问矩阵中对应的元素，时间复杂度为O(1)。定义：邻接矩阵是一个二维数组，矩阵中的元素表示两个顶点之间是否有边。14.答案：D解析：双向链表+哈希表适合实现LRU缓存淘汰算法，因为双向链表可以快速调整元素的访问顺序，而哈希表可以快速查找元素。具体来说，当访问一个元素时，可以通过哈希表找到该元素对应的链表结点，并将其移动到链表头部，表示最近访问。15.答案：A解析：KMP算法的时间复杂度为O(m+n)，其中m是模式串的长度，n是主串的长度。公式：KMP算法通过预处理模式串得到部分匹配表，然后在主串中只需回溯模式串的位置，而不需要回溯主串的位置。16.答案：D解析：基数排序是一种外部排序算法，适用于对大规模数据进行排序。而快速排序、归并排序和堆排序都是内部排序算法。易错警示：误认为所有常见的排序算法都是内部排序，实际上基数排序是一种外部排序算法。17.答案：A解析：在平衡二叉树（AVL树）中，插入一个结点后，树的高度最多增加1，然后通过旋转操作保持平衡。定义：平衡二叉树是一种特殊的二叉搜索树，其中每个结点的左右子树高度差的绝对值不超过1。18.答案：C解析：树适合实现文件系统的目录结构，因为目录结构具有层次关系，每个目录可以包含子目录和文件。定义：树是一种非线性数据结构，由根结点和若干棵子树组成，子树之间不相交。19.答案：D解析：在并查集中，路径压缩操作的时间复杂度为O(α(n))，其中α(n)是阿克曼函数的反函数，增长非常缓慢，可以视为常数。公式：阿克曼函数A(m,n)是一个增长极快的函数，其反函数α(n)增长非常缓慢。20.答案：C解析：在B树中，查找一个元素的时间复杂度为O(logn)，其中n是树中元素的个数。定义：B树是一种多路平衡搜索树，每个结点包含多个键和多个子结点指针。二、填空题（共15分，每空1分）1.数据结构的四种基本类型是：_________、_________、_________和_________。2.在链表中，每个结点包含_________和_________两部分。3.二叉树的遍历方式有：_________、_________和_________。4.在排序算法中，排序的稳定性是指_________。5.哈希函数的设计原则包括：_________、_________和_________。6.图的存储方式主要有：_________和_________。7.在堆排序中，构建初始堆的时间复杂度为_________。8.在字符串匹配中，KMP算法的核心是利用_________来避免不必要的回溯。9.平衡二叉树（AVL树）的平衡因子定义为_________。10.在B树中，每个结点最多有_________个子结点，最少有_________个子结点（根结点除外）。11.在并查集中，两个常用的优化操作是_________和_________。12.线索二叉树是为了解决_________问题而设计的。1.答案：集合、线性结构、树形结构、图形结构解析：数据结构的四种基本类型是集合、线性结构、树形结构和图形结构。它们之间的区别在于元素之间关系的复杂程度，从无关系（集合）到一对一关系（线性结构），再到一对多关系（树形结构），最后到多对多关系（图形结构）。2.答案：数据域、指针域解析：在链表中，每个结点包含数据域和指针域两部分。数据域用于存储数据元素，指针域用于存储指向下一个结点的地址。定义：链表是一种线性数据结构，由一系列结点组成，每个结点包含数据和指向下一个结点的指针。3.答案：前序遍历、中序遍历、后序遍历解析：二叉树的遍历方式有前序遍历、中序遍历和后序遍历。前序遍历的顺序是根-左-右，中序遍历的顺序是左-根-右，后序遍历的顺序是左-右-根。此外，还有一种层序遍历，按照层级顺序访问结点。4.答案：相等元素的相对顺序在排序前后保持不变解析：排序的稳定性是指相等元素的相对顺序在排序前后保持不变。如果排序算法是稳定的，那么对于相等的元素，它们在排序后的顺序与在原始序列中的顺序相同。例如，稳定的排序算法可以保持学生按学号排序时，相同成绩的学生按学号顺序排列。5.答案：计算简单、均匀分布、减少冲突解析：哈希函数的设计原则包括计算简单、均匀分布和减少冲突。计算简单意味着哈希函数应该快速计算，均匀分布意味着哈希函数应该将键均匀地分布在哈希表的槽中，减少冲突意味着哈希函数应该尽量避免不同的键映射到同一个槽。6.答案：邻接矩阵、邻接表解析：图的存储方式主要有邻接矩阵和邻接表。邻接矩阵使用二维数组表示图，适合稠密图；邻接表使用链表数组表示图，适合稀疏图。定义：邻接矩阵是一个二维数组，矩阵中的元素表示两个顶点之间是否有边；邻接表是一个数组，数组的每个元素是一个链表，存储与该顶点相邻的所有顶点。7.答案：O(n)解析：在堆排序中，构建初始堆的时间复杂度为O(n)。公式：构建堆的过程是从最后一个非叶子结点开始，依次向前调整每个子树，使其满足堆的性质。对于包含n个元素的堆，调整操作的总时间复杂度为O(n)。8.答案：部分匹配表解析：在字符串匹配中，KMP算法的核心是利用部分匹配表来避免不必要的回溯。部分匹配表记录了模式串中每个位置的最长相同前后缀的长度，当匹配失败时，根据部分匹配表确定模式串应该向右移动的距离，而不需要回溯主串的位置。9.答案：左子树高度减去右子树高度解析：平衡二叉树（AVL树）的平衡因子定义为左子树高度减去右子树高度。定义：平衡因子是衡量二叉树平衡程度的指标，对于AVL树，每个结点的平衡因子的绝对值不超过1。10.答案：m、⌈m/2⌉解析：在B树中，每个结点最多有m个子结点，最少有⌈m/2⌉个子结点（根结点除外）。定义：B树是一种多路平衡搜索树，每个结点包含多个键和多个子结点指针，子结点指针的数量比键的数量多1。11.答案：路径压缩、按秩合并解析：在并查集中，两个常用的优化操作是路径压缩和按秩合并。路径压缩是在查找过程中压缩路径，使后续查找更快；按秩合并是在合并时将深度较小的树合并到深度较大的树下，以保持树的平衡。定义：并查集是一种树形数据结构，用于处理一些不相交集合的合并及查询问题。12.答案：二叉树的遍历效率解析：线索二叉树是为了解决二叉树的遍历效率问题而设计的。在普通二叉树中，遍历需要使用栈或递归来保存访问路径，而线索二叉树利用空指针域存储遍历信息，使得遍历无需额外的栈空间。定义：线索二叉树是在二叉树的结点中增加线索，指向前驱和后继结点，从而可以像链表一样直接访问结点的前驱和后继。三、判断题（共10分，每题1分）1.顺序表的插入和删除操作的时间复杂度均为O(1）。（）2.循环队列不存在假溢出现象。（）3.满二叉树一定是完全二叉树。（）4.二叉排序树的中序遍历序列一定是有序的。（）5.快速排序的最坏时间复杂度为O(n²)。（）6.在哈希表中，负载因子越大，发生冲突的概率越大。（）7.深度优先遍历可以使用栈来实现。（）8.归并排序是稳定的排序算法。（）9.在邻接表表示的图中，删除一个顶点的时间复杂度为O(n)。（）10.B树和B+树都是多路平衡搜索树，它们的查找效率相同。（）1.答案：×解析：顺序表的插入和删除操作的时间复杂度均为O(n)，而不是O(1)。在顺序表中插入或删除元素需要移动其他元素，时间复杂度与元素的位置有关。易错警示：误认为顺序表的插入和删除操作可以直接通过下标访问，实际上需要移动元素。2.答案：√解析：循环队列通过将队列的首尾相连，避免了假溢出现象。在循环队列中，当队尾指针到达数组末尾时，会回到数组开头继续存储元素。定义：循环队列是一种特殊的队列，其存储空间是首尾相连的循环空间。3.答案：√解析：满二叉树一定是完全二叉树。满二叉树是指所有层都被完全填满的二叉树，而完全二叉树是指除了最后一层外，其他层都被完全填满，且最后一层的结点都靠左对齐。满二叉树满足完全二叉树的所有条件。定义：满二叉树是指所有层都被完全填满的二叉树；完全二叉树是指除了最后一层外，其他层都被完全填满，且最后一层的结点都靠左对齐。4.答案：√解析：二叉排序树的中序遍历序列一定是有序的。这是二叉排序树的性质之一，因为二叉排序树是一种二叉搜索树，其中每个结点的左子树中的所有结点的值都小于该结点的值，右子树中的所有结点的值都大于该结点的值。定义：二叉排序树是一种二叉搜索树，其中每个结点的左子树中的所有结点的值都小于该结点的值，右子树中的所有结点的值都大于该结点的值。5.答案：√解析：快速排序的最坏时间复杂度为O(n²)，当输入序列已经有序或逆序时，快速排序会退化到O(n²)。公式：快速排序的平均时间复杂度为O(nlogn)，但最坏情况下为O(n²)。易错警示：忽略了快速排序最坏情况下的时间复杂度，误认为快速排序的时间复杂度总是O(nlogn)。6.答案：√解析：在哈希表中，负载因子越大，发生冲突的概率越大。负载因子是哈希表中元素数量与哈希表容量的比值，负载因子越大，意味着哈希表越满，发生冲突的概率越大。定义：负载因子是哈希表中元素数量与哈希表容量的比值，用于衡量哈希表的填充程度。7.答案：√解析：深度优先遍历可以使用栈来实现。深度优先遍历的递归实现本质上是使用了系统栈，而非递归实现则可以使用显式栈。定义：深度优先遍历是从图的某个顶点出发，沿着一条路径尽可能深地访问顶点，直到无法继续为止，然后回溯并选择其他路径继续遍历。8.答案：√解析：归并排序是稳定的排序算法。在归并排序中，当两个相等元素被合并时，它们的相对顺序保持不变，因为合并操作是按顺序进行的。定义：稳定的排序算法是指相等元素的相对顺序在排序前后保持不变。9.答案：×解析：在邻接表表示的图中，删除一个顶点的时间复杂度为O(n+e)，其中n是顶点数，e是边数。因为需要遍历所有顶点的邻接表来删除与该顶点相关的边。易错警示：误认为删除一个顶点只需O(1)时间，实际上需要遍历所有邻接表来删除相关边。10.答案：×解析：B树和B+树都是多路平衡搜索树，但它们的查找效率不相同。B+树的查找效率通常比B树高，因为B+树的内部结点不存储数据，只作为索引，而B树的内部结点存储数据和索引。定义：B树是一种多路平衡搜索树，每个结点包含多个键和多个子结点指针；B+树是B树的一种变体，所有数据存储在叶子结点中，内部结点只作为索引。四、简答题（共25分，每题5分）1.简述顺序存储结构和链式存储结构的优缺点，并说明它们分别适用于什么场景。2.解释什么是平衡二叉树（AVL树），并说明在插入新结点后如何进行旋转调整以保持平衡。3.简述快速排序的基本思想，并分析其平均时间复杂度和最坏时间复杂度。4.解释什么是哈希冲突，并列举至少三种处理哈希冲突的方法。5.简述Dijkstra算法的基本思想，并说明为什么它不能处理带负权边的图。1.答案：顺序存储结构和链式存储结构的优缺点及适用场景：顺序存储结构：优点：-可以随机访问，通过下标直接访问任意元素-存储密度高，不需要额外的指针空间-实现简单，内存连续缺点：-插入和删除操作需要移动大量元素，时间复杂度高-需要预先分配连续的存储空间，可能导致空间浪费或溢出-扩容操作复杂，需要重新分配内存并复制数据适用场景：-数据量固定且需要频繁随机访问的场景-内存充足且数据连续性要求高的场景-如数组、顺序表等链式存储结构：优点：-插入和删除操作效率高，只需修改指针-动态分配内存，不会出现空间浪费或溢出-扩容操作简单，只需添加新结点缺点：-不能随机访问，只能顺序访问-存储密度低，需要额外的指针空间-实现相对复杂，内存不连续适用场景：-数据量不确定且需要频繁插入和删除的场景-内存有限且数据动态变化的场景-如链表、栈、队列等2.答案：平衡二叉树（AVL树）是一种特殊的二叉搜索树，其中每个结点的左右子树高度差的绝对值不超过1。这种平衡性保证了树的高度保持在O(logn)范围内，从而保证了查找、插入和删除操作的时间复杂度为O(logn)。在插入新结点后，AVL树可能会失去平衡，需要进行旋转调整以保持平衡。根据插入位置的不同，可能出现的失衡情况有四种：-左左型（LL）：在某个结点的左子树的左子树中插入结点导致失衡。解决方案是进行右旋。-右右型（RR）：在某个结点的右子树的右子树中插入结点导致失衡。解决方案是进行左旋。-左右型（LR）：在某个结点的左子树的右子树中插入结点导致失衡。解决方案是先左旋再右旋。-右左型（RL）：在某个结点的右子树的左子树中插入结点导致失衡。解决方案是先右旋再左旋。旋转操作的基本思想是通过重新组织树的结构，使树恢复平衡。例如，右旋操作将失衡结点的左子树提升为新的根结点，原根结点成为其右子树的根，原左子树的右子树成为原根结点的左子树。3.答案：快速排序的基本思想是分治法。选择一个基准元素（pivot），将数组分为两部分：一部分的所有元素小于基准元素，另一部分的所有元素大于基准元素。然后递归地对这两部分进行排序，最后将排序好的两部分和基准元素合并起来。快速排序的平均时间复杂度为O(nlogn)，这是因为在平均情况下，每次划分都能将数组大致分为两个相等的部分，递归树的深度为logn，每一层处理的总时间为O(n)。然而，快速排序的最坏时间复杂度为O(n²)，当输入序列已经有序或逆序时，每次划分只能将数组分为一个元素和n-1个元素的两部分，递归树的深度为n，导致时间复杂度退化为O(n²)。为了避免最坏情况，可以采用随机选择基准元素或三数取中法选择基准元素，这样可以提高划分的均衡性，降低出现最坏情况的概率。4.答案：哈希冲突是指不同的键通过哈希函数映射到哈希表的同一个位置的现象。由于哈希表的容量通常小于键的数量，哈希冲突是不可避免的。处理哈希冲突的方法有：-开放定址法：当发生冲突时，按照一定的规则寻找下一个可用的位置。常用的探测方法有线性探测、二次探测和双重哈希等。-链地址法：将哈希表中每个位置维护为一个链表，所有映射到同一位置的键都存储在对应的链表中。-再哈希法：使用多个不同的哈希函数，当一个哈希函数发生冲突时，尝试使用另一个哈希函数。-建立公共溢出区：将哈希表分为两个区域：基本区和溢出区。发生冲突的元素被存储在溢出区中。这些方法各有优缺点：开放定址法节省空间但可能导致聚集现象；链地址法空间利用率高但需要额外的指针空间；再哈希法效果好但计算复杂；建立公共溢出区实现简单但可能导致溢出区过大。5.答案：Dijkstra算法用于求解单源最短路径问题，其基本思想是从源点开始，逐步确定到其他顶点的最短路径。算法维护一个集合S，包含已确定最短路径的顶点，以及一个距离数组dist，记录从源点到各顶点的当前最短距离。初始时，S只包含源点，dist数组中源点的距离为0，其他顶点的距离为无穷大。然后，每次从S外的顶点中选择距离最小的顶点u加入S，并更新u的所有邻接顶点的距离。重复这个过程，直到S包含所有顶点或没有可达顶点为止。Dijkstra算法不能处理带负权边的图，因为它基于贪心策略，每次选择当前距离最小的顶点加入集合S，并认为其最短路径已经确定。如果存在负权边，已经加入S的顶点的最短路径可能会因为后续发现的负权边而变得更短，这与算法的贪心选择矛盾。例如，考虑一个图，其中从源点到某个顶点u有一条路径长度为5，从u到另一个顶点v有一条长度为-3的边，那么从源点到v的最短路径长度为2，但如果算法先确定了u的最短路径为5，就不会考虑这条更短的路径。对于带负权边的图，可以使用Bellman-Ford算法，它可以处理负权边并能检测负权环，但时间复杂度较高，为O(VE)，其中V是顶点数，E是边数。五、算法设计与分析题（共30分，每题10分）1.设计一个算法，判断一个单链表是否有环。如果有环，返回环的入口结点；如果没有环，返回NULL。2.设计一个算法，实现二叉树的层序遍历，并分析算法的时间复杂度和空间复杂度。3.设计一个算法，实现归并排序，并分析算法的时间复杂度和空间复杂度。1.答案：判断单链表是否有环，并返回环的入口结点的算法：```cstructListNode{intval;ListNodenext;ListNode(intx):val(x),next(NULL){}};ListNodedetectCycle(ListNodehead){if(head==NULL||head->next==NULL){returnNULL;}ListNodeslow=head;ListNodefast=head;//使用快慢指针判断是否有环while(fast!=NULL&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;if(slow==fast){//有环，找到环的入口slow=head;while(slow!=fast){slow=slow->next;fast=fast->next;}returnslow;}}//没有环returnNULL;}```算法分析：时间复杂度：O(n)，其中n是链表的长度。快慢指针相遇需要最多n步，找到环的入口也需要最多n步。空间复杂度：O(1)，只使用了常数个额外空间。算法原理：1.使用快慢指针遍历链表，快指针每次移动两步，慢指针每次移动一步。2.如果链表有环，快慢指针最终会在环中的某一点相遇。3.当快慢指针相遇时，将一个指针重新指向链表头部，然后两个指针以相同的速度移动，它们会在环的入口处再次相遇。证明：假设链表头部到环入口的距离为a，环的长度为b，快慢指针在环中相遇的位置距离环入口为c。当快慢指针相遇时，慢指针走了a+c步，快指针走了a+c+kb步（k为快指针在环中绕的圈数）。因为快指针的速度是慢指针的两倍，所以有：2(a+c)=a+c+kb化简得：a+c=kb即：a=kb-c=(k-1)b+(b-c)这表明，如果将一个指针重新指向链表头部，另一个指针保持在相遇位置，然后两个指针以相同的速度移动，它们会在环的入口处再次相遇。2.答案：二叉树的层序遍历算法：```cstructTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(intx):val(x),left(NULL),right(NULL){}};vector<vector<int>>levelOrder(TreeNoderoot){vector<vector<int>>result;if(root==NULL){returnresult;}queue<TreeNode>q;q.push(root);while(!q.empty()){intlevelSize=q.size();vector<int>currentLevel;for(inti=0;i<levelSize;i++){TreeNodenode=q.front();q.pop();currentLevel.push_back(node->val);if(node->left!=NULL){q.push(node->left);}if(node->right!=NULL){q.push(node->right);}}result.push_back(currentLevel);}returnresult;}```算法分析：时间复杂度：O(n)，其中n是二叉树的结点数。每个结点被访问一次。空间复杂度：O(n)，在最坏情况下（完全二叉树），队列中最多存储⌈n/2⌉个结点。算法原理：1.使用队列来存储待访问的结点。2.首先将根结点入队。3.当队列不为空时，循环执行以下操作：a.获取当前队列的大小（即当前层的结点数）。b.创建一个临时列表存储当前层的结点值。c.循环处理当前层的所有结点：i.出队一个结点，将其值加入临时列表。ii.如果该结点有左子结点，将左子结点入队。iii.如果该结点有右子结点，将右子结点入队。d.将临时列表加入结果列表。4.返回结果列表。3.答案：归并排序算法：```cvoidmerge(vector<int>&nums