2014广工数据结构期末考试试卷(B)

### 数据结构知识点解析 #### 一、单项选择题解析 1. **算法的定义** - **选项解析**： - A项：算法不是简单的计算机程序，它是一系列解决问题的步骤集合。 - B项：算法不仅仅是计算方法，还包括一系列逻辑步骤。 - C项：排序算法只是算法的一种类型，并非所有算法都是排序算法。 - D项：算法是由一系列有限的操作步骤组成的，用于解决特定问题的方法。 - **正确答案**：D。算法是指解决特定问题的有限步骤序列。 2. **线性表链式存储** - **选项解析**： - A项：线性表采用链式存储时，结点的存储地址不一定非得不连续。 - B项：链式存储时，结点的存储地址可以是连续的也可以是不连续的，取决于具体的实现方式。 - C项：线性表采用链式存储时，结点的存储地址并不一定必须是连续的。 - D项：链式存储与头结点的存储地址是否连续没有直接关系。 - **正确答案**：B。线性表采用链式存储时，结点的存储地址可以是连续的也可以是不连续的。 3. **无向连通图的最小生成树** - **选项解析**： - A项：一个无向连通图的最小生成树可能不止一棵。 - B项：一个无向连通图可能有多棵不同的最小生成树，也可能只有一棵。 - C项：一个无向连通图不可能一定有两棵以上的最小生成树。 - D项：如果图是连通的，那么至少存在一棵最小生成树。 - **正确答案**：B。任何一个无向连通图可能有一棵或多棵最小生成树。 4. **筛选法建堆** - **选项解析**：使用筛选法建堆时，通常从最后一个非叶子节点开始调整，以确保每次调整后都能保持堆的性质。 - **正确答案**：B。对于给定的关键字值序列，需要从关键字值为101的结点开始。 5. **循环队列的出队操作** - **选项解析**：在循环队列中，出队操作后队头指针需要向前移动一位，但考虑到队列的循环特性，需要使用取模运算来处理队头指针。 - **正确答案**：D。front=(front+1)%m。 6. **串的概念** - **选项解析**： - A项：串确实是一种特殊的线性表，由字符构成。 - B项：串的长度可以为零，即空串。 - C项：串中的元素不仅可以是字母，还可以是数字或其他符号。 - D项：空串并不是空白串，两者是有区别的。 - **正确答案**：A。串是一种特殊的线性表。 7. **广义表的表头** - **选项解析**： - A项：广义表的表头可以是子表。 - B项：广义表的表头可以是子表，也可以是原子。 - C项：广义表的表头可以是原子。 - D项：广义表的表头可以是子表或原子。 - **正确答案**：D。一个非空广义表的表头可以是子表或原子。 8. **哈希表及其他概念** - **选项解析**： - A项：哈希表不是用来解决排序问题的，而是用来快速查找的。 - B项：拓扑排序中，弧头结点总是出现在弧尾结点之后。 - C项：图的广度优先搜索算法中并没有采用递归。 - D项：树确实是图的一种特殊形式。 - **正确答案**：D。树是图的一种特殊形式。 9. **连通图的边数** - **选项解析**：n个顶点的连通图至少有n-1条边。 - **正确答案**：A。n-1。 10. **排序方法的识别** - **选项解析**：根据排序过程中序列的变化情况，可以看出采用的是快速排序的方法。 - **正确答案**：C。快速排序。 11. **二叉树的高度与结点数关系** - **选项解析**：高度为h的二叉树的结点最多数量可以通过公式2^(h+1)-1计算得出。 - **正确答案**：C。2^(h+1)-1。 12. **二叉树后序遍历** - **选项解析**：通过观察给定的二叉树结构，可以确定后序遍历的顺序为4526731。 - **正确答案**：C。4526731。 13. **哈夫曼树的带权路径长度** - **选项解析**：哈夫曼树的带权路径长度WPL等于各个叶子结点的带权路径长度之和。 - **正确答案**：C。各叶子结点的带权路径长度之和。 14. **栈的输出序列** - **选项解析**：栈是后进先出的数据结构，因此有些序列无法通过栈得到。 - **正确答案**：B。4,1,3,2,5。 15. **拓扑排序** - **选项解析**：拓扑排序是基于有向无环图的排序，某些序列无法通过拓扑排序得到。 - **正确答案**：B。1,5,2,6,3,7,4,8。 #### 二、填空题解析 16. **单链表删除操作** - **解析**：删除指针P所指结点的后继结点的最后一步是释放被删除结点的空间。 - **正确答案**：free(u)。 17. **单循环链表的头部指针** - **解析**：在单循环链表中，尾结点的下一个结点即是头结点。 - **正确答案**：p->next。 18. **栈顶位置的变化** - **解析**：栈顶的位置会随着压栈和出栈操作而发生变化。 - **正确答案**：压栈/出栈。 19. **二叉链表的空链域数量** - **解析**：在二叉链表中，每个结点有两个链域，对于n个结点来说，总共有2n个链域，其中n个用于连接，剩下的n个为空。 - **正确答案**：n。 20. **有向完全图的边数** - **解析**：有向完全图中，每个顶点与其他所有顶点都有两条边相连，因此边数为n*(n-1)。 - **正确答案**：n*(n-1)。 21. **完全二叉树的叶子结点数** - **解析**：完全二叉树的叶子结点数与总的结点数之间有一定的关系，可以通过公式计算得出。 - **正确答案**：384。 22. **完全二叉树的左孩子结点编号** - **解析**：在完全二叉树中，编号为i的结点的左孩子结点的编号为2*i。 - **正确答案**：2*i。 23. **关键活动的定义** - **解析**：关键活动是指活动最早开始时间和最迟开始时间相同的活动。 - **正确答案**：e(i)=l(i)。 24. **折半查找的关键字比较次数** - **解析**：有序表中折半查找关键字72，由于表是有序的，可以直接找到中间位置的元素进行比较。 - **正确答案**：1次。 25. **队列的插入端** - **解析**：队列遵循先进先出的原则，插入操作在一端进行。 - **正确答案**：队尾。 #### 三、解答题解析 26. **事件结点网络分析** - **解析**：在事件结点网络中，需要分析各个事件之间的依赖关系以及关键路径，以确定整个项目的完成时间等信息。 - **具体分析**：由于题目提供的部分内容并未给出具体的事件结点网络图，这里无法给出具体的分析结果。但是，一般情况下，需要找出所有的关键路径，确定项目完成的最短时间，并分析哪些任务是关键任务，哪些任务存在一定的松弛时间。