408 真题做题本·数据结构部分

第 3 章 栈、队列和数组

3.1 栈

1. 【2009】设栈S 和队列Q 的初始状态均为空, 元素a、b、c、d、e、f 、g 依次进入栈S。若每个元素出栈后立即进入队列Q, 且7 个元素出队的顺序是b、d、c、f 、e、a、g，则栈S 的容量至少是（ ）。

A. 1
B. 2
C. 3
D. 4

答案： C

解析： 队列按先进先出方式工作，因此元素从队列Q中出队的顺序，就是它们从栈S中出栈并进入队列的顺序。按目标出栈序列模拟，栈中元素按“栈底到栈顶”表示：

• 依次将a、b入栈，弹出b，此时栈为 $[a]$，栈中最多有2个元素；
• 将c、d入栈，弹出d、c。弹出d前栈为 $[a,c,d]$，栈中有3个元素；
• 将e、f入栈，弹出f、e、a。弹出f前栈为 $[a,e,f]$，栈中有3个元素；
• 最后将g入栈并弹出。

整个过程中栈内元素个数的最大值为3，因此栈S的容量至少为3。

2. 【2010】若元素a,b,c,d,e,f 依次进栈, 允许进栈、退栈操作交替进行, 但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（ ）。

A. dcebfa
B. cbdaef
C. bcaefd
D. afedcb

答案： D

解析： 逐项判断：

• A项可按“a、b、c、d入栈，弹出d、c；e入栈，弹出e、b；f入栈，弹出f、a”实现，任意时刻均不超过连续两次出栈；
• B项可按“a、b、c入栈，弹出c、b；d入栈，弹出d、a；e入栈并弹出；f入栈并弹出”实现；
• C项可按“a、b入栈，弹出b；c入栈，弹出c、a；d、e入栈，弹出e；f入栈，弹出f、d”实现；
• D项要求a首先出栈，因此a入栈后必须立即出栈。随后为了使f第二个出栈，必须将b、c、d、e、f全部入栈。此时输入元素已经全部入栈，接下来只能连续弹出f、e、d、c、b，共连续5次出栈，违反“不允许连续三次退栈”的限制。

故不可能得到的出栈序列是afedcb。

3. 【2011】元素a,b,c,d,e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈, 直到所有元素都出栈，则在所有可能的出栈序列中, 以元素d 开头的序列个数是（ ）。

A. 3
B. 4
C. 5
D. 6

答案： B

解析： 要使d第一个出栈，必须先将a、b、c、d依次入栈，再弹出d。此时栈中从栈底到栈顶为 $[a,b,c]$，元素e尚未入栈。

后续操作只有以下4种可能：

1. 依次弹出c、b、a，再将e入栈并弹出，得到d、c、b、a、e；
2. 弹出c、b，再将e入栈并弹出，最后弹出a，得到d、c、b、e、a；
3. 弹出c，再将e入栈并弹出，最后弹出b、a，得到d、c、e、b、a；
4. 将e入栈并弹出，再弹出c、b、a，得到d、e、c、b、a。

因此，以d开头的出栈序列共有4个。

4. 【2013】一个栈的入栈序列为 $1,2,3,\cdots ,n$， 其出栈序列是 $p_1,p_2,p_3,\cdots ,p_n$。若 $p_2=3$，则 $p_3$ 可能取值的个数是（ ）。

A. n - 3
B. n - 2
C. n - 1
D. 无法确定

答案： C

解析： 由于 $p_2=3$，元素3已经在第二个位置出栈，所以 $p_3$ 不可能再取3。下面说明除3以外的每个元素都可能成为 $p_3$：

• $p_3=1$：可先将1、2入栈并弹出2，再将3入栈并弹出3，随后弹出1，出栈序列前3项为 $2,3,1$；
• $p_3=2$：可将1入栈并弹出，再将2、3入栈，依次弹出3、2，前3项为 $1,3,2$；
• 对任意 $k\in \{4,5,\cdots ,n\}$，可先将1入栈并弹出，再将2、3入栈并弹出3，然后继续将4至k依次入栈并弹出k，前3项为 $1,3,k$。

