云南大学软件学院数据结构期末考试试题

"云南大学2010至2011学年上学期软件学院2009级《数据结构》期末考试（闭卷）试卷A，由柳青和张德海任课教师" 本试卷主要考察了数据结构的基础概念与核心算法，包括顺序表、稀疏矩阵、链表操作、时间复杂度分析、二叉树性质、模式匹配、快速排序、邻接矩阵以及排序算法等知识点。 1. **顺序表**：在顺序表中删除第i个元素时，需要移动n-i+1个元素。这是因为要将第i个元素之后的所有元素都向前移动一位来填补被删除元素留下的空位。 2. **稀疏矩阵**：稀疏矩阵的三元组存储方式通常包括三列，分别存储非零元素的行下标、列下标和值。这种存储方式节省空间，适用于大部分元素为零的大矩阵。 3. **链表操作**：在单链表中插入一个节点S到P节点之后，需要执行S->next=p->next和P->next=s，这样可以确保新节点正确插入且链表的连续性不受影响。 4. **链表合并**：将长度为n的单链表连接到长度为m的单链表之后，算法的时间复杂度是O(m)，因为只需要遍历一次较短的链表即可完成连接。 5. **二叉树性质**：在二叉树中，如果度为2的节点数为5个，度为1的节点数为6个，根据霍夫曼(Huffman)定理，叶子节点数为6个。 6. **模式匹配**：当目标串长度为n，模式串长度为[n/3]时，最坏情况下KMP算法的时间复杂度是O(n^2)，这里可能指的是朴素匹配算法的情况。 7. **快速排序**：对数组{46, 79, 56, 25, 76, 38, 40, 80}进行快速排序，第一次划分后，基准元素46将数组分为两部分，右区间元素个数为3，即{40, 38, 25}。 8. **邻接矩阵**：在图的邻接矩阵表示中，对于无向图，每个节点的度是其邻接矩阵对应行和列之和的一半；对于有向图，每个节点的度是其出度加上入度。 9. **选择题**：涉及了邻接矩阵对称性、平衡二叉排序树的平衡因子范围、希尔排序的趟序结果、完全二叉树的双亲节点编号、B树的关键码数量、搜索算法适用的存储结构、折半搜索的平均搜索长度等。 这些题目覆盖了数据结构课程中的基本概念和理论，旨在检验学生对这些基础知识的理解和应用能力。解答这些题目需要对数据结构的基本原理有深入理解，并能够灵活运用。