《數(shù)據(jù)結(jié)構(gòu)》-第二章-線性表習(xí)題

《數(shù)據(jù)結(jié)構(gòu)》第二章線性表習(xí)題一、單項(xiàng)選擇題1.線性表是________。A．一個(gè)有限序列，可以為空 B．一個(gè)有限序列，不可以為空C．一個(gè)無限序列，可以為空 D．一個(gè)無限序列，不可以為空2.在一個(gè)長度為n的順序表中刪除第i個(gè)元素(0<=i<=n)時(shí)，需向前移動個(gè)元素。A．n-i B．n-i+l C．n-i-1 D．i3.線性表采用鏈?zhǔn)酱鎯r(shí)，其地址________。A．必須是連續(xù)的 B．一定是不連續(xù)的C．部分地址必須是連續(xù)的 D．連續(xù)與否均可以4.從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較________個(gè)元素結(jié)點(diǎn)。A．n/2 B．n C．（n+1）/2 D．（n-1）/25.在雙向循環(huán)鏈表中，在p所指的結(jié)點(diǎn)之后插入s指針?biāo)傅慕Y(jié)點(diǎn)，其操作是____。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é)點(diǎn)m，若要?jiǎng)h除m之后的結(jié)點(diǎn)（若存在），則需修改指針的操作為________。A．p->next=p->next->next;B．p=p->next;C．p=p->next->next;D．p->next=p;7.在一個(gè)長度為n的順序表中向第i個(gè)元素(0<i<n+l)之前插入一個(gè)新元素時(shí)，需向后移動______個(gè)元素。A．n-i B．n-i+l C．n-i-1 D．i8.在一個(gè)單鏈表中，已知q結(jié)點(diǎn)是p結(jié)點(diǎn)的前趨結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則須執(zhí)行A．s->next=p->next;p->next=sB．q->next=s;s->next=pC．p->next=s->next;s->next=pD．p->next=s;s->next=q9.以下關(guān)于線性表的說法不正確的是______。

A．線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。B．線性表中包含的數(shù)據(jù)元素個(gè)數(shù)不是任意的。C．線性表中的每個(gè)結(jié)點(diǎn)都有且只有一個(gè)直接前趨和直接后繼。D．存在這樣的線性表：表中各結(jié)點(diǎn)都沒有直接前趨和直接后繼。10.線性表的順序存儲結(jié)構(gòu)是一種_______的存儲結(jié)構(gòu)。

A．隨機(jī)存取 B．順序存取 C．索引存取 D．散列存取11.在順序表中，只要知道_______，就可在相同時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲地址。A．基地址B．結(jié)點(diǎn)大小C．向量大小D．基地址和結(jié)點(diǎn)大小12.在等概率情況下，順序表的插入操作要移動______結(jié)點(diǎn)。

A．全部B．一半C．三分之一D．四分之一13.在______運(yùn)算中，使用順序表比鏈表好。