因此，$p_3$ 可以取集合

$\{1,2,4,5,\cdots ,n\}$

中的任意值，共有 $n-1$ 个可能值。

5. 【2017】下列关于栈的叙述中,错误的是（ ）。 I. 采用非递归方式重写递归程序时必须使用栈 II. 函数调用时,系统要用栈保存必要的信息 III. 只要确定了入栈次序, 就可确定出栈次序 IV. 栈是一种受限的线性表,允许在其两端进行操作

A. 仅I
B. 仅I、II、III
C. 仅I、III、IV
D. 仅II、III、IV

答案： C

解析：

• I错误。递归程序改写为非递归程序时，经常需要用栈模拟递归调用过程，但并非所有递归程序都必须显式使用栈。例如尾递归或某些具有简单递推关系的程序可以直接改写为循环；
• II正确。函数调用时，系统通常使用运行栈保存返回地址、实参或局部变量等调用现场信息；
• III错误。入栈次序确定后，进栈与出栈操作可以有多种交替方式，因此可能产生多种不同的出栈序列；
• IV错误。栈只允许在同一端进行插入和删除操作，该端称为栈顶，并非允许在两端操作。

故错误的是I、III、IV。

6. 【2018】若栈S1中保存整数, 栈S2中保存运算符, 函数F（ ） 依次执行下述各步操作: (1) 从S1中依次弹出两个操作数a 和b； (2) 从S2中弹出一个运算符op； (3) 执行相应的运算 b op a； (4) 将运算结果压入S1中。假定S1中的操作数依次是5,8,3,2(2 在栈顶), S2中的运算符依次是*, -, + (+ 在栈顶)。调用3 次F（ ） 后, S1栈顶保存的值是（ ）。

A. - 15
B. 15
C. - 20
D. 20

答案： B

解析： 栈S1从栈底到栈顶为 $[5,8,3,2]$，栈S2从栈底到栈顶为 $[\ast ,-,+]$。

第一次调用F()：

• 弹出 $a=2$、$b=3$，弹出运算符“+”；
• 计算 $b+a=3+2=5$；
• 将5压入S1，此时S1为 $[5,8,5]$。

第二次调用F()：

• 弹出 $a=5$、$b=8$，弹出运算符“-”；
• 计算 $b-a=8-5=3$；
• 将3压入S1，此时S1为 $[5,3]$。

第三次调用F()：

• 弹出 $a=3$、$b=5$，弹出运算符“*”；
• 计算 $b\times a=5\times 3=15$。

因此，最终S1栈顶保存的值为15。

7. 【2020】对空栈S 进行Push 和Pop 操作, 入栈序列a,b,c,d,e, 经过Push, Push, Pop, Push, Pop,Push, Push, Pop 操作后,得到的出栈序列是（ ）。

A. b,a,c
B. b,a,e
C. b,c,a
D. b,c,e

答案： D

解析： 按给定操作依次执行：

1. Push(a)，栈为 $[a]$；
2. Push(b)，栈为 $[a,b]$；
3. Pop()，弹出b；
4. Push(c)，栈为 $[a,c]$；
5. Pop()，弹出c；
6. Push(d)，栈为 $[a,d]$；
7. Push(e)，栈为 $[a,d,e]$；
8. Pop()，弹出e。

因此，得到的出栈序列为b、c、e。

8. 【2022】给定有限符号集S, in 和out 均为S 中所有元素的任意排列。对于初始为空的栈ST, 下列叙述中, 正确的是（ ）。

