清华数据结构试题详解：从填空到图论

数据结构是一门重要的计算机科学分支，它主要研究如何组织和存储数据，并通过高效的算法处理这些数据结构，以便于非数值计算的程序设计问题。在这份数据结构试卷中，涵盖了多种数据结构和相关概念，包括： 1. **线性结构与关系**：线性结构如顺序表，元素间存在一对一的关系，每个元素只有一个前驱和后继。树形结构，如二叉树，元素之间存在父-子关系，而图形结构，如图或图的遍历，元素间的关系更为复杂，可能存在多个邻居。 2. **顺序表和链表的特性**：顺序表的优点是随机访问速度快，但插入和删除操作可能导致大量元素移动，移动次数与插入位置有关；而单链表的物理位置不连续，插入和删除操作效率较高，但访问任一元素需要从头开始遍历。 3. **字符串操作**：串的匹配算法如朴素算法，其时间复杂度与主串和子串的长度有关，最坏情况下需要比较n-m+1次字符。广义表操作涉及数据结构的高级操作，如获取头部和尾部元素。 4. **完全二叉树的性质**：完全二叉树的特点是除了最后一层外，每一层都是完全填满的，且最后一层的节点都集中在左边。这使得我们可以根据节点数量计算出树的深度、叶子节点数、度为2的节点数等。 5. **图的存储与遍历**：图可以采用邻接矩阵或邻接表等形式存储，不同的存储方式对算法的时间复杂度有影响。遍历图的方法有深度优先搜索（DFS）和广度优先搜索（BFS），后者通常用于寻找最短路径。 6. **排序算法与查找算法**：Dijkstra算法用于求解单源最短路径问题，按照路径长度递增顺序找到最短路径。折半查找在有序线性表中按对半分的方式进行，查找次数与查找目标的位置相关。查找算法中，哈希查找通常不受结点个数影响，而直接插入排序和选择排序的性能取决于数据的初始排列。 7. **归并排序的时间复杂度**：归并排序是一种稳定的排序算法，对于n个记录，平均时间复杂度为O(n log n)，这在任何情况下都是稳定的。 这份试卷覆盖了数据结构的基础理论和实际应用，旨在考察学生对数据结构概念的理解、算法实现以及对数据操作性能的分析能力。通过解答这些问题，学习者可以巩固对数组、链表、树、图、排序算法等核心数据结构的掌握，并提升解决问题的能力。