數(shù)據(jù)結(jié)構(gòu)課程課后習(xí)題答案

1、練習(xí)題及參考答案數(shù)據(jù)結(jié)構(gòu)簡明教程練習(xí)題及參考答案練習(xí)題11. 單項(xiàng)選擇題（1）線性結(jié)構(gòu)中數(shù)據(jù)元素之間是（ ）關(guān)系。A.一對多B.多對多C.多對一D.一對一答：D（2）數(shù)據(jù)結(jié)構(gòu)中與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（ ）結(jié)構(gòu)。A.存儲B.物理C.邏輯D.物理和存儲答：C（3）算法分析的目的是（ ）。A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D.分析算法的易懂性和文檔性答：C（4）算法分析的兩個主要方面是（ ）。A.空間復(fù)雜性和時間復(fù)雜性B.正確性和簡明性C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性答：A（5）計(jì)算機(jī)算法指的是（ ）。A.計(jì)算方法B. 排序方法C.

2、求解問題的有限運(yùn)算序列D.調(diào)度方法答：C（6）計(jì)算機(jī)算法必須具備輸入、輸出和（ ）等5個特性。A.可行性、可移植性和可擴(kuò)充性B.可行性、確定性和有窮性C.確定性、有窮性和穩(wěn)定性D.易讀性、穩(wěn)定性和安全性答：B2. 填空題（1）數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 、數(shù)據(jù)的 和數(shù)據(jù)的 這三個方面的內(nèi)容。答：邏輯結(jié)構(gòu) 存儲結(jié)構(gòu) 運(yùn)算（2）數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是 和 。答：線性結(jié)構(gòu) 非線性結(jié)構(gòu)（3）數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R），其中D是 的有限集合，R是D上的 有限集合。答：數(shù)據(jù)元素 關(guān)系（4）在線性結(jié)構(gòu)中，第一個結(jié)點(diǎn) 前驅(qū)結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有1個前驅(qū)結(jié)點(diǎn)；最后一個結(jié)點(diǎn) 后繼結(jié)點(diǎn)，其余每

3、個結(jié)點(diǎn)有且只有1個后繼結(jié)點(diǎn)。答：沒有 沒有（5）在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有 結(jié)點(diǎn)，其余每個結(jié)點(diǎn)有且只有 個前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有 結(jié)點(diǎn)，其余每個結(jié)點(diǎn)的后繼結(jié)點(diǎn)數(shù)可以是 。答：前驅(qū) 1 后繼 任意多個（6）在圖形結(jié)構(gòu)中，每個結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后繼結(jié)點(diǎn)數(shù)可以是（ ）。答：任意多個（7）數(shù)據(jù)的存儲結(jié)構(gòu)主要有四種，它們分別是 、 、 和 存儲結(jié)構(gòu)。答：順序 鏈?zhǔn)?索引 哈希（8）一個算法的效率可分為 效率和 效率。答：時間 空間3. 簡答題（1）數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個概念之間有區(qū)別嗎？答：簡單地說，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素的集合。數(shù)據(jù)類型不僅定義了一組數(shù)據(jù)元素，而且還在其上定義

4、了一組操作。（2）簡述線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)的不同點(diǎn)。答：線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對一的，樹形線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對多的，圖在結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是多對多的。（3）設(shè)有采用二元組表示的數(shù)據(jù)邏輯結(jié)構(gòu)S=(D,R)，其中D=a,b,i，R=(a,b),(a,c),(c,d),(c,f),(f,h),(d,e),(f,g),(h,i)，問相對于關(guān)系R，哪些結(jié)點(diǎn)是開始結(jié)點(diǎn)，哪些結(jié)點(diǎn)是終端結(jié)點(diǎn)？答：該邏輯結(jié)構(gòu)為樹形結(jié)構(gòu)，其中a結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，稱為根結(jié)點(diǎn)，b、e、g、i結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)，是終端結(jié)點(diǎn)，也稱為葉子結(jié)點(diǎn)。（4）以下各函數(shù)是算法中語句的執(zhí)行頻度，n為問題規(guī)模，給出對

5、應(yīng)的時間復(fù)雜度：T1(n)=nlog2n-1000log2nT2(n)=-1000log2nT3(n)=n2-1000log2nT4(n)=2nlog2n-1000log2n答：T1(n)=O(nlog2n)，T2(n)=O( )，T3(n)=O(n2)，T4(n)=O(nlog2n)。（5）分析下面程序段中循環(huán)語句的執(zhí)行次數(shù)。int j=0,s=0,n=100;doj=j+1;s=s+10*j; while (jn & sn);答：j=0，第1次循環(huán)：j=1，s=10。第2次循環(huán)：j=2，s=30。第3次循環(huán)：j=3，s=60。第4次循環(huán)：j=4，s=100。while條件不再滿足。所以，其

