数据结构(本)期末综合练习(6月)(2).doc

数据结构期末综合练习 数据结构是计算机科学中的一门基础学科，涉及到数据的存储、组织和操作。以下是本期末综合练习的知识点总结： 一、树结构 1. 深度为 5 的完全二叉树共有 20 个结点，则第 5 层上有 3 个结点。 二、逻辑结构和存储结构 2. 同一种逻辑结构可以有不同的存储结构。 三、图结构 3. 已知一个图的边数为 m，则该图的所有顶点的度数之和为 2m。 四、链表结构 4. 链表所具备的特点是插入删除元素的操作不需要移动元素结点。 五、数据结构的分类 5. 数据结构中，与所使用的计算机无关的是数据的逻辑结构。 六、物理结构 6. 数据的物理结构包括数据元素的表示和关系的表示。 七、链表结构 7. 链表所具备的特点是插入删除元素的操作不需要移动元素结点。 八、线性结构 8. 线性结构中数据元素的位置之间存在一对一的关系。 九、查找算法 9. 线性表只要以顺序方式存储就能进行折半查找。 十、链表结构 10. 顺序表能够随机访问。 十一、散列查找 11. 散列查找的原理是在待查记录的关键字值与该记录的存储位置之间建立确定的对应关系。 十二、算法时间复杂度 12. 算法的时间复杂度与算法本身有关。 十三、排序算法 13. 对 n 个元素进行冒泡排序若某趟冒泡中只进行了 0 次元素间的交换，则表明序列已经排好序。 十四、排序算法 14. 设有一个长度为 n 的顺序表，要删除第 i 个元素需移动元素的个数为 n-i。 十五、排序算法 15. 排序过程中，每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序列的适当位置，直到全部排好序为止，该排序算法是直接插入排序。 十六、链表结构 16. 在一个单链表中，p、q 分别指向表中两个相邻的结点，且 q 所指结点是 p 所指结点的直接后继，现在要删除 q 所指结点，可用的语句是 p->next=q->next。 十七、排序算法 17. 在对一组元素进行直接插入排序时，当进行到要把第 7 个元素 70 插入到已经排好序的子表时，为找到插入位置，需进行 2 次元素间的比较。