资源描述：
《数据结构部分习题与解答》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第二章线性表一、基础知识题2.1试描述头指针、头结点、开贻结点的区别、并说明头指针和头结点的作用。答：开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。链表的头指针是一指向链表开始结点的指针(没冇头结点时)，单链表由头指针唯-确定，因此单链表可以用头指针的名字來命名。头结点是在链表的开始结点Z前附加的一个结点。有了头结点Z厉，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作-•致(都是在某一结点之后)。2.2何时选用顺
2、序衣、何时选用链衣作为线性衣的存储结构为宜？答：在实际应用屮，应根据具体问题的要求和性质來选择顺序表或链表作为线性表的存储结构，通常右以下几方面的考虑：1•基于空间的考虑。当要求存储的线性衣长度变化不人，易于事先确定其人小时，为了节约存储空间,宜采用顺序表;反Z,当线性表长度变化人，难以估计其存储规模时，采用动态链表作为存储结构为好。2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入利删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储
3、结构。并若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。2.3在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决丁•哪两个因索？答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-l)/2个结点。具体的移动次数取决于顺序衣的长度n以及需插入或删除的位置i。i越接近n则所需移动的结点数越少。2.4为什么在单循环链表中设置尾指针比设置头指针更好？答：尾指针是指向终端结点的指针，用它來表示单循坏链表可以使得杳找链表的开始
4、结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear,则开始结点和终端结点的位置分别rear->next->next和rear,S找时间都是0(1)。若用头指针來表示该链表，则査找终端结点的时间为0(n)。2.5在单链表、双链表和单循坏链表中,若仅知道指针p指向某结点,不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少？答：卜•面分别讨论三种链表的情况。1•单链表。若指针P指向某结点时，能够根据该指针找到其直接后继，能够顺后继指针链找到*P结点后的结点。但是
5、由于不知道其头指针，所以无法访问到P指针指向的结点的直接前趋。因此无法删去该结点。2.双链表。由于这样的链衣提供双向指针，根据*p结点的前趋指针和后继指针可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为0(1)。2.单循环链表。根据已知结点位置，可以直接得到其后相邻的结点位置(直接后继)，乂因为是循环链表，所以我们可以通过査找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。2.6下述算法的功能是什么？LinkListDemo(LinkListL){//L是
6、无头结点单链农ListNode*Q,*P;if{L&&L->ncxt){Q-L;L=L->next;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;}returnL;}//Demo答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原來的第二个结点成为新的开始结点，返回新链表的头指针。二、算法设计题2.7设线性表的n个结点定义为(a0,a
7、,...an.
8、),重写顺序表上实现的插入和删除算法：InsertList和Delete
9、List.解：算法如下：//defineListSize100//假定表空间大小为100typedefiniDataType;//假定DataType的类型为int型typedefstruct{DataTypedata[ListSizc];//向量data用于存放表结点intlength;//当前的农长度}Seqlist;〃以上为定义表结构voidInsertList(Scqlist*L,Datatypex,inti){〃将新结点x插入L所指的顺序表的第i个结点ai的位置上，即插入的合法位置为：0<
10、=iv=L->lengthintj；if(i<0
11、
12、i>L->length)Error("positionerror");//非法位置，退出，该函数定义见教材P7.if(L->length>=ListSize)Errofoverflow");for(j=L->lcngth-l;j>=i;j-)L->data[j+1]=L->data[j];L->data[i]=x;L->length++;}voidDeleteList(Seqlist*L,inti){//从L所指的顺
