計(jì)算機(jī)軟件技術(shù)基礎(chǔ)所有題目答案-自學(xué)講解

1、數(shù)據(jù)結(jié)構(gòu)習(xí)題答案2第一節(jié) 概 論2第二節(jié) 線性表5第三節(jié) 棧和隊(duì)列16第五節(jié) 樹19第七節(jié) 查找25第八節(jié) 排序 2932操作系統(tǒng)練習(xí)題參考答案數(shù)據(jù)結(jié)構(gòu)習(xí)題答案第一節(jié) 概 論一、選擇題 1要求同一邏輯結(jié)構(gòu)的所有數(shù)據(jù)元素具有相同的特性，這意味著 ( ) 。 A數(shù)據(jù)元素具有同一的特點(diǎn)B不僅數(shù)據(jù)元素包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對應(yīng)數(shù)據(jù)項(xiàng)的類型要一致 C 每個(gè)數(shù)據(jù)元素都一樣 D 數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等 2數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的 ( (1) ) 以及它們之間的 ( (2) ) 和 運(yùn)算的學(xué)科。(1) A操作對象 B 計(jì)算方法 C 邏輯存儲 D 數(shù)據(jù)映像(2)

2、A 結(jié)構(gòu)B關(guān)系 C 運(yùn)算 D 算法3數(shù)據(jù)結(jié)構(gòu)被形式地定義為 (D，R)，其中 D是( (1) ) 的有限集合， R是 D上( (2) ) 的有限集 合。(1) A 算法B數(shù)據(jù)元素 C 數(shù)據(jù)操作 D 邏輯結(jié)構(gòu)(2)A 操作 B 映像 C 存儲D關(guān)系4在數(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) C線性結(jié)構(gòu)和非線性結(jié)構(gòu) D 內(nèi)部結(jié)構(gòu) 和外部結(jié)構(gòu) 5線性表的順序存儲結(jié)構(gòu)是一種 ( ) 的存儲結(jié)構(gòu)。A隨機(jī)存取 B 順序存取 C 索引存取 D Hash 存取 6算法分析的目的是 ( ) 。A找出數(shù)據(jù)結(jié)構(gòu)的合理性 B 研究算法中的輸入和輸出的關(guān)系 C

3、分析算法的效率以求改進(jìn) D分析算法的易懂性和文檔性7計(jì)算機(jī)算法指的是 ( (1) ) ，它必須具備輸入、輸出和 ( (2) ) 等五個(gè)特征。(1) A 計(jì)算方法 B 排序方法C解決某一問題的有限運(yùn)算序列D 調(diào)度方法(2) A 可行性、可移植性和可擴(kuò)充性 B可行性、確定性和有窮性 C 確定性，有窮性和穩(wěn) 定性 D 易讀性、穩(wěn)定性和安全性 8線性表若采用鏈表存儲結(jié)構(gòu)，要求內(nèi)存中可用存儲單元的地址 ( ) 。A必須是連續(xù)的 B 部分必須是連續(xù)的 C 一定是不連續(xù)的D連續(xù)不連續(xù)都可以9在以下的敘述中，正確的是 ( ) 。A線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu)B二維數(shù)組是它的每個(gè)數(shù)據(jù)元素為一個(gè)線性表的線

4、性表 C 棧的操作方式是先進(jìn)先出 D 隊(duì)列的操作方式是先進(jìn)后出 10根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，以下四類基本的邏輯結(jié)構(gòu)反映了四類基本的數(shù)據(jù)組織形 式，其中解釋錯(cuò)誤的是 ( ) 。A集合中任何兩個(gè)結(jié)點(diǎn)之間都有邏輯關(guān)系但組織形式松散B 線性結(jié)構(gòu)中結(jié)點(diǎn)按邏輯關(guān)系依次排列形成一條“鎖鏈” C 樹形結(jié)構(gòu)具有分支、層次特性，其形態(tài)有點(diǎn)像自然界中的樹 D圖狀結(jié)構(gòu)中的各個(gè)結(jié)點(diǎn)按邏輯關(guān)系互相纏繞，任何兩個(gè)結(jié)點(diǎn)都可以鄰接11以下說法正確的是 ( ) 。 A數(shù)據(jù)元素是數(shù)據(jù)的最小單位B 數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位 C 數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合D數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合二、判斷題 1數(shù)據(jù)元素是數(shù)據(jù)的

5、最小單位。2數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。 3數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)在計(jì)算機(jī)中的映像分別稱為存儲結(jié)構(gòu)、結(jié)點(diǎn)、數(shù)據(jù)域。 4數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位。5數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立的。 6數(shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù)在計(jì)算機(jī)中實(shí)際的存儲形式。7算法和程序沒有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的。 8順序存儲結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)屬于動(dòng)態(tài)結(jié)構(gòu)。三、填空題 1所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)元素之間的 邏輯關(guān)系 。2，數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它包括三方面的內(nèi)容_數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)、對數(shù)據(jù)施加的操作 _。3數(shù)據(jù)的邏輯結(jié)構(gòu)

