选择：
1. 已知某算法的执行时间为（n3+n2+n）log2(n+2)，n为问题规模，则该算法的时间复杂度
是（）。

A．O(n) B．O(n2) C．O(log2n) D．O(n3log2n)
2．设有二维数组A[50][60]，其元素长度为1字节，按列优先顺序存储，首元素A[0][0]的地址为200，则元素A[10][20]的存储地址为( )。

A．820 B．720 C．1210 D．1410
3．设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6先后进入栈S，一个元素出栈后即进入队列Q，若6个元素的出队顺序是e2,e4,e3,e6,e5,e1，则栈S至少可以容纳（）个元素。

A．3 B．4 C．5 D．6
4．串是。

A）不少于一个字母的序列B）任意个字母的序列
C）不少于一个字符的序列D）有限个字符的序列
5．A，B，C，D依次入栈，则不可能的出栈序列是。

A）A，B，C，D C）D，C，B，A
B）A，C，D，B D）D，A，B，C
6．栈和队列的共同点是。

A）都是先进后出B）都是先进先出
C）只允许在端点处插入和删除D）都采用顺序方式存储
7．下面关于线性表的叙述中，错误的是。

A）线性表采用顺序方式存储，必须占用一片连续的存储单元
B）线性表采用链式存储，便于进行插入和删除操作
C）线性表采用链式存储，不必占用一片连续的存储单元
D）线性表采用顺序方式存储，便于进行插入和删除操作
8．广义表A=（（a,b,c），（d,e,f）），从A中取出原子e的运算是。

A）tail(head(A)) B）head(tail(tail(head(A))))
C）head(tail(A)) D）head(tail(head(tail(A))))
9．判定一个指针ST指向的顺序栈（栈中最多元素为M个）为栈满的条件是。

A）ST->top!=0 B）ST->top==0
C）ST->top!=M-1 D）ST->top==M-1
10．指针head指向一个非空循环单链表的头结点，指针p指向该链表的尾结点的条件是。

A）p->next=NULL B）p=NULL
C）p->next=head D）p=head
11.链表不具有的特点是。

A．插入、删除不需要移动元素 B．可随机访问任一元素
C．不必事先估计存储空间D．所需空间与线性长度成正比
12. 在作进栈运算时,应先判别栈是否 B ,在作退栈运算时应先判别栈是否 A 。

当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为③。

①, ②: A. 空 B. 满 C. 上溢 D. 下溢
③: A. n-1 B. n C. n+1 D. n/2
13. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结
点，则在进行删除操作时。

A．仅修改队头指针 B. 仅修改队尾指针
C. 队头、队尾指针都要修改
D. 队头,队尾指针都可能要修改
14．下面关于串的的叙述中，是不正确的？
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储
15. 广义表L=（a，（b，c）），进行Tail（L）操作后的结果为。

A. c
B. b，c
C.（b，c）
D.（（b，c））
判断:
1．算法与程序没有别，所以在数据结构中两者是通用的。

2．串长度是指串中不同字符的个数。

3．栈是一种后进先出表。

5．根据线性表的链式存储结构中每个结点所含指针的个数，链表分为单链表和双链表。

6．在栈满的情况下不能作进栈的运算，否则产生“上溢”。

7．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此单链表是随机存取的结构。

8．一个n维数组可以视为其数据元素是n-1维的线性表。

9.顺序存储结构的主要缺点是不利于插入或删除操作。

10.线性表的特点是每个元素都有一个前驱和一个后继。

11.循环链表不是线性表。

12.广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。

算法设计:
1．写出将一单链表就地逆置的算法（设单链表带头结点、非循环，链表中每一结点包含一个数据域和一个指针域）。

2.写出将一单链表中所有值相同的重复结点删除，使所得结果表中各结点值均不相同的算法（设单链表带头结点、非循环，链表中每一结点只包含一个数据域和一个指针域）。