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

1、第 2 章 線性表 課后習(xí)題講解 1. 填空 在順序表中，等概率情況下，插入和刪除一個元素平均需移動（ ）個元素，具體移動元素的個數(shù)與（ ）和（ ）有關(guān)?！窘獯稹勘黹L的一半，表長，該元素在表中的位置 順序表中第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的存儲地址是（ ）?！窘獯稹?08【分析】第5個元素的存儲地址=第1個元素的存儲地址(51)×2=108 設(shè)單鏈表中指針p 指向結(jié)點(diǎn)A，若要刪除A的后繼結(jié)點(diǎn)（假設(shè)A存在后繼結(jié)點(diǎn)），則需修改指針的操作為（ ）?！窘獯稹縫->next=(p->next)->next 單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是（ ）?！窘?/p>

2、答】為了運(yùn)算方便【分析】例如在插入和刪除操作時不必對表頭的情況進(jìn)行特殊處理。 非空的單循環(huán)鏈表由頭指針head指示，則其尾結(jié)點(diǎn)（由指針p所指）滿足（ ）?！窘獯稹縫->next=head【分析】如圖2-8所示。 在由尾指針rear指示的單循環(huán)鏈表中，在表尾插入一個結(jié)點(diǎn)s的操作序列是（ ）；刪除開始結(jié)點(diǎn)的操作序列為（ ）。【解答】s->next =rear->next; rear->next =s; rear =s;q=rear->next->next; rear->next->next=q->next; delete q;【分析】操作示意圖

3、如圖2-9所示： 一個具有n個結(jié)點(diǎn)的單鏈表，在指針p所指結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)的時間復(fù)雜度為（ ）；在給定值為x的結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)的時間復(fù)雜度為（ ）?！窘獯稹?1)，(n)【分析】在p所指結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)只需修改指針，所以時間復(fù)雜度為(1)；而在給定值為x的結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)需要先查找值為x的結(jié)點(diǎn)，所以時間復(fù)雜度為(n)。 可由一個尾指針唯一確定的鏈表有（ ）、（ ）、（ ）?！窘獯稹垦h(huán)鏈表，循環(huán)雙鏈表，雙鏈表2. 選擇題 線性表的順序存儲結(jié)構(gòu)是一種（ ）的存儲結(jié)構(gòu)，線性表的鏈接存儲結(jié)構(gòu)是一種（ ）的存儲結(jié)構(gòu)。 A 隨機(jī)存取 B 順序存取 C 索引存取 D 散列存取【解答】A，B【

4、分析】參見2.2.1。 線性表采用鏈接存儲時，其地址（ ）。A 必須是連續(xù)的 B 部分地址必須是連續(xù)的C 一定是不連續(xù)的 D 連續(xù)與否均可以【解答】D【分析】線性表的鏈接存儲是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，這組存儲單元可以連續(xù)，也可以不連續(xù)，甚至可以零散分布在內(nèi)存中任意位置。 單循環(huán)鏈表的主要優(yōu)點(diǎn)是（ ）。A 不再需要頭指針了 B 從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個鏈表；C 已知某個結(jié)點(diǎn)的位置后，能夠容易找到它的直接前趨；D 在進(jìn)行插入、刪除操作時，能更好地保證鏈表不斷開?！窘獯稹緽 鏈表不具有的特點(diǎn)是（ ）。A 可隨機(jī)訪問任一元素 B 插入、刪除不需要移動元素C 不必事先估計存儲空

5、間 D 所需空間與線性表長度成正比【解答】A 若某線性表中最常用的操作是取第i 個元素和找第i個元素的前趨，則采用（ ）存儲方法最節(jié)省時間。A 順序表 B 單鏈表 C 雙鏈表 D 單循環(huán)鏈表【解答】A【分析】線性表中最常用的操作是取第i 個元素，所以，應(yīng)選擇隨機(jī)存取結(jié)構(gòu)即順序表，同時在順序表中查找第i個元素的前趨也很方便。單鏈表和單循環(huán)鏈表既不能實現(xiàn)隨機(jī)存取，查找第i個元素的前趨也不方便，雙鏈表雖然能快速查找第i個元素的前趨，但不能實現(xiàn)隨機(jī)存取。 若鏈表中最常用的操作是在最后一個結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)和刪除第一個結(jié)點(diǎn)，則采用（ ）存儲方法最節(jié)省時間。A 單鏈表 B 帶頭指針的單循環(huán)鏈表 C 雙鏈