6、包括 集合結(jié)構(gòu) _、線性結(jié)構(gòu) _、樹型結(jié)構(gòu) 和_圖狀結(jié)構(gòu)四種類型。4在線性結(jié)構(gòu)中，開始結(jié)點(diǎn) _沒有_前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 _一個(gè) _個(gè)前驅(qū)結(jié)點(diǎn)。 5在樹形結(jié)構(gòu)中，根結(jié)點(diǎn)只有 _一個(gè)_，其余每個(gè)結(jié)點(diǎn)有且只有 _一個(gè) _前驅(qū)結(jié)點(diǎn)；葉結(jié)點(diǎn) 沒有_后繼_結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)可以有 _任意個(gè) _ 6在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)可以有 _任意個(gè) _。7算法的五個(gè)重要特性是 _可行性_、 _確定性 _、_有窮性 _、_輸入 _、_輸出 _。8下列程序段的時(shí)間復(fù)雜度是 _O（n）_。for （i=1；i=n ；i+） Ai ，i=0 ；9下列程序段的時(shí)間復(fù)雜度是 _ O（ n2

7、）_。S=0 ；for（i=1； i=n ； i+）for（j=1；j=n ；j+） s=s+Bi,j ；sum=s ；10存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)的 _物理 _實(shí)現(xiàn)。 11從數(shù)據(jù)結(jié)構(gòu)的觀點(diǎn)看，通常所說的“數(shù)據(jù)”應(yīng)分成三個(gè)不同的層次，即_數(shù)據(jù) _、_數(shù)據(jù)元素_和_數(shù)據(jù)項(xiàng) _。12根據(jù)需要，數(shù)據(jù)元素又被稱為 _結(jié)點(diǎn) _、_記錄_、_元素_或_頂點(diǎn)_。 13通常，存儲結(jié)點(diǎn)之間可以有 _順序存儲 _、鏈?zhǔn)酱鎯?_、 索引存儲 _、_散列存儲_四種關(guān)聯(lián)方式，稱為四種基本存儲方式。14通常從 _確定性_、_可讀性_、_健壯性_、_高效性_等幾方面評價(jià)算法 （包括程序 ）的 質(zhì)量。15一個(gè)算法的時(shí)空性能是指該算

8、法的 _時(shí)間復(fù)雜度和 _空間復(fù)雜度 _，前者是算法包含的 _計(jì)算 量_，后者是算法需要的 _存儲量 _。16在一般情況下，一個(gè)算法的時(shí)間復(fù)雜度是 _問題規(guī)模 _的函數(shù)。 17常見時(shí)間復(fù)雜度的量級有：常數(shù)階 O（_1_）、對數(shù)階 O（_log 2n_）、線性階 O（_n_）、平方 階 O（_n2_）和指數(shù)階 O（_2n_） 。通常認(rèn)為，具有指數(shù)階量級的算法是 _不可行 _的。 18數(shù)據(jù)結(jié)構(gòu)的基本任務(wù)是數(shù)據(jù)結(jié)構(gòu)的 _設(shè)計(jì)_和_實(shí)現(xiàn) _。19數(shù)據(jù)對象是性質(zhì)相同的 _數(shù)據(jù)元素 _的集合。20抽象數(shù)據(jù)類型是指一個(gè) _數(shù)學(xué)模型 _以及定義在該模型上的一組操作。四、應(yīng)用題1分析下列程序段的時(shí)間復(fù)雜度。i=1

