第一章第1章作業：1.1,1.2,1.6 (1) (3) 1.8
1.1 簡述下列概念：資料、資料元素、資料型別、資料結構、邏輯結構、儲存結構、線性結構、非線性結構。
● 資料：指能夠被計算機識別、儲存和加工處理的資訊載體。
● 資料元素：就是資料的基本單位，在某些情況下，資料元素也稱為元素、結點、頂點、記錄。資料元素有時可以由若干資料項組成。
● 資料型別：是乙個值的集合以及在這些值上定義的一組操作的總稱。通常資料型別可以看作是程式語言中已實現的資料結構。
● 資料結構：指的是資料之間的相互關係，即資料的組織形式。一般包括三個方面的內容:資料的邏輯結構、儲存結構和資料的運算。
● 邏輯結構：指資料元素之間的邏輯關係。
● 儲存結構：資料元素及其關係在計算機儲存器內的表示，稱為資料的儲存結構.
● 線性結構：資料邏輯結構中的一類。它的特徵是若結構為非空集，則該結構有且只有乙個開始結點和乙個終端結點，並且所有結點都有且只有乙個直接前趨和乙個直接後繼。
線性表就是乙個典型的線性結構。棧、佇列、串等都是線性結構。
● 非線性結構：資料邏輯結構中的另一大類，它的邏輯特徵是乙個結點可能有多個直接前趨和直接後繼。陣列、廣義表、樹和圖等資料結構都是非線性結構。
1.2 試舉乙個資料結構的例子、敘述其邏輯結構、儲存結構、運算三個方面的內容。
答：例如有一張學生體檢情況登記表，記錄了乙個班的學生的身高、體重等各項體檢資訊。這張登記表中，每個學生的各項體檢資訊排在一行上。
這個表就是乙個資料結構。每個記錄(有姓名，學號，身高和體重等字段)就是乙個結點，對於整個表來說，只有乙個開始結點(它的前面無記錄)和乙個終端結點(它的後面無記錄)，其他的結點則各有乙個也只有乙個直接前趨和直接後繼(它的前面和後面均有且只有乙個記錄)。這幾個關係就確定了這個表的邏輯結構是線性結構。
這個表中的資料如何儲存到計算機裡，並且如何表示資料元素之間的關係呢? 即用一片連續的記憶體單元來存放這些記錄(如用陣列表示)還是隨機存放各結點資料再用指標進行鏈結呢? 這就是儲存結構的問題。
在這個表的某種儲存結構基礎上，可實現對這張表中的記錄進行查詢，修改，刪除等操作。對這個表可以進行哪些操作以及如何實現這些操作就是資料的運算問題了。
1.6 設n為正整數，利用大"o"記號，將下列程式段的執行時間表示為n的函式。
(1) i=1; k=0;
while(i
分析：i=1; //1
k=0; //1
while(i
由以上列出的各語句的頻度，可得該程式段的時間消耗：
t(n)=1+1+n+(n-1)+(n-1)=3n
可表示為t(n)=o(n)
(3) i=1; j=0;
while(i+j<=n)
分析：通過分析以上程式段，可將i+j看成乙個控制迴圈次數的變數，且每執行一次迴圈，i+j的值加1。該程式段的主要時間消耗是while迴圈，而while迴圈共做了n次，所以該程式段的執行時間為：
t(n)=o(n)
1.8 按增長率由小至大的順序排列下列各函式：2100, (3/2)n，(2/3)n， nn ,n0.5 , n! ，2n ，lgn ,nlgn, n(3/2)
答：常見的時間複雜度按數量級遞增排列,依次為:常數階0(1)、對數階0(log2n)、線性階0(n)、線性對數階0(nlog2n)、平方階0(n2)、立方階0(n3)、k次方階0(nk)、指數階0(2n)。
先將題中的函式分成如下幾類：
常數階：2100
對數階：lgn
k次方階：n0.5、n(3/2)
指數階 (按指數由小到大排)：nlgn、(3/2)n、2n、 n!、 nn
注意：(2/3)^n由於底數小於1，所以是乙個遞減函式，其數量級應小於常數階。
根據以上分析按增長率由小至大的順序可排列如下：(2/3)n < 2100 < lgn < n0.5 < n(3/2) < nlgn < (3/2)n < 2n < n! < nn
第二章第2章作業：2.2，2.6,2.9,2.13
2.2 何時選用順序表、何時選用鍊錶作為線性表的儲存結構為宜?
答：在實際應用中，應根據具體問題的要求和性質來選擇順序表或鍊錶作為線性表的儲存結構，通常有以下幾方面的考慮：
1.基於空間的考慮。當要求儲存的線性表長度變化不大，易於事先確定其大小時，為了節約儲存空間，宜採用順序表；反之，當線性表長度變化大，難以估計其儲存規模時，採用動態鍊錶作為儲存結構為好。
2.基於時間的考慮。若線性表的操作主要是進行查詢，很少做插入和刪除操作時，採用順序表做儲存結構為宜；反之， 若需要對線性表進行頻繁地插入或刪除等的操作時，宜採用鍊錶做儲存結構。
並且，若鍊錶的插入和刪除主要發生在表的首尾兩端，則採用尾指標表示的單迴圈鍊錶為宜。
2.6 下述演算法的功能是什麼?
linklist demo(linklist l)
return l;
}// demo
答：該演算法的功能是：將開始結點摘下鏈結到終端結點之後成為新的終端結點，而原來的第二個結點成為新的開始結點，返回新鍊錶的頭指標。
2.9 設順序表l是乙個遞增有序表，試寫一演算法，將x插入l中，並使l仍是乙個有序表。
答：因已知順序表l是遞增有序表，所以只要從順序表終端結點（設為i位置元素）開始向前尋找到第乙個小於或等於x的元素位置i後插入該位置即可。在尋找過程中，由於大於x的元素都應放在x之後，所以可邊尋找，邊後移元素，當找到第乙個小於或等於x的元素位置i時，該位置也空出來了。
演算法如下：
//順序表儲存結構如題2.7
void insertincreaselist( seqlist *l , datatype x )
2.13 設 a和b是兩個單鏈表，其表中元素遞增有序。試寫一演算法將a和b歸併成乙個按元素值遞減有序的單鏈表c，並要求輔助空間為o(1)，請分析演算法的時間複雜度。
解：根據已知條件，a和b是兩個遞增有序表，所以可以先取a表的表頭建立空的c表。然後同時掃瞄a表和b表，將兩表中最大的結點從對應表中摘下，並作為開始結點插入c表中。
如此反覆，直到a表或b表為空。最後將不為空的a表或b表中的結點依次摘下並作為開始結點插入c表中。這時，得到的c表就是由a表和b表歸併成的乙個按元素值遞減有序的單鏈表c。
並且輔助空間為o(1)。
演算法如下：
linklist mergesort ( linklist a , linklist b )
else
q->next=c->next;c->next=q;//將摘下的結點q作為開始結點插入c表
}//若pa表非空，則處理pa表
while(pa)
//若pb表非空，則處理pb表
while(pb)
return(c);
}該演算法的時間複雜度分析如下：
演算法中有三個while 迴圈，其中第二個和第三個迴圈只執行乙個。每個迴圈做的工作都是對鍊錶中結點掃瞄處理。整個演算法完成後，a表和b表中的每個結點都被處理了一遍。
所以若a表和b表的表長分別是m和n，則該演算法的時間複雜度o(m+n)
●練習2.1：寫出**性表中的查詢運算演算法。
即查詢資料元素x在表中的位置，也就是資料元素下標值加1。
例如：若l.data[i]=x,則返回i+1;若不存在，則返回n+1
練習2.2：編寫尾插法建立鍊錶的演算法。
練習2.3：若是帶頭指標的單鏈表，演算法又是怎樣？
若是兩個鍊錶，既知道頭結點，又知道尾結點，演算法又是怎樣？
●練習2：按公升序列印帶頭結點h的單鏈表中各節點的資料域值，並將列印完的節點從表中刪除。
第三章第3章作業：3.2, 3.3，3.4（2）， 3.6， 3.11
3.2 迴圈佇列的優點是什麼? 如何判別它的空和滿?
答：迴圈佇列的優點是：它可以克服順序佇列的"假上溢"現象，能夠使儲存佇列的向量空間得到充分的利用。
判別迴圈佇列的"空"或"滿"不能以頭尾指標是否相等來確定，一般是通過以下幾種方法：一是另設一布林變數來區別佇列的空和滿。二是少用乙個元素的空間,每次入隊前測試入隊後頭尾指標是否會重合，如果會重合就認為佇列已滿。
三是設定一計數器記錄佇列中元素總數，不僅可判別空或滿，還可以得到佇列中元素的個數。
3.3設長度為n的鏈隊用單迴圈鍊錶表示，若設頭指標，則入隊出隊操作的時間為何? 若只設尾指標呢?
答：當隻設頭指標時，出隊的時間為1，而入隊的時間需要n，因為每次入隊均需從頭指標開始查詢，找到最後乙個元素時方可進行入隊操作。若只設尾指標，則出入隊時間均為1。
因為是迴圈鍊錶，尾指標所指的下乙個元素就是頭指標所指元素，所以出隊時不需要遍歷整個佇列。
資料結構課後習題答案
5 選擇題 ccbdca 6 試分析下面各程式段的時間複雜度。1 o 1 2 o m n 3 o n2 4 o log3n 5 因為x 共執行了n 1 n 2 1 n n 1 2，所以執行時間為o n2 6 o 1 選擇題 babadbcabdcddac 2 演算法設計題 6 設計乙個演算法，通過一...
資料結構課後習題答案
1.填空 是資料的基本單位，在電腦程式中通常作為乙個整體進行考慮和處理。解答 資料元素 是資料的最小單位，是討論資料結構時涉及的最小資料單位。解答 資料項，資料元素 分析 資料結構指的是資料元素以及資料元素之間的關係。從邏輯關係上講，資料結構主要分為和 解答 集合，線性結構，樹結構，圖結構 資料的儲...
資料結構課後習題
1.1 簡述資料與資料元素的關係與區別 資料元素 data element 是資料的基本單位，在電腦程式中通常作為乙個整體進行考慮和處理。有時，乙個資料元素可由若干個資料項組成 1.2 資料結構和資料型別有什麼區別 資料結構是指計算機處理的資料元素的組織形式和相互關係，而資料型別是某種程式語言已實現...