2016数据结构与算法离线作业

《2016数据结构与算法离线作业》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、浙江大学远程教育学院《数据结构与算法》课程离线作业姓名:年级:学号:学习中心:一、填空题：(【序号，章，节loooooo)【1,1,2】线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系,图形结构中元素之间存在多对多关系。【2,1,2】为了最快地存取数据元素，物理结构宜采用顺序存储结构。[3,1,2】存储结构可根据数据元素在机器中的位置是否一定连续分为」®序在储结堂，链式存储结构。【4,1,3】度量算法效率可通过时间复杂度来进行。[5,1,3】设n为正整数，下面程序段中前置以记号@

2、的语句的频度是—n(n+l)/2—Ofor(i=0;i0;}[6,1,3】设n为正整数，试确定下列各程序段中前置以记号@的语句的频度:(1)i=l;k=0;while(i<=n-l){i卄；@k+=10*i;〃语句的频度是ipIo(2)k=0;for(i=l;i<=n;i++){for(j=i；j<=n;j++)@k++;//语句的频度是[7,3,2】线性表（％,a2,aj有两种存储结构：顺序存储结构和链式存储结

3、构,请就这两种存储结构完成下列填充：顺序存储密度较大;顺序存储利用率较高；_顺序—可以随机存取；链式不可以随机存取;链式插入和删除操作比较方鼠[8,3,2]从一个长度为n的顺序表中删除第i个元素（lnext二NULL【10,3,2】在一个单链表中p所指结点（p所指不是最后结点）之后插入一个由指针s所指结点，应执行s・>next=p・>next;和p->next=s的操作。【11,3,2】在一个单链

4、表中删除p所指结点时，应执行以下操作:q=p->next;p->data=p->next->data;D・>next=p・>next・>next;frcc(q);【12,3,2】带头结点的单循环链表Head的判空条件是_Head・>next==Head；不带头结点的单循环链表的判空条件是—Head二二NULI,。【13,3,2］已知L是带表头结点的非空单链表，且P结点既然不首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a.删除P结点的直接前驱结点的语句序列是—101281141

5、4一。b.删除结点P的语句序列是10127314。c.删除尾元结点的语句序列是911314。(1)P=P->ncxt;(2)P->next=P;(3)P->next=P->next・>next;(4)P=P->next->next;(5)while(P!=NULL)P=P->next;(6)while(Q->next!=NULL){P=Q;Q=Q->next};(7)while(P->next!=Q)P=P->next;(8)while(P->next->next!=Q)P=P->next;(1)

6、while(P->next->next!=NULL)P=P->next;(2)Q=P;(3)Q=P->next;(4)P=L;(5)L=L->next;(6)free(Q);【14,3,3］对一个栈，给定输入的顺序是A、B、C,则全部不可能的输出序列有不可能得到的彳出序列有CAB【15,3,3】.在栈顶指针为HS的链栈屮，判定栈空的条件是—h£ad・>iwxt=NULL【16,3,3】下列程序把十进制数转换为十六进制数，请填写合适的语句成分。voidconversion10_16(){InitSt

7、ack(&s);scanf(“％d'',&N);while(N){Push6N%16)_:N=N/16;}whilc(!StackEmpty(s)){_Fop6e);if(e<=9)printf(t<%d,e);elseprintf(“％c",e・10+'A‘)；}}/*conversion*/【17,3,4］若用一个大小为6个元素的数组来实现循环队列，且当前rear=0和front=3o当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是一2和4。【18,3,4】堆栈和队列

8、都是线性表，堆栈是后进先出的线性表.而队列是—先进先出的线性表。【19,3,4】若用一个大小为6个元素的数组來实现循环队列，且当前rear=0和front=3□当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是2和4。[20,4,2]已知一棵树边的集{,,,,,,,,}o那么根结点是点b的双亲是一d结点a的子孙有bcdj树的深丿戛是是一3,结点g在树的第3层。【21,4,