2003年哈工大春季学期数据结构期末考试难题解析

本资源是一份关于哈工大2003年春季学期的数据结构期末考试试卷，包含填空题和单项选择题，涵盖了数据结构的基础概念和操作。 1. 填空题部分： - 问题1：下三角矩阵的元素存储在一行存储的一维数组中，由于矩阵是下三角形，元素aij的位置在B数组中对应的是从上到下的顺序，因此k = i * (i + 1) / 2 - j + 1。 - 问题2：二元树中度数为2的节点数等于总节点数减去度为0的节点数，即67 - (67 - 1)/2 = 34个。 - 问题3：在无环路有向图中，从顶点i到j的路径保证了拓扑序列中i在j之前。 - 问题4：无向图的邻接表中，表结点代表边，所以边的数量等于结点个数减去1（因为每个结点都有一条指向自己的边）。 - 问题5：对于已排序的表，堆排序和快速排序的时间复杂度较低，但堆排序在最坏情况下仍保持O(n log n)，而快速排序在最差情况下退化为O(n^2)，因此堆排序可能更优。 - 问题6：根据先根序和中根序可以推断，叶节点出现在两个序列的相同位置，因此是DEFGH。 - 问题7：哈夫曼树的叶子节点数总是比非叶子节点数多1，所以19个结点的哈夫曼树有10个叶节点。 - 问题8：归并排序过程中，每次合并需要比较一次，直到合并为一个有序表，因此至少需要比较m + n - 1次。 - 问题9：在顺序表中插入元素，平均移动元素个数为(n-1)/2，假设概率均匀分布。 - 问题10：元素进出栈和队列的顺序要求，a3和a5出栈后立即进入队列，其余依次出队，意味着栈至少要容纳所有元素，即6个。 2. 单项选择题部分： - 题目1：算法分析的主要目标是分析算法的效率以求改进，C选项正确。 - 题目2：查找前后继，单链表操作简单，双向链表更适合，B选项正确。 - 题目3：顺序表的缺点之一是空间利用率低于链表，C选项错误。 - 题目4：队列常用顺序存储（数组）和链式存储（链表）两种结构，A选项正确。 - 题目5：具有三个节点的二元树有5种形态，分别是全左分支、全右分支、左中右分支、右中左分支和全平衡分支，C选项正确。 - 题目6：未给出深度为5的具体二元树形态，但一般深度为5的完全二叉树有31个节点，二叉树形态多样。 这份试卷涵盖了数据结构的基本概念，如矩阵和数组的映射、二叉树的性质、图的表示、排序算法的比较、线性表的操作以及常见数据结构的选择等，适合用于测试学生对数据结构理论的理解和应用能力。