A.n-i
B.n-i+l
C.n-i-1
D.i
8.在一个单链表中,已知q结点是p结点的前趋结点,若在q和p之间插入s结点,则须执行
A.s->next=p->next;p->next=s
B.q->next=s;s->next=p
C.p->next=s->next;s->next=p
D.p->next=s;s->next=q
9.以下关于线性表的说法不正确的是______。
A.线性表中的数据元素可以是数字、字符、记录等不同类型。
B.线性表中包含的数据元素个数不是任意的。
C.线性表中的每个结点都有且只有一个直接前趋和直接后继。
D.存在这样的线性表:
表中各结点都没有直接前趋和直接后继。
10.线性表的顺序存储结构是一种_______的存储结构。
A.随机存取
B.顺序存取
C.索引存取
D.散列存取
11.在顺序表中,只要知道_______,就可在相同时间内求出任一结点的存储地址。
A.基地址
B.结点大小
C.向量大小
D.基地址和结点大小
12.在等概率情况下,顺序表的插入操作要移动______结点。
A.全部
B.一半
C.三分之一
D.四分之一
13.在______运算中,使用顺序表比链表好。
A.插入
B.删除
C.根据序号查找
D.根据元素值查找
14.在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是_______。
A.O
（1）
B.O（n）
C.O（n2）
D.O（log2n）
15.设有一个栈,元素的进栈次序为A,B,C,D,E,下列是不可能的出栈序列__________。
A.A,B,C,D,E
B.B,C,D,E,A
C.E,A,B,C,D
D.E,D,C,B,A
16.在一个具有n个单元的顺序栈中,假定以地址低端（即0单元）作为栈底,以top作为栈顶指针,当做出栈处理时,top变化为______。
A.top不变
B.top=0
C.top--
D.top++
17.向一个栈顶指针为hs的链栈中插入一个s结点时,应执行______。
A.hs->next=s;
B.s->next=hs;hs=s;
C.s->next=hs->next;hs->next=s;
D.s->next=hs;hs=hs->next;
18.在具有n个单元的顺序存储的循环队列中,假定front和rear分别为队头指针和队尾指针,则判断队满的条件为________。
A.rear%n==front
B.（front+l）%n==rear
C.rear%n-1==front
D.（rear+l）%n==front
19.在具有n个单元的顺序存储的循环队列中,假定front和rear分别为队头指针和队尾指针,则判断队空的条件为________。
A.rear%n==front
B.front+l=rear
C.rear==front
D.（rear+l）%n=front
20.在一个链队列中,假定front和rear分别为队首和队尾指针,则删除一个结点的操作为________。
A.front=front->next
B.rear=rear->next
C.rear=front->next
D.front=rear->next
二、填空题
1.线性表是一种典型的_________结构。
2.在一个长度为n的顺序表的第i个元素之前插入一个元素,需要后移____个元素。
2.n-i+1
3.顺序表中逻辑上相邻的元素的物理位置________。
4.要从一个顺序表删除一个元素时,被删除元素之后的所有元素均需_______一个位置,移动过程是从_______向_______依次移动每一个元素。
5.在线性表的顺序存储中,元素之间的逻辑关系是通过_______决定的;在线性表的链接存
储中,元素之间的逻辑关系是通过_______决定的。
6.在双向链表中,每个结点含有两个指针域,一个指向_______结点,另一个指向_______结点。
7.当对一个线性表经常进行存取操作,而很少进行插入和删除操作时,则采用_______存储结构为宜。
相反,当经常进行的是插入和删除操作时,则采用_______存储结构为宜。
8.顺序表中逻辑上相邻的元素,物理位置_______相邻,单链表中逻辑上相邻的元素,物理位置_______相邻。
9.线性表、栈和队列都是_______结构,可以在线性表的______位置插入和删除元素;对于栈只能在_______位置插入和删除元素;对于队列只能在_______位置插入元素和在_______位置删除元素。
10.根据线性表的链式存储结构中每个结点所含指针的个数,链表可分为_________和_______;而根据指针的联接方式,链表又可分为________和_________
11.在单链表中设置头结点的作用是________。
12.对于一个具有n个结点的单链表,在已知的结点p后插入一个新结点的时间复杂度为______,在给定值为x的结点后插入一个新结点的时间复杂度为_______。
13.对于一个栈作进栈运算时,应先判别栈是否为_______,作退栈运算时,应先判别栈是否为_______,当栈中元素为m时,作进栈运算时发生上溢,则说明栈的可用最大容量为_______。
为了增加内存空间的利用率和减少发生上溢的可能性,由两个栈共享一片连续的内存空间时,应将两栈的_______分别设在这片内存空间的两端,这样只有当_______时才产生上溢。
14.设有一空栈,现有输入序列1,2,3,4,5,经过push,push,pop,push,pop,push,push后,输出序列是_________。
15.无论对于顺序存储还是链式存储的栈和队列来说,进行插入或删除运算的时间复杂度均相同为__________。
三、简答题
1.描述以下三个概念的区别:
头指针,头结点,表头结点。
2.线性表的两种存储结构各有哪些优缺点?
3.对于线性表的两种存储结构,如果有n个线性表同时并存,而且在处理过程中各表的长度会动态发生变化,线性表的总数也会自动改变,在此情况下,应选用哪一种存储结构?
为什么?
4.对于线性表的两种存储结构,若线性表的总数基本稳定,且很少进行插入和删除操作,但要求以最快的速度存取线性表中的元素,应选用何种存储结构?
试说明理由。
四、算法设计题
1.设计在无头结点的单链表中删除第i个结点的算法。
2.在单链表上实现线性表的求表长ListLength（L）运算。
3.设计将带表头的链表逆置算法。
4.假设有一个带表头结点的链表,表头指针为head,每个结点含三个域:
data,next和prior。
其中data为整型数域,next和prior均为指针域。
现在所有结点已经由next域连接起来,试编一个算法,利用prior域（此域初值为NULL）把所有结点按照其值从小到大的顺序链接起来。
升级会员 