數(shù)據(jù)結(jié)構(gòu)習(xí)題及答案線性表第1次更新2013

1、第2章線性表選擇題1 .表長(zhǎng)為N的順序表，當(dāng)在任何位置上插入或刪除一個(gè)元素的概率相等時(shí)，插入一個(gè)元素所需移動(dòng)元素的平均次數(shù)為（），刪除一個(gè)元素需要移動(dòng)的元素個(gè)數(shù)為（）?！?,】A.（N-1）/2B.NC.N+1D.N-1E.N/2F.（N+1）2G.（N-2）/22 .線性表是具有N個(gè)（）的有限序列?！?】A、表元素B、字符C、數(shù)據(jù)元素D、數(shù)據(jù)項(xiàng)E、信息3 .“線性表的邏輯順序和物理順序總是一致的。”這個(gè)結(jié)論是（）?！?】A、正確的B、錯(cuò)誤的C、不一定，與具體結(jié)構(gòu)有關(guān)。4 .線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（A、必須是連續(xù)的B、部分地址必須是連續(xù)的G一定是不連續(xù)的D、連續(xù)

2、或不連續(xù)都可以。5 .帶頭結(jié)點(diǎn)的單鏈表為空的判定條件是（）。【*】A、head=NULLB、head->next=NULLChead->next=headD、head!=NULL6 .不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是（）。【*】A、head=NULLB、head->next=NULLChead->next=headD、head!=NULL7 .非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)P滿足（）。（注:帶頭結(jié)點(diǎn)）【*】A、P->NEXT=NULLB、p=NULLCp->next=headD、p=head8 .在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍

3、然有序的時(shí)間復(fù)雜度是（A、O（1）B、O（n）C、O（n2）D、O（nlog2n）9 .在一個(gè)單鏈表中，若刪除P所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行（【*,A、p->next=p->next->nextB、p=p->next;p->next=p->next->nextCp->next=p->next;D、p=p->next->next;10 .在一個(gè)單鏈表中，若在P所指結(jié)點(diǎn)之后插入S所指結(jié)點(diǎn)，則執(zhí)行（A、s->next=p;p->next=s;B、s->next=p->next;p->next=s;Cs-&g

4、t;next=p->next;p=s;D、p->next=s;s->next=p;11 .在一個(gè)單鏈表中，已知q是p的前趨結(jié)點(diǎn)，若q和p之間插入結(jié)點(diǎn)s,則執(zhí)行（）?！?】A、s->next=p->next;p->next=s;B、p->next=s->next;s->next=p;Cq->next=s;s->next=p;D、p->next=s;s->next=q;12 .假設(shè)雙鏈表結(jié)點(diǎn)的類型如下：【*,】typedefstructlinknodeintdata;/數(shù)據(jù)域structlinknode*llink;/指

5、向前趨結(jié)點(diǎn)的指針域structlinknode*rlink;/指向后繼結(jié)點(diǎn)的指針域bnode;現(xiàn)將一個(gè)q所指新結(jié)點(diǎn)作為非空雙向鏈表中的p所指結(jié)點(diǎn)的前趨結(jié)點(diǎn)插入到該雙鏈表中，能正確完成此要求的語句段是（）。A、q->rlink=p;q->llink=p->llink;p->llink=q;p->llink->rlink=q;B、p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=p->llinkGq->llink=p->rlink;q->rlink=p;p-&g

6、t;llink->rlink=q;p->llink=q;1/9北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)學(xué)院“數(shù)據(jù)結(jié)構(gòu)”課程組編制2011-3-1D、以上都不對(duì)13 .如上題結(jié)點(diǎn)結(jié)構(gòu)，如在此非空循環(huán)雙向鏈表的結(jié)點(diǎn)p之后插入結(jié)點(diǎn)s的操作序列是（）?！?】A、p->rlink=s;s->llink=p;p->rlink->llink=s;s->rlink=p->rlink;B、p->rlink=s;p->rlink->llink=s;s->llink=p;s->rlink=p->rlink;Gs->llink=p;s->

7、;rlink=p->rlink;p->rlink=s;p->rlink->llink=s;D、s->llink=p;s->rlink=p->rlink;p->rlink->llink=s;p->rlink=s;14 .在一個(gè)長(zhǎng)度為n的單鏈表上，設(shè)有頭和尾兩個(gè)指針，執(zhí)行（）操作與鏈表的長(zhǎng)度有關(guān)?！?,】A、刪除單鏈表中的第一個(gè)元素B、刪除單鏈表中最后一個(gè)元素G在單鏈表第一個(gè)元素前插入一個(gè)新元素D、在單鏈表最后一個(gè)元素后插入一個(gè)新元素15 .線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)代表一個(gè)（）【*】A、數(shù)據(jù)元素B、數(shù)據(jù)項(xiàng)C、數(shù)據(jù)D、數(shù)據(jù)結(jié)構(gòu)16 .非空線性表

