答案：b
对称矩阵压缩存储原理及计算思路
对于对称矩阵，我们只需要存储其下三角（或上三角）部分的元素即可，因为对称矩阵中处于对称位置的元素值是相等的。
在以行序为主存储下三角部分元素时，第
行（
从
开始计数）之前（包括第
行）的元素个数可以通过等差数列求和公式来计算，然后再根据要查找的元素在当前行的位置来确定其在压缩存储中的相对位置，进而得出存储地址。
具体计算过程
1.
计算前
行元素的总数：
对于下三角矩阵，第
行有
个元素（
从
开始），计算前
行元素个数之和，根据等差数列求和公式
（这里
）可得：
2.
确定
在第
行的位置及相对地址：
因为是对称矩阵，我们只考虑下三角部分，
处于第
行第
列，在存储下三角元素时，第
行存储的元素是从
到
，那么
是第
个元素（从左往右数）。
3.
计算
的存储地址：
前面已经算出前
行一共有
个元素，再加上第
行的
个元素（
在第
行是第
个元素），可得
的相对地址为
，又已知首元素
的存储地址为
，且每个元素占
个地址空间，所以
的存储地址就是
。
综上，选择b选项。
答案：c
1.
快速排序
-
时间复杂度：平均时间复杂度是
，但最坏情况时间复杂度是
。
-
稳定性：快速排序是不稳定的排序算法。
例如，序列
，如果以第一个
作为基准进行划分，可能会将两个
的相对顺序改变，所以a选项不符合要求。
2.
堆排序
-
时间复杂度：时间复杂度为
。
-
稳定性：堆排序是不稳定的排序算法。
在堆调整过程中，可能会改变相同元素的相对顺序，例如，在构建堆和调整堆的过程中，相同键值的元素顺序可能会被打乱，所以b选项不符合。
3.
归并排序
-
时间复杂度：时间复杂度始终为
。
-
稳定性：归并排序是稳定的排序算法。
在合并两个有序子序列时，如果两个子序列中有相同的元素，按照顺序将左边子序列中的元素先放入合并后的序列，从而保证了相同元素的相对顺序不变，符合题目要求，c选项正确。
4.
直接插入排序
-
时间复杂度：时间复杂度为
，在最好情况下（序列已经有序）时间复杂度为
，但不满足在
时间内完成排序的
要求，所以d选项不合适。
答案：c
栈的特点及输出序列可能性分析
栈是一种后进先出（last
in
first
out，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选项，它是栈的不可能输出的序列。
本章未完，点击下一页继续阅读