1、第1章 緒 論課后習(xí)題講解1.填空(1)()是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。【解答】數(shù)據(jù)元素3()是數(shù)據(jù)的最小單位，()是討論數(shù)據(jù)結(jié)構(gòu)時涉及的最小數(shù)據(jù)單位。【解答】數(shù)據(jù)項，數(shù)據(jù)元素 【分析】數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)元素以及數(shù)據(jù)元素之間的關(guān)系。 從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為( )、( )、( )和( )。【解答】集合，線性結(jié)構(gòu)，樹結(jié)構(gòu)，圖結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu)主要有( )和( )兩種基本方法，不論哪種存儲結(jié)構(gòu)，都要存儲兩方面的內(nèi)容：()和( )。【解答】順序存儲結(jié)構(gòu)，鏈接存儲結(jié)構(gòu)，數(shù)據(jù)元素，數(shù)據(jù)元素之間的關(guān)系 算法具有五個特性，分別是( )、( )、()、( )、(

2、)。【解答】有零個或多個輸入，有一個或多個輸出，有窮性，確定性，可行性 算法的描述方法通常有( )、( )、()和( )四種， 其中， ( )被稱為算法語言。【解答】自然語言，程序設(shè)計語言，流程圖，偽代碼，偽代碼 在一般情況下，一個算法的時間復(fù)雜度是( )的函數(shù)。【解答】問題規(guī)模設(shè)待處理問題的規(guī)模為n,若一個算法的時間復(fù)雜度為一個常數(shù)，則表示成數(shù)量級的形式為()，若為n*log25n，則表示成數(shù)量級的形式為()。【解答】0(1)，O(nlog2n)【分析】用大0記號表示算法的時間復(fù)雜度，需要將低次冪去掉，將最高次冪的系數(shù)去掉。2.選擇題 順序存儲結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由( )表示的，鏈

3、接存儲結(jié)構(gòu)中的數(shù)據(jù)元素之間的邏輯關(guān) 系是由( )表示的。A線性結(jié)構(gòu)B非線性結(jié)構(gòu)C存儲位置D指針【解答】C，D【分析】 順序存儲結(jié)構(gòu)就是用一維數(shù)組存儲數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素， 其邏輯關(guān)系由存儲位置(即元素在數(shù) 組中的下標(biāo))表示；鏈接存儲結(jié)構(gòu)中一個數(shù)據(jù)元素對應(yīng)鏈表中的一個結(jié)點，元素之間的邏輯關(guān)系由結(jié)點中 的指針表示。 假設(shè)有如下遺產(chǎn)繼承規(guī)則： 丈夫和妻子可以相互繼承遺產(chǎn)； 子女可以繼承父親或母親的遺產(chǎn)； 能相互繼承。則表示該遺產(chǎn)繼承關(guān)系的最合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是（ ）。A樹B圖C線性表D集合【解答】B【分析】將丈夫、妻子和子女分別作為數(shù)據(jù)元素，根據(jù)題意畫出邏輯結(jié)構(gòu)圖。 算法指的是（ ）。A對特定問題求

4、解步驟的一種描述，是指令的有限序列。B計算機程序C解決問題的計算方法D數(shù)據(jù)處理【解答】A【分析】計算機程序是對算法的具體實現(xiàn)；簡單地說，算法是解決問題的方法；數(shù)據(jù)處理是通過算法完成 的。所以，只有A是算法的準(zhǔn)確定義。 下面（ ）不是算法所必須具備的特性。A有窮性B確切性C高效性D可行性【解答】C【分析】高效性是好算法應(yīng)具備的特性。子女間不 算法分析的目的是（ ），算法分析的兩個主要方面是（ ）。A找出數(shù)據(jù)結(jié)構(gòu)的合理性B研究算法中輸入和輸出的關(guān)系C分析算法的效率以求改進D分析算法的易讀性和文檔性E空間性能和時間性能F正確性和簡明性G可讀性和文檔性H數(shù)據(jù)復(fù)雜性和程序復(fù)雜性【解答】C，E3.判斷題

