實用標(biāo)準(zhǔn)文案數(shù)據(jù)結(jié)構(gòu)第二章線性表習(xí)題一、單項選擇題1.線性表是 _。A一個有限序列，可以為空B一個有限序列，不可以為空C一個無限序列，可以為空D一個無限序列，不可以為空2.在一個長度為n 的順序表中刪除第i 個元素 (0<=i<=n) 時，需向前移動個元素。A n-iB n-i+lC n-i-1D i3. 線性表采用鏈?zhǔn)酱鎯r，其地址_。A必須是連續(xù)的B一定是不連續(xù)的C部分地址必須是連續(xù)的D連續(xù)與否均可以4.從一個具有n 個結(jié)點的單鏈表中查找其值等于x 的結(jié)點時，在查找成功的情況下，需平均比較_個元素結(jié)點。A n/2B nC（ n+1）/2D（ n-1 ）/25.在雙向循環(huán)鏈表中，在p 所指的結(jié)點之后插入s 指針?biāo)傅慕Y(jié)點，其操作是_。A p->next=s;s->prior=p;p->next->prior=s; s->next=p->next;B s->prior=p; s->next=p->next;p->next=s; p->next->prior=s;C p->next=s;p->next->prior=s;s->prior=p; s->next=p->next;D s->prior=p; s->next=p->next;p->next->prior=s; p->next=s;6. 設(shè)單鏈表中指針 p 指向結(jié)點 m，若要刪除 m之后的結(jié)點 （若存在），則需修改指針的操作為 _。A p->next=p->next->next;Bp=p->next; C p=p->next->next; D p->next=p;7. 在一個長度為n 的順序表中向第i 個元素 (0< i<n+l )之前插入一個新元素時，需向后移動_個元素。A n-iB n-i+lC n-i-1D i8. 在一個單鏈表中，已知q 結(jié)點是 p 結(jié)點的前趨結(jié)點，若在q 和 p 之間插入 s 結(jié)點，則須執(zhí)行A s->next=p->next; p->next=sBq->next=s; s->next=pC p->next=s->next; s->next=pDp->next=s; s->next=q9. 以下關(guān)于線性表的說法不正確的是_ 。A線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。B線性表中包含的數(shù)據(jù)元素個數(shù)不是任意的。C線性表中的每個結(jié)點都有且只有一個直接前趨和直接后繼。D存在這樣的線性表：表中各結(jié)點都沒有直接前趨和直接后繼。精彩文檔實用標(biāo)準(zhǔn)文案10. 線性表的順序存儲結(jié)構(gòu)是一種 _的存儲結(jié)構(gòu)。A隨機(jī)存取B順序存取C索引存取D散列存取11. 在順序表中，只要知道 _ ，就可在相同時間內(nèi)求出任一結(jié)點的存儲地址。A基地址B結(jié)點大小C向量大小D基地址和結(jié)點大小12. 在等概率情況下，順序表的插入操作要移動_結(jié)點。A全部B一半C三分之一D四分之一13. 在 _運算中，使用順序表比鏈表好。A插入B刪除C根據(jù)序號查找D根據(jù)元素值查找14.在一個具有n 個結(jié)點的有序單鏈表中插入一個新結(jié)點并保持該表有序的時間復(fù)雜度是_。A O(1)BO(n)C O(n2)D O(log 2n)15.設(shè)有一個棧，元素的進(jìn)棧次序為A, B, C, D, E,下列是不可能的出棧序列_ 。AA, B, C, D, EBB, C, D, E, ACE,A,B,C,D DE, D, C, B, A16.在一個具有 n 個單元的順序棧中，假定以地址低端（即0 單元）作為棧底，以top 作為棧頂指針，當(dāng)做出棧處理時， top變化為 _ 。A top不變B top=0C top-D top+17. 向一個棧頂指針為 hs 的鏈棧中插入一個 s 結(jié)點時，應(yīng)執(zhí)行 _。A hs->next=s;B s->next=hs; hs=s;C s->next=hs->next;hs->next=s;D s->next=hs; hs=hs->next;18. 在具有 n 個單元的順序存儲的循環(huán)隊列中，假定front 和 rear 分別為隊頭指針和隊尾指針，則判斷隊滿的條件為 _。A rear n= = frontB（ front+l ） n= = rearC rear n -1= = frontD (rear+l) n= = front19.在具有 n 個單元的順序存儲的循環(huán)隊列中，假定front和 rear 分別為隊頭指針和隊尾指針，則判斷隊空的條件為_。A rear n= = frontB front+l= rearC rear= = frontD (rear+l) n= front20. 在一個鏈隊列中， 假定 front 和 rear 分別為隊首和隊尾指針， 則刪除一個結(jié)點的操作為 _。A front=front->nextB rear=rear->nextC rear=front->nextD front=rear->next二、填空題1. 線性表是一種典型的 _結(jié)構(gòu)。2.在一個長度為n 的順序表的第i 個元素之前插入一個元素，需要后移_個元素。3. 順序表中邏輯上相鄰的元素的物理位置_。4.要從一個順序表刪除一個元素時，被刪除元素之后的所有元素均需_一個位置，移動過程是從 _向 _依次移動每一個元素。5.在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過_決定的；在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過 _決定的。6.在雙向鏈表中，每個結(jié)點含有兩個指針域，一個指向_ 結(jié)點，另一個指向 _結(jié)點。7.當(dāng)對一個線性表經(jīng)常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時，則采用 _存儲結(jié)構(gòu)為宜。精彩文檔實用標(biāo)準(zhǔn)文案相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時，則采用_存儲結(jié)構(gòu)為宜。8. 順序表中邏輯上相鄰的元素， 物理位置 _相鄰，單鏈表中邏輯上相鄰的元素， 物理位置 _相鄰。9. 線性表、棧和隊列都是 _結(jié)構(gòu)，可以在線性表的 _位置插入和刪除元素；對于棧只能在_ 位置插入和刪除元素；對于隊列只能在_位置插入元素和在_位置刪除元素。10.根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每個結(jié)點所含指針的個數(shù)，鏈表可分為_和 _；而根據(jù)指針的聯(lián)接方式，鏈表又可分為_和_ 。11.在單鏈表中設(shè)置頭結(jié)點的作用是_。12.對于一個具有 n 個結(jié)點的單鏈表，在已知的結(jié)點p 后插入一個新結(jié)點的時間復(fù)雜度為_，在給定值為 x 的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為_。13. 對于一個棧作進(jìn)棧運算時， 應(yīng)先判別棧是否為 _，作退棧運算時， 應(yīng)先判別棧是否為 _，當(dāng)棧中元素為m時，作進(jìn)棧運算時發(fā)生上溢，則說明棧的可用最大容量為_。為了增加內(nèi)存空間的利用率和減少發(fā)生上溢的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應(yīng)將兩棧的 _分別設(shè)在這片內(nèi)存空間的兩端，這樣只有當(dāng)_ 時才產(chǎn)生上溢。14.設(shè)有一空棧，現(xiàn)有輸入序列1， 2， 3， 4，5，經(jīng)過 push, push, pop, push, pop, push, push后，輸出序列是 _。15. 無論對于順序存儲還是鏈?zhǔn)酱鎯Φ臈：完犃衼碚f，進(jìn)行插入或刪除運算的時間復(fù)雜度均相同為_。三、簡答題1. 描述以下三個概念的區(qū)別：頭指針，頭結(jié)點，表頭結(jié)點。2. 線性表的兩種存儲結(jié)構(gòu)各有哪些優(yōu)缺點？3.對于線性表的兩種存儲結(jié)構(gòu)，如果有 n 個線性表同時并存，而且在處理過程中各表的長度會動態(tài)發(fā)生變化，線性表的總數(shù)也會自動改變，在此情況下，應(yīng)選用哪一種存儲結(jié)構(gòu)？為什么？4. 對于線性表的兩種存儲結(jié)構(gòu)，若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素，應(yīng)選用何種存儲結(jié)構(gòu)？試說明理由。5.在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針好嗎？為什么?6.假定有四個元素 A, B, C, D 依次進(jìn)棧，進(jìn)棧過程中允許出棧，試寫出所有可能的出棧序列。7. 什么是隊列的上溢現(xiàn)象？一般有幾種解決方法，試簡述之。8. 下述算法的功能是什么 ?LinkList *Demo(LinkList *L) / L是無頭結(jié)點的單鏈表LinkList *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;return (L);精彩文檔實用標(biāo)準(zhǔn)文案四、算法設(shè)計題1. 設(shè)計在無頭結(jié)點的單鏈表中刪除第i 個結(jié)點的算法。2.在單鏈表上實現(xiàn)線性表的求表長ListLength(L)運算。3. 設(shè)計將帶表頭的鏈表逆置算法。4. 假設(shè)有一個帶表頭結(jié)點的鏈表，表頭指針為head ，每個結(jié)點含三個域： data, next 和 prior 。其中data 為整型數(shù)域， next 和 prior均為指針域?，F(xiàn)在所有結(jié)點已經(jīng)由next 域連接起來，試編一個算法，利用 prior域（此域初值為NULL）把所有結(jié)點按照其值從小到大的順序鏈接起來。5.已知線性表的元素按遞增順序排列，并以帶頭結(jié)點的單鏈表作存儲結(jié)構(gòu)。試編寫一個刪除表中所有值大于 min 且小于 max 的元素（若表中存在這樣的元素）的算法。6.已知線性表的元素是無序的，且以帶頭結(jié)點的單鏈表作為存儲結(jié)構(gòu)。設(shè)計一個刪除表中所有值小于max 但大于 min 的元素的算法。7.假定用一個單循環(huán)鏈表來表示隊列（也稱為循環(huán)隊列），該隊列只設(shè)一個隊尾指針，不設(shè)隊首指針，試編寫下列各種運算的算法：（ 1）向循環(huán)鏈隊列插入一個元素值為x 的結(jié)點；（ 2）從循環(huán)鏈隊列中刪除一個結(jié)點。8.設(shè)順序表L 是一個遞減有序表，試寫一算法，將x 插入其后仍保持L 的有序性。精彩文檔實用標(biāo)準(zhǔn)文案習(xí)題 2 參考答案一、單項選擇題1A2 A3 D4C5D6A7 B8 B9 C10 A11D12B13C14 B15C 16 C17B 18 D19 C20 A二、填空題1線性2 n-i+1 3相鄰4 前移，前，后5物理存儲位置，鏈域的指針值6前趨，后繼7順序，鏈接8一定，不一定9線性，任何，棧頂，隊尾，隊頭10單鏈表，雙鏈表，非循環(huán)鏈表，循環(huán)鏈表11使空表和非空表統(tǒng)一；算法處理一致12 O(1) ， O(n)13棧滿，?？眨琺，棧底，兩個棧的棧頂在?？臻g的某一位置相遇14 2、 315O(1)三、簡答題1頭指針是指向鏈表中第一個結(jié)點（即表頭結(jié)點）的指針；在表頭結(jié)點之前附設(shè)的結(jié)點稱為頭結(jié)點；表頭結(jié)點為鏈表中存儲線性表中第一個數(shù)據(jù)元素的結(jié)點。 若鏈表中附設(shè)頭結(jié)點，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。2線性表具有兩種存儲結(jié)構(gòu)即順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)。線性表的順序存儲結(jié)構(gòu)可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時將會引起元素的大量移動，因而降低效率：而在鏈接存儲結(jié)構(gòu)中內(nèi)存采用動態(tài)分配，利用率高，但需增設(shè)指示結(jié)點之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲方便，但結(jié)點的插入、刪除操作較簡單。3應(yīng)選用鏈接存儲結(jié)構(gòu)，因為鏈?zhǔn)酱鎯Y(jié)構(gòu)是用一組任意的存儲單元依次存儲線性表中的各元素，這里存儲單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲結(jié)構(gòu)對于元素的刪除或插入運算是不需要移動元素的，只需修改指針即可，所以很容易實現(xiàn)表的容量的擴(kuò)充。4應(yīng)選用順序存儲結(jié)構(gòu)， 因為每個數(shù)據(jù)元素的存儲位置和線性表的起始位置相差一個和數(shù)據(jù)元素在線性表中的序號成正比的常數(shù)。因此，只要確定了其起始位置，線性表中的任一個數(shù)據(jù)元素都可隨機(jī)存取，因此，線性表的順序存儲結(jié)構(gòu)是一種隨機(jī)存取的存儲結(jié)構(gòu)，而鏈表則是一種順序存取的存儲結(jié)構(gòu)。5設(shè)尾指針比設(shè)頭指針好。尾指針是指向終端結(jié)點的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點和終端結(jié)點都很方便，設(shè)一帶頭結(jié)點的單循環(huán)鏈表，其尾指針為rear ，則開始結(jié)點和終端結(jié)點的位置分別是rear->next->next和 rear,查找時間都是O(1) 。若用頭指針來表示該鏈表，則查找終端結(jié)點的時間為O(n) 。6共有 14 種可能的出棧序列，即為：ABCD, ABDC， ACBD, ACDB， BACD，ADCB， BADC， BCAD, BCDA，BDCA,CBAD, CBDA， CDBA, DCBA7在隊列的順序存儲結(jié)構(gòu)中，設(shè)隊頭指針為front，隊尾指針為rear ，隊列的容量（即存儲的空間大小）為 maxnum。當(dāng)有元素要加入隊列（即入隊）時，若rear=maxnum，則會發(fā)生隊列的上溢現(xiàn)象，此時就不能將該元素加入隊列。對于隊列，還有一種“假溢出”現(xiàn)象，隊列中尚余有足夠的空間，精彩文檔實用標(biāo)準(zhǔn)文案但元素卻不能入隊， 一般是由于隊列的存儲結(jié)構(gòu)或操作方式的選擇不當(dāng)所致，可以用循環(huán)隊列解決。一般地，要解決隊列的上溢現(xiàn)象可有以下幾種方法：（ 1）可建立一個足夠大的存儲空間以避免溢出，但這樣做往往會造成空間使用率低，浪費存儲空間。（ 2）要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決：第一種：采用移動元素的方法。每當(dāng)有一個新元素入隊，就將隊列中已有的元素向隊頭移動一個位置，假定空余空間足夠。第二種：每當(dāng)刪去一個隊頭元素，則可依次移動隊列中的元素總是使 front 指針指向隊列中的第一個位置。第三種：采用循環(huán)隊列方式。將隊頭、隊尾看作是一個首尾相接的循環(huán)隊列，即用循環(huán)數(shù)組實現(xiàn)，此時隊首仍在隊尾之前，作插入和刪除運算時仍遵循“先進(jìn)先出”的原則。8該算法的功能是：將開始結(jié)點摘下鏈接到終端結(jié)點之后成為新的終端結(jié)點，而原來的第二個結(jié)點成為新的開始結(jié)點，返回新鏈表的頭指針。四、算法設(shè)計題1 算法思想為：（ 1）應(yīng)判斷刪除位置的合法性，當(dāng)i<0 或 i>n-1 時，不允許進(jìn)行刪除操作；（ 2）當(dāng) i=0 時，刪除第一個結(jié)點：（ 3）當(dāng) <i<n 時，允許進(jìn)行刪除操作，但在查找被刪除結(jié)點時，須用指針記住該結(jié)點的前趨結(jié)點。算法描述如下：delete(LinkList *q,int i) / 在無頭結(jié)點的單鏈表中刪除第i 個結(jié)點LinkList *p,*s; int j;if(i<0)printf("Can't delete");else if(i= =0) s=q;q=q->next;free(s);else j=0; s=q;while(j<i) && (s! = NULL) p=s;s=s->next;j+;if (s= =NULL)printf("Cant't delete");elsep->next=s->next;free(s);2由于在單鏈表中只給出一個頭指針，所以只能用遍歷的方法來數(shù)單鏈表中的結(jié)點個數(shù)了。算法描述如下：int ListLength ( LinkList *L ) /求帶頭結(jié)點的單鏈表的表長精彩文檔實用標(biāo)準(zhǔn)文案int len=0;ListList *p;p=L;while ( p->next!=NULL ) p=p->next;len+;return (len);3設(shè)單循環(huán)鏈表的頭指針為head ，類型為LinkList。逆置時需將每一個結(jié)點的指針域作以修改，使其原前趨結(jié)點成為后繼。如要更改q 結(jié)點的指針域時，設(shè)s 指向其原前趨結(jié)點，p 指向其原后繼結(jié)點，則只需進(jìn)行q->next=s;操作即可，算法描述如下：void invert(LinkList *head) / 逆置 head 指針?biāo)赶虻膯窝h(huán)鏈表 linklist *p, *q, *s;q=head;p=head->next;while (p!=head) /當(dāng)表不為空時，逐個結(jié)點逆置 s=q;q=p;p=p->next;q->next=s;p->next=q;4定義類型LinkList如下：typedef struct node int data;struct node *next,*prior;LinkList;此題可采用插入排序的方法，設(shè)p 指向待插入的結(jié)點，用q 搜索已由prior域鏈接的有序表找到合適位置將p 結(jié)點鏈入。算法描述如下：insert (LinkList *head) LinkList *p,*s,*q;p=head->next; /p 指向待插入的結(jié)點，初始時指向第一個結(jié)點 while(p!=NULL) s=head; / s指向 q 結(jié)點的前趨結(jié)點q=head->prior; /q指向由 prior 域構(gòu)成的鏈表中待比較的結(jié)點while(q!=NULL)&& (p->data>q->data) /查找插入結(jié)點p 的合適插入位置 s=q;q=q->prior;s->prior=p;p->prior=q; /結(jié)點 p 插入到結(jié)點s 和結(jié)點 q 之間p=p->next;精彩文檔實用標(biāo)準(zhǔn)文案5算法描述如下：delete(LinkList *head, int max, int min) linklist *p, *q;if (head!=NULL) q=head;p=head->next;while(p!=NULL) && (p->data<=min) q=p; p=p->next;while(p!=NULL) && (p->data<max)p=p->next;q->next=p;6算法描述如下：delete(LinkList *head, int max, int min) LinkList *p,*q;q=head;p=head->next;while (p!=NULL)if(p->data<=min) | (p->data>=max) q=p;p=p->next;else q->next=p->next; free(p); p=q->next;7本題是對一個循環(huán)鏈隊列做插入和刪除運算，假設(shè)不需要保留被刪結(jié)點的值和不需要回收結(jié)點，算法描述如下：（ 1）插入（即入隊）算法：insert(LinkList *rear, elemtype x) / 設(shè)循環(huán)鏈隊列的隊尾指針為rear,x 為待插入的元素LinkList *p;p=(LinkList *)malloc(sizeof(LinkList);if(rear= =NULL) /如為空隊，建立循環(huán)鏈隊列的第一個結(jié)點 rear=p;rear->next=p;/鏈接成循環(huán)鏈表精彩文檔實用標(biāo)準(zhǔn)文案else /否則在隊尾插入p 結(jié)點 p->next=rear->next; rear->next=p;rear=p;（ 2）刪除（即出隊）算法：delete(LinkList *rear) /設(shè)循環(huán)鏈隊列的隊尾指針為rearif (rear= =NULL) /空隊printf("underflown");if(rear->next= =rear) /隊中只有一個結(jié)點rear=NULL;elserear->next=rear->next->next; /rear->next指向的結(jié)點為循環(huán)鏈隊列的隊頭結(jié)點8只要從終端結(jié)點開始往前找到第一個比x 大 ( 或相等 ) 的結(jié)點數(shù)據(jù)，在這個位置插入就可以了。算法描述如下：int InsertDecreaseList( SqList *L, elemtype x ) int i;if ( (*L).len>= maxlen) printf( “overflow"); return(0);for ( i=(*L).len ; i>0 && (*L).elem i-1 < x ; i-)(*L).elem i =(*L).elem i-1 ;/比較并移動元素(*L).elem i =x;(*L).len+;return(1);精彩文檔