绪论
两个升序链表进行合并, 一个链表比完了, 另一个链表剩下的直接接上即可. 所以实际上的比较次数是 $m + n - 1 $ 次, 使用 max() 时就化简为答案的格式.已知两个长度为 $m$ 和 $n$ 的升序链表, 若将它们合并为长度为 $m + n$ 的一个降序链表, 则最坏情况下的时间复杂度为__. O(max(m,n))
线性表
顺序表
顺序表能够随机读取, 所以肯定在 I 更快; 而链表的交换需要通过遍历找到前驱节点, 所以相比于顺序表的swap()操作(三次)更为繁琐.顺序表上实现比在链表上实现效率更高的操作是__. I, II I. 输出第 i 元素; II. 交换第3元素与第4元素; III.顺序输出所有元素.
链表
注意搞清楚"顺序存取"和"随机存取"之间的联系和区别. 顺序存储两者都可实现, 而链式存储只能实现顺序存取.顺序存储结构和链式存储结构都可以进行顺序存取. (T/F)__ T
A. 都不用移动元素, 只需要改变指针. 而且双链表反而更复杂一些与单链表相比, 双链表的优点之一是:__ D
A. 插入删除更方便
B. 可以进行随机访问
C. 可以省略表头指针或表尾指针
D. 访问前后相邻结点更灵活
这里要求使用尾插法和尾删法时最便捷, 那么就是需要读取尾结点和尾结点的前驱结点的地址. B. 单循环链表, 读取尾结点需要遍历; C. 带尾指针的单循环链表, 删除尾结点时, 需要更新尾结点的前驱结点, 因此也需要遍历; D. 单链表, 当然是最麻烦的一个链表最常用的操作是在末尾插入结点和删除结点, 则选用__最节省时间. A
A. 带头结点的双循环链表 B. 单循环链表 C. 带尾指针的单循环链表 D. 单链表
A. 删尾结点需要其前驱结点更新指针域, 从前往后遍历耗时$O(n)$; B. 删头节点需要其后继结点更新指针域, 从后往前遍历耗时$O(n)$; D. 删尾结点需要其前驱结点更新指针域, 从前往后遍历耗时$O(n)$.要求对线性表支持4种操作: 删除第一元素, 删除最后一个元素, 在第一个元素前插入元素, 在最后一个元素之后插入元素. 那么最好使用:__ I, II
A. 有尾指针, 无头指针, 循环单链表
B. 有尾指针, 无头指针, 双链表
C. 有头指针, 无尾指针, 循环双链表
D. 有头指针, 有尾指针, 循环单链表
栈, 队列, 数组
栈
C. 已知使用头插法和头删法, 而且没有头结点, 因此这个单向循环链表在完成增删操作后就需要将尾结点的 next 更新为新头结点的地址. 而该链表又没有尾指针, 因此每次更新都需要重新遍历得到尾结点.设链表不带头结点且操作总在表头进行, 则最不适合作为链栈的是( C )
A. 有表头指针, 无表尾指针的双向循环链表
B. 有表尾指针, 无表头指针的双向循环链表
C. 有表头指针, 无表尾指针的单向循环链表
D. 有表尾指针, 无表头指针的单向循环链表
上溢: 相当于"栈满", 指栈已经满了还要往里添加新元素; 下溢: 相当于"栈空", 指站已经空了还要向外弹出一个元素. 共享栈节省空间是必然的, 为什么说是降低发生上溢的可能呢? 这是因为操作都是在栈顶进行的, 只有可能是产生上溢.(两个栈顶指针相逢)采用共享栈的好处是( B ).
A. 减少存取时间, 降低发生上溢的可能
B. 节省存储空间, 降低发生上溢的可能
C. 减少存取时间, 降低发生下溢的可能
D. 节省存储空间, 降低发生下溢的可能
这里重点要积累的是 A,B. 实际上, 只有我们能够确定哪一个是出栈, 哪一个是入栈, 那么我们一定可以通过模拟出入栈来判断两者是否可以具有对应关系. 因此A, B里的"不能判断"是错误的给定有限符号集 S, in 和 out 均为 S 中所有元素的任意排列, 对于初始空的栈 ST, 下列叙述正确的是( D )
A. 若 in 为 ST 的入栈序列, 则不能判断 out 是否为其可能的出栈序列
B. 若 out 为 ST 的出栈序列, 则不能判断 in 是否为其可能的入栈序列
C. 若 in 为 ST 的入栈序列, out 是对应 in 的出栈序列, 则 in 与 out 一定不同
D. 若 in 为 ST 的入栈序列, out 是对应 in 的出栈序列, 则 in 与 out 可能互为倒序
队列
A. 相较于 B. 的循环条件对于队列而言是完全多余的.最适合用作链队的是( B )
A. 带队首指针和队尾指针的循环单链表
B. 带队首指针和队尾指针的非循环单链表
C. 只带队首指针的非循环单链表
D. 只带队首指针的循环单链表
最不适合用作链队的链表是( A)
A. 只带队首指针的非循环双链表
B. 只带队首指针的循环双链表
C. 只带队尾指针的循环双链表
D. 只带队尾指针的循环单链表
对于循环链表而言, 只要知道了队头和队尾指针中的一个, 就可以通过结构体内的 prior 或着 next 知道另一个. 而对于A. 选项, 又是双链表, 又是非循环, 极大地增加了更新结点所需要的工作量. 所以 A 最不合适.最不适合用作链队的链表是( A)
A. 只带队首指针的非循环双链表
B. 只带队首指针的循环双链表
C. 只带队尾指针的循环双链表
D. 只带队尾指针的循环单链表
注意:设置头指针就隐藏着一层含义, 即这个链表并没有头结点. 所以进队时会使头结点产生更新, 这又是一个循环链表, 所以每次进队后都要遍历一次以得到尾结点并且更新其 next 指针, 所以综合下来的时间复杂度为 $O(n)$.假设循环单链表表示的队列长度为 n, 队头固定在链表尾, 若只设头指针, 则进队操作的时间复杂度为( A)
A. $O(n)$
B. $O(1)$
C. $O(n^2)$
D. $O(n\log_2 n)$
记住队列结构中, 入队看的是 rear 指针, 也就是 rear = (rear + 1) % n, 所以如果我们要让第一个入队的元素位置在A[0], 那么就有 (rear0 + 1) % n = 0, 反解即有 rear0 = n - 1.已知循环队列存储在一维数组 A[0..n-1]中, 且队列非空时, front 和 rear 分别指向队头元素和队尾元素. 若初始时队列为空, 且要求第一个进入队列的元素存储在 A[0] 处, 则初始时的 front 和 rear 的值分别为( 0, n - 1)
栈与队列的应用
D. 缓冲区使用的是队列结构栈的应用不包括( D)
A. 递归 B. 进制转换 C. 迷宫求解 D. 缓冲区
- 栈在表达式求值中的应用
扫到运算符的时候, 要输出优先级大于等于该运算符的所有运算符, 也就是说, 扫到'+'的时候要将所有的算符都输出, 包括'-'.将中缀表达式
a+b-a*((c+d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+时, 用栈存放暂时还不能确定运算次序的操作符. 栈初始为空, 转换过程中同时保存在栈中的操作符的最大个数为( 5)
数组和特殊矩阵
三元组表是指这样一种数据结构: 一个三元组表的结点存储 row, col, value 三个值的信息, 可以用来存储稀疏矩阵.适用于压缩存储稀疏矩阵的两种存储结构是( A)
A. 三元组表和十字链表 B. 三元组表和邻接矩阵 C. 十字链表和二叉链表 D. 邻接矩阵和十字链表
树 & 二叉树
二叉树
对于度为2的有序树, 如果存在度为1的分支节点, 那么这个结点无法区分左右孩子, 所以不能够被算作是二叉树度为2的有序树就是二叉树(T/F)( F)
