數據結構課程課后習題答案(已修改)

　

【正文】 練習題及參考答案《數據結構簡明教程》練習題及參考答案練習題11. 單項選擇題（1）線性結構中數據元素之間是（ ）關系。 答：D（2）數據結構中與所使用的計算機無關的是數據的（ ）結構。 答：C（3）算法分析的目的是（ ）。 答：C（4）算法分析的兩個主要方面是（ ）。 答：A（5）計算機算法指的是（ ）。 B. 排序方法 答：C（6）計算機算法必須具備輸入、輸出和（ ）等5個特性。、可移植性和可擴充性 、確定性和有窮性、有窮性和穩定性 、穩定性和安全性答：B2. 填空題（1）數據結構包括數據的 ① 、數據的 ② 和數據的 ③ 這三個方面的內容。答：①邏輯結構 ②存儲結構 ③運算（2）數據結構按邏輯結構可分為兩大類，它們分別是 ① 和 ② 。答：①線性結構 ②非線性結構（3）數據結構被形式地定義為（D,R），其中D是 ① 的有限集合，R是D上的 ② 有限集合。答：①數據元素 ②關系（4）在線性結構中，第一個結點 ① 前驅結點，其余每個結點有且只有1個前驅結點；最后一個結點 ② 后繼結點，其余每個結點有且只有1個后繼結點。答：①沒有 ②沒有（5）在樹形結構中，樹根結點沒有 ① 結點，其余每個結點有且只有 ② 個前驅結點；葉子結點沒有 ③ 結點，其余每個結點的后繼結點數可以是 ④ 。答：①前驅 ②1 ③后繼 ④任意多個（6）在圖形結構中，每個結點的前驅結點數和后繼結點數可以是（ ）。答：任意多個（7）數據的存儲結構主要有四種，它們分別是 ① 、 ② 、 ③ 和 ④ 存儲結構。答：①順序 ②鏈式 ③索引 ④哈希（8）一個算法的效率可分為 ① 效率和 ② 效率。答：①時間 ②空間3. 簡答題（1）數據結構和數據類型兩個概念之間有區別嗎？答：簡單地說，數據結構定義了一組按某些關系結合在一起的數組元素的集合。數據類型不僅定義了一組數據元素，而且還在其上定義了一組操作。（2）簡述線性結構、樹形結構和圖形結構的不同點。答：線性結構反映結點間的邏輯關系是一對一的，樹形線性結構反映結點間的邏輯關系是一對多的，圖在結構反映結點間的邏輯關系是多對多的。（3）設有采用二元組表示的數據邏輯結構S=(D,R)，其中D={a,b,…,i}，R={(a,b),(a,c),(c,d),(c,f),(f,h),(d,e),(f,g),(h,i)}，問相對于關系R，哪些結點是開始結點，哪些結點是終端結點？答：該邏輯結構為樹形結構，其中a結點沒有前驅結點，稱為根結點，b、e、g、i結點沒有后繼結點，是終端結點，也稱為葉子結點。（4）以下各函數是算法中語句的執行頻度，n為問題規模，給出對應的時間復雜度：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）分析下面程序段中循環語句的執行次數。int j=0,s=0,n=100。do{ j=j+1。 s=s+10*j。} while (jn amp。amp。 sn)。答：j=0，第1次循環：j=1，s=10。第2次循環：j=2，s=30。第3次循環：j=3，s=60。第4次循環：j=4，s=100。while條件不再滿足。所以，其中循環語句的執行次數為4。（6）執行下面的語句時，語句s++的執行次數為多少？int s=0。for (i=1。in1。i++) for (j=n。j=i。j) s++。答：語句s的執行次數。（7）設n為問題規模，求以下算法的時間復雜度。void fun1(int n){ int x=0,i。 for (i=1。i=n。i++) for (j=i+1。j=n。j++) x++。}答：其中x++語句屬基本運算語句，=O(n2)。（8）設n為問題規模，是一個正偶數，試計算以下算法結束時m的值，并給出該算法的時間復雜度。void fun2(int n){ int m=0。 for (i=1。i=n。i++) for (j=2*i。j=n。j++) m++。}答：由于內循環j的取值范圍，所以i≤n/2，則，該程序段的時間復雜度為O(n2)。上機實驗題1有一個整型數組a，其中含有n個元素，設計盡可能好的算法求其中的最大元素和次大元素，并采用相關數據測試。解：maxs算法用于返回數組a[0..n1]中的最大元素值max1和次大元素值max2，max1和max2設計為引用類型。對應的程序如下：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)。}練習題21. 單項選擇題（1）數據在計算機存儲器內表示時，物理地址與邏輯地址相對順序相同并且是連續的，稱之為（ ）。 答：C（2）在n個結點的順序表中，算法的時間復雜度是O（1）的操作是（ ）。（1≤i≤n）和求第i（2≤i≤n）個結點的前驅結點（1≤i≤n）個結點后插入一個新結點（1≤i≤n）答：A（3） 向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動（ ）個元素。 答：B（4）鏈式存儲結構所占存儲空間（ ）。，一部分存放結點值，另一部分存放表示結點間關系的指針，存放結點值，存儲表示結點間關系的指針，一部分存放結點值，另一部分存放結點所占單元數答：A（5）線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址（ ）。 答：D（6）一個線性表在（ ）情況下適用于采用鏈式存儲結構。 答：B（7）單鏈表的存儲密度（ ） 答：C2. 填空題（1）在順序表中插入或刪除一個元素時，需要平均移動（ ① ）元素，具體移動的元素個數與（ ② ）有關。答：①表中一半 ②表長和該元素在表中的位置（2）向一個長度為n的順序表的第i個元素（1≤i≤n+1）之前插入一個元素時，需向后移動（ ）個元素。答：ni+1（3）向一個長度為n的順序表中刪除第i個元素（1≤i≤n）時，需向前移動（ ）個元素。答：ni（4）在順序表中訪問任意一個元素的時間復雜度均為（ ① ），因此順序表也稱為（ ② ）的數據結構。答：①O(1) ②隨機存取（5）順序表中邏輯上相鄰的元素的物理位置（ ① ）相鄰。單鏈表中邏輯上相鄰的元素的物理位置（ ② ）相鄰。答：①一定 ②不一定（6）在帶頭結點的單鏈表中，除頭結點外，任一結點的存儲位置由（ ）指示。答：其前驅結點的鏈域的值（7）在含有n個數據結點的單鏈表中要刪除已知結點*p，需找到它的（ ① ），其時間復雜度為（ ② ）。答：①前驅結點的地址 ②O(n)（8）含有n（n1）個結點的循環雙向鏈表中，為空的指針域數為（ ）。答：03. 簡答題（1）試比較順序存儲結構和鏈式存儲結構的優缺點。在什么情況下用順序表比鏈表好？答：順序存儲結構中，相鄰數據元素的存放地址也相鄰，并要求內存中可用存儲單元的地址必須是連續的。其優點是存儲密度大，存儲空間利用率高；缺點是插入或刪除元素時不方便。鏈式存儲結構中，相鄰數據元素可隨意存放，但所占存儲空間分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針。其優點是插入或刪除元素時很方便，使用靈活；缺點是存儲密度小，存儲空間利用率低。順序表適宜于做查找這樣的靜態操作；鏈表宜于做插入、刪除這樣的動態操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。（2）對于表長為n的順序表，在任何位置上插入或刪除一個元素的概率相等時，插入一個元素所需要移動的元素的平均個數為多少？刪除一個元素所需要移動的平均個數為多少？答：插入一個元素所需要移動的元素的平均個數為(n1)/2，刪除一個元素所需要移動的平均個數為n/2。（3）在鏈表中設置頭結點的作用是什么？答：在鏈表中設置頭結點后，不管鏈表是否為空表，頭結點指針均不空，并使得對鏈表的操作（如插入和刪除）在各種情況下統一，從而簡化了算法的實現過程。（4）對于雙鏈表和單鏈表，在兩個結點之間插入一個新結點時需修改的指針各為多少個？答：對于雙鏈表，在兩個結點之間插入一個新結點時，需修改前驅結點的next域、后繼結點的prior域和新插入結點的next、prior域。所以共修改4個指針。對于單鏈表，在兩個結點之間插入一個新結點時，需修改前一結點的next域，新插入結點的next域。所以共修改兩個指針。（5）某含有n（n1）結點的線性表中，最常用的操作是在尾結點之后插入一個結點和刪除第一個結點，則采用以下哪種存儲方式最節省運算時間。①單鏈表；②僅有頭指針不帶頭結點的循環單鏈表；③雙鏈表；④僅有尾指針的循環單鏈表。答：在單鏈表中，刪除第一個結點的時間復雜度為O(1)。插入結點需找到前驅結點，所以在尾結點之后插入一個結點，需找到尾結點，對應的時間復雜度為O(n)。在僅有頭指針不帶頭結點的循環單鏈表中，刪除第一個結點的時間復雜度O(n)，因為刪除第一個結點后還要將其改為循環單鏈表；在尾結點之后插入一個結點的時間復雜度也為O(n)。在雙鏈表中，刪除第一個結點的時間復雜度為O(1)；在尾結點之后插入一個結點，也需找到尾結點，對應的時間復雜度為O(n)。在僅有尾指針的循環單鏈表中，通過該尾指針可以直接找到第一個結點，所以刪除第一個結點的時間復雜度為O(1)；在尾結點之后插入一個結點也就是在尾指針所指結點之后插入一個結點，時間復雜度也為O(1)。因此④最節省運算時間。4. 算法設計題（1）設計一個高效算法，將順序表的所有元素逆置，要求算法空間復雜度為O(1)。解：遍歷順序表L的前半部分元素，[i]（0≤i＜），[]進行交換。對應的算法如下：void reverse(SqList amp。L){ int i。 ElemType x。 for (i=0。i。i++) { x=[i]。 //[i][]交換 [i]=[]。 []=x。 }}本算法的時間復雜度為O(n)。（2）設計一個算法從順序表中刪除重復的元素，并使剩余元素間的相對次序保持不變。解：對于順序表L，用i從1開始遍歷其元素，[0..j]（j的初值為0）中沒有重復的元素。[i]（ji），[i][0..j]中任何一個元素都不相同，[i][j+1]中。對應的算法如下：void delsame(SqList amp。L) //L為引用型參數{ 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。 //順序表長度置新值}本算法的時間復雜度為O(n2)，空間復雜度為O(1)。（3）設計一個算法從有序順序表中刪除重復的元素，并使剩余元素間的相對次序保持不變。解：在有序順序表L中，所有重復的元素應是相鄰存放的，用k保存不重復出現的元素個數，[0..0]，置e=[0]，用i從1開始遍歷L的所有元素：[i]≠e時，[k]中，k增1，置e=[i]，最后將L的length置為k。對應的算法如下：void delsame1(SqList amp。L) //L為引用型參數{ int i,k=1。 //k保存不重復的元素個數 ElemType e。 e=[0]。 for (i=1。i。i++) { if ([i]!=e) //只保存不重復的元素 { [k]=[i]。 k++。 e=[i]。 } } =k。 //順序表長度置新值}本算法是一個高效算法，其時間復雜度為O(n)，空間復雜度為O(1)。如果每次遇到重復的元素，都通過移動其后所有元素來刪除它，這樣的時間復雜度會變成O(n2)。（4）設計一個算法刪除單鏈表L中第一個值為x的結點。解：用p、q遍歷整個單鏈表，p指向*q的前驅結點，q用于查找第一個值為x的結點，當找到后將*q結點刪除，返回1；否則返回0。對應的算法如下：int delx(SLink *amp。L,ElemType x){ SLink *p=L,*q=pnext。 //p指向*q的前驅結點 while (q!=NULL amp。amp。 qdata!=x) { p=q。 q=qnext。 } if (q!=NULL) //找到值為x的結點 { pnext=qne