计算机专业基础综合数据结构(线性表)-试卷1

计算机专业基础综合数据结构（线性表）卷1(分：72.00做题时间：分钟)一、单项择(总题数：，数42.00)1.单项选择1-40小题。下列每题给出的四个选项中，有一个选项是最符题目要求。__________________________________________________________________________________________2.若某线性表中最用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算时间的存储方式是()。A.链表B.有头指针的单循环链表C.链表D.有尾指针的单循环链表√在链表中的最后一个结点之后插入一个结点要知道终端结点的地址，所以，单链表、带有头指针的单循环链表、双链表都不合适。考虑在带有尾指针的单循环链表中删除第一个结点，其时间性能是O(1)，以答案是D3.已知两个长度分为l和s降序链表，若将它们合并为一个长度为的升序链表，则最坏况下的时间复杂度是()。A.O(l)B.O(ls)C.O(min(l，D.O(max(l，

√在合并过程中，最坏的情况是两个链表中的元素依次进行比较，比较的次数最少是和n中的最大值。4.线性表中存放的要是()A.型常量B.符C.据元素D.息元素

√线性表中主要存放的是数据元素，而数据元素可以是整型也可以是字符型，但对于一个线性表来说，所有的数据元素的类型必须相同。5.下面的叙述中正的是()．性表在链式存储时，查找i元素的时间同i的成正比Ⅱ．线性表在链式存储时，查找第i个元素的间同i的值无关．线性表在顺序存储时，查找i元素的时间同i的成正比A.仅I

√B.ⅡC.ⅢD.I、、Ⅲ在线性表链式存储结构中，查找第元素的时间与i的位置成正比。而在顺序存储结构中查找第i个元素的时间与i的置无关。6.对于某线性表来，主要的操作是存取任一指定序号的元素和在最后进行插入运算，那么应该选择)存储方式最节省时间。A.序表

√B.链表C.头结点的双循环链表D.循环链表线性表中要想最省时间地存取某一指定序号的元素，那么就要利用顺序表这种存储方式。但顺序表不利于插入和删除运算，可是题目中强调是在最后进行插入运算，因此，本题最合适的选项是顺序表。7.若线性表最常用运算是查找第i个元素及其前驱的，则下列存储方式中最节省时间的是)。A.链表

B.链表C.循环链表D.序表

√本题的考点是线性表的存储结构及其特点线性表中主要存储结构有顺序表和链表两种特如下：(1)顺表可以实现随机存取，其时间复杂度为O(1)。但顺序表中，进行插入和删除操作需要移动大量的元素，其时间复杂度为O(n)；表中只能实现顺序查找，其时间复杂度为O(n)。但链表中进行插入和删除操作不需要移动元素，只需要修改指针，其时间复杂度为本题中，线性表中常用操作是取第i个素，所以应选择随机存取结构，即顺序表；同时在顺序表中查找第i元素的前驱也很方便。单链表和单循环链表既不能实现随机存取，查找第元素的前驱也不方便：双链表虽然能快速查找第i个元素的前驱，但不能实现随机存取。8.如果线性表中最用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采(储方式最节省运算时间。A.链表B.有头指针的单循环链表C.链表D.有尾指针的单循环链表√最常用的操作是最后一个元素之后插入一个元素和删除第一个元素，则采用尾指针的单循环链表。9.算法的时间复杂取决于()A.题的规模B.处理数据的初态C.AB

√D.上都不正确此题考查的知识点是算法时间复杂度的定义。算法的时间复杂度取决于输入问题的规模和待处理数据的初态，所以选CA和B不全面。10.关链表的特点，下面的叙述中不正确的是)。A.入、删除运算方便B.实现随机访问任一元素√C.必事先估计存储空间D.需空间与线性长度成正比链表的特点包括：事先不需要申请存储空间，插入和删除运算方便，但不能实现随机存取。11.设性表中有2n个元素，以下操作中，在单链表上实现要比在顺序表上实现效率更高的是)。A.除指定元素

√B.最后一个元素的后面插入一个新元素C.序输出前k个元素D.换第i个元素和第2n—个素的值(i=0，1…，1)对于A删除指定元素，在顺序表中需要移动较多元素，而在单链表上执行同样的操作不需要移动元素，因此单链表的效率要高一些。对于在最后一个元素的后面插入一个新元素不需要移动元素，顺序表的效率和单链表相同。对于顺序输出前元素，单链表和顺序表的效率几乎相同。对于D交换第i个元素和第2ni一1个元素的值i=0，1，…n一1)，由于顺序表可以实现随机查找，因此顺序表的效率会更高一些。12.下的算法实现的是带附加头结点的单链表数据结点逆序连接，空缺处应当填()。reverse(pointerh){／／为附加头点指针p，P=h一＞next；h＞；while(P|=null){q=P：P=P一＞next：q一＞next=h一＞next；h一＞next=(_____)；}A.hB.PC.q

√D.q＞nexth一＞next=q；表示将当前结点作为头结点后的第一元素结点插入。

13.若度为n的线性表采用顺序存储结构，在其第位置插入一个新元素的算法的时间复杂度为)(1≤in+1)A.O(0)B.O(1)C.O(n)D.O(n

√)此题考查的知识点是线性表基本操作的时间复杂度。顺序存储的线性表插入元素时需要从插入位置开始向后移动元素，腾出位置以便插入，平均移动次数为(n+1)／2，所以复杂度为选C14.线表a