6、表 D 帶尾指針的單循環(huán)鏈表【解答】D【分析】在鏈表中的最后一個結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)需要知道終端結(jié)點(diǎn)的地址，所以，單鏈表、帶頭指針的單循環(huán)鏈表、雙鏈表都不合適，考慮在帶尾指針的單循環(huán)鏈表中刪除第一個結(jié)點(diǎn)，其時間性能是O(1)，所以，答案是D 。 若鏈表中最常用的操作是在最后一個結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)和刪除最后一個結(jié)點(diǎn)，則采用（ ）存儲方法最節(jié)省運(yùn)算時間。A 單鏈表 B 循環(huán)雙鏈表 C單循環(huán)鏈表 D 帶尾指針的單循環(huán)鏈表【解答】B【分析】在鏈表中的最后一個結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)需要知道終端結(jié)點(diǎn)的地址，所以，單鏈表、單循環(huán)鏈表都不合適，刪除最后一個結(jié)點(diǎn)需要知道終端結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的地址，所以，帶尾指針的

7、單循環(huán)鏈表不合適，而循環(huán)雙鏈表滿足條件。 在具有n個結(jié)點(diǎn)的有序單鏈表中插入一個新結(jié)點(diǎn)并仍然有序的時間復(fù)雜度是（ ）。A O(1) B O(n) C O(n2) D O(nlog2n)【解答】B【分析】首先應(yīng)順序查找新結(jié)點(diǎn)在單鏈表中的位置。 對于n個元素組成的線性表，建立一個有序單鏈表的時間復(fù)雜度是（ ）。A O(1) B O(n) C O(n2) D O(nlog2n)【解答】C【分析】該算法需要將n個元素依次插入到有序單鏈表中，而插入每個元素需O(n)。 使用雙鏈表存儲線性表，其優(yōu)點(diǎn)是可以（ ）。A 提高查找速度 B 更方便數(shù)據(jù)的插入和刪除C 節(jié)約存儲空間 D 很快回收存儲空間【解答】B【分

8、析】在鏈表中一般只能進(jìn)行順序查找，所以，雙鏈表并不能提高查找速度，因為雙鏈表中有兩個指針域，顯然不能節(jié)約存儲空間，對于動態(tài)存儲分配，回收存儲空間的速度是一樣的。由于雙鏈表具有對稱性，所以，其插入和刪除操作更加方便。 在一個單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接前驅(qū)，若在q和p之間插入s所指結(jié)點(diǎn)，則執(zhí)行（ ）操作。A s->next=p->next; p->next=s; B q->next=s; s->next=p; C p->next=s->next; s->next=p; D p->next=s; s->next=q;【解答】

9、B【分析】注意此題是在q和p之間插入新結(jié)點(diǎn)，所以，不用考慮修改指針的順序。 在循環(huán)雙鏈表的p所指結(jié)點(diǎn)后插入s所指結(jié)點(diǎn)的操作是（ ）。A p->next=s; s->prior=p; p->next->prior=s; s->next=p->next; B p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;C s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;D

10、s->prior=p; s->next=p->next; p->next->prior=s; p->next=s【解答】D【分析】在鏈表中，對指針的修改必須保持線性表的邏輯關(guān)系，否則，將違背線性表的邏輯特征，圖2-10給出備選答案C和D的圖解。3. 判斷題 線性表的邏輯順序和存儲順序總是一致的?！窘獯稹垮e。順序表的邏輯順序和存儲順序一致，鏈表的邏輯順序和存儲順序不一定一致。 線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈接存儲結(jié)構(gòu)?！窘獯稹垮e。兩種存儲結(jié)構(gòu)各有優(yōu)缺點(diǎn)。 設(shè)p，q是指針，若p=q，則*p=*q?！窘獯稹垮e。p=q只能表示p和q指向同一起始地址，而所指類型則不一定相