8、L=（a1,a2,ai,an）,下列說法正確的是（）【*】A、每個(gè)元素都有一個(gè)直接前驅(qū)和直接后繼B、線性表中至少要有一個(gè)元素G表中諸元素的排列順序必須是由小到大或由大到小的D、除第一個(gè)元素和最后一個(gè)元素外其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼17 .順序表是線性表的（）【*,】A、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B、順序存儲(chǔ)結(jié)構(gòu)G索引存儲(chǔ)結(jié)構(gòu)D、散列存儲(chǔ)結(jié)構(gòu)18 .對(duì)于順序表，以下說法錯(cuò)誤的是（）【*,A、順序表是用一維數(shù)組實(shí)現(xiàn)的線性表，數(shù)組的下標(biāo)可以看成是元素的絕對(duì)地址B、順序表的所有存儲(chǔ)結(jié)點(diǎn)按相應(yīng)數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列G順序表的特點(diǎn)是：邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中仍相鄰D、順序表

9、的特點(diǎn)是：邏輯上相鄰的元素，存儲(chǔ)在物理位置也相鄰的單元中19 .對(duì)順序表上的插入、刪除算法的時(shí)間復(fù)雜性分析來說，通常以（）為標(biāo)準(zhǔn)操作?！?】A、插入操作B、結(jié)點(diǎn)移動(dòng)C、算術(shù)表達(dá)式D、刪除操作20 .對(duì)于順序表的優(yōu)缺點(diǎn)，以下說法錯(cuò)誤的是（）【*】A、無需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間B、可以方便地隨機(jī)存取表中的任一結(jié)點(diǎn)G插入和刪除運(yùn)算較方便D、由于順序表要求占用連續(xù)的空（0,存儲(chǔ)分配只能預(yù)先進(jìn)行（靜態(tài)分配）21 .若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素，則采用（）存儲(chǔ)方式最節(jié)省時(shí)間?！?】A、順序表B、單鏈表C、雙鏈表D、單循環(huán)鏈表22 .循環(huán)鏈表主要優(yōu)點(diǎn)是（

10、）【*】A、不再需要頭指針了B、已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到它的直接前趨G在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好地保證鏈表不斷開D、從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表23 .在線性表的下列存儲(chǔ)結(jié)構(gòu)中，讀取元素花費(fèi)時(shí)間最少的是（）【*,A、單鏈表B、雙鏈表C、循環(huán)鏈表D、順序表二、填空題1 .在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)()前趨結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有()個(gè)前趨結(jié)點(diǎn)。【*】2 .在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)()元素，具體移動(dòng)的元素個(gè)數(shù)與()有關(guān)?！?】3 .已知L是無表頭結(jié)點(diǎn)的單鏈表，試從下列提供的答案中選擇合適的語句序列，分別實(shí)現(xiàn)：【*,】(1)表首插入S結(jié)點(diǎn)的語句序列是()。(2

11、)表尾插入S結(jié)點(diǎn)的語句序列是()。A、P->next=S;B、P=L;C、L=S;D、P->next=S->next;E、S->next=P->next;F、S->next=L;G、S->next=NULL;H、while(P->next!=Q)p=p->next;I、while(P->next!=NULL)P=P->next;4 .已知L是帶表頭結(jié)點(diǎn)的非空單鏈表，試從下列提供的答案中選擇合適的語句序列。*,(1)刪除首元結(jié)點(diǎn)的語句序列是()，(2)刪除尾元結(jié)點(diǎn)的語句序列是()A、P=P->next;B、P->nex

12、t=P->next->next;C、while(P!=NULL)P=P->next;D、while(Q->next!=NULL)P=Q;Q=Q->next;E、while(P->next!=Q)P=P->next;F、Q=P;G、Q=P->next;H、P=L;I、L=L->next;J、free(Q);5 .已知L是帶表頭結(jié)點(diǎn)的非空單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語句序列。*(1)刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是()，(2)刪J除P結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)的語句序列是()A、P->next