A. 若in 是ST 的入栈序列，则不能判断out 是否为其可能的出栈序列
B. 若out 是ST 的出栈序列，则不能判断in 是否为其可能的入栈序列
C. 若in 是ST 的入栈序列, out 是对应in 的出栈序列，则in 与out 一定不同
D. 若in 是ST 的入栈序列, out 是对应in 的出栈序列，则in 与out 可能互为倒序

答案： D

解析：

• A错误。给定入栈序列in和候选出栈序列out后，可以利用辅助栈进行模拟，判断out是否为合法出栈序列；
• B错误。同理，给定out和in后也可以判断二者是否能够构成同一栈操作过程中的入栈、出栈序列；
• C错误。每个元素入栈后立即出栈时，出栈序列可以与入栈序列完全相同；
• D正确。将in中的所有元素全部压入栈后再依次弹出，得到的out恰好是in的逆序排列。

3.2 队列

1. 【2010】某队列允许在其两端进行入队操作, 但仅允许在一端进行出队操作。若元素a、b、c、d、e 依次入此队列后再进行出队操作，则不可能得到的出队序列是（ ）。

A. bacde
B. dbace
C. dbcae
D. ecbad

答案： C

解析： 由于元素按a、b、c、d、e的次序入队，而每个元素只能从队列两端之一插入，最后又只能从固定的一端出队，因此可以反向检验候选序列：从最终排列中按e、d、c、b的逆入队次序逐个删除，每次被删除的元素必须位于当前序列的某一端。

• A项bacde：依次删除e、d、c、b时，它们均位于当前序列的一端，可以实现；
• B项dbace：依次删除e、d、c、b时，它们均位于当前序列的一端，可以实现；
• C项dbcae：先删除e、d后，剩余序列为bca，此时c位于中间，无法通过从两端入队形成，故不能实现；
• D项ecbad：依次删除e、d、c、b时，它们均位于当前序列的一端，可以实现。

因此，不可能得到的出队序列是dbcae。

2. 【2011】已知循环队列存储在一维数组 $A[0,\cdots ,n-1]$ 中, 且队列非空时front 和rear 分别指向队头元素和队尾元素。若初始时队列为空, 且要求第1 个进入队列的元素存储在 $A[0]$ 处，则初始时 front 和rear 的值分别是（ ）。

A. 0,0
B. 0,n - 1
C. n - 1,0
D. n - 1,n - 1

答案： B

解析： 题目规定队列非空时，front指向队头元素，rear指向队尾元素。入队时先令

$rear=(rear+1)\mathrm{mod}n$

再将新元素存入 $A[rear]$。

要使第一个入队元素存入 $A[0]$，初始时必须有

$rear=n-1$

这样第一次入队后 $rear=0$。同时，第一个元素入队后应有front指向 $A[0]$，故初始时令 $front=0$。

因此，初始值为 $front=0$，$rear=n-1$。

3. 【2014】循环队列放在一维数组 $A[0,\cdots ,M-1]$ 中, end1 指向队头元素, end2 指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作, 队列中最多能容纳 $M-1$ 个元素。初始时为空。下列判断队空和队满的条件中, 正确的是（ ）。

A. 队空: end1 == end2; 队满: end1 == (end2 + 1) mod M;
B. 队空: end1 == end2; 队满: end2 == (end1 + 1) mod M;
C. 队空: end2 == (end1 + 1) mod M; 队满: end1 == (end2 + 1) mod M;
D. 队空: end1 == (end2 + 1) mod M; 队满: end2 == (end1 + 1) mod M;

答案： A

解析： end1指向队头元素，end2指向队尾元素的后一个位置。

• 队列为空时，队头位置与队尾后继位置重合，故队空条件为

$end1=end2$；

• 为区分队空与队满，循环队列牺牲一个存储单元，最多存放 $M-1$ 个元素。队满时，end2的下一个位置就是end1，即

$(end2+1)\mathrm{mod}M=end1$。

因此，队空和队满条件分别为

$end1=end2$，$end1=(end2+1)\mathrm{mod}M$。

