表达式转换
1-1
对于顺序存储的长度为N的线性表，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。
(2分)
T
1-2
若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用顺序表存储最节省时间。
(2分)
T
1-3
在具有N个结点的单链表中，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。
(2分)
F
1-4
通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。
(2分)
F
1-5
若一个栈的输入序列为1，2，3，…，N，输出序列的第一个元素是i，则第j个输出元素是j−i−1。
(2分)
F
1-6
所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。
(2分)
F
1-7
在用数组表示的循环队列中，front值一定小于等于rear值。
(2分)
F
1-8
对于顺序存储的长度为N的线性表，删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(1)和O(N)。
(2分)
F
1-9
若一个栈的输入序列为{1, 2, 3, 4, 5}，则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。
(2分)
F
1-10
若用链表来表示一个线性表，则表中元素的地址一定是连续的。
(2分)
F
2-1
若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用哪种存储方式最节省运算时间？
(5分)d
A.
单链表
B.
双链表
C.
单循环链表
D.
带头结点的双循环链表
2-2
将线性表La和Lb头尾连接，要求时间复杂度为O(1)，且占用辅助空间尽量小。应该使用哪种结构？
(5分)c
A.
单链表
B.
单循环链表
C.
带尾指针的单循环链表
D.
带头结点的双循环链表
2-3
假设有5个整数以1、2、3、4、5的顺序被压入堆栈，且出栈顺序为3、5、4、2、1，那么为了获得这样的输出，堆栈大小至少为：
(5分)c
A.
2
B.
3
C.
4
D.
5
作者
DS课程组
单位
浙江大学
2-4
表达式a*(b+c)-d的后缀表达式是：a
(5分)
A.
a b c + * d -
B.
a b c d * + -
C.
a b c * + d -
D.
- + * a b c d
2-5
若采用带头、尾指针的单向链表表示一个堆栈，那么该堆栈的栈顶指针top应该如何设置？
(5分)a
A.
将链表头设为top
B.
将链表尾设为top
C.
随便哪端作为top都可以
D.
链表头、尾都不适合作为top
作者
DS课程组
单位
浙江大学
2-6
某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a、b、c、d、e依次入此队列后再进行出队操作，则不可能得到的出队序列是：
(5分)d
A.
b a c d e
B.
d b a c e
C.
e c b a d
D.
d b c a e
作者
DS课程组
单位
浙江大学
2-7
若用大小为6的数组来实现循环队列，且当前front和rear的值分别为0和4。当从队列中删除两个元素，再加入两个元素后，front和rear的值分别为多少？
(5分)a
A.
2和0
B.
2和2
C.
2和4
D.
2和6
作者
DS课程组
单位
浙江大学
2-8
如果循环队列用大小为m的数组表示，且用队头指针front和队列元素个数size代替一般循环队列中的front和rear指针来表示队列的范围，那么这样的循环队列可以容纳的元素个数最多为：
(5分)b
A.
m-1
B.
m
C.
m+1
D.
不能确定
作者
DS课程组
单位
浙江大学
2-10
有一个100阶的三对角矩阵M，其三对角元素mi,j（1≤i≤100，1≤j≤100）按行优先次序压缩存入下标从0开始的一维数组N中。元素m30,30在N中的下标是：
(5分)b
A.
86
B.
87
C.
88
D.
89
作者
DS课程组
单位
浙江大学
2-11
设有一个 12×12 的对称矩阵M，将其上三角部分的元素mi,j（1≤i≤j≤12）按行优先存入C语言的一维数组N中，元素m6,6在N中的下标是：
A.50