A．插入B．刪除C．根據(jù)序號查找D．根據(jù)元素值查找14.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并保持該表有序的時(shí)間復(fù)雜度是_______。A．O(1)B．O(n)C．O(n2)D．O(log2n)15.設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳,B,C,D,E,下列是不可能的出棧序列__________。A．A,B,C,D,EB．B,C,D,E,AC．E,A,B,C,DD．E,D,C,B,A16.在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時(shí)，top變化為______。A．top不變 B．top=0 C．top-- D．top++17.向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí)，應(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個(gè)單元的順序存儲的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)滿的條件為________。A．rear％n==frontB．（front+l）％n==rearC．rear％n-1==frontD．(rear+l)％n==front19.在具有n個(gè)單元的順序存儲的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)空的條件為________。A．rear％n==frontB．front+l=rearC．rear==frontD．(rear+l)％n=front20.在一個(gè)鏈隊(duì)列中，假定front和rear分別為隊(duì)首和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為________。A．front=front->nextB．rear=rear->nextC．rear=front->nextD．front=rear->next二、填空題1.線性表是一種典型的_________結(jié)構(gòu)。2.在一個(gè)長度為n的順序表的第i個(gè)元素之前插入一個(gè)元素，需要后移____個(gè)元素。3.順序表中邏輯上相鄰的元素的物理位置________。4.要從一個(gè)順序表刪除一個(gè)元素時(shí)，被刪除元素之后的所有元素均需_______一個(gè)位置，移動過程是從_______向_______依次移動每一個(gè)元素。5.在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過_______決定的；在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過_______決定的。6.在雙向鏈表中，每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域，一個(gè)指向_______結(jié)點(diǎn)，另一個(gè)指向_______結(jié)點(diǎn)。7.當(dāng)對一個(gè)線性表經(jīng)常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時(shí)，則采用_______存儲結(jié)構(gòu)為宜。相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時(shí)，則采用_______存儲結(jié)構(gòu)為宜。習(xí)題2參考答案一、單項(xiàng)選擇題1．A2．A3．D4．C5．D6．A7．B8．B9．C10．A11．D12．B13．C14．B15．C16．C17．B18．D19．C 20．A二、填空題1．線性2．n-i+13．相鄰4．前移，前，后5．物理存儲位置，鏈域的指針值6．前趨，后繼7．順序，鏈接8．一定，不一定9．線性，任何，棧頂，隊(duì)尾，隊(duì)頭10．單鏈表，雙鏈表，非循環(huán)鏈表，循環(huán)鏈表11．使空表和非空表統(tǒng)一；算法處理一致12．O(1)，O(n)13．棧滿，棧空，m，棧底，兩個(gè)棧的棧頂在?？臻g的某一位置相遇14．2、315．O(1)三、簡答題1．頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（即表頭結(jié)點(diǎn)）的指針；在表頭結(jié)點(diǎn)之前附設(shè)的結(jié)點(diǎn)稱為頭結(jié)點(diǎn)；表頭結(jié)點(diǎn)為鏈表中存儲線性表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。若鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。2．線性表具有兩種存儲結(jié)構(gòu)即順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)。線性表的順序存儲結(jié)構(gòu)可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時(shí)將會引起元素的大量移動，因而降低效率：而在鏈接存儲結(jié)構(gòu)中內(nèi)存采用動態(tài)分配，利用率高，但需增設(shè)指示結(jié)點(diǎn)之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲方便，但結(jié)點(diǎn)的插入、刪除操作較簡單。3．應(yīng)選用鏈接存儲結(jié)構(gòu)，因?yàn)殒準(zhǔn)酱鎯Y(jié)構(gòu)是用一組任意的存儲單元依次存儲線性表中的各元素，這里存儲單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲結(jié)構(gòu)對于元素的刪除或插入運(yùn)算是不需要移動元素的，只需修改指針即可，所以很容易實(shí)現(xiàn)表的容量的擴(kuò)充。4．應(yīng)選用順序存儲結(jié)構(gòu)，因?yàn)槊總€(gè)數(shù)據(jù)元素的存儲位置和線性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線性表中的序號成正比的常數(shù)。因此，只要確定了其起始位置，線性表中的任一個(gè)數(shù)據(jù)元素都可隨機(jī)存取，因此，線性表的順序存儲結(jié)構(gòu)是一種隨機(jī)存取的存儲結(jié)構(gòu)，而鏈表則是一種順序存取的存儲結(jié)構(gòu)。5．設(shè)尾指針比設(shè)頭指針好。尾指針是指向終端結(jié)點(diǎn)的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很方便，設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其尾指針為rear，則開始結(jié)點(diǎn)和終端結(jié)點(diǎn)的位置分別是rear->next->next和rear,查找時(shí)間都是O(1)。若用頭指針來表示該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為O(n)。6．共有14種可能的出棧序列，即為：ABCD,ABDC，ACBD,ACDB，BACD，ADCB，BADC，BCAD,BCDA，BDCA,CBAD,CBDA，CDBA,DCBA7．在隊(duì)列的順序存儲結(jié)構(gòu)中，設(shè)隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列的容量（即存儲的空間大?。閙axnum。當(dāng)有元素要加入隊(duì)列（即入隊(duì)）時(shí)，若rear=maxnum，則會發(fā)生隊(duì)列的上溢現(xiàn)象，此時(shí)就不能將該元素加入隊(duì)列。對于隊(duì)列，還有一種“假溢出”現(xiàn)象，隊(duì)列中尚余有足夠的空間，但元素卻不能入隊(duì)，一般是由于隊(duì)列的存儲結(jié)構(gòu)或操作方式的選擇不當(dāng)所致，可以用循環(huán)隊(duì)列解決。一般地，要解決隊(duì)列的上溢現(xiàn)象可有以下幾種方法：（1）可建立一個(gè)足夠大的存儲空間以避免溢出，但這樣做往往會造成空間使用率低，浪費(fèi)存儲空間。（2）要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決：第一種：采用移動元素的方法。每當(dāng)有一個(gè)新元素入隊(duì)，就將隊(duì)列中已有的元素向隊(duì)頭移動一個(gè)位置，假定空余空間足夠。第二種：每當(dāng)刪去一個(gè)隊(duì)頭元素，則可依次移動隊(duì)列中的元素總是使front指針指向隊(duì)列中的第一個(gè)位置。第三種：采用循環(huán)隊(duì)列方式。將隊(duì)頭、隊(duì)尾看作是一個(gè)首尾相接的循環(huán)隊(duì)列，即用循環(huán)數(shù)組實(shí)現(xiàn)，此時(shí)隊(duì)首仍在隊(duì)尾之前，作插入和刪除運(yùn)算時(shí)仍遵循“先進(jìn)先出”的原則。8．該算法的功能是：將開始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而原來的第二個(gè)結(jié)點(diǎn)成為新的開始結(jié)點(diǎn)，返回新鏈表的頭指針。四、算法設(shè)計(jì)題1．算法思想為：（1）應(yīng)判斷刪除位置的合法性，當(dāng)i<0或i>n-1時(shí)，不允許進(jìn)行刪除操作；（2）當(dāng)i=0時(shí)，刪除第一個(gè)結(jié)點(diǎn)：（3）當(dāng)０<i<n時(shí)，允許進(jìn)行刪除操作，但在查找被刪除結(jié)點(diǎn)時(shí)，須用指針記住該結(jié)點(diǎn)的前趨結(jié)點(diǎn)。算法描述如下：delete(LinkList*q,inti){//在無頭結(jié)點(diǎn)的單鏈表中刪除第i個(gè)結(jié)點(diǎn)LinkList*p,*s;intj;if(i<0)printf("Can'tdelete");elseif(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'tdelete");else{p->next=s->next;free(s);}}}2．由于在單鏈表中只給出一個(gè)頭指針，所以只能用遍歷的方法來數(shù)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)了。算法描述如下：intListLength(LinkList*L){//求帶頭結(jié)點(diǎn)的單鏈表的表長intlen=0;ListList*p;p=L;while(p->next!=NULL){p=p->next;len++;}return(len);}3．設(shè)單循環(huán)鏈表的頭指針為head，類型為LinkList。逆置時(shí)需將每一個(gè)結(jié)點(diǎn)的指針域作以修改，使其原前趨結(jié)點(diǎn)成為后繼。如要更改q結(jié)點(diǎn)的指針域時(shí)，設(shè)s指向其原前趨結(jié)點(diǎn)，p指向其原后繼結(jié)點(diǎn)，則只需進(jìn)行q->next=s;操作即可，算法描述如下：voidinvert(LinkList*head){//逆置head指針?biāo)赶虻膯窝h(huán)鏈表linklist*p,*q,*s;q=head;p=head->next;while(p!=head)//當(dāng)表不為空時(shí)，逐個(gè)結(jié)點(diǎn)逆置{s=q;q=p;p=p->next;q->next=s;}p->next=q;}4．定義類型LinkList如下：typedefstructnode{intdata;structnode*next,*prior;}LinkList;此題可采用插入排序的方法，設(shè)p指向待插入的結(jié)點(diǎn)，用q搜索已由prior域鏈接的有序表找到合適位置將p結(jié)點(diǎn)鏈入。算法描述如下：insert(LinkList*head){LinkList*p,*s,*q;p=head->next;//p指向待插入的結(jié)點(diǎn)，初始時(shí)指向第一個(gè)結(jié)點(diǎn)while(p!=NULL){s=head;//s指向q結(jié)點(diǎn)的前趨結(jié)點(diǎn)q=head->prior;//q指向由prior域構(gòu)成的鏈表中待比較的結(jié)點(diǎn)while((q!=NULL)&&(p->data>q->data))//查找插入結(jié)點(diǎn)p的合適插入位置{s=q;q=q->prior;}s->prior=p;p->prior=q;//結(jié)點(diǎn)p插入到結(jié)點(diǎn)s和結(jié)點(diǎn)q之間p=p->next;}}5．算法描述如下：delete(LinkList*head,intmax,intmin){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,intmax,intmin){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．本題是對一個(gè)循環(huán)鏈隊(duì)列做插入和刪除運(yùn)算，假設(shè)不需要保留被刪結(jié)點(diǎn)的值和不需要回收結(jié)點(diǎn)，算法描述如下：（1）插入（即入隊(duì)）算法：insert(LinkList*rear,elemtypex){//設(shè)循環(huán)鏈隊(duì)