ds02线性表习题参考解答

《ds02线性表习题参考解答》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性表第2章线性表习题参考解答一、简答题1．试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。【答】头指针：是指向链表中的第一个结点的指针。头结点：在开始结点之前附加上的一个结点。开始结点：链表的第一个结点。头指针是一个指向地址的变量，用于表示一个链表的开始。引入头结点可以更加方便的进行链表是否为空的判断，同时方便了插入和删除结点。开始结点用于存储链表的第一个数据元素。2．何时选用顺序表、何时选用链表作为线性表的存储结构为宜?【答】顺序表中查找元素、获取表长非常容易，但是，要插入或者删除一个元素却需要移动大量的元

2、素；相反，链表中却是方便插入或者删除元素，在查找元素的是，需要进行遍历。因此，当所涉及的问题常常进行查找等操作，而插入、删除相对较少的是，适合采用顺序表；当常常需要插入、删除的时候，适合采用链表。3．为什么在单循环链表中设置尾指针比设置头指针更好?【答】在单循环链表中，设置尾指针，可以更方便的判断链表是否为空。4．在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?【答】本题分三种情况讨论：1、单链表：当知道指针p指向某结点时，能够根据该指针找到其直接后继，但是不知道头指针，因此不

3、能找到该结点的直接前趋，因此，无法删除该结点。2、双链表：根据指针p可以找到该结点的直接前趋和直接后继，因此，能够删除该结点。3、单循环链表：和双链表类似，根据指针p也可以找到该结点的直接前趋和直接后继，因此，也可以删除该结点。5．下述算法的功能是什么?LinkListDemo(LinkList*L)/*L是无头结点单链表*/{LNode*Q,*P;if(L&&L->next){Q=L;L=L->next;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;}returnL;}/*De

4、mo*/【答】将原来的第一个结点变成末尾结点，原来的第二个结点变成链表的第一个结点。二、算法设计题1．试分别用顺序表和单链表作为存储结构，实现将线性表(a0,a1,...an-1第二章线性表)就地逆置的操作，所谓"就地"指辅助空间应为O(1)。【答】分两种情况讨论如下。①顺序表：要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。算法如下：voidreverlist(sequenlist*L){datatypet;/*设置临时空间用于存放data*/inti;for(i=0;

5、ilength/2;i++){t=L->data[i];/*交换数据*/L->data[i]=L->data[L->length-1-i];L->data[L->length-1-i]=t;}}②链表：可以利用指针的指向转换来达到表逆置的目的。算法是这样的：LinkList*reverselist(LinkList*head)/*将head所指的单链表逆置*/{LNode*p,*q;/*设置两个临时指针变量*/if((head->next!=NULL)&&(head->next->next!=NULL))/*当链表不是空表或单

6、结点时*/{p=head->next;q=p->next;p->next=NULL;/*将开始结点变成终端结点*/while(q)/*每次循环将后一个结点变成开始结点*/{p=q;q=q->next;p->next=head->next;head->next=p;}returnhead;}returnhead;/*如是空表或单结点表，直接返回head*/}2．顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。【答】因已知顺序表L是递增有序表，所以只要从头找起找到第一个比它大（或相等）的结点数据，把x插入到这个数

7、所在的位置就是了。算法如下：voidInsertIncreaseList(Sequenlist*L,Datatypex){inti;第二章线性表for(i=0;ilength&&L->data[i]

8、，请分析你的算法的时间复杂度。【答】算法如下：LinkList*Link(LinkList*L1,LinkList*L2){/*将两个单链表连接在一起*/LNode*p,*q;p=L1;q=L2;while(p->nex