11、同。 線性結(jié)構(gòu)的基本特征是：每個元素有且僅有一個直接前驅(qū)和一個直接后繼?！窘獯稹垮e。每個元素最多只有一個直接前驅(qū)和一個直接后繼，第一個元素沒有前驅(qū)，最后一個元素沒有后繼。 在單鏈表中，要取得某個元素，只要知道該元素所在結(jié)點(diǎn)的地址即可，因此單鏈表是隨機(jī)存取結(jié)構(gòu)?！窘獯稹垮e。要找到該結(jié)點(diǎn)的地址，必須從頭指針開始查找，所以單鏈表是順序存取結(jié)構(gòu)。4請說明順序表和單鏈表各有何優(yōu)缺點(diǎn)，并分析下列情況下，采用何種存儲結(jié)構(gòu)更好些。 若線性表的總長度基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素。 如果n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化。 描述一個城市的設(shè)計和

12、規(guī)劃。【解答】順序表的優(yōu)點(diǎn)： 無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲空間； 可以快速地存取表中任一位置的元素（即隨機(jī)存?。?。順序表的缺點(diǎn)： 插入和刪除操作需移動大量元素； 表的容量難以確定； 造成存儲空間的“碎片”。單鏈表的優(yōu)點(diǎn)： 不必事先知道線性表的長度； 插入和刪除元素時只需修改指針，不用移動元素。單鏈表的缺點(diǎn)： 指針的結(jié)構(gòu)性開銷； 存取表中任意元素不方便，只能進(jìn)行順序存取。 應(yīng)選用順序存儲結(jié)構(gòu)。因為順序表是隨機(jī)存取結(jié)構(gòu)，單鏈表是順序存取結(jié)構(gòu)。本題很少進(jìn)行插入和刪除操作，所以空間變化不大，且需要快速存取，所以應(yīng)選用順序存儲結(jié)構(gòu)。 應(yīng)選用鏈接存儲結(jié)構(gòu)。鏈表容易實現(xiàn)表容量的擴(kuò)充，適合

13、表的長度動態(tài)發(fā)生變化。 應(yīng)選用鏈接存儲結(jié)構(gòu)。因為一個城市的設(shè)計和規(guī)劃涉及活動很多，需要經(jīng)常修改、擴(kuò)充和刪除各種信息，才能適應(yīng)不斷發(fā)展的需要。而順序表的插入、刪除的效率低，故不合適。5算法設(shè)計 設(shè)計一個時間復(fù)雜度為(n)的算法，實現(xiàn)將數(shù)組An中所有元素循環(huán)右移k個位置?！窘獯稹克惴ㄋ枷胝垍⒁娭鹘滩牡谝徽滤枷牖鸹?。下面給出具體算法。分析算法，第一次調(diào)用Reverse函數(shù)的時間復(fù)雜度為O(k)，第二次調(diào)用Reverse函數(shù)的時間復(fù)雜度為O(n-k)，第三次調(diào)用Reverse函數(shù)的時間復(fù)雜度為O(n)，所以，總的時間復(fù)雜度為O(n)。 已知數(shù)組An中的元素為整型，設(shè)計算法將其調(diào)整為左右兩部分，左邊所有

14、元素為奇數(shù)，右邊所有元素為偶數(shù)，并要求算法的時間復(fù)雜度為(n)?！窘獯稹繌臄?shù)組的兩端向中間比較，設(shè)置兩個變量i和j，初始時i=0，j=n-1，若Ai為偶數(shù)并且Aj為奇數(shù)，則將Ai與Aj交換。具體算法如下：分析算法，兩層循環(huán)將數(shù)組掃描一遍，所以，時間復(fù)雜度為(n)。 試編寫在無頭結(jié)點(diǎn)的單鏈表上實現(xiàn)線性表的插入操作的算法，并和帶頭結(jié)點(diǎn)的單鏈表上的插入操作的實現(xiàn)進(jìn)行比較?！窘獯稹繀⒁?.2.3。 試分別以順序表和單鏈表作存儲結(jié)構(gòu)，各寫一實現(xiàn)線性表就地逆置的算法。【解答】順序表的逆置，即是將對稱元素交換，設(shè)順序表的長度為length，則將表中第i個元素與第length-i-1個元素相交換。具體算法如下

