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

1、數(shù)據(jù)結(jié)構(gòu)第二章線性表習(xí)題、單項(xiàng)選擇題1.線性表是A 一個(gè)有限序列，可以為空C 一個(gè)無(wú)限序列，可以為空B一個(gè)有限序列，不可以為空一個(gè)無(wú)D限序列，不可以為空個(gè)元素2.在一個(gè)長(zhǎng)度為n的順序表中刪除第i(o<=i<=n)時(shí)，需向前移動(dòng)丁本個(gè)兀索。An-iB-n-i+lCn-i-i3 .線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址A必須是連續(xù)的B.一定是不連續(xù)的C部分地址必須是連續(xù)的D.連續(xù)與否均可以x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較D. ( n-1 ) /24 .從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于個(gè)元素結(jié)點(diǎn)。A. n/2B.nC.(n+1)/25.在雙向循環(huán)鏈表中，在P所指的結(jié)點(diǎn)之后插入s指

2、針?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-&

3、gt;next=s;6.設(shè)單鏈表中指針p指向結(jié)點(diǎn)m若要?jiǎng)h除m之后的結(jié)點(diǎn)（若存在），則需修改指針的操作為.p=p->next;C,p=p->next->next;D.p->next=p;i個(gè)元素(0<A.p->next=p->next->next;B.,.一ivn+l)之前插入一個(gè)新元素時(shí)需向后移動(dòng)£在一I長(zhǎng)度為n的順序表中向第線性表中的每個(gè)結(jié)點(diǎn)都有且只有一個(gè)直接前趨和直接后繼。石素。A.n-iB.n-i+lC,n-i-1D.i8.在一個(gè)單鏈表中，已知q結(jié)點(diǎn)是p結(jié)點(diǎn)的前趨結(jié)點(diǎn)，若在q和P之間插入s結(jié)點(diǎn)，則須執(zhí)行A.s->next=p

4、->next;p->next=s,q->next=s;s->next=pC.p->next=s->next;s->next=p以下.p->next=s;s->next=q關(guān)于線性表的說(shuō)法不正確的是此線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。B,線性表中包含的數(shù)據(jù)元素個(gè)數(shù)不是任意的。存在這樣的線性表：表中各結(jié)點(diǎn)都沒(méi)有直接前趨和直接后繼。10 .線性表的順序存儲(chǔ)結(jié)構(gòu)是一種的存儲(chǔ)結(jié)構(gòu)。A.隨機(jī)存取B.順序存取C.索引存取D.散列存取11 .在順序表中，只要知道，就可在相同時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲(chǔ)地址。A.基地址B.結(jié)點(diǎn)大小C.向量大小D

5、,基地址和結(jié)點(diǎn)大小12 .在等概率情況下，順序表的插入操作要移動(dòng)結(jié)點(diǎn)。A.全部B.一半C.三分之一D.四分之一13 .在運(yùn)算中，使用順序表比鏈表好。A.插入B刪除C根據(jù)序號(hào)查找D根據(jù)元素值查找14 .在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并保持該表有序的時(shí)間復(fù)雜度是2cA-0(1)B-O(n)CO(n2)D-O(log2n)15 .設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳,B,C,D,E,下列是不可能的出棧序列。A-A,B,C,D,EBB,C,D,E,ACE,A,B,C,DD-E,D,C,B,A16 .在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端(即0單元)作為棧底，以top作為棧頂指針，當(dāng)做出

6、棧處理時(shí)，top變化為。A-top不變Btop=0Ctop-Dtop+17 .A - hs->next=s;BC s->next=hs->next;hs->next=s; D18 .在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定 斷隊(duì)滿的條件為 。A rear %n= = frontBC rear %n -1= = frontD19 .在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定 斷隊(duì)空的條件為 。向一個(gè)棧頂指針為hs的鏈棧,中插入一個(gè)s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行s->next=hs; hs=s;s->next=hs; hs=hs->next;front和rear分別為

7、隊(duì)頭指針和隊(duì)尾指針，則判front+l )% n= = rear(rear+l) % n= = frontfront和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判Arear%n=frontBfront+l=rearCrear=frontD(rear+l)%n=front20.在一個(gè)鏈隊(duì)列中，假定front和rear分別為隊(duì)首和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為Afront=front->nextBrear=rear->nextCrear=front->nextDfront=rear->next二、填空題1 .線性表是一種典型的結(jié)構(gòu)。2 .在一個(gè)長(zhǎng)度為n的順序表的第i個(gè)元素之前插