4. 【2018】现有队列Q 与栈S, 初始时Q 中的元素依次是1、2、3、4、5、6(1 在队头), S 为空。若仅允许下列三种操作: ①出队并输出出队元素；②出队并将出队元素入栈；③出栈并输出出栈元素，则不能得到的输出序列是（ ）。

A. 1、2、5、6、4、3
B. 2、3、4、5、6、1
C. 3、4、5、6、1、2
D. 6、5、4、3、2、1

答案： C

解析： 队列中的元素只能按1、2、3、4、5、6的次序取出。取出的元素可以直接输出，也可以先压入栈，再按后进先出的次序输出。

• A项可实现：1、2直接输出；3、4入栈；5、6直接输出；再依次出栈得到4、3；
• B项可实现：1入栈；2、3、4、5、6直接输出；最后出栈输出1；
• D项可实现：将1至6全部入栈，再依次出栈，得到6、5、4、3、2、1；
• C项要求先输出3、4、5、6，再输出1、2。为了先输出3，元素1、2都必须先入栈。此时栈顶为2，因此在输出完3、4、5、6后，只能先输出2再输出1，不可能输出1、2。

故不能得到的输出序列是3、4、5、6、1、2。

5. 【2021】已知初始为空的队列Q 的一端仅能进行入队操作, 另外一端既能进行入队操作又能进行出队操作，若Q 的入队序列是1、2、3、4、5 则不能得到的出队序列是（ ）。

A. 5、4、3、1、2
B. 5、3、1、2、4
C. 4、2、1、3、5
D. 4、1、3、2、5

答案： D

解析： 设左端只能入队，右端既能入队又能出队。每个新元素可以从左端或右端入队，但所有元素都只能从右端出队。

前三项均可构造：

• A项：左入1、左入2、右入3、右入4、右入5，再从右端依次出队，可得到5、4、3、1、2；
• B项：左入1、左入2、右入3、左入4、右入5，再从右端依次出队，可得到5、3、1、2、4；
• C项：左入1、右入2、左入3、右入4，依次输出4、2、1、3，再将5入队并输出，可得到4、2、1、3、5。

对于D项，要首先输出4，则在4输出前，1、2、3均已入队。输出4后若接着输出1，则1必须位于右端。此时2、3只能位于1的左侧；输出1后，后续从右端能够首先输出的应是2或3中靠右者，不可能按3、2的顺序同时满足此前的入队约束。因此D项不能实现。

6. 【2019】请设计一个队列, 要求满足: ①初始时队列为空；②入队时, 允许增加队列占用空间；③出队后, 出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；④入队操作和出队操作的时间复杂度始终保持为$O(1)$ 。请回答下列问题: (1) 该队列应该选择链式存储结构, 还是顺序存储结构； (2) 画出队列的初始状态, 并给出判断队空和队满的条件； (3) 画出第一个元素入队后的队列状态； (4) 给出入队操作和出队操作的基本过程。

答案： 选择循环单链表形式的链式存储结构；设置front和rear两个指针，并保留已出队结点以供后续复用。

解析：

（1）存储结构的选择

应选择链式存储结构。顺序存储结构在空间不足时通常需要申请更大的连续空间并搬移已有元素，难以保证扩容操作始终为 $O(1)$；链式结构可以在需要时只申请一个新结点，申请成功后链接操作为 $O(1)$。

可采用循环单链表，并令：

• front指向“最近一次出队的结点”，即当前队头元素的前驱结点；
• rear指向当前队尾元素；
• front与rear之间沿next方向的结点为有效队列元素；
• rear之后到front之间的结点为已分配但当前空闲、可复用的结点。

（2）初始状态、队空与队满条件

初始化时申请一个结点，使其next指向自身，并令front和rear均指向该结点：

Text

          front,rear
              ↓
          ┌────────┐
          │ 结点 q │
          └────┬───┘
               └────────→ q

队空条件为：