9、 ；WHILE (i0) if(x10) y-；(3) i=1 ；j=0 ； while(i+jj)j+ ； else i+;(4) x=n ； y=0； while(x=(y+1) (y+1) y+ ； 答：(1) O(n) (2) O(1) (3) O(n) (4) O(n1/2) 9設(shè) n 為正數(shù)。試確定下列各程序段中前面加記號 的語句的頻度：(1)i=1 ； k=0；while(i=n-1) k+=10 i ； i+ ； ) (2) k=0 ；for(i=1；i=n ； i+)for(j=i； jnext=NULL C head-next=head D head!=NULL 10非空單

10、循環(huán)鏈表 head的尾結(jié)點(diǎn)p 滿足( ) 。A p-next=NULL B p=NULL Cp-next=head D p=head11在雙循環(huán)鏈表的 p 結(jié)點(diǎn)之后插入 s 結(jié)點(diǎn)的操作是 ( ) 。A p-next=s ； s-prior=p ；p-next-prior=s ；s-next=p-next ； B p-next=s ；p- next-prior=s ； s-prior=p ：s-next=p-next ； C s-prior=p ； s-next=p-next ； p- next=s ；p-next-prior=s ； D s-prior=p ； s-next=p-next ；

11、p-next-pror=s ； p- next=s ；12. 在一個(gè)單鏈表中，已知 q 結(jié)點(diǎn)是 p 結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在 q 和p 之間插入結(jié)點(diǎn) s，則執(zhí)行 ( ) 。A s-next=p-next ；p-next=s ； B p-next=s-next ； s-next=p ； Cq-next=s; s-next=p ； D p-next=s; s-next=q ；13. 在一個(gè)單鏈表中，若 p 結(jié)點(diǎn)不是最后結(jié)點(diǎn)。在 p 之后插入結(jié)點(diǎn) s，則執(zhí)行 ( ) 。A s-next=p ； p-next=s; Bs-next=p-next ；p-next=s ；C s-next=p-next ； p

12、=s ； D p-next=s ； s-next=p;14. 若某線性表中最常用的操作是取第 i 個(gè)元素和找第 i 個(gè)元素的前驅(qū)元素，則采用 ( ) 存儲 方式最節(jié)省時(shí)間。A順序表 B. 單鏈表 C 雙鏈表 D 單循環(huán)鏈表 15設(shè) rear 是指向非空帶頭結(jié)點(diǎn)的單循環(huán)鏈表的尾指針，則刪除表頭結(jié)點(diǎn)的操作可表示為 ( ) 。A p=rear ； rear=rear-next ； free(p) B rear=rear-next ；free(rear) ； Crear=rear-next-next ； free(rear) ； Dp=rear-next-next ； rear-next- next=

13、p-next ；free(p) ； 16在一個(gè)單鏈表中，若刪除 p 結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行 ( ) 。Aq=p-next ； p-next=q-next ； free(q) ； B p=p-next ；p-next=p-next-next ； free(p) ； C p-next=p-next ；free(p-next) ； D p=p-next-next ； free(p-next) ； 17設(shè)指針 p 指向雙鏈表的某一結(jié)點(diǎn)，則雙鏈表結(jié)構(gòu)的對稱性可用 ( ) 式來刻畫。A p-prior-next-=p-next-next Bp-prior-prior=p-next-priorCp-prio

14、r-next-=p-next-prior Dp-next-next=p-prior-prior18在循環(huán)鏈表中，將頭指針改設(shè)為尾指針 rear 后，其頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的存儲位置分別是 ( ) 。A rear 和 rear-next-nextB rear-next 和rear C rear-next-next 和rearDrear 和 rear-next 19循環(huán)鏈表的主要優(yōu)點(diǎn)是 ( ) 。A 不再需要頭指針了 B 已知某個(gè)結(jié)點(diǎn)的位置后，容易找到它的直接前驅(qū) C 在進(jìn)行插 入、刪除操作時(shí)，能更好地保證鏈表不斷開D從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表20在線性表的下列存儲結(jié)構(gòu)中，讀取元素花費(fèi)時(shí)間最少

15、的是( ) 。A 單鏈表 B 雙鏈表 C 循環(huán)鏈表D順序表二、判斷題1順序存儲的線性表可以隨機(jī)存取。 2順序存儲的線性表的插入和刪除操作不需要付出很大的代價(jià)，因?yàn)槠骄看尾僮髦挥薪话?的元素需要移動(dòng)。3線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此是屬 于同一數(shù)據(jù)對象。4在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上不一定相鄰。 5在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。 6在單鏈表中，可以從頭結(jié)點(diǎn)開始查找任何一個(gè)元素。7線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。 8在線性表的順序存儲結(jié)構(gòu)中，插入和刪除元素時(shí)，移動(dòng)元素的個(gè)數(shù)與該