5、算法的時間復(fù)雜度都要通過算法中的基本語句的執(zhí)行次數(shù)來確定。 【解答】錯。時間復(fù)雜度要通過算法中基本語句執(zhí)行次數(shù)的數(shù)量級來確定。 每種數(shù)據(jù)結(jié)構(gòu)都具備三個基本操作：插入、刪除和查找。 【解答】錯。如數(shù)組就沒有插入和刪除操作。此題注意是每種數(shù)據(jù)結(jié)構(gòu)。 所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)之間的邏輯關(guān)系。 【解答】錯。是數(shù)據(jù)之間的邏輯關(guān)系的整體。 邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。 【解答】對。因此邏輯結(jié)構(gòu)是數(shù)據(jù)組織的主要方面。 基于某種邏輯結(jié)構(gòu)之上的基本操作，其實現(xiàn)是唯一的。 【解答】錯。基本操作的實現(xiàn)是基于某種存儲結(jié)構(gòu)設(shè)計的，因而不是唯一的。4.分析以下各程序段，并用大0記號表示其執(zhí)行時間【解答】

6、基本語句是k=k+10*i，共執(zhí)行了n-2次，所以T(n)=O(n)。基本語句是k=k+10*i，共執(zhí)行了n次，所以T(n)=O(n)。 分析條件語句，每循環(huán)一次，i+j整體加1，共循環(huán)n次，所以T(n)=O(n)。 設(shè)循環(huán)體共執(zhí)行T(n)次，每循環(huán)一次，循環(huán)變量y加1，最終T(n)=y，即：仃(n)+1)2n，所以T(n)=0(n1/2)。x+是基本語句，所以5設(shè)有數(shù)據(jù)結(jié)構(gòu)(D, R),其中D=1,2, 3, 4, 5, 6，R=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)。 試畫出其邏輯結(jié)構(gòu)圖并指出屬于何種結(jié)構(gòu)【解答】其邏輯結(jié)構(gòu)圖如圖1-3

7、所示，它是一種圖結(jié)構(gòu)。6.為整數(shù)定義一個抽象數(shù)據(jù)類型， 包含整數(shù)的常見運算， 每個運算對應(yīng)一個基本操作， 每個基本操作的接 口需定義前置條件、輸入、功能、輸出和后置條件。【解答】整數(shù)的抽象數(shù)據(jù)類型定義如下：ADT integerData整數(shù)a：可以是正整數(shù)(1,2, 3,)、負(fù)整數(shù)(-1,-2,-3,)和零OperationConstructor前置條件：整數(shù)a不存在輸入：一個整數(shù)b功能：構(gòu)造一個與輸入值相同的整數(shù)輸出：無后置條件：整數(shù)a具有輸入的值Set前置條件：存在一個整數(shù)a輸入：一個整數(shù)b功能：修改整數(shù)a的值，使之與輸入的整數(shù)值相同輸出：無后置條件：整數(shù)a的值發(fā)生改變Add前置條件：存在

8、一個整數(shù)a輸入：一個整數(shù)b功能：將整數(shù)a與輸入的整數(shù)b相加輸出：相加后的結(jié)果后置條件：整數(shù)a的值發(fā)生改變Sub前置條件：存在一個整數(shù)a輸入：一個整數(shù)b功能：將整數(shù)a與輸入的整數(shù)b相減輸出：相減的結(jié)果后置條件：整數(shù)a的值發(fā)生改變Multi前置條件：存在一個整數(shù)a輸入：一個整數(shù)b功能：將整數(shù)a與輸入的整數(shù)b相乘 輸出：相乘的結(jié)果 后置條件：整數(shù)a的值發(fā)生改變Div前置條件：存在一個整數(shù)a輸入：一個整數(shù)b功能：將整數(shù)a與輸入的整數(shù)b相除 輸出：若整數(shù)b為零，則拋出除零異常，否則輸出相除的結(jié)果 后置條件：整數(shù)a的值發(fā)生改變Mod前置條件：存在一個整數(shù)a輸入：一個整數(shù)b功能：求當(dāng)前整數(shù)與輸入整數(shù)的模，即

