数据结构复习：线性结构、时间复杂度解析

"数据结构总复习.pdf" 在计算机科学中，数据结构是组织和管理数据的方式，它对理解和处理信息至关重要。本复习资料涵盖了数据结构的基础概念，包括逻辑结构、存储结构以及它们与计算机的关系。 1. 数据结构分为两大类：线性结构和非线性结构。线性结构如数组、链表、栈和队列，数据元素之间存在一对一的关联；非线性结构如树、图等，数据元素之间的关系更为复杂。 2. 线性表L的LengthList(L)初始值为5，经过DelList(L, 2)操作，即删除第二个元素后，LengthList(L)将减一，因此新的值为4。 3. 在数据结构中，逻辑结构与所使用的计算机无关，它只关注数据元素之间的关系，而存储结构则涉及数据在内存中的实际布局，这与硬件和操作系统相关。 4. 下面的双层循环程序段的时间复杂度为O(m*n)，因为两个循环是嵌套的，每次外层循环执行m次，内层循环执行n次，总操作次数为m*n。 5. 双层嵌套循环，每层循环都是从1到n，因此执行T语句的次数为n*(n+1)/2，时间复杂度为O(n^2)。 6. void fun(int n)中的循环是指数增长的，每次循环i变为i*3，所以时间复杂度为O(log3n)，以3为底n的对数。 7. 链队中删除一个节点的操作通常是更新队首指针，使其指向下一个节点，即f=f->next。 8. 栈遵循后进先出（LIFO）原则，因此编号为1，2，3，4的列车，按栈结构出站，不可能出现1在4之前且2在3之前的情况，例如1423。 9. 时间代价T(n) = 300n + 20nLog2n + 10n^2，主要项是10n^2，因此时间复杂度为O(n^2)。 10. 二分查找法在长度为n的线性表上的平均查找长度为O(log2n)，因为它每次将查找范围减半。 11. 归并排序是分治法的一个例子，给定的有序子表合并时，应保持原有的相对顺序。对于给出的序列(25，48，16，35，79，82，23，40)，一次归并后可能的结果是16, 25, 35, 48, 23, 40, 79, 82，因为每个长度为2的有序子表被正确地合并在一起。 这些知识点是数据结构学习中的基础，对于理解和解决计算机问题至关重要，尤其是对于使用C语言或其他编程语言进行编程的大学生来说。通过深入理解这些概念，可以更有效地设计和分析算法的效率。