數(shù)據(jù)結(jié)構(gòu)第2章典型例題解析

1、第 2章 線 性 表典型例題解析、選擇題1線性表是具有 n 個（ n0）的有限序列。A表元素B 字符 C 數(shù)據(jù)元素 D 數(shù)據(jù)項【分析】線性表是具有相同數(shù)據(jù)類型的n（n 0）個數(shù)據(jù)元素的有限序列，通常記為（a1,a2,an），其中 n為表長， n=0 時稱為空表。【答案】 C2順序存儲結(jié)構(gòu)的優(yōu)點是。A存儲密度大B插入運算方便C刪除運算方便D可方便地用于各種邏輯結(jié)構(gòu)的存儲表示【分析】順序存儲結(jié)構(gòu)是采用一組地址連續(xù)的存儲單元來依次存放數(shù)據(jù)元素，數(shù)據(jù)元素 的邏輯順序和物理次序一致。因此，其存儲密度大?！敬鸢浮?A3帶頭結(jié)點的單鏈表 head 為空的判斷條件是 。A head=NULLB head- n

2、ext=NULLC head- next=headDhead!=NULL【分析】鏈表為空時，頭結(jié)點的指針域為空?！敬鸢浮?B 4若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素， 則采用 存儲方式最節(jié)省運算時間。A單鏈表B僅有頭指針的單循環(huán)鏈表C雙鏈表D僅有尾指針的單循環(huán)鏈表【分析】根據(jù)題意要求，該線性表的存儲應(yīng)能夠很方便地找到線性表的第一個元素和最 后一個元素， A和 B都能很方便地通過頭指針找到線性表的第一個元素，卻要經(jīng)過所有元素 才能找到最后一個元素；選項 C 雙鏈表若存為雙向循環(huán)鏈表，則能很方便地找到線性表的第 一個元素和最后一個元素，但存儲效率要低些，插入和刪

3、除操作也略微復(fù)雜；選項 D 可通過 尾指針直接找到線性表的最后一個元素，通過線性表的最后一個元素的循環(huán)指針就能很方便 地找到第一個元素?！敬鸢浮?D5若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算， 則利用 存儲方式最節(jié)省時間。A順序表 B雙鏈表C帶頭結(jié)點的雙循環(huán)鏈表D單循環(huán)鏈表【分析】某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運 算。因此不需要移動線性表種元素的位置。根據(jù)題意要求，該線性表的存儲應(yīng)能夠很方便地 找到線性表的任一指定序號的元素和最后一個元素，順序表是由地址連續(xù)的向量實現(xiàn)的，因 此具有按序號隨機訪問的特點。鏈表需要通過指針才能找到

4、線性表的莫以指定序號的元素， 需要一定的時間開銷。【答案】 A6設(shè)一個鏈表最常用的操作是在末尾插入結(jié)點和刪除尾結(jié)點，則選用最節(jié)省時間。A. 單鏈表B. 單循環(huán)鏈表C. 帶尾指針的單循環(huán)鏈表D. 帶頭結(jié)點的雙循環(huán)鏈表【分析】根據(jù)題意要求，該線性表的存儲應(yīng)能夠很方便地找到線性表的最后一個元素和 最后一個元素的前驅(qū)元素， A 和 B 都不能很方便地通過頭指針找到線性表的第一個元素；選 項 C 可以方便地找到最后一個元素， 單不能很快地找到其前驅(qū)元素； 選項 D為雙向循環(huán)鏈表， 可以很方便地找到線性表的最后一個元素，通過其前驅(qū)指針，從而可以方便地找到其前驅(qū)元 素?！敬鸢浮?D7靜態(tài)鏈表中指針表示的是。

5、A 內(nèi)存地址B 數(shù)組下標 C 下一元素地址 D 左、右孩子地址【分析】靜態(tài)鏈表采用的是鏈式方式存儲線性表，以數(shù)組方式存儲鏈表的數(shù)據(jù)，指針域 存儲的是該結(jié)點邏輯上的后繼結(jié)點的相對地址（即在數(shù)組中的下標） ，也稱為靜態(tài)指針。【答案】 B8鏈表不具有的特點是。A插入、刪除不需要移動元素B可隨機訪問任一元素C不必事先估計存儲空間D所需空間與線性長度成正比【分析】鏈表是通過一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素的，為建立起數(shù)據(jù) 元素之間的線性關(guān)系，對每個數(shù)據(jù)元素，除了存放數(shù)據(jù)元素自身的信息之外，還需要和存放 其后繼元素所在的存儲單元的地址。鏈表不具有按序號隨機訪問第 i 個元素的特點，必須通 過標識

