绪论
已知两个长度为 $m$ 和 $n$ 的升序链表, 若将它们合并为长度为 $m + n$ 的一个降序链表, 则最坏情况下的时间复杂度为__. O(max(m,n))
线性表
顺序表
顺序表上实现比在链表上实现效率更高的操作是__. I, II I. 输出第 i 元素; II. 交换第3元素与第4元素; III.顺序输出所有元素.
链表
顺序存储结构和链式存储结构都可以进行顺序存取. (T/F)__ T
与单链表相比, 双链表的优点之一是:__ D
A. 插入删除更方便
B. 可以进行随机访问
C. 可以省略表头指针或表尾指针
D. 访问前后相邻结点更灵活
一个链表最常用的操作是在末尾插入结点和删除结点, 则选用__最节省时间. A
A. 带头结点的双循环链表 B. 单循环链表 C. 带尾指针的单循环链表 D. 单链表
要求对线性表支持4种操作: 删除第一元素, 删除最后一个元素, 在第一个元素前插入元素, 在最后一个元素之后插入元素. 那么最好使用:__ I, II
A. 有尾指针, 无头指针, 循环单链表
B. 有尾指针, 无头指针, 双链表
C. 有头指针, 无尾指针, 循环双链表
D. 有头指针, 有尾指针, 循环单链表
栈, 队列, 数组
栈
设链表不带头结点且操作总在表头进行, 则最不适合作为链栈的是( C )
A. 有表头指针, 无表尾指针的双向循环链表
B. 有表尾指针, 无表头指针的双向循环链表
C. 有表头指针, 无表尾指针的单向循环链表
D. 有表尾指针, 无表头指针的单向循环链表
采用共享栈的好处是( B ).
A. 减少存取时间, 降低发生上溢的可能
B. 节省存储空间, 降低发生上溢的可能
C. 减少存取时间, 降低发生下溢的可能
D. 节省存储空间, 降低发生下溢的可能
给定有限符号集 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 可能互为倒序
队列
最适合用作链队的是( B )
A. 带队首指针和队尾指针的循环单链表
B. 带队首指针和队尾指针的非循环单链表
C. 只带队首指针的非循环单链表
D. 只带队首指针的循环单链表
最不适合用作链队的链表是( A)
A. 只带队首指针的非循环双链表
B. 只带队首指针的循环双链表
C. 只带队尾指针的循环双链表
D. 只带队尾指针的循环单链表
最不适合用作链队的链表是( A)
A. 只带队首指针的非循环双链表
B. 只带队首指针的循环双链表
C. 只带队尾指针的循环双链表
D. 只带队尾指针的循环单链表
假设循环单链表表示的队列长度为 n, 队头固定在链表尾, 若只设头指针, 则进队操作的时间复杂度为( A)
A. $O(n)$
B. $O(1)$
C. $O(n^2)$
D. $O(n\log_2 n)$
已知循环队列存储在一维数组 A[0..n-1]中, 且队列非空时, front 和 rear 分别指向队头元素和队尾元素. 若初始时队列为空, 且要求第一个进入队列的元素存储在 A[0] 处, 则初始时的 front 和 rear 的值分别为( 0, n - 1)
栈与队列的应用
栈的应用不包括( D)
A. 递归 B. 进制转换 C. 迷宫求解 D. 缓冲区
- 栈在表达式求值中的应用
将中缀表达式
a+b-a*((c+d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+时, 用栈存放暂时还不能确定运算次序的操作符. 栈初始为空, 转换过程中同时保存在栈中的操作符的最大个数为( 5)
数组和特殊矩阵
适用于压缩存储稀疏矩阵的两种存储结构是( A)
A. 三元组表和十字链表 B. 三元组表和邻接矩阵 C. 十字链表和二叉链表 D. 邻接矩阵和十字链表
树 & 二叉树
二叉树
度为2的有序树就是二叉树(T/F)( F)