13、=P->next->next;B、P=P->Pnext->next;C、while(P->next!=Q)P=P->next;D、while(P->next->next!=Q)P=P->next;E、Q=P;F、Q=P->next;G、P=L;H、L=L->next;I、free(Q);6 .已知結(jié)點(diǎn)編號(hào)，在各結(jié)點(diǎn)查找概率相等的情況下，從n個(gè)結(jié)點(diǎn)的單鏈表中查找一個(gè)結(jié)點(diǎn)，平均要訪問()個(gè)結(jié)點(diǎn)，從n個(gè)結(jié)點(diǎn)的雙鏈表中查找一個(gè)結(jié)點(diǎn)，平均要訪問()個(gè)結(jié)點(diǎn)?！?,?7 .對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)

14、雜度是（）;在值域?yàn)榻o定值的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是（）。【*,8 .單鏈表是（）的鏈接存儲(chǔ)表示。【*】9 .單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是（）?！?】10 .在單鏈表中，除首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由（）指示?！?】11 .在非空雙向循環(huán)鏈表中，在結(jié)點(diǎn)q的前面插入結(jié)點(diǎn)p的過程如下：【*】p->prior=q->prior;q->prior->next=p;p->next=q;（）；12 .在雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向（），另一個(gè)指向（）。【*】13 .順序表中邏輯上相鄰的元素的物理位置（）相鄰。單鏈表中邏輯上相鄰的元素的物理位置（）相鄰

15、。【*】14 .為了便于討論，有時(shí)將含n（n>0）個(gè)結(jié)點(diǎn)的線性結(jié)構(gòu)表示成（a1,a2,an）,其中每個(gè)ai代表一個(gè)。a1稱為結(jié)點(diǎn),an稱為結(jié)點(diǎn)，i稱為ai在線性表中的。對(duì)任意一對(duì)相鄰結(jié)點(diǎn)ai、ai+1（1&i<n）,ai稱為ai+1的直接,ai+1稱為ai的直接?！?15 .線性結(jié)構(gòu)的基本特征是：若至少含有一個(gè)結(jié)點(diǎn)，則除起始結(jié)點(diǎn)沒有直接外，其他結(jié)點(diǎn)有且僅有一個(gè)直接;除終端結(jié)點(diǎn)沒有直接外，其它結(jié)點(diǎn)有且僅有一個(gè)直接.【*】16 .所有結(jié)點(diǎn)按R1的鄰接關(guān)系構(gòu)成的整體就是結(jié)構(gòu)?！?】17 .線性表的邏輯結(jié)構(gòu)是結(jié)構(gòu)。其所含結(jié)點(diǎn)的個(gè)數(shù)稱為線性表的。【*】18 .在單鏈表中，指針p所指結(jié)

16、點(diǎn)為最后一個(gè)結(jié)點(diǎn)的條件是?！?】三、判斷題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)進(jìn)行查找任何一個(gè)元素。【*】7 .線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。【*】8 .在線性表的順序存儲(chǔ)結(jié)構(gòu)中，

17、插入和刪除元素時(shí)，移動(dòng)元素的個(gè)數(shù)與該元素的位置有關(guān)?！?】9 .在單鏈表中，要取得某個(gè)元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)?！?】10 .順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。【*,】四、簡(jiǎn)答題1. 若較頻繁地對(duì)一個(gè)線性表進(jìn)行插入和刪除操作，該線性表宜采用哪種存儲(chǔ)結(jié)構(gòu)？為什么？【*】2. 描述概念：頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)的區(qū)別？【*,】3. 設(shè)A是一個(gè)線性表（a1a2,an）,采用順序存儲(chǔ)結(jié)構(gòu)，則在等概率的前提下，平均每插入一個(gè)元素需要移動(dòng)的元素個(gè)數(shù)為多少？若元素插在ai與ai+1之間（0<=I<=n-1）的概率為2（n-i）/（n（n+1）,則平均每插入

