云南大学2019计算机专业复试题

### 云南大学2019计算机专业复试题分析 #### 数据结构相关知识点 根据提供的信息，我们可以总结出以下几个重要的知识点： ##### 1. **顺序表的逆置** - **定义**：顺序表是由一组地址连续的存储单元组成的线性表，其中的数据元素按照一定的逻辑顺序排列。 - **逆置方法**：对于一个顺序表，可以通过循环遍历表的一半，将第一个元素和最后一个元素交换位置，然后依次向前移动，直至完成整个表的逆置。具体步骤如下： - 设置两个索引变量`i`和`j`，其中`i`从0开始，`j`从顺序表长度`n-1`开始。 - 在循环过程中，交换`i`和`j`所指向的元素。 - 每次循环后，`i`加1，`j`减1，直至`i >= j`。 ##### 2. **链表的逆置** - **定义**：链表是一种通过节点之间的链接关系构成的数据结构，每个节点包含数据和指向下一个节点的指针。 - **逆置方法**： - 初始化三个指针：`prev`、`current` 和 `next`，分别表示前一个节点、当前节点和下一个节点。 - 将`current`初始化为链表的头结点，`prev`设置为`NULL`。 - 遍历链表，每次循环时，将`next`设置为`current`的下一个节点；然后更新`current`的指针，使其指向`prev`；最后将`prev`和`current`向前移动。 - 当遍历完整个链表后，原头结点变为尾节点，原尾节点变为头结点。 ##### 3. **排序** - **顺序表排序**：常用的排序方法包括2路归并排序、堆排序、冒泡排序和插入排序等。其中，折半插入排序是在插入排序的基础上进行优化，减少关键字比较次数。 - **链表排序**：可以直接采用直接插入排序的方法，构建一个有序的单链表，然后将源链表中的节点逐个插入到有序链表中。 ##### 4. **合并有序链表或顺序表** - **合并有序链表**：遍历两个有序链表，将较小的节点插入到结果链表中。如果一个链表遍历完毕，则将另一个链表的剩余部分直接添加到结果链表的末尾。 - **合并有序顺序表**：类似地，遍历两个有序顺序表，比较并选择较小的元素添加到结果顺序表中，直到一个表遍历完毕，再将另一个表的剩余部分加入到结果表中。 ##### 5. **数据结构三要素** - **逻辑结构**：指数据元素之间的逻辑关系，不受存储方式的影响。 - **物理结构**：即存储结构，是指数据元素在计算机存储器中的存储方式。 - **数据的运算**：包括基本操作如插入、删除、查找等。 ##### 6. **特殊数据结构** - **广义表**：一种特殊的数据结构，其中元素可以是子表，子表的元素还可以是广义表，通常采用链式存储结构。 - **数组**：顺序存储的数据结构，具有固定的大小。 - **链表**：动态存储的数据结构，可以通过顺序或链式的方式存储。 ##### 7. **堆、栈、队列** - **栈**：只允许在一端进行插入和删除操作的线性表，遵循“后进先出”(LIFO)原则。 - **队列**：允许在一端插入、另一端删除的线性表，遵循“先进先出”(FIFO)原则。 - **堆**：完全二叉树结构，分为大根堆和小根堆。大根堆中父节点的值总是大于或等于子节点的值；小根堆反之。 ##### 8. **堆排序** - **原理**：首先构建一个大根堆，然后不断移除堆顶元素（最大元素）放到数组末尾，并重新调整堆，直至所有元素都被移除并正确排序。 - **步骤**： 1. 构造初始堆。 2. 输出堆顶元素，并用堆底元素填补堆顶位置。 3. 调整堆以恢复堆性质。 4. 重复步骤2和3，直至堆仅剩一个元素。 以上内容是针对云南大学2019年计算机专业复试中涉及的部分数据结构相关知识点的总结，旨在帮助考生更好地复习和准备考试。