华东理工数据结构期末复习：填空与单选题解析

"该文档是华东理工大学网络教育数据结构本科课程的期末复习资料，包含了填空题和单选题，涵盖了数据结构的基础概念和算法，如图和树的遍历、有向图的性质、完全二叉树的特性、字符串操作、数组存储、队列的概念以及相关操作、线索二叉树的判断、顺序表的操作、折半查找的效率、广义表的操作和二叉树的遍历序列等。" 在数据结构中，图的深度优先遍历（DFS）和广度优先遍历（BFS）是重要的算法，它们分别对应于树的先序遍历和层次遍历。例如，DFS类似于先序遍历，从根节点开始，而BFS则类似于层次遍历，从根节点逐层展开。对于有向图，邻接矩阵是一种常用的存储方式，其中第i行所有元素之和表示顶点i的出度，即以顶点i为起点的边的数量。 完全二叉树的性质是另一个重点。如果一棵完全二叉树有1000个结点，那么它有500个叶子结点（度为0的结点），499个度为2的结点，由于最后一层只有一个结点度为1，其余结点要么度为2要么是叶子，所以只有一个结点只有非空左子树，没有结点只有非空右子树。 图的边数在无向图中是顶点数量的组合，最多可以达到n(n-1)/2条，而有8个结点的无向图最多有28条边。树转换为二叉树时，根节点的右子树总是空的。 字符串操作中的子串定位是指找出一个字符串q在另一个字符串p中首次出现的位置。在二维数组的存储中，可以通过已知元素的位置计算其他元素的地址，比如题目中的例子展示了如何从A[1][5]的地址推算A[18][9]的地址。 队列是一种线性数据结构，遵循先进先出（FIFO）原则，允许在队尾进行插入操作。在顺序表的插入操作中，若在第i个位置插入元素，需要将后面的n-i+1个元素都向后移动一位。 折半查找是一种高效的查找方法，对于长度为n的有序顺序表，查找关键码11，如果不存在，比较次数最多会是log2n次。广义表A=(())是一个空表，它的表尾也是空表。 最后，二叉树的中序和后序遍历可以用来确定先序遍历序列。例如，给定中序和后序遍历序列，可以反推出先序序列。在给出的例子中，先序序列是ABDEGCFA。 这些知识点覆盖了数据结构的基础内容，对于学习者来说，理解和掌握这些概念和算法对于通过期末考试至关重要。