数据结构（思政版）习题解答 第2章 线性表

第二章线性表一、选择题1B；2C；3A；4D；5B；6D；7B；8C；9B；10A；11C；12D；13D；14C二、填空题1、O(1),O(n)；2、单链表，双链表；3、相邻地址，指针；4、4，2；5、便于从任何头结处开始查找；6、前驱；7、L->next=L->prior=L；8、顺序；9．、O(1),O(n)；10．逻辑顺序与物理顺序一致、可随机访问、节省存储空间、占用连续存储空间、不便于插入、删除和动态增长。11．不需占用连续存储空间，便于插入、删除和动态增长，不能随机访问、只能顺序存取，需额外存储空间；12．在任何位置插入和删除操作一致；13．指针；14．DL=NULL；15．(1)i<=S.length∥L.length为元素个数(2)j++∥有值不相等的元素(3)S.a[j]:=S.a[i]∥元素前移(4)L.length=j∥元素个数16．p->Llink->Rlink=p->Rlink;p->Rlink->Llink=p->Llink.三、问答题与算法题1、头指针：结点或头结点的指针变量。其作用是存放第一个结点或头结点的地址，从头指针出发可以找到链表中所有结点的信息。头结点：是附加在链表的第一个结点之前的一个特殊结点，其数据域一般不存放信息。其作用是为了简化运算，将空表与非空表统一起来，将第一个结点与其他结点的处理统一起来。首结点：是链表的第一个结点。2、(1)基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。(2)基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。3、尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next和rear,查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)4、将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针5、S=P->Prior;P->Prior=S->Prior;S->Prior->Next=P;S->Prior=P;S->Next=P->Next;P->Next=S;S->Next->Prior=S;6、15，26，51，37，48，55。四、算法设计题1、CreatList_L(LinkList&Lintn){L=(LinkList)molloc(sizeof(Lnode));//建立头结点L->next==NULL;q=L;For(i=1;i<=n;++i){P=(LinkList)molloc(sizeof(Lnode));Scanf(&(p->data));p->next=NULL;q->next=p;q=p;}returenOK;}2、Voidsinsert(Sqlist&S,intx){inti=0;n=S.Length;while(x<S.elem[i]&&i<n)i++;//查找插入点if(i==n)S.elem[n]=x;//插在最后一个结点的后面else{for(j=n-1;j>=i;j++)S.elem[j+1]=S.elem[j];//元素后移S.elem[i]=x;//插入}}3、intListLength(LinkListL){q=L->next;i=0;while(q){i++;q=q->next;}returni;}4、intdelete(LinkList&L,intx){p=L->next;//p为定位指针q=L;//q为定位指针的前导while((p->data!=x)&&p){q=p;//q前进p=p->next;//p前进}if(!q)returnERROR;//查找失败q->next=p->next;free(p);returnOK;}5、voidmergelist(linklist&La,linklistLb){pa=La->next;pb=Lb->next;pc=La;while(pa&&pb)if(pa->data<pa->data){pc->next=pa;pc=pa;pa=pa->next;}elseif(pa->data==pa->data){pc->next=pa;pc=pa;pa=pa->next;pb=pb->next;}else({pc->next=pb;pc=pb;pb=pb->next;}pc->next=pa?pb:pb;}6、Voidinvertlinklist(linklist&L){if(!L)returnOK;//空表p=L->next;if(!p)returnOK;//仅有一个结点的表else{q=p->next;//q指向p的后继p->next=NULL;while(q){r=q->next;//r指向q的后继q->next=p;//逆置p=q;//p前进q=r;//q前进}L=p;//第一个结点}}7、VoiddelDuplicate(intA[]，int&n){for(i=0;i<