數(shù)據(jù)結(jié)構(gòu)(清華大學出版社)第2章習題.doc

第2章：線性表 1. 理解線性表的定義和邏輯結(jié)構(gòu)特性；填空題：1、 線性表中結(jié)點的集合是 有限 的，結(jié)點間的關(guān)系是 一對一 的。2、 線性表的存儲方式分為 順序存儲 和 鏈式存儲 。判斷題：1、（）線性表的每個結(jié)點只能是一個簡單類型，而鏈表每個結(jié)點可以是一個復雜類型。錯，混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，鏈表也是線性表！且即使是順序表，也能存放記錄型數(shù)據(jù)。 2、（）線性表在物理存儲空間中也一定是連續(xù)的。錯，線性表有兩種存儲方式，順序存儲和鏈式存儲。后者不要求連續(xù)存放。3、（）線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。錯，線性表有兩種存儲方式，在順序存儲時，邏輯上相鄰的元素在存儲的物理位置次序上也相鄰。4、 （）線性表的邏輯順序與存儲順序總是一致的。錯，鏈式存儲就無需一致。簡答題：1、試比較線性表的兩種存儲結(jié)構(gòu)的優(yōu)缺點。在什么情況下用順序表比鏈表好？答： 順序存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。優(yōu)點：存儲密度大（1？），存儲空間利用率高。缺點：插入或刪除元素時不方便。鏈式存儲時，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲空間分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針優(yōu)點：插入或刪除元素時很方便，使用靈活。缺點：存儲密度?。?），存儲空間利用率低。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。2. 掌握線性表的順序存儲方法和基本操作算法實現(xiàn)，會計算地址；填空題：1、在順序表中插入或刪除一個元素，需要平均移動 表中一半 元素，具體移動的元素個數(shù)與 表長和該元素在表中的位置 有關(guān)。2、 向一個長度為n的向量的第i個元素(1in+1)之前插入一個元素時，需向后移動 n-i+1 個元素。3、向一個長度為n的向量中刪除第i個元素(1in)時，需向前移動 n-i 個元素。4、 在順序表中訪問任意一結(jié)點的時間復雜度均為 O(1) ，因此，順序表也稱為 隨機存取 的數(shù)據(jù)結(jié)構(gòu)。5、 順序表中邏輯上相鄰的元素的物理位置 必定 相鄰。單鏈表中邏輯上相鄰的元素的物理位置 不一定 相鄰。選擇題：（ C ）1、數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址相同并連續(xù)，稱之為： （A）存儲結(jié)構(gòu) （B）邏輯結(jié)構(gòu) （C）順序存儲結(jié)構(gòu) （D）鏈式存儲結(jié)構(gòu)（ B ）2、一個向量第一個元素的存儲地址是100，每個元素長度為2，則第5個元素的地 址是 （A）110 （B）108 （C）100 （D）120（ A ）3、 在n個結(jié)點的順序表中，算法的時間復雜度是O（1）的操作是： （A）訪問第i個結(jié)點（1in）和求第i個結(jié)點的直接前驅(qū)（2in） （B）在第i個結(jié)點后插入一個新結(jié)點（1in） （C）刪除第i個結(jié)點（1in） （D）將n個結(jié)點從小到大排序（ B ）4、向一個有127個元素的順序表中插入一個新元素并保持原來順序，平均要移 動 個元素 （A）8 （B）63.5 （C）63 （D）7判斷題：1、（）順序表結(jié)構(gòu)適宜于進行順序存取，而鏈表適宜于進行隨機存取。 錯，正好說反了。順序表才適合隨機存取，鏈表恰恰適于“順藤摸瓜”2、（）序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。錯，前一半正確，但后一半說法錯誤，那是鏈式存儲的優(yōu)點。順序存儲方式插入、刪除運算效率較低，在表長為n的順序表中，插入和刪除一個數(shù)據(jù)元素，平均需移動表長一半個數(shù)的數(shù)據(jù)元素。3、（）順序存儲方式只能用于存儲線性結(jié)構(gòu)。錯，順序存儲方式不僅能用于存儲線性結(jié)構(gòu)，還可以用來存放非線性結(jié)構(gòu)，例如完全二叉樹是屬于非線性結(jié)構(gòu)，但其最佳存儲方式是順序存儲方式。3. 掌握線性表的鏈式存儲方法和基本操作算法實現(xiàn)；填空題：1、 在單鏈表中，除了首元結(jié)點外，任一結(jié)點的存儲位置由 其直接前驅(qū)結(jié)點的鏈域的值 指示。2、 在n個結(jié)點的單鏈表中要刪除已知結(jié)點*p，需找到它的 前驅(qū)結(jié)點的地址 ，其時間復雜度為O（n）。選擇題：（ A ）1、 鏈接存儲的存儲結(jié)構(gòu)所占存儲空間： （A）分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針 （B）只有一部分，存放結(jié)點值 （C）只有一部分，存儲表示結(jié)點間關(guān)系的指針 （D）分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)（ B ）2、鏈表是一種采用 存儲結(jié)構(gòu)存儲的線性表； （A）順序 （B）鏈式 （C）星式 （D）網(wǎng)狀（ D ）3、線性表若采用鏈式存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址: （A）必須是連續(xù)的 （B）部分地址必須是連續(xù)的 （C）一定是不連續(xù)的 （D）連續(xù)或不連續(xù)都可以（ B ）4、線性表在 情況下適用于使用鏈式結(jié)構(gòu)實現(xiàn)。 （）需經(jīng)常修改中的結(jié)點值 （）需不斷對進行刪除插入 （）中含有大量的結(jié)點 （）中結(jié)點結(jié)構(gòu)復雜（ C ）5、單鏈表的存儲密度 （）大于1； （）等于1； （）小于1； （）不能確定（ B ）6、設a1、a2、a3為3個結(jié)點，P0，3，4代表地址，則如下的鏈式存儲結(jié)構(gòu)稱為P034P0a13a24a30 （）循環(huán)鏈表 （）單鏈表 （）雙向循環(huán)鏈表 （）雙向鏈表判斷題：1、（）鏈表的每個結(jié)點中都恰好包含一個指針。 錯，鏈表中的結(jié)點可含多個指針域，分別存放多個指針。例如，雙向鏈表中的結(jié)點可以含有兩個指針域，分別存放指向其直接前趨和直接后繼結(jié)點的指針。2、（）鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序。錯，鏈表的存儲結(jié)構(gòu)特點是無序，而鏈表的示意圖有序。 3、（）鏈表的刪除算法很簡單，因為當刪除鏈中某個結(jié)點后，計算機會自動地將后續(xù) 各個單元向前移動。錯，鏈表的結(jié)點不會移動，只是指針內(nèi)容改變。簡答題：1、描述以下三個概念的區(qū)別：頭指針、頭結(jié)點、首元結(jié)點（第一個元素結(jié)點）。在單鏈表中設置頭結(jié)點的作用是什么？答：首元結(jié)點是指鏈表中存儲線性表中第一個數(shù)據(jù)元素a1的結(jié)點。為了操作方便，通常在鏈表的首元結(jié)點之前附設一個結(jié)點，稱為頭結(jié)點，該結(jié)點的數(shù)據(jù)域中不存儲線性表的數(shù)據(jù)元素，其作用是為了對鏈表進行操作時，可以對空表、非空表的情況以及對首元結(jié)點進行統(tǒng)一處理。頭指針是指向鏈表中第一個結(jié)點（或為頭結(jié)點或為首元結(jié)點）的指針。若鏈表中附設頭結(jié)點，則不管線性表是否為空表，頭指針均不為空。否則表示空表的鏈表的頭指針為空。這三個概念對單鏈表、雙向鏈表和循環(huán)鏈表均適用。是否設置頭結(jié)點，是不同的存儲結(jié)構(gòu)表示同一邏輯結(jié)構(gòu)的問題。 頭結(jié)點h