9、正的余數(shù) 輸出：若整數(shù)b為零，則拋出除零異常，否則輸出取模的結(jié)果 后置條件：整數(shù)a的值發(fā)生改變Equal前置條件：存在一個整數(shù)a輸入：一個整數(shù)b功能：判斷整數(shù)a與輸入的整數(shù)b是否相等 輸出：若相等返回1，否則返回0后置條件：整數(shù)a的值不發(fā)生改變endADT7.求多項式A(x)的算法可根據(jù)下列兩個公式之一來設(shè)計：A(x)=anxn+an-1xn- 1+a1x+aOA(x)=(anx+an - 1)x+a1)x)+aO根據(jù)算法的時間復(fù)雜度分析比較這兩種算法的優(yōu)劣。【解答】第二種算法的時間性能要好些。第一種算法需執(zhí)行大量的乘法運算，而第二種算法進行了優(yōu)化， 減少了不必要的乘法運算。8.算法設(shè)計(要求

10、：算法用偽代碼和C+描述，并分析最壞情況下的時間復(fù)雜度) 對一個整型數(shù)組An設(shè)計一個排序算法。【解答】下面是簡單選擇排序算法的偽代碼描述。下面是簡單選擇排序算法的C+描述。分析算法，有兩層嵌套的for循環(huán)，所以， 找出整型數(shù)組An中元素的最大值和次最大值。【解答】算法的偽代碼描述如下：算法的C+描述如下:分析算法，只有一層循環(huán)，共執(zhí)行n-2次，所以，T(n)=O(n)。學(xué)習(xí)自測及答案1順序存儲結(jié)構(gòu)的特點是()，鏈接存儲結(jié)構(gòu)的特點是( )。【解答】用元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系，用指示元素存儲地址的指針表示 數(shù)據(jù)元素之間的邏輯關(guān)系。2.算法在發(fā)生非法操作時可以作出處理的特

11、性稱為( )。【解答】健壯性3.常見的算法時間復(fù)雜度用大0記號表示為：常數(shù)階()、對數(shù)階()、線性階()、平方階()和指數(shù)階()next=（p-next）-next 單鏈表中設(shè)置頭結(jié)點的作用是（ ）。【解答】為了運算方便【分析】例如在插入和刪除操作時不必對表頭的情況進行特殊處理。 非空的單循環(huán)鏈表由頭指針head指示，則其尾結(jié)點（由指針p所指）滿足（ ）。【解答】p-next=head【分析】如圖2-8所示。 在由尾指針rear指示的單循環(huán)鏈表中，在表尾插入一個結(jié)點s的操作序列是（ ）；刪除開始結(jié)點的操 作序列為（ ）。【解答】s-next =rear-next; rear-next =s;

12、rear =s; q=rear-next-next;rear-next-next=q-next; deIete q;【分析】操作示意圖如圖2-9所示： 一個具有n個結(jié)點的單鏈表，在指針p所指結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為（ ）；在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為（ ）。【解答】O（1）,0（n）【分析】在p所指結(jié)點后插入一個新結(jié)點只需修改指針，所以時間復(fù)雜度為0（1）;而在給定值為x的結(jié)點后插入一個新結(jié)點需要先查找值為x的結(jié)點，所以時間復(fù)雜度為0（n）。 可由一個尾指針唯一確定的鏈表有（ ）、（ ）、（ ）。【解答】循環(huán)鏈表，循環(huán)雙鏈表，雙鏈表2.選擇題 線性表的順序存儲結(jié)構(gòu)