18、一個(gè)元素所要移動(dòng)的元素個(gè)數(shù)又是多少？【*4. 為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好？*,5. 雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某個(gè)結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)*p從相應(yīng)的鏈表中刪除？若可以，其時(shí)間復(fù)雜度各為多少？【*】6. 下列算法的功能是什么？【*,】LinkedListtest1(LinkedListL)(/L是無頭結(jié)點(diǎn)的單鏈表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;ret

19、urnL;7. 如果有n個(gè)線性表同時(shí)共存，并且在處理過程中各表的長(zhǎng)度會(huì)發(fā)生動(dòng)態(tài)變化，線性表的總長(zhǎng)度也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選擇哪一種存儲(chǔ)結(jié)構(gòu)。為什么？【*】8. 若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入刪除操作，但要求以最快的方式存取線性表的元素，應(yīng)該用哪種存儲(chǔ)結(jié)構(gòu)。為什么？【*】4_109. 設(shè)有多項(xiàng)式a(x)=9+8x+9x+5xb(x)=-2x+22x7-5x10(1)用單鏈表給出a(x)、b(x)的存儲(chǔ)表示；(2)設(shè)c(x)=a(x)+b(x),求得c(x)并用單鏈表給出其存儲(chǔ)表示?！?,五、設(shè)計(jì)題1. 編寫一個(gè)函數(shù)將一個(gè)順序表A(有多個(gè)元素且任何元素不為0)分拆成兩個(gè)順序表，使A

20、中大于0的元素存放在B中，小于0的元素存放在C中?！?】2. 設(shè)順序表L中的數(shù)據(jù)元素遞增有序。試寫一算法，將e插入到順序表的適當(dāng)位置，插入后保持該表的有序性?！?】3. A、B為元素遞增有序排列的單鏈表(同一表中可能有相同元素)，編寫算法另建一單鏈表C,保存兩個(gè)表的公共元素，要求C的元素值各不相同且遞增有序?！?】4、設(shè)有一個(gè)由正整數(shù)組成的無序單鏈表，編寫算法實(shí)現(xiàn)下列功能：【*】(1)找出最小值結(jié)點(diǎn)，且顯示該數(shù)值。(2)若該數(shù)值為奇數(shù)，則將其與直接后繼結(jié)點(diǎn)的數(shù)值交換。(3)若為偶數(shù)，則將其直接后繼結(jié)點(diǎn)刪除。六、編程附加題1. 試分別用順序表和單鏈表作為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)將線性表(a0,a1,a2,

21、.an-1)就地逆置的操作，所謂“就地”指輔助空間為O(1)。【*,2. 設(shè)單鏈表L是一個(gè)非遞減有序表，試寫一個(gè)算法將x插入其中后仍保持L的有序性。【*】3. 設(shè)A、B是兩個(gè)線性表，其表中元素遞增有序，長(zhǎng)度分別為m和no試寫一算法分別以順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)將A和B歸并成一個(gè)仍按元素值遞增有序的線性表C,請(qǐng)分析算法的時(shí)間復(fù)雜度。【*,4. 單鏈表L是一個(gè)遞減有序表，試寫一高效算法，刪除表中值大于mink且小于maxk的結(jié)點(diǎn)(若表中有這樣的結(jié)點(diǎn))，同時(shí)釋放被刪結(jié)點(diǎn)空間，這里mink和maxk是兩個(gè)給定的參數(shù)，它們可以和表中元素相同，也可以不同?！?】5. 假設(shè)以兩個(gè)元素依值遞增有序排列的線性表A,B

22、分別表示兩個(gè)集合，先要求另辟空間構(gòu)造一個(gè)線性表C,其元素為兩集合的交集，且表C中的元素也依值遞增有序排列。是對(duì)順序表編寫求C的算法?！?】6. 假設(shè)在長(zhǎng)度大于1的單循環(huán)鏈表中，既無頭結(jié)點(diǎn)也無頭指針。S為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法刪除結(jié)點(diǎn)*s的直接前驅(qū)結(jié)點(diǎn)?！?】7. 計(jì)算帶頭結(jié)點(diǎn)的單循環(huán)鏈表的結(jié)點(diǎn)個(gè)數(shù)?！?】8. 給定一個(gè)不帶頭結(jié)點(diǎn)的單鏈表，編寫計(jì)算此鏈表長(zhǎng)度的算法?！?】第2章線性表參考答案七、選擇題1、E,A2、C3、B4、D5、B6、A7、C8、B9、A10、B11、C12、D龔注:(2012-4-25)。修改4個(gè)指針,按順序(1)->(2)->(3)->(4

23、)o或(1),(2),(3)順序任意，(4)最后。13、D14、BA.刪除第一個(gè)元素：只需移動(dòng)頭指針-與長(zhǎng)度n無關(guān)B.刪除最后一個(gè)元素：尾指針需移動(dòng)上一個(gè)結(jié)點(diǎn)，需搜索整個(gè)鏈表。-與長(zhǎng)度n有關(guān)C.在頭插入一個(gè)元素：新結(jié)點(diǎn)的next=頭指針；頭指針賦新結(jié)點(diǎn)指針。-與長(zhǎng)度n無關(guān)D.在尾部插入一個(gè)元素：尾指針的next=新結(jié)點(diǎn)；尾指針=新結(jié)點(diǎn)指針-與長(zhǎng)度n無關(guān)15、A16、D17、B18、A19、B20、C21、A22、D23、D八、填空題1、沒有；12、表中一半；該元素的位置3、(1)FC(2)BIAG4、(1)HGBJ(2)HFDBJ5、(1)FAI(2)EGDFAI6、n/2,n/4(此題有誤！

24、另作說明)7、O(1)O(n)8、線性表9、插入和刪除首元素時(shí)不必進(jìn)行特殊處理10、其直接前趨結(jié)點(diǎn)的鏈域11、q->prior=p;12、前趨結(jié)點(diǎn)，后繼結(jié)點(diǎn)13、必定，不一定14、結(jié)點(diǎn)、第一個(gè)、最后一個(gè)、位置、前驅(qū)、后繼15、前驅(qū)、前驅(qū)、后繼、后繼16、線性17、線性、長(zhǎng)度18、p-next=NULL;九、判斷題1V2.X3/4.X5/6V7.X879.X10X十、簡(jiǎn)答題1、宜采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因?yàn)樗咕€性表的插入和刪除操作的時(shí)間復(fù)雜度為O(1),而順序存儲(chǔ)結(jié)構(gòu)的為O(n)o2、首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。為了操作方便，通常在鏈表的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭

25、結(jié)點(diǎn),該結(jié)點(diǎn)的數(shù)據(jù)域中不存線性表的數(shù)據(jù)元素，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)空表非空表的情況以及對(duì)首元結(jié)點(diǎn)進(jìn)行統(tǒng)一的處理。頭指針是指向鏈表第一個(gè)結(jié)點(diǎn)(頭結(jié)點(diǎn)或首元結(jié)點(diǎn))的指針。若鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。這三個(gè)概念對(duì)單鏈表、雙向鏈表和循環(huán)鏈表均適用。4、解答：?jiǎn)窝h(huán)鏈表中無論設(shè)置尾指針還是頭指針都可以任一結(jié)點(diǎn)從遍歷表中其它結(jié)點(diǎn)，但設(shè)置尾指針時(shí)，若在表尾進(jìn)行插入或刪除操作時(shí)可在O(1)時(shí)間內(nèi)完成，同樣在表頭進(jìn)行才f入或刪除操作時(shí)也可在O(1)時(shí)間內(nèi)完成。但設(shè)置的是頭指針，表尾進(jìn)行插入或刪除操作，需要遍歷整個(gè)鏈表，時(shí)間復(fù)雜度為O(

26、n)。5、解答：能刪除。雙鏈表上刪除p所指向的結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1),單循環(huán)鏈表上刪除p所指向的結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n)。6、解答：如果長(zhǎng)度大于1,則將首元結(jié)點(diǎn)刪除并插入到表尾。7、解答：應(yīng)選用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。因?yàn)轫樞虮硎庆o態(tài)存儲(chǔ)結(jié)構(gòu)，只能預(yù)先分配存儲(chǔ)單元，不能隨著線性表長(zhǎng)度的改變而變化。而鏈表則可根據(jù)需要?jiǎng)討B(tài)的申請(qǐng)空間，因此適用于動(dòng)態(tài)變化表長(zhǎng)的線性表。8、解答：應(yīng)該用順序存儲(chǔ)結(jié)構(gòu)。因?yàn)轫樞虼鎯?chǔ)結(jié)構(gòu)存取元素操作的時(shí)間復(fù)雜度為O(1)。9、解答：用單鏈表表示多項(xiàng)式，除指針域外需設(shè)置兩個(gè)數(shù)據(jù)域，一個(gè)用來存儲(chǔ)系數(shù)，一個(gè)用來存儲(chǔ)指數(shù)。H一、設(shè)計(jì)題1、voidsplit(SqListA,SqList

27、&B,SqList&C)采用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)intI;B.length=C.length=0;for(I=0;I<AS.length;I+)if(A.elemi>0)B.elemB.length=A.elemi;B.length+;elseC.elemC.length=A.elemi;C.length+;)2、statusListInsert(SqList&L,ElemTypee)ElemType*p,*q,*newbase;intj;if(L.length>=L.listsize)newbase=(ElemType)realloc(L.elem,(L.listsize+LISTINCRMENT)*sizeof(ElemType);if(!newbase