$front=rear$。

在当前已经分配的结点中没有空闲结点时，有：

$rear\to next=front$。

该条件可视为“当前存储空间已满”。由于允许继续申请新结点，只要内存申请成功，队列就不存在永久意义上的队满；出现上述条件时申请一个新结点即可扩容。

（3）第一个元素入队后的状态

设第一个入队元素为x。初始时有 $rear\to next=front$，故申请新结点p，将其插入rear与front之间，再令rear指向p：

Text

       front                         rear
         ↓                             ↓
      ┌─────┐      next          ┌─────────┐
      │  q  │ ─────────────────→ │ data=x  │
      └─────┘ ←─────────────────  └─────────┘
                    next

此时队头元素为x，且front仍指向队头元素的前驱结点。

（4）入队与出队的基本过程

设结点类型为：

C++

struct Node {
    ElemType data;
    Node *next;
};

struct Queue {
    Node *front;
    Node *rear;
};

初始化：

C++

void InitQueue(Queue &Q) {
    Node *p = new Node;
    p->next = p;
    Q.front = Q.rear = p;
}

入队：

C++

void EnQueue(Queue &Q, ElemType x) {
    if (Q.rear->next == Q.front) {       // 当前无可复用的空闲结点
        Node *p = new Node;              // 申请一个新结点
        p->next = Q.front;
        Q.rear->next = p;                // 插入rear与front之间
    }
    Q.rear = Q.rear->next;               // 优先使用已有空闲结点
    Q.rear->data = x;
}

出队：

C++

bool DeQueue(Queue &Q, ElemType &x) {
    if (Q.front == Q.rear)               // 队空
        return false;
    Q.front = Q.front->next;
    x = Q.front->data;
    return true;
}

出队时不释放结点，只移动front指针。该结点随后进入空闲区，可被后续入队操作重复使用。只有在当前没有空闲结点时才申请新结点，因此整个队列占用的结点总数只增不减。入队和出队均只进行常数次指针操作，时间复杂度始终为 $O(1)$。

3.3 栈与队列的应用

1. 【2009】为解决计算机主机与打印机之间速度不匹配问题, 通常设置一个打印数据缓冲区, 主机将要输出的数据依次写入该缓冲区, 而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。

A. 栈
B. 队列
C. 树
D. 图

答案： B

解析： 主机按照先后次序将打印任务写入缓冲区，打印机也应优先处理最早进入缓冲区的数据，即遵循“先进先出”原则。队列的逻辑特性正是先进先出，因此应采用队列。

2. 【2012】已知操作符包括‘+’、‘-’、‘*’、‘/’、‘(’和‘)’。将中缀表达式 $a+b-a\ast ((c+d)/e-f)+g$ 转换为等价的后缀表达式 $ab+acd+e/f-\ast -g+$ 时,用栈来存放暂时还不能确定运算次序的操作符,若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（ ）。

A. 5
B. 7
C. 8
D. 11

答案： A

解析： 按中缀表达式转后缀表达式的规则扫描，操作符栈的关键状态如下，栈中元素按“栈底到栈顶”排列：