6、中循環(huán)語句的執(zhí)行次數(shù)為4。（6）執(zhí)行下面的語句時，語句s+的執(zhí)行次數(shù)為多少？int s=0;for (i=1;i=i;j-)s+;答：語句s的執(zhí)行次數(shù)。（7）設(shè)n為問題規(guī)模，求以下算法的時間復(fù)雜度。void fun1(int n)int x=0,i;for (i=1;i=n;i+)for (j=i+1;j=n;j+)x+;答：其中x+語句屬基本運(yùn)算語句，=O(n2)。（8）設(shè)n為問題規(guī)模，是一個正偶數(shù)，試計(jì)算以下算法結(jié)束時m的值，并給出該算法的時間復(fù)雜度。void fun2(int n)int m=0;for (i=1;i=n;i+)for (j=2*i;j=n;j+)m+;答：由于內(nèi)循環(huán)j的

7、取值范圍，所以in/2，則，該程序段的時間復(fù)雜度為O(n2)。上機(jī)實(shí)驗(yàn)題1有一個整型數(shù)組a，其中含有n個元素，設(shè)計(jì)盡可能好的算法求其中的最大元素和次大元素，并采用相關(guān)數(shù)據(jù)測試。解：maxs算法用于返回?cái)?shù)組a0.n-1中的最大元素值max1和次大元素值max2，max1和max2設(shè)計(jì)為引用類型。對應(yīng)的程序如下：#include void maxs(int a,int n,int &max1,int &max2)int i;max1=max2=a0;for (i=1;imax1)max2=max1;max1=ai;else if (aimax2)max2=ai;void main()int a=1

8、,4,10,6,8,3,5,7,9,2;int n=10;int max1,max2;maxs(a,n,max1,max2);printf(最大元素值=%d,次大元素值=%dn,max1,max2);練習(xí)題21. 單項(xiàng)選擇題（1）數(shù)據(jù)在計(jì)算機(jī)存儲器內(nèi)表示時，物理地址與邏輯地址相對順序相同并且是連續(xù)的，稱之為（ ）。A.存儲結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.順序存儲結(jié)構(gòu)D.鏈?zhǔn)酱鎯Y(jié)構(gòu)答：C（2）在n個結(jié)點(diǎn)的順序表中，算法的時間復(fù)雜度是O（1）的操作是（ ）。A.訪問第i個結(jié)點(diǎn)（1in）和求第i（2in）個結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)B.在第i（1in）個結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)C.刪除第i個結(jié)點(diǎn)（1in）D.將n個結(jié)點(diǎn)從小到

9、大排序答：A（3） 向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動（ ）個元素。A.8B.63.5C.63D.7答：B（4）鏈?zhǔn)酱鎯Y(jié)構(gòu)所占存儲空間（ ）。A.分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針B.只有一部分，存放結(jié)點(diǎn)值C.只有一部分，存儲表示結(jié)點(diǎn)間關(guān)系的指針D.分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)答：A（5）線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（ ）。A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)或不連續(xù)都可以答：D（6）一個線性表在（ ）情況下適用于采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。A.需經(jīng)常修

10、改其中的結(jié)點(diǎn)值B.需不斷對其進(jìn)行刪除插入C.其中含有大量的結(jié)點(diǎn)D.其中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜答：B（7）單鏈表的存儲密度（ ）A.大于1B.等于1C.小于1D.不能確定答：C2. 填空題（1）在順序表中插入或刪除一個元素時，需要平均移動（ ）元素，具體移動的元素個數(shù)與（ ）有關(guān)。答：表中一半 表長和該元素在表中的位置（2）向一個長度為n的順序表的第i個元素（1in+1）之前插入一個元素時，需向后移動（ ）個元素。答：n-i+1（3）向一個長度為n的順序表中刪除第i個元素（1in）時，需向前移動（ ）個元素。答：n-i（4）在順序表中訪問任意一個元素的時間復(fù)雜度均為（ ），因此順序表也稱為（ ）的數(shù)據(jù)結(jié)構(gòu)

11、。答：O(1) 隨機(jī)存?。?）順序表中邏輯上相鄰的元素的物理位置（ ）相鄰。單鏈表中邏輯上相鄰的元素的物理位置（ ）相鄰。答：一定 不一定（6）在帶頭結(jié)點(diǎn)的單鏈表中，除頭結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲位置由（ ）指示。答：其前驅(qū)結(jié)點(diǎn)的鏈域的值（7）在含有n個數(shù)據(jù)結(jié)點(diǎn)的單鏈表中要刪除已知結(jié)點(diǎn)*p，需找到它的（ ），其時間復(fù)雜度為（ ）。答：前驅(qū)結(jié)點(diǎn)的地址 O(n)（8）含有n（n1）個結(jié)點(diǎn)的循環(huán)雙向鏈表中，為空的指針域數(shù)為（ ）。答：03. 簡答題（1）試比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點(diǎn)。在什么情況下用順序表比鏈表好？答：順序存儲結(jié)構(gòu)中，相鄰數(shù)據(jù)元素的存放地址也相鄰，并要求內(nèi)存中可用存儲單元的地址