6、鏈表的頭指針(或尾指針) “順藤摸瓜”才能找到第 i 個結(jié)點?！敬鸢浮?B9線性表的靜態(tài)鏈表存儲結(jié)構(gòu)與順序存儲結(jié)構(gòu)相比優(yōu)點是。A所有的操作算法簡單B便于插入和刪除C便于利用零散的存儲器空間D便于隨機存取【分析】靜態(tài)鏈表采用的是鏈式方式存儲線性表，因此其具有鏈式存儲的特點?！敬鸢浮?B10若長度為 n 的線性表采用順序存儲結(jié)構(gòu)，在其第 i 個位置插入一個新元素算法的時間復(fù)雜度為 。2A O(log 2n)BO(1)CO( n)D O( n2)【分析】在第 i 個位置上插入新元素需要從最后一個元素開始后移直到第 i 個元素后移 為止，后移元素的次數(shù)為 n-i +1，即時間復(fù)雜度為 O(n)。【答案

7、】 C11線性表( a1,a2, ,an )以鏈接方式存儲時，訪問第i 個位置元素的時間復(fù)雜性為。AO(i )BO(1)CO( n)D O( i -1)【分析】線性表以鏈接方式存儲時，訪問第 i 個位置元素從第一個元素開始移動指針到 第i 個元素，移動指針的次數(shù)為 n- i +1，即時間復(fù)雜度為 O(n)?！敬鸢浮?C12將兩個各有 n 個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是 。AnB 2n-1C2nD n-1分析】當(dāng)一個表的最小元素大于另一個表的最大元素時比較次數(shù)為最少，共需 n 次。 答案】 A13非空的循環(huán)單鏈表 head 的尾結(jié)點 p 滿足A p-next=headB p-

8、next=NULL Cp=NULLD p=head分析】非空的循環(huán)單鏈表 head 的尾結(jié)點的后繼指針指向鏈表的頭結(jié)點。答案】 A14在雙循環(huán)鏈表 p所指結(jié)點之后插入 s 所指結(jié)點的操作是Ap- next=s; s- prior=p; p - next - prior=s; s- prior=p - next;Bp- next=s; p- next - prior=s; s - prior=p; s- next=p - next;Cs- prior=p; s- next=p - next; p - next=s; p- next - prior=s;Ds- prior=p; s- next=p

9、 - next; p - next - prior=s; p - next=s;分析】由于要將s 所指結(jié)點插入到 p 所指結(jié)點之后， p 結(jié)點為 s 結(jié)點的前驅(qū)， s 結(jié)點為p 結(jié)點的新后繼，而結(jié)點 p 的原后繼結(jié)點為結(jié)點 s 的后繼結(jié)點，結(jié)點 s 為結(jié)點 p 的原后繼結(jié) 點的前驅(qū)結(jié)點 s。在選項 A、B和 C中均是先執(zhí)行操作 p- next=s ，就是修改了結(jié)點 p的后繼 結(jié)點 s，然后再執(zhí)行操作 p- next - prior=s ，因此，無法使得結(jié)點 s 為結(jié)點 p 的原后繼結(jié)點 的前驅(qū)結(jié)點，這樣的賦值會使 s 結(jié)點為其自身的前驅(qū)。應(yīng)先執(zhí)行操作 p- next - prior=s ，再

10、執(zhí)行操作 p- next=s 。答案】 D15在一個單鏈表中，已知 q 所指結(jié)點是 p 所指結(jié)點的前驅(qū)結(jié)點，若在 q 結(jié)點和 p 結(jié)點 之間插入 s 結(jié)點，則執(zhí)行 。A s- next=p - next;p - next=s;B p- next=s - next;s - next=p;C q- next=s; s - next=p;Dp- next=s; s - next=q;【分析】由于是將 s所指結(jié)點插入到 q和 p所指結(jié)點之間，即使其為 q所指結(jié)點的后繼 結(jié)點，為 p 所指結(jié)點的前驅(qū)結(jié)點，因此 s - next 的取值應(yīng)為 p， p- next 的取值無需改動， q- next 的取值應(yīng)

