《数据结构课后练习第2章.ppt》由会员分享，可在线阅读，更多相关《数据结构课后练习第2章.ppt（24页珍藏版）》请在三一办公上搜索。
1、第二章 线性表,2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现2.4 一元多项式的表示及相加,学习要点,了解线性表的逻辑结构特性，即数据元素之间存在着线性关系，在计算机中表示这种关系两类不同的存储结构：顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。熟练掌握这两类存储结构的描述方法，如一维数组中一个区域i.j的上、下界和长度之间的变换公式（L=j-i+1,i=j-L+1,j=i+L-1），链表中指针p和结点*p的对应关系（结点*(p-next)是结点*p的后继等），链表中头结点、头指针和首元结点（第一个元素的结点）
2、的区别及循环链表、双向链表的特点等。链表是本章的重点和难点，掌握指针操作和内存动态分配的编程技术。,学习要点,熟练掌握在顺序存储结构上线性表的基本操作，如查找、插入和删除的算法。熟练掌握在各种链表结构中线性表的基本操作，能在实际应用中选用适当的链表结构。能够从时间与空间复杂度方面综合比较线性表两种存储结构的不同特点及其适用场合。,一、判断对错题,1.线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（）2.线性表的链式存储结构优于顺序存储。（）3.在单链表中，任何两个元素的存储位置之间都有固定的联系，所以可以从头结点开始查找任何一个元素。（）4.顺序
3、存储的线性表可以实现随机存取。（）,二、单项选择题,1.用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个是_。A.当前结点所在的地址域B.指针域C.空指针域D.空闲域2.在具有n个结点的单链表中，实现_的操作，其算法的时间复杂度都是O(n)。A.遍历链表和求链表的第i个结点B.在地址为p的结点之后插入一个结点C.删除开始结点D.删除地址为p的结点的后继结点,B,A,二、单项选择题,3.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为da1，则第i个结点的地址为_。A.da1+(i-1)mB.da1+imC.da1-imD.da1+(i+1)m4.在
4、n个结点的顺序表中，算法的时间复杂度是O(1)的操作是_。A.访问第i个结点（1in）和求第i个结点的直接前驱（2in）B.在第i个结点之后插入一个新结点（1in）C.删除第i个结点（1in）D.将n个结点从小到大排序,A,A,二、单项选择题,5.两个指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素前驱的条件是_。A.p-next=q-nextB.p-next=qC.q-next=pD.p=q,B,三、填空题,1.在链表中逻辑上相邻的元素的物理位置_相连。2.在n个结点的顺序表中删除一个结点平均需要移动_个结点，具体的移动次数取决于_。3.在单链表中要在已知结点*p之前插入一个新结
5、点，需找到_。,不一定,(n-1)/2,顺序表的长度与被删元素在表中的位序,结点*p的直接前驱结点（的地址）,四、简答题,1.简述线性表的存储结构及各自的优点。何时选用顺序表、何时选用链表作为线性表的存储结构为宜？,从空间上来看：当线性表的长度变化较大、难以估计其规模时，选用动态的链表作为存储结构比较合适。但链表除了需要设置数据域外，还要额外设置指针域，因此当线性表长度变化不大、易于事先确定规模时，为了节约存储空间，宜采用顺序存储结构。,四、简答题,1.简述线性表的存储结构及各自的优点。何时选用顺序表、何时选用链表作为线性表的存储结构为宜？,从时间上来看：若线性表的操作主要是查找，很少进行插入
6、和删除操作时，应选用顺序表。对于频繁进行插入和删除操作的线性表，宜采用链表作为存储结构。,四、简答题,2.什么是头指针、头结点、首元结点。,首元结点：链表中存储的线性表中的第一个数据元素的结点。头结点：为了操作的方便，通常在链表的首元结点之前附设一个结点，称头结点。头指针：指向链表中的第一个结点（或为头结点或为首元结点）的指针。,四、简答题,3.在顺序表中插入和删除一个结点需平均移动多少个结点？具体的移动次数取决于哪两个因素？,插入结点：移动元素次数n-i+1；删除结点：移动元素次数n-i。决定因素：顺序表的长度以及插入、删除元素在表中的位序。,4.分析下述三个算法的具体功能。ListNode
7、*Demo1(LinkList L,ListNode*p)/L是有头结点的单链表 ListNode*q=L-next;while(q,算法功能：寻找*p结点的直接前驱结点*q。,4.分析下述三个算法的具体功能。void Demo2(ListNode*p,ListNode*q)/p，*q是链表中的两个结点 DataType temp;temp=p-data;p-data=q-data;q-data=temp;,算法功能：*p结点和*q结点的值互换。,4.分析下述三个算法的具体功能。LinkList test1(LinkList L)/L是无头结点的单链表LinkList*q,*p;if(L,算法
8、功能：如果表长度大于1，则将首元结点删除并插入到表尾。或者可以这么说：把表(a1,a2,ai,an)改成(a2,a3,ai,an,a1)。,5.设有多项式 请画出 的单链表存储表示。设，求得并画出的单链表存储表示。,五、程序设计题,1.对给定的带头结点的单链表L，编写一个删除L中值为x的结点的直接前驱结点的算法。,Status ListDelete _L(LinkList L，ElemType x)/在带头结点的单链表L中，删除值为x的结点。LNode*p,*q;p=L;while(p-next,线性表的结构定义：-线性表的动态分配顺序存储结构-#define LIST_INIT_SIZE 1
9、00/顺序表的初始分配量#define LISTINCREMENT 10/顺序表的分配增量typedef structElemType*elem;/存储空间基址：即数组的起始地址int length;/顺序表的当前长度：实际的元素个数int listsize;/当前分配的存储容量（以sizeof（ElemType）为单位）SqList;,2.将一个顺序表中从第i个结点开始的k个结点删除。,Status ListDelete_Sq(SqList/从最后一个元素开始,if(k=(q-p)+1)/第i个元素后的所有元素均被删除 L.length=i-1;return OK;elsefor(;k=1;
10、k=1;-k;)for(+p;p=q;+p)*(p-1)=*p;/到第i+1个元素平移 p+;-L.length;q=L.elem+L.length 1;return OK;/返回删除元素成功标志,有没有更快的方法？比如若干元素依次前移k位？如何实现？,五、程序设计题,3.设顺序表L是一个递增（允许有相同的值）有序表，试写一算法将x插入L中，并使L仍为一个有序表。,3.设链表L是一个递增（允许有相同的值）有序表，试写一算法将x插入L中，并使L仍为一个有序表。,算法分析：先找到x的正确插入位置；（插入位i的确定）然后在链表中最后一个小于或等于x的元素结点以及第一个大于x的元素结点之间插入新的元素结点x。（单链表的插入操作）,Status LinkListInsert(LinkList L,ElemType x)/在升序链表L（带头结点）中插入一个新元素结点x q=L;p=q-next;/找到插入位置 while(p!=NULL/LinkListInsert,/-线性单链表存储结构-typedef struct LNode ElemType data;/数据域 struct LNode*next;/指针域LNode,*LinkList;/*LinkList应该为指向线性单链表结点的指针,结束,