16、元素的位置有關(guān)。 9在單鏈表中，要取得某個(gè)元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存 儲結(jié)構(gòu)。10順序存儲方式只能用于存儲線性結(jié)構(gòu)。三、填空題1為了便于討論，有時(shí)將含 n(n0) 個(gè)結(jié)點(diǎn)的線性結(jié)構(gòu)表示成 (a1 ，a2， an) ，其中每個(gè) ai 代 表一個(gè)_結(jié)點(diǎn)_。a1稱為_第一個(gè)_結(jié)點(diǎn)， an稱為_最后一個(gè)_結(jié)點(diǎn)， i 稱為 ai 在線性表中的 _位置 _。對任意一對相鄰結(jié)點(diǎn) ai 、ai+1(1 inext ；p-next=q-next ； free(q) ；_6非空的單循環(huán)鏈表 head的尾結(jié)點(diǎn) (由指針 p所指)滿足_ p-next= head 。7rear 是指向非

17、空帶頭結(jié)點(diǎn)的單循環(huán)鏈表的尾指針，則刪除起始結(jié)點(diǎn)的操作可表示為_ p=rear-next ； q=p-next ；p-next=q-next ；free(q) ；。8對于一個(gè)具有 n 個(gè)結(jié)點(diǎn)的單鏈表，在 p 所指結(jié)點(diǎn)后插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為 _O(1) _，在 給定值為 x 的結(jié)點(diǎn)后插入新結(jié)點(diǎn)的時(shí)間復(fù)雜度為 _ O(n)_。9單鏈表表示法的基本思想是用 _指針 _表示結(jié)點(diǎn)間的邏輯關(guān)系。 10在順序表中插入或刪除一個(gè)元素，平均需要移動(dòng) _一半 _元素，具體移動(dòng)的元素個(gè)數(shù)與 _元素 的位置_有關(guān)。11在一個(gè)長度為 n的向量的第 i(1 i n+1)個(gè)元素之前插入一個(gè)元素時(shí)，需向后移動(dòng) _ n-

18、i+1 _個(gè)元素。12在一個(gè)長度為 n的向量中刪除第 i(1 i n)個(gè)元素時(shí)，需向前移動(dòng) _ n-i _個(gè)元素。13在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向 _前驅(qū) _，另一個(gè)指向 _后繼 _。 14在一個(gè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表中， p 指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的指針 head 可用 p 表示為 head=_ p-next-next ； _。15設(shè) head指向單鏈表的表頭， p 指向單鏈表的表尾結(jié)點(diǎn)，則執(zhí)行 p-next=head 后，該單鏈表構(gòu) 成_單循環(huán)鏈表 _。16在單鏈表中，若 p 和 s 是兩個(gè)指針，且滿足 p-next 與 s 相同，則語句 p-next=s-next

19、 的 作用是_刪除_s 指向的結(jié)點(diǎn)。17設(shè) r 指向單循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)，要在最后一個(gè)結(jié)點(diǎn)之后插入s 所指的結(jié)點(diǎn)，需執(zhí)行的三條語句是 _s-next= r-next _ ；r-next=s ；r=s ；18在單鏈表中，指針 p 所指結(jié)點(diǎn)為最后一個(gè)結(jié)點(diǎn)的條件是 _ p-next=NULL_。 19在雙循環(huán)鏈表中，若要在指 p 所指結(jié)點(diǎn)前插入 s 所指的結(jié)點(diǎn)，則需執(zhí)行下列語句： s- next=p ； s-prior=p-prior；_ p-prior-next _=s；p-prior=s ；20在單鏈表中，若要在 p所指結(jié)點(diǎn)之前插入 s 所指的結(jié)點(diǎn)，可進(jìn)行下列操作：s-next=_ p-ne

20、xt _； p-next=s ； temp=p-data ；p-data=_ s-data _； s-data=_ temp _ ；四、應(yīng)用題1描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn) ( 第一個(gè)元素結(jié)點(diǎn) )。 答：首元結(jié)點(diǎn)是指鏈表中存儲的線性表中的第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。為了操作方便，通常在鏈表 的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)。頭指針是指向鏈表中的第一個(gè)結(jié)點(diǎn)的指針。 2何時(shí)選用順序表，何時(shí)選用鏈表作為線性表的存儲結(jié)構(gòu)為宜？ 答：從空間上來看，當(dāng)線性表的長度變化較大、難以估計(jì)其規(guī)模時(shí)，選用動(dòng)態(tài)的鏈表作為存儲結(jié) 構(gòu)比較合適，但鏈表除了需要設(shè)置數(shù)據(jù)域外，還要額外設(shè)置指針域，因此當(dāng)線性

21、表長度變化不 大、易于事先確定規(guī)模時(shí)，為了節(jié)約存儲空間，宜采用順序存儲結(jié)構(gòu)。從時(shí)間上來看，若線性表 的操作主要是查找，很少進(jìn)行插入和刪除操作時(shí)，應(yīng)選用順序表。對于頻繁進(jìn)行插入和刪除操作 的線性表，宜采用鏈表作為存儲結(jié)構(gòu)。3在順序表中插入和刪除一個(gè)結(jié)點(diǎn)需平均移動(dòng)多少個(gè)結(jié)點(diǎn)？具體的移動(dòng)次數(shù)取決于哪兩個(gè)因素？ 答：平均移動(dòng)表中大約一半的結(jié)點(diǎn)，插入操作平均移動(dòng) n/2 個(gè)結(jié)點(diǎn)，刪除操作平均移動(dòng)( n-1) /2 個(gè)結(jié)點(diǎn)。具體移動(dòng)的次數(shù)取決于表長和插入、刪除的結(jié)點(diǎn)的位置。4為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好？答：單循環(huán)鏈表中無論設(shè)置尾指針還是頭指針都可以遍歷表中任一個(gè)結(jié)點(diǎn)，但設(shè)置尾指針時(shí)，若

