第2章线性表习题练习答案
2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。
答:
开始结点是指链表中的第一个结点,也就是没有直接前趋的那个结点。
链表的头指针是一指向链表开始结点的指针(没有头结点时),单链表由头指针唯一确定,因此单链表可以用头指针的名字来命名。
头结点是在链表的开始结点之前附加的一个结点。有了头结点之后,头指针指向头结点,不论链表否为空,头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。
2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜?
答:
在实际应用中,应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构,通常有以下几方面的考虑:
1.基于空间的考虑。当要求存储的线性表长度变化不大,易于事先确定其大小时,为了节约存储空间,宜采用顺序表;
反之,当线性表长度变化大,难以估计其存储规模时,采用动态链表作为存储结构为好。
2.基于时间的考虑。若线性表的操作主要是进行查找,很少做插入和删除操作时,采用顺序表做存储结构为宜;反之,若需要对线性表进行频繁地插入或删除等的操作时,宜采用链表做存储结构。并且,若链表的插入和删除主要发生在表的首尾两端,则采用尾指针表示的单循环链表为宜。2.3 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?
答:
在等概率情况下,顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i 越接近n则所需移动的结点数越少。2.4 为什么在单循环链表中设置尾指针比设置头指针更好?
答:
尾指针是指向终端结点的指针,用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便,设一带头结点的单循环链表,其尾指针为rear,则开始结点和终端结点的位置分别是rear->next->next 和rear, 查找时间都是
O(1)。
若用头指针来表示该链表,则查找终端结点的时间为
O(n)。2.5 在单链表、双链表和单循环链表中,若仅知道指针p指向某结点,不知道头指针,能否将结点*p从相应的链表中删去?若可以,其时间复杂度各为多少?
答:
下面分别讨论三种链表的情况。
1. 单链表。若指针p指向某结点时,能够根据该指针找到其直接后继,能够顺后继指针链找到*p结点后的结点。但是由于不知道其头指针,所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。
2. 双链表。由于这样的链表提供双向指针,根据*p结点的前趋指针和后继指针可以查找到其直接前趋和直接后继,从而可以删除该结点。其时间复杂度为O(1)。
3. 单循环链表。根据已知结点位置,可以直接得到其后相邻的结点位置(直接后继),又因为是循环链表,所以我们可以通过查找,得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。2.6 下述算法的功能是什么?
LinkList Demo(LinkList L){ // L 是无头结点单链表
ListNode *Q,*P;
if(L&&L->next){
Q=L;L=L->next;P=L;
while (P->next) P=P->next;
P->next=Q; Q->next=NULL;
}
return L;
}// Demo答:
该算法的功能是:将开始结点摘下链接到终端结点之后成为新的终端结点,而原来的第二个结点成为新的开始结点,返回新链表的头指针。2.7 设线性表的n个结点定义为(a0,a1,...an-1),重写顺序表上实现的插入和删除算法:InsertList 和DeleteList.
解:算法如下:
#define ListSize 100 // 假定表空间大小为100
typedef int DataType;//假定DataType的类型为int型
typedef struct{
DataType data[ListSize];// 向量data用于存放表结点
int length; // 当前的表长度
} Seqlist;
//以上为定义表结构
void InsertList ( Seqlist *L, Datatype x, int i)
{
//将新结点x插入L所指的顺序表的第i个结点ai的位置上,即插入的合法位置为:0length
int j;
if ( i L -> length )
Error('position error');// 非法位置,退出,该函数定义见教材P7.
if ( L->length>=ListSize )
Error(“overflow');
for ( j=L->length-1 ; j >= i ; j --)
L->data[ j+1]=L->data [ j ];
L->data[ i ]=x ;
L->length++ ;
}
void DeleteList ( Seqlist *L, int i )
{// 从L所指的顺序表中删除第i个结点ai,合法的删除位置为0length-1
int j;
if ( i= L-> length)
Error( ' position error' ) ;
for ( j = i ; j length ; j++ )
L->data [ j ]=L->data [ j+1]; //结点前移
L-> length-- ; //表长减小
}2.8 试分别用顺序表和单链表作为存储结构,实现将线性表(a0,a1,...an-1)就地逆置的操作,所谓'就地'指辅助空间应为O(1)。
答:
1. 顺序表:
要将该表逆置,可以将表中的开始结点与终端结点互换,第二个结点与倒数第二个结点互换,如此反复,就可将整个表逆置了。算法如下:
// 顺序表结构定义同上题
void ReverseList( Seqlist *L)
{
DataType temp ; //设置临时空间用于存放data
int i;
for (i=0;ilength/2;i++)//L->length/2为整除运算
{ temp = L->data[i]; //交换数据
L -> data[ i ] = L -> data[ L -> length-1-i];
L -> data[ L -> length - 1 - i ] = temp;
}
}
2. 链表:
分析:
可以用交换数据的方式来达到逆置的目的。但是由于是单链表,数据的存取不是随机的,因此算法效率太低。可以利用指针改指来达到表逆置的目的。具体情况入下:
(1)当链表为空表或只有一个结点时,该链表的逆置链表
与原表相同。
(2)当链表含2个以上结点时,可将该链表处理成只含第一结点的带头结点链表和一个无头结点的包含该链表剩余结点的链表。然后,将该无头结点链表中的所有结点顺着链表指针,由前往后将每个结点依次从无头结点链表中摘下,作为第一个结点插入到带头结点链表中。这样就可以得到逆置的链表。算法是这样的:
结点结构定义如下:
typedef char DataType; //假设结点的数据域类型的字符
typedef struct node{ //结点类型定义
DataType data; //结点的数据域
struct node *next;//结点的指针域
}ListNode;
typedef ListNode *LinkList;
ListNode *p;
LinkList head;
LinkList ReverseList( LinkList head )
{// 将head 所指的单链表(带头结点)逆置
ListNode *p ,*q ;//设置两个临时指针变量
if( head->next && head->next->next)
{ //当链表不是空表或单结点时
p=head->next;
q=p->next;
p -> next=NULL; //将开始结点变成终端结点
while (q)
{ //每次循环将后一个结点变成开始结点
p=q;
q=q->next ;
p->next = head-> next ;
head->next = p;
}
return head;
}
return head; //如是空表或单结点表,直接返回head }2.9 设顺序表L是一个递增有序表,试写一算法,将x插入L中,并使L仍是一个有序表。答:
因已知顺序表L是递增有序表,所以只要从顺序表终端结点(设为i位置元素)开始向前寻找到第一个小于或等于x的元素位置i后插入该位置即可。
在寻找过程中,由于大于x的元素都应放在x之后,所以可边寻找,边后移元素,当找到第一个小于或等于x的元素位置i时,该位置也空出来了。
算法如下:
//顺序表存储结构如题2.7
void InsertIncreaseList( Seqlist *L , Datatype x )
{
int i;
if ( L->length>=ListSize)
Error(“overflow');
for ( i=L -> length ; i>0 && L->data[ i-1 ] > x ; i--)
L->data[ i ]=L->data[ i ] ; // 比较并移动元素L->data[ i ] =x;
L -> length++;
}2.10 设顺序表L是一个递减有序表,试写一算法,将x插入其后仍保持L的有序性。
答:
与上题相类似,只要从终端结点开始往前找到第一个比x大(或相等)的结点数据,在这个位置插入就可以了。(边寻找,边移动)算法如下:
void InsertDecreaseList( Seqlist *L, Datatype x )
{
int i;
if ( L->length>=ListSize)
Error(“overflow');
for ( i=L -> length ; i>0 && L->data[ i-1 ] length++;
}2.11 写一算法在单链表上实现线性表的ListLength(L)运算。
解:
由于在单链表中只给出一个头指针,所以只能用遍历的方法来数单链表中的结点个数了。算法如下:
int ListLength ( LinkList L )
{
int len=0 ;
ListNode *p;
p=L; //设该表有头结点
while ( p->next )
{
p=p->next;
len++;
}
return len;
}2.12 已知L1和L2分别指向两个单链表的头结点,且已知其长度分别为m和n。试写一算法将这两个链表连接在一起,请分析你的算法的时间复杂度。
解:
分析:
由于要进行的是两单链表的连接,所以应找到放在前面的那张表的表尾结点,再将后表的开始结点链接到前表的终端结点后即可。该算法的主要时间消耗是用在寻找第一张表的终端尾结点上。这两张单链表的连接顺序无要求,并且已知两表的表长,则为了提高算法效率,可选表长小的单链表在前的方式连接。
具体算法如下:
LinkList Link( LinkList L1 , LinkList L2,int m,int n ) {//将两个单链表连接在一起
ListNode *p , *q, *s ;
//s指向短表的头结点,q指向长表的开始结点,回收长表头结点空间
if (mnext = q; //将长表的开始结点链接在短表终端结点后
return s;
}
本算法的主要操作时间花费在查找短表的终端结点上,所以本算的法时间复杂度为:
O(min(m,n))2.13 设A和B是两个单链表,其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C,并要求辅助空间为O(1),请分析算法的时间复杂度。
解:
根据已知条件,A和B是两个递增有序表,所以可以先取A表的表头建立空的C表。然后同时扫描A表和B表,将两表中最大的结点从对应表中摘下,并作为开始结点插入C表中。如此反复,直到A表或B表为空。最后将不为空的A表或B表中的结点依次摘下并作为开始结点插入C表中。这时,得到的C表就是由A表和B表归并成的一个按元素值递减有序的单链表C。并且辅助空间为O(1)。
算法如下:
LinkList MergeSort ( LinkList A , LinkList B )
{// 归并两个带头结点的递增有序表为一个带头结点递减有序表
ListNode *pa , *pb , *q , *C ;
pa=A->next;//pa指向A表开始结点
C=A;C->next=NULL;//取A表的表头建立空的C表
pb=B->next;//pb指向B表开始结点
free(B);//回收B表的头结点空间
while ( pa && pb)
{
if ( pb->data data )
{ // 当B中的元素小于等于A中当前元素时,将pa表的开始结点摘下
q=pa;pa=pa->next;
}
else
{// 当B中的元素大于A中当前元素时,将pb表的开始结点摘下
q=pb;pb=pb->next;}
q->next=C->next;C->next=q;//将摘下的结点q 作为开始结点插入C表
}
//若pa表非空,则处理pa表
while(pa){
q=pa;pa=pa->next;
q->next=C->next;C->next=q;}
//若pb表非空,则处理pb表
while(pb){
q=pb;pa=pb->next;
q->next=C->next;C->next=q;}
return(C);
}
该算法的时间复杂度分析如下:
算法中有三个while 循环,其中第二个和第三个循环只执行一个。每个循环做的工作都是对链表中结点扫描处理。
整个算法完成后,A表和B表中的每个结点都被处理了一遍。所以若A表和B表的表长分别是m和n,则该算法的时间复杂度O(m+n)2.14 已知单链表L是一个递增有序表,试写一高效算法,删除表中值大于min 且小于max的结点(若表中有这样的结点),同时释放被删结点的空间,这里min 和max 是两个给定的参数。请分析你的算法的时间复杂度。
解:
要解这样的问题,我们首先想到的是拿链表中的元素一个个地与max和min比较,然后删除这个结点。由于为已知其是有序链表,则介于min 和max之间的结点必为连续的一段元素序列。所以我们只要先找到所有大于min结点中的最小结点的直接前趋结点*p后,依次删除小于max的结点,直到第一个大于等于max结点*q位置,然后将*p结点的直接后继指针指向*q结点。
算法如下:
void DeleteList ( LinkList L, DataType min , DataType max )
{
ListNode *p , *q , *s;
p=L;
while( p->next && p->next->data next=q;//将*p结点的直接后继指针指向*q结点
}2.15 写一算法将单链表中值重复的结点删除,使所得的结果表中各结点值均不相同。
解:
本题可以这样考虑,先取开始结点中的值,将它与其后的所有结点值一一比较,发现相同的就删除掉,然后再取第二结点的值,重复上述过程直到最后一个结点。
具体算法:
void DeleteList ( LinkList L )
{
ListNode *p , *q , *s;
p=L-next;
while( p->next&&p->next->next)
{
q=p;//由于要做删除操作,所以q指针指向要删除元素的直接前趋
while (q->next)
if (p->data==q->next->data)
{s=q->next;q->next=s->next;free(s);//删除与*p的值相同的结点
}
else q=q->next;
p=p->next;
}
} 2.16 假设在长度大于1的单循环链表中,既无头结点也无头指针。s为指向链表中某个结点的指针,试编写算法删除结点*s的直接前趋结点。
解:
已知指向这个结点的指针是*s,那么要删除这个结点的直接前趋结点,就只要找到一个结点,它的指针域是指向*s 的直接前趋,然后用后删结点法,将结点*s的直接前趋结点删除即可。
算法如下:
void DeleteNode( ListNode *s)
{//删除单循环链表中指定结点的直接前趋结点
ListNode *p, *q;
p=s;
while( p->next->next!=s)
p=p->next;
//删除结点
q=p->next;
p->next=q->next;
free(p); //释放空间
}
注意:
若单循环链表的长度等于1,则只要把表删空即可。2.17 已知由单链表表示的线性表中,含有三类字符的数据元素(如:字母字符、数字字符和其它字符),试编写算法构造三个以循环链表表示的线性表,使每个表中只含同一类的字符,且利用原表中的结点空间作为这三个表的结点空间,头结点可另辟空间。
解:
要解决这样的问题,只要新建三个头结点,然后在原来的单链表中依次查询,找到一类字符结点时,就摘下此结点链接到相应头结点指明的新链表中就是了。
算法如下:
//设已建立三个带头结点的空循环链表A,B,C且A、B、C分别是尾指针.
void DivideList( LinkList L, LinkList A, LinkList B, LinkList C)
{
ListNode *p=L->next, *q;
while ( p )
{
if ( p->data>='a' &&p->datadata>='A'
&&p->datadatanext=q;B=q;
}
else { //分出其他字符结点
q=p->next;
p=p->next;//指向下一结点
q->next=C->next;//将其他结点链到C表中
C->next=q;C=q;
}
}
}//结束2.18 设有一个双链表,每个结点中除有prior、data和next三个域外,还有一个访问频度域freq,在链表被起用之前,其值均初始化为零。每当在链表进行一次LocateNode(L,x)运算时,令元素值为x的结点中freq域的值加1,并调整表中结点的次序,使其按访问频度的递减序排列,以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。
解:
LocateNode运算的基本思想就是在双向链表中查找值
为x的结点,具体方法与单链表中查找一样。找到结点*p后给freq域的值加1。由于原来比*p结点查找频度高的结点都排它前面,所以,接下去要顺着前趋指针找到第一个频度小于或等于*p结点频度的结点*q后,将*p结点从原来的位置删除,并插入到*q后就可以了。
算法如下:
//双向链表的存储结构
typedef struct dlistnode{
DataType data;
struct dlistnode *prior,*next;
int freq;
}DListNode;
typedef DListNode *DLinkList;
void LocateNode( LinkList L, DataType x)
{
ListNode *p, *q;
p=L->next; //带有头结点
while( p&&p->data!=x )
p=p->next;
if (!p) ERROR('x is not in L');//双链表中无值为x 的结点
else { p->freq++;//freq加1
q=p->prior;//以q为扫描指针寻找第一个频度大于或等于*p频度的结点
while(q!=L&&q->freqfreq)
q=q->prior;
if (q->next!=p)//若* q结点和*p结点不为
直接前趋直接后继关系,
//则将*p结点链到* q结点后
{p->prior->next=p->next;//将*p从原来
位置摘下
p->next->prior=p->prior;
q->next->prior=p;//将*p插入*q之后。
p->next=q->next;
q->next=p;
p->prior=q;
}
}
}
2.11 设顺序表va中的数据元素递增有序。试写一算法,将x插入到顺序表的适当位置上,以保持该表的有序性。 Status OrderListInsert-sq(SqList va, ElemType x) { //将x插入到递增有序的顺序表va中,插入后va仍然递增有序(算法1) if (va.length==va.listsize){ newbase=(ElemType *)realloc(va.elem,(va.listsize+LISTINCREMENT)*sizeof(ElemType)); if (!newbase) exit(OVERFLOW); va.elem=newbase; va.listsize+=LISTINCREMENT; }//当前存储空间已满,增加分配空间 if (!va.length) {va.elem[0]=x; ++va.length; return OK;} q=&(va.elem[0]); while (*q<=x)&&(q<=&(va.elem[va.length-1])) ++q; //查找插入位置 for (p=&(va.elem[va.length-1]); p>=q; --p) *(p+1)=*p; *q=x; ++va.length; return OK; }//OrderListInsert-sq Status OrderListInsert-sq(SqList va, ElemType x) { //将x插入到递增有序的顺序表va中,插入后va仍然递增有序(算法2) if (va.length==va.listsize){ newbase=(ElemType *)realloc(va.elem,(va.listsize+LISTINCREMENT)*sizeof(ElemType)); if (!newbase) exit(OVERFLOW); va.elem=newbase; va.listsize+=LISTINCREMENT; }//当前存储空间已满,增加分配空间 if (!va.length) {va.elem[0]=x; ++va.length; return OK;} p=&(va.elem[va.length-1]); while (P>=&(va.elem[0])&&*p>x) {*(p+1)=*p; --p;} *(p+1)=x; ++va.length;
第二章线性表作业 一、选择题 1.下述哪一条是顺序存储结构的优点?() A.存储密度大B.插入运算方便 C.删除运算方便D.可方便地用于各种逻辑结构的存储表示 2.下面关于线性表的叙述中,错误的是哪一个?() A.线性表采用顺序存储,必须占用一片连续的存储单元。 B.线性表采用顺序存储,便于进行插入和删除操作。 C.线性表采用链接存储,不必占用一片连续的存储单元。 D.线性表采用链接存储,便于插入和删除操作。 3.线性表是具有n个()的有限序列(n>0)。 A.表元素B.字符C.数据元素D.数据项 4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用()存储方式最节省时间。 A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表 5.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用()存储方式最节省运算时间。 A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表 6.设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用( )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用()存储方式最节省运算时间。 A.单链表B.双链表C.单循环链表D.带头结点的双循环链表 8. 静态链表中指针表示的是(). A.内存地址B.数组下标C.下一元素地址D.左、右孩子地址 9. 链表不具有的特点是() A.插入、删除不需要移动元素B.可随机访问任一元素 C.不必事先估计存储空间D.所需空间与线性长度成正比 10. 下面的叙述不正确的是()
第二章线性表练习题 一、选择题 1.线性表是具有n个的有限序列。 A、表元素 B、字符 C、数据元素 D、数据项 E、信息项 2.线性表的静态链表存储结构与顺序存储结构相比优点是。 A、所有的操作算法实现简单 B、便于随机存储 C、便于插入和删除 D、便于利用零散的存储器空间 3.若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素算法的时间复杂度为。 A、O(log2n) B、O(1) C、O(n) D、O(n2) 4.(1)静态链表既有顺序存储的特点,又有动态链表的优点。所以,它存取表中第i个元素的时间与i无关; (2)静态链表中能容纳元素个数的最大数在定义时就确定了,以后不能增加;(3)静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。 以上错误的是。 A、(1)、(2) B、(1) C、(1)、(2)、(3) D、(2) 6.在双向链表存储结构中,删除p所指的结点时须修改指针。 A、p->next->prior=p->prior; p->prior->next=p->next; B、p->next=p->next->next;p->next->prior=p; C、p->prior->next=p;p->prior=p->prior->prior; D、p->prior=p->next->next;p->next=p->prior->prior;
7.在双向循环链表中,在P指针所指的结点后插入q所指向的新结点,其修改指针的操作是。 A、p->next=q; q->prior=p;p->next->prior=q;q->next=q; B、p->next=q;p->next->prior=q;q->prior=p;q->next=p->next; C、q->prior=p; q->next=p->next; p->next->prior=q; p->next=q; D、q->next=p->next;q->prior=p;p->next=q;p->next=q; 8.将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是。 A、 n b、2n-1 c、2n d、n-1 9.在一个长度为n的顺序表中,在第i个元素(1≤i≤n+1)之前插入一个新元素时须向后移动个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 10.线性表L=(a1,a2,……an),下列说法正确的是。 A、每个元素有有一个直接前驱和一个直接后继 B、线性表中至少有一个元素 C、表中诸元素的排列必须是由小到大或由大到小。 D、除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继。 11.对单链表表示法,以下说法错误的是。 A、数据域用于存储线性表的一个数据元素 B、指针域(或链域)用于存放一指向本结点所含数据元素的直接后继所在结点的指针 C、所有数据通过指针的链接而组织成单链表 D、NULL称为空指针,它不指向任何结点只起标志作用
第2章线性表 一选择题 1.下述哪一条是顺序存储结构的优点?( A ) A.存储密度大 B.插入运算方便 C.删除运算方 便 D.可方便地用于各种逻辑结构的存储表示 2.下面关于线性表的叙述中,错误的是哪一个?( B )A.线性表采用顺序存储,必须占用一片连续的存储单元。B.线性表采用顺序存储,便于进行插入和删除操作。 C.线性表采用链接存储,不必占用一片连续的存储单元。D.线性表采用链接存储,便于插入和删除操作。 3.线性表是具有n个( C )的有限序列(n>0)。 A.表元素 B.字符 C.数据元 素 D.数据项 E.信息项 4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用( A )存储方式最节省时间。 AHA12GAGGAGAGGAFFFFAFAF
A.顺序表 B.双链表 C.带头结点的双循环链表 D.单循环链表 5.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用( D )存储方式最节省运算时间。 A.单链表 B.仅有头指针的单循环链 表 C.双链表D.仅有尾指针的单循环链表 6.设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用( D )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用( D )存储方式最节省运算时间。 AHA12GAGGAGAGGAFFFFAFAF
A.单链表 B.双链表 C.单循环链 表 D.带头结点的双循环链表 8. 静态链表中指针表示的是( BC ). A.内存地址 B.数组下标 C.下一元素地址D.左、右孩子地址 9. 链表不具有的特点是( C ) A.插入、删除不需要移动元素 B.可随机访问任一元素C.不必事先估计存储空间 D.所需空间与线性长度成正比 10. 下面的叙述不正确的是( BC ) A.线性表在链式存储时,查找第i个元素的时间同i的值成正比 AHA12GAGGAGAGGAFFFFAFAF
第二章线性表 1、描述一下三个概念的区别:头指针,头结点,首元结点。并给予图示。 2、对于有头结点的单链表,分别写出定位成功时,实现下列定位语句序列。(1)定位到第i 个结点a i ; (2)定位到第i 个结点的前驱a i-1; (3)定位到尾结点; (4)定位到尾结点的前驱。 3、已知L 是有表头结点的单链表,且P 结点既不是首元结点,也不是尾结点,试写出实现下列功能的语句序列。 (1)在P 结点后插入S 结点;(2)在P 结点前插入S 结点;(3)在表首插入S 结点;(4)在表尾插入S 结点 . p=head; p=head; j=0; while ( p && jnext; j++;} p=head; j=0; while ( p && j
4、设计算法:在顺序表中删除值为e 的元素,删除成功,返回1;否则,返回0。 5、设计一个算法,将一个带头节点的数据域依次为a 1,a 2,…,a n (n ≥3)的单链表的所有节点逆置,即第一个节点的数据域变为a n ,…,最后一个节点的数据域为a 1。(注意:先用自然语言描述算法基本思想,然后用类C++语言描述) int Sqlist
第2章线性表 班级学号__________-姓名 一、判断正误 (×)1. 链表的每个结点中都恰好包含一个指针。 链表中的结点可含多个指针域,分别存放多个指针。例如,双向链表中的结点可以含有两个指针域,分别存放指向其直接前趋和直接后继结点的指针。 (×)2. 链表的物理存储结构具有同链表一样的顺序。 链表的存储结构特点是无序,而链表的示意图有序。 (×)3. 链表的删除算法很简单,因为当删除链中某个结点后,计算机会自动地将后续的各个单元向前移动。 链表的结点不会移动,只是指针内容改变。 (×)4. 线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。 混淆了逻辑结构与物理结构,链表也是线性表!且即使是顺序表,也能存放记录型数据。 (×)5. 顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。 正好说反了。顺序表才适合随机存取,链表恰恰适于“顺藤摸瓜” (×)6. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。 前一半正确,但后一半说法错误,那是链式存储的优点。顺序存储方式插入、删除运算效率较低,在表长为n的顺序表中,插入和删除一个数据元素,平均需移动表长一半个数的数据元素。 (×)7. 线性表在物理存储空间中也一定是连续的。 线性表有两种存储方式,顺序存储和链式存储。后者不要求连续存放。 (×)8. 线性表在顺序存储时,逻辑上相邻的元素未必在存储的物理位置次序上相邻。 线性表有两种存储方式,在顺序存储时,逻辑上相邻的元素在存储的物理位置次序上也相邻。 (×)9. 顺序存储方式只能用于存储线性结构。 顺序存储方式不仅能用于存储线性结构,还可以用来存放非线性结构,例如 完全二叉树是属于非线性结构,但其最佳存储方式是顺序存储方式。(后一节介绍) (×)10. 线性表的逻辑顺序与存储顺序总是一致的。 理由同7。链式存储就无需一致。 二、单项选择题 (C )1.数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称之为:(A)存储结构(B)逻辑结构(C)顺序存储结构(D)链式存储结构( B )2. 一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是(A)110 (B)108 (C)100 (D)120 ( A )3. 在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是: (A)访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n) (B)在第i个结点后插入一个新结点(1≤i≤n) (C)删除第i个结点(1≤i≤n) (D)将n个结点从小到大排序 ( B )4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动个元素(A)8 (B)63.5 (C)63 (D)7 ( A )5. 链式存储的存储结构所占存储空间:
第二章线性表 2.1 填空题 (1)一半插入或删除的位置 (2)静态动态 (3)一定不一定 (4)头指针头结点的next 前一个元素的next 2.2 选择题 (1)A (2) DA GKHDA EL IAF IFA(IDA) (3)D (4)D (5) D 2.3 头指针:在带头结点的链表中,头指针存储头结点的地址;在不带头结点的链表中,头指针存放第一个元素结点的地址; 头结点:为了操作方便,在第一个元素结点前申请一个结点,其指针域存放第一个元素结点的地址,数据域可以什么都不放; 首元素结点:第一个元素的结点。 2.4已知顺序表L递增有序,写一算法,将X插入到线性表的适当位置上,以保持线性表的有序性。 void InserList(SeqList *L,ElemType x) { int i=L->last; if(L->last>=MAXSIZE-1) return FALSE; //顺序表已满 while(i>=0 && L->elem[i]>x) { L->elem[i+1]=L->elem[i]; i--; } L->elem[i+1]=x; L->last++; } 2.5 删除顺序表中从i开始的k个元素 int DelList(SeqList *L,int i,int k) { int j,l; if(i<=0||i>L->last) {printf("The Initial Position is Error!"); return 0;} if(k<=0) return 1; /*No Need to Delete*/ if(i+k-2>=L->last) L->last=L->last-k; /*modify the length*/
第2章线性表习题解答
第2章习题 (2) 第2章习题 2.1若将顺序表中记录其长度的分量listlen改为指向最后一个元素的位置last,在实现各基本运算时需要做那些修改? 【解】 //用线性表最后一个元素的下标last代替listLen实现顺序表 #define MAXLEN 100 typedef int elementType; typedef struct sllLast { elementType data[MAXLEN]; int last; }seqList; //初始化 void initialList(seqList &S)
{ https://www.wendangku.net/doc/a63686333.html,st=-1; } //求表长度 int listLength(seqList S) { return https://www.wendangku.net/doc/a63686333.html,st+1; } //按序号取元素 bool getElement(seqList S,int i,elementType &x) { if(i<1 || i>https://www.wendangku.net/doc/a63686333.html,st+1) //i为元素编号,有效范围在https://www.wendangku.net/doc/a63686333.html,st+1之间 return false; else { x=S.data[i-1];
return true; } } //查找元素x,成功:返回元素编号;失败:返回0 int listLocate(seqList S,elementType x) { int i; for(i=0;i<=https://www.wendangku.net/doc/a63686333.html,st;i++) { if(S.data[i]==x) return i+1; //找到,转换为元素编号输出 } return 0; } //插入元素 int listInsert(seqList &S,elementType x, int i)
第二章测试试题 班级:学号:姓名:成绩: 一、选择题(每小题5分) 1.线性表是( A )。 A一个有限序列,可以为空;B一个有限序列,不能为空; C一个无限序列,可以为空;D一个无序序列,不能为空。 2.用链表表示线性表的优点是(C)。 A便于随机存取 B花费的存储空间较顺序存储少 C便于插入和删除 D数据元素的物理顺序与逻辑顺序相同 3.某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素,则采用( D )存储方式最节省运算时间。 A单链表 B双链表 C单循环链表 D带头结点的双循环链表 4.带头结点的单链表head为空的判定条件是(B )。 A.head==NULL; B.head->next==NULL; C.head->next==head; D.head!=NULL; 5.在一个单链表中,已知q所指结点是p所指结点的前驱结点,若在q和p之间插入s结点,则执行(C )。 A.s->next=p->next;p->next=s; B.p->next=s->next;s->next=p; C.q->next=s;s->next=p; D.p->next=s; s->next=q; 二、填空题(每小题5分) 1.给定有n个结点的向量,建立一个单链表的时间复杂度_______。建立一个有序单链表的时间复杂度_______。 2.从一个具有n个结点的单链表中查找其值等于x结点时,在查找成功的情况下,需平均比较_____个结点。 3.在一个长度为n的线性表(采用顺序存储结构)中删除第i个元素(1≤i≤n)时,需向前移动____个元素。 4.当对一个线性表经常进行存取操作,而很少进行插入和删除操作时,则采用_____存储结构为宜。相反,当经常进行的是插入和删除操作时,则采用_______存储结构为宜。5.对顺序存储的线性表,设其长度为n,在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的个元素。 三、算法设计题(每小题25分) 1.设有一个用向量表示的线性表L,要求写出一个将该表逆置的过程,允许在原表的存储空间外再增加一个附加的工作单元。 2.已知两个整数集合A和B,它们的元素分别依元素值递增有序存放在两个单链表HA 和HB中,编写一个函数求出这两个集合的并集C,并要求集合C的链表的结点仍依元素值递增有序存放。(注意:并集不是归并)
(A )需经常修改L 中的结点值 (E )需不断对L 进行删除插入 第二部分线性表 、选择题 1 ?关于顺序存储的叙述中,哪一条是不正确的 (B ) A. 存储密度大 B. 逻辑上相邻的结点物理上不必邻接 C. 可以通过计算直接确定第 i 个结点的位置 D. 插入、删除操作不方便 2.长度为n 的单链表连接在长度为 m 的单链表后的算法的时间复杂度为 (C ) A 0( n ) B 0(1) C 0(m ) D 0(m+n ) 3 .在n 个结点的顺序表中,算法的时间复杂度是 0(1)的操作是:(A ) A 访问第i 个结点(1<=i<=n )和求第i 个结点的直接前趋(2<=i<=n ) B 在第i 个结点(1<=i<=n )后插入一个新结点 C 删除第i 个结点(1<=i<=n ) D 将n 个结点从小到大排序 4.一个向量第一个兀素的存储地址是 100 ,每个兀素的长度为 2 ,则第5 个兀素的地址是 (B ) ( A ) 110 ( B ) 108 (C ) 100 ( D ) 120 5 .已知一个顺序存储的线性表, 设每个结点需要占 m 个存储单元,若第一个结点的地址为 da , 则第i 个结点的地址为:(A ) 7 .链表是一种采用( B )存储结构存储的线性表。 (A )顺序 (B )链式 (C )星式 (D )网状 8 .线性表若采用链式存储结构时,要求内存中可用存储单兀的地址: (D ) (A )必须是连续的 (B )部分地址必须是连续的 (C )一定是不连续的 (D )连续或不连续都可以 9 .线性表L 在_ ( B )情况下适用于使用链式结构实现。 A ) da+(i-1)*m B ) da+i*m 6.在具有n 个结点的单链表中,实现( A )遍历链表和求链表的第 i 个结点 C )删除开始结点 C ) da-i*m D ) da+(i+1)*m A )的操作,其算法的时间复杂度为 0(n )。 B )在地址为p 的结点之后插入一个结点 D ) 删除地址为p 的结点的后继结点
第2章线性表 1.下面关于线性表的叙述中,错误的是哪一个?()A.线性表采用顺序存储,必须占用一片连续的存储单元。 B.线性表采用顺序存储,便于进行插入和删除操作。 C.线性表采用链接存储,不必占用一片连续的存储单元。 D.线性表采用链接存储,便于插入和删除操作。 2.线性表是具有n个()的有限序列(n>0)。 A.表元素 B.字符 C.数据元素 D.数据项 E.信息项 3.线性表( a1,a2,…,an)以链接方式存储时,访问第i位置 元素的时间复杂性为() A.O(i) B.O(1) C.O(n) D.O(i-1) 4.若长度为n的线性表采用顺序存储结构,在其第i个位置插 入一个新元素的算法的时间复杂度为()(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 5. 对于顺序存储的线性表,访问结点和增加、删除结点的时间 复杂度为()。 A.O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 6.对于一个头指针为head的带头结点的单链表,判定该表为空 表的条件是()
A.head==NULL B.head→next==NULL C.head→next==head D.head!=NULL 7.链表不具有的特点是() A.可随机访问任一元素 B.插入、删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与线性长度成正比 8.在双向链表指针p的结点前插入一个指针q的结点操作是()。 >Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q; >Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink ; C. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q; >Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q ; 9.在单链表指针为p的结点之后插入指针为s的结点,正确的 操作是:()。 A. s->next=p->next;p->next=s; B. p->next=s;s->next=p->next; C.p->next=s;p->next=s->next; D. p->next=s->next;p->next=s; 10.对于一个头指针为head的带头结点的单链表,判定该表为
第二章线性表习题 判断题 1.线性表的链接存储,表中元素的逻辑顺序与物理顺序一定相同。() 选择题 1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( ) (A)110 (B)108 (C)100 (D)120 3. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动()个元素。 (A)64 (B)63 (C)63.5 (D)7 4.线性表采用链式存储结构时,其地址()。 (A) 必须是连续的 (B) 部分地址必须是连续的 (C) 一定是不连续的 (D) 连续与否均可以 5. 在一个单链表中,若p所指结点不是最后结点,在p之后插入s所指结点,则执行() (A)s->next=p;p->next=s; (B) s->next=p->next;p->next=s; (C)s->next=p->next;p=s; (D)p->next=s;s->next=p; 6.在一个单链表中,若删除p所指结点的后续结点,则执行() (A)p->next=p->next->next; (B)p=p->next; p->next=p->next->next; (C)p->next=p->next; (D)p =p->next->next; 7.下列有关线性表的叙述中,正确的是() (A)线性表中的元素之间隔是线性关系 (B)线性表中至少有一个元素 (C)线性表中任何一个元素有且仅有一个直接前趋 (D)线性表中任何一个元素有且仅有一个直接后继 8.线性表是具有n个()的有限序列(n≠0) (A)表元素(B)字符(C)数据元素(D)数据项 填空题 1.已知P为单链表中的非首尾结点,在P结点后插入S结点的语句为:( ) 。 2.顺序表中逻辑上相邻的元素物理位置(一定 )相邻,单链表中逻辑上相邻的元素物理位置( )相邻。
第二章线性表习题及答案 一、基础知识题 2.1 试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。 答:始结点是指链表中的第一个结点,也就是没有直接前趋的那个结点。 链表的头指针是一指向链表开始结点的指针(没有头结点时),单链表由头指针唯一确定,因此单链表可以用头指针的名字来命名。 头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后,头指针指向头结点,不论链表否为空,头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。 2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答:在实际应用中,应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构,通常有以下几方面的考虑: 1.基于空间的考虑。当要求存储的线性表长度变化不大,易于事先确定其大小时,为了节约存储空间,宜采用顺序表;反之,当线性表长度变化大,难以估计其存储规模时,采用动态链表作为存储结构为好。 2.基于时间的考虑。若线性表的操作主要是进行查找,很少做插入和删除操作时,采用顺序表做存储结构为宜;反之,若需要对线性表进行频繁地插入或删除等的操作时,宜采用链表做存储结构。并且,若链表的插入和删除主要发生在表的首尾两端,则采用尾指针表示的单循环链表为宜。 2.3 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素? 答:在等概率情况下,顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i 越接近n则所需移动的结点数越少。 2.4 为什么在单循环链表中设置尾指针比设置头指针更好? 答:尾指针是指向终端结点的指针,用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便,设一带头结点的单循环链表,其尾指针为rear,则开始结点和终端结点的位置分别是rear->next->next 和rear, 查找时间都是O(1)。 若用头指针来表示该链表,则查找终端结点的时间为O(n)。 2.5 在单链表、双链表和单循环链表中,若仅知道指针p指向某结点,不知道头指针,能否将结点*p从相应的链表中删去?若可以,其时间复杂度各为多少? 答:我们分别讨论三种链表的情况。 1. 单链表。当我们知道指针p指向某结点时,能够根据该指针找到其直接后继,但是由于不知道其头指针,所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。 2. 双链表。由于这样的链表提供双向链接,因此根据已知结点可以查找到其直接前趋和直接后继,从而可以删除该结点。其时间复杂度为O(1)。 3. 单循环链表。根据已知结点位置,我们可以直接得到其后相邻的结点位置(直接后继),又因为是循环链表,所以我们可以通过查找,得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。 2.6 下述算法的功能是什么? LinkList Demo(LinkList L){ // L 是无头结点单链表 ListNode *Q,*P; if(L&&L->next){ Q=L;L=L->next;P=L;
第二章 一选择题 1.一个线性表第一个元素的存储地址是100,每个元素的长度为4,则第5个元素的地址是( ) A.110 B.116 C.100 D.120 2. 向一个有128个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动()个元素。 A.64 B.63 C.63.5 D.7 3.在循环双链表的p所指接点之前插入s所指接点的操作是 A.p-> prior =s;s-> next t=p;p-> prior t->left=s;s-> prior =p-> prior; B. p-> prior =s;p-> prior -> next =s;s-> next =p;s-> prior =p-> prior; C.s-> next =p;s-> prior =p-> prior;p-> prior =s;p-> prior -> next =s; D.s-> next =p;s-> prior =p-> prior;p-> prior -> next =s;p-> prior =s; 4.从一个具有n个结点的单链表中查找其值等于x结点时,在查找成功的情况下,需平均比较()个结点。 A.n B.n/2 C.(n-1)/2 D.(n+1)/2 5.线性表是具有n个()的有限序列(n≠0) A.表元素 B.字符 C.数据元素 D.数据项 6.非空的循环单链表head的尾结点(由P指向)满足 A. p->next=NULL B. p=NULL C. p->next=head D.p=head 7.在一个单链表中已知q所指的结点是p所指结点的前驱结点,若在q和p之间插入s 结点,则执行( ) A. s->next=p->next;p->next=s; B.p->next=s->next;s->next=p; C. q->next=s;s->next=p; D.p->next=s;s->next=q; 8.已知一个顺序存储线性表,若第1个结点的地址d,第3个的地址是5d,则第n个结点的地址为( ) A.[2*(n-1)+1]*d B.2*(n-1)*d C.[2*(n-1)-1]*d D.(n+1)*d 9.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( ) A.O(1) B.O(n) C.O(n2) D.O(nlog2n) 10.如果最常用的操作是提取第i个结点及其前驱,则采用( )存储方式最节省时间。 A.单链表 B.顺序表 C.循环链表 D.双链表 11.在一个长度为n的顺序存储线性表中,向第i个元素(1≤i≤n)之前插入一个新元素时,需要从后向前依次后移( )个元素。 A.n-i B.n-i+1 C.n-i-1 D.i 12.在一个长度为n的顺序存储线性表中,删除第i个元素(0≤i≤n-1)时,需要从后向
第二章线性表 一、填空题 1、数据逻辑结构包括线性结构、树型结构、图型结构这三种类型,树形结构和图形结构合称为非线性结构。 2、在线性结构中,第一个结点没有前驱结点,其余每个结点有且只有个前驱结点,最后一个结点没有后续结点,其余每个结点有且只有一个后续结点。 3、在顺序表中插入或删除一个元素,需要平均移动一半元素,具体移动的元素个数与插入或删除的位置有关。 4、在顺序表中,逻辑上相邻的元素,其物理位置一定相邻。在单链表中,逻辑上相邻的元素,其物理位置不一定相邻。 5、在带头结点的非空单链表中,头结点的存储位置由头指针指示,首元素结点的存储位置由头结点的next域指示,除首元素结点外,其它任一元素结点的存储位置由其直接前趋结点的next域指示。 6、阅读下列算法,并补充所缺内容。 void purge_linkst( ListNode *& la ) { // 从头指针为 la 的有序链表中删除所有值相同的多余元素,并释放被删结点空间ListNode *p,*q; if(la==NULL) return; q=la; p = la->link; while (p) { if (p && ___(1)p->data!=q->data___) {q=p; p = p->link;} else { q->link= ___(2)p->link___; delete(p); p=___(3)q->link___; } }//while }// purge_linkst 二、选择题 1、在数据结构中,从逻辑上可以把数据结构分成 C。 A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 2、线性表的逻辑顺序与存储顺序总是一致的,这种说法 B。 A、正确 B、不正确 3、线性表若采用链式存储结构时,要求内存中可用存储单元的地址D。 A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以 4、在以下的述叙中,正确的是B。 A、线性表的线性存储结构优于链表存储结构 B、二维数组是其数据元素为线性表的线性表 C、栈的操作是先进先出 D、队列的操作方式是先进后出 三、综合题 1、已知L是无表头结点的单链表,且P结点既不是首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。 A、在P结点后插入S结点的语句序列是((4)、(1)); B、在P结点前插入S结点的语句序列是((7)、(11)、(8)、(4)、(1)); C、在表首插入S结点的语句序列是((5)、(12));
一、选择题 1. D 2. B 3. B 4. B 5. B 6. B 7. D 8. B 9. C 10. B 11. C 12. C 13. B 14. D 15. A 16. B 17. B 18. C 19. A 20. C 21. D 22. A 23. A 24. A 二、填空题 1. 首元素其直接前驱结点的链域的值 2. HL→next =NULL; HL=HL→next 3. 有限、一对一 4. O(1) 随机存取 5. 表中一半表长和该元素在表中的位置 6. 必定不一定 7. O(1) O(n) 8. 前驱结点的地址 O(n) 9. n-i+1 n-i 10. s->left=p p->right 三、判断题 1. × 2. × 3. × 4. × 5. × 6. × 7. √ 8. × 9. × 10. × 11. × 四、简答题 1. 线性表为:(78,50,40,60,34,90) 2. (36, 12, 8, 50, 25, 5, 15) 3. 解答: 尾指针是指向终端结点的指针,用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便,设一带头结点的单循环链表,其尾指针为rear,则开始结点和终端结点的位置分别是rear->next->next和rear, 查找时间都是O(1)。
若用头指针来表示该链表,则查找终端结点的时间为O(n)。 五、编程题 1. 解答:由于在单链表中只给出一个头指针,所以只能用遍历的方法来数单链表中的结点个数了。算法如下: int ListLength ( LinkList L ) { int len=0 ; ListNode *p; p=L; //设该表有头结点 while ( p->next ) { p=p->next; len++; } return len; } 2. int searchmin(linklist l) { int min; int *p; p=l; min=p->data; p=p->next; while (p->next< >nil) { if (min>p->data) min=p->data; p=p->next; } return min; } 3. int searchmax(linklist l) { int max; int *p; p=l; max=p->data; p=p->next; while (p->next< >nil) { if (max
第二章线性表习题(答案) 1.描述以下三个概念的区别:头指针,头结点,首元素结点。 首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便,通常在链表的首元结点之前附设一个结点,称为头结点,该结点的数据域中不存储线性表的数据元素,其作用是为了对链表进行操作时,可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点(或为头结点或为首元结点)的指针。 若链表中附设头结点,则不管线性表是否为空表,头指针均不为空。否则表示空表的链表的头指针为空。 2.填空: (1)在顺序表中插入或删除一个元素,需要平均移动一半元素,具体移动的元素个数与插入或删除的位置有关。 (2)在顺序表中,逻辑上相邻的元素,其物理位置也相邻。在单链表中,逻辑上相邻的元素,其物理位置不一定相邻。 (3)在带头结点的非空单链表中,头结点的存储位置由头指针指示,首元素结点的存储位置由头结点的next域指示,除首元素结点外,其它任一元素结点的存储位置由其直接前趋的next域指示。 3.已知L是无表头结点的单链表,且P结点既不是首元素结点,也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是:(4)、(1)。 b. 在P结点前插入S结点的语句序列是:(7)、(11)、(8)、(4)、(1)。 c. 在表首插入S结点的语句序列是:(5)、(12)。 d. 在表尾插入S结点的语句序列是:(11)、(9)、(1)、(6)。 供选择的语句有: (1)P->next=S; (2)P->next= P->next->next; (3)P->next= S->next;(4)S->next= P->next; (5)S->next= L; (6)S->next= NULL;(7)Q= P; (8)while(P->next!=Q) P=P->next; (9)while(P->next!=NULL) P=P->next; (10)P= Q; (11)P= L; (12)L= S; (13)L= P; 4.设线性表存于a[n]中且递增有序。试写一算法,将X插入到线性表的适当位置上,以保 持线性表的有序性。 void insertData(int a[],int data) { int i,location=0; for(i=0;i