数据结构习题参考答案

《数据结构习题参考答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、参考答案354参考答案参考答案354第1章一、选择题1.B2.C3.B4.C二、填空题1.数据、数据2.基本单位3.数据项、数据项4.相互关系、组织形式5.逻辑关系、逻辑关系、数学模型6.存储结构、存储结构7.数据的运算、数据的运算、数据的运算8.集合、集合9.线性结构10.树型结构11.多对多12.非线性结构、线性结构、非线性结构13.顺序存储14.链接存储15.稠密索引、稀疏索引、稠密索引、稀疏索引、稠密索引、稀疏索引16.散列存储17.有限序列18.有穷19.确定、相同20.可行、有限、具体实现21.正确性、可读性、健壮性、效率22.运行时间、所占据空间2

2、3.存储空间三、判断题1.错误：树型结构也可以用顺序方式进行存储。2.错误：数据元素是数据的基本单位，数据项是数据的最小单位。3.错误：算法用各种计算机语言描述表现为一个程序，但是不等于程序，程序逻辑不一定能满足有穷性。4.正确。5.正确。6.正确。7.正确。8.正确。四、综合题1.该算法的时间复杂度为：O(m×n)。2.该算法的时间复杂度为：O()3.该算法的时间复杂度为：O(m×n×t)。4.该算法的时间复杂度为：log3(n)。5.该算法的时间复杂度为：O()。第2章一、选择题1.A2.C3.A4.D5.D6.A7.B8.D9.B10.C11.C12.C1

3、3.D14.D二、填空题1.一对一2.直接前驱、直接后继3.有限序列、长度、空表4.顺序存储结构、逻辑顺序、地址相邻5.任意、任意、不连续、逻辑关系6.数据域、指针域、链域7.非顺序、非顺序映像8.循环链表9.双向链表10.所指向的结点本身11.P->next=p->next->next12.P->next->prior=P->prior13.线性表14.双链表15.n-i+116.n-i17.S->next=P->next;P->next=S18.p->prior->next=S;s->prior=p->prior;s->next=p;参考答案354p->pr

4、ior=s;19.head(tail(tail((head(tail(head(A))))))20.O(n)21.(L==L->Next)&&(L==L->Prior)22.线性23.顶三、判断题1.错误：链表存储中，结点之间可以连续也可以不连续，但结点内部是连续的。2.错误：头指针指向头结点而不是数据结点。3.错误：顺序存储的线性表可以随机存取。4.正确。5.错误。6.错误：顺序存储结构是静态存储结构，链式存储结构是动态存储结构。7.错误：先行表的长度是线性表中结点的个数。8.错误：注意最后一个结点。9.错误：也可以有顺序存储的形式。四、综合题1.将带头结点单

5、链表逆置的算法如下：voidreverse_list(linklist*head){/*逆置带头结点的单链表*/linklist*s,*p;p=head->next;/*p指向线性表的第一个元素*/head->next=NULL;/*初始空表*/while(p!=NULL){s=p;p=p->next;s->next=head->next;head->next=s;/*将s结点插入逆表*/}}/*reverse_list*/2.把这两个单链表合并成一个按升序排列的单链表，并用hc指向它的头结点的算法如下所示：linklist*combine_list(linkl

6、ist*ha,linklist*hb){/*ha,hb分别是两个按升序排列的,带有头结点的单链表的头指针，设计一个算法，把这两个单链表合并成一个按升序排列的单链表,并用hc指向它的头结点*/linklist*hc,*pa,*pb,*pc,*p,*q,*r;hc=(linklist*)malloc(sizeof(linklist));/*建立hc头结点*/p=hc;pa=ha->next;free(ha);/*释放ha头结点*/pb=hb->next;free(hb);/*释放hb头结点*/while(pa!=NULL&&pb!=NULL){q=(linklist

7、*)malloc(sizeof(linklist));/*产生新结点*/if(pb->datadata){q->data=pb->data;pb=pb->next;}else{q->data=pa->data;pa=pa->next;if(pa->data==pb->data)/*将相同的元素删除*/{r=pb;pb=pb->next;free(r);}}p->next=q;/*将结点链入c链表*/p=q;}while(pa!=NULL)/*a链表非空*/{q=(linklist*)malloc(sizeof(linklist));q->data=pa

8、->data;pa=pa