【正文】 數(shù)鏈和一個(gè)偶數(shù)鏈，算法中不得申請(qǐng)新的結(jié)點(diǎn)空間。 } return C。 Cnext=pb。 } while(pb!=null){r=pbnext。 Cnext=pa。 while(pa!=null) {r=panext。 Cnext=pb。 }else{ r=pbnext。 Cnext=pa。 pb!=null) if(padata=pbdata){ r=panext。 while(pa!=null amp。 C=A。LinkList Union( LinkList A, LinkList B, LinkList C){ pa=Anext。}鏈表的合并：把元素遞增排列的鏈表A和B合并為C，且C中元素遞減排列，使用原結(jié)點(diǎn)空間。 j。 }}if(j0) //判斷l(xiāng)b是否為空 { [k]=[j]。 k。 i。j0){if ([i]=[j]){[k]=[i]。 //循環(huán)指針賦值，從后往前比較while (i0amp。 i=m。 n=。 //修改表頭結(jié)點(diǎn)指針值}（2）線性表的合并順序表的合并：順序存儲(chǔ)的線性表la，lb的關(guān)鍵字為整數(shù)，元素非遞減有序，線性表空間足夠大，試編寫(xiě)高效算法，將lb中元素合并到la中，使新的la的元素仍非遞減有序。 }Lnextnext=NULL。 p=q。 while (q){r=qnext。L){p=Lnext。i++,j)[i][j]。A) { for(i=1,j=。A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)8．線性表（ a1,a2,…,an）以鏈接方式存儲(chǔ)時(shí)，訪問(wèn)第i位置元素的時(shí)間復(fù)雜性為（ C ）。A．單鏈表 B．僅有頭指針的單循環(huán)鏈表 C．雙鏈表 D．僅有尾指針的單循環(huán)鏈表6．若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（ C ）(1=i=n+1)。 A．表元素 B．字符 C．?dāng)?shù)據(jù)元素 D．?dāng)?shù)據(jù)項(xiàng) E．信息項(xiàng)4．若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（ A ）存儲(chǔ)方式最節(jié)省時(shí)間。D．線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。B．線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。學(xué)習(xí)過(guò)程中要注意多積累，多看、多寫(xiě)一些相關(guān)算法。分析：線性表一章在線性結(jié)構(gòu)的學(xué)習(xí)乃至整個(gè)數(shù)據(jù)結(jié)構(gòu)學(xué)科的學(xué)習(xí)中，其作用都是不可低估的。三、考查重點(diǎn)1．線性結(jié)構(gòu)的特點(diǎn)；2．線性表在順序存儲(chǔ)及鏈?zhǔn)酱鎯?chǔ)方式下的基本操作及其應(yīng)用；3．線性表的順序存儲(chǔ)及鏈?zhǔn)酱鎯?chǔ)情況下，其不同和優(yōu)缺點(diǎn)比較，及其各自適用的場(chǎng)合。} } return A[s1]B[s2]? A[s1]:B[s2]。} else{d1=m1+1。} else if(s1+d1)%2==0 {d1=m1。} else{s1=m1+1。 else if(A[m1B[m2]) if(s1+d1)%2==0 {s1=m1。 m2=(s2+d2)/2。（2）算法實(shí)現(xiàn)如下：int M_search(int A[],int B[].int n){ int s1=0,d1=n1,m1,s2=0,d2=n1,m2。做此題時(shí)要把握算法的效率。（2）根據(jù)設(shè)計(jì)思想，采用C或C++或JAVA語(yǔ)言描述算法，關(guān)鍵之處給出注釋?，F(xiàn)在有兩個(gè)等長(zhǎng)升序序列A和B，試設(shè)計(jì)一個(gè)在時(shí)間和空間方面都盡可能高效的算法，找出兩個(gè)序列A和B的中位數(shù)。3.（11年）一個(gè)長(zhǎng)度為L(zhǎng)（L=1）的生序列S，處在第┌L/2┐個(gè)位置的數(shù)稱為S的中位數(shù)，例如，若序列S1=（11,13,15,17,19），則S1的中位數(shù)是15，兩個(gè)序列的中位數(shù)是含它們所有元素的升序序列的中位數(shù)。解法二：算法思想：創(chuàng)建大小為p的輔助數(shù)組S，將R中前p個(gè)整數(shù)依次暫存在S中，同時(shí)將R中后np個(gè)整數(shù)左移，然后將S中暫存的p個(gè)數(shù)依次放回到R中的后續(xù)單元。 reverse(R,0,n1)。}}void converse(int R[], int n, int p){ reverse(R,0,p1)。 R[l0ow+i]=R[highi]。i=(highlow)/2。（2）算法描述：void reverse(int R[], int low, int high){//將數(shù)組中從low到high的元素逆置 int temp。設(shè)reverse函數(shù)執(zhí)行將數(shù)組元素逆置的操作，對(duì)abcdefgh向左循環(huán)移動(dòng)3（p=3）個(gè)位置的過(guò)程如下：reverse(0,p1)得到cbadefgh；reverse(p,n1)得到cbahgfde；reverse(0,n1)得到defghabc。做此題時(shí)要考慮算法的時(shí)間和空間復(fù)雜度。（2）根據(jù)設(shè)計(jì)思想，采用C或C++或JAVA語(yǔ)言表述算法，關(guān)鍵之處給出注釋。 X0 return 1。 //如果ik，則p也后移}if(p==list)return 0。 i++。i=1。（3）算法描述：int locate(Linklist list, int k){p1=listlink。用整型變量i表示當(dāng)前遍歷了多少結(jié)點(diǎn)，當(dāng)ik時(shí)，指針p隨著每次遍歷，也向前移動(dòng)一個(gè)結(jié)點(diǎn)。當(dāng)遍歷到鏈表的最后一個(gè)結(jié)點(diǎn)時(shí)，指針p所指向的結(jié)點(diǎn)即為所查找的結(jié)點(diǎn)。做此題時(shí)要把握算法的效率。要求：（1）描述算法的基本設(shè)計(jì)思想；（2）描述算法的詳細(xì)實(shí)現(xiàn)步驟；（3）根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，采用程序設(shè)計(jì)語(yǔ)言描述算法（使用C或C++或JAVA語(yǔ)言實(shí)現(xiàn)），關(guān)鍵之處給出簡(jiǎn)要注釋。在不改變鏈表的前提下，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，查找鏈表中倒數(shù)第k個(gè)位置上的結(jié)點(diǎn)（k為正整數(shù)）?？梢苑旁诘诙拢瑢?shí)際這內(nèi)容貫穿每一章內(nèi)容中算法的度量。 (nlogn) (n)(logn) x=2。第2章 線性表一、考研知識(shí)點(diǎn)（一）線性表的定義和基本操作（二）線性表的實(shí)現(xiàn)二、考研真題（一）選擇題近兩年第2章沒(méi)有考選擇題，因?yàn)榇苏轮饕蔷€性表的操作，而且又是這門(mén)課的一個(gè)基礎(chǔ)，考綜合題的可能性比較大，而且可以和第3章、第9章和第10章的內(nèi)容結(jié)合來(lái)出題。 3. 2.數(shù)據(jù)結(jié)構(gòu)考研真題及知識(shí)點(diǎn)解析考察目標(biāo)1.理解數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法。掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及基本操作的實(shí)現(xiàn)，能夠?qū)λ惴ㄟM(jìn)行基本的時(shí)間復(fù)雜度與空間復(fù)雜度的分析。能夠運(yùn)用數(shù)據(jù)結(jié)構(gòu)的基本原理和方法進(jìn)行問(wèn)題的分析與求解，具備采用C、C++或Java語(yǔ)言設(shè)計(jì)與實(shí)現(xiàn)算法的能力。1．（11年）設(shè)n是描述問(wèn)題規(guī)模的非負(fù)整數(shù)，下面程序片段的時(shí)間復(fù)雜度是（ ）。 while(xn/2) x=2*x。 (n2)分析：答案是A，此題考查的是算法時(shí)間復(fù)雜度的計(jì)算。（二）綜合題1.（09年）已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表結(jié)點(diǎn)結(jié)構(gòu)為(data,link)，假設(shè)該鏈表只給出了頭指針list。若查找成功，算法輸出該結(jié)點(diǎn)的data值，并返回1；否則，只返回0。 分析：此題考查線性表的鏈?zhǔn)酱鎯?chǔ)，主要是線性表的基本操作的應(yīng)用。（1）算法基本思想如下：從頭到尾遍歷單鏈表，并用指針p指向當(dāng)前結(jié)點(diǎn)的前k個(gè)結(jié)點(diǎn)。（2）詳細(xì)實(shí)現(xiàn)步驟：增加兩個(gè)指針變量和一個(gè)整型變量，從鏈表頭向后遍歷，其中指針p1指向當(dāng)前遍歷的結(jié)點(diǎn)，指針p指向p1所指向結(jié)點(diǎn)的前k個(gè)結(jié)點(diǎn)，如果p1之前沒(méi)有k個(gè)結(jié)點(diǎn)，那么p指向表頭結(jié)點(diǎn)。當(dāng)遍歷完成時(shí)，p或者指向表頭結(jié)點(diǎn)，或者指向鏈表中倒數(shù)第k個(gè)位置上的結(jié)點(diǎn)。p=list。while(p1){ p1=p1link。 if(ik)p=pnext。 //鏈表沒(méi)有k個(gè)結(jié)點(diǎn)else{ printf(“%\n”,pdata)。}}2.（10年）設(shè)將n(n,1)個(gè)整數(shù)存放到一維數(shù)組R中，試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面盡可能有效的算法，將R中保有的序列循環(huán)左移P（0﹤P﹤n）個(gè)位置，即將R中的數(shù)據(jù)由（X0 X1 ……Xn1）變換為（Xp Xp+1 ……Xn1 X1 ……Xp1）要求：（1）給出算法的基本設(shè)計(jì)思想。（3）說(shuō)明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度分析：此題考查的是數(shù)組的操作，線性表的順序存儲(chǔ)的核心就是數(shù)組，因此此題實(shí)質(zhì)上是考查的線性表的順序存儲(chǔ)的操作及其應(yīng)用。解法一：（1）算法的基本設(shè)計(jì)思想：可以將這個(gè)問(wèn)題看做是把數(shù)組ab轉(zhuǎn)化成數(shù)組ba（a代表數(shù)組的前p個(gè)元素，b代表數(shù)組中余下的np個(gè)元素），先將a逆置得到a1b，再將b逆置得到a1b1，最后將整個(gè)a1b1逆置得到（a1b1）1=ba。注：reverse中，兩個(gè)參數(shù)分別表示數(shù)組中待轉(zhuǎn)換元素的始末位置。 for(i=0。i++) { temp=R[low+i]。 R[highi]=temp。 reverse(R,p,n1)。}（3）上述算法中三個(gè)reverse函數(shù)的時(shí)間復(fù)雜度分別是O(p/2)、O((np)/2)、O(n/2)，故所設(shè)計(jì)算法的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(p)。例如，若S2=（2,4,6,8,20），則S1和S2的中位數(shù)是11。要求：（1）給出算法的基本設(shè)計(jì)思想。解答：此題考查線性表的順序存儲(chǔ)，主要是線性表的基本操作的應(yīng)用。（1）算法的基本設(shè)計(jì)思想如下：分別求出序列A 和B的中位數(shù)，設(shè)為a和b，求序列A和B的中位數(shù)過(guò)程如下：1）若a=b，則a或b即為所求中位數(shù)，算法結(jié)束；2）若ab，則舍棄序列A中較小的一半，同時(shí)舍棄序列B中較大的一半，要求舍棄的長(zhǎng)度相等；3）若ab，則舍棄序列A中較大的一半，同時(shí)舍棄序列B中較小的一半，要求舍棄的長(zhǎng)度相等；在保留的兩個(gè)升序序列中，重復(fù)過(guò)程1）3），直到兩個(gè)序列中只含一個(gè)元素時(shí)為止，較小者即為所求的中位數(shù)。 //分別表示序列A和B的首位數(shù)、末尾數(shù)和中位數(shù) While(s1!=d1||s2!=d2){ m1=(s1+d1)/2。 if(A[m1]==B[m2]) return A[m1]。d2=m2。d2=m2。s2=m2。s2=m2。}（3）算法的時(shí)間復(fù)雜度為O(logn)，空間負(fù)責(zé)雜度為O(1)。單鏈表中設(shè)置頭指針、循環(huán)鏈表中設(shè)置尾指針而不設(shè)置頭指針的各自好處；4．能分析所寫(xiě)算法的時(shí)間和空間復(fù)雜度。線性表一章小的知識(shí)點(diǎn)比較少，一般會(huì)出一個(gè)綜合題，并且容易和第三章、第九章和第十章的內(nèi)容結(jié)合來(lái)考，注意對(duì)基本知識(shí)的理解，能夠利用書(shū)上的理論解決具體問(wèn)題。四、練習(xí)題（一）選擇題1．下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？（ A ）A．存儲(chǔ)密度大 B．插入運(yùn)算方便 C．刪除運(yùn)算方便 D．可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示2．下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？（ B ）A．線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。C．線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。3．線性表是具有n個(gè)（ C ）的有限序列（n0）。A．順序表 B．雙鏈表 C．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D．單循環(huán)鏈表5．某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（ D ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A. O(0) B. O(1) C. O(n) D. O(n2) 7. 對(duì)于順序存儲(chǔ)的線性表，訪問(wèn)結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為（ C ）。A．O（i） B．O（1） C．O（n） D．O（i