type
status
date
slug
summary
tags
category
icon
password
前言：
算法与数据结构第二次作业
一、栈和队列作业
1. 若按课本中图 3 . 1 ( b ) 所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道），请问：
1）如果进站的车厢序列为 1 2 3 ，则可能得到的出站车厢序列是什么？
2）如果进站的车厢序列为 1 2 3 4 5 6 ，则能否得到 4 3 5 6 1 2 和 1 3 5 4 2 6 的出站序列，并请说明为什么不能得到或者如何得到（即写出以“s”表示进栈和以“x”表示出栈的栈操作序列）
1）1 2 3 ，1 3 2 ，2 1 3 ，2 3 1 ，3 2 1 ，不能得到 3 1 2
2）序列 4 3 5 6 1 2 ：不能得到
解释
原因是按照栈操作规则，若最后两个出站车厢为“ 1 2 ”，则此时栈顶应为 1 ，但实际在操作过程中，当处理到 6 出栈后，栈中剩余的为 2 、1（栈顶为 2 ），无法实现“ 1 2 ”的顺序出栈
序列 1 3 5 4 2 6 ：能通过栈操作得到，操作序列为 “s x s s x s s x x x s x”
步骤
1. 车厢1进栈（s）、出栈（x）；
2. 车厢2进栈（s）；
3. 车厢3进栈（s）、出栈（x）；
4. 车厢4进栈（s）、车厢5进栈（s）、车厢5出栈（x）；
5. 车厢4出栈（x）；
6. 车厢2出栈（x）；
7. 车厢6进栈（s）、出栈（x）。
2.若元素的进栈序列为A，B，C，D，E，运用栈操作，能否得到出栈序列B，C，A，E， D和D，B， A，C，E？为什么？
1）能否得到出栈序列 B，C，A，E，D
模拟操作
• A 进栈，栈状态：[ A ]
• B 进栈，栈状态：[ A , B ]
• B 出栈，得到 B，栈状态：[ A ]
• C 进栈，栈状态：[ A , C ]
• C 出栈，得到 C，栈状态：[ A ]
• A 出栈，得到 A，栈状态：[ ]
• D 进栈，栈状态：[ D ]
• E 进栈，栈状态：[ D , E ]
• E 出栈，得到 E，栈状态：[ D ]
• D 出栈，得到 D，栈状态：[ ]
结论：该序列可以通过栈操作实现
2）能否得到出栈序列 D，B，A，C，E
模拟操作
• A 进栈，栈状态：[ A ]
• B 进栈，栈状态：[ A , B ]
• C 进栈，栈状态：[ A , B , C ]
• D 进栈，栈状态：[ A , B , C , D ]
• D 出栈，得到 D，此时栈状态：[ A , B , C ]
• 此时要得到 B，需要将 C 出栈，但这样会导致无法得到后续的 C 和 E
结论：该序列无法实现，因为 D 出栈后，C 仍在栈中，无法直接得到 B，A 和后续的 C, E
3.什么是栈，什么是队列？它们分别有哪几种存储结构？
栈 是只允许在一端进行插入或删除操作的线性表，特点为后进先出（ L I F O ）
队列 是允许只在一端进行插入操作，在另一端进行删除操作的线性表，特点为先进先出（ F I F O ）
它们的存储结构主要有两种：
顺序存储结构：栈可以用数组实现，通过栈顶指针指示操作位置；队列可用数组实现，普通数组队列存在“假溢出”问题，循环队列可解决该问题
链式存储结构：栈用链表实现，栈顶在链表头部，入栈出栈均在头部操作；队列用链表实现，队头指针指向前端节点，队尾指针指向尾端节点，入队在尾部，出队在头部
4.循环队列的优点是什么？如何判断它的空和满？
优点：解决了普通队列“假溢出”问题，提高了存储空间的利用率
判断空和满的方法如下：
队空：当队头指针等于队尾指针时，即`Q.front == Q.rear`，表示队列为空
队满：当队尾指针加 1 后等于队头指针时，即`(Q.rear + 1) % MAXSIZE == Q.front`，表示队列已满
5.写出下列术语的英文数据结构，算法，算法分析，时间复杂性，空间复杂性，线性表，顺序表，链表，循环链表，双向链表，栈，队列，中缀表达式，后缀表达式
数据结构：Data Structure
算法：Algorithm
算法分析：Algorithm Analysis
时间复杂性：Time Complexity
空间复杂性：Space Complexity
线性表：Linear List
顺序表：Sequential List
链表：Linked List
循环链表：Circular Linked List
双向链表：Doubly Linked List
栈：Stack
队列：Queue
中缀表达式：Infix Expression
后缀表达式：Postfix Expression
6.设环形队列中数组的下标是0到M-1，其中头、尾下标分别为front和rear，假定队列不满，则插入一个元素后，队尾rear变为多少？
7.写一个算法（使用栈）判定给定的字符向量是否为回文（即正读反读均相同的字符序列)
见作业一
8. Please convert the infix expression into postfix expression(OPTR stack) and then calculate the value of postfix expression(OPDN stack).
将下列中缀表达式转换为后缀表达式（使用 OPTR 栈），再计算后缀表达式的值（使用 OPDN 栈）
（1） A-B*C/D+E^F#
（2）a+b*((c+d)/(e-f))#
（3） ((a+b)+c*(d+e))*(g+h)#
答案：
（1）A B C * D / - E F∧+
（2）a b c d + e f - / ∗ +
（3）a b + c d e + * + g h + *
9.写出算法实现的功能及每步操作的含义
见作业一
10.已知带头节点的单链表H，写一算法，删除其重复结点实现如图的操作，并分析算法复杂度。(a)为删除前，(b)为删除后
见作业一
<ins/>
二、数组和广义表作业
1.给出下列稀疏矩阵的三元组表示
答案：行数、列数、非零元个数分别为： mu=7， nu=6， tu=8，所以，三元组表示为
行 | 列 | 值 |
1 | 3 | -3 |
1 | 6 | 15 |
2 | 1 | 12 |
2 | 5 | 18 |
3 | 1 | 9 |
3 | 4 | 24 |
4 | 6 | -7 |
5 | 3 | 14 |
2.二维数组 a [0..2] [0..5] 按“行优先顺序”存储在内存中，假设每个元素占用 2 个字节，LOC ( a [0] [0] ) = 10 , 求 LOC (a [2] [4] )
链接课本
答案：42
解释：二维数组 a [0..2] [0..5] 共有 3 行，每行有 6 个元素（索引从 0 到 5）
每个元素占 2 个字节，起始地址 LOC ( a [0] [0] ) = 10
按行优先顺序存储，计算 LOC ( a [2] [4] ) 的公式为：
代入数据：
3.给出对称矩阵压缩存放在一维数组中的坐标变换公式
链接课本
对称矩阵 A_n×n 存放下三角矩阵时，下三角矩阵共有 n ( n + 1 ) / 2 个元素
所以用一维数组 B 存放时， B 的大小为 n(n+1)/2 个单元，即下标为 0~n ( n + 1 ) / 2 - 1
• 当 i ＞ j 时 ：
a_i,j 位于下三角区域
在 a_i,j 之前的 i-1 行（从第 0 行到第 i-1 行），共有 1 + 2 + … + i = i ( i + 1 ) / 2 个元素
在第 i 行上， a_i,j 之前恰有 j 个元素。
因此，对应的一维数组 B 中的索引为：
• 当 i < j 时 ：
a_i,j 位于上三角矩阵中
由于对称矩阵的性质 a_i,j = a_j,i，因此只需将上述对应关系式中的 i 和 j 交换，即可得到对应的一维数组 B 中的索引：
4.给出右上三角形矩阵压缩存放在一维数组中的坐标变换公式
链接课本
右上三角矩阵的重复元素 c 可共享一个存储空间，其余的元素共有 n ( n + 1 ) / 2 个
因此，三角矩阵可以压缩存储到一维数组 B [ 0 . . n ( n + 1 ) / 2 ] 中，其中 c 存放在 B 的最后一个单元中
若 i<= j，则 a _ i j 在上三角矩阵中，因为 a _ i j 之前的 i - 1 行（从第 0 行到第 i-1 行）共有 n + ( n - 1 ) + ( n - 2 ) + … + ( n - i + 1 ) 个元素，在第 i 行上，a _ i j 之前恰有 j - i 个元素
所以有：k = i * ( 2 n - i + 1 ) / 2 + j - i
5.将一个 n*n 的三对角带状矩阵中的元素值 a [i] [j] 压缩存储在向量 B [k] 中
1）写出 i、j 和 k 之间的对应关系
2）当 n=1000，每个元素占 L 个单元，则用 B [k] 方式存储，比常规存储节约多少单元？
答案：
1）当 | i - j | > 1 时，元素 a _ i j = 0
当 | i - j | ≤ 1 时， k = ( 3 i - 1 ) + ( j - i + 1 ) = 2 i + j ，其中 0 ≤ i , j ≤（ n - 1 ），0 ≤ k ≤ 3 n - 3
由 k 可得： i = ( k + 1 ) / 3（取下整数）
j = k - 2 i = k - ( k + 1 ) / 3
2）[ n² - ( 3 n - 2 ) ] * L
当 n = 1000 时，常规存储需要 n² 个单元
而三对角带状矩阵的非零元素共有 3n - 2 个（每行有 3 个非零元素，除了第一行和最后一行少一个）
所以，压缩存储需要 3n - 2 个单元
节约的单元数为：
每个元素占 L 个单元，节约的总单元数为 997002 × L
<ins/>
- 作者:EageYren
- 链接:https://eageyren.edu.deal/learning/algorithm2
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