22、 在表尾進(jìn)行插入或刪除操作可在 O(1) 時(shí)間內(nèi)完成，同樣在表頭進(jìn)行插入或刪除操作也可在 O(1) 時(shí) 間內(nèi)完成。但若設(shè)置的是頭指針，表尾進(jìn)行插入或刪除操作，需要遍歷整個(gè)鏈表，時(shí)間復(fù)雜度為 O(n)。5雙鏈表和單循環(huán)鏈表中，若僅知道指針 p 指向某個(gè)結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn) p 從相 應(yīng)的鏈表中刪除？若可以，其時(shí)間復(fù)雜度各為多少？答：能刪除。雙鏈表上刪除 p所指向的結(jié)點(diǎn)的時(shí)間復(fù)雜度為 O(1) ，單循環(huán)鏈表上刪除 p 所指向的 結(jié)點(diǎn)的時(shí)間復(fù)雜度為 O(n) 。6下列算法的功能是什么？LinkList testl(LinkList L)/L 是無頭結(jié)點(diǎn)的單鏈表ListNodeq， p；if

23、(L&L-next) q=L ； L=L-next ； p=L;while(p-next) p=p-next ； p-next=q; q-next=NULL； return L ；答： 如果長度大于 1，則將首元結(jié)點(diǎn)刪除并插入到表尾。7如果有 n 個(gè)線性表同時(shí)共存，并且在處理過程中各表的長度會發(fā)生動(dòng)態(tài)變化，線性表的總長度 也會自動(dòng)地改變。在此情況下，應(yīng)選擇哪一種存儲結(jié)構(gòu)？為什么？答：應(yīng)選用鏈?zhǔn)酱鎯Y(jié)構(gòu)。因?yàn)轫樞虮硎庆o態(tài)存儲結(jié)構(gòu)，只能預(yù)先分配，不能隨著線性表長度的 改變而變化。而鏈表則可根據(jù)需要?jiǎng)討B(tài)地申請空間，因此適用于動(dòng)態(tài)變化表長的線性表。8若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入、刪除操作，但