，a

，…，

)链式存储方式存储时，访问第i置元素的时间复杂度为()。A.O(i)B.O(1)C.O(n)

√D.O(i1)此题考查的知识点是线性表基本操作的时间复杂度。链式存储的线性表访问第个位置的元素时需要从头开始向后查找，平均查找次数为(n+1)／所以时间复杂度为O(n)，C。15.非的循环单链表head的尾结P满()A.p＞next=headB.p＞next=NULLC.p=NULLD.p=head

√此题考查的知识点是循环单链表的存储定义空的循环单链表的尾结点的指针指向头结点以选、CD均不能构成非空的循环单链表。16.双链表中有两个指针域，prior和next，别指向前驱及后继，P向链表中的一个结点q指向一个待插入结点，现要求在插入q，则正确的插入为)A.P＞prior=q；＞p一＞prior一next=q；＞prior=p＞prior；√B.q＞prior=p＞prior；＞prior＞next=q；q一next=P；p一＞prior=q；C.q＞next=P；p＞next=q；p＞prior一>next=q；＞next=P；D.p＞prior一＞next=q；q一＞next=P；q一＞prior=p一＞prior；一prior=q；此题考查的知识点是双向链表的插入操作。在插入，要修p的prior针、所指结点的next指，所以选AB、C、都将地址丢失，连接失败。17.静链表中指针表示的是)A.存地址B.组下标C.一元素数组下标D.、右孩子地址

√静态链表中指针表示的是下一元素的数组下标。18.在链表指针为P的结点之后插入指针为结点，正确的操作是)。A.p＞next=s；s＞next=p一next；B.s＞next=p一＞next；一next=s；C.p＞next=s；p＞next=s一next；D.p＞next=s一＞next；一next=s；

√此题考查的知识点是单链表的插入操作。要先保p的后继结点，再连入s点，所以BAC、D都将使地址丢失，连接失败。19.对一个头指针为head的带头结点单链表，判定该表为空表的条件是)。A.head==NULLB.head一＞next==NULLC.head-＞next==headD.head!=NULL

√

此题考查的知识点是带头结点的单链表操作。带头结点的单链表空的时候表示只有一个结点存在，但没有存信息。所以选BA示没有结点，示循环单链表，D示有一个指针不为空，所以都不对。20.以与数据的存储结构无关的术语是()。A.环队列B.表C.希表D.

√此题考查的知识点是对数据结构和存储结构的理解A、BC述的均为物理结构即数据的存储结构D逻辑结构，所以选D21.以数据结构中，)线性数据结构。A.义表B.叉树C.疏矩阵D.

