2014广工数据结构期末考试难题解析与关键知识点总结

这是一份2014年广东工业大学数据结构期末考试试卷B，涵盖了数据结构的基础概念和理论测试。考试包含多项选择题，主要考察学生对数据结构核心概念的理解和应用。 1. 算法定义：算法是指解决问题的有限运算序列，它不仅包括计算机程序，也涉及数学上的逻辑步骤，用于指导如何解决特定问题。 2. 线性表存储：线性表采用链式存储时，结点的存储地址不一定连续，可以选择连续或不连续，关键在于如何组织和管理节点间的链接。 3. 无向连通图的最小生成树：在一个无向连通图中，最小生成树是指连接所有顶点的边数最少的树形结构，通常存在唯一一棵这样的树。 4. 筛选法与堆的构建：筛选法（如堆排序）是从大根堆或小根堆的角度，所以对于构建堆，起点通常是最后一个非叶子节点，即关键字值最大的或最小的节点。 5. 循环队列的队头指针：在执行出队操作后，队头指针会向前移动一位，但需要考虑队列的边界，因此通常取模操作（front=(front+1)%m）以保持指针在合法范围内。 6. 串和线性表的区别：串是一种特殊的线性表，但并不意味着串的长度必须大于零，空串是表示没有字符的串，与空白串不同。 7. 广义表的表头：广义表可以包含原子（单个元素）或子表，表头可以是原子也可以是子表。 8. 图和排序的关系：哈希表是一种高效的数据结构，用于查找和存储，而非排序；图的拓扑排序根据边的方向进行排序，不一定遵循弧头在弧尾之前的顺序；广度优先搜索是非递归的；树是图的特殊形式，具有树状结构。 9. 连通图的边数：对于n个顶点的连通图，至少需要n-1条边，确保所有顶点之间都可通过路径相连。 10. 排序方法判断：通过观察序列的变化过程，由开始的乱序逐渐变为有序，这种稳定的排序方法是插入排序（希尔排序），因为它在每次迭代中都会将未排序的部分插入到已排序部分的适当位置。 这份试卷全面地检验了学生的数据结构基础知识，从基本概念到实际操作技巧，涵盖了线性表、树、图、队列等数据结构的重要知识点。