13、是一種（ ）的存儲結(jié)構(gòu)，線性表的鏈接存儲結(jié)構(gòu)是一種（ ）的存儲結(jié)構(gòu)。A隨機存取B順序存取C索引存取D散列存取【解答】A，B【分析】參見2.2.1。 線性表采用鏈接存儲時，其地址（ ）。A必須是連續(xù)的B部分地址必須是連續(xù)的C一定是不連續(xù)的D連續(xù)與否均可以【解答】D【分析】線性表的鏈接存儲是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，這組存儲單元可以連續(xù)，也 可以不連續(xù)，甚至可以零散分布在內(nèi)存中任意位置。 單循環(huán)鏈表的主要優(yōu)點是（ ）。A不再需要頭指針了B從表中任一結(jié)點出發(fā)都能掃描到整個鏈表;C已知某個結(jié)點的位置后，能夠容易找到它的直接前趨;D在進行插入、刪除操作時，能更好地保證鏈表不斷開。【解答】

14、B 鏈表不具有的特點是（ ）。A可隨機訪問任一元素B插入、刪除不需要移動元素C不必事先估計存儲空間D所需空間與線性表長度成正比【解答】A 若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨， 則采用（ ）存儲方法最節(jié)省時間。A順序表B單鏈表C雙鏈表D單循環(huán)鏈表【解答】A【分析】線性表中最常用的操作是取第i個元素，所以，應(yīng)選擇隨機存取結(jié)構(gòu)即順序表，同時在順序表中 查找第i個元素的前趨也很方便。單鏈表和單循環(huán)鏈表既不能實現(xiàn)隨機存取，查找第i個元素的前趨也不方便，雙鏈表雖然能快速查找第i個元素的前趨，但不能實現(xiàn)隨機存取。 若鏈表中最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除第一個結(jié)點，

15、則采用( )存儲方法 最節(jié)省時間。A單鏈表B帶頭指針的單循環(huán)鏈表C雙鏈表D帶尾指針的單循環(huán)鏈表【解答】D【分析】在鏈表中的最后一個結(jié)點之后插入一個結(jié)點需要知道終端結(jié)點的地址，所以，單鏈表、帶頭指針 的單循環(huán)鏈表、雙鏈表都不合適，考慮在帶尾指針的單循環(huán)鏈表中刪除第一個結(jié)點，其時間性能是O(1)， 所以，答案是D。 若鏈表中最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除最后一個結(jié)點， 則采用( )存儲方 法最節(jié)省運算時間。A單鏈表B循環(huán)雙鏈表C單循環(huán)鏈表D帶尾指針的單循環(huán)鏈表【解答】B【分析】在鏈表中的最后一個結(jié)點之后插入一個結(jié)點需要知道終端結(jié)點的地址，所以，單鏈表、單循環(huán)鏈 表都不合適，刪除

16、最后一個結(jié)點需要知道終端結(jié)點的前驅(qū)結(jié)點的地址，所以，帶尾指針的單循環(huán)鏈表不合 適，而循環(huán)雙鏈表滿足條件。 在具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復(fù)雜度是( )。A O(1) B O(n) C O(n2) D O(nlog2n)【解答】B【分析】首先應(yīng)順序查找新結(jié)點在單鏈表中的位置。 對于n個元素組成的線性表，建立一個有序單鏈表的時間復(fù)雜度是( )。A O(1) B O(n) C O(n2) D O(nlog2n)【解答】C【分析】該算法需要將n個元素依次插入到有序單鏈表中，而插入每個元素需O(n)。 使用雙鏈表存儲線性表，其優(yōu)點是可以( )。A提高查找速度B更方便數(shù)據(jù)的插入

