XX大学成人教育学院2022-2023学年度第二学期期末考试《数据结构》复习试卷.docx
XX大学成人教育学院2022-2023学年度第二学期期末考试数据结构复习试卷学习中心（教学点）批次：层次：专业：学号：身份证号：姓名：得分:一单选题（共10题，总分值20分，下列选项中有且仅有一个选项符合题目要求，请在答题卡上正确填涂。）1.在长为n的顺序表中删除一个数据元素，平均需移动（D）个数据元素。（2分）A.nB.n-1C.n/2D.（n-l）22 .在树形结构中，数据元素间存在（B）的关系。（2分）A.一对一B.一对多C.多对多D,除同属一个集合外别无关系3 .下列不属算法特性的是（D）。（2分）A.有穷性B.确定性C.零或多个输入D.健壮性4 .设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则判定该队中只有一个结点的条件是（C）。（2分）A.front->nextB.rear->nextC.front=rearD.front!=rear5 .在一个可存放n个数据元素的顺序栈中，假设以高地址端为栈底，以top为栈顶指针，当向栈中压入一个数据元素时，top的变化是（D）O（2分）A.不变B.top=nC.top+D.top-6 .判定一个栈顶指针为S且不带头结点的链栈为空栈的条件是（D）。（2分）A.SB.S->nextC.S->next=NULLD.!S7 .若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用（八）存储方式最节省时间。（2分）A.顺序表B.双链表C.带头结点的双向循环链表D,单循环链表8 .串的长度是指（B）O（2分）A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D,串中所含非空格字符的个数9 .下列说法中错误的是（B）。（2分）A.数据对象是数据的子集B.数据元素间关系在计算机中的映象即为数据的存储结构C.非顺序映象的特点是借助指示元素存储地址的指针来表示数据元素间逻辑关系D.抽象数据类型指一个数学模型及定义在该模型上的一组操作10 .设在一不带头结点的链队列中，front和。分别为其队头和队尾指针，则删除一个结点的操作是（C）。（2分）A. rear=front->nextC. front=front->nextB. rear=rear->nextD. front=rear->next二多选题（共6题，总分值12分，下列选项中至少有2个或2个以上选项符合题目要求，请在答题卡上正确填涂。）11 .下列关于链式存储结构的说法中，正确的是（ABD）。（2分）A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构；B.逻辑上相邻的结点物理上不必邻接；C.可以通过计算直接确定第i个结点的存储地址；D.插入、删除操作方便，不必移动节点12.下列叙述中错误的是（AB）。（2分）A.顺序文件不要求物理记录的顺序和逻辑记录的顺序一致；B.散列文件既适合随机存取，也适合顺序存取；C.按桶散列可减小内存开销，提高内存利用率；D.索引文件中包括文件数据区和索引表两大部分，其主文件关键字不一定有序13 .线性表（AC）。（2分）A.存在唯一的一个被称作“第一个"的数据元素；B.不存在唯一的一个被称作“第一个"的数据元素；C.存在唯一的一个被称作“最后一个的数据元素；D.不存在唯一的一个被称作“最后一个的数据元素14 .下列说法正确的有（BCE）。（2分）A.算法和程序原则上没有区别，在讨论数据结构时二者通用;B.从逻辑关系上讲，数据结构分为两大类：线性结构和非线性结构；C.所谓数据的逻辑结构是指数据元素之间的逻辑关系D.同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数相等；E.数据的逻辑结构与数据元素本身的内容和形式无关；F.数据结构是指相互之间存在一种或多种关系的数据元素的全体15 .下列数据结构中，属于线性数据结构的是（AB）。（2分）A.栈；B.队列；C.树；D.图16 .从表中任一结点出发都能扫描整个表的是（DE）。（2分）A.静态链表；B.单链表；C.顺序表；D.双链表；E.循环链表三判断题（共10题，总分值10分正确的填涂“A”，错误的填涂"B"o）17 .在一个设置有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。（1分）（B）18 .数据的逻辑结构是指数据的各数据项之间的逻辑关系。（1分）（B）19 .若一个栈的输入序列为U,2,3,4,5）,则不可能得到3,4,1,2,5这样的出栈序列。（1分）（B）20 .对顺序栈进行进栈、出栈操作不涉及元素的前、后移动问题。（1分）（八）21 .将长度分别为m,n的两个单链表合并为一个单链表的时间复杂度为0（m+n）.（1分）（B）22 .带头结点的单循环链表中，任一结点的后继结点的指针域均不空。（1分）（八）23 .算法可以没有输入，但是必须有输出。（1分）（八）24 .链表中逻辑上相邻的元素，其物理位置也一定相邻。（1分）（B）25 .对于顺序存储的长度为N的线性表，访问结点和增加结点的时间复杂度分别对应为0（1）和O（N）o（1分）（八）26 .在顺序表中逻辑上相邻的元素，其对应的物理位置也是相邻的。（1分）（八）四简答题（共2题，总分值20分）27 .设元素的入栈次序为a、b、c、d,且在入栈的过程中允许出栈，试写出所有不可能得到的出栈序列。(10分)答：dabcdacbdbacdbcadcabcadbcabdcdabbdacadbc28 .设n为正整数，试确定如下程序段中语句“x+;''的频度。for(i=l;i<=n;i+)for(j=l;j<=i;j+)for(k=l;k<=n;k+)×+;(Io分)j(÷1)答:2五综合题(共3题，总分值38分)29 .已知单链表L中含有三类字符的数据元素，即字母字符、数字字符和其他字符，试编写算法将L分割为三个循环链表，其中每个循环链表只含一类字符。(12分)答：voidpartition(LinkList&L,LinkList&LC,LinkList&LN,LinkList&L0)L带头结点，LC为含字母字符的循环链表，LN为含数字字符的循环链表，/LO为含其他字符的循环链表InitCL(LC);InitCL(LN);InitCL(LO);对三个循环链表进行初始化p=L->next;p指向第一个结点while(p)q二P；p=p->next;q指向当前待处理结点，p指向剩余链表if(q->data>三,A,&&q->data<=,Z,q->data>三,a,&&q->data<三,z,)q->next=LC->next;1.C->next=q;)字母字符入循环链表LCelseif(q->data>,0,&&q->data<,9,)q->next=LN->next;1.N->next=q:/数字字符入循环链表LNelseq->next=LO->next;1.O->next=q;)其他字符入循环链表LO!/whilefree(L);释放单链表L的头结点1/partitionvoidInitCL(LinkList&L)对循环链表进行初始化1.=(LinkList)mal1oc(sizeof(LNode);if(!L)exit(OVERFLOW);1.->next=L;)30 .设a=,datastructure*,b='computer*,c='demo,试求：(1)StrLength(a)的返回值;执行StrlnSert(b,4,c)后串b的值；(3)IndeX(a,'u',10)的返回值;(4)执行RePIaCe(a,lStructurHb)后串a的值；（5）执行SUbString（S,b,3,3）后串S的值。（13分）答：(1)14(2),comdemoputer,(3)12(4),datacomputer'(5),mpu,31.设单链表L如图所示:画出执行如下程序段后，各指针变量及单链表L的示意图。P=L;for(i=l;i<=3;i+)q=(LinkList)malloc(sizeof(LNode);q->data=i*3;q->next=p->ne×t;p->next=q;)(13分)答:
