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

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

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

3、然有序的時間復(fù)雜度是（A、O（1）B、O（n）C、O（n2）D、O（nlog2n）9 .在一個單鏈表中，若刪除P所指結(jié)點的后繼結(jié)點，則執(zhí)行（【*,A、p->next=p->next->nextB、p=p->next;p->next=p->next->nextCp->next=p->next;D、p=p->next->next;10 .在一個單鏈表中，若在P所指結(jié)點之后插入S所指結(jié)點，則執(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 .在一個單鏈表中，已知q是p的前趨結(jié)點，若q和p之間插入結(jié)點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é)點的類型如下：【*,】typedefstructlinknodeintdata;/數(shù)據(jù)域structlinknode*llink;/指

5、向前趨結(jié)點的指針域structlinknode*rlink;/指向后繼結(jié)點的指針域bnode;現(xiàn)將一個q所指新結(jié)點作為非空雙向鏈表中的p所指結(jié)點的前趨結(jié)點插入到該雙鏈表中，能正確完成此要求的語句段是（）。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é)院計算機學(xué)院“數(shù)據(jù)結(jié)構(gòu)”課程組編制2011-3-1D、以上都不對13 .如上題結(jié)點結(jié)構(gòu)，如在此非空循環(huán)雙向鏈表的結(jié)點p之后插入結(jié)點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 .在一個長度為n的單鏈表上，設(shè)有頭和尾兩個指針，執(zhí)行（）操作與鏈表的長度有關(guān)?！?,】A、刪除單鏈表中的第一個元素B、刪除單鏈表中最后一個元素G在單鏈表第一個元素前插入一個新元素D、在單鏈表最后一個元素后插入一個新元素15 .線性結(jié)構(gòu)中的一個結(jié)點代表一個（）【*】A、數(shù)據(jù)元素B、數(shù)據(jù)項C、數(shù)據(jù)D、數(shù)據(jù)結(jié)構(gòu)16 .非空線性表

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

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

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

11、)表尾插入S結(jié)點的語句序列是()。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é)點的非空單鏈表，試從下列提供的答案中選擇合適的語句序列。*,(1)刪除首元結(jié)點的語句序列是()，(2)刪除尾元結(jié)點的語句序列是()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é)點的非空單鏈表，且P結(jié)點既不是首元結(jié)點，也不是尾元結(jié)點，試從下列提供的答案中選擇合適的語句序列。*(1)刪除P結(jié)點的直接后繼結(jié)點的語句序列是()，(2)刪J除P結(jié)點的直接前趨結(jié)點的語句序列是()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é)點編號，在各結(jié)點查找概率相等的情況下，從n個結(jié)點的單鏈表中查找一個結(jié)點，平均要訪問()個結(jié)點，從n個結(jié)點的雙鏈表中查找一個結(jié)點，平均要訪問()個結(jié)點?！?,?7 .對于一個具有n個結(jié)點的單鏈表，在已知p所指結(jié)點后插入一個新結(jié)點的時間復(fù)

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

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

16、點為最后一個結(jié)點的條件是?！?】三、判斷題1 .順序存儲的線性表可以隨機存取?！?】2 .順序存儲的線性表的插入和刪除操作不需要付出很大的代價，因為平均每次操作只有近一半的元素需要移動?！?】3 .線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此是屬于同一數(shù)據(jù)對象?！?】4 .在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上不一定相鄰?！?】5 .在線性表的鏈式存儲結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰?！?】6 .在單鏈表中，可以從頭結(jié)點進行查找任何一個元素?！?】7 .線性表的鏈式存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)?！?】8 .在線性表的順序存儲結(jié)構(gòu)中，

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

18、一個元素所要移動的元素個數(shù)又是多少？【*4. 為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好？*,5. 雙鏈表和單循環(huán)鏈表中，若僅知道指針p指向某個結(jié)點，不知道頭指針，能否將結(jié)點*p從相應(yīng)的鏈表中刪除？若可以，其時間復(fù)雜度各為多少？【*】6. 下列算法的功能是什么？【*,】LinkedListtest1(LinkedListL)(/L是無頭結(jié)點的單鏈表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個線性表同時共存，并且在處理過程中各表的長度會發(fā)生動態(tài)變化，線性表的總長度也會自動地改變。在此情況下，應(yīng)選擇哪一種存儲結(jié)構(gòu)。為什么？【*】8. 若線性表的總數(shù)基本穩(wěn)定，且很少進行插入刪除操作，但要求以最快的方式存取線性表的元素，應(yīng)該用哪種存儲結(jié)構(gòu)。為什么？【*】4_109. 設(shè)有多項式a(x)=9+8x+9x+5xb(x)=-2x+22x7-5x10(1)用單鏈表給出a(x)、b(x)的存儲表示；(2)設(shè)c(x)=a(x)+b(x),求得c(x)并用單鏈表給出其存儲表示。【*,五、設(shè)計題1. 編寫一個函數(shù)將一個順序表A(有多個元素且任何元素不為0)分拆成兩個順序表，使A

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

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

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

23、)o或(1),(2),(3)順序任意，(4)最后。13、D14、BA.刪除第一個元素：只需移動頭指針-與長度n無關(guān)B.刪除最后一個元素：尾指針需移動上一個結(jié)點，需搜索整個鏈表。-與長度n有關(guān)C.在頭插入一個元素：新結(jié)點的next=頭指針；頭指針賦新結(jié)點指針。-與長度n無關(guān)D.在尾部插入一個元素：尾指針的next=新結(jié)點；尾指針=新結(jié)點指針-與長度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、插入和刪除首元素時不必進行特殊處理10、其直接前趨結(jié)點的鏈域11、q->prior=p;12、前趨結(jié)點，后繼結(jié)點13、必定，不一定14、結(jié)點、第一個、最后一個、位置、前驅(qū)、后繼15、前驅(qū)、前驅(qū)、后繼、后繼16、線性17、線性、長度18、p-next=NULL;九、判斷題1V2.X3/4.X5/6V7.X879.X10X十、簡答題1、宜采用鏈式存儲結(jié)構(gòu)，因為它使線性表的插入和刪除操作的時間復(fù)雜度為O(1),而順序存儲結(jié)構(gòu)的為O(n)o2、首元結(jié)點是指鏈表中存儲線性表中第一個數(shù)據(jù)元素的結(jié)點。為了操作方便，通常在鏈表的首元結(jié)點之前附設(shè)一個結(jié)點，稱為頭

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

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

27、&B,SqList&C)采用順序存儲結(jié)構(gòu)實現(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