• 扫描到第一个“+”时：$[+]$；
• 扫描到“*”时：$[-,\ast ]$；
• 扫描到第一个左括号时：$[-,\ast ,(]$；
• 扫描到第二个左括号时：$[-,\ast ,(,(]$；
• 扫描到c后的“+”时：$[-,\ast ,(,(,+]$。

此时栈中共有5个操作符，是转换过程中的最大值。之后遇到右括号或低优先级运算符时，会弹出部分操作符，栈深不会超过5。

3. 【2014】假设栈初始为空, 将中缀表达式 $a/b+(c\ast d-e\ast f)/g$ 转换为等价的后缀表达式的过程中, 当扫描到f 时, 栈中的元素依次是（ ）。

A. +(-
B. +(-
C. /+-
D. /+-*

答案： B

解析： 依次扫描表达式：

1. 扫描a后遇到“/”，将“/”入栈；
2. 扫描b后遇到“+”，由于“/”优先级高，先弹出“/”，再将“+”入栈；
3. 遇到“(”，入栈，此时为 $[+,(]$；
4. 扫描c后遇到“*”，入栈，得到 $[+,(,\ast ]$；
5. 扫描d后遇到“-”，先弹出“*”，再将“-”入栈，得到 $[+,(,-]$；
6. 扫描e后遇到“*”，入栈，得到 $[+,(,-,\ast ]$；
7. 扫描到f时，f是操作数，操作符栈不变。

因此，从栈底到栈顶依次为“+、(、-、”，即+(-。

4. 【2015】已知程序如下,程序运行时使用栈来保存调用过程的信息,自栈底到栈顶保存的信息依次对应的是（ ）。

C++

int s(int n) { return (n <= 0) ? 0 : s(n - 1) + n; }
int main（ ） { cout << s(1); }

A. main（ ） →S 1 →S 0
B. S 0 →S 1 →main（ ）
C. main（ ） →S 0 →S 1
D. S 1 →S 0 →main（ ）

答案： A

解析： main()首先调用s(1)，因此main()的活动记录先入栈；执行s(1)时，由于 $1>0$，继续调用s(0)；s(0)满足终止条件并返回。

递归调用达到最深处时，调用栈从栈底到栈顶依次对应：

$main()\to s(1)\to s(0)$。

5. 【2016】设有如下图所示的火车车轨, 入口到出口之间有n 条轨道, 列车的行进方向均为从左至右, 列车可驶入任意一条轨道。现有编号为1~9 的9 列列车, 驶入的次序依次是8、4、2、5、3、 9、1、6、7。若期望驶出的次序依次为1 ∼9，则n 至少是（ ）。

A. 2
B. 3
C. 4
D. 5

答案： C

解析： 每条轨道中的列车只能从左向右行驶，所以同一轨道上的列车驶出次序与驶入该轨道的次序相同。为了最终按1至9递增驶出，每条轨道中列车编号必须按递增次序排列。

因此，问题等价于：将序列

$8,4,2,5,3,9,1,6,7$

划分为尽可能少的递增子序列。根据序列划分性质，所需递增子序列的最少个数等于原序列最长下降子序列的长度。

原序列存在长度为4的下降子序列，例如

$8,4,2,1$

或

$8,5,3,1$，

故至少需要4条轨道。另一方面，可作如下划分：

• 轨道1：$8,9$；
• 轨道2：$4,5,6,7$；
• 轨道3：$2,3$；
• 轨道4：$1$。

每条轨道内均递增，因此4条轨道足够。故n至少为4。

6. 【2024】与表达式x + y * (z - u)/v 等价的后缀表达式是（ ）。

A. xyzu -* v/ +
B. xyzu - v/ +
C. + x/ * y - zuv
D. + xy/ - zuv

答案： A

解析： 先计算括号内的 $z-u$，其后缀形式为zu-；再计算 $y\ast (z-u)$，得到yzu-*；然后除以v，得到yzu-*v/；最后与x相加，得到

$xyzu-\ast v/+$。

因此选择A。

3.4 数组与压缩存储

1. 【2016】有一个100 阶的三对角矩阵 M， 其元素 $m_{i,j}(1\le i\le 100,1\le j\le 100)$ 按行优先次序压缩存入下标从0 开始的一维数组 N 中。元素 $m_{30,30}$ 在 N 中的下标是（ ）。

A. 86
B. 87
C. 88
D. 89

答案： B

解析： 三对角矩阵只存储满足 $|i-j|\le 1$ 的元素。

• 第1行有2个元素：$m_{1,1},m_{1,2}$；
• 第2行至第29行，每行有3个元素，共有 $28\times 3=84$ 个元素。

因此，第30行之前共存储

$2+84=86$

个元素。第30行按顺序存储 $m_{30,29},m_{30,30},m_{30,31}$，故 $m_{30,30}$ 是第30行的第2个存储元素，其下标为

$86+1=87$。

2. 【2017】适用于压缩存储稀疏矩阵的两种存储结构是（ ）。

A. 三元组表和十字链表
B. 三元组表和邻接矩阵
C. 十字链表和二叉链表
D. 邻接矩阵和十字链表

答案： A

解析： 稀疏矩阵中绝大多数元素为零，压缩存储的核心是只保存非零元素及其位置信息。

• 三元组表用“行号、列号、元素值”表示每个非零元素；
• 十字链表使每个非零元素同时链接在所在行链表和所在列链表中。

二者都是稀疏矩阵的典型压缩存储结构。邻接矩阵主要用于图的存储，仍需占用完整二维数组空间；二叉链表主要用于二叉树。

3. 【2018】设有一个12 × 12 的对称矩阵 M， 将其上三角部分的元素 $m_{i,j}(1\le i\le j\le 12)$ 按行优先存入C 语言的一维数组 N 中, 元素 $m_{6,6}$ 在 N 中的下标是（ ）。

A. 50
B. 51
C. 55
D. 66

答案： A

解析： 上三角部分按行优先存储时：

• 第1行存12个元素；
• 第2行存11个元素；
• 第3行存10个元素；
• 第4行存9个元素；
• 第5行存8个元素。

因此，在第6行之前共存储

$12+11+10+9+8=50$

个元素。第6行第一个被存储的元素就是 $m_{6,6}$。由于C语言数组下标从0开始，故其下标为50。

4. 【2020】将一个 $10\times 10$ 对称矩阵M 的上三角部分的元素 $m_{i,j}(1\le i\le j\le 10)$ 按列优先存入C 语言的一维数组 N 中, 元素 $m_{7,2}$ 在 N 中的下标是（ ）。

A. 15
B. 16
C. 22
D. 23

答案： C

解析： 由于M为对称矩阵，

$m_{7,2}=m_{2,7}$。

上三角部分按列优先存储时，第j列依次存储

$m_{1,j},m_{2,j},\cdots ,m_{j,j}$，

共j个元素。在第7列之前，共存储

$1+2+3+4+5+6=21$

个元素。$m_{2,7}$ 是第7列中的第2个元素，相对偏移量为1，因此其下标为

$21+1=22$。

5. 【2021】已知二维数组 A 按行优先方法存储, 每个元素占用1 个存储单元，若元素 $A[0][0]$ 的存储地址为 100，$A[3][3]$ 的存储地址为 220，则元素 $A[5][5]$ 的存储地址是（ ）。

A. 295
B. 300
C. 301
D. 306

答案： B

解析： 设二维数组每行有n个元素。按行优先存储且每个元素占1个存储单元，则

$\mathrm{LOC}(A[i][j])=100+in+j$。

由 $A[3][3]$ 的地址为220，得

$100+3n+3=220$，

所以

$3n=117$，$n=39$。

于是

$\mathrm{LOC}(A[5][5])=100+5\times 39+5=300$。

6. 【2023】若采用三元组表存储结构存储稀疏矩阵M，则除三元组表外, 下列数据中还需要保存的是（ ）。 I. M 的行数 II. M 中包含非零元素的行数 III. M 的列数 IV. M 中包含非零元素的列数

A. 仅I、III
B. 仅I、IV
C. 仅II、IV
D. I、II、III、IV

答案： A

解析： 三元组表中的每个三元组记录一个非零元素的行号、列号和值。为了完整确定原稀疏矩阵的规模，还必须保存矩阵M的总行数和总列数。

“包含非零元素的行数”和“包含非零元素的列数”并不是恢复矩阵结构所必需的信息，它们可以根据三元组中的行号、列号统计得到。

因此，还需要保存的是M的行数和列数，即I、III。