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

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

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

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

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

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

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

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