南邮数据结构C语言期末复习：重点题型与解题技巧

本资源是一份针对南京邮电大学数据结构课程期末复习的资料，主要涉及C语言在数据结构中的应用。内容包括选择题和填空题，旨在帮助学生巩固和准备考试。 一、单选题 1. 在单链表HL中向表头插入一个新节点，正确操作是将新节点的next指针指向原表头，然后更新表头指针，即`p->next = HL; HL = p;`，因此答案是C。 2. 强连通图中，任意两个顶点都互为源点和汇点，所以至少存在一条从每个顶点到其他所有顶点的路径。对于n个顶点的图，至少需要n条有向边，使得每个顶点都能到达其他顶点，答案是B。 3. 二叉搜索树查找的时间复杂度与树的高度有关，最坏情况下（完全不平衡）为O(n)，但平均情况下是O(logn)，因此答案是C。 4. 计算哈夫曼树的带权路径长度，可以通过构建哈夫曼树的过程得知，这里没有给出具体的构建过程，但带权路径长度等于所有叶子结点的权值之和，答案可能是A、B或C，具体数值需根据实际计算。 5. 当需要处理大对象且可能修改时，应选择引用类型，因为这样可以避免复制整个对象，答案是B。 6. 顺序表插入操作的时间复杂度与表长度成正比，平均情况下是线性的，答案是A。 二、填空题 1. 数据的存储结构主要包括顺序存储、链式存储、索引存储和散列存储。 2. 广义表的存储结构中，单元素结点通常有指针域指向下一个元素，而表元素结点除了数据域外可能还有其他关联的指针域。 3. 中缀表达式`3 + x * (2.4 / 5 - 6)`转换为后缀表达式需要考虑运算符优先级，答案需要根据具体规则来确定。 4. 一棵高度为h的3叉树最多结点数可通过递归公式得出，为`3^(h+1) - 1`，填空时需要计算具体数值。 5. 二叉树的最小深度是1（根节点），最大深度为h（完全二叉树）。对于18个结点的二叉树，其最小深度取决于具体形状，填空时需进一步分析。 6. 在二叉搜索树中，左子树的节点值小于父节点，右子树的节点值大于父节点。 7. 小根堆插入最小值元素时，需要调整堆结构使其满足堆性质，通常是从堆顶（最后一个已排序元素的位置）开始向下调整。 8. 表示图的三种常见存储结构是邻接矩阵、邻接表和邻接多重表，用于记录顶点之间的连接关系。 9. 邻接矩阵表示图时，它是一个n×n的矩阵，其中行和列对应图的顶点，元素表示顶点间是否有边以及边的权重。 这份复习资料全面覆盖了数据结构中C语言的基本概念、操作和理论，以及与二叉树、哈夫曼树和图相关的知识点，适合南邮数据结构课程期末复习使用。