期中考试试卷答案

期中考试试卷答案期中考试试卷答案期中考试试卷答案资料仅供参考文件编号：2022年4月期中考试试卷答案版本号：A修改号：1页次：1.0审核：批准:发布日期：单项选择题（共15小题，每小题2分，共30分）1.一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（b）。

A、23415

B、54132

C、23145

D、154322.设循环队列中数组的下标范围是1-n，其头尾指针分别为f和r，则其元素个数为（d）。

A、r-f

B、r-f+1

C、(r-f)modn+1

D、(r-f+n)modn3.对于C语言的二维数组DataTypeA[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j]的存储位置可由(c)式确定.A、Loc[i,j]=A[m,n]+[(n+1)*i+j]*kB、Loc[i,j]=loc[0,0]+[(m+n)*i+j]*kC、Loc[i,j]=loc[0,0]+[n*i+j]*kD、Loc[i,j]=[(n+1)*i+j]*k4．如果以链表作为栈的存储结构，则退栈操作是(B)A、必须判别栈是否满B、必须判别栈是否空C、判别栈元素的类型D、对栈不做任何操作5．基于三元组的稀疏矩阵，对每个非零元素aij,可以用一个（b）唯一确定。A、非零元素B、三元组(i,j,aij)C、aijD、④i,j6.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出线的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是（B）A、2B、3C、5D、67．算法指的是（

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+1B．front=(front+1)%(m-1)C．front=(front-1)%m

D．front=(front+1)%m12．如下陈述中正确的是（

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依次联接后的结果是goodbook。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、没有、19.在一个长度为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个位置之前插入一个元素的算法，请将算法补齐。statusListInsert_L(LinkList&L,inti,ElemTypee){p=L;j=0;while(p&&j<i-1){p=;++j;}if(!p||j>i-1)returnERROR;s=(LinkList)(sizeof(LNODE));s->data=;___________=p->n