《數(shù)據(jù)結(jié)構(gòu)與算法》線性表習(xí)題

《數(shù)據(jù)結(jié)構(gòu)與算法》線性表習(xí)題第2部分習(xí)題精選一、填空.在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)元素，具體移動(dòng)的元素個(gè)數(shù)與有關(guān)。.線性表中結(jié)點(diǎn)的集合是的，結(jié)點(diǎn)間的關(guān)系是的。.向一個(gè)長(zhǎng)度為n的向量的第i個(gè)元素（IWiWn+l）之前插入一個(gè)元素時(shí)，需向后移動(dòng)個(gè)元素。.向一個(gè)長(zhǎng)度為n的向量中刪除第i個(gè)元素（IWiWn）時(shí)，需向前移動(dòng)個(gè)元素。.在順序表中訪問(wèn)任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為,因此，順序表也稱為的數(shù)據(jù)結(jié)構(gòu)。.順序表中邏輯上相鄰的元素的物理位置相鄰。單鏈表中邏輯上相鄰的元素的物理位置相鄰。.在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由指示。.在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p,需找到它的,其時(shí)間復(fù)雜度為。二、判斷正誤（在正確的說(shuō)法后面打勾，反之打叉）（）1.鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。（）2.鏈表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序。（）3.鏈表的刪除算法很簡(jiǎn)單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)地將后續(xù)的各個(gè)單元向前移動(dòng)。（）4.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類(lèi)型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類(lèi)型。（）5.順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。（）6.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。（）7.線性表在物理存儲(chǔ)空間中也一定是連續(xù)的。（）8.線性表在順序存儲(chǔ)時(shí)，邏輯上相鄰的元素未必在存儲(chǔ)的物理位置次序上相鄰。（）9.順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。（）10.線性表的邏輯順序與存儲(chǔ)順序總是一致的。三、單項(xiàng)選擇題（）I.數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：（A）存儲(chǔ)結(jié)構(gòu)（B）邏輯結(jié)構(gòu)（C）順序存儲(chǔ)結(jié)構(gòu)（D）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（）2.一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100,每個(gè)元素的長(zhǎng)度為2,則第5個(gè)元素的地址是（A）110（B）108（C）100（D）120（）3.在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是0（1）的操作是：訪問(wèn)第i個(gè)結(jié)點(diǎn)（IWiWn）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2WiWn）在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（iWiWn）刪除第i個(gè)結(jié)點(diǎn)（IWiWn）（D）將n個(gè)結(jié)點(diǎn)從小到大排序

()4.向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng)個(gè)元素(A)8(B)63.5(C)63(D)7()5.鏈接存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間：分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針只有一部分，存放結(jié)點(diǎn)值(C)只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針(D)分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)()6.鏈表是一種采用存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表；(A)順序(B)鏈?zhǔn)?C)星式(D)網(wǎng)狀()7.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址：(A)必須是連續(xù)的(B)部分地址必須是連續(xù)的一定是不連續(xù)的(D)連續(xù)或不連續(xù)都可以()8.線性表L在情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。(A)需經(jīng)常修改L中的結(jié)點(diǎn)值(B)需不斷對(duì)'L進(jìn)行刪除插入(C)L中含有大量的結(jié)點(diǎn)(D)L中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜()9.單鏈表的存儲(chǔ)密度(A)大于1；(B)等于1；(C)小于1；(D)不能確定精選習(xí)題答案一、填空I.表中一半表長(zhǎng)和該元素在表中的位置2.有限一對(duì)一3.n-i+14.n-i5.0(1)隨機(jī)存取6.必定不一定7.其直接前驅(qū)結(jié)點(diǎn)的鏈域的值8.前驅(qū)結(jié)點(diǎn)的地址O(n)(X)答：錯(cuò)誤。鏈表中的結(jié)點(diǎn)可含多個(gè)指針域，分別存放多個(gè)指針。例如，雙向鏈表中的結(jié)點(diǎn)可以含有兩個(gè)指針域，分別存放指向其直接前趨和直接后繼結(jié)點(diǎn)的指針。(X)錯(cuò)，鏈表的存儲(chǔ)結(jié)構(gòu)特點(diǎn)是無(wú)序，而鏈表的示意圖有序。(X)錯(cuò)，鏈表的結(jié)點(diǎn)不會(huì)移動(dòng)，只是指針內(nèi)容改變。(X)錯(cuò)，混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，鏈表也是線性表！且即使是順序表，也能存放記錄型數(shù)據(jù)。(X)錯(cuò)，正好說(shuō)反了。順序表才適合隨機(jī)存取，鏈表恰恰適于“順藤摸瓜”(X)錯(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)錯(cuò)，線性表有兩種存儲(chǔ)方式，順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。后者不要求連續(xù)存放。(X)錯(cuò)誤。線性表有兩種存儲(chǔ)方式，在順序存儲(chǔ)時(shí)，邏輯上相鄰的元素在存儲(chǔ)的物理位置次序上也相鄰。9.(X)錯(cuò)誤。順序存儲(chǔ)方式不僅能用于存儲(chǔ)線性結(jié)構(gòu)，還可以用來(lái)存放非線性結(jié)構(gòu)，例如完全二叉樹(shù)是屬于非線性結(jié)構(gòu)