【正文】 棧頂 。頭結(jié)點headdatalink 頭指針 首元結(jié)點簡而言之，頭指針是指向鏈表中第一個結(jié)點（或為頭結(jié)點或為首元結(jié)點）的指針；頭結(jié)點是在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長等信息（內(nèi)放頭指針？那還得另配一個頭指針！?。。┦自亟Y(jié)點是指鏈表中存儲線性表中第一個數(shù)據(jù)元素a1的結(jié)點。這三個概念對單鏈表、雙向鏈表和循環(huán)鏈表均適用。若鏈表中附設(shè)頭結(jié)點，則不管線性表是否為空表，頭指針均不為空。為了操作方便，通常在鏈表的首元結(jié)點之前附設(shè)一個結(jié)點，稱為頭結(jié)點，該結(jié)點的數(shù)據(jù)域中不存儲線性表的數(shù)據(jù)元素，其作用是為了對鏈表進行操作時，可以對空表、非空表的情況以及對首元結(jié)點進行統(tǒng)一處理。2 .【①】描述以下三個概念的區(qū)別：頭指針、頭結(jié)點、首元結(jié)點（第一個元素結(jié)點）。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。②鏈?zhǔn)酱鎯r，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針優(yōu)點：插入或刪除元素時很方便，使用靈活。優(yōu)點：存儲密度大（＝1？），存儲空間利用率高。（Ａ）需經(jīng)常修改Ｌ中的結(jié)點值（Ｂ）需不斷對Ｌ進行刪除插入 （Ｃ）Ｌ中含有大量的結(jié)點 （Ｄ）Ｌ中結(jié)點結(jié)構(gòu)復(fù)雜（C）9． 單鏈表的存儲密度（Ａ）大于1； （Ｂ）等于1；（Ｃ）小于1； （Ｄ）不能確定（B）10． 設(shè)aaa3為3個結(jié)點，整數(shù)P0，3，4代表地址，則如下的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為P034P0a13a24A30（Ａ）循環(huán)鏈表 （Ｂ）單鏈表（Ｃ）雙向循環(huán)鏈表 （Ｄ）雙向鏈表四、簡答題1. 【②】試比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點。鏈?zhǔn)酱鎯蜔o需一致。（）10. 線性表的邏輯順序與存儲順序總是一致的。錯誤。線性表有兩種存儲方式，在順序存儲時，邏輯上相鄰的元素在存儲的物理位置次序上也相鄰。（）8. 線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。錯，線性表有兩種存儲方式，順序存儲和鏈?zhǔn)酱鎯?。順序存儲方式插入、刪除運算效率較低，在表長為n的順序表中，插入和刪除一個數(shù)據(jù)元素，平均需移動表長一半個數(shù)的數(shù)據(jù)元素。順序表才適合隨機存取，鏈表恰恰適于“順藤摸瓜”（）6. 順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。（）5. 順序表結(jié)構(gòu)適宜于進行順序存取，而鏈表適宜于進行隨機存取。（）4. 線性表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復(fù)雜類型。（）3. 鏈表的刪除算法很簡單，因為當(dāng)刪除鏈中某個結(jié)點后，計算機會自動地將后續(xù)的各個單元向前移動。（）2. 鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序。鏈表中的結(jié)點可含多個指針域，分別存放多個指針。二、判斷正誤（在正確的說法后面打勾，反之打叉）（）1. 鏈表的每個結(jié)點中都恰好包含一個指針。7. 【①】在單鏈表中，除了首元結(jié)點外，任一結(jié)點的存儲位置由 其直接前驅(qū)結(jié)點的鏈域的值 指示。6. 【①】順序表中邏輯上相鄰的元素的物理位置 必定相鄰。4. 向一個長度為n的向量中刪除第i個元素(1≤i≤n)時，需向前移動 ni 個元素。2. 線性表中結(jié)點的集合是 有限 的，結(jié)點間的關(guān)系是 一對一 的。答：O（log3n）五、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)S=（D,R），試按各小題所給條件畫出這些邏輯結(jié)構(gòu)的圖示，并確定相對于關(guān)系R，哪些結(jié)點是開始結(jié)點，哪些結(jié)點是終端結(jié)點？ 1. 【嚴(yán)蔚敏習(xí)題集P7 ②】D={d1,d2,d3,d4} R={(d1,d2),(d2,d3),(d3,d4) }答： d1→d2→d3→d4 d1—無直接前驅(qū)，是首結(jié)點d4—無直接后繼是尾結(jié)點2。解：因為x++共執(zhí)行了n1+n2+……＋1= n(n1)/2，所以執(zhí)行時間為O（n2）4. i=1。 j=ni。 in。答：O（m*n）四、【④】分析下面各程序段的時間復(fù)雜度3. x=0。 jm。 in。sum=s。 jn。 in。2. s=0。2. 簡述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點。A) 可行性、可移植性和可擴充性B) 可行性、確定性和有窮性C) 確定性、有窮性和穩(wěn)定性 D) 易讀性、穩(wěn)定性和安全性三、簡答題1.【②】數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個概念之間有區(qū)別嗎？答：簡單地說，數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素。11. 一個算法的效率可分為 時間 效率和 空間 效率。9．?dāng)?shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示，它們分別是順序 、鏈?zhǔn)?、索引 和 散列 。7. 在樹形結(jié)構(gòu)中，樹根結(jié)點沒有 前驅(qū) 結(jié)點，其余每個結(jié)點有且只有 1 個前驅(qū)結(jié)點；葉子結(jié)點沒有 后續(xù) 結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點數(shù)可以任意多個 。5. 線性結(jié)構(gòu)中元素之間存在一對一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。3. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 邏輯結(jié)構(gòu) 、數(shù)據(jù)的 存儲結(jié)構(gòu) 和數(shù)據(jù)的 運算 這三個方面的內(nèi)容。. .. . ..第一章概論 自測題答案 一、填空題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的 操作對象 以及它們之間的 關(guān)系 和運算等的學(xué)科。2. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D, R），其中D是 數(shù)據(jù)元素 的有限集合，R是D上的 關(guān)系 有限集合。4. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是 線性結(jié)構(gòu) 和 非線性結(jié)構(gòu) 。6．在線性結(jié)構(gòu)中，第一個結(jié)點 沒有 前驅(qū)結(jié)點，其余每個結(jié)點有且只有 1個前驅(qū)結(jié)點；最后一個結(jié)點 沒有 后續(xù)結(jié)點，其余每個結(jié)點有且只有1個后續(xù)結(jié)點。8. 在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以 任意多個 。10. 數(shù)據(jù)的運算最常用的有5種，它們分別是插入 、 刪除、修改、 查找 、排序。二、單項選擇題（ B ）1. 非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：A）一對多關(guān)系 B）多對多關(guān)系 C）多對一關(guān)系 D）一對一關(guān)系（ C ）2. 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的 結(jié)構(gòu)；A) 存儲 B) 物理 C) 邏輯 D) 物理和存儲（ C ）3. 算法分析的目的是：A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B) 研究算法中的輸入和輸出的關(guān)系C) 分析算法的效率以求改進D) 分析算法的易懂性和文檔性（ A ）4. 算法分析的兩個主要方面是：A) 空間復(fù)雜性和時間復(fù)雜性 B) 正確性和簡明性C) 可讀性和文檔性 D) 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性（ C ）5. 計算機算法指的是：A) 計算方法B) 排序方法 C) 解決問題的有限運算序列D) 調(diào)度方法（ B ）6. 計算機算法必須具備輸入、輸出和 等5個特性。數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素，而且還在其上定義了一組操作。答：線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是 一對一的，非線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是多對多的。 for i=0。 i++)for(j=0。 j++) s+=B[i][j]。答：O（n2）1. for (i=0。 i++)for (j=0。 j++)A[i][j]=0。for(i=1。 i++) for (j=1。 j++)x++。 while(i=n) i=i*3。D={d1,d2,…,d9} R={(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) }答： 此圖為樹形結(jié)構(gòu) d1—無直接前驅(qū)，是根結(jié)點 d2,d5,d7,d9—無直接后繼是葉子結(jié)點3．D={d1,d2,…,d9} R={(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6)}答： 此圖為圖形結(jié)構(gòu) d1，d2—無直接前驅(qū)，是開始結(jié)點 d6,d7—無直接后繼是終端結(jié)點 (2) (3)第2章 自測卷答案一、填空1. 【①】在順序表中插入或刪除一個元素，需要平均移動 表中一半元素，具體移動的元素個數(shù)與 表長和該元素在表中的位置 有關(guān)。3. 向一個長度為n的向量的第i個元素(1≤i≤n+1)之前插入一個元素時，需向后移動 ni+1 個元素。5. 在順序表中訪問任意一結(jié)點的時間復(fù)雜度均為 O(1) ，因此，順序表也稱為 隨機存取 的數(shù)據(jù)結(jié)構(gòu)。單鏈表中邏輯上相鄰的元素的物理位置 不一定 相鄰。8． 在n個結(jié)點的單鏈表中要刪除已知結(jié)點*p，需找到它的前驅(qū)結(jié)點的地址，其時間復(fù)雜度為O（n）。 答：錯誤。例如，雙向鏈表中的結(jié)點可以含有兩個指針域，分別存放指向其直接前趨和直接后繼結(jié)點的指針。錯，鏈表的存儲結(jié)構(gòu)特點是無序，而鏈表的示意圖有序。錯，鏈表的結(jié)點不會移動，只是指針內(nèi)容改變。錯，混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，鏈表也是線性表！且即使是順序表，也能存放記錄型數(shù)據(jù)。 錯，正好說反了。錯，前一半正確，但后一半說法錯誤，那是鏈?zhǔn)酱鎯Φ膬?yōu)點。（）7. 線性表在物理存儲空間中也一定是連續(xù)的。后者不要求連續(xù)存放。錯誤。（）9. 順序存儲方式只能用于存儲線性結(jié)構(gòu)。順序存儲方式不僅能用于存儲線性結(jié)構(gòu)，還可以用來存放非線性結(jié)構(gòu)，例如完全二叉樹是屬于非線性結(jié)構(gòu)，但其最佳存儲方式是順序存儲方式。錯，理由同7。三、單項選擇題（C）1．?dāng)?shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：（A）存儲結(jié)構(gòu) （B）邏輯結(jié)構(gòu)（C）順序存儲結(jié)構(gòu) （D）鏈?zhǔn)酱鎯Y(jié)構(gòu)（B），每個元素的長度為2，則第5個元素的地址是 （A）110 （B）108 （C）100 （D）120（A）3. 在n個結(jié)點的順序表中，算法的時間復(fù)雜度是O（1）的操作是：（A）訪問第i個結(jié)點（1≤i≤n）和求第i個結(jié)點的直接前驅(qū)（2≤i≤n） （B）在第i個結(jié)點后插入一個新結(jié)點（1≤i≤n）（C）刪除第i個結(jié)點（1≤i≤n）（D）將n個結(jié)點從小到大排序（B）4. 向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動 個元素（A）8 （B） （C）63 D）7（A）5. 鏈接存儲的存儲結(jié)構(gòu)所占存儲空間：（A）分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針（B）只有一部分，存放結(jié)點值（C）只有一部分，存儲表示結(jié)點間關(guān)系的指針（D）分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)（B）6. 鏈表是一種采用 存儲結(jié)構(gòu)存儲的線性表；（A）順序 （B）鏈?zhǔn)?（C）星式 （D）網(wǎng)狀（D）7. 線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址:（A）必須是連續(xù)的 （B）部分地址必須是連續(xù)的（C）一定是不連續(xù)的 （D）連續(xù)或不連續(xù)都可以（B）8． 線性表Ｌ在 情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)。在什么情況下用順序表比鏈表好？答：① 順序存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。缺點：插入或刪除元素時不方便。缺點：存儲密度?。?），存儲空間利用率低。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。在單鏈表中設(shè)置頭結(jié)點的作用是什么？答：首元結(jié)點是指鏈表中存儲線性表中第一個數(shù)據(jù)元素a1的結(jié)點。頭指