12、必須是連續(xù)的。其優(yōu)點(diǎn)是存儲密度大，存儲空間利用率高；缺點(diǎn)是插入或刪除元素時不方便。鏈?zhǔn)酱鎯Y(jié)構(gòu)中，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針。其優(yōu)點(diǎn)是插入或刪除元素時很方便，使用靈活；缺點(diǎn)是存儲密度小，存儲空間利用率低。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。（2）對于表長為n的順序表，在任何位置上插入或刪除一個元素的概率相等時，插入一個元素所需要移動的元素的平均個數(shù)為多少？刪除一個元素

13、所需要移動的平均個數(shù)為多少？答：插入一個元素所需要移動的元素的平均個數(shù)為(n-1)/2，刪除一個元素所需要移動的平均個數(shù)為n/2。（3）在鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么？答：在鏈表中設(shè)置頭結(jié)點(diǎn)后，不管鏈表是否為空表，頭結(jié)點(diǎn)指針均不空，并使得對鏈表的操作（如插入和刪除）在各種情況下統(tǒng)一，從而簡化了算法的實(shí)現(xiàn)過程。（4）對于雙鏈表和單鏈表，在兩個結(jié)點(diǎn)之間插入一個新結(jié)點(diǎn)時需修改的指針各為多少個？答：對于雙鏈表，在兩個結(jié)點(diǎn)之間插入一個新結(jié)點(diǎn)時，需修改前驅(qū)結(jié)點(diǎn)的next域、后繼結(jié)點(diǎn)的prior域和新插入結(jié)點(diǎn)的next、prior域。所以共修改4個指針。對于單鏈表，在兩個結(jié)點(diǎn)之間插入一個新結(jié)點(diǎn)時，需修改前一

14、結(jié)點(diǎn)的next域，新插入結(jié)點(diǎn)的next域。所以共修改兩個指針。（5）某含有n（n1）結(jié)點(diǎn)的線性表中，最常用的操作是在尾結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)和刪除第一個結(jié)點(diǎn)，則采用以下哪種存儲方式最節(jié)省運(yùn)算時間。單鏈表；僅有頭指針不帶頭結(jié)點(diǎn)的循環(huán)單鏈表；雙鏈表；僅有尾指針的循環(huán)單鏈表。答：在單鏈表中，刪除第一個結(jié)點(diǎn)的時間復(fù)雜度為O(1)。插入結(jié)點(diǎn)需找到前驅(qū)結(jié)點(diǎn)，所以在尾結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)，需找到尾結(jié)點(diǎn)，對應(yīng)的時間復(fù)雜度為O(n)。在僅有頭指針不帶頭結(jié)點(diǎn)的循環(huán)單鏈表中，刪除第一個結(jié)點(diǎn)的時間復(fù)雜度O(n)，因?yàn)閯h除第一個結(jié)點(diǎn)后還要將其改為循環(huán)單鏈表；在尾結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)的時間復(fù)雜度也為O(n)。在雙鏈表中，刪

15、除第一個結(jié)點(diǎn)的時間復(fù)雜度為O(1)；在尾結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)，也需找到尾結(jié)點(diǎn)，對應(yīng)的時間復(fù)雜度為O(n)。在僅有尾指針的循環(huán)單鏈表中，通過該尾指針可以直接找到第一個結(jié)點(diǎn)，所以刪除第一個結(jié)點(diǎn)的時間復(fù)雜度為O(1)；在尾結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)也就是在尾指針?biāo)附Y(jié)點(diǎn)之后插入一個結(jié)點(diǎn)，時間復(fù)雜度也為O(1)。因此最節(jié)省運(yùn)算時間。4. 算法設(shè)計(jì)題（1）設(shè)計(jì)一個高效算法，將順序表的所有元素逆置，要求算法空間復(fù)雜度為O(1)。解：遍歷順序表L的前半部分元素，對于元素L.datai（0iL.length/2），將其與后半部分對應(yīng)元素L.dataL.length-i-1進(jìn)行交換。對應(yīng)的算法如下：void reve

16、rse(SqList &L)int i;ElemType x;for (i=0;iL.length/2;i+)x=L.datai;/L.datai與L.dataL.length-i-1交換L.datai=L.dataL.length-i-1;L.dataL.length-i-1=x;本算法的時間復(fù)雜度為O(n)。（2）設(shè)計(jì)一個算法從順序表中刪除重復(fù)的元素，并使剩余元素間的相對次序保持不變。解：對于順序表L，用i從1開始遍歷其元素，設(shè)L.data0.j（j的初值為0）中沒有重復(fù)的元素。檢測L.datai（jiL.length），若L.datai和L.data0.j中任何一個元素都不相同，則將L.

17、datai存入L.dataj+1中。對應(yīng)的算法如下：void delsame(SqList &L)/L為引用型參數(shù)int i,j=0,k;for (i=1;iL.length;i+)k=0;while (kj)/表示L.datai和L.data0.j中所有元素都不相同j+;L.dataj=L.datai;L.length=j+1;/順序表長度置新值本算法的時間復(fù)雜度為O(n2)，空間復(fù)雜度為O(1)。（3）設(shè)計(jì)一個算法從有序順序表中刪除重復(fù)的元素，并使剩余元素間的相對次序保持不變。解：在有序順序表L中，所有重復(fù)的元素應(yīng)是相鄰存放的，用k保存不重復(fù)出現(xiàn)的元素個數(shù)，先將不重復(fù)的有序區(qū)看成是L.da