11、改為 s，故 A、B 和 D均是錯誤的?！敬鸢浮?C二、判斷題1線性表的特點是每個元素都有一個前驅(qū)和一個后繼?！痉治觥烤€性表是一種邏輯結(jié)構(gòu)，其數(shù)據(jù)元素屬于相同數(shù)據(jù)類型，之間的關(guān)系是線性關(guān) 系。線性表中除第一個數(shù)據(jù)元素和最后一個數(shù)據(jù)元素外，外每個元素都有一個前驅(qū)和一個后 繼。【答案】錯誤2順序存儲的線性表可以按序號隨機存取?！痉治觥恳驗轫樞虮碓趦?nèi)存是用地址連續(xù)的空間存儲的，設(shè)a1的存儲地址為 Loc( a1) ，每個數(shù)據(jù)元素占 d 個存儲地址，則第 i 個數(shù)據(jù)元素的地址為：Loc( ai )=Loc( a)+( i-1)d 1 i n這就是說只要知道順序表首地址和每個數(shù)據(jù)元素所占地址單元的個數(shù)就

12、可求出第 i 個數(shù) 據(jù)元素的地址來，這也是順序表具有按數(shù)據(jù)元素的序號隨機存取的特點。【答案】正確3鏈表中的頭結(jié)點僅起到標識的作用。【分析】頭結(jié)點是附加在第一個元素結(jié)點之前的一個結(jié)點，當(dāng)該鏈表表示一個非空的線 性表時，頭結(jié)點的指針域指向第一個元素結(jié)點，為空表時，該指針域為空。其作用是為了運 算上的方便?！敬鸢浮垮e誤 4線性表采用鏈表存儲時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的?！痉治觥挎湵硎峭ㄟ^一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素的，為建立起數(shù)據(jù) 元素之間的線性關(guān)系，對每個數(shù)據(jù)元素，除了存放數(shù)據(jù)元素自身的信息之外，還需要存放其 后繼元素所在的存儲單元的地址。鏈表中結(jié)點的存儲空間可以是不連

13、續(xù)的，但結(jié)點內(nèi)部的存 儲空間必須是連續(xù)的?！敬鸢浮垮e誤5在單鏈表中和在順序表中插入一個元素其時間復(fù)雜度均為O(n) ，因此說它們的執(zhí)行時間是相等的。【分析】大 O記法表示時間漸近復(fù)雜度，是指一個算法中的時間耗費，往往是問題規(guī)模n的函數(shù) T( n) ，當(dāng) n趨向于無窮大時， T( n)的數(shù)量級稱為算法的時間漸近復(fù)雜度。雖然兩種存 儲結(jié)構(gòu)下的插入操作時間復(fù)雜度均為 O(n) ，但由于兩者的基本操作不同， 因此不能說它們的 執(zhí)行時間是相等的?！敬鸢浮垮e誤6所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表?！痉治觥快o態(tài)鏈表是指以數(shù)組方式存儲鏈表的數(shù)據(jù)，數(shù)組的每個元素包含有數(shù)據(jù)域data和指針域 next ，其存儲

14、的是該結(jié)點邏輯上的后繼結(jié)點的相對地址(即在數(shù)組中的下標)。其存儲空間不發(fā)生變化，而其內(nèi)容可以發(fā)生變化。【答案】錯誤7靜態(tài)鏈表與動態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動?！痉治觥快o態(tài)鏈表是指以數(shù)組方式存儲鏈表的數(shù)據(jù)，對鏈表進行插入和刪除運算時，只 需改變指針，不需移動數(shù)據(jù)。【答案】正確8靜態(tài)鏈表既有順序存儲的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以，它存取表中第i 個元素的時間與 i 無關(guān)?！痉治觥恳驗殪o態(tài)鏈表的存取特性與動態(tài)鏈表是一樣的，只能順序地找到第 i 個元素， 不能隨機地存取第 i 個元素，故其存取表中第 i 個元素的時間與 i 有關(guān)?！敬鸢浮垮e誤9靜態(tài)鏈表中能容納的元素個數(shù)的最大數(shù)在

