第二章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4一元多项式的表示及相加学习要点1.了解线性表的逻辑结构特性，即数据元素之间存在着线性关系，在计算机中表示这种关系两类不同的存储结构：顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。2.熟练掌握这两类存储结构的描述方法，如一维数组中一个区域[i..j]的上、下界和长度之间的变换公式（L=j-i+1,i=j-L+1,j=i+L-1），链表中指针p和结点*p的对应关系（结点*(p->next)是结点*p的后继等），链表中头结点、头指针和首元结点（第一个元素的结点）的区别及循环链表、双向链表的特点等。链表是本章的重点和难点，掌握指针操作和内存动态分配的编程技术。学习要点3.熟练掌握在顺序存储结构上线性表的基本操作，如查找、插入和删除的算法。4.熟练掌握在各种链表结构中线性表的基本操作，能在实际应用中选用适当的链表结构。5.能够从时间与空间复杂度方面综合比较线性表两种存储结构的不同特点及其适用场合。一、判断对错题1.线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（）2.线性表的链式存储结构优于顺序存储。（）3.在单链表中，任何两个元素的存储位置之间都有固定的联系，所以可以从头结点开始查找任何一个元素。（）4.顺序存储的线性表可以实现随机存取。（）√××√二、单项选择题1.用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个是______。A.当前结点所在的地址域B.指针域C.空指针域D.空闲域2.在具有n个结点的单链表中，实现______的操作，其算法的时间复杂度都是O(n)。A.遍历链表和求链表的第i个结点B.在地址为p的结点之后插入一个结点C.删除开始结点D.删除地址为p的结点的后继结点BA二、单项选择题3.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为da1，则第i个结点的地址为______。A.da1+(i-1)×mB.da1+i×mC.da1-i×mD.da1+(i+1)×m4.在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是______。A.访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B.在第i个结点之后插入一个新结点（1≤i≤n）C.删除第i个结点（1≤i≤n）D.将n个结点从小到大排序AA二、单项选择题5.两个指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素前驱的条件是______。A.p->next==q->nextB.p->next=qC.q->next=pD.p==qB三、填空题1.在链表中逻辑上相邻的元素的物理位置__________相连。2.在n个结点的顺序表中删除一个结点平均需要移动__________个结点，具体的移动次数取决于_______________________________________________。3.在单链表中要在已知结点*p之前插入一个新结点，需找到______________________________。不一定(n-1)/2顺序表的长度与被删元素在表中的位序结点*p的直接前驱结点（的地址）四、简答题1.简述线性表的存储结构及各自的优点。何时选用顺序表、何时选用链表作为线性表的存储结构为宜？•从空间上来看：当线性表的长度变化较大、难以估计其规模时，选用动态的链表作为存储结构比较合适。但链表除了需要设置数据域外，还要额外设置指针域，因此当线性表长度变化不大、易于事先确定规模时，为了节约存储空间，宜采用顺序存储结构。四、简答题1.简述线性表的存储结构及各自的优点。何时选用顺序表、何时选用链表作为线性表的存储结构为宜？•从时间上来看：若线性表的操作主要是查找，很少进行插入和删除操作时，应选用顺序表。对于频繁进行插入和删除操作的线性表，宜采用链表作为存储结构。四、简答题2.什么是头指针、头结点、首元结点。•首元结点：链表中存储的线性表中的第一个数据元素的结点。•头结点：为了操作的方便，通常在链表的首元结点之前附设一个结点，称头结点。•头指针：指向链表中的第一个结点（或为头结点或为首元结点）的指针。四、简答题3.在顺序表中插入和删除一个结点需平均移动多少个结点？具体的移动次数取决于哪两个因素？•插入结点：移动元素次数n-i+1；•删除结点：移动元素次...