24、要求以最快的方式存取線性表的元 素，應(yīng)該用哪種存儲結(jié)構(gòu)？為什么？ 答：應(yīng)選用順序存儲結(jié)構(gòu)。因?yàn)轫樞虼鎯Y(jié)構(gòu)存取元素操作的時(shí)間復(fù)雜度為O(1) 。五、算法設(shè)計(jì)題1試用順序表作為存儲結(jié)構(gòu)，實(shí)現(xiàn)將線性表 (a0 ，a1，a2，an-1) 就地逆置的操作，所謂“就 地”是指輔助空間為 O(1) 。答： (1) 順序表的就地逆置 分析：分別用兩個(gè)整型變量指向順序表的兩端，同時(shí)向中間移動(dòng)，移動(dòng)的同時(shí)互換兩個(gè)下標(biāo)指示 的元素的值。void Seqreverse(SeqList L) 順序表的就地逆置for(i=0 ； j=L.1ength-1 ；inext ； L-next=NULL； while(p!=N

25、ULL)r=p， p=p-next ； r 指向當(dāng)前待逆置的結(jié)點(diǎn)， p 記下下個(gè)結(jié)點(diǎn)r-next=Lnext ； L-next=r ；放到表頭 2設(shè)順序表 L 是一個(gè)遞增 ( 允許有相同的值 ) 有序表，試寫一算法將 x 插入 L 中，并使 L 仍為一個(gè) 有序表。答：分析：先找到 x 的正確插入位置，然后將大于 x 的元素從后向前依次向下移動(dòng)，最后將 x 插 入到其位置上，同時(shí)順序表長度增 1。void SeqListinsert(SeqList L，int x) x 插入到遞增有序的順序表 L 中i=0;while(i=L.datai) i+ ； 找正確的插入位置 for(k=L.lengt

26、h-1;k=i； k-) 元素從后往前依次后移L.datak+1 ： L.datak ；L.data(i x； x 插入到正確位置L.1ength+ ；)3. 設(shè)單鏈表 L 是一個(gè)非遞減有序表，試寫一個(gè)算法將 x 插入其中后仍保持 L 的有序性。 答：分析：此問題的關(guān)鍵是在鏈表中找到 x 的插入位置，因此需要兩個(gè)指針一前一后地依次向后 移動(dòng)。void LinkListinsert(LinkedList L，int x) x 插入有序鏈表 L 中q=L ； p=q next ； while(p!=NULL&p datanext ； s=(LinkedList)malloc(sizeof(LNod

27、e) ； 生成新結(jié)點(diǎn)S data=x ； S next=p； q next=s ； 4. 試寫出在不帶頭結(jié)點(diǎn)的單鏈表的第 i 個(gè)元素之前插入一個(gè)元素的算法。答：分析：對不帶頭結(jié)點(diǎn)的鏈表操作時(shí)，要注意對第一個(gè)結(jié)點(diǎn)和其他結(jié)點(diǎn)操作的不同void LinkedListlnsert(LinkedList 不帶頭結(jié)點(diǎn)的單鏈表的第 p=L ： j=1; while(p!=NULL&jnext ；j+ ； if(idata=x ；if(i=1) qnext=L ；L=q； 在第一個(gè)元素之前插入elseq next=p next ；pnext=q ；在其他位置插入 5設(shè) A、B 是兩個(gè)線性表，其表中元素遞增有序

28、，長度分別為 m和 n。試寫一算法分別以順序存儲 和鏈?zhǔn)酱鎯?A和 B 歸并成一個(gè)仍按元素值遞增有序的線性表 C。答：(1) 分析：用三個(gè)變量 i 、j 、k分別指示 A、B、C三個(gè)順序表的當(dāng)前位置，將 A、B表中較小 的元素寫入 C中，直到有一個(gè)表先結(jié)束。最后將沒結(jié)束的表的剩余元素寫入C 表中。SeqList Seqmerge(SeqList A ，SeqList B) 有序順序表 A和 B 歸并成有序順序表 C i=0 ；j=0 ；k=0； i ，i ，k 分別為順序表 A，B，C的下標(biāo) while(im&jn)if(A.dataiB.dataj) A中當(dāng)前元素較小C.datak=A.d

29、atail；i+； else C.datak=B.dataj;j+； B中當(dāng)前元素較小k+ ； if (i=m) for(t=j；tn ；t+) C.datak=B.datat;k+； B 表長度大于 A表else for(t=i；tnext ； pb=Bnext ；C=A；pc=C； while(pa&pb) A和 B 都不為空時(shí)10if(pa datadata)A 當(dāng)前結(jié)點(diǎn)值較小qa=pa-next ； pC-next=pa ； pc=pc-next ； pa=qa ； else qb=pb-next ；pc-next=pb ： pc=pc-next ；pb=qb； B當(dāng)前結(jié)點(diǎn)值較小if(

30、pa)pc next=pa；A 沒有結(jié)束，將 A表剩余元素鏈接到 C表if(pb)pc next=pb；B 沒有結(jié)束，將 B表剩余元素鏈接到 C表free(B) ；釋放 B 表的頭結(jié)點(diǎn)本算法需要遍歷兩個(gè)線性表，因此時(shí)間復(fù)雜度為 O(m+n)。6設(shè)指針 la 和 lb 分別指向兩個(gè)不帶頭結(jié)點(diǎn)的單鏈表的首結(jié)點(diǎn)，設(shè)計(jì)從表 la 中刪除第 i 個(gè)元素 起共 len 個(gè)元素，并將這些元素插入到 lb 中第 j 個(gè)結(jié)點(diǎn)之前的算法。答：分析：先在 la 中找到第 i 個(gè)結(jié)點(diǎn)，分別用兩個(gè)指針 pre 和p指向第 i-1 和第 i 個(gè)結(jié)點(diǎn)，然后 用指針 q 從第 i 個(gè)結(jié)點(diǎn)起向后走 len 個(gè)元素，使 q 指向

31、此位置。然后在 lb 中找到第 j 個(gè)結(jié)點(diǎn)，將 p 所指向的 la 表中的第 i 個(gè)及 q 所指向的最后一個(gè)共 len 個(gè)結(jié)點(diǎn)插入到 lb 中。void Deletelnsert(LinkedList la，LinkedList lb ，int i ， int j, int len) 刪除不帶頭結(jié)點(diǎn)的單鏈表 la 中第 i 個(gè)元素起共 len 個(gè)元素 , 并將這峰元素插入到單鏈表 lb 中第 j 個(gè)結(jié)點(diǎn)之前if(i0|j0|len0) exit(0) ；p=la ；k=1； pre=NULL；while(p&knext; k+ ； if(!p) exit(0) ；q=p ；k=l ； p 指向

32、 la 表中第 i 個(gè)結(jié)點(diǎn)while(q&knext ； k+ ； 查找 la 表中第 i+len-1 個(gè)結(jié)點(diǎn)if(!q) exit(0) ；if(pre=la) la=q next ； i=1 的情況else pre next=q next ；完成刪除將從 la 中刪除的結(jié)點(diǎn)插入到 lb 中if(j=1) q-next=lb ； lb=p ； j=1 時(shí)else r=lb; k=1 ； j1 時(shí)while(r&knext ； k+ ； 查找 Lb表中第 i 1個(gè)元素if(!r) exit(0) ；qnext=r next ； r next=p ； 完成插入 7單鏈表 L 是一個(gè)遞減有序表，試

33、寫一高效算法，刪除表中值大于min 且小于 max的結(jié)點(diǎn) ( 若表中有這樣的結(jié)點(diǎn) ) ，同時(shí)釋放被刪結(jié)點(diǎn)空間，這里 min 和 max是兩個(gè)給定的參數(shù)。答： LinkedList delete(LinkedList L，int min ，int max) 刪除遞減有序單鏈表 L 中值大于 min 且小于 max 的結(jié)點(diǎn)q=L ；if(minmax) printf(” minmax n” ) ； exit(0) ；else p=L next ； q 始終指向 p 的前驅(qū)while(p data=max)當(dāng)前元素大于或等于 max，則 p、 q 依次向后移動(dòng)q=p ；p=pnext ；while(

34、p!=NULL)&(p 一 datamin) 當(dāng)前元素的值比 min 大同時(shí)比 max 小，刪除 p 指向的結(jié)點(diǎn)q next=p next ， free(p) ； p=qnext ； return L ； 10118編寫一個(gè)算法將一個(gè)頭結(jié)點(diǎn)指針為 pa的單鏈表 A分解成兩個(gè)單鏈表 A和 B，其頭結(jié)點(diǎn)指針分別 為 pa 和 pb，使得 A 鏈表中含有原鏈表 A 中序號為奇數(shù)的元素，而 B 鏈表中含有原鏈表 A 中序號為 偶數(shù)的元素，且保持原來的相對順序。答：分析：用兩個(gè)工作指針 p和 q分別指示序號為奇數(shù)和序號為偶數(shù)的結(jié)點(diǎn)，將 q所指向的結(jié)點(diǎn) 從 A 表刪除，并鏈接到 B表。void decom

35、pose(LinkedList A， LinkedList B) 單鏈表 A 分解成元素序號為奇數(shù)的單鏈表 A 和元素序號為偶數(shù)的單鏈表 Bp=A-next ； B=(LinkedList)malloc(sizeof(LNode) ；r=B ；while(p!=NULL&p-next!=NULL)q=p next ；q 指向偶數(shù)序號的結(jié)點(diǎn)p next=qnext； 將 q從 A表中刪除r next=q ；將 q 結(jié)點(diǎn)鏈接到 B鏈表的末尾r=q ； r 總是指向 B 鏈表的最后個(gè)結(jié)點(diǎn)p=p next ；p 指向原鏈表 A中的奇數(shù)序號的結(jié)點(diǎn)r next=NULL；將生成 B 鏈表中的最后一個(gè)結(jié)點(diǎn)的

36、 next 域置為空9假設(shè)以兩個(gè)元素依值遞增有序排列的線性表 A、B 分別表示兩個(gè)集合，要求另辟空間構(gòu)造一個(gè) 線性表 C，其元素為兩集合的交集，且表 C中的元素也依值遞增有序排列。對順序表編寫求 C 的算 法。答：分析：用三個(gè)變量 i 、j 、k 分別指示 A、B、C三個(gè)順序表的當(dāng)前位置，若 A、B 表中當(dāng)前元素 值相同，則寫入 C中，并使 i、j、k值增 1；若 A表元素值較小，則使 i 增1；若 B表元素值較 小，則使 j 增 1，直到有一個(gè)表先結(jié)束。SeqLiSt intersection(SeqList A，SeqList B ，SeqList C) 求元素依值遞增有序排列的順序表 A

37、、B 的交集 C i=0 ； j=0 ； k=0；while(i=A.length-1)&(j=B.length-1)if(A.datai=B.dataj)C.datak=A.dataik+；i+ ；j+ ； else if(A.datain時(shí))，線性表 A、 B、 C均以單鏈表作為存儲結(jié)構(gòu)，且 C表利用 A 表和 B 表的 結(jié)點(diǎn)空間。答：分析：使 p 和 q 指向 A和 B 表當(dāng)前元素，并分別使 nextp 和 nextq 指向 p 和 q 的后繼，這樣 將 q 所指向的結(jié)點(diǎn)鏈接到 p 的后面，再把 nextp 和 nextq 的值賦給 p 和 q ，處理下一個(gè)結(jié)點(diǎn)。 void merge(

38、LinkedList A ， LinkedList B ，LinkedList C) 把鏈表 A 和 B合并為 C，A 和 B的元素間隔排列，且使用原存儲空間p=A next；q=Bnext ；C=A；while(p&q)nextp=p next ；pnext=q ；將 B的元素插入if(nextp) nextq=q-next； q-next=nextp ； 如果 A非空，將 A的元素插入1112p=nextp ； q=nextq ； 11假設(shè)在長度大于 1的單循環(huán)鏈表中，既無頭結(jié)點(diǎn)也無頭指針。 s 為指向鏈表中某個(gè)結(jié)點(diǎn)的指 針，試編寫算法刪除結(jié)點(diǎn) s 的直接前驅(qū)結(jié)點(diǎn)。答：分析：因?yàn)榧炔恢来?/p>

39、單循環(huán)鏈表的頭指針，也不知道其尾指針，所以找 s 的前驅(qū)就只能從 s 開始，順次向后尋找。void DeletePre(LinkedNode s) 刪除單循環(huán)鏈表中結(jié)點(diǎn) s 的直接前驅(qū)p=s ；while(p next next!=s) p=p next ； 找到 s 的前驅(qū)的前驅(qū) pq=p next ；q是p的后繼，即 s 的前驅(qū)p next=s ；將 q 刪除free(q) ； 12計(jì)算帶頭結(jié)點(diǎn)的循環(huán)鏈表的結(jié)點(diǎn)個(gè)數(shù)。 答：int number(LinkedNode head) 計(jì)算單循環(huán)鏈表中結(jié)點(diǎn)的個(gè)數(shù)p=head next ； i=0 ；while(p!=head) i+； p=p-ne

40、xt ；return i ； 13已知由單鏈表表示的線性表中，含有三類字符的數(shù)據(jù)元素 ( 如：字母字符、數(shù)字字符和其他字 符) ，試編寫算法構(gòu)造三個(gè)以循環(huán)鏈表表示的線性表，使得每個(gè)表中只含有同一類的字符，且利用 原表中的結(jié)點(diǎn)空間作為這三個(gè)表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。答：分析： p 指向待處理的單鏈表的首元結(jié)點(diǎn)，構(gòu)造三個(gè)空的單循環(huán)鏈表，分別存儲三類字符，其 中一個(gè)可使用原來的單鏈表。 q 指向 p 的下一個(gè)結(jié)點(diǎn)，根據(jù) p 的數(shù)據(jù)域的值將其插入到不同的鏈 表上。再把 q 的值給 p，處理下一個(gè)結(jié)點(diǎn)。void change(LinkedList L ，LinkedList pa ，LinkedL

41、ist pb ， LinkedList pc) 分解含有三類字符的單鏈表為三個(gè)以循環(huán)鏈表表示的線性表，使其分別含有三類字符p=L next ； pa=L ；pa next=pa ；分別構(gòu)造三個(gè)單循環(huán)鏈表pb=(LinkedList)malloc(sizeof(LNode)；pc=(LinkedList)malloc(sizeof(LNode)；pb next=pb ； pcnext=pc ； while(p!=L)q=p next ；q 記下 L 中下一個(gè)結(jié)點(diǎn)的位置if(p datadata=a)鏈接到字母鏈表的頭部p next=pa next ； pa next=p ；else if (pd

42、atadata=0) 鏈接到數(shù)字鏈表的頭部p next=pbnext ；pbnext=p； elsep-next=pc-next；pc-next=p ； 鏈接到其他字母鏈表的頭部p=q ； 14、己知 A、B 和 C為三個(gè)遞增有序的線性表，現(xiàn)要求對 A表進(jìn)行如下操作：刪去那些既在 B表中 出現(xiàn)又在 C表中出現(xiàn)的元素。試對順序表編寫實(shí)現(xiàn)上述操作的算法 ( 注：題中未特別指明同一表中 的元素值各不相同 ) 。答：分析：先從 B 和 C中找出共有元素，記為 same，再在 A中從當(dāng)前位置開始，凡小于 same的元 素均保留 ( 存到新的位置 ) ，等于 same的就跳過，到大于 same時(shí)就再找下一

43、個(gè) SameSeqList IntersectDelete(SeqList A，SeqList B ，SeqList C) 對順序表 A 刪去那些既在 B 表中出現(xiàn)又在 C表中出現(xiàn)的元素i=0 ；j=0 ；k=0；m=0; i 指示 A中元素原來的位置， m為移動(dòng)后的位置1213while(iA.length&iB.length&kC.length)if(B.datajC.datak) k+;else same=B.dataj ； 找到了相同元素 same while(B.dataj=same) j+；while(C.datak=same) k+； j 、 k 后移到新的元素while(iA.length&A.dataisame)A.datam+=A.datai+ ；需保留的元素移動(dòng)到新位置 while(iA.1ength&A.datai1=same i+ ；跳過相同的元素 while(inext ； while(p!=L&p-data!=x) p=p-next； 在