15、表定義時就確定了，以后不能增加。【分析】因為靜態(tài)鏈表是以數(shù)組方式存儲鏈表的數(shù)據(jù)，數(shù)組空間大小在數(shù)組定義時就已 確定，一般不會發(fā)生變化?！敬鸢浮空_10取線性表的第 i 個元素的時間同 i 的大小有關(guān)?！痉治觥看嫒【€性表中數(shù)據(jù)元素的時間開銷與其存儲結(jié)構(gòu)有關(guān)。順序存儲結(jié)構(gòu)具有按序 號隨機訪問的特點，同 i 的大小無關(guān)?！敬鸢浮垮e誤三、簡答題1如圖 2-11 所示的雙向鏈表中，欲在結(jié)點 s-prior=p-prior;p-prior=s;s-next=p;解答】只能是“ s- prior - next=s; ”而不能為 p- prior - next=s; ”。因為在上面的第二條語句中已經(jīng)改變了結(jié)點

16、p 前插入一個結(jié)點 s，請完成有關(guān)操作。圖 2-11 第 1 題圖p 的前驅(qū)結(jié)點，結(jié)點 p 的前驅(qū)結(jié)點已經(jīng)為 s結(jié)點，而不是操作前的前驅(qū)結(jié)點。在下面的語句順序下，可有兩個答案進行選擇。s-prior=p-prior;p-prior=s;s-next=p;讀者做這種題時，最好予以圖示，不易出錯。2已知線性表非遞減有序，存儲于一個一維數(shù)組A0. n-1 中(表長為 n，設(shè)為全局量)，下面算法的功能是什么void del(DataType A)int i,j;i=1;while (i=n-1)if (Ai!=Ai+1)i+;elsefor (j=(i+2);jnext)q=L;L=L-next;p=

17、L;while (p-next)p=p-next;p-next=Q;q-next=NULL;return L;【解答】算法的功能是把單鏈表的第一個結(jié)點從表頭移到了鏈尾。返回的 L 指向原鏈表 的第二個結(jié)點。 若原鏈表表示的線性表是 ( a1, a2, , an) ，則操作后表示的線性表為 ( a2, a3, , an, a1) 。4試描述頭指針、頭結(jié)點、開始結(jié)點的區(qū)別，并說明頭指針和頭結(jié)點的作用?！窘獯稹款^指針是一個指針變量，里面存放的是鏈表中首結(jié)點的地址，并以此來標識一 個鏈表。如鏈表 H，鏈表 L 等，表示鏈表中第一個結(jié)點的地址存放在H和 L 中。頭結(jié)點是附加在第一個元素結(jié)點之前的一個結(jié)點

18、，頭指針指向頭結(jié)點。當(dāng)該鏈表表示一 個非空的線性表時，頭結(jié)點的指針域指向第一個元素結(jié)點，為空表時，該指針域為空。開始結(jié)點指第一個元素結(jié)點。 頭指針的作用是用來唯一標識一個單鏈表。 頭結(jié)點的作用有兩個：一是使得對空表和非空表的處理得以統(tǒng)一。二是使得在鏈表的第 一個位置上的操作和在其他位置上的操作一致，無需特殊處理。5在單鏈表、雙鏈表和單循環(huán)鏈表中，若僅知道指針p 指向某結(jié)點，而不知道頭指針，能否將結(jié)點 p 從相應(yīng)的鏈表中刪除若可以，其時間復(fù)雜度各為多少【解答】單鏈表：若結(jié)點 p 有后繼結(jié)點，則可將結(jié)點 p的后繼元素數(shù)據(jù)放入結(jié)點 p 中，再將后繼 結(jié)點刪除。時間復(fù)雜度為 O(1) ；若結(jié)點 p 無

