c[i][j]=i+j;
A．O
（1） B.O（n） C.（log2n） D.O（n2）
19.算法分析的两个主要方面是（A）。
A.空间复杂性和时间复杂性B.正确性和简明性
C.可读性和文档性 D.数据复杂性和程序复杂性
20.计算机算法必须具备输入、输出和（C）。
A.计算方法 B.排序方法 C.解决问题的有限运算步骤D.程序设计方法
第2章线性表
一、判断题
1.线性表的链式存储结构优于顺序存储。
（×）
2.链表的每个结点都恰好包含一个指针域。
（×）
3.在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。
（√）
4.顺序存储方式的优点是存储密度大，插入、删除效率高。
（×）
5.线性链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
（×）
6.顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
（×）
7.线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。
（√）
8.线性表采用顺序存储，必须占用一片连续的存储单元。
（√）
9.顺序表结构适宜进行顺序存取，而链表适宜进行随机存取。
（×）
10.插入和删除操作是数据结构中是最基本的两种操作，所以这两种操作在数组中也经常使用。
（×）
二、填空题
1.顺序表中逻辑上相邻的元素在物理位置上必须相邻。
2.线性表中结点的集合是有限的，结点间的关系是一对一关系。
3.顺序表相对于链表的优点是节省存储和随机存取。
4.链表相对于顺序表的优点是插入、删除方便。
5.当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快速度存取线性表中的元素时，应采用 顺序 存储结构。
6.顺序表中访问任意一个结点的时间复杂度均为O
（1）。
7.链表相对于顺序表的优点是插入、删除方便；缺点是存储密度小。
8.在双向链表中要删除已知结点*P，其时间复杂度为O
（1）。
9.在单向链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前驱结点的地址，其查找的时间复杂度为O（n）。
10.在单向链表中需知道头指针才能遍历整个链表。
11.线性表中第一个结点没有直接前驱，称为开始结点。
12.在一个长度为n的顺序表中删除第i个元素，要移动 n-i 个元素。
13.在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移n-i+1 个元素。
14.在无头结点的单向链表中，第一个结点的地址存放在头指针中，而其他结点的存储地址存放在
前趋 结点的指针域中。
15.线性表的元素总数不确定，且经常需要进行插入和删除操作，应采用 链子 存储结构。
16.在线性表中的链式存储中，元素之间的逻辑关系是通过 指针 决定。
17.在双向链表中，每个结点都有两个指针域，它们一个指向其前趋 结点，另一个指向其后继结点。
18.对一个需要经常进行插入和删除操作的线性表，采用 链式 存储结构为宜。
19.双向链表中，设P是指向其中待删除的结点，则需要执行的操作为p->prior->next=p->next；p-
>next->prior=p->prior
20.在如图所示的链表中，若在指针P所在的结点之后插入数据域值为a和b的两个结点，则可用语句S->next->next=p->next和P->next=S；来实现该操作。
L
∧
D
C
B
A
p
∧
b
a
s
三、选择题
1.在具有n个结点的单向链表中，实现（A）的操作，其算法的时间复杂度都是O（n）.
A.遍历链表或求链表的第i个结点 B.在地址为P的结点之后插入一个结点
C.删除开始结点 D.删除地址为P的结点的后继结点
∧
c
20
b
10
a
2.设a、b、c为3个结点，p、10、20分别代表它们的地址，则如下的存储结构称为（B）。
p
A．循环链表
3. 单向链表的存储密度（
B．单向链表
C）。
C．双向循环链表
D．双向链表
A.大于1
B.等于1
C.小于1
D.不能确定
4.已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为（A）。
A.B+（i-1）×m B.B+i×m C.B-i×m D.B+（i+1）×m
5.在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为（ B）。
A．O
（1） B.O（n） C.O（n2） D.O（log2n）
6.设front、rear分别为循环双向链表结点的左指针和右指针，则指针P所指的元素是双循环链表L
的尾元素的条件是（D）。
A.P==L B.P->front==L C.P==NULL D.P->rear==L
7.两个指针P和Q，分别指向单向链表的两个元素，P所指元素是Q所指元素前驱的条件是（ B）
A．P->next==Q->next B.P->next==Q C.Q->next==P D.P==Q
8. 用链表存储的线性表，其优点是（ C）。
A．便于随机存取 B．花费的存储空间比顺序表少
C．便于插入和删除 D．数据元素的物理顺序与逻辑顺序相同
9.在单链表中，增加头结点的目的是（C）。
A．使单链表至少有一个结点B．标志表中首结点的位置C．方便运算的实现 D．说明该单链表是线性表的链式存储结构
10.下面关于线性表的叙述中，错误的是（D）关系。
A．顺序表必须占一片地址连续的存储单元B．顺序表可以随机存取任一元素C．链表不必占用一片地址连续的存储单元D．链表可以随机存取任一元素
11.L是线性表，已知LengthList（L）的值是5，经DelList（L，2）运算后，LengthList（L）的值是（C）。
A．2 B．3 C．4 D．5
12.单向链表的示意图如下：
P Q R
指向链表Q结点的前驱的指针是（B）。
A．L B．P C．Q D．R
13.设p为指向单循环链表上某结点的指针，则*p的直接前驱（C）。
A．找不到 B．查找时间复杂度为O
（1）C．查找时间复杂度为O（n）D．查找结点的次数约为n
14.等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为（8）。
A．n B.（n-1）/2 C.n/2 D.（n+1）/2
15.在下列链表中不能从当前结点出发访问到其余各结点的是（C）。
A.双向链表 B.单循环链表 C.单向链表 D.双向循环链表
16.在顺序表中，只要知道（D），就可以求出任一结点的存储地址。
A.基地址 B.结点大小 C.向量大小 D.基地址和结点大小
17.在双向链表中做插入运算的时间复杂度为（A）。
A．O
（1） B.O（n） C.O（n2） D.O（log2n）
18.链表不具备的特点是（A）。
A．随机访问 B.不必事先估计存储空间C.插入删除时不需要移动元素D.所需空间与线性表成正比
19.以下关于线性表的论述，不正确的为（C）。
A.线性表中的元素可以是数字、字符、记录等不同类型B.线性顺序表中包含的元素个数不是任意的
C.线性表中的每个结点都有且仅有一个直接前驱和一个直接后继
D.存在这样的线性表，即表中没有任何结点
20.在（B）的运算中，使用顺序表比链表好。
A.插入 B.根据序号查找 C.删除 D.根据元素查找
第3章栈
一、判断题
1.栈是运算受限制的线性表。
（√）
2.在栈空的情况下，不能作出栈操作，否则产生下溢。
（√）
3.栈一定是顺序存储的线性结构。
（×）
4.栈的特点是“后进先出”。
（√）
5.空栈就是所有元素都为0的栈。
（×）
6.在C（或C++）语言中设顺序栈的长度为MAXLEN，则top=MAXLEN时表示栈满。
（×）
7.链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。
（√）
8.一个栈的输入序列为：
A，B，C，D，可以得到输出序列：
C，A，B，D。
（×）
9.递归定义就是循环定义。
（×）
10.将十进制数转换为二进制数是栈的典型应用之一。
（√）
二、填空题
1.在栈结构中，允许插入、删除的一端称为 栈顶 。
2.在顺序栈中，当栈顶指针top=-1时，表示 栈空 。
3.在有n个元素的栈中，进栈操作时间复杂度为 O
（1） 。
4.在栈中，出栈操作时间复杂度为 O
（1） 。
5.已知表达式，求它的后缀表达式是 栈 的典型应用。
6.在一个链栈中，若栈顶指针等于NULL，则表示 栈空 。
7.向一个栈顶指针为top的链栈插入一个新结点*p时，应执行p->next=top;top=p；操作。
8.顺序栈S存储在数组S->data[0…MAXLEN-1]中，进栈操作时要执行的语句有：
S->top++。
（或S-
>top+1）
S->data[S->top]=x
9.链栈LS，指向栈顶元素的指针是LS->next。
10.从一个栈删除元素时，首先取出 栈顶元素 ，然后再移动栈顶指针。
11.由于链栈的操作只在链表的头部进行，所以没有必要设置 头 结点。
12.已知顺序栈S，在对S进栈操作之前首先要判断 栈是否满 。
13.已知顺序栈S，在对S出栈操作之前首先要判断 栈是否空 。
14.若内在空间充足， 链 栈可以不定义栈满运算。
15.链栈LS为空的条件是 LS->next=NULL 。
16.链栈LS的栈顶元素是链表的 首 元素。
17.同一栈的各元素的类型 相同 。
18.若进栈的次序是A、B、C、D、E，执行3次出栈操作以后，栈顶元素为 B 。
19.A+B/C-D*E的后缀表达式是 ABC/+DE*- 。
20.4个元素A、B、C、D顺序进S栈，执行两次Pop（S,x）运算后，x的值是 C 。
三、选择题
1.插入和删除操作只能在一端进行的线性表，称为（C）。
A．队列 B．循环队列 C．栈 D．循环栈
2.设有编号为1，2。
3，4的4辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为（D）。
A．1234 B．1243 C．1324 D．1423
3.如果以链表作为栈的存储结构，则出栈操作时（B）。
A．必须判别栈是否满 B．必须判别栈是否为空 C．必须判别栈元素类型 D．栈可不做任何判别
4.元素A、B、C、D依次进栈以后，栈顶元素是（D）
A．A B．B C．C D．D
5.顺序栈存储空间的实现使用（B）存储元素。
A．链表 B．数组 C．循环链表 D．变量
6.在C（或C++）语言中，一个顺序栈一旦被声明，其占用空间的大小（A）。
A．已固定 B．不固定 C．可以改变 D．动态变化
∧
D
C
B
A
H
7.带头结点的链栈LS的示意图如下，栈顶元素是（ A）。
LS
A．A B．B C．C D．D
8.链栈与顺序栈相比，有一个比较明显的优点是（ B）。
A.插入操作更加方便 B.通常不会出现栈满的情况 C.不会出现栈空的情况 D.删除操作更加方便
9.从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列（d ）命令。
A．x=top;top->next; B.top=top->next;x=top->dataC.x=top->data; D.x=top->data;top=top->next
10.在一个栈顶指针为HS的链栈中，将一个S指针所指的结点入栈，应执行下列（ B）命令。
A.HS->next=S B.S->next=HS->next;HS->next=S;C.S->next=HS->next;HS=S; D.S->next=HS=HS->next
11.4元素按A、B、C、D顺序进S栈，执行两次Pop（S，x）运算后，栈顶元素的值是（ B）。
A．A B．B C．C D．D
12.元素A、B、C、D依次进栈以后，栈底元素是（A）。
A.AB．B C．C D．D
13.经过下列栈的运算后，再执行ReadTop（s）的值是（ A）。
InitStack（s）;Push（s，a）;Push（s，b）;Pob（s）;
A.a B.b C.1 D.0
14.经过下列栈的运算后，x的值是（B）。
InitStack（s）（初始化栈）;Push（s，a）;Push（s，b）;ReadTop（s）；Pob（s，x）;
A.a B.b C.1 D.0
15.经过下列栈的运算后，x的值是（ B）。
InitStack（s）（初始化栈）;Push（s,a）;Pob（s，x）;Push（s,b）;Pob（s，x）;
A.a B.b C.1 D.0
16.经过下列栈的运算后,SEmpty（s）的值是（ C）。
InitStack（s）（初始化栈）;Push（s,a）;Push（s,b）;Pob（s，x）;Pob（s，x）;
A.a B.b C.1 D.0
17.向顺序栈中输入元素时（B）。
A．先存入元素，后移动栈顶指针 B．先移动栈顶指针，后存入元素C．谁先谁后无关紧要 D．同时进行
18.初始化一个空间大小为5的顺序栈S后，S->top的值是（B）。
A．0 B．-1 C．不再改变 D．动态变化
19.设有一个入栈的次序A、B、C、D、E，则栈不可能的输出序列是（ C）。
A．EDCBA B．DECBA C．DCEAB D．ABCDE
20.设有一个顺序栈S，元素A、B、C、D、E、F依次进栈，如果6个元素出栈的顺序是
B、D、C、F、E、A，则栈的容量至少应是（A）。
A．3 B．4 C．5 D．6
第4章队列
一、判断题
1.队列是限制在两端进行操作的线性表。
（√）
2.判断顺序队列为空的标准是头指针和尾指针都指向同一个结点。
（√）
3.在链队列上做出队操作时，会改变front指针的值。
（×）
4.在循环队列中，若尾指针rear大于头指针front，其元素个数为rear-front。
（√）
5.在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是p=h。
（×）
6.链队列在一定范围内不会出现队满的情况。
（√）
7.在循环链队列中无溢出现象。
（×）
8.栈和队列都是顺序存储的线性结构。
（×）
9.在队列中允许删除的一端称为队尾。
（×）
10.顺序队和循环队关于队满和队空的判断条件是一样的。
（×）
二、填空题
1.在队列中存取数据应遵循的原则是 先进先出 。
2. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算线性表。
3.在队列中，允许插入的一端称为 队尾 。
4.在队列中，允许删除的一端称为 队首（或队头）。
5.队列在进行出队操作时，首先要判断队列是否为空 。
6.顺序队列在进行入队操作时，首先在判断队列是否为 满 。
7.顺序队列初始化后，初始化后，front=rear=-1 。
8.解决顺序队列“假溢出”的方法是采用 循环队列 。
9.循环队列的队指针为front，队尾指针为rear，则队空的条件为 front==rear 。
10.链队列LQ为空时，LQ->front->next= NULL 。
11.设长度为n的链队列用单循环表表示，若只设头指针，则入队操作的时间复杂度为 O（n） 。
12.设长度为n的链队列用单循环表表示，若只设尾指针，则入队操作的时间复杂度为 O
（1）
。
13.在一个链队列中，若队首指针与队尾指针的值相同，则表示该队列为 空 。
14.设循环队列的头指针front指向队首元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，则队满标志为front==（rear+1）%MAXLEN。
15.在一个链队列中，若队首指针为front，队尾指针为rear，则判断队列只有一个结点的条件为front==rear或front!
。
16.向一个循环队列中插入元素时，首先要判断队尾指针，然后再向指针所指的位置写入新的数据。
17.读队首元素的操作不改变或不影响队列元素的个数。
18.设循环队列的容量为40（序号0～39），现经过一系列的入队和出队的运算后，front=11，rear=19，则循环队列中还有 8 个元素。
19.队列Q，经过下列运算：
InitQueue（Q）（初始化队列）；InQueue（Q,a）；InQueue（Q,b）；OutQueue（Q,x）；ReadFront（Q,x）；QEmpty（Q）；后的值是 8 。
20.队列Q经过InitQueue（Q）（初始化队列）；InQueue（Q,a）；InQueue（Q,b）；ReadFront（Q,x）后，x的值是 a 。
三、选择题
1.队列是限定在（
升级会员 