√此题考查的知识点是线性结构的定义。线性结构的定义可简单地理解为元素只有一个前导、一个后继，而AB、多个后继，均错，所以选二、综合用(总题数：，数30.00)22.合应用题41-47小题。__________________________________________________________________________________________23.有个集合A和B利用带头结点链表表示，设头指针分别为lalb。两集合的链表元素皆为递增有序。设计一个算法，将A与合并，合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间，只能在AB的原有结点空间上完成。要求：(1)给出算法的基本设计思。(2)根据设计思想，采用cC++Java言描述算法，关键之处给出注释。(3)别给出算法各部分的时间复杂度。__________________________________________________________________________________________正确答案：(确答案：(1)法的基本设计思想：分别从、B的头结点开，依次比较A、B中元素的内容，如果A中元素值大于B中的元素，则将B中的结插入结果链表，反之将A的结点插入结果链表。由于题目中要求将结果链表中的结点按元素值的大小依次递增地排列。因此，如果、中两个元素值相同，只将其中的一个加入结果链表。算法的设计如下：typedefLNode{int：structLNode*next}*LinkedlistLinkedListUnion(LinkedListla，pa=la一＞next；pb=lb一＞next／／设工作指针pa和pc=la；／为果链表当前结点的前驱指针while(pa&&pb){if(pa一＞datapb一＞data){pc一＞next=pa；pc=pa；pa=pa一＞next；}elseif(pa一＞＞pb＞data){pc＞next=pb；pb=pb-＞；}else{／／处理pa＞data=pb一＞data．pc一＞next=pa；pa=pa一next：u=pbpb=pb一nextfree(u)}}next=pa／／若la表空，则链入结果表else＞next=pb／若表空，则链入结果表；／／释放lb头点；}(3)本中的主要操作是依次比较AB链表中的数据元素值的大小，因此时间复杂度为O(n)。24.线表a

，

，a

，…，

)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素，并其与后继元素位置相交换。如果线性表中找不到该元素，则将该元素插入表中并使表中元素仍递增有序。(1)出算法的基本设计思想。(2)根据设计思想，采用C或C++或Java语描述算法，关键之处给出注释。(3)别给出算法各部分的时间复杂度。__________________________________________________________________________________________正确答案：(确答案：(1)序存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在表中查找数值为的元素”，这里应使用折半查找方法。(2)法的设计如下：voidsearchExchangeInsert(ElemTypea[]，ElemTypex){intlow=0：inthigh=n一：mid；／／low和high指线性表下界和上界的下标while(low＜=high){／／／找中间位置if(a[mid]==x)break／找到x，退while循环elseif(a[mid]＜x)low=mid+1；／中mid的右部去查elsehigh=mid一／／到中点mid的部去查if(a[mid]==x&&mid!=n){／／若最后一个元素与x相，／／则不存在与其后继交换的操作t=a[mid]；a[mid]=a[mid+1]；a[mid+1]=t；}／／数值x与后继元素位置交换if(low＞high){／／查失败，插入数据元素inti；—：

ihigh；i一)a[i+1]=a[i]；／／后移元素a[low]=x；／插入x}／结束插入}在利用折半查找的方法查找x的过程中时间复度为

n)交换元素位置时的时间复杂度为O(1)当查找不成功时，插入元素时的时间复杂度为。)25.已顺序表A在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下，设计算法，将所有奇数号元素移到所有偶数号元素前。(1)出算法的基本设计思想。(2)根据设计思想，采C或C++或Java语言描述算法，关键之处给出注释。(3)明你所设计算法的时间复杂度和空间复杂度。__________________________________________________________________________________________正确答案：(确答案：(1)本的设计思想：先将偶数号元素复制到一个辅助空间，然后整理数组剩下的奇数号元素，最后将辅助空间中的元素复制到数组的后半部分，但这种思路的空间复杂度为。另一种思路：①在数组尾部从后往前找到第一个奇数号元素，将此元素与其前面的偶数号元素交换。这样，就形成了两个前后相连且相对顺序不变的奇数号元“块②暂存①“块前面的偶数号元素“块”内奇数号结点依次前移，然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了三个连续的奇数号元素“块”③暂存②中“块”前面的偶数号元素，将“块”内奇数号结点依次前移，然后将暂存的偶数号结点复制到空出来的数组单元中。就形成了四个连续的奇数号元素“块”④如此继续，直到前一步的“块”前没有元素为止。(2)法的设计如下：voidSwap(ElemType，intn){int，v=1／i工作指针，初始假设n为奇数，v“块”的大小ElemTypetemp：／辅助变量％2==0)i=n一1／／若n偶数，则令i为n一1while(i＞1){／／假设数组从1始存放。当，气泡浮出水面temp=A[i—1]／／将“块”前的偶数号元素暂存for(int；j＜j++)／／将大小为v的“块”整体向前平移A[i一1+j]=A[i+j]／／从前往后依次向前平移A[i+v一1]=temp／暂存的奇数号元素复制到平移后空出的位置i一；v++／／指针向前，块大小增1／／while一共进行了n2次交换每交换的元素个数从1一n2因此时间复杂度为O(n

)虽然时间复杂度为2

)但因n

前的系数很小，实际达到的效率是很高的。算法的空间复杂度为O(1)。)26.已单链表L是一个递增有序表，试写一高效算法，删除表中值大于min且小于max的结点表中有这样的结点)同时释放被删结点的空间，这里和max两个给定的参数。__________________________________________________________________________________________正确答案(确答案struetnode{data；structnode*next}ListNodetypedef*；voidDeleteList(LinkList，DataType，DataTypemax){ListNode*P，*q，*h;P=L一＞next／采用代表头结点的单链表p一＞＜=min){／找比min大的前个元素位置q=pp=p一＞next;}p=q;／／保存这个元素位置＆＆q一＞＜max)q=q一next；／／找比max小最后一个元素位置while(p＞next!=q){h=p一＞；p=p＞；；／／释放空间}p一＞next=q；／把断点链上}提示：首先想到的是拿链表中的元素一个个地max和min比，然后删除这个结点。其实因为已知其是有序链表，所以只要找到大于min结点的直接前趋结点，再找到小于max的结点，然后一把中间的全部摘掉就可以了。27.线表a

