【正文】 t=pnext； pnext=s； pnextprior=s； *D． sprior=p； snext=pnext； pnextpror=s； pnext=s； 12. 在一個(gè)單鏈表中，已知 *q 結(jié)點(diǎn)是 *p 結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在 *q 和 *p 之間插入結(jié)點(diǎn) *s，則執(zhí)行 ( )。 A． snext=pnext； pnext=s； B． pnext=snext； snext=p； *C． qnext=s。 snext=p； D． pnext=s。 snext=q； 13. 在一個(gè)單鏈表中，若 *p 結(jié)點(diǎn)不是最后結(jié)點(diǎn)。在 *p 之后插入結(jié)點(diǎn) *s，則執(zhí)行 ( )。 A． snext=p； pnext=s。 *B． snext=pnext； pnext=s； C． snext=pnext； p=s； D． pnext=s； snext=p。 14. 若某線性表中最常用的操作是取第 i 個(gè)元素和找第 i 個(gè)元素的前驅(qū)元素，則采用 ( )存儲(chǔ)方式最節(jié)省時(shí)間。 *A．順序表 B. 單鏈表 C．雙鏈表 D．單循環(huán)鏈表 15．設(shè) rear 是指向非空帶頭結(jié)點(diǎn)的單循環(huán)鏈表的尾指針，則刪除表頭結(jié)點(diǎn)的操作可表示為 ( )。 A． p=rear； rear=rearnext； free(p) B． rear=rearnext； free(rear)； C． rear=rearnextnext； free(rear)； *D． p=rearnextnext；rearnextnext=pnext； free(p)； 16．在一個(gè)單鏈表中，若刪除 *p 結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行 ( )。 *A． q=pnext； pnext=qnext； free(q)； B． p=pnext； pnext=pnextnext； free(p)； C． pnext=pnext； free(pnext)； D． p=pnextnext；free(pnext)； 17． 設(shè)指針 p 指向雙鏈表的某一結(jié)點(diǎn)，則雙鏈表結(jié)構(gòu)的對(duì)稱性可用 ( )式來刻畫。 A ． ppriornext==pnextnext B ． ppriorprior==pnextprior *C ． ppriornext==pnextprior D． pnextnext==ppriorprior 18．在循環(huán)鏈表中，將頭指針改設(shè)為尾指針 rear 后，其頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的存儲(chǔ)位置分別是 ( )。 A． rear 和 rearnextnext *B． rearnext 和 rear C． rearnextnext 和 rear D． rear 和 rearnext 19．循環(huán)鏈表的主要優(yōu)點(diǎn)是 ( )。 A．不再需要頭指針了 B．已知某個(gè)結(jié)點(diǎn)的位置后，容易找到它的直接前驅(qū) C．在進(jìn)行插入、刪除操作時(shí)，能更好地保證鏈表不斷開 *D．從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表 20．在線性表的下列存儲(chǔ)結(jié)構(gòu)中，讀取元素花費(fèi)時(shí)間最少的是 ( )。 A．單鏈表 B．雙鏈表 C．循環(huán)鏈表 *D．順序表 二、判斷題 √ 1．順序存儲(chǔ)的線性表可以隨機(jī)存取。 ╳ 2．順序存儲(chǔ)的線性表的插入和刪除操作不需要付出很大的代價(jià)，因?yàn)槠骄看尾僮髦挥薪话氲脑匦枰苿?dòng)。 √ 3．線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此是屬于同一數(shù)據(jù)對(duì)象。 ╳ 4．在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上不一定相鄰。 √ 5．在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。 √ 6．在單鏈表中，可以從頭結(jié)點(diǎn)開始查找任何一個(gè)元素。 ╳ 7．線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。 √ 8．在線性表的順 序存儲(chǔ)結(jié)構(gòu)中，插入和刪除元素時(shí)，移動(dòng)元素的個(gè)數(shù)與該元素的位置有關(guān)。 ╳ 9．在單鏈表中，要取得某個(gè)元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。 ╳ 10．順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。 三、填空題 1．為了便于討論，有時(shí)將含 n(n0)個(gè)結(jié)點(diǎn)的線性結(jié)構(gòu)表示成 (a1， a2，?， an)，其中每個(gè) ai 代表一個(gè) __結(jié)點(diǎn) _。 a1 稱為 _第一個(gè) _結(jié)點(diǎn)， an 稱為 __最后一個(gè) _結(jié)點(diǎn)， i 稱為 ai 在線性表中的 _位置 __。對(duì)任意一對(duì)相鄰結(jié)點(diǎn) ai、 ai+1(1≤ in)， ai 稱為 ai+1 的直接 _前驅(qū) _， ai+1稱為 ai的直接 __后繼 __。 2．線性結(jié)構(gòu)的基本特征是：若至少含有一個(gè)結(jié)點(diǎn)，則除起始結(jié)點(diǎn)沒有直接 __前驅(qū) _外，其他結(jié)點(diǎn)有且僅有一個(gè)直接 __前驅(qū) _；除終端結(jié)點(diǎn)沒有直接 __后繼 _外，其他結(jié)點(diǎn)有且僅有一個(gè)直接 _后繼 __。 5 3．所有結(jié)點(diǎn)按一對(duì)一的鄰接關(guān)系構(gòu)成的整體就是 __線性 __結(jié)構(gòu)。 4．線性表的邏輯結(jié)構(gòu)是 __線性 _結(jié)構(gòu)，其所含結(jié)點(diǎn)的個(gè)數(shù)稱為線性表的 ___長(zhǎng)度 _。 5．在單鏈表中，刪除 p 所指結(jié)點(diǎn)的直接后繼的操作是 __ q=pnext； pnext=qnext； free(q)； ___ 6．非空的單循環(huán)鏈 表 head 的尾結(jié)點(diǎn) (由指針 p 所指 )滿足 __ pnext= head _____。 7． rear 是指向非空帶頭結(jié)點(diǎn)的單循環(huán)鏈表的尾指針，則刪除起始結(jié)點(diǎn)的操作可表示為 __ p=rearnext； q=pnext； pnext=qnext； free(q)； ____。 8．對(duì)于一個(gè)具有 n 個(gè)結(jié)點(diǎn)的單鏈表，在 p 所指結(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為 __O(1)__，在給定值為 x 的結(jié)點(diǎn)后插入新結(jié)點(diǎn)的時(shí)間復(fù)雜度為 __ O(n)__。 9．單鏈表表示法的基本思想是用 ___指針 ___表示結(jié)點(diǎn)間的邏輯關(guān)系。 10． 在順序表中插入或刪除一個(gè)元素，平均需要移動(dòng) _一半 _元素，具體移動(dòng)的元素個(gè)數(shù)與 __元素的位置 _有關(guān)。 11．在一個(gè)長(zhǎng)度為 n 的向量的第 i(1≤ i≤ n+1)個(gè)元素之前插入一個(gè)元素時(shí)，需向后移動(dòng) ___ ni+1__個(gè)元素。 12．在一個(gè)長(zhǎng)度為 n 的向量中刪除第 i(1≤ i≤ n)個(gè)元素時(shí)，需向前移動(dòng) __ ni __個(gè)元素。 13．在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向 ___前驅(qū) __，另一個(gè)指向 ___后繼 ___。 14．在一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表中， p 指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的指針 head 可用 p 表示為 head=__ pnextnext ； ___。 15．設(shè) head 指向單鏈表的表頭， p 指向單鏈表的表尾結(jié)點(diǎn)，則執(zhí)行 pnext=head 后，該單鏈表構(gòu)成 __單循環(huán)鏈表 ___。 16．在單鏈表中，若 p 和 s 是兩個(gè)指針，且滿足 pnext 與 s相同，則語句 pnext=snext的作用是 _刪除 __s 指向的結(jié)點(diǎn)。 17．設(shè) r 指向單循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)，要在最后一個(gè)結(jié)點(diǎn)之后插入 s 所指的結(jié)點(diǎn)，需執(zhí)行的三條語句是 ___snext= rnext __； rnext=s； r=s； 18．在單鏈表中，指針 p 所指結(jié)點(diǎn)為最后一個(gè)結(jié)點(diǎn)的條件是 __ pnext=NULL___。 19．在雙循環(huán)鏈表中，若要在指 p 所指結(jié)點(diǎn)前插入 s 所指的結(jié)點(diǎn)，則需執(zhí)行下列語句： snext=p； sprior=pprior； __ ppriornext __=s； pprior=s； 20．在單鏈表中，若要在 p 所指結(jié)點(diǎn)之前插入 s 所指的結(jié)點(diǎn)，可進(jìn)行下列操作： snext=___ pnext __； pnext=s； temp=pdata； pdata=__ sdata ___； sdata=__ temp _； 四、應(yīng)用題 1．描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn) (第一個(gè)元素結(jié)點(diǎn) )。 答：首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)的線性表中的第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。為了操作方便，通常在鏈表的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)。頭指針是指向鏈表中的第一個(gè)結(jié)點(diǎn)的指針。 2．何時(shí)選用順序表，何時(shí)選用鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)為宜？ 答：從空間上來看，當(dāng)線性表的長(zhǎng)度變化較大、難以估計(jì)其規(guī)模時(shí)，選用動(dòng)態(tài)的鏈表作為存儲(chǔ)結(jié)構(gòu)比較合適，但鏈表除了需要設(shè)置數(shù)據(jù)域外，還要額外設(shè)置指針域，因 此當(dāng)線性表長(zhǎng)度變化不大、易于事先確定規(guī)模時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序存儲(chǔ)結(jié)構(gòu)。從時(shí)間上來看，若線性表的操作主要是查找，很少進(jìn)行插入和刪除操作時(shí)，應(yīng)選用順序表。對(duì)于頻繁進(jìn)行插入和刪除操作的線性表，宜采用鏈表作為存儲(chǔ)結(jié)構(gòu)。 3．在順序表中插入和刪除一個(gè)結(jié)點(diǎn)需平均移動(dòng)多少個(gè)結(jié)點(diǎn)？具體的移動(dòng)次數(shù)取決于哪兩個(gè)因素？ 答：平均移動(dòng)表中大約一半的結(jié)點(diǎn)，插入操作平均移動(dòng) n/2 個(gè)結(jié)點(diǎn)，刪除操作平均移動(dòng)（ n1） /2 個(gè)結(jié)點(diǎn)。具體移動(dòng)的次數(shù)取決于表長(zhǎng)和插入、刪除的結(jié)點(diǎn)的位置。 4．為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指 針更好？ 答：?jiǎn)窝h(huán)鏈表中無論設(shè)置尾指針還是頭指針都可以遍歷表中任一個(gè)結(jié)點(diǎn)，但設(shè)置尾指針時(shí)，若在表尾進(jìn)行插入或刪除操作可在 O(1)時(shí)間內(nèi)完成，同樣在表頭進(jìn)行插入或刪除操作也可在 O(1)時(shí)間內(nèi)完成。但若設(shè)置的是頭指針，表尾進(jìn)行插入或刪除操作，需要遍歷整個(gè)鏈表，時(shí)間復(fù)雜度為 O(n)。 5．雙鏈表和單循環(huán)鏈表中，若僅知道指針 p 指向某個(gè)結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn) *p 從相應(yīng)的鏈表中刪除？若可以，其時(shí)間復(fù)雜度各為多少？ 答：能刪除。雙鏈表上刪除 p 所指向的結(jié)點(diǎn)的時(shí)間復(fù)雜度為 O(1)，單循環(huán)鏈表上刪除 p 所指向的結(jié)點(diǎn)的 時(shí)間復(fù)雜度為 O(n)。 6．下列算法的功能是什么？ LinkList *testl(LinkList *L) {//L 是無頭結(jié)點(diǎn)的單鏈表 LinkList *q， *p； if(Lamp。amp。Lnext) { q=L； L=Lnext； p=L。 while(pnext) p=pnext； pnext=q。 qnext=NULL； } return L； } 答：如果長(zhǎng)度大于 1，則將首元結(jié)點(diǎn)刪除并插入到表尾。 7．如果有 n 個(gè)線性表同時(shí)共存，并且在處理過程中各表的長(zhǎng)度會(huì)發(fā)生動(dòng)態(tài)變化，線性表的總長(zhǎng)度也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選擇哪一種存儲(chǔ)結(jié)構(gòu)？為什么？ 答：應(yīng)選用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。因?yàn)轫樞虮硎庆o態(tài)存儲(chǔ)結(jié)構(gòu)，只能預(yù)先分配，不能隨著線性表長(zhǎng)度的改變而變化。而鏈表則可根據(jù)需要?jiǎng)討B(tài)地申請(qǐng)空間，因此適用 6 于動(dòng)態(tài)變化表長(zhǎng)的線性表。 8．若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入、刪除操作，但要求以最快的方式存取線性表的元素，應(yīng)該用哪種存儲(chǔ)結(jié)構(gòu)？為什么？ 答：應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。因?yàn)轫樞虼鎯?chǔ)結(jié)構(gòu)存取元素操作的時(shí)間復(fù)雜度為 O(1)。 五、 算法設(shè)計(jì)題 假設(shè)算法中用到的順序表和鏈表結(jié)構(gòu)如下： define maxsize 100。 Typedef struct node1 {datatype data[maxsize]。 int length } SeqList。 Typedef struct node2 {datatype data。 struct node2 *next } LinkedList 。 1．試用順序表作為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)將線性表 (a0， a1， a2，? an1)就地逆置的操作，所謂“就地”是指輔助空間為 O(1)。 答： (1)順序表的就地逆置 分析：分別用兩個(gè)整型變量指向順序表的兩端，同時(shí)向中間移動(dòng)，移動(dòng)的同時(shí)互換兩個(gè)下標(biāo)指示的元素的值。 void Seqreverse(SeqList *L){／／順序表的就地逆置 for(i=0； j=Llength1； ij； i++， j) {t=Ldata[i]。 Ldata[i]=[j]。 Ldata[j]=t。 } } (2)鏈表的就地逆置 分析：本算法的思想是逐個(gè)地把 L 的當(dāng)前元素 r 插入到新的鏈表頭部。 void Linkedreverse(LinkedList *L){／／鏈表的就地逆置 p=Lnext； Lnext=NULL； while(p!=NULL) {r=p， p=pnext； ／／ r 指向當(dāng)前待逆置的結(jié)點(diǎn)， p 記下下 — 個(gè)結(jié)點(diǎn) rnext=L— next； Lnext=r； ／／放到表頭 } } 2．設(shè)順序表 L 是一個(gè)遞增 (允許有相同的值 )有序表，試寫一算法將 x 插入 L 中，并使 L仍為一個(gè)有序表。 答 ：分析：先找到 x 的正確插入位置，然后將大于 x 的元素從后向前依次向下移動(dòng)，最后將 x 插入到其位置上，同時(shí)順序表長(zhǎng)度增 1。 void SeqListinsert(SeqList *L， int x){／／ x 插入到遞增有序的