数据结构复习重点：填空题及答案解析

"《数据结构》综合复习资料涵盖了数据结构的基本概念、数据结构的类型、树的存储方式、哈希表、抽象数据类型、算法设计评价标准、时间复杂度分析、中缀表达式与后缀表达式的转换、字符串定义、排序算法、线性表的链式存储、矩阵存储、图的表示、模式匹配、二叉树性质以及各种排序算法的应用实例等。" 1. 数据结构是研究数据的组织方式、存储结构和操作的学科，它为数据的处理提供高效的方法。 2. 堆栈是后进先出（LIFO）的数据结构，而队列则是先进先出（FIFO）；字符串中的数据元素通常是字符。 3. 树的存储方式包括顺序存储（数组实现）、链式存储（链表实现）和二叉链表（二叉树的节点结构）。 4. 哈希表查找的性能取决于哈希函数的选择、冲突解决策略以及表的装载因子。 5. 抽象数据类型（ADT）是逻辑上的一组数据和在这些数据上定义的操作，与具体实现无关。 6. 给定程序的时间复杂度为O(n^2)，因为它包含两个嵌套循环，每个循环都与n成正比。 7. 中缀表达式a+b*c/d+e*f转换为后缀表达式为ab*c/d+ef*+，这是通过堆栈来实现的。 8. 含零个字符的串称为空串，用空格表示；其他串称为非空串；串的长度是它所含字符的数量。 9. 2路归并排序一趟后的结果未给出，一般会交替合并元素，保持相对顺序。 10. 数据的逻辑结构分为集合、线性结构、树形结构和图形结构。 11. 算法设计的评价标准通常包括正确性、效率（时间复杂度和空间复杂度）、可读性和健壮性。 12. 在单链表中，当前元素的后继结点地址可通过指针字段获取，若用数组表示，其后继结点下标为p+1。 13. 串的模式匹配是查找子串是否存在于主串中的过程，存在返回子串起始位置，不存在返回失败信息。 14. 二叉树第5层最多有2^4=16个结点；给定双分支5个，单分支6个，叶子结点数可以通过公式2n0+n1-1计算得出，此处n0为叶子结点，n1为单分支结点。 15. 邻接矩阵求度数的时间复杂度为O(n)，邻接表为O(e)，其中n是顶点数，e是边数。 16. 增量为4的希尔排序结果未给出，希尔排序是一种插入排序的变种，通过比较间隔为增量的元素来逐步减小增量并排序。 17. 数据结构的四种基本形式包括集合、线性结构、树形结构和图形结构。 18. 线性表的链式存储结构有单链表、双向链表和循环链表。 19. 矩阵T[i,j]的存储地址可以通过base+w*(i-1)*m+j-1计算得出。 20. 在邻接表中，无向图顶点的度等于其邻接点域的元素个数；对于有向图，出度是出边数，入度是入边数。 21. 排序序列的关键字在希尔排序中可能经历多次调整，每次调整后序列的局部有序性会增强。 以上是对《数据结构》复习资料中涉及知识点的详细解析，涵盖了许多核心概念和重要算法。