一、单项选择题（共15小题，每小题2分，共30分）
1.一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（b）。
A、2 3 4 1 5
B、5 4 1 3 2
C、2 3 1 4 5
D、1 5 4 3 2
2.设循环队列中数组的下标范围是1-n，其头尾指针分别为f和r，则其元素个数为（d）。
A、r-f
B、r-f+1
C、(r-f) mod n+1
D、(r-f+n) mod n
3.对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由( c)式确定.
A、Loc[i,j]=A[m,n]+[(n+1)*i+j]*k
B、Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k
C、Loc[i,j]=loc[0,0]+[n*i+j]*k
D、Loc[i,j]=[(n+1)*i+j]*k
4．如果以链表作为栈的存储结构，则退栈操作是(B )
A、必须判别栈是否满
B、必须判别栈是否空
C、判别栈元素的类型
D、对栈不做任何操作
5．基于三元组的稀疏矩阵，对每个非零元素a ij,可以用一个（ b ）唯一确定。
:
A、非零元素
B、三元组(i,j,a ij)
C、a ij
D、④i,j
6.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出线的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是（ B ）
A、2
B、3
C、5
D、6
7．算法指的是（ D ）
A．计算机程序B．解决问题的计算方法C．排序算法D．解决问题的有限运算序列8．线性表采用链式存储时，结点的存储地址（ B ）
A．必须是不连续的B．连续与否均可C．必须是连续的D．和头结点的存储地址相连续9．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ c ）
A．O（1）B．O（n）C．O（m）D．O（m+n）
10．由两个栈共享一个向量空间的好处是：（ b ）
}
A．减少存取时间，降低下溢发生的机率B．节省存储空间，降低上溢发生的机率
C．减少存取时间，降低上溢发生的机率D．节省存储空间，降低下溢发生的机率11．设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ d ）
A．front=front+1 B．front=(front+1)%(m-1) C．front=(front-1)%m D．front=(front+1)%m 12．如下陈述中正确的是（ a ）
A．串是一种特殊的线性表 B．串的长度必须大于零
C．串中元素只能是字母 D．空串就是空白串
13．一个非空广义表的表头（ d ）
A．不可能是子表 B．只能是子表C．只能是原子 D．可以是子表或原子
14、数据结构是研究数据的（c ）以及它们之间的关系。
-
A)理想结构和物理结构B)理想结构和抽象结构
C)物理结构和逻辑结构D)抽象结构和逻辑结构
15．设单链表中指针p指向接点A，若要删除A后的结点（若存在），则应执行的语句是( a ) A．p->next=p->next->next; B．p=p->next;
C．p=p->next->next; D．p->next=p;
二、填空题（共10小题，每小题2分）
1．数据的逻辑结构是从逻辑关系上描述数据，它与数据的__存储结构___无关，是独立于计算机的。
2.设S1=“good”，S2=“”，S3=“book”，则S1，S2和S3依次联接后的结果是good book 。
《
3.假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A[9][8][7]的存储地址是667 。
4．在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head 可用p表示为head=_ p－>next－>next ____。
5．栈顶的位置是随着_进栈和退栈____操作而变化的。
6．在串S=“structure”中，以t为首字符的子串有__12___个。
7．现有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。
表示该遗传关系最适合的数据结构为树。
8．在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点_____后续结点，其余每个结点有且只有_______个后续结点。
1、没有、1、没有、1
9.在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为____。
10.如果入栈序列是1，3，5，…，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为______。
三、判断题（每题1分，共5分）
【
1. 线性表的逻辑顺序与物理顺序总是一致的。
( F )
2 .线性表的顺序存储表示优于链式存储表示。
( F )
3．如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。
( F )
4. 空串与空格串是相同的( F )
5．进栈操作时，必须判断栈是否满。
( F )
四、程序填空题（每空1分，共5分）
下面是在单链表的第i个位置之前插入一个元素的算法，请将算法补齐。
status ListInsert_L(LinkList &L,int i,ElemType e){
p=L;j=0;
[
while(p&&j<i-1){p= ;++j;}
if(!p||j>i-1)return ERROR;
s=(LinkList) (sizeof(LNODE));
s->data= ;
___________=p->next;
p->next= ; return OK;}
p->next
malloc
e
：
s->next
s
五、算法题（每题10分，共40分）
1．2-14 （2）
2．2-15 （4）
3．3-7 4．3-11。