【正文】 練習(xí)題及參考答案《數(shù)據(jù)結(jié)構(gòu)簡明教程》練習(xí)題及參考答案練習(xí)題11. 單項(xiàng)選擇題（1）線性結(jié)構(gòu)中數(shù)據(jù)元素之間是（ ）關(guān)系。 答：D（2）數(shù)據(jù)結(jié)構(gòu)中與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的（ ）結(jié)構(gòu)。 答：C（3）算法分析的目的是（ ）。 答：C（4）算法分析的兩個主要方面是（ ）。 答：A（5）計算機(jī)算法指的是（ ）。 B. 排序方法 答：C（6）計算機(jī)算法必須具備輸入、輸出和（ ）等5個特性。、可移植性和可擴(kuò)充性 、確定性和有窮性、有窮性和穩(wěn)定性 、穩(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)，其余每個結(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ù)元素，而且還在其上定義了一組操作。（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ī)模，給出對應(yīng)的時間復(fù)雜度：T1(n)=nlog2n1000log2nT2(n)=1000log2nT3(n)=n21000log2nT4(n)=2nlog2n1000log2n答：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。do{ j=j+1。 s=s+10*j。} while (jn amp。amp。 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條件不再滿足。所以，其中循環(huán)語句的執(zhí)行次數(shù)為4。（6）執(zhí)行下面的語句時，語句s++的執(zhí)行次數(shù)為多少？int s=0。for (i=1。in1。i++) for (j=n。j=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ù)，試計算以下算法結(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的取值范圍，所以i≤n/2，則，該程序段的時間復(fù)雜度為O(n2)。上機(jī)實(shí)驗(yàn)題1有一個整型數(shù)組a，其中含有n個元素，設(shè)計盡可能好的算法求其中的最大元素和次大元素，并采用相關(guān)數(shù)據(jù)測試。解：maxs算法用于返回數(shù)組a[0..n1]中的最大元素值max1和次大元素值max2，max1和max2設(shè)計為引用類型。對應(yīng)的程序如下：include void maxs(int a[],int n,int amp。max1,int amp。max2){ int i。 max1=max2=a[0]。 for (i=1。in。i++) if (a[i]max1) { max2=max1。 max1=a[i]。 } else if (a[i]max2) max2=a[i]。}void main(){ int a[]={1,4,10,6,8,3,5,7,9,2}。 int n=10。 int max1,max2。 maxs(a,n,max1,max2)。 printf(最大元素值=%d,次大元素值=%d\n,max1,max2)。}練習(xí)題21. 單項(xiàng)選擇題（1）數(shù)據(jù)在計算機(jī)存儲器內(nèi)表示時，物理地址與邏輯地址相對順序相同并且是連續(xù)的，稱之為（ ）。 答：C（2）在n個結(jié)點(diǎn)的順序表中，算法的時間復(fù)雜度是O（1）的操作是（ ）。（1≤i≤n）和求第i（2≤i≤n）個結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)（1≤i≤n）個結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)（1≤i≤n）答：A（3） 向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動（ ）個元素。 答：B（4）鏈?zhǔn)酱鎯Y(jié)構(gòu)所占存儲空間（ ）。，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針，存放結(jié)點(diǎn)值，存儲表示結(jié)點(diǎn)間關(guān)系的指針，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)答：A（5）線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（ ）。 答：D（6）一個線性表在（ ）情況下適用于采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。 答：B（7）單鏈表的存儲密度（ ） 答：C2. 填空題（1）在順序表中插入或刪除一個元素時，需要平均移動（ ① ）元素，具體移動的元素個數(shù)與（ ② ）有關(guān)。答：①表中一半 ②表長和該元素在表中的位置（2）向一個長度為n的順序表的第i個元素（1≤i≤n+1）之前插入一個元素時，需向后移動（ ）個元素。答：ni+1（3）向一個長度為n的順序表中刪除第i個元素（1≤i≤n）時，需向前移動（ ）個元素。答：ni（4）在順序表中訪問任意一個元素的時間復(fù)雜度均為（ ① ），因此順序表也稱為（ ② ）的數(shù)據(jù)結(jié)構(gòu)。答：①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)存中可用存儲單元的地址必須是連續(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ù)為多少？刪除一個元素所需要移動的平均個數(shù)為多少？答：插入一個元素所需要移動的元素的平均個數(shù)為(n1)/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)時，需修改前一結(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)。在雙鏈表中，刪除第一個結(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è)計題（1）設(shè)計一個高效算法，將順序表的所有元素逆置，要求算法空間復(fù)雜度為O(1)。解：遍歷順序表L的前半部分元素，[i]（0≤i＜），[]進(jìn)行交換。對應(yīng)的算法如下：void reverse(SqList amp。L){ int i。 ElemType x。 for (i=0。i。i++) { x=[i]。 //[i][]交換 [i]=[]。 []=x。 }}本算法的時間復(fù)雜度為O(n)。（2）設(shè)計一個算法從順序表中刪除重復(fù)的元素，并使剩余元素間的相對次序保持不變。解：對于順序表L，用i從1開始遍歷其元素，[0..j]（j的初值為0）中沒有重復(fù)的元素。[i]（ji），[i][0..j]中任何一個元素都不相同，[i][j+1]中。對應(yīng)的算法如下：void delsame(SqList amp。L) //L為引用型參數(shù){ int i,j=0,k。 for (i=1。i。i++) { k=0。 while (k=j amp。amp。 [k]!=[i]) k++。 if (kj) //[i][0..j]中所有元素都不相同 { j++。 [j]=[i]。 } } =j+1。 //順序表長度置新值}本算法的時間復(fù)雜度為O(n2)，空間復(fù)雜度為O(1)。（3）設(shè)計一個算法從有序順序表中刪除重復(fù)的元素，并使剩余元素間的相對次序保持不變。解：在有序順序表L中，所有重復(fù)的元素應(yīng)是相鄰存放的，用k保存不重復(fù)出現(xiàn)的元素個數(shù)，[0..0]，置e=[0]，用i從1開始遍歷L的所有元素：[i]≠e時，[k]中，k增1，置e=[i]，最后將L的length置為k。對應(yīng)的算法如下：void delsame1(SqList amp。L) //L為引用型參數(shù){ int i,k=1。 //k保存不重復(fù)的元素個數(shù) ElemType e。 e=[0]。 for (i=1。i。i++) { if ([i]!=e) //只保存不重復(fù)的元素 { [k]=[i]。 k++。 e=[i]。 } } =k。 //順序表長度置新值}本算法是一個高效算法，其時間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。如果每次遇到重復(fù)的元素，都通過移動其后所有元素來刪除它，這樣的時間復(fù)雜度會變成O(n2)。（4）設(shè)計一個算法刪除單鏈表L中第一個值為x的結(jié)點(diǎn)。解：用p、q遍歷整個單鏈表，p指向*q的前驅(qū)結(jié)點(diǎn)，q用于查找第一個值為x的結(jié)點(diǎn)，當(dāng)找到后將*q結(jié)點(diǎn)刪除，返回1；否則返回0。對應(yīng)的算法如下：int delx(SLink *amp。L,ElemType x){ SLink *p=L,*q=pnext。 //p指向*q的前驅(qū)結(jié)點(diǎn) while (q!=NULL amp。amp。 qdata!=x) { p=q。 q=qnext。 } if (q!=NULL) //找到值為x的結(jié)點(diǎn) { pnext=qne