复旦大学计算机科学期末考卷：数据结构习题详解

本资源是一份复旦大学计算机科学技术学院《数据结构》期末考试试卷A卷，包含了填空题部分，涵盖了数据结构的基础概念和基本操作。以下是各题目的知识点概述： 1. **二维数组空间计算**：题目询问了二维数组W的空间占用以及按行存储时特定元素的地址。由于每个元素占4个字节，行数为8，列数为4，因此总字节数为\(8 \times 4 = 32\)字节/元素。数组起始地址为100，所以元素W[6,3]位于第6行，第3列，其起始地址为\(100 + (6 \times 4) + (3 \times 4) = 128\)字节。 2. **后缀表达式计算**：后缀算式923+-102/-的值需要根据运算规则从左到右依次计算，最后得到结果为-1。中缀表达式(3+4X)-2Y/3转换为后缀表达式时，首先将操作数移到末尾，符号放在前面，即34X*+2Y*3/-。 3. **哈夫曼树**：哈夫曼树是构建最优二叉树的过程，求解带权路径长度（WPL）需利用赫夫曼编码。题目没有给出具体步骤，但5个权值的哈夫曼树构建后，WPL可以通过递归构建过程中节省的边权值之和得到，为71。 4. **二分查找次数**：在有序表中查找关键字72，由于72恰好位于中间位置，二分查找会比较一次就找到，次数为1次。 5. **邻接矩阵的零元素**：无向图的邻接矩阵中，每行每列对应一个顶点，除了对角线上的元素（表示自环），其余非边的元素为0。无自环且无重边的图中，零元素数量为\(n^2 - 2e\)，其中n为顶点数，e为边数。 6. **完全二叉树的叶子结点**：在完全二叉树中，最后一层的所有节点都尽可能靠左排列，叶子结点的数量等于所有结点数减去1（根节点不算）。768个结点的完全二叉树有\(768 - 1 = 767\)个叶子结点。 7. **有向图的拓扑排序**：给出了一个有向图的边集，拓扑排序需要确定结点之间的依赖关系，最终得到的排序是a->e->b->d->c->f。 8. **队列操作**：题目要求实现队列的入队操作，队列是先进先出（FIFO）的数据结构。EnQueue函数需要检查队列是否满，不满时将元素x添加到队尾，并更新队列头指针和尾指针。 以上知识点涵盖了数据结构中的数组存储、后缀表达式、哈夫曼树、图论、搜索算法、队列操作等基础内容，是衡量学生掌握数据结构理论和实践能力的重要部分。