，

，a

，…，

)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容：(1)最少的时间在表中查找数值为x的元素。(2)若到将其与后继元素位置相交换。(3)找不到将其插入表中并使表中元素仍递增有序。__________________________________________________________________________________________正确答案：(确答案：(1)序存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在表中查找数值为的元素里应使用折半查找方法voidSearchExchangelnsert(ElemTypea[]；ElemTypex)a是具有n个元素的递增有序线性表，顺序存储。本算法在表中查找数值为x／／元素如查到则与其后继交换位置如查不到则插入表中，且使表仍递增有{low=0high=n一1／／lowhigh向线性表下界和上界的下标while(low＜=high){mid=(low+high)／2；／／找中间位置if(a[mid]==x)break；／／找到退出while循环elseif(a[mid]x)low=mid+1；／／到中点mid右半去查high=mid—／到中点左半去查}／／若最后一个元素与x相，则不存在与其后继交换的操作{；a[mid]=a[mid+1]；a[mid+1]=t；}／／数值x与后继元素位置交换if(low＞high)／／查找失败，插入数据元素x{；i＞high；i一一)a[i+1]=a[i]；／／后移元素；／插入}结束插入}∥结束本算法(2)算法讨论首先是线性表的描述。算法中使用一维数a示线性表，未使用包含数据元素的一维数组和指示线性表长度的结构体。若使用结构体，对元素的引用应使用elem[i]另外，元素类型就假定是ElemType，

