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

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