数据结构 习题与解答

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

1、数据结构习题第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表第六章树和二叉树第七章图第八章动态存储管理第九章查找第十章内部排序第十一章外部排序11.1简述下列术语:数据结构、存储结构、数据类型和抽象数据类型.1.2若n为正整数，计算下列式子的时间复杂度。（1）for(i=0;i

2、*n);（2）T（n）=O(n*n);32.1已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a.在P结点后插入S结点的语句序列是__4.1____b.在P结点前插入S结点的语句序列是_7.11.8.4.1__________c.在表首擂入S结点的语句序列是__5.12____d.在表尾插入S结点的语句序列是___9.1.6______(1)P->next=S;(2)P->next=P->next->next;(3)P->next=S->next;(4)s->

3、next=P->next;(5)S->next=L;(6)S->next=NULL;(7)Q=P;(8)while(P->next!=Q)P=P->next;(9)while(P->next!=NULL)P=P->next;(10)P=Q;(11)P=L;(12)L=S;(13)L=P;42.2已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列.a.删除P结点的直接后继结点的语句序列__11.3_.14____c.删除P结点的语句序列是____10.12.7.

4、3.14_________d.删除首元结点的语句序列是_12.11.3.14e.删除尾元结点的语句序列是____9.11.3.14_____(1)P=P->next,(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)

5、P=P->next;(9)while(P->next->next!=NULL)P=P->next;(10)Q=P,(11)Q=P->next;(12)P=L;(13)L=L->next;(14)free(Q);52.3对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。typedefstructnode{intdata;structnode*next;}linknode,*link;voidInsertsort(linkL){linkp,q,r,u;p=L->

6、next;(1)______;while((2)________){r=L;q=L->next;while((3)________&&q->data<=p->data){r=q;q=q->next;}u=p->next;(4)______;(5)______;p=u;}}62.4设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性.2.5假设有两个元素值递增有序排列的线性表A和B,均以单链表作存储结构,请编写算法将A表和B表归并成一个按元素值递增有序(即非递增有序,允许表中含有

7、值相同的元素)排列的线性表C,并要求利用原表(即A表和B表)的结点空间构造C表.7答案：2.1a{4-1};b{7-11-8-4-1};c{5-12};d{9-16}2.2a{11-3-14};b{10-12-7-3-14};c{12-11-3-14};d{11-3-14}2.3(1)L->next=null∥置空链表,然后将原链表结点逐个插入到有序表中(2)p!=null∥当链表尚未到尾，p为工作指针(3)q!=null∥查p结点在链表中的插入位置，这时q是工作指针。(4)p->next=r->next∥将p结点链入

8、链表中(5)r->next=p∥r是q的前驱，u是下个待插入结点的指针。82.4StatusInsert_SqList(SqList&va,intx)//把x插入递增有序表va中{if(va.length+1>va.listsize)returnERROR;va.length++;for(i=va.length-1;va.e