線性表部分習(xí)題

《線性表部分習(xí)題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、線性表習(xí)題2/32本節(jié)重點(diǎn)復(fù)習(xí)要點(diǎn)單項(xiàng)選擇題綜合應(yīng)用題3/32線性表-復(fù)習(xí)要點(diǎn)（1）1.線性表的概念線性表的定義和特點(diǎn)線性表的基本操作2.線性表的存儲(chǔ)表示順序表的定義及基本運(yùn)算的實(shí)現(xiàn)單鏈表的定義及基本運(yùn)算的實(shí)現(xiàn)3.線性表的特殊鏈接表示循環(huán)鏈表的特殊遍歷方式雙向鏈表的方向性4/32線性表-復(fù)習(xí)要點(diǎn)（2）4.線性表的應(yīng)用（1）在一維數(shù)組上的算法，如原地逆置、非零元素壓縮、成塊元素移動(dòng)等。在一維數(shù)組上的遞歸算法，如求和平均值等。在順序表上的查找、插入、刪除、合并、求交等算法及性能分析。在單鏈表上的迭代求

2、解算法及性能，包括統(tǒng)計(jì)鏈表結(jié)點(diǎn)個(gè)數(shù)、在鏈表中尋找與給定值x匹配的結(jié)點(diǎn)、在鏈表中尋找第i個(gè)結(jié)點(diǎn)、鏈表逆轉(zhuǎn)等。5/32線性表-復(fù)習(xí)要點(diǎn)（3）4.線性表的應(yīng)用（2）帶表頭結(jié)點(diǎn)的單鏈表上的迭代算法，包括統(tǒng)計(jì)鏈表結(jié)點(diǎn)個(gè)數(shù)、在鏈表中尋找與給定值x匹配的結(jié)點(diǎn)、在鏈表中尋找第i個(gè)結(jié)點(diǎn)、兩個(gè)有序鏈表的合并等。單鏈表的遞歸算法，包括統(tǒng)計(jì)鏈表結(jié)點(diǎn)個(gè)數(shù)、在鏈表中尋找與給定值x匹配的結(jié)點(diǎn)、在鏈表中尋找第i個(gè)結(jié)點(diǎn)、求鏈表各結(jié)點(diǎn)值的和、平均值等。循環(huán)鏈表的迭代算法、雙向鏈表的迭代算法。5.多項(xiàng)式的建立，兩個(gè)多項(xiàng)式的相加，兩個(gè)多

3、項(xiàng)式的相乘算法6/32單項(xiàng)選擇題7/32單項(xiàng)選擇題8/32單項(xiàng)選擇題9/32單項(xiàng)選擇題10/32單項(xiàng)選擇題11/32單項(xiàng)選擇題例11若在長(zhǎng)度為n的順序表的表尾插入一個(gè)新元素的漸進(jìn)時(shí)間復(fù)雜度是（）。A.O(n)B.O(1)C.O(n2)D.O(log2n)【解答】B。在有n個(gè)元素的順序表的表尾插入一個(gè)新元素，可直接在表的第n+1個(gè)位置插入，漸進(jìn)時(shí)間復(fù)雜度為O(1)。12/32綜合應(yīng)用題此題還有其他做法13/32復(fù)習(xí)要點(diǎn)（1）1.棧的定義及特點(diǎn)棧的定義、棧頂與棧底概念棧的基本運(yùn)算，包括進(jìn)棧、出棧、判空

