十套數(shù)據(jù)結(jié)構(gòu)試題及答案2

1、第2章線性表練習題答案一、填空向一個長度為n的向量的第i個元素(1WiWn+1)之前插入一個元素時，需向后移動n-i+1個元素。向一個長度為n的向量中刪除第i個元素(1WiWn)時，需向前移動n-i個元素。在順序表中訪問任意一結(jié)點的時間復(fù)雜度均為0(1)，因此，順序表也稱為隨機存取的數(shù) 據(jù)結(jié)構(gòu)。在單鏈表中，除了首元結(jié)點外，任一結(jié)點的存儲位置由其直接前驅(qū)結(jié)點的鏈域的指示。5在n個結(jié)點的單鏈表中要刪除已知結(jié)點*p，需找到它的前驅(qū)結(jié)點的地址，其時間復(fù)雜度0 (n)。二、判斷正誤(X)1.鏈表的每個結(jié)點中都恰好包含一個指針。答：錯誤。鏈表中的結(jié)點可含多個指針域，分別存放多個指針。例如，雙向鏈表中的結(jié)點

2、可 以含有兩個指針域，分別存放指向其直接前趨和直接后繼結(jié)點的指針。(X)2.鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序。錯，鏈表的存儲結(jié)構(gòu)特點是無序，而鏈表的示 意圖有序。(X)3.鏈表的刪除算法很簡單，因為當刪除鏈中某個結(jié)點后，計算機會自動地將后續(xù)的各個單元向 前移動。錯，鏈表的結(jié)點不會移動，只是指針內(nèi)容改變。(X)4.線性表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復(fù)雜類型。錯，混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，鏈表也是線性表！且即使是順序表，也能存放記錄型數(shù) 據(jù)。(X)5.順序表結(jié)構(gòu)適宜于進行順序存取，而鏈表適宜于進行隨機存取。錯，正好說反了。順序表才適合隨機存取，鏈表恰恰適于“順藤摸

3、瓜”(X)6.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。錯，前一半正確，但后一半說法錯誤，那是鏈式存儲的優(yōu)點。順序存儲方式插入、刪除運 算效率較低，在表長為n的順序表中，插入和刪除一個數(shù)據(jù)元素，平均需移動表長一半個數(shù) 的數(shù)據(jù)元素。(X)7.線性表在物理存儲空間中也一定是連續(xù)的。錯，線性表有兩種存儲方式，順序存儲和鏈式存儲。后者不要求連續(xù)存放。(X)8.線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。錯誤。線性表有兩種存儲方式，在順序存儲時，邏輯上相鄰的元素在存儲的物理位置次序 上也相鄰。(X)9.順序存儲方式只能用于存儲線性結(jié)構(gòu)。錯誤。順序存儲方式不僅能用于存

4、儲線性結(jié)構(gòu)，還可以用來存放非線性結(jié)構(gòu)，例如完全二叉 樹是屬于非線性結(jié)構(gòu)，但其最佳存儲方式是順序存儲方式。(X)10.線性表的邏輯順序與存儲順序總是一致的。錯，理由同7。鏈式存儲就無需一致。三、單項選擇題(C)數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址連續(xù)，數(shù)據(jù)間的邏輯關(guān)系依靠其物理地址間的 連續(xù)性來表達，稱之為：存儲結(jié)構(gòu)(B)邏輯結(jié)構(gòu)(C)順序存儲結(jié)構(gòu)(D)鏈式存儲結(jié)構(gòu)(B )一個向量第一個元素的存儲地址是100，每個元素的長度為2,則第5個元素的地址是(A) 110 (B) 108 (C) 100 (D) 120(A)在n個結(jié)點的順序表中，算法的時間復(fù)雜度是O (1)的操作是：訪問第i個結(jié)點(1W

5、iWn)和求第i個結(jié)點的直接前驅(qū)(2WiWn) (B)在第i個點 后插入一個新結(jié)點(1WiWn) (C)刪除第i個結(jié)點(1WiWn) (D)將n個結(jié)點從小到 大排序(B )向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動個元 素(A) 8(B) 63.5 (C) 63 (D) 72(A )鏈接存儲的存儲結(jié)構(gòu)所占存儲空間：分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針只有一部分，存放結(jié)點值只有一部分，存儲表示結(jié)點間關(guān)系的指針分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)(B)鏈表是一種采用存儲結(jié)構(gòu)存儲的線性表;(A)順序(B)鏈式(C)星式(D)網(wǎng)

6、狀(D)線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的(B)部分地址必須是連續(xù)的(C) 一定是不連續(xù)的(D)連續(xù)或不連續(xù) 都可以(B)線性表L在,情況下適用于使用鏈式結(jié)構(gòu)實現(xiàn)。(A)需經(jīng)常修改L中的結(jié)點值(B)需不斷對L進行刪除插入L中含有大量的結(jié)點(D)L中結(jié)點結(jié)構(gòu)復(fù)雜(C)單鏈表的存儲密度(A)大于1；(B)等于1；(C)小于1；(D)不能確定四、簡答題1.試比較順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)的優(yōu)缺點。在什么情況下用順序表比鏈表好？答：順序存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰(邏輯與物理統(tǒng)一)；要求內(nèi)存中可 用存儲單元的地址必須是連續(xù)的。優(yōu)點：存儲密度大(=1?),存儲空

7、間利用率高。缺點：插入或刪除元素時不方便。鏈式存儲時，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點值， 另一部分存放表示結(jié)點間關(guān)系的指針優(yōu)點：插入或刪除元素時很方便，使用靈活。缺點：存儲密度小(1)，存儲空間利用率低。順 序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。若線性表的長 度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操 作是插入、刪除操作，則采用鏈表。2 .描述以下三個概念的區(qū)別：頭指針、頭結(jié)點、首元結(jié)點(第一個元素結(jié)點)。在單鏈表中 設(shè)置頭結(jié)點的作用是什么？答：首元結(jié)點是指鏈表中存儲線性表中第一個數(shù)據(jù)元素a1的結(jié)點。為了操作方便，通常在 鏈表的首元結(jié)點之前附設(shè)一個結(jié)點，稱為頭結(jié)點，該結(jié)點的數(shù)據(jù)域中不存儲線性表的數(shù)據(jù)元 素，其作用是為了對鏈表進行操作時，可以對空表、非空表的情況以及對首元結(jié)點進行統(tǒng)一 處理。頭指針是指向鏈表中第一個結(jié)點(或為頭結(jié)點或為首元結(jié)點)的指針。若鏈表中 附設(shè)頭結(jié)點，則不管線性表是否為空表，頭指針均不為空。否則表示空表的鏈表的頭指針為 空。這三個概念對單鏈表、雙向鏈表和循環(huán)鏈表均