北航软院2011年数据结构与C语言程序设计试题与答案

### 北航软院2011年数据结构与C语言程序设计试题与答案解析 #### 单项选择题解析 **1. 关于线性表的存储结构** - **选项分析**： - A选项指出线性表的顺序存储结构中隐式地存储了数据元素之间的逻辑关系，这是正确的，因为在顺序存储中，元素的位置直接反映了它们之间的逻辑关系。 - B选项提到线性表的顺序存储结构一定需要占用一片地址连续的存储空间，这也是正确的，因为顺序存储的特点就是利用数组实现，而数组要求连续的空间。 - C选项描述了线性表的链式存储结构通过指针来反映数据元素之间的逻辑关系，这一点也是准确的，链表中的节点通过指针指向下一个节点，从而表示逻辑上的顺序。 - D选项断言线性表的链式存储结构占用的存储空间一定不连续，这个说法过于绝对，虽然通常链表的空间是不连续的，但也有可能在某些特殊情况下，部分或全部节点恰好位于连续的空间内。 **2. 链接队列插入新元素的操作** - **选项分析**： - A选项和B选项的操作都是错误的，因为它们没有正确处理队列的队头和队尾指针。 - C选项的步骤是正确的，首先更新队尾节点的指针，然后将新节点设置为队尾。 - D选项同样错误，因为它没有正确更新队尾指针。 **3. 关于二叉树的性质** - **选项分析**： - A选项指出二叉树的度可以小于2，这是正确的，因为二叉树的每个节点最多有两个子节点。 - B选项说二叉树的度等于2，这显然是错误的，因为度指的是节点的最大子节点数，而不是整个树的特性。 - C选项表明二叉树中至少有一个结点的度为2，这也可能不成立，例如完全由度为1的节点组成的二叉树。 - D选项声称二叉树中每一个结点的度都为2，这是不正确的，因为二叉树允许节点的度为0、1或2。 **4. 二叉树的结点总数** - **选项分析**： - 此题考查二叉树的性质。根据满二叉树的性质，如果有40个叶结点，则该二叉树至少是一个完全二叉树。对于完全二叉树，叶结点的数量和总结点数之间有一定的关系。最小的二叉树是完全二叉树，此时总共有40个叶结点，根据完全二叉树的性质，叶结点数为\(n\)时，总的结点数至少为\(2n-1\)，因此总结点数最少为\(2*40-1=79\)。 **5. 有向图的拓扑序列** - **选项分析**： - 如果邻接矩阵主对角线以下元素均为0，说明图中所有边的方向是从较小编号的顶点指向较大编号的顶点，这样的图可能存在一个拓扑序列，但不一定是唯一的。 **6. AOE网的定义** - **选项分析**： - AOE网是一种特殊的有向图，用于表示工程项目的活动网络图，其中每个节点代表一个事件，每条边代表一项活动，并带有完成活动所需的持续时间。选项A、D描述了AOE网的基本特征，即它是一个带权的无回路的有向图。 **7. 线性表查找方法** - **选项分析**： - 对于顺序查找，如果表中有重复元素，查找方法可以找到表中首次出现的元素；而对于折半查找，由于其是基于有序表的查找方法，如果查找元素在中间位置重复多次，折半查找可能会返回不同的索引值，因此不一定能找到首次出现的元素。 **8. 二叉排序树的查找时间** - **选项分析**： - 在二叉排序树中进行查找的平均时间效率主要与树的高度有关，而高度又与树的形态（即深度）紧密相关。 **9. 排序方法的性质** - **选项分析**： - 插入排序、快速排序、堆排序在每一趟排序结束时都会确定一个元素的最终位置，而二路归并排序在每次合并过程中并不会直接确定任何元素的最终位置。 **10. 特殊情况下的排序效率** - **选项分析**： - 当待排序的序列已经是有序的时，快速排序的效率会降低，因为在这种情况下，每次划分都将序列分为极不平衡的两部分，导致时间复杂度退化至O(n^2)。 #### 简答题解析 **1. 顺序表插入和删除的移动次数** - 在等概率的情况下，对于长度为n的顺序表，插入一个数据元素时平均需要移动(n+1)/2个元素，删除一个数据元素时平均需要移动n/2个元素。移动的元素个数主要取决于顺序表当前的长度以及操作的具体位置。 **2. 循环单链表作为队列存储结构的指针设置** - 从操作的时间效率考虑，只设置一个队尾指针更合适。这是因为插入操作只需要修改队尾指针，而删除操作则需要遍历链表找到队头元素并释放它，因此队头指针的存在不会提高效率。 **3. 邻接矩阵和邻接表的空间性能** - 对于稀疏图，采用邻接表存储更节省空间，因为邻接矩阵会有很多0元素，而邻接表只需存储实际存在的边。对于稠密图，采用邻接矩阵存储更合适，因为此时邻接矩阵的利用率较高。 **4. 小顶堆的概念和最大元素位置** - 小顶堆是一种特殊的完全二叉树，其中每个节点的值都不大于其子节点的值。在小顶堆中，值最大的元素可能出现在除根节点外的任何位置。 #### 综合题解析 **1. 删除顺序表中的重复元素** - 算法的目的是删除重复的元素，保持每个元素只出现一次。在空白处应填写适当的代码来实现这一功能。 - 第一个空白处应填写`k=j+1`，确保从当前节点的下一个位置开始移动。 - 第二个空白处应填写`j++`，以检查下一个元素是否重复。 - 第三个空白处应填写`else j++`，表示如果没有重复元素，则继续检查下一个元素。 **2. 树转换为二叉树** - 给定的树转换为二叉树时，每个非叶子节点的左子树为其第一个孩子，右子树为其兄弟节点。 **3. B-树插入关键字后的变化** - 插入关键字20后，B-树需要根据其插入规则进行调整，以保持B-树的性质。 **4. Shell排序过程** - Shell排序通过不断缩小间隔的方式对序列进行排序。以间隔数为4、2、1为例，展示排序过程中的每一趟结果。 #### 算法设计题解析 **哈夫曼树的带权路径长度计算** - 算法的基本思想是通过遍历哈夫曼树，累加每个叶节点的权重乘以其到根节点的距离，从而得到整个哈夫曼树的带权路径长度。 - 具体实现时，可以通过非递归的方式遍历树，并维护一个计数器来记录当前节点到根节点的距离。 - 需要注意的是，哈夫曼树的构造保证了距离较远的节点具有较小的权重，因此带权路径长度能够反映最优的编码方案。