《数据结构》习题集答案：第2章线性表.doc

数据结构课后练习题参考答案 第2章 线性表第2章 线性表参考答案一、 选择题1、E，A 2、C 3、B 4、D 5、B 6、A 7、C 8、B 9、A 10、B 11、C 12、D 13、D 14、A，C，D 15、A 16、D 17、B 18、A 19、B 20、C21、A 22、D 23、D二、 填空题1、没有；12、表中一半；该元素的位置3、（1）FC （2）BIAG4、（1）HGBJ （2）HFDBJ5、（1）FAI （2）EGDFAI6、 n/2, n/4（此题有误！另作说明）7、O(1 ) O(n)8、线性表9、插入和删除首元素时不必进行特殊处理10、其直接前趋结点的链域11、q-prior=p;12、前趋结点，后继结点13、必定，不一定14、结点、第一个、最后一个、位置、前驱、后继15、前驱、前驱、后继、后继16、线性17、线性、长度18、pnext=NULL;三、 判断题1. 2.X 3. 4.X 5. 6. 7.X 8. 9.X 10.X四、 简答题1、宜采用链式存储结构，因为它使线性表的插入和删除操作的时间复杂度为O（1），而顺序存储结构的为O（n）。2、首元结点是指链表中存储线性表中第一个数据元素的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存线性表的数据元素，其作用是为了对链表进行操作时，可以对空表非空表的情况以及对首元结点进行统一的处理。头指针是指向链表第一个结点（头结点或首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。3、在等概率前提下，平均每插入一个元素需要移动的元素个数为(0+1+2+n)/(n+1)=n/2。若元素插在ai 与ai+1 间（0=i=n-1）的概率为2(n-i)/(n(n+1)，则平均每插入一个元素所要移动的元素个数为：（2n+1）/34、解答：单循环链表中无论设置尾指针还是头指针都可以任一结点从遍历表中其它结点，但设置尾指针时，若在表尾进行插入或删除操作时可在O(1)时间内完成，同样在表头进行插入或删除操作时也可在O(1)时间内完成。但设置的是头指针，表尾进行插入或删除操作，需要遍历整个链表，时间复杂度为O(n)。5、解答：能删除。双链表上删除p 所指向的结点的时间复杂度为O(1)，单循环链表上删除p 所指向的结点的时间复杂度为O(n)。6、解答：如果长度大于 1，则将首元结点删除并插入到表尾。7、解答：应选用链式存储结构。因为顺序表是静态存储结构，只能预先分配存储单元，不能随着线性表长度的改变而变化。而链表则可根据需要动态的申请空间，因此适用于动态变化表长的线性表。8、解答：应该用顺序存储结构。因为顺序存储结构存取元素操作的时间复杂度为 O(1)。9、解答：用单链表表示多项式，除指针域外需设置两个数据域，一个用来存储系数，一个用来存储指数。五、 设计题1、void split(SqList A,SqList &B,SqList &C)/采用顺序存储结构实现int I;B.length=C.length=0;for(I=0;I0)B.elemB.length=A.elemi;B.length+;elseC.elemC.length=A.elemi;C.length+;2、status ListInsert(SqList &L,ElemType e)ElemType *p,*q,*newbase;int j;if(L.length=L.listsize)newbase=(ElemType )realloc(L.elem,(L.listsize+LISTINCRMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize=+LISTINCRMENT;For(j=L.length-1;j=0&eL.elemj;j-)L.elemj+1=L.elemj;L.elemj+1=e;+L.length;return OK;3、提示：两个表的公共元素指的是既存在于A 表中，也存在于B 表中的元素，为了操作方便，先让单链表C 带有一个头结点c，再后将其删除。LinkList Inter_eq(LinkList a,LinkList b)LinkList p,q,r,c;c=(LinkList)malloc(sizeof(LNode);/建立单链表C 的头指针r=c;p=a;q=b;while(p&q)if(p.dataq.data)q=q.next;else /找到元素值相同的结点s=(LinkList)malloc(sizeof(LNode);s.data=p.data;r.next=s;r=s; /把s 结点链到c 的末尾，r 始终指向链表C 的最后一个结点while(p.data=p.next.data)p=p.next; /跳过相同的值的结点p=p.next;while(q.data=q.next.data)q=q/next;q=q.next;r.next=NULL;s=c;c=c.next;free(c); /删除C 链表的头结点return (c);4、参考程序：void outmin(LinkList L)LinkList p=L,q=L;int temp;while(q)if(p.dataq.data)p=q;q=q.next;printf(“%d”,p.data);if(p.next)if(p.data%2=1)temp=p.d