17、和刪除C節(jié)約存儲空間D很快回收存儲空間【解答】B【分析】在鏈表中一般只能進行順序查找，所以，雙鏈表并不能提高查找速度，因為雙鏈表中有兩個指針 域，顯然不能節(jié)約存儲空間，對于動態(tài)存儲分配，回收存儲空間的速度是一樣的。由于雙鏈表具有對稱性， 所以，其插入和刪除操作更加方便。(11)在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的直接前驅(qū)，若在q和p之間插入s所指結(jié)點，則執(zhí)行( )操作。A s-next=p-next; p-next=s; B q-next=s; s-next=p;C p-next=s-next; s-next=p; D p-next=s; s-next=q;【解答】B【分析】注意此題是

18、在q和p之間插入新結(jié)點，所以，不用考慮修改指針的順序。(12)在循環(huán)雙鏈表的p所指結(jié)點后插入s所指結(jié)點的操作是()。A p-next=s; s-prior=p; p-next-prior=s; s-next=p-next;B p-next=s; p-next-prior=s; s-prior=p; s-next=p-next;C s-prior=p; s-next=p-next; p-next=s; p-next-prior=s;D s-prior=p; s-next=p-next; p-next-prior=s; p-next=s【解答】D【分析】在鏈表中，對指針的修改必須保持線性表的邏輯關(guān)

19、系，否則，將違背線性表的邏輯特征，圖2-10給出備選答案C和D的圖解。3.判斷題 線性表的邏輯順序和存儲順序總是一致的。 【解答】錯。順序表的邏輯順序和存儲順序一致，鏈表的邏輯順序和存儲順序不一定一致。 線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈接存儲結(jié)構(gòu)。【解答】錯。兩種存儲結(jié)構(gòu)各有優(yōu)缺點。 設(shè)p,q是指針，若p=q,則*p=*q。【解答】錯。p=q只能表示p和q指向同一起始地址，而所指類型則不一定相同。 線性結(jié)構(gòu)的基本特征是：每個元素有且僅有一個直接前驅(qū)和一個直接后繼。 【解答】錯。每個元素最多只有一個直接前驅(qū)和一個直接后繼，第一個元素沒有前驅(qū)，最后一個元素沒有 后繼。 在單鏈表中，要取得某個元素，只要知

20、道該元素所在結(jié)點的地址即可，因此單鏈表是隨機存取結(jié)構(gòu)。 【解答】錯。要找到該結(jié)點的地址，必須從頭指針開始查找，所以單鏈表是順序存取結(jié)構(gòu)。4請說明順序表和單鏈表各有何優(yōu)缺點，并分析下列情況下，采用何種存儲結(jié)構(gòu)更好些。 若線性表的總長度基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素。 如果n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化。 描述一個城市的設(shè)計和規(guī)劃。【解答】順序表的優(yōu)點： 無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲空間；可以快速地存取表中任一位置的元素(即隨機存取)。順序表的缺點：插入和刪除操作需移動大量元素； 表的容量難以確定； 造成存

21、儲空間的“碎片”。單鏈表的優(yōu)點： 不必事先知道線性表的長度；插入和刪除元素時只需修改指針，不用移動元素。單鏈表的缺點： 指針的結(jié)構(gòu)性開銷； 存取表中任意元素不方便，只能進行順序存取。 應(yīng)選用順序存儲結(jié)構(gòu)。 因為順序表是隨機存取結(jié)構(gòu)， 單鏈表是順序存取結(jié)構(gòu)。 本題很少進行插入和刪除 操作，所以空間變化不大，且需要快速存取，所以應(yīng)選用順序存儲結(jié)構(gòu)。 應(yīng)選用鏈接存儲結(jié)構(gòu)。鏈表容易實現(xiàn)表容量的擴充，適合表的長度動態(tài)發(fā)生變化。 應(yīng)選用鏈接存儲結(jié)構(gòu)。 因為一個城市的設(shè)計和規(guī)劃涉及活動很多， 需要經(jīng)常修改、 擴充和刪除各種信息， 才能適應(yīng)不斷發(fā)展的需要。而順序表的插入、刪除的效率低，故不合適。5算法設(shè)計設(shè)計

