哈工大2008数据结构期末试题：算法与链表操作

"这是一份2008年哈工大的数据结构与算法期末试题，包含填空题、简答题和算法设计等部分，重点考察学生对数据结构和算法的理解与应用。" 以下是对试题中涉及知识点的详细解释： 1. 对称矩阵的压缩存储：在主序存储方式下，对称矩阵只存储下三角或上三角部分，可以节省空间。对于10阶对称矩阵，85位于第5行第5列，其地址可以通过矩阵存储规律计算得出。 2. 广义表操作：广义表的Head和Tail操作用于获取表头和表尾元素。Tail操作连续两次应用于Head(A)，将得到A的第二个元素的表，再应用Head得到元素本身。 3. 链表操作的时间复杂度：在已知节点P后插入节点的时间复杂度是O(1)，因为只需要改变几个指针。在值域给定值的节点后插入，需遍历找到特定值的节点，时间复杂度是O(n)。 4. 后缀表达式：后缀表达式（逆波兰表示法）是不使用括号，而是使用堆栈来表示运算优先级的表达式。转换表达式需要遵循运算符优先级规则。 5. 栈和队列的操作：元素通过栈S进入队列Q，出队顺序为b，d，c，f，e，a，说明栈的容量至少要能容纳三个元素，因为a进栈后，b，c，d出栈，然后e进栈，最后f进栈。 6. 二叉树的结点数：对于二叉树，如果只有叶子结点，总结点数最少为50，最多为2^50-1（满二叉树）。 7. 完全二叉树的层关系：在同一层的节点i和j满足2^(i-1) <= j < 2^(i)，即它们的二进制位数相同。 8. Huffman树：根据Huffman编码构建的树，高度取决于最远叶节点到根的距离，带权路径长度WPL是所有叶节点权值与其路径长度之积的和。 9. 无向图的最小顶点数：非连通图至少有两个连通分量，所以至少有14个顶点（每个连通分量至少有1个环，28/2=14）。形成环的图有n棵树，当图是树时，生成树数为1。 10. 折半查找：在有序数组中，查找7需要比较3次，查找41需要比较3次。最大比较次数为log2(100)+1=7次。 11. 希尔排序：基于插入排序的改进方法，步长序列一般选取为1，1/2，1/4...，第二趟排序结束后，记录间的差距缩小至原来的一半。 12. 拓扑排序：有向无环图（DAG）可进行拓扑排序，入度为0的顶点（没有前驱）可以从图中移除。若无法拓扑排序，说明图中存在环。 13. 散列冲突解决：线性探测再散列是一种处理冲突的方法，当K个关键字为同义词时，会在同一位置产生冲突，可能导致探测序列很长。如果图不能一次拓扑排序，说明图中存在环或不是DAG。 以上是试题中的主要知识点，涵盖了数据结构如链表、栈、队列、二叉树、图，以及算法如哈希、后缀表达式、希尔排序和拓扑排序。这些知识点在计算机科学中至关重要，是理解算法和数据结构的基础。