穿越四合院我成了一大爷最新章节_第223章第1页_穿越四合院我成了一大爷九思微微

AC小说网>穿越四合院我成了一大爷 > 第223章（第1页）

答案：b

对称矩阵压缩存储原理及计算思路

对于对称矩阵，我们只需要存储其下三角（或上三角）部分的元素即可，因为对称矩阵中处于对称位置的元素值是相等的。

在以行序为主存储下三角部分元素时，第行（从开始计数）之前（包括第行）的元素个数可以通过等差数列求和公式来计算，然后再根据要查找的元素在当前行的位置来确定其在压缩存储中的相对位置，进而得出存储地址。

具体计算过程

1.计算前行元素的总数：

对于下三角矩阵，第行有个元素（从开始），计算前行元素个数之和，根据等差数列求和公式（这里）可得：

2.确定在第行的位置及相对地址：

因为是对称矩阵，我们只考虑下三角部分，处于第行第列，在存储下三角元素时，第行存储的元素是从到，那么是第个元素（从左往右数）。

3.计算的存储地址：

前面已经算出前行一共有个元素，再加上第行的个元素（在第行是第个元素），可得的相对地址为，又已知首元素的存储地址为，且每个元素占个地址空间，所以的存储地址就是。

综上，选择b选项。

答案：c

1.快速排序

-时间复杂度：平均时间复杂度是，但最坏情况时间复杂度是。

-稳定性：快速排序是不稳定的排序算法。例如，序列，如果以第一个作为基准进行划分，可能会将两个的相对顺序改变，所以A选项不符合要求。

2.堆排序

-时间复杂度：时间复杂度为。

-稳定性：堆排序是不稳定的排序算法。在堆调整过程中，可能会改变相同元素的相对顺序，例如，在构建堆和调整堆的过程中，相同键值的元素顺序可能会被打乱，所以b选项不符合。

3.归并排序

-时间复杂度：时间复杂度始终为。

-稳定性：归并排序是稳定的排序算法。在合并两个有序子序列时，如果两个子序列中有相同的元素，按照顺序将左边子序列中的元素先放入合并后的序列，从而保证了相同元素的相对顺序不变，符合题目要求，c选项正确。

4.直接插入排序

-时间复杂度：时间复杂度为，在最好情况下（序列已经有序）时间复杂度为，但不满足在时间内完成排序的要求，所以d选项不合适。

答案：c

栈的特点及输出序列可能性分析

栈是一种后进先出（LastInFirstout，LIFo）的数据结构，元素进栈和出栈的顺序遵循这个特点。

我们可以通过模拟栈的操作过程来分析各个选项是否可行：

选项A

输入序列为a，b，c，d，e，如果按照进栈一个元素就马上出栈一个元素的操作方式，就可以得到输出序列为a，b，c，d，e，是完全可行的，符合栈的操作规则。

选项b

可以先将a，b，c，d依次进栈，此时栈内元素从栈底到栈顶依次为a，b，c，d，然后依次出栈得到d，c，b，a，接着将e进栈再出栈，最终输出序列就是d，e，c，b，a，这种操作符合栈的后进先出特点，是可行的。

选项c

若要输出d，则需要先将a，b，c，d依次进栈，然后d出栈；接着若要输出c，此时栈内剩下a，b，c，c出栈符合规则；再要输出e，但是e还未进栈，必须先将e进栈才能输出，而按照这个输出序列此时要输出a了，也就是在e还没进栈操作之前就输出了其他元素，不符合栈后进先出的原则，所以该输出序列是不可能实现的。

选项d

可以先将a，b，c，d，e全部依次进栈，此时栈内元素从栈底到栈顶依次为a，b，c，d，e，然后再依次出栈，就能得到输出序列e，d，c，b，a，是符合栈操作规则的。

综上，选择c选项，它是栈的不可能输出的序列。

请勿开启浏览器阅读模式，否则将导致章节内容缺失及无法阅读下一章。