22、一個時間復(fù)雜度為O(n)的算法，實現(xiàn)將數(shù)組An中所有元素循環(huán)右移k個位置。 【解答】算法思想請參見主教材第一章思想火花。下面給出具體算法。分析算法，第一次調(diào)用Reverse函數(shù)的時間復(fù)雜度為O(k)，第二次調(diào)用Reverse函數(shù)的時間復(fù)雜度為O(n-k)，第三次調(diào)用Reverse函數(shù)的時間復(fù)雜度為O(n)，所以，總的時間復(fù)雜度為O(n)。 已知數(shù)組An中的元素為整型，設(shè)計算法將其調(diào)整為左右兩部分，左邊所有元素為奇數(shù)，右邊所有元 素為偶數(shù)，并要求算法的時間復(fù)雜度為O(n)。【解答】從數(shù)組的兩端向中間比較，設(shè)置兩個變量i和j，初始時i=0,j=n-1,若Ai為偶數(shù)并且Aj為奇數(shù)，則將Ai與Aj交換

23、。具體算法如下：分析算法，兩層循環(huán)將數(shù)組掃描一遍，所以，時間復(fù)雜度為O(n)。 試編寫在無頭結(jié)點的單鏈表上實現(xiàn)線性表的插入操作的算法， 并和帶頭結(jié)點的單鏈表上的插入操作的實 現(xiàn)進行比較。【解答】參見2.2.3。 試分別以順序表和單鏈表作存儲結(jié)構(gòu)，各寫一實現(xiàn)線性表就地逆置的算法。【解答】順序表的逆置，即是將對稱元素交換，設(shè)順序表的長度為length， 則將表中第i個元素與第length-i-1個元素相交換。具體算法如下：單鏈表的逆置請參見2.2.4算法2-4和算法2-6。 假設(shè)在長度大于1的循環(huán)鏈表中，即無頭結(jié)點也無頭指針，s為指向鏈表中某個結(jié)點的指針，試編寫算 法刪除結(jié)點s的前趨結(jié)點。【解答】

24、利用單循環(huán)鏈表的特點，通過指針s可找到其前驅(qū)結(jié)點r以及r的前驅(qū)結(jié)點p,然后將結(jié)點r刪除，如圖2-11所示，具體算法如下： 已知一單鏈表中的數(shù)據(jù)元素含有三類字符：字母、數(shù)字和其他字符。試編寫算法，構(gòu)造三個循環(huán)鏈表， 使每個循環(huán)鏈表中只含同一類字符。【解答】在單鏈表A中依次取元素，若取出的元素是字母，把它插入到字母鏈表B中，若取出的元素是數(shù)字，則把它插入到數(shù)字鏈表D中，直到鏈表的尾部，這樣表B，D, A中分別存放字母、數(shù)字和其他字符。 具體算法如下： 設(shè)單鏈表以非遞減有序排列，設(shè)計算法實現(xiàn)在單鏈表中刪去值相同的多余結(jié)點。【解答】從頭到尾掃描單鏈表，若當(dāng)前結(jié)點的元素值與后繼結(jié)點的元素值不相等，則指針

25、后移；否則刪除 該后繼結(jié)點。具體算法如下： 判斷帶頭結(jié)點的雙循環(huán)鏈表是否對稱。【解答】設(shè)工作指針p和q分別指向循環(huán)雙鏈表的開始結(jié)點和終端結(jié)點，若結(jié)點p和結(jié)點q的數(shù)據(jù)域相等,則工作指針p后移，工作指針q前移，直到指針p和指針q指向同一結(jié)點 (循環(huán)雙鏈表中結(jié)點個數(shù)為奇數(shù)) 或結(jié)點q成為結(jié)點p的前驅(qū)(循環(huán)雙鏈表中結(jié)點個數(shù)為偶數(shù))。如圖2-12所示。學(xué)習(xí)自測及答案1.已知一維數(shù)組A采用順序存儲結(jié)構(gòu)，每個元素占用4個存儲單元，第9個元素的地址為144，則第一個 元素的地址是( )。A 108 B 180 C 176 D 112【解答】D2在長度為n的線性表中查找值為x的數(shù)據(jù)元素的時間復(fù)雜度為： ( )。