18、ta0.0，置e=L.data0，用i從1開始遍歷L的所有元素：當(dāng)L.dataie時，將它放在L.datak中，k增1，置e=L.datai，最后將L的length置為k。對應(yīng)的算法如下：void delsame1(SqList &L)/L為引用型參數(shù)int i,k=1;/k保存不重復(fù)的元素個數(shù)ElemType e;e=L.data0;for (i=1;inext;/p指向*q的前驅(qū)結(jié)點(diǎn)while (q!=NULL & q-data!=x)p=q;q=q-next;if (q!=NULL)/找到值為x的結(jié)點(diǎn)p-next=q-next;free(q);return 1;else return 0

19、;/未找到值為x的結(jié)點(diǎn)（5）設(shè)計(jì)一個算法判定單鏈表L是否是遞增的。解：判定鏈表L從第2個結(jié)點(diǎn)開始的每個結(jié)點(diǎn)的值是否比其前驅(qū)的值大。若有一個不成立，則整個鏈表便不是遞增的；否則是遞增的。對應(yīng)的算法如下：int increase(SLink *L)SLink *pre=L-next,*p;/pre指向第一個數(shù)據(jù)結(jié)點(diǎn)p=pre-next;/p指向*pre結(jié)點(diǎn)的后繼結(jié)點(diǎn)while (p!=NULL)if (p-data=pre-data)/若正序則繼續(xù)判斷下一個結(jié)點(diǎn)pre=p;/pre、p同步后移p=p-next;else return 0;return 1;（6）有一個整數(shù)元素建立的單鏈表A，設(shè)計(jì)一

20、個算法，將其拆分成兩個單鏈表A和B，使得A單鏈表中含有所有的偶數(shù)結(jié)點(diǎn)，B單鏈表中所有的奇數(shù)結(jié)點(diǎn)，且保持原來的相對次序。解：采用重新單鏈表的方法，由于要保持相對次序，所以采用尾插法建立新表A、B。用p遍歷原單鏈表A的所有數(shù)據(jù)結(jié)點(diǎn)，若為偶數(shù)結(jié)點(diǎn)，將其鏈到A中，若為奇數(shù)結(jié)點(diǎn)，將其鏈到B中。對應(yīng)的算法如下：void Split(SLink *&A,SLink *&B)SLink *p=A-next,*ra,*rb;ra=A;B=(SLink *)malloc(sizeof(SLink);/建立頭結(jié)點(diǎn)rb=B;/r總是指向B鏈表的尾結(jié)點(diǎn)while (p!=NULL)if (p-data%2=0)/偶數(shù)結(jié)

21、點(diǎn)ra-next=p;/將*p結(jié)點(diǎn)鏈到A中ra=p;p=p-next;else/奇數(shù)結(jié)點(diǎn)rb-next=p;/將*p結(jié)點(diǎn)鏈到B中rb=p;p=p-next;ra-next=rb-next=NULL;本算法的時間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。（7）有一個有序單鏈表（從小到大排列），表頭指針為L，設(shè)計(jì)一個算法向該單鏈表中插入一個元素為x的結(jié)點(diǎn)，使插入后該鏈表仍然有序。解：先建立一個待插入的結(jié)點(diǎn)，然后依次與鏈表中的各結(jié)點(diǎn)的數(shù)據(jù)域比較大小，找到插入該結(jié)點(diǎn)的位置，最后插入該結(jié)點(diǎn)。對應(yīng)的算法如下：void inorderList(SLink *&L,ElemType x)SLink *s,*p,

22、*q;s=(SLink *)malloc(sizeof(SLink); /建立一個待插入的結(jié)點(diǎn)s-data=x;s-next=NULL;if (L=NULL | xdata)/若單鏈表為空或x小于第1個結(jié)點(diǎn)date域s-next=L;/把*s結(jié)點(diǎn)插入到頭結(jié)點(diǎn)之后L=s;elseq=L;/尋找插入位置,p指向待比較的結(jié)點(diǎn),q指向p的前驅(qū)結(jié)點(diǎn)p=q-next;while (p!=NULL & xp-data)/若x小于p所指結(jié)點(diǎn)的data域值if (xp-data) q=p;p=p-next;s-next=p;/將s結(jié)點(diǎn)插入到*q和*p之間q-next=s;（8）有一個單鏈表L，其中可能出現(xiàn)值域重

23、復(fù)的結(jié)點(diǎn)，設(shè)計(jì)一個算法刪除值域重復(fù)的結(jié)點(diǎn)。并分析算法的時間復(fù)雜度。解：用p遍歷單鏈表，用r遍歷*p結(jié)點(diǎn)之后的結(jié)點(diǎn)，q始終指向*r結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若r-data=p-data，則刪除*r結(jié)點(diǎn)，否則q、r同步后移一個結(jié)點(diǎn)。對應(yīng)的算法如下：void dels1(SLink *&L)SLink *p=L-next,*q,*r,*t;while (p!=NULL)q=p;r=q-next;while (r!=NULL)if (r-data=p-data)/r指向被刪結(jié)點(diǎn)t=r-next;q-next=t;free(r);r=t;elseq=r;r=r-next;p=p-next;本算法的時間復(fù)雜度為

24、O(n2)。（9）有一個遞增有序單鏈表（允許出現(xiàn)值域重復(fù)的結(jié)點(diǎn)），設(shè)計(jì)一個算法刪除值域重復(fù)的結(jié)點(diǎn)。并分析算法的時間復(fù)雜度。解：由于是有序表，所以相同值域的結(jié)點(diǎn)都是相鄰的。用p遍歷遞增單鏈表，若*p結(jié)點(diǎn)的值域等于其后結(jié)點(diǎn)的值域，則刪除后者。對應(yīng)的算法如下：void dels(SLink *&L)SLink *p=L-next,*q;while (p-next!=NULL) if (p-data=p-next-data) /找到重復(fù)值的結(jié)點(diǎn)q=p-next;/q指向這個重復(fù)值的結(jié)點(diǎn)p-next=q-next;/刪除*q結(jié)點(diǎn)free(q);else p=p-next;本算法的時間復(fù)雜度為O(n)。（

25、10）有一個雙鏈表L，設(shè)計(jì)一個算法查找第一個元素值為x的結(jié)點(diǎn)，將其與后繼結(jié)點(diǎn)進(jìn)行交換。解：先找到第一個元素值為x的結(jié)點(diǎn)*p，q指向其后繼結(jié)點(diǎn)，本題是將*p結(jié)點(diǎn)移到*q結(jié)點(diǎn)之后，實(shí)現(xiàn)過程是：刪除*p結(jié)點(diǎn)，再將其插入到*q結(jié)點(diǎn)之后。對應(yīng)的算法如下：int swap(DLink *L,ElemType x)DLink *p=L-next,*q;while (p!=NULL & p-data!=x)p=p-next;if (p=NULL)/未找到值為x的結(jié)點(diǎn)return 0;else/找到值為x的結(jié)點(diǎn)*pq=p-next;/q指向*p的后繼結(jié)點(diǎn)if (q!=NULL)/*p結(jié)點(diǎn)不是尾結(jié)點(diǎn)p-prior

26、-next=q;/先刪除*p結(jié)點(diǎn)q-prior=p-prior;p-next=q-next;/將*p結(jié)點(diǎn)插入到*q結(jié)點(diǎn)之后if (q-next!=NULL)q-next-prior=p;q-next=p;p-prior=q;return 1;else/*p結(jié)點(diǎn)是尾結(jié)點(diǎn)return 0;/無法與后繼結(jié)點(diǎn)交換，返回0（11）對于有n（n1）個數(shù)據(jù)結(jié)點(diǎn)的循環(huán)單鏈表L，設(shè)計(jì)一個算法將所有結(jié)點(diǎn)逆置。解：采用頭插法重建循環(huán)單鏈表L的思路，先建立一個空的循環(huán)單鏈表，用p遍歷所有數(shù)據(jù)結(jié)點(diǎn)，每次將*p結(jié)點(diǎn)插入到前端。對應(yīng)的算法如下：void Reverse(SLink *&L)SLink *p=L-next,*

27、q;L-next=L;/建立一個空循環(huán)單鏈表while (p!=L)q=p-next;p-next=L-next;/將*p結(jié)點(diǎn)插入到前端L-next=p;p=q;上機(jī)實(shí)驗(yàn)題2有兩個整數(shù)集合采用有序單鏈表存儲，設(shè)計(jì)盡可能高效的算法求兩個集合的并集、交集和差集。并用相關(guān)數(shù)據(jù)進(jìn)行測試。#include #include SLink.hvoid Union(SLink *L1,SLink *L2,SLink *&L3)/求并集SLink *p,*q,*s,*tc;L3=(SLink *)malloc(sizeof(SLink);tc=L3;p=L1-next;q=L2-next;while (p!=N

28、ULL & q!=NULL)if (p-datadata)s=(SLink *)malloc(sizeof(SLink);s-data=p-data;tc-next=s;tc=s;p=p-next;else if (p-dataq-data)s=(SLink *)malloc(sizeof(SLink);s-data=q-data;tc-next=s;tc=s;q=q-next;elses=(SLink *)malloc(sizeof(SLink);s-data=p-data;tc-next=s;tc=s;p=p-next;q=q-next;while (p!=NULL)s=(SLink *)

29、malloc(sizeof(SLink);s-data=p-data;tc-next=s;tc=s;p=p-next;while (q!=NULL)s=(SLink *)malloc(sizeof(SLink);s-data=q-data;tc-next=s;tc=s;q=q-next;tc-next=NULL;void InterSection(SLink *L1,SLink *L2,SLink *&L3)/求交集SLink *p,*q,*s,*tc;L3=(SLink *)malloc(sizeof(SLink);tc=L3;p=L1-next;q=L2-next;while (p!=NU

30、LL & q!=NULL)if (p-datadata)p=p-next;else if (p-dataq-data)q=q-next;else/p-data=q-datas=(SLink *)malloc(sizeof(SLink);s-data=p-data;tc-next=s;tc=s;p=p-next;q=q-next;tc-next=NULL;void Subs(SLink *L1,SLink *L2,SLink *&L3)/求差集SLink *p,*q,*s,*tc;L3=(SLink *)malloc(sizeof(SLink);tc=L3;p=L1-next;q=L2-next

31、;while (p!=NULL & q!=NULL)if (p-datadata)s=(SLink *)malloc(sizeof(SLink);s-data=p-data;tc-next=s;tc=s;p=p-next;else if (p-dataq-data)q=q-next;else/p-data=q-datap=p-next;q=q-next;while (p!=NULL)s=(SLink *)malloc(sizeof(SLink);s-data=p-data;tc-next=s;tc=s;p=p-next;tc-next=NULL;void main()SLink *A,*B,*

32、C,*D,*E;ElemType a=1,3,6,8,10,20;CreateListR(A,a,6);/尾插法建表printf(集合A:);DispList(A);ElemType b=2,5,6,10,16,20,30;CreateListR(B,b,7);/尾插法建表printf(集合B:);DispList(B);printf(求A、B并集Cn);Union(A,B,C);/求A、B并集Cprintf(集合C:);DispList(C);printf(求A、B交集Cn);InterSection(A,B,D);/求A、B并集Dprintf(集合D:);DispList(D);print

33、f(求A、B差集En);Subs(A,B,E);/求A、B差集Eprintf(集合E:);DispList(E);DestroyList(A);DestroyList(B);DestroyList(C);DestroyList(D);DestroyList(E);練習(xí)題31. 單項(xiàng)選擇題（1）棧中元素的進(jìn)出原則是（ ）。A.先進(jìn)先出B.后進(jìn)先出C.?？談t進(jìn)D.棧滿則出答：B（2）設(shè)一個棧的進(jìn)棧序列是A、B、C、D（即元素AD依次通過該棧），則借助該棧所得到的輸出序列不可能是（ ）。A.A,B,C,DB.D,C,B,AC.A,C,D,BD.D,A,B,C答：D（3）一個棧的進(jìn)棧序列是a、b、c、

34、d、e，則棧的不可能的輸出序列是（ ）。A.edcbaB.decbaC.dceabD.abcde答：C（4）已知一個棧的進(jìn)棧序列是1，2，3，n，其輸出序列的第一個元素是i（1in）則第j（1jn）個出棧元素是（ ）。A.iB.n-iC.j-i+1D.不確定答：D（5）設(shè)順序棧st的棧頂指針top的初始時為-1，?？臻g大小為MaxSize，則判定st棧為?？盏臈l件為（ ）。A.st.top=-1B.st.top!=-1C.st.top!=MaxSize D.st.top=MaxSize答：A（6）設(shè)順序棧st的棧頂指針top的初始時為-1，?？臻g大小為MaxSize，則判定st棧為棧滿的條件是

35、 。A.st.top!=-1B.st.top=-1C.st.top!=MaxSize-1D.st.top=MaxSize-1答：D（7）隊(duì)列中元素的進(jìn)出原則是（ ）。A.先進(jìn)先出B.后進(jìn)先出C.?？談t進(jìn)D.棧滿則出答：A（8）元素A、B、C、D順序連續(xù)進(jìn)入隊(duì)列qu后，隊(duì)頭元素是（ ），隊(duì)尾元素是（ ）。A.AB.BC.CD.D答：A D。（9）一個隊(duì)列的入列序列為1234，則隊(duì)列可能的輸出序列是（ ）。A.4321B.1234C.1432D.3241答：B（10）循環(huán)隊(duì)列qu（隊(duì)頭指針front指向隊(duì)首元素的前一位置，隊(duì)尾指針rear指向隊(duì)尾元素的位置）的隊(duì)滿條件是（ ）。A. (qu.rea

36、r+1)%MaxSize=(qu.front+1)%MaxSizeB. (qu.rear+1)%MaxSize=qu.front+1C.(qu.rear+1)%MaxSize=qu.frontA.qu.rear=qu.front答：C（11）循環(huán)隊(duì)列qu（隊(duì)頭指針front指向隊(duì)首元素的前一位置，隊(duì)尾指針rear指向隊(duì)尾元素的位置）的隊(duì)空條件是（ ）。A. (qu.rear+1)%MaxSize=(qu.front+1)%MaxSizeB. (qu.rear+1)%MaxSize=qu.front+1C.(qu.rear+1)%MaxSize=qu.frontD.qu.rear=qu.fron

37、t答：D（12）設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)是0N-1，其頭尾指針分別為f和r（隊(duì)頭指針f指向隊(duì)首元素的前一位置，隊(duì)尾指針r指向隊(duì)尾元素的位置），則其元素個數(shù)為（ ）。A.r-fB.r-f-1C.(r-f)N+1D.(r-f+N)N答：D（13）設(shè)有4個數(shù)據(jù)元素a、b、c和d，對其分別進(jìn)行棧操作或隊(duì)操作。在進(jìn)?；蜻M(jìn)隊(duì)操作時，按a、b、c、d次序每次進(jìn)入一個元素。假設(shè)?；蜿?duì)的初始狀態(tài)都是空。現(xiàn)要進(jìn)行的棧操作是進(jìn)棧兩次，出棧一次，再進(jìn)棧兩次，出棧一次；這時，第一次出棧得到的元素是（ ），第二次出棧得到的元素是（ ）；類似地，考慮對這4個數(shù)據(jù)元素進(jìn)行的隊(duì)操作是進(jìn)隊(duì)兩次，出隊(duì)一次，再進(jìn)隊(duì)兩次，出隊(duì)一次；這時

38、，第一次出隊(duì)得到的元素是（ ），第二次出隊(duì)得到的元素是（ ）。經(jīng)操作后，最后在棧中或隊(duì)中的元素還有（ ）個。：A.aB.bC.cD.d：A.1B.2C.3D.0答：B D A B B（14）設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1e6依次通過棧S，一個元素出后即進(jìn)隊(duì)列Q，若6個元素出隊(duì)的序列是e2、e4、e3、e6、e5、e1，則棧S的容量至少應(yīng)該是（ ）。A.5B.4C.3D.2答：C2. 填空題（1）棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為（ ）。不允許插入和刪除運(yùn)算的一端稱為（ ）。答：棧頂 棧底（2）一個棧的輸入序列是12345，的輸出序列為12345，其進(jìn)棧出棧的操作為（ ）

39、。答：1進(jìn)棧，1出棧，2進(jìn)棧，2出棧，3進(jìn)棧，3出棧，4進(jìn)棧，4出棧，5進(jìn)棧，5出棧。（3）有5個元素，其進(jìn)棧次序?yàn)锳、B、C、D、E，在各種可能的出棧次序中，以元素C、D最先出棧（即C第一個且D第二個出棧）的次序有（ ）。答：CDBAE、CDEBA、CDBEA。（4）順序棧用data0.n-1存儲數(shù)據(jù)，棧頂指針為top，其初始值為0，則元素x進(jìn)棧的操作是（ ）。答：datatop=x; top+;（5）順序棧用data0.n-1存儲數(shù)據(jù)，棧頂指針為top，其初始值為0，則出棧元素x的操作是（ ）。答：top-; x=datatop;（6）（ ）是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一

40、端進(jìn)行刪除運(yùn)算的線性表。答：隊(duì)列（7）設(shè)有數(shù)組A0.m作為循環(huán)隊(duì)列的存儲空間，front為隊(duì)頭指針（它指向隊(duì)首元素的前一位置），rear為隊(duì)尾指針（它指向隊(duì)尾元素的位置），則元素x執(zhí)行入隊(duì)的操作是（ ）。答：rear=(rear+1)%(m+1); Arear=x;（8）設(shè)有數(shù)組A0.m作為循環(huán)隊(duì)列的存儲空間，front為隊(duì)頭指針（它指向隊(duì)首元素的前一位置），rear為隊(duì)尾指針（它指向隊(duì)尾元素的位置），則元素出隊(duì)并保存到x中的操作是（ ）。答：front=(front+1)%(m+1); x=Arear;3. 簡答題（1）簡要說明線性表、棧與隊(duì)的異同點(diǎn)。答：相同點(diǎn)：都屬地線性結(jié)構(gòu)，都可以用順序

41、存儲或鏈表存儲；棧和隊(duì)列是兩種特殊的線性表，即受限的線性表，只是對插入、刪除運(yùn)算加以限制。不同點(diǎn)：運(yùn)算規(guī)則不同，線性表為隨機(jī)存取，而棧是只允許在一端進(jìn)行插入、刪除運(yùn)算，因而是后進(jìn)先出表LIFO；隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表FIFO。用途不同，棧用于子程調(diào)用和保護(hù)現(xiàn)場等，隊(duì)列用于多道作業(yè)處理、指令寄存及其他運(yùn)算等等。（2）順序隊(duì)的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊(duì)列是空還是滿？答：一般的一維數(shù)組隊(duì)列的尾指針已經(jīng)到了數(shù)組的上界，不能再有進(jìn)隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫“假溢出”。采用循環(huán)隊(duì)列是解決假溢出的途徑。另外，解決循環(huán)隊(duì)列是空還是滿的辦法如下：

42、 設(shè)置一個布爾變量以區(qū)別隊(duì)滿還是隊(duì)空； 浪費(fèi)一個元素的空間，用于區(qū)別隊(duì)滿還是隊(duì)空。 使用一個計(jì)數(shù)器記錄隊(duì)列中元素個數(shù)（即隊(duì)列長度）。通常采用法，讓隊(duì)頭指針front指向隊(duì)首元素的前一位置，隊(duì)尾指針rear指向隊(duì)尾元素的位置，這樣判斷循環(huán)隊(duì)列隊(duì)空標(biāo)志是：front=rear，隊(duì)滿標(biāo)志是：(rear+1)%MaxSize=front。4. 算法設(shè)計(jì)題（1）假設(shè)采用順序棧存儲結(jié)構(gòu)，設(shè)計(jì)一個算法，利用棧的基本運(yùn)算返回指定棧中棧底元素，要求仍保持棧中元素不變。這里只能使用棧st的基本運(yùn)算來完成，不能直接用st.data0來得到棧底元素。解：假定采用順序棧結(jié)構(gòu)。先退棧st中所有元素，利用一個臨時棧tmps

43、t存放從st棧中退棧的元素，最后的一個元素即為所求，然后將臨時棧tmpst中的元素逐一出棧并進(jìn)棧到st中，這樣恢復(fù)st棧中原來的元素。對應(yīng)算法如下：int GetBottom(SqStack st,ElemType &x)ElemType e;SqStack tmpst;/定義臨時棧InitStack(tmpst);/初始化臨時棧if (StackEmpty(st)/空棧返回0return 0;while (!StackEmpty(st)/臨時棧tmpst中包含st棧中逆轉(zhuǎn)元素Pop(st,x);Push(tmpst,x);while (!StackEmpty(tmpst)/恢復(fù)st棧中原來的

44、內(nèi)容Pop(tmpst,e);Push(st,e);return 1;/返回1表示成功（2）設(shè)計(jì)一個算法，采用一個順序棧逆向輸出單鏈表L中所有元素。解：本題并不需要改變單鏈表L的結(jié)構(gòu)。設(shè)置一個順序棧st，先遍歷單鏈表并將所有元素進(jìn)棧，然后棧不空循環(huán)并輸出棧中所有元素。對應(yīng)算法如下：void ReverseDisp(SLink *L)ElemType x;struct nodeElemType dataMaxSize;int top; st;/定義一個順序棧st.top=-1;SLink *p=L-next;while (p!=NULL)/遍歷單鏈表，將所有元素進(jìn)棧st.top+;st.data

45、st.top=p-data;p=p-next;while (st.top!=-1)/棧不空循環(huán)，輸出棧中所有元素x=st.datast.top;st.top-;printf(%d ,x);printf(n);（3）設(shè)計(jì)一個循環(huán)隊(duì)列，用front和rear分別作為隊(duì)頭和隊(duì)尾指針，另外用一個標(biāo)志tag標(biāo)識隊(duì)列可能空（0）或可能滿（1），這樣加上front=rear可以作為隊(duì)空或隊(duì)滿的條件。要求設(shè)計(jì)隊(duì)列的相關(guān)基本運(yùn)算算法。解：設(shè)計(jì)的隊(duì)列的類型如下：typedef struct ElemType dataMaxSize;int front,rear;/隊(duì)頭和隊(duì)尾指針int tag;/為0表示隊(duì)空,為1

46、時表示不空 QueueType;初始時tag=0，進(jìn)行成功的插入操作后tag=1，進(jìn)行成功的刪除操作后tag=0；因?yàn)橹挥性诓迦氩僮骱箨?duì)列才有可能滿，只有在刪除操作后隊(duì)列才有可能空，因此，這樣的隊(duì)列的基本要素如下：初始時：tag=0，front=rear隊(duì)空條件：qu.front=qu.rear & qu.tag=0隊(duì)滿條件：qu.front=qu.rear & qu.tag=1對應(yīng)的算法如下：/-初始化隊(duì)列算法-void InitQueue1(QueueType &qu)qu.front=qu.rear=0;qu.tag=0;/為0表示隊(duì)空可能為空/-判隊(duì)空算法-int QueueEmpty

47、1(QueueType qu)return(qu.front=qu.rear & qu.tag=0);/-判隊(duì)滿算法-int QueueFull1(QueueType qu) return(qu.tag=1 & qu.front=qu.rear);/-進(jìn)隊(duì)算法-int enQueue1(QueueType &qu,ElemType x)if (QueueFull1(qu)=1)/隊(duì)滿return 0;qu.rear=(qu.rear+1)%MaxSize;qu.dataqu.rear=x;qu.tag=1;/至少有一個元素,可能滿return 1;/-出隊(duì)算法-int deQueue1(QueueType &qu,ElemType &x)/出隊(duì)if (QueueEmpty1(qu)=1)/隊(duì)空return 0;qu.front=(qu.front+1)%MaxSize;x=qu.dataqu.front;qu.tag=0;/出隊(duì)一個元素,可能空return 1;（4）假設(shè)用一個循環(huán)單鏈表表示隊(duì)列，并且只設(shè)一個指針rear指向隊(duì)尾結(jié)點(diǎn)，但不設(shè)頭指針，設(shè)計(jì)出相應(yīng)的隊(duì)初始化、進(jìn)隊(duì)、出隊(duì)和判隊(duì)空的算法。解：假設(shè)鏈隊(duì)是不帶頭結(jié)點(diǎn)的循環(huán)單鏈表，其示意