2023年春电大数据结构形考答案

一、单项选择题1.C2.D3.B4.C5.D6.C7.B8.C9.A10511.C12.D13.C14.A15.B16.C17.C18.B19.B20.D二、填空题lAA.n-i+142.n-ia.集合线性结构树形结构图状结构a.物理结构存储结构A5.线性结构非线性结构A.有穷性拟定性可形性有零个或多个输入有零个或多个输出.图状结构a.树形结构.线性结构.n—1O(n)A11,s—>next=p->next;a12.headaa13.q—>next=p->next;14^A.p->next=head;a15.单链表16.顺序存储链式存储17.存储结构“8.两个直接后继直接前驱尾结点头结点-19.头结点的指针指向第一个结点的指针420.链式链表④a三、问答题Q->rear=NULL;)44Voidenqueue(LinkQueue*Q,elemtypex)/*入队算法*/structnodes=(structnode*)malloc(sizeof(structnode));^As—>data=x；aif(Q->rear■二二NULL)/*原为空队时*/a(aQ—>rear=s;^As->next=s;else/*原队不为空时*/{ap=Q->rear->next;/*p指向第一个结点*/aQ—>rear->next=s；/*将s链接到队尾*/Q->rear=s;/*Q->rear指向队尾*As—>next=p；aa}aa}aaavoiddelqueue(LinkQueue*Q)/*出队算法*/structnode*t；aaif(Q->rear==NULL)a{aaprintf(n队列为空!\n”);areturn(0)”}Aelseif(Q->rear->next==Q->rear)/*只有一个结点时*/a9t=Q->rear;aQ—>rear=NULL；a}melse/*有多个结点时*/{at=Q—>rear->next；/*t指向第一个结点*/Q—>rear—>next=t->next;/*引成循环链*A八free(t)；aelemtypegethead(LinkQueue*Q)/*取队首元素算法*/{aaif(Q->rear==NULL)APrintf("队列为空!\n“)；Ae1sreturn(Q->rear->next->data);^}AAintemptyqueue(LinkQueue*Q)/*判断队列是否为空算法*/aa{if(Q->rear==NULL)return(l);/*为空，则返回true*/ae1sereturn(O)；/*不为空，则返回flase*/}AAvoiddispqueue(LinkQueue*Q)/*显示队列中元素算法*/{aastruetnode*p=Q—>rear->next；Aprintf("队列元素:");awhi1e(p!=Q->rear>A{aaprintf("%c",p—>data);ap=p->next;笔printf(n%c\n",p—>data);^}AAa六、完毕:实验2——栈、队列、递归程序设计根据实验规定（见教材P203）认真完毕本实验，并提交实验报告。1.简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现?答：若用结点表达某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表达称为数据的存储结构。可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表达。尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保存了逻辑结构的特点。采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大。a42.解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺陷。A答4顺序结构存储时,相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的一规定内存中存储单元的地址必须是连续的。A优点:一般情况下,存储密度大，存储空间运用率高。缺陷：（1）在做插入和删除操作时，需移动大量元素；⑵由于难以估计，必须预先分派较大的空间，往往使存储空间不能得到充足运用;⑶表的容量难以扩充。链式结构存储时，相邻数据元素可随意存放,所占空间分为两部分，一部分存放结点值，另一部分存放表达结点间关系的指针。4优点:插入和删除元素时很方便，使用灵活。a缺陷：存储密度小,存储空间运用率低。AAA3,什么情况下用顺序表比链表好？A答：顺序表适于做查找这样的静态操作，链表适于做插入和删除这样的动态操作。假如线性表的变化长度变化不大，且其重要操作是查找，则采用顺序表；假如线性表的长度变化较大，且其重要操作是插入、删除操作,则采用链表。皿4.解释头结点、第一个结点（或称首元结点）、头指针这三个概念的区别?答:A头结点是在链表的开始结点之前附加的一个结点；第一个结点（或称首元结点）是链表中存储第一个数据元素的结点；头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。A5.解释带头结点的单链表和不带头结点的单链表的区别。A答：4带头结点的单链表和不带头结点的单链表的区别重要体现在其结构上和算法操作上。A在结构上，带头结点的单链表，不管链表是否为空，均具有一个头结点，不带头结点的单链表不含头结点。a在操作上，带头结点的单链表的初始化为申请一个头结点。无论插入或删除的位置是地第一个结点还是其他结点，算法环节都相同。不带头结点的单链表，其算法环节要分别考虑插入或删除的位置是第一个结点还是其他结点。由于两种情况的算法环节不同。4aaa四、程序填空题1a（l）p->data二/（2）p->next=NULL3（AA）q->next=p（4）q=Paa2.a(1)head=ga(2)q=p3(aa)p->next=NULL(4)p->next=q->next(5)q—>next=pA3.aa(l)p=q->next-A2)q->next=p->nexMa五、完毕：实验1——线性表4根据实验规定(见教材P201-202丁认真完毕本实验，并提交实验报告。4作业2答录(本部分作业覆盖教材第3-5章的内容)aa一、单项选择题C2.B3.A4.C5.B6.A7.B8.C9.A10.Ca1LB12.C13.B14.B15.A16.C17.B18.A19.C20.Da2LB22.D23.C24.B25.D26.A27.C28.D29.D30.C31.A32.Daaa二、填空题41.后进先出皿2.下一个a.增1增144.假上溢5.a栈是否满s->top=MAXSlZE-l栈顶指针栈顶相应的数组元素栈是否空s->top=-1栈顶元素修改栈顶指针—6.bceda^7.终止条件递归部分以4.LU—>front==LU->rearA.运算符操作数ab+c/fde/a.s—>next=h;h=h->next；ar—>next=s；1-aa3.f=f->next;al4.字符a.顺序存储方式链式存储方式.0空格字符的个数a.特殊稀疏A.()(())2A19.((d,e,f))20.串长度相等且相应位置的字符相等21aA.i(i-1)/2+j224.行下标、列下标、非零元素三、问答题.简述栈和一般线性表的区别。a答：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。.简述队列和一般线性表的区别。AA队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。44.链栈中为什么不设头结点？皿答：由于链栈只在链头插入和删除结点,不也许在链表中间插入和删除结点，算法实现很简朴，所以一般不设立头结点。A.运用一个栈，则:a（1）假如输入序列由A,B工组成，试给出所有也许的输出序列和不也许的输出序列。2（皿）假如输入序列由A,B,C,D组成，试给出所有也许的输出序列和不也许的输出序列。答：（1）栈的操作特点是后进先出，因此输出序列有4A入，A出，B入,B出，C入C出，输出序列为ABCoA入，A出，B入，C入工出，B出，输出序列为ACB。aA入,B入,B出,A出,C入工出，输出序列为BAC。4A入,B入,B出，C入，C出，A出，输出序列为BCAoA入，B入，C入,C出，B出,A出,输出序列为CBA。由A,B,C组成的数据项，除上述五个不同的组合外，尚有一个C,A,B组合。但不也许先把C出栈，再把A出栈，（A不在栈顶位置），最后把B出栈，所以序列CAB不也许由输入序列A,B,C通过栈得到。2）按照上述方法，也许的输出序列有：ABCD,ABDC,ACBD,ACDB,ADCB,BACD,BADC,BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBAoa不也许的输出序列有:DABC,ADBC,DACB,DBAC,BDAC,DBCA,DCAB,CDAB,CADB,CABDAA5.用S表达入栈操作，X表达出栈操作，若元素入栈顺序为1234,为了得到1342出栈顺序,相应的S和X操作串是什么？④答:应是SXSSXSXX。各操作结果如下:aS1入栈◎X1出栈输出序列:14s2入栈S3入栈aX3出栈输出序列：13aS4入栈X4出栈输出序列：134aX2出栈输出序列:1342aa6.有5个元素，其入栈顺序为：A、B、C、D、E,在各种也许的出栈顺序中,以元素C、D最先的顺序有哪几个？A答:从题中可知，要使C第一个且D第二个出栈，应是A入栈,B入栈，C入栈，C出栈，D入栈。之后可以有以下几种情况：(1)B出栈，A出栈，E入栈，E出栈,输出序列为：CDBAEo(2)B出栈，E入栈,E出栈,A出栈，输出序列为CDBEA。a(3)E入栈,E出栈，B出栈，A出栈，输出序列为CDEBAa所以也许的顺序有:CDBAE,CDBEA,CDEBA.写出以下运算式的后缀算术运算超3x2+x-l/x+5a(2)(A+B)*C・D/(E+F)+Ga答；相应的后缀算术运算式aa⑴3x2八*x+1x/-5+aA(2)AB+C*DEF+/-G+4.简述广义表和线性表的区别和联系。a答:广义表是线性表的的推广,它也是n(n>0)个元素al,a2…ai…an的有限序列，其中ai或者是原子或者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这种特性，线性表可以当作广义表的特殊情况，当ai都是原子时，广义表退化成线性表。Aa四、程序填空题a1.a(1)q—>front->next=p->next;a(2)free(p)泠(3)q->rear=q->front五、综合题al.a答：出队序列是e2,e4,e3,e6,e5,e1的过程：aa⑴el入栈(栈底到栈顶元素是e1)aa⑵e2入栈(栈底到栈顶元素是el,e2)去⑶e2出栈(栈底到栈顶元素是e1)(4)e3入栈(栈底到栈顶元素是el,e38a(5)e4入栈(栈底到栈顶元素是el,e3,e4)e4出栈（栈底到栈顶元素是el,e3）⑺e3出栈（栈底到栈顶元素是e1.⑻e5入栈（栈底到栈顶元素是el,e5）-⑼e6入栈（栈底到栈顶元素是el,e5,e6）我0）e6出栈（栈底到栈顶元素是el,e5）01）e5出栈（栈底到栈顶元素是el）我2）el出栈（栈底到栈顶元素是空）△栈中最多时有3个元素,所以栈S的容量至少是3o2.4算法设计如下:4/*只有一个指针rear的链式队的基本操作*/a#include<stdio.hx^typedef