26、A O(0) B O(1) C O(n) D O(n2)【解答】C3.在一個長度為n的順序表的第i(1in+1)個元素之前插入一個元素，需向后移動()個元素，刪除第i(1in)個元素時，需向前移動()個元素。【解答】n-i+1，n-i4.在單鏈表中， 除了頭結(jié)點以外，任一結(jié)點的存儲位置由()指示。 【解答】其前趨結(jié)點的指針域5.當(dāng)線性表采用順序存儲結(jié)構(gòu)時，其主要特點是()。 【解答】邏輯結(jié)構(gòu)中相鄰的結(jié)點在存儲結(jié)構(gòu)中仍相鄰6.在雙鏈表中，每個結(jié)點設(shè)置了兩個指針域，其中一個指向()結(jié)點，另一個指向( )結(jié)點。 【解答】前驅(qū)，后繼7設(shè)A是一個線性表(a1, a2,，an)，采用順序存儲結(jié)構(gòu)，則在等概

27、率的前提下，平均每插入一個元素需要移動的元素個數(shù)為多少？若元素插在ai與ai+1之間(1inext; B x=top-data;C top=top-next; x=top-data; D x=top-data; top=top-next;【解答】D4.設(shè)元素1, 2, 3, P, A依次經(jīng)過一個棧，進棧次序為123PA在棧的輸出序列中，有哪些序列可作為C+程序設(shè)計語言的變量名。【解答】PA321, P3A21, P32A1, P321A, AP3215.設(shè)S=I_ am_ a_ teacther，其長度為（ ）。【解答】15第4章 廣義線性表多維數(shù)組和廣義表課后習(xí)題講解1.填空 數(shù)組通常只有兩

28、種運算：（ ）和（ ），這決定了數(shù)組通常采用（ ）結(jié)構(gòu)來實現(xiàn)存儲。 【解答】存取，修改，順序存儲【分析】數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)集合，在數(shù)組上一般不能做插入、刪除元素的操作。除了 初始化和銷毀之外，在數(shù)組中通常只有存取和修改兩種操作。 二維數(shù)組A中行下標(biāo)從10到20，列下標(biāo)從5到10，按行優(yōu)先存儲，每個元素占4個存儲單元，A105的存儲地址是1000，則元素A1510的存儲地址是（ ）。【解答】1140【分析】數(shù)組A中每行共有6個元素，元素A1510的前面共存儲了（15-10）X6+5個元素，每個元素占4個存儲單元，所以，其存儲地址是1000+140=1140。 設(shè)有一個10階的對稱