未指明具体类型。其次，C一维数组下标从开始，若说有凡个元素的一维数组，其最后一个元素的下标应是n1最后，本算法可以写成三个函数，即查找函数、交换后继函数与插入函数，写成三个函数显得逻辑清晰、易读。)28.设一个双链表L每个结点中除有priordata和next3个域外，有一个访问频度域freq，在链表被启用之前，其值均初始化为零。每当在链表进行一LocateNode(L，运算时，令元素值x的结点中freq域值加1并调整表中结点的次序，使其按访问频度的递减排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的运的算法。__________________________________________________________________________________________正确答案：(确答案：typedefstructDuLNode{ElemTypedata；intfreq；，*next；}*DListlocate(DList，ElemTypex){／L是带头结点的按访问频度递减的双向链表DList一＞next，q／／p为L的工作指针，q为P的驱，用于查找插入位置while(P&&p＞data!=x)p=p-next；／／查找值为x的结点if(!P){printf(不存在所查结点＼n”)exit(0)；else{p＞freq++；／／令元素值为x的结点的freq域加p一＞nextpred=p一＞pred；／／将P结从链表上摘下p＞pred＞next=p一＞next：q=p一pred；／以下查找P点的插入位置while(q|=L&&q一＞freq＜p一freq)q=q一＞pred一next=q一next;q一＞一＞pred=P／／将P结插入p一＞pred=q；一＞next=p;}return(P)／／返回值为的结点的指}提示：在算法中先查找数据x查找成功时结点的访问频度域增1，最后将该结点频度递减插入链表中。)29.有个不带头结点的单链表链表中结点都有两个域数据域和指针Iink已知初始时该单链表无序，请设计一个算法将该链表按结点数据域的值的大小，将其从小到大依次重新链接，在链接过程中不得使用除该链表以外的任何链结点空间。要求：(1)给出算法的基本设计思想(2)根据设计思想，采用CC++Java言描述算法，关键之处给出注释。__________________________________________________________________________________________正确答案：(确答案：(1)法的基本设计思想：本题实质上是一个排序问题。链表上的排序采用直接插入排序比较方便，即首先假定第一个结点有序，然后，从第二个结点开始，依次插入到前面有序链表中，最终达到整个链表有序。(2)算法设计如下：typedefstructLNode{intdata；structLNode*link}*linkedlist；Lnode*p，p=list一＞link／／p工作指针，指向待排序的当前元素list一＞link=null；／／假第一个元素有序，即链表中现只有一个结点while(P!=null)f一＞link／r是P的继q=list一＞data＞一data){／／处理待排序结点P比第一个元素结小的情况p一＞link=listlist=p／／链表指针指向最小元素}else{／查找元素值最小的结点while(q一＞link==null&&q＞link＞data＜一＞data)q=q一＞linkp一＞link=q一link；／／将当前排序结点链入有序链表中q一＞link=P；}P=r；／／向下个待排序结点}})30.如以单链表表示集合设集合A用单链LA表，集B用单链表示设计算法求两个集合的差，即AB__________________________________________________________________________________________正确答案：(确答案：由集合运算的规则知，集合的差为包含所有属于A不属于元素，因此，算法的思路在于对于所有属于集合的元素e集合B进行查找能找到则说明它不属于B应从LA中除。若LA的长度为O(n)，的度为O(m)，则该算法的时间复杂度O(mXn)算法参考伪代码如下：voidDifference(LinkList*LA，LinkListLB)／／设，LB均具有头结点{，*pre*p*r：pre=LA；一＞next／／指向LA表中的某一结点，而pre指P的前面一个结点while(P!=NULL){＞／／遍历LB表，判断中元素是否在LB中Node*while(q|=NULL&&q一＞data!=＞data)q=q一＞nextif(q!=NULL){／／LB中找到相同结元素，则应在LA中除该结点r=Ppre一＞next=r一next：p=p一next；}else{／／未能找到，说明该结点属于A-B继在LA中下一个元素进行判断pre=Pp=p＞next}}})31.已3带头结点的线性链表A、BC中的结点均依元素值自小至大非递减排列能存在两个以上值相同的结点)编写算法对链A行如下操作使操作后的链表A中仅留下3个表中均包含的据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为其中m、和p分别为3个的长度。__________________________________________________________________________________________

