數據結構(第3版)習題答案(已修改)

　

【正文】 .. . . ..十二五普通高等教育國家級本科規劃教材第 1 章緒論高等學校精品資源共享課程學習好幫手 什么是數據結構？【答】：數據結構是指按一定的邏輯結構組成的一批數據，使用某種存儲結構將這批數據存儲于計算機中，并在這些數據上定義了一個運算集合。 數據結構涉及哪幾個方面？【答】：數據結構涉及三個方面的內容，即數據的邏輯結構、數據的存儲結構和數據的運算集合。 兩個數據結構的邏輯結構和存儲結構都相同，但是它們的運算集合中有一個運算的定義不一樣，它們是否可以認作是同一個數據結構？為什么？【答】：不能，運算集合是數據結構的重要組成部分，不同的運算集合所確定的數據結構是不一樣的，例如，棧與隊列它們的邏輯結構與存儲結構可以相同，但由于它們的運算集合不一樣，所以它們是兩種不同的數據結構。 線性結構的特點是什么？非線性結構的特點是什么？【答】：線性結構元素之間的關系是一對一的，在線性結構中只有一個開始結點和一個終端結點，其他的每一個結點有且僅有一個前驅和一個后繼結點。而非線性結構則沒有這個特點，元素之間的關系可以是一對多的或多對多的。 數據結構的存儲方式有哪幾種？【答】：數據結構的存儲方式有順序存儲、鏈式存儲、散列存儲和索引存儲等四種方式。 算法有哪些特點？它和程序的主要區別是什么？【答】：算法具有（1）有窮性（2）確定性（3）0 個或多個輸入（4）1 個或多個輸出（5）可行性等特征。程序是算法的一種描述方式，通過程序可以在計算機上實現算法。 抽象數據類型的是什么？它有什么特點？【答】：抽象數據類型是數據類型的進一步抽象，是大家熟知的基本數據類型的延伸和發展。抽象數據類型是與表示無關的數據類型，是一個數據模型及定義在該模型上的一組運算。對一個抽象數據類型進行定義時，必須給出它的名字及各運算的運算符名，即函數名，并且規定這些函數的參數性質。一旦定義了一個抽象數據類型及具體實現，程序設計中就可以像使用基本數據類型那樣，十分方便地使用抽象數據類型。抽象數據類型的設計者根據這些描述給出操作的具體實現，抽象數據類型的使用者依據這些描述使用抽象數據類型。 算法的時間復雜度指的是什么？如何表示？【答】：算法執行時間的度量不是采用算法執行的絕對時間來計算的，因為一個算法在不同的機器上執行所花的時間不一樣，在不同時刻也會由于計算機資源占用情況的不同，使得算法在同一臺計算機上執行的時間也不一樣，另外，算法執行的時間還與輸入數據的狀態有關，所以對于算法的時間復雜性，采用算法執行過程中其基本操作的執行次數，稱為計算量來度量。算法中基本操作的執行次數一般是與問題規模有關的，對于結點個數為 n 的數據處理問題，用T(n)表示算法基本操作的執行次數。為了評價算法的執行效率，通常采用大寫 O 符號表示算法的時間復雜度，大寫 O 符號給出了函數 f 的一個上限。其它義如下：3十二五普通高等教育國家級本科規劃教材高等學校精品資源共享課程定義：f (n)=O (g (n)) 當且僅當存在正的常數 c 和 n0，使得對于所有的 n≥n0，有 f (n) ≤c g(n)。上述定義表明，函數 f 頂多是函數 g 的 c 倍，除非 n 小于 n0。因此對于足夠大的 n (如 n≥n0)，g 是 f 的一個上限（不考慮常數因子 c）。在為函數 f 提供一個上限函數 g 時，通常使用比較簡單的函數形式。比較典型的形式是含有 n 的單個項（帶一個常數系數）。表 11 列出了一些常用的 g 函數及其名稱。對于表 11 中的對數函數 logn，沒有給出對數基，原因是對于任何大于 1 的常數 a 和 b 都有 logan =logbn/logba,所以 logan 和 logbn 都有一個相對的乘法系數 1/logba，其中 a 是一個常量。表 11 常用的漸進函數 算法的空間復雜度指的是什么？如何表示？【答】：算法的空間復雜度是指算法在執行過程中占用的額外的輔助空間的個數。可以將它表示為問題規模的函數，并通過大寫O符號表示空間復雜度。 對于下面的程序段，分析帶下劃線的語句的執行次數，并給出它們的時間復雜度 T(n)。（1） i++ 。（2） for(i=0。in。i++)if (a[i]x) x=a[i]。（3）for(i=0。in。i++)for(j=0。jn。j++)printf(“%d”,i+j) 。（4）for (i=1。i=n1。i++){ k=i。for(j=i+1。j=n。j++)if(a[j]a[j+1]) k=j。t=a[k]。 a[k]=a[i]。 a[i]=t。}（5）for(i=0。in。i++)for(j=0。jn。j++){++x。s=s+x。}【答】：（1）O（1）；（2）O（n）；（3）O（n2）；（4）O（n2）；（5）O（n2）4函數名稱1lognnnlogn2n3nn2n!常數對數線性n 個 logn平方立方指數階乘十二五普通高等教育國家級本科規劃教材高等學校精品資源共享課程第 2 章線性表及其順序存儲 選擇題（1）表長為 n 的順序存儲的線性表，當在任何位置上插入或刪除一個元素的概率相等時，插入一個元素所需移動元素的平均個數為（為（ A ）。E），刪除一個元素所需移動元素的平均個數A．（n?1）/2E．n/2B．nF．(n+1)/2C．n+1G．(n?2)/2D．n?1（2）設棧 S 和隊列 Q 的初始狀態為空，元素 eeeee5 和 e6 依次通過棧 S，一個元素出棧后即進入隊列 Q，若 6 個元素出隊的序列為 eeeee5 和 e1，則棧 S的容量至少應該為（ C ）。A．6B．4C．3D．2（3）設棧的輸入序列為 3… n，若輸出序列的第一個元素為 n，則第 i 個輸出的元素為（ B ）。A．不確定B．n?i+1C．iD．n?i（4）在一個長度為 n 的順序表中刪除第 i 個元素（1=i=n）時，需向前移動（ A ）個元素。A．n?iB．n?i+1C．n?i?1D．i（5）若長度為 n 的線性表采用順序存儲結構存儲，在第 i 個位置上插入一個新元素的時間復雜度為（ A ）。A．O(n)B．O(1)C．O(n2)D．O(n3)（6）表達式 a*(b+c)?d 的后綴表達式是（ B）。A．abcd*+?B．abc+*d?C．abc*+d?D．?+*abcd（7）隊列是一種特殊的線性表，其特殊性在于（ C ）。A．插入和刪除在表的不同位置執行 B．插入和刪除在表的兩端位置執行C．插入和刪除分別在表的兩端執行 D．插入和刪除都在表的某一端執行（8）棧是一種特殊的線性表，具有（ B ）性質。A．先進先出B．先進后出C．后進后出D．順序進出（9）順序循環隊列中（數組的大小為 n），隊頭指示 front 指向隊列的第 1 個元素，隊尾指示 rear 指向隊列最后元素的后 1 個位置，則循環隊列中存放了 n ? 1 個元素，即循環隊列滿的條件為（ B）。A．(rear+1)%n=front?1C．(rear)%n=frontB．(rear+1)%n=frontD．rear+1=front（10）順序循環隊列中（數組的大小為 6），隊頭指示 front 和隊尾指示 rear 的值分別為 3和 0，當從隊列中刪除 1 個元素，再插入 2 個元素后，front 和 rear 的值分別為（ D ）。A．5 和 1B．2 和 4C．1 和 5D．4 和 2 什么是順序表？什么是棧？什么是隊列？5十二五普通高等教育國家級本科規劃教材高等學校精品資源共享課程【答】：當線性表采用順序存儲結構時，即為順序表。棧是一種特殊的線性表，它的特殊性表現在約定了在這種線性表中數據的插入與刪除操作只能在這種線性表的同一端進行（即棧頂），因此，棧具有先進后出、后進先出的特點。隊列也是一種特殊的線性表，它的特殊性表現在約定了在這種線性表中數據的插入在表的一端進行，數據的刪除在表的另一端進行，因此隊列具有先進先出，后進后出的特點。 設計一個算法，求順序表中值為 x 的結點的個數。【答】：順序表的存儲結構定義如下（文件名 ）：include define N 100typedef int datatype。typedef struct {datatype data[N]。int length。} seqlist。/*預定義最大的數據域空間*//*假設數據類型為整型*//*此處假設數據元素只包含一個整型的關鍵字域*//*線性表長度*//*預定義的順序表類型*/算法 countx（L,x）用于求順序表 L 中值為 x 的結點的個數。int countx(seqlist *L,datatype x){int c=0。int i。for (i=0。iLlength。i++)if (Ldata[i]==x) c++。return c。} 設計一個算法，將一個順序表倒置。即，如果順序表各個結點值存儲在一維數組 a 中，倒置的結果是使得數組 a 中的 a[0]等于原來的最后一個元素，a[1] 等于原來的倒數第 2 個元素，…，a 的最后一個元素等于原來的第一個元素。【答】：順序表的存儲結構定義同題 ，實現順序表倒置的算法程序如下：void verge(seqlist *L){int t,i,j。i=0。j=Llength1。while (ij){ t=Ldata[i]。Ldata[i++]=Ldata[j]。Ldata[j]=t。}} 已知一個順序表中的各結點值是從小到大有序的，設計一個算法，插入一個值為 x 的結點，使順序表中的結點仍然是從小到大有序。【答】：順序表的定義同題 ，實現本題要求的算法程序如下：6十二五普通高等教育國家級本科規劃教材void insertx(seqlist *L,datatype x){int j。if (LlengthN){ j=Llength1。while (j=0 amp。amp。 Ldata[j]x){ Ldata[j+1]=Ldata[j]。j。}Ldata[j+1]=x。Llength++。}} 將下列中綴表達式轉換為等價的后綴表達式。(1) 5+6*7(2) (56)/7(3) 56*7*8(4) 5*78(5) 5*(76)+8/9(6) 7*(56*8)9【答】：高等學校精品資源共享課程(7) 5+6*7(8) (56)/7(9) 56*7*8(10)5*78(11)5*(76)+8/9(12)7*(56*8)9后綴表達式：5 6 7*+后綴表達式：5 67/后綴表達式：5 6 7*8*后綴表達式：5 7* 8后綴表達式：5 7 6*8 9/+后綴表達式：7 5 6 8**9 循環隊列存儲在一個數組中，數組大小為 n，隊首指針和隊尾指針分別為 front 和 rear，請寫出求循環隊列中當前結點個數的表達式。【答】：循環隊列中當前結點個數的計算公式是：(n+rearfront)%n 編號為 1,2,3,4 的四列火車通過一個棧式的列車調度站，可能得到的調度結果有哪些？如果有 n 列火車通過調度站，請設計一個算法，輸出所有可能的調度結果。【答】：方法一：算法思想：逐次輸出所有可能，用回溯法。即：總體：對原始序列中的每一個元素，總是先入棧，后出棧1．入棧后的操作：；；2．出棧后的操作：a.（棧中其他元素）繼續出棧；b. （原始序列中）下一個數入棧；注意：回溯法，關鍵在于回溯，即在某分支結點 X：處理 X 的一個子分支，再退回分支 X，接著處理 X 的下一個子分支,若所有 X 的子分支處理完，再退回上一層分支節點。所謂“退回”，7十二五普通高等教育國家級本科規劃教材高等學校精品資源共享課程實際上就是恢復。程序代碼：()include define MAX 26typedef struct s{char a[MAX]。int top。}Stack。/*定義一些全局變量*/Stack S。 /*