19、后繼結(jié)點，則不可以實現(xiàn)。雙鏈表：可以實現(xiàn)，時間復(fù)雜度為 O(1) 。單循環(huán)鏈表：像單鏈表那樣進行操作，也可以從p開始，找結(jié)點 p 的直接前驅(qū)，然后再刪除 p 結(jié)點，時間復(fù)雜度為 O(n) 。四、算法設(shè)計題1設(shè)線性表存放在一維數(shù)組 Aarrsize 的前 num個分量中，且遞增有序。試寫一算法， 將 x 插入到線性表的適當(dāng)位置上，以保持線性表的有序性。并且分析算法的時間復(fù)雜度。【分析】直接用題目中所給定的數(shù)據(jù)結(jié)構(gòu)(順序存儲的思想是用物理上的相鄰表示邏輯 上的相鄰， 不一定要將一維數(shù)組和表示線性表長度的變量封裝成一個結(jié)構(gòu)體) ，因為是順序存 儲，分配的存儲空間是固定大小的，所以首先確定是否還有存儲

20、空間，若有，則根據(jù)原線性 表中元素的有序性確定插入元素的插入位置，后面的元素為它讓出位置(也可以從高下標端 開始一邊比較，一邊移位) ，然后插入 x，最后修改表示表長的變量?！舅惴ā縄nsertSeq(DataType A,int *num,DataType x)/ 設(shè) num為表的最大下標int i;if (*num=arrsize-1)return 0;elsei=*num;while (i=0&Aix)/ 邊找位置邊移動Ai+1=Ai;Ai+1=x;/ 找到的位置是插入位的下一位(*num)+;return 1;時間復(fù)雜度為 O(n) 。s 為指向鏈表中某個結(jié)p及 p的前驅(qū)結(jié)點 q，2假

21、設(shè)在長度大于 1 的單循環(huán)鏈表中，既無頭結(jié)點也無頭指針。 點的指針，試編寫算法刪除結(jié)點 s 的直接前驅(qū)結(jié)點?！痉治觥坷醚h(huán)單鏈表的特點， 通過 s 指針可循環(huán)找到其前驅(qū)結(jié)點 然后可刪除結(jié)點 p?！舅惴ā縱iod delepre(LNode *s)LNode *p,*q;p=s;while (p-next=s)q=p;p=p-next;q-next=s;delete p;3已知兩個單鏈表 A 與 B 分別表示兩個集合，其元素遞增排列，編寫一個函數(shù)求出A和 B 的交集 C，要求 C同樣以元素值遞增的單鏈表形式存儲?！痉治觥拷患傅氖莾蓚€單鏈表的元素值相同的結(jié)點的集合，為了操作方便，先讓單鏈表 C

22、帶有一個頭結(jié)點，最后將其刪除掉。算法中指針p用來指向 A中的當(dāng)前結(jié)點，指針 q 用來指向 B 中的當(dāng)前結(jié)點，將其值進行比較，兩者相等時，屬于交集中的一個元素，兩者不等 時，將其較小者跳過，繼續(xù)后面的比較?！舅惴ā縇inkNode *inter(LinkList A,B) LNode *q,*p,*r,*s,*C;C=new LNode;r=C;p=A;q=B;while (p & q )if (p-datadata) p=p-next;elseif (p-data=q-data) s=new LNode; s-data=p-data; r-next=s;r=s;p=p-next; q=q-ne

23、xt;elseq=q-next; r-next=NULL;r=C-next;delete C;return r;4單鏈表 L 是一個遞減有序表，試編寫一個高效算法，刪除表中值大于min 且小于 max的結(jié)點（若表中有這樣的結(jié)點） ，同時釋放被刪結(jié)點的空間，這里 min 和 max 是兩個給定的 參數(shù)。并分析算法的時間復(fù)雜度?！痉治觥坑捎趩捂湵?L 是一個遞減有序表，即由大到小有序，故可從表頭開始查找第一 個比 max 小的結(jié)點，記住其位置，再接著向后查找第一個不大于 min 的結(jié)點，然后將它們之 間的結(jié)點刪除。算法】LinkList delete(LinkList L,int min,int max) / 設(shè) L 為帶頭結(jié)點的循環(huán)鏈表 LNode *p,*q,*s,*k;if(L-next)p=L-next;s=L;while (p-data