8、入一個(gè)元素，需要后移個(gè)元素。3 .順序表中邏輯上相鄰的元素的物理位置。4 .要從一個(gè)順序表刪除一個(gè)元素時(shí)，被刪除元素之后的所有元素均需一個(gè)位置，移動(dòng)過(guò)程是從向依次移動(dòng)每一個(gè)元素。5 .在線性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)決定的；在線性表的鏈接存儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)決定的。6 .在雙向鏈表中，每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域，一個(gè)指向結(jié)點(diǎn)，另一個(gè)指向結(jié)點(diǎn)。7 .當(dāng)對(duì)一個(gè)線性表經(jīng)常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時(shí)，則采用存儲(chǔ)結(jié)構(gòu)為宜。相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時(shí)，則采用存儲(chǔ)結(jié)構(gòu)為宜。8 .順序表中邏輯上相鄰的元素，物理位置相鄰，單鏈表中邏輯上相鄰的元素，物理位置相鄰。9

9、.線性表、棧和隊(duì)列都是結(jié)構(gòu)，可以在線性表的位置插入和刪除元素；對(duì)于棧只能在位置插入和刪除元素；對(duì)于隊(duì)列只能在位置插入元素和在位置刪除元素。10 .根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表可分為和；而根據(jù)指針的聯(lián)接方式，鏈表又可分為和。11 .在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是。12 .對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為，在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為。13 .對(duì)于一個(gè)棧作進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否為，作退棧運(yùn)算時(shí)，應(yīng)先判別棧是否為，當(dāng)棧中元素為m時(shí)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說(shuō)明棧的可用最大容量為。為了增加內(nèi)存空間的利用率和減少發(fā)

10、生上溢的可能性，由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí)，應(yīng)將兩棧的分別設(shè)在這片內(nèi)存空間的兩端，這樣只有當(dāng)時(shí)才產(chǎn)生上溢。14 .設(shè)有一空棧，現(xiàn)有輸入序列1，2，3，4，5，經(jīng)過(guò)push,push,pop,push,pop,push,push后，輸出序列是。15 .無(wú)論對(duì)于順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)的棧和隊(duì)列來(lái)說(shuō)，進(jìn)行插入或刪除運(yùn)算的時(shí)間復(fù)雜度均相同為三、簡(jiǎn)答題1 .描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，表頭結(jié)點(diǎn)。2 .線性表的兩種存儲(chǔ)結(jié)構(gòu)各有哪些優(yōu)缺點(diǎn)3 .對(duì)于線性表的兩種存儲(chǔ)結(jié)構(gòu)，如果有n個(gè)線性表同時(shí)并存，而且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化，線性表的總數(shù)也會(huì)自動(dòng)改變，在此情況下，應(yīng)選用哪一種存儲(chǔ)結(jié)

11、構(gòu)為什么4 .對(duì)于線性表的兩種存儲(chǔ)結(jié)構(gòu)，若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素，應(yīng)選用何種存儲(chǔ)結(jié)構(gòu)試說(shuō)明理由。5 .在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針好嗎為什么6 .假定有四個(gè)元素A,B,C,D依次進(jìn)棧，進(jìn)棧過(guò)程中允許出棧，試寫出所有可能的出棧序列。7 .什么是隊(duì)列的上溢現(xiàn)象一般有幾種解決方法，試簡(jiǎn)述之。8 .下述算法的功能是什么LinkList*Demo(LinkList*L)設(shè)計(jì)在無(wú)頭結(jié)點(diǎn)的單鏈表中刪除第i個(gè)結(jié)點(diǎn)的算法。2 .在單鏈表上實(shí)現(xiàn)線性表的求表長(zhǎng)ListLength(L)運(yùn)算。3 .設(shè)計(jì)將帶表頭的鏈表逆置算法。4 .假設(shè)有一個(gè)帶表頭

12、結(jié)點(diǎn)的鏈表，表頭指針為head，每個(gè)結(jié)點(diǎn)含三個(gè)域：data,next和prior。其中data為整型數(shù)域，next和prior均為指針域?，F(xiàn)在所有結(jié)點(diǎn)已經(jīng)由next域連接起來(lái)，試編一個(gè)算法，利用prior域(此域初值為NULL把所有結(jié)點(diǎn)按照其值從小到大的順序鏈接起來(lái)。5 .已知線性表的元素按遞增順序排列，并以帶頭結(jié)點(diǎn)的單鏈表作存儲(chǔ)結(jié)構(gòu)。試編寫一個(gè)刪除表中所有值大于min且小于max的元素(若表中存在這樣的元素)的算法。6 .已知線性表的元素是無(wú)序的，且以帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)。設(shè)計(jì)一個(gè)刪除表中所有值小于max但大于min的元素的算法。7 .假定用一個(gè)單循環(huán)鏈表來(lái)表示隊(duì)列(也稱為循環(huán)隊(duì)列)