正确答案确答案structLNode{intdatastructLNodenext}*LinkedlistLinkedListCommon(LinkedListA，C){／／链表A链表B和链表C是三个带头结点且结点元素值非递减排列的有序表／／本算法使链表留下三个表均包含的结点点值不重复放所有结点Linkedlist*pa*pb，*pre*upa=A-nextpb=B一＞nextpc=C一next／／papbPc分别是链表ABC的工作指针；／／pre是链表当前结点的前驱结点的指针while(pa&pb&&pc){／／当链表AB和C均不空时，查找三链表共同元素while(pa&&pb)一＞data＜pb＞data){u=Pa：pa=pa一＞nextfree(u)}／结点元素值小时后移指针else(pa-＞＞pb一＞data)pb=pb一＞next：elseif(pa&&pb){／／处理链表A和B元值相等的结点while(pc&&pcdata＜pa一data)pc=pc一＞nextif(pc){／／当前结点值与当结点值不等，后指针一＞data＞＞data){u=papa=pa一＞nextfree(u)}／／pcpa和pb对应结点素值相等if(pre==A){pre-＞next=pa；pre=pa；＞next；／结果表中第一个结点else＞data==pa-＞data)／(理)复结点不链入链表A{u=pa；pa=pa一＞next；free(u)}else{pre-＞next=pa；pre=papa=pa一＞next}／将新结点链入链表＞nextpc=pc-＞next／／链表的工作指针后移／elsepcpa和pb对应结点元素值相等}if(pa==null)pre-＞next=null；／／原链A已到尾，置新链表A表尾else{／／处理原链表A未到尾而链表B或表C到尾的情况pre-＞next=null／／置链表A表尾标记while(pa!=null){u=papa=pa-＞next；free(u)；／／删除原链表A剩余元素}}})32.已非空链表A其指针list，表中的结点由两部分组成：数据data和指针link。计一个算法，将链表中数据域值最小的那个链结点移到链表的最前面，在不额外申请新的链结点的情况下，使得算法时间复杂度和空间复杂度尽可能低。要求：(1)出算法的基本设计思想。(2)根据设计思想，采用C或C++Java言描述算法，关键之处给出注释。__________________________________________________________________________________________正确答案：(确答案：(1)法的基本设计思想：首先要查找最小值结点。将其移到链表最前面，实质上是将该结点从链：上摘(是删除并回收空间)，再插入到表的最前面(2)算的实现如下typedefstructLNode{chardata；LNode*link；}*LinkedlistLinkedListdelinsert(LinkedListlist){／／将链表中数据域值最小的那个结点移到链表的最前面Linkedlist*P，*pre，；P=list＞link／／是链表的工作指针；／／pre向链表中数据域最小值结点的前驱q=P；／／q指向数据域最小值结点，初始假定是第一结点while(p一＞link!=null){一＞link＞data＜q一＞data){pre=Pq=p＞link}／找到新的最小值结点p=p一link}if(q!=list一＞link){／／若最小值是第一元素结点，则不需再操作一＞link=q一＞link：／／将最小值结点从链表上摘下q一＞link=list＞link；／／q结点插到链表最前面listlink=q}}／算法结束)33.已一个双向链表，其结点结构为数据域data、指针域llink、右指针域rlink设指针向双向链表中的某个结点。写出一个算法，实现指向的结点和它的前缀结点之间顺序的互换。要求：(1)出算法的基本设计思想。(2)根据设计思想，采用C或C++语言描述法，关键之处给出注释。__________________________________________________________________________________________正确答案：(确答案：(1)法的基本思想：已知双向循环链表中的一个结点P，与前驱交换涉4个结点(P结，前驱结点，前驱的前驱结，后继结点6链。法的设计如下：typedefstructDuLNode{intdata；structDuLNode＞llink＞rlink＞Linkedlist；voidExchange(LinkedListP){／／将指结点与其前驱结点交换Linkedlistq一＞llink；q-＞llink-rlink=P／／的驱的前驱之后继为p-＞llink=q-＞＞llink／前驱指向其前驱的前驱q-＞rlink=p-＞rlink／／p前驱的后继为P后继＞llink=P／／与前驱交换P一＞rlink-llink=q／／的继的前驱指向原的前驱p一＞rlink=q；／／的后继指向其原来的前驱})34.两整数序列A=a

，

，a

，…，a

和

，

，b

，…，

已经存入两个单链表中，设计一个算法，判断序列否是序列A的序列。__________________________________________________________________________________________正确答案：(确答案：typedefstructLNode{intLNode*；}*Linkedlist；intPattern(LinkedList，B){／／和B分别是数据域为数的单链表，本算法判断链表B是是／／链表A的序列。如是，返回；否则，返回0表示失败。Linkedlist*P，*pre，；p=A：／p为链表A的作指针，本题假定链表A和链B无头结点pre=p；／pre记住每趟比较中链表A的开始结