4、棧、置空棧等2.棧的存儲(chǔ)表示順序棧的實(shí)現(xiàn)及基本操作鏈?zhǔn)綏５膶?shí)現(xiàn)及基本操作3.隊(duì)列的定義及特點(diǎn)隊(duì)列的定義、先進(jìn)先出特點(diǎn)隊(duì)列的基本運(yùn)算，包括進(jìn)隊(duì)、出隊(duì)、判隊(duì)空、置空隊(duì)14/32復(fù)習(xí)要點(diǎn)（2）4.隊(duì)列的存儲(chǔ)表示隊(duì)列的順序存儲(chǔ)及基本操作隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及基本操作5.棧的應(yīng)用棧在遞歸過程中作為工作棧的使用，棧在表達(dá)式計(jì)算中從中綴表示轉(zhuǎn)后綴表示，棧在括號(hào)配對(duì)中的應(yīng)用，棧在數(shù)制轉(zhuǎn)換中的應(yīng)用雙棧共用一個(gè)數(shù)組的進(jìn)棧、退棧、置空棧算法及棧滿、?？諚l件，使用兩個(gè)棧模擬一個(gè)隊(duì)列時(shí)的進(jìn)隊(duì)列和出隊(duì)列算法。15/32復(fù)習(xí)要點(diǎn)（3

5、）6.隊(duì)列的應(yīng)用隊(duì)列在分層處理中的使用，包括二叉樹、樹、圖等層次遍歷過程中的使用隊(duì)列在對(duì)數(shù)據(jù)循環(huán)處理過程中的使用，例如約瑟夫問題、歸并排序隊(duì)列在調(diào)度算法中的使用16/32單項(xiàng)選擇題例1為解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配的問題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)。主機(jī)將要打印輸出的數(shù)據(jù)依次寫入緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)，該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（）。A、棧B、隊(duì)列C、樹D、圖【解答】B。通常用于輸入輸出的緩沖區(qū)都是采用先入先出的隊(duì)列。17/32單項(xiàng)選擇題例2設(shè)棧S和隊(duì)列Q的初始狀態(tài)都為空

6、，元素a,b,c,d,e,f,g依次進(jìn)入棧S.如果每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素出隊(duì)的順序?yàn)閎,d,c,f,e,a,g,則棧S的容量至少是__;A.1B.2C.3D.4【解答】C。隊(duì)列的特點(diǎn)是先進(jìn)先出，出隊(duì)順序和入隊(duì)順序一致，即與出棧順序一致。如果用S表示進(jìn)棧，用X表示出棧，則進(jìn)棧/出棧序列為下圖。由圖知，棧中最多時(shí)有3個(gè)元素，所以棧的容量最少為3。18/32單項(xiàng)選擇題例3假設(shè)一個(gè)循環(huán)隊(duì)列Q[maxSize]的隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列的最大容量為maxSize，除此

7、之外，該隊(duì)列再?zèng)]有其他數(shù)據(jù)成員，則該隊(duì)列的隊(duì)滿條件是__。A.Q.front==Q.rearB.Q.front+Q.rear>=maxSizeC.Q.front==(Q.rear+1)%maxSizeD.Q.rear==(Q.front+1)%maxSize【解答】C。既然不能附加任何其他數(shù)據(jù)成員，只能采用犧牲一個(gè)隊(duì)列元素的整除取余的方式區(qū)分隊(duì)空和隊(duì)滿的條件，因此選項(xiàng)C是合理的，選項(xiàng)A是判斷隊(duì)列是否為空的條件，其他都是干擾項(xiàng)。19/32綜合應(yīng)用題例1鐵路進(jìn)行列車調(diào)度時(shí)，常把站臺(tái)設(shè)計(jì)成棧式結(jié)構(gòu)的站臺(tái)

8、，如右圖所示。試問：（1）設(shè)有編號(hào)為1，2，3，4，5，6的六輛車，順序開入棧式結(jié)構(gòu)的站臺(tái)，則可能的出棧序列有多少種？（2）若進(jìn)站的六輛列車順序如上所述，那么是否能夠得到435612，325641，154623和135426的出站序列，如果不能，說明為什么不能；如果能，說明如何得到（即寫出“進(jìn)站”或“出站”的序列）。20/32綜合應(yīng)用題編號(hào)大的車開出后，編號(hào)比其小的車反序開出，即編號(hào)大的車開出后，編號(hào)比其小的車只能由大到小依次開出（中間可以插入編號(hào)更大的車，但此車后面編號(hào)比其小的車