15、：單鏈表的逆置請參見2.2.4算法2-4和算法2-6。 假設(shè)在長度大于1的循環(huán)鏈表中，即無頭結(jié)點(diǎn)也無頭指針，s為指向鏈表中某個結(jié)點(diǎn)的指針，試編寫算法刪除結(jié)點(diǎn)s的前趨結(jié)點(diǎn)?！窘獯稹坷脝窝h(huán)鏈表的特點(diǎn)，通過指針s可找到其前驅(qū)結(jié)點(diǎn)r以及r的前驅(qū)結(jié)點(diǎn)p，然后將結(jié)點(diǎn)r刪除，如圖2-11所示，具體算法如下： 已知一單鏈表中的數(shù)據(jù)元素含有三類字符：字母、數(shù)字和其他字符。試編寫算法，構(gòu)造三個循環(huán)鏈表，使每個循環(huán)鏈表中只含同一類字符?！窘獯稹吭趩捂湵鞟中依次取元素，若取出的元素是字母，把它插入到字母鏈表B 中，若取出的元素是數(shù)字，則把它插入到數(shù)字鏈表D中，直到鏈表的尾部，這樣表B，D，A中分別存放字母、數(shù)字和

16、其他字符。具體算法如下： 設(shè)單鏈表以非遞減有序排列，設(shè)計算法實現(xiàn)在單鏈表中刪去值相同的多余結(jié)點(diǎn)。【解答】從頭到尾掃描單鏈表，若當(dāng)前結(jié)點(diǎn)的元素值與后繼結(jié)點(diǎn)的元素值不相等，則指針后移；否則刪除該后繼結(jié)點(diǎn)。具體算法如下： 判斷帶頭結(jié)點(diǎn)的雙循環(huán)鏈表是否對稱?！窘獯稹吭O(shè)工作指針p和q分別指向循環(huán)雙鏈表的開始結(jié)點(diǎn)和終端結(jié)點(diǎn)，若結(jié)點(diǎn)p和結(jié)點(diǎn)q的數(shù)據(jù)域相等，則工作指針p后移，工作指針q前移，直到指針p和指針 q指向同一結(jié)點(diǎn)（循環(huán)雙鏈表中結(jié)點(diǎn)個數(shù)為奇數(shù)），或結(jié)點(diǎn)q成為結(jié)點(diǎn)p的前驅(qū)（循環(huán)雙鏈表中結(jié)點(diǎn)個數(shù)為偶數(shù)）。如圖2-12所示。學(xué)習(xí)自測及答案 1. 已知一維數(shù)組A采用順序存儲結(jié)構(gòu)，每個元素占用4個存儲單元，第9

17、個元素的地址為144，則第一個元素的地址是（ ）。A 108 B 180 C 176 D 112【解答】D2在長度為n的線性表中查找值為x的數(shù)據(jù)元素的時間復(fù)雜度為： （ ）。 A O(0) B O(1) C O(n) D O(n2)【解答】C3在一個長度為n的順序表的第i（1in+1）個元素之前插入一個元素，需向后移動（ ）個元素，刪除第i（1in）個元素時，需向前移動（ ）個元素?！窘獯稹縩-i+1，n-i 4在單鏈表中，除了頭結(jié)點(diǎn)以外，任一結(jié)點(diǎn)的存儲位置由（ ）指示?！窘獯稹科淝摆吔Y(jié)點(diǎn)的指針域 5當(dāng)線性表采用順序存儲結(jié)構(gòu)時，其主要特點(diǎn)是（ ）?！窘獯稹窟壿嫿Y(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲結(jié)構(gòu)中仍相鄰

18、6在雙鏈表中，每個結(jié)點(diǎn)設(shè)置了兩個指針域，其中一個指向（ ）結(jié)點(diǎn)，另一個指向（ ）結(jié)點(diǎn)?！窘獯稹壳膀?qū)，后繼7設(shè)A是一個線性表（a1, a2, , an），采用順序存儲結(jié)構(gòu)，則在等概率的前提下，平均每插入一個元素需要移動的元素個數(shù)為多少？若元素插在ai與ai+1之間（1in）的概率為 ，則平均每插入一個元素所要移動的元素個數(shù)又是多少？【解答】 ，。8線性表存放在整型數(shù)組Aarrsize的前elenum 個單元中，且遞增有序。編寫算法，將元素x插入到線性表的適當(dāng)位置上，以保持線性表的有序性，并且分析算法的時間復(fù)雜度?！窘獯稹勘绢}是在一個遞增有序表中插入元素x，基本思路是從有序表的尾部開始依次取元素與x比較，若大于x，此元素后移一位，再取它前面一個元素重復(fù)上述步驟；否則，找到插入位置，將x插入。具體算法如下：9. 已知單鏈表中各