數(shù)據(jù)結(jié)構(gòu)(Java)復(fù)習(xí)題及答案2線性表

1、第2章線性表 一、填空 1. 在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng) 一半的元素，具體移動(dòng)的元素個(gè)數(shù)與 插入位置有關(guān)。 2. 向一個(gè)長度為n的向量的第i個(gè)元素(K i n+1)之前插入一個(gè)元素時(shí)，需向后移動(dòng)n-i+1 個(gè)元素。 3. 向一個(gè)長度為n的向量中刪除第i個(gè)元素(K i n)時(shí)，需向前移動(dòng) n-i個(gè)元素。 4. 在順序表中訪問任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為 0，因此,順序表也稱為隨機(jī)讀取的 數(shù)據(jù)結(jié)構(gòu)。 5順序表中邏輯上相鄰的元素的物理位置也相鄰。單鏈表中邏輯上相鄰的元素的物理位 置不一定相鄰。 6. 在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲位置由前驅(qū)節(jié)點(diǎn)的引用域指示。 7. 在n個(gè)結(jié)

2、點(diǎn)的單鏈表 中要?jiǎng)h除已知結(jié)點(diǎn)*p,需找到它的存儲位置,其時(shí)間復(fù)雜度為 0 (n)o 8 鏈表中邏輯上相鄰的元素的物理位置環(huán)一定一相連。 在單鏈表中除首結(jié)點(diǎn)外，任意結(jié)點(diǎn)的存儲位置都由前驅(qū) 結(jié)點(diǎn)中的引用指示。 (3)在單鏈表中，設(shè)置頭結(jié)點(diǎn)的作用是在插入或刪除首結(jié)點(diǎn)時(shí)不必對頭指針一進(jìn)行處理 二、判斷正誤VX (V) 1 鏈表的每個(gè)結(jié)點(diǎn)中都包含一個(gè)引用域。 (X ) 2鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序。 (X ) 3鏈表的刪除算法很簡單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會自動(dòng)將后續(xù)各個(gè)單元向 前移動(dòng)。 (X ) 4順序表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。 X )

3、5順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。 (X ) 6順序存儲方式的優(yōu)點(diǎn)是存儲密度大，且插入、刪除運(yùn)算效率高。 X ) 7線性表在物理存儲空間中也一定是連續(xù)的。 (V ) 8線性表在順序存儲時(shí)，邏輯上相鄰的元素在存儲的物理位置次序上相鄰。 (X ) 9順序存儲方式只能用于存儲線性結(jié)構(gòu)。 X ) 10線性表的邏輯順序與存儲順序總是一致的。 (V ) 11 順序存儲的線性表的插入和刪除操作需要付出很大的代價(jià)，因?yàn)槠骄看尾僮饔?近一半 的元素需要移動(dòng)。 (V ) 12線性表中的元素可以是各種各樣的但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此是 屬于同一數(shù)據(jù)對象。 三、單項(xiàng)選擇題

4、(C ) 1 數(shù)據(jù)在計(jì)算機(jī)存儲器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為： (A) 存儲結(jié)構(gòu)(B)邏輯結(jié)構(gòu)(C)順序存儲結(jié)構(gòu) (D)鏈?zhǔn)酱鎯Y(jié)構(gòu) (B) 2. 一個(gè)數(shù)組第一個(gè)元素的存儲地址是100,每個(gè)元素的長度為2,則第5個(gè)元素的地址 是 (A) 110( B) 108( C) 100( D) 120 (A)3在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是0 (1)的操作是： (A) 訪問第i個(gè)結(jié)點(diǎn)(K i n)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)(2 i n) (B) 在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)(K i n) (0刪除第i個(gè)結(jié)點(diǎn)(K i n) (D)將n個(gè) 結(jié)點(diǎn)從小到大排序 (B ) 4線性表

5、L在情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。 (A)需經(jīng)常修改L中的結(jié)點(diǎn)值(E)需不斷對L進(jìn)行刪除插入 (0L中含有大量的結(jié)點(diǎn)(D)L中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜 (A ) 5鏈接存儲的存儲結(jié)構(gòu)所占存儲空間： 17 17 17 )/ A B c D /V /( / 分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的引用 只有一部分，存放結(jié)點(diǎn)值 只有一部分，存儲表示結(jié)點(diǎn)間關(guān)系的引用 分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù) (B ) 6鏈表是一種采用存儲結(jié)構(gòu)存儲的線性表； (A)順序(B)鏈?zhǔn)?C)星式(D)網(wǎng)狀 (D ) 7線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲單元的地址: (A)必須是連續(xù)的(B)部分地址必須是連續(xù)的 (0 一定是不連續(xù)的(D)連續(xù)或不連續(xù)都可以 (C ) 8在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成( (A)動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)(B)緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) (0線性結(jié)構(gòu)和非線性結(jié)構(gòu)(D)內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) 四、簡答題 1試比較順序存儲