13、，該隊(duì)列只設(shè)一個(gè)隊(duì)尾指針，不設(shè)隊(duì)首指針，試編寫下列各種運(yùn)算的算法：(1)向循環(huán)鏈隊(duì)列插入一個(gè)元素值為x的結(jié)點(diǎn)；(2)從循環(huán)鏈隊(duì)列中刪除一個(gè)結(jié)點(diǎn)。8 .設(shè)順序表L是一個(gè)遞減有序表，試寫一算法，將x插入其后仍保持L的有序性。習(xí)題2參考答案一、單項(xiàng)選擇題1A2A3D4C5D6A7B8B9C10-A11-D12-B13-C14-B15-C16C17-B18-D19-C20-A二、填空題1-線性2ni+13相鄰4前移，前，后5物理存儲(chǔ)位置，鏈域的指針值6前趨，后繼7順序，鏈接8一定，不一定9線性，任何，棧頂，隊(duì)尾，隊(duì)頭10單鏈表，雙鏈表，非循環(huán)鏈表，循環(huán)鏈表11使空表和非空表統(tǒng)一；算法處理一致12 0(

14、1)，O(n)13 棧滿，棧空，m棧底，兩個(gè)棧的棧頂在?？臻g的某一位置相遇14 -2>315。三、簡(jiǎn)答題1 .頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)(即表頭結(jié)點(diǎn))的指針；在表頭結(jié)點(diǎn)之前附設(shè)的結(jié)點(diǎn)稱為頭結(jié)點(diǎn)；表頭結(jié)點(diǎn)為鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。若鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。2 線性表具有兩種存儲(chǔ)結(jié)構(gòu)即順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)。線性表的順序存儲(chǔ)結(jié)構(gòu)可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時(shí)將會(huì)引起元素的大量移動(dòng)，因而降低效率：而在鏈接存儲(chǔ)結(jié)構(gòu)中內(nèi)存采用動(dòng)態(tài)分配，利用率高，但需增設(shè)指示結(jié)點(diǎn)之間關(guān)系的指針域，存取

15、數(shù)據(jù)元素不如順序存儲(chǔ)方便，但結(jié)點(diǎn)的插入、刪除操作較簡(jiǎn)單。3 應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)，因?yàn)殒準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元依次存儲(chǔ)線性表中的各元素，這里存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲(chǔ)結(jié)構(gòu)對(duì)于元素的刪除或插入運(yùn)算是不需要移動(dòng)元素的，只需修改指針即可，所以很容易實(shí)現(xiàn)表的容量的擴(kuò)充。4 應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)，因?yàn)槊總€(gè)數(shù)據(jù)元素的存儲(chǔ)位置和線性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線性表中的序號(hào)成正比的常數(shù)。因此，只要確定了其起始位置，線性表中的任一個(gè)數(shù)據(jù)元素都可隨機(jī)存取，因此，線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，而鏈表則是一種順序存取的存儲(chǔ)結(jié)構(gòu)。5設(shè)尾指針比設(shè)頭指針好。尾指針是指向終端

16、結(jié)點(diǎn)的指針，用它來(lái)表示單循環(huán)鏈表可以使得查找鏈表的開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很方便，設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其尾指針為rear，則開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)的位置分別是rear->next->nextftrear,查找時(shí)間都是。若用頭指針來(lái)表示該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為O(n)。6 共有14種可能的出棧序列，即為：ABCD,ABDC，ACBD,ACDB，BACD，ADCB，BADC，BCAD,BCDA，BDCA,CBAD,CBD，ACDBA,DCBA7 .在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，設(shè)隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列的容量(即存儲(chǔ)的空間大小)為maxnum當(dāng)有元素要加入隊(duì)列(即入

17、隊(duì))時(shí)，若rear=maxnum，則會(huì)發(fā)生隊(duì)列的上溢現(xiàn)象，此時(shí)就不能將該元素加入隊(duì)列。對(duì)于隊(duì)列，還有一種“假溢出”現(xiàn)象，隊(duì)列中尚余有足夠的空間，但元素卻不能人隊(duì)，一般是由于隊(duì)列的存儲(chǔ)結(jié)構(gòu)或操作方式的選擇不當(dāng)所致，可以用循環(huán)隊(duì)列解決。一般地，要解決隊(duì)列的上溢現(xiàn)象可有以下幾種方法：(1)可建立一個(gè)足夠大的存儲(chǔ)空間以避免溢出，但這樣做往往會(huì)造成空間使用率低，浪費(fèi)存儲(chǔ)空間。(2)要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決：第一種：采用移動(dòng)元素的方法。每當(dāng)有一個(gè)新元素人隊(duì)，就將隊(duì)列中已有的元素向隊(duì)頭移動(dòng)一個(gè)位置，假定空余空間足夠。第二種：每當(dāng)刪去一個(gè)隊(duì)頭元素，則可依次移動(dòng)隊(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該算法的功能是：將開(kāi)始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而原來(lái)的第二個(gè)結(jié)點(diǎn)成為新的開(kāi)始結(jié)點(diǎn)，返回新鏈表的頭指針。四、算法設(shè)計(jì)題1算法思想為：(1)應(yīng)判斷刪除位置的合法性，當(dāng)i