29、矩陣A采用壓縮存儲，A00為第一個元素，其存儲地址為d,每個元素占1個 存儲單元，則元素A85的存儲地址為（ ）。【解答】d+41【分析】元素A85的前面共存儲了（1+2+8）+5=41個元素。 稀疏矩陣一般壓縮存儲方法有兩種，分別是( )和( )。【解答】三元組順序表，十字鏈表 廣義表(a), (b),c),(d)的長度是( )，深度是( )，表頭是( )，表尾是( ) 【解答】3，4，(a)，(b),c),(d)已知廣義表LS=(a,(b,c,d),e)，用Head和Tail函數(shù)取出LS中原子b的運算是()。【解答】Head(Head(Tail(LS)2.選擇題 二維數(shù)組A的每個元素是由6

30、個字符組成的串，行下標(biāo)的范圍從08,列下標(biāo)的范圍是從09，則存放A至少需要()個字節(jié)，A的第8列和第5行共占()個字節(jié)，若A按行優(yōu)先方式存儲，元素A85的起始地址與當(dāng)A按列優(yōu)先方式存儲時的()元素的起始地址一致。A 90 B 180 C 240 D 540 E 108 F 114 G 54H A85 I A310 J A58 K A49【解答】D，E，K【分析】數(shù)組A為9行10列，共有90個元素，所以，存放A至少需要90X6=540個存儲單元，第8列和 第5行共有18個元素(注意行列有一個交叉元素)，所以，共占108個字節(jié)，元素A85按行優(yōu)先存儲 的起始地址為d+8X10+5=d+85設(shè)元素A

31、ij按列優(yōu)先存儲的起始地址與之相同，則d+jX9+i=d+85，解此方程，得i=4，j=9。 將數(shù)組稱為隨機存取結(jié)構(gòu)是因為()A數(shù)組元素是隨機的B對數(shù)組任一元素的存取時間是相等的C隨時可以對數(shù)組進行訪問D數(shù)組的存儲結(jié)構(gòu)是不定【解答】B 下面的說法中，不正確的是()A數(shù)組是一種線性結(jié)構(gòu)B數(shù)組是一種定長的線性結(jié)構(gòu)C除了插入與刪除操作外，數(shù)組的基本操作還有存取、修改、檢索和排序等D數(shù)組的基本操作有存取、修改、檢索和排序等，沒有插入與刪除操【解答】C【分析】 數(shù)組屬于廣義線性表， 數(shù)組被創(chuàng)建以后， 其維數(shù)和每維中的元素個數(shù)是確定的， 所以，數(shù)組通常 沒有插入和刪除操作。 對特殊矩陣采用壓縮存儲的目的主

32、要是為了()A表達(dá)變得簡單B對矩陣元素的存取變得簡單C去掉矩陣中的多余元素D減少不必要的存儲空間【解答】D【分析】 在特殊矩陣中， 有很多值相同的元素并且他們的分布有規(guī)律， 沒有必要為值相同的元素重復(fù)存儲。 下面()不屬于特殊矩陣。A對角矩陣B三角矩陣C稀疏矩陣D對稱矩陣【解答】C 若廣義表A滿足Head(A)=Tail(A)，則A為( )A ( ) B ( ) C ( ),( ) D( ),( ),( )【解答】B 下面的說法中，不正確的是( )A廣義表是一種多層次的結(jié)構(gòu)B廣義表是一種非線性結(jié)構(gòu)C廣義表是一種共享結(jié)構(gòu)D廣義表是一種遞歸【解答】B【分析】從各層元素各自具有的線性關(guān)系講，廣義表屬

33、于線性結(jié)構(gòu)。 下面的說法中，不正確的是( )A對稱矩陣只須存放包括主對角線元素在內(nèi)的下(或上)三角的元素即可。B對角矩陣只須存放非零元素即可。C稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲。D稀疏矩陣中大量值為零的元素分布有規(guī)律，因此可以采用三元組表方法存儲【解答】D【分析】 稀疏矩陣中大量值為零的元素分布沒有規(guī)律， 因此采用三元組表存儲。 如果零元素的分布有規(guī)律， 就沒有必要存儲非零元素的行號和列號，而需要按其壓縮規(guī)律找出相應(yīng)的映象函數(shù)。3.判斷題 數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的，也不是樹形的。 【解答】錯。例如二維數(shù)組可以看成是數(shù)據(jù)元素為線性表的線性表。 使用三元組表存儲稀疏矩陣的元素，有時并不能節(jié)省存儲空間。【解答】對。因為三元組表除了存儲非零元素值外，還需要存儲其行號和列號。 稀疏矩陣壓縮存儲后，必會失去隨機存取功能。【解答】對。因為壓縮存儲后，非零元素的存儲位置和行號、列號之間失去了確定的關(guān)系。 線性表可以看成是廣義表的