南宁师范大学818计算机基础2017-2019年试题答案.docx

简介：
该文档包含南宁师范大学在2017年至2019年间《计算机基础》课程考试的试题及详细解答，适合备考学生参考学习。 ### 快速排序基本思想 快速排序是基于冒泡排序改进的一种算法。其核心在于选取一个基准元素（通常为第一个元素），将该元素放置在适当位置后，数据序列会被分成两部分：所有关键字比基准小的元素位于前一部分，而所有的关键子大于基准的则置于后一部分，并且把选定的这个基准放在这两个分区中间的位置。这一过程称为一次快速排序或一趟划分。 接下来对生成的这两个分区分别重复上述步骤，直到每个区段内只剩下一个元素或者为空为止。快速排序算法在最坏情况下的时间复杂度为O(n²)，而在最好和平均情况下均为O(nlog2n)；它的空间复杂度是O(log2n), 并且该排序方法不保证稳定性。 ### 简单选择排序思想 假设待排元素存储于数组R[0...n-1]中，在整个过程中，此数组被划分为两个子区间：有序区（初始为空）和无序区。简单选择排序的每次操作是从当前无序区间内选取关键字最小的元素并将其与该分区的第一个位置交换，这样就形成了新的有序区域R[0...i]。重复这一过程直至所有元素均完成排序。 以上是关于快速排序以及简单选择排序的基本概念和思想概述。