數(shù)據(jù)結(jié)構(gòu)第二章線性表習(xí)題(編輯修改稿)
2025-04-21 03:01 本頁面
【文章內(nèi)容簡介】 刪除操作，但要求以最快的速度存取線性表中的元素，應(yīng)選用何種存儲結(jié)構(gòu)？試說明理由。5. 在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針好嗎？為什么?6. 假定有四個元素A, B, C, D依次進棧，進棧過程中允許出棧，試寫出所有可能的出棧序列。7. 什么是隊列的上溢現(xiàn)象？一般有幾種解決方法，試簡述之。8. 下述算法的功能是什么?LinkList *Demo(LinkList *L){ // L是無頭結(jié)點的單鏈表LinkList *q,*p。if(Lamp。amp。Lnext){ q=L。 L=Lnext。 p=L?！ ?while (pnext) p=pnext?！ ? pnext=q。 qnext=NULL?！ return (L)。}四、算法設(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的有序性。 完美WORD格式編輯 習(xí)題2參考答案一、單項選擇題1．A 2．A 3．D 4．C 5．D 6．A 7．B 8．B 9．C 10．A 11．D 12．B 13．C 14．B 15．C 16．C 17．B 18．D 19．C 20．A二、填空題1．線性 2．ni+1 3．相鄰 4．前移，前，后 5．物理存儲位置，鏈域的指針值6．前趨，后繼 7．順序，鏈接 8．一定，不一定 9．線性，任何，棧頂，隊尾，隊頭10．單鏈表，雙鏈表，非循環(huán)鏈表，循環(huán)鏈表11．使空表和非空表統(tǒng)一；算法處理一致12．O(1)，O(n)13．棧滿，?？?，m，棧底，兩個棧的棧頂在?？臻g的某一位置相遇14．3 15．O(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)表的容量的擴充。4．應(yīng)選用順序存儲結(jié)構(gòu)，因為每個數(shù)據(jù)元素的存儲位置和線性表的起始位置相差一個和數(shù)據(jù)元素在線性表中的序號成正比的常數(shù)。因此，只要確定了其起始位置，線性表中的任一個數(shù)據(jù)元素都可隨機存取，因此，線性表的順序存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu)，而鏈表則是一種順序存取的存儲結(jié)構(gòu)。5．設(shè)尾指針比設(shè)頭指針好。尾指針是指向終端結(jié)點的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點和終端結(jié)點都很方便，設(shè)一帶
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1