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

1、241518222628第一節(jié)概論第二節(jié)線性表第三節(jié)棧和隊(duì)列第五節(jié)樹(shù)第七節(jié)查找第八節(jié)排序操作系統(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ù)要相同，而且對(duì)應(yīng)數(shù)據(jù)項(xiàng)的類(lèi)型要一致 C .每個(gè)數(shù)據(jù)元素都一樣D .數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等2 .數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的（1）以及它們之間的（2）和運(yùn)算的學(xué)科。（1） A.操作對(duì)象 B .計(jì)算方法 C .邏輯存儲(chǔ) D .數(shù)據(jù)映像A .結(jié)構(gòu) B.關(guān)系 C .運(yùn)算 D .算法3 .數(shù)據(jù)結(jié)構(gòu)被形

2、式地定義為（D, R）,其中D是（1）的有限集合，R是D上（2）的有限集 合。A .算法B.數(shù)據(jù)元素 C .數(shù)據(jù)操作 D .邏輯結(jié)構(gòu)（2）A .操作 B .映像 C .存儲(chǔ)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 .線性表的順序存儲(chǔ)結(jié)構(gòu)是一種（）的存儲(chǔ)結(jié)構(gòu)。A.隨機(jī)存取 B .順序存取 C .索引存取D . Hash存取6 .算法分析的目的是（）。A,找出數(shù)據(jù)結(jié)構(gòu)的合理性B .研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D.分析算法的易懂性和文檔性7 .計(jì)算

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

4、元素之間關(guān)系的不同特性，以下四類(lèi)基本的邏輯結(jié)構(gòu)反映了四類(lèi)基本的數(shù)據(jù)組織形 式，其中解釋錯(cuò)誤的是（）。A.集合中任何兩個(gè)結(jié)點(diǎn)之間都有邏輯關(guān)系但組織形式松散B .線性結(jié)構(gòu)中結(jié)點(diǎn)按邏輯關(guān)系依次排列形成一條“鎖鏈”C .樹(shù)形結(jié)構(gòu)具有分支、層次特性，其形態(tài)有點(diǎn)像自然界中的樹(shù)D.圖狀結(jié)構(gòu)中的各個(gè)結(jié)點(diǎn)按邏輯關(guān)系互相纏繞，任何兩個(gè)結(jié)點(diǎn)都可以鄰接11 .以下說(shuō)法正確的是（）。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ù)元素的集合二、判斷題X1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。V 2.數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。V 3.數(shù)據(jù)結(jié)構(gòu)、數(shù)

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

6、 四種類(lèi)型。4 .在線性結(jié)構(gòu)中，開(kāi)始結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有一個(gè)個(gè)前驅(qū)結(jié)點(diǎn)。5 .在樹(shù)形結(jié)構(gòu)中，根結(jié)點(diǎn)只有 一個(gè)，其余每個(gè)結(jié)點(diǎn)有且只有 一個(gè)_前驅(qū)結(jié)點(diǎn)；葉結(jié)點(diǎn) 沒(méi)有 后繼結(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è)重要特性是可行性、 確定性、 有窮性、 輸入、 輸出o8 .下列程序段的時(shí)間復(fù)雜度是_O (n)。for (i=1； i<=n ； i+) Ai , i=0 ；9 .下列程序段的時(shí)間復(fù)雜度是_ O (n2)。S=0 ;for(i=1 ； i<=n ； i+)for(j=1 ； j&

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

8、，一個(gè)算法的時(shí)間復(fù)雜度是問(wèn)題規(guī)模 的函數(shù)。17 .常見(jiàn)時(shí)間復(fù)雜度的量級(jí)有：常數(shù)階 。(_1_)、對(duì)數(shù)階O(_log2n)、線性階O(_n_)、平方 階O(_n2_)和指數(shù)階O(_2_)。通常認(rèn)為，具有指數(shù)階量級(jí)的算法是 不可行的。18 .數(shù)據(jù)結(jié)構(gòu)的基本任務(wù)是數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì) 和 實(shí)現(xiàn)。19 .數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素 的集合。20 .抽象數(shù)據(jù)類(lèi)型是指一個(gè)數(shù)學(xué)模型 以及定義在該模型上的一組操作。四、應(yīng)用題1.分析下列程序段的時(shí)間復(fù)雜度。i=1 ；WHILE (i<=n) i=i2;答：O(log2n)2,敘述算法的定義及其重要特性。答：算法是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列

9、。其中每一條指令表示一個(gè)或多個(gè)操作。算法應(yīng)該具有下列特性：可行性、確定性、有窮性、輸入和輸出。3 .簡(jiǎn)述下列術(shù)語(yǔ)：數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)對(duì)象。答：數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符，以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程 序識(shí)別和處理的符號(hào)的集合。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱(chēng)為 元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。 數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合。4 .邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是什么關(guān)系？答：在數(shù)據(jù)結(jié)構(gòu)中，邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是密切相關(guān)的，存儲(chǔ)結(jié)構(gòu)不僅將數(shù)據(jù)元素存儲(chǔ)到計(jì)算機(jī) 中，而且還要表示各數(shù)據(jù)元素之間的邏

10、輯關(guān)系。邏輯結(jié)構(gòu)與計(jì)算機(jī)無(wú)關(guān)，存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)元素之 間的關(guān)系在計(jì)算機(jī)中的表示。5 .將數(shù)量級(jí) 210, n, n2, n3, nlog2n, log 2n, 2n, n! , (2/3)n, n2 3按增長(zhǎng)率進(jìn)行排列。答:(2/3)n, 210, 10g2n , n2/3, n, nlog2n , n2, n3, 2n, n!6 .設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為： D=k1 , k2, k3,，k9 , R=<k1, k3>, <k1 , k8>, <k2, k3>, <k2, k4>, <k2, k5>, <k3, k9>, <

11、;k5, k6>, <k8, k9>, <k9, k7>, <k4, k6>,畫(huà)出這個(gè)邏輯結(jié)構(gòu)的 圖示，并確定相對(duì)于關(guān)系 R,哪些結(jié)點(diǎn)是開(kāi)始結(jié)點(diǎn)，哪些結(jié)點(diǎn)是終端結(jié)點(diǎn)？答：圖略。開(kāi)始結(jié)點(diǎn)k1、k2,終端結(jié)點(diǎn)k6、k707 .設(shè)有如圖1.1所示的邏輯結(jié)構(gòu)圖，給出它的邏輯結(jié)構(gòu)，并說(shuō)出它是什么類(lèi)型的邏輯結(jié)構(gòu)。答：數(shù)據(jù)邏輯結(jié)構(gòu)為：D=k1 , k2, k3,，k8, R=<k1, k2>, <k1, k3>, <k3, k5>, <k3, k4>, <k4, k7>, <k4, k6>, &

12、lt;k5, k8>,其邏輯結(jié)構(gòu)類(lèi)型為樹(shù)型結(jié)構(gòu)。8 .分析下列程序的時(shí)間復(fù)雜度(設(shè)n為正整數(shù))。(1)int rec(int n)if(n=1)return(1) ； else return(nrec(n-1) ； x=91; y=100;While (y>0) if(x>10) y-；i=1； j=0 ；while(i+j<=n)if(i>j)j+ ； else i+;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ù)。試確定下列各程序段中前面

13、加記號(hào) 1語(yǔ)句的頻度：i=1； k=0；while(i<=n-1) k+=10 i ；i+;)(2) k=0；for(i=1 ; i<=n ； i+)for(j=i ; j<=n : j+) k+ ；答：(1)n-1 (2)n+(n-1)+1=n(n+1)/2第二節(jié)線性表一、選擇題1 .線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)代表一個(gè)()。A.數(shù)據(jù)元素B .數(shù)據(jù)項(xiàng) C .數(shù)據(jù)D .數(shù)據(jù)結(jié)構(gòu)2 .線性表L=(a1 , a2,，ai ,，an),下列說(shuō)法正確的是()。A.每個(gè)元素都有一個(gè)直接前驅(qū)和直接后繼B .線性表中至少要有一個(gè)元素C .表中諸元素的排列順序必須是由小到大或由大到小的D .除第一個(gè)

14、元素和最后一個(gè)元素外其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼3 .順序表是線性表的（）。A .鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B.順序存儲(chǔ)結(jié)構(gòu)C .索引存儲(chǔ)結(jié)構(gòu)D .散列存儲(chǔ)結(jié)構(gòu)4 .對(duì)于順序表，以下說(shuō)法錯(cuò)誤的是（）。A .順序表是用一維數(shù)組實(shí)現(xiàn)的線性表，數(shù)組的下標(biāo)可以看成是元素的絕對(duì)地址B .順序表的所有存儲(chǔ)結(jié)點(diǎn)按相應(yīng)數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列C .順序表的特點(diǎn)是：邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中仍相鄰D .順序表的特點(diǎn)是：邏輯上相鄰的元素，存儲(chǔ)在物理位置也相鄰的單元中5 .對(duì)順序表上的插入、刪除算法的時(shí)間復(fù)雜度分析來(lái)說(shuō)，通常以 （）為標(biāo)準(zhǔn)操作。A .條件判斷B.結(jié)點(diǎn)移動(dòng)C .算術(shù)表達(dá)式D

15、.賦值語(yǔ)句6 .對(duì)于順序表的優(yōu)缺點(diǎn)，以下說(shuō)法錯(cuò)誤的是（）。A .無(wú)需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間B .可以方便地隨機(jī)存取表中的任一結(jié)點(diǎn)C.插入和刪除操作較方便 D .由于順序表要求占用連續(xù)的空間，存儲(chǔ)分配只能預(yù)先進(jìn)行（靜態(tài)分配）7 .在含有n個(gè)結(jié)點(diǎn)的順序存儲(chǔ)的線性表中，在任一結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)所需移動(dòng)結(jié)點(diǎn)的平均次數(shù) 為（）。A . nB. n/2 C . （n-1）/2 D . （n+1）/28 .在含有n個(gè)結(jié)點(diǎn)的順序存儲(chǔ)的線性表中，刪除一個(gè)結(jié)點(diǎn)所需移動(dòng)結(jié)點(diǎn)的平均次數(shù)為（）。A . n B . n/2C. （n-1）/2 D . （n+1）/29 .帶頭結(jié)點(diǎn)的單鏈表head為空的

16、條件是（）。A. head=NULL B. head->next=NULL C , head->next=head D . head!=NULL10 .非空單循環(huán)鏈表head的尾結(jié)點(diǎn)-p滿足（）。A . p->next=NULL B . p=NULL C. p->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- &g

17、t;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； p->next->pror=s；p->next=s12 .在一個(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

18、=s ； B . p->next=s->next ； s->next=p ；C. q->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; B. s->next=p->next ； p->next=s ；C . s->next=p->next ； p=s ； D . p->next=s ； s->next=p;14 .若某線性表中最

19、常用的操作是取第i個(gè)元素和找第i個(gè)元素的前驅(qū)元素，則采用（）存儲(chǔ) 方式最節(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） ;C. rear=rear->next->next ； free（rear） ; D. p=rear->next->next ； rear->next- >next=p->

20、next free（p）16 .在一個(gè)單鏈表中，若刪除p結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行（）。A. q=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)的對(duì)稱(chēng)性可用（）式來(lái)刻畫(huà)。A . p->pri

21、or->next->=p->next->next B . p->prior->prior=p->next->prior -C. p->prior->next->=p->next->prior D . p->next->next=p->prior->prior18 .在循環(huán)鏈表中，將頭指針改設(shè)為尾指針rear后，其頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的存儲(chǔ)位置分別是（）。A . rear 和 rear->next->nextB. rear->next 和 rear C . rear->next

22、->next 和 rearD. rear 和 rear->next19 .循環(huán)鏈表的主要優(yōu)點(diǎn)是()。A .不再需要頭指針了B ,已知某個(gè)結(jié)點(diǎn)的位置后，容易找到它的直接前驅(qū)C .在進(jìn)行插入、刪除操作時(shí)，能更好地保證鏈表不斷開(kāi)D.從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表20 .在線性表的下列存儲(chǔ)結(jié)構(gòu)中，讀取元素花費(fèi)時(shí)間最少的是()。A .單鏈表 B .雙鏈表 C .循環(huán)鏈表D.順序表二、判斷題，1 .順序存儲(chǔ)的線性表可以隨機(jī)存取。X2 .順序存儲(chǔ)的線性表的插入和刪除操作不需要付出很大的代價(jià)，因?yàn)槠骄看尾僮髦挥薪话?的元素需要移動(dòng)。V3.線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)

23、據(jù)元素具有相同的特性，因此是屬 于同一數(shù)據(jù)對(duì)象。X4.在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上不一定相鄰。，5.在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。V6.在單鏈表中，可以從頭結(jié)點(diǎn)開(kāi)始查找任何一個(gè)元素。X7.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。V8.在線性表的順序存儲(chǔ)結(jié)構(gòu)中，插入和刪除元素時(shí)，移動(dòng)元素的個(gè)數(shù)與該元素的位置有關(guān)。X9.在單鏈表中，要取得某個(gè)元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存 儲(chǔ)結(jié)構(gòu)。X10.順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。三、填空題1 .為了便于討論，有時(shí)將含n(n>0)個(gè)結(jié)點(diǎn)的線性結(jié)構(gòu)表示成(a1

24、, a2,，an),其中每個(gè)ai代 表一個(gè)結(jié)點(diǎn)_。a1稱(chēng)為第一個(gè)結(jié)點(diǎn)，an稱(chēng)為_(kāi)最后一個(gè)結(jié)點(diǎn)，i稱(chēng)為ai R線性表中的一位置 _0對(duì)任意一又t相鄰結(jié)點(diǎn)ai、ai+1(1 < i<n) , ai稱(chēng)為ai+1的直接_前驅(qū)_, ai+1稱(chēng)為ai的直接_ 后繼。2 .線性結(jié)構(gòu)的基本特征是：若至少含有一個(gè)結(jié)點(diǎn)，則除起始結(jié)點(diǎn)沒(méi)有直接前驅(qū)外，其他結(jié)點(diǎn)有且僅有一個(gè)直接 前驅(qū)；除終端結(jié)點(diǎn)沒(méi)有直接 后繼 外，其他結(jié)點(diǎn)有且僅有一個(gè)直接 后繼o3 .所有結(jié)點(diǎn)按一對(duì)一的鄰接關(guān)系構(gòu)成的整體就是線性結(jié)構(gòu)。4 .線性表的邏輯結(jié)構(gòu)是線性 結(jié)構(gòu)，其所含結(jié)點(diǎn)的個(gè)數(shù)稱(chēng)為線性表的長(zhǎng)度。5 .在單鏈表中，刪除p所指結(jié)點(diǎn)的直接

25、后繼的操作是 q=p->next ; p->next=q->next ; free(q) ; 6 .非空的單循環(huán)鏈表head的尾結(jié)點(diǎn)(由指針p所指)滿足p->next= head 。7 . rear是指向非空帶頭結(jié)點(diǎn)的單循環(huán)鏈表的尾指針，則刪除起始結(jié)點(diǎn)的操作可表示為p=rear->next; q=p->next ; p->next=q->next ; free(q) ; 。8 .對(duì)于一個(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ù)雜度為_(kāi)O(n)_。9 .單鏈表表示法的基本

26、思想是用 指針_表示結(jié)點(diǎn)間的邏輯關(guān)系。10 .在順序表中插入或刪除一個(gè)元素，平均需要移動(dòng) 一半 元素，具體移動(dòng)的元素個(gè)數(shù)與元素的位置有關(guān)。11 .在一個(gè)長(zhǎng)度為n的向量的第i(1 &i&n+1)個(gè)元素之前插入一個(gè)元素時(shí)，需向后移動(dòng) n- i+1個(gè)元素。12 .在一個(gè)長(zhǎng)度為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

27、->next; 。15 .設(shè)head指向單鏈表的表頭，p指向單鏈表的表尾結(jié)點(diǎn)，則執(zhí)行 p->next=head后，該單鏈表構(gòu) 成單循環(huán)鏈表。16 .在單鏈表中，若p和s是兩個(gè)指針，且滿足p->next與s相同，則語(yǔ)句p->next=s->next的 作用是_刪除_s指向的結(jié)點(diǎn)。17 .設(shè)r指向單循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)，要在最后一個(gè)結(jié)點(diǎn)之后插入s所指的結(jié)點(diǎn)，需執(zhí)行的三條語(yǔ)句是 s->next= r->next _ ; r->next=s ; r=s ;18 .在單鏈表中，指針p所指結(jié)點(diǎn)為最后一個(gè)結(jié)點(diǎn)的條件是 p->next=NULL。19 .

28、在雙循環(huán)鏈表中，若要在指 p所指結(jié)點(diǎn)前插入s所指的結(jié)點(diǎn)，則需執(zhí)行下列語(yǔ)句：s->next=p; s->prior=p->prior ； _ p->prior->next_=s； p->prior=s ;20.在單鏈表中，若要在p所指結(jié),垣前插入s所指的永，可進(jìn)行下列操作：s->next=p->next _；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))。答：首元

29、結(jié)點(diǎn)是指鏈表中存儲(chǔ)的線性表中的第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。為了操作方便，通常在鏈表 的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱(chēng)為頭結(jié)點(diǎn)。頭指針是指向鏈表中的第一個(gè)結(jié)點(diǎn)的指針。2 .何時(shí)選用順序表，何時(shí)選用鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)為宜？答：從空間上來(lái)看，當(dāng)線性表的長(zhǎng)度變化較大、難以估計(jì)其規(guī)模時(shí)，選用動(dòng)態(tài)的鏈表作為存儲(chǔ)結(jié) 構(gòu)比較合適，但鏈表除了需要設(shè)置數(shù)據(jù)域外，還要額外設(shè)置指針域，因此當(dāng)線性表長(zhǎng)度變化不 大、易于事先確定規(guī)模時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序存儲(chǔ)結(jié)構(gòu)。從時(shí)間上來(lái)看，若線性表 的操作主要是查找，很少進(jìn)行插入和刪除操作時(shí)，應(yīng)選用順序表。對(duì)于頻繁進(jìn)行插入和刪除操作 的線性表，宜采用鏈表作為存儲(chǔ)結(jié)構(gòu)。3 .在

30、順序表中插入和刪除一個(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ù)取決于表長(zhǎng)和插入、刪除的結(jié)點(diǎn)的位置。4 .為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好？答：?jiǎn)窝h(huán)鏈表中無(wú)論設(shè)置尾指針還是頭指針都可以遍歷表中任一個(gè)結(jié)點(diǎn)，但設(shè)置尾指針時(shí)，若在表尾進(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)鏈表中，若僅知道指針

31、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 是無(wú)頭結(jié)點(diǎn)的單鏈表ListNode q, p；if(L&&L->next) q=L ; L=L->next ; p=L;while(p->next) p=p->next ;p->next=q; q->next=NULL ; return L 答：如

32、果長(zhǎng)度大于1,則將首元結(jié)點(diǎn)刪除并插入到表尾。7 .如果有n個(gè)線性表同時(shí)共存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)發(fā)生動(dòng)態(tài)變化，線性表的總長(zhǎng)度 也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選擇哪一種存儲(chǔ)結(jié)構(gòu)？為什么？答：應(yīng)選用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。因?yàn)轫樞虮硎庆o態(tài)存儲(chǔ)結(jié)構(gòu)，只能預(yù)先分配，不能隨著線性表長(zhǎng)度的 改變而變化。而鏈表則可根據(jù)需要?jiǎng)討B(tài)地申請(qǐng)空間，因此適用于動(dòng)態(tài)變化表長(zhǎng)的線性表。8 .若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入、刪除操作，但要求以最快的方式存取線性表的元 素，應(yīng)該用哪種存儲(chǔ)結(jié)構(gòu)？為什么？答：應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。因?yàn)轫樞虼鎯?chǔ)結(jié)構(gòu)存取元素操作的時(shí)間復(fù)雜度為O(1)。五、算法設(shè)計(jì)題1 .試用順序表作為存儲(chǔ)結(jié)構(gòu)，實(shí)

33、現(xiàn)將線性表(a0, al, a2,)就地逆置的操作，所謂“就地”是指輔助空間為0(1)。答：(1)順序表的就地逆置分析：分別用兩個(gè)整型變量指向順序表的兩端，同時(shí)向中間移動(dòng)，移動(dòng)的同時(shí)互換兩個(gè)下標(biāo)指示 的元素的值。void Seqreverse(SeqList L)/順序表的就地逆置for(i=0 ； j=L.1ength-1 ； i<j ； i+ , j-)t=L.datai; L.datai=L.dataj; L.dataj=t; (2)鏈表的就地逆置分析：本算法的思想是逐個(gè)地把L的當(dāng)前元素r插入到新的鏈表頭部。void Linkedreverse(LinkedList L)/鏈表的就

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

35、i=0;while(i<=L.length-1)&&(x>=L.datai) i+;/找正確的插入位置for(k=L.length-1;k>=i ； k-)/元素從后往前依次后移L.datak+1 : L.datak;L.data(i ' x；/x插入到正確位置L.1ength+ ；)3 .設(shè)單鏈表L是一個(gè)非遞減有序表，試寫(xiě)一個(gè)算法將x插入其中后仍保持L的有序性。答：分析：此問(wèn)題的關(guān)鍵是在鏈表中找到x的插入位置，因此需要兩個(gè)指針一前一后地依次向后移動(dòng)。void LinkListinsert(LinkedList L, int x) /x 插入有序鏈表

36、L 中q=L ; p=q>next;while(p!=NULL&&p >data<x) /找到插入的位置q=p ; p=p>next; s=(LinkedList)malloc(sizeof(LNode) ;/生成新結(jié)點(diǎn)S >data=x ； S >next=p; q >next=s ; 4 .試寫(xiě)出在不帶頭結(jié)點(diǎn)的單鏈表的第i個(gè)元素之前插入一個(gè)元素的算法。答：分析：對(duì)不帶頭結(jié)點(diǎn)的鏈表操作時(shí)，要注意對(duì)第一個(gè)結(jié)點(diǎn)和其他結(jié)點(diǎn)操作的不同。void LinkedListlnsert(LinkedList head, int x , int i)/

37、不帶頭結(jié)點(diǎn)的單鏈表的第i個(gè)元素之前插入一個(gè)元素p=L : j=1;while(p!=NULL&&j<i-1)/找到第 i-1 個(gè)元素p=p >next; j+ ; if(i<=0|p=NULL) printf("插入位置不正確、n”)；else q=(LinkedList)malloc(sizeof(LNode); q>data=x ；if(i=1) q >next=L ； L=q； /在第一個(gè)元素之前插入elseq >next=p >next; p>next=q ; /在其他位置插入 )5 .設(shè)A、B是兩個(gè)線性表，其表

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

39、 中當(dāng)前元素較小C.datak=A.datail； i+ ；else C.datak=B.dataj;j+; /B 中當(dāng)前元素較小k+ ； if (i=m) for(t=j ; t<n ； t+) C.datak=B.datat;k+ ； /B表長(zhǎng)度大于 A表 else for(t=i ; t<m； t+) C.datak=A.datat ; k+； /A表長(zhǎng)度大于 B表 C.length=m+n ； return C;VOid Linkmerge(LinkedList A , LinkedList B , LinkedList C)/有序鏈表A和B歸并成有序鏈表Cpa=A>

40、next; pb=B >next; C=A pc=C;while(pa&&pb) /A和B都不為空時(shí)if(pa>data<pb>data)/ 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(pa)pc >next=pa；/A沒(méi)有結(jié)束，將A表剩余元素鏈接到 C表if(pb)pc >next=pb;/B沒(méi)有結(jié)

41、束，將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指向此位置。然后在lb中找到第j個(gè)結(jié)點(diǎn)，將 p所指向的la表中的第i個(gè)及q所指向的最后一個(gè)共len個(gè)結(jié)點(diǎn)插入到lb中。void Deletelnsert(LinkedList la ,

42、LinkedList lb , int i , int j, int len)/刪除不帶頭結(jié)點(diǎn)的單鏈表la中第i個(gè)元素起共len個(gè)元素，并將這峰元素插入到單鏈表lb 中第j個(gè)結(jié)點(diǎn)之前if(i<0|j<0|len<0) exit(0)；p=la ； k=1； pre=NULLwhile(p&&k<i) /在la表中查找第i個(gè)結(jié)點(diǎn)pre=p ; p=p->next; k+； if(!p) exit(0) ；q=p ; k=l ；/p指向la表中第i個(gè)結(jié)點(diǎn)while(q&&k<len) q=q >next; k+ ； /查找

43、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；/j>1 時(shí)while(r&&k<j-1) r=r >next; k+ ； /查找 Lb 表中第 i 1 個(gè)元素if(!r) exit(0);q >next=r >next; r >next=p ;/完成插

44、入 7 .單鏈表L是一個(gè)遞減有序表，試寫(xiě)一高效算法，刪除表中值大于 min且小于max的2點(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(min>max) printf( " min>max n" ) ； exit(0) ; else p=L >next;/q始終指向p的前驅(qū)while(p >data>=max)/當(dāng)前元素大于或等

45、于 max,則p、q依次向后移動(dòng)q=p ; p=p >next; while(p!=NULL)&&(p ->data>min) /當(dāng)前元素的值比min大同時(shí)比max小，刪除p指向的結(jié)點(diǎn)q >next=p>next, free(p) ; p=q>next;return L ；8 .編寫(xiě)一個(gè)算法將一個(gè)頭結(jié)點(diǎn)指針為 pa的單鏈表A分解成兩個(gè)單鏈表A和B,其頭結(jié)點(diǎn)指針?lè)謩e 為pa和pb,使得A鏈表中含有原鏈表A中序號(hào)為奇數(shù)的元素，而B(niǎo)鏈表中含有原鏈表A中序號(hào)為 偶數(shù)的元素，且保持原來(lái)的相對(duì)順序。答：分析：用兩個(gè)工作指針p和q分別指示序號(hào)為奇數(shù)和序號(hào)為

46、偶數(shù)的結(jié)點(diǎn)，將 q所指向的結(jié)點(diǎn) 從A表刪除，并鏈接到B表。void decompose(LinkedList A , LinkedList B)/單鏈表A分解成元素序號(hào)為奇數(shù)的單鏈表 A和元素序號(hào)為偶數(shù)的單鏈表Bp=A->next ; B=(LinkedList)malloc(sizeof(LNode) ;r=B ；while(p!=NULL&&p->next!=NULL)q=p >next;/q指向偶數(shù)序號(hào)的結(jié)點(diǎn)p >next=q>next;/將 q 從 A表中刪除r >next=q ;/將q結(jié)點(diǎn)鏈接到B鏈表的末尾r=q ;/r總是指向B鏈

47、表的最后一個(gè)結(jié)點(diǎn)p=p >next;/p指向原鏈表A中的奇數(shù)序號(hào)的結(jié)點(diǎn)r >next=NULL.；/將生成B鏈表中的最后一個(gè)結(jié)點(diǎn)的next域置為空9 .假設(shè)以兩個(gè)元素依值遞增有序排列的線性表A、B分別表示兩個(gè)集合，要求另辟空間構(gòu)造一個(gè)線性表C,其元素為兩集合的交集，且表 C中的元素也依值遞增有序排列。對(duì)順序表編寫(xiě)求C的算法。答：分析：用三個(gè)變量i、j、k分別指示A、B、C三個(gè)順序表的當(dāng)前位置，若 A、B表中當(dāng)前元素 值相同，則寫(xiě)入C中，并使i、j、k值增1;若A表元素值較小，則使i增1;若B表元素值較 小，則使j增1,直到有一個(gè)表先結(jié)束。SeqLiSt intersection(S

48、eqList A , SeqList B , SeqList C)/求元素依值遞增有序排列的順序表 A、B的交集Ci=0 ； j=0 ； k=0；while(i<=A.length-1)&&(j<=B.length-1)if(A.datai=B.dataj)/找到值相同的元素C.datak=A.datai ；/相同元素寫(xiě)入C表中k+； i+ ; j+ ;elseif(A.datai<B.dataj) i+； /A、B表當(dāng)前元素不等，值較小的下標(biāo)增 1else j+；C.length=k；return C ;10 .設(shè)有線性表 A=(a1, a2,，am)和B=

49、(b1, b2,，bn)。試編寫(xiě)合并 A、B為線性表C的算 法，使得：C=(a1 , b1,，am bm bm+1,bn)(當(dāng) m< n 時(shí))或(a1 , b1,，an, bn, an+1, am)(當(dāng)m>n時(shí))，線性表A、B C均以單鏈表作為存儲(chǔ)結(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(LinkedList A , LinkedList B , LinkedList C)/把鏈

50、表A和B合并為C, A和B的元素間隔排列，且使用原存儲(chǔ)空間p=A >next; q=B >next ; C=A while(p&&q)nextp=p >next; p>next=q ;/將 B 的元素插入if(nextp) nextq=q->next ; q->next=nextp ; /如果 A非空，將 A的元素插入 p=nextp ; q=nextq ; 11 .假設(shè)在長(zhǎng)度大于1的單循環(huán)鏈表中，既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針。s為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫(xiě)算法刪除結(jié)點(diǎn)s的直接前驅(qū)結(jié)點(diǎn)。答：分析：因?yàn)榧炔恢来藛窝h(huán)鏈表的頭指針，也不知道其尾指

51、針，所以找s的前驅(qū)就只能從s開(kāi)始，順次向后尋找。void DeletePre(LinkedNode s)/刪除單循環(huán)鏈表中結(jié)點(diǎn)s的直接前驅(qū) p=s ;while(p >next>next!=s) p=p >next; /找至U 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-&g

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

53、, LinkedList pc)/分解含有三類(lèi)字符的單鏈表為三個(gè)以循環(huán)鏈表表示的線性表，使其分別含有三類(lèi)字符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; pc>next=pc ;while(p!=L)q=p >next ; /q記下L中下一個(gè)結(jié)點(diǎn)的位置if(p >data<=' z' &&p- >data>

54、=' a' )/鏈接到字母鏈表的頭部p >next=pa>next ； pa >next=p ； else if (p >data<=' 9' &&(p ->data>=' 0' ) /鏈接到數(shù)字鏈表的頭部 p >next=pb>next ; pb>next=p; elsep->next=pc->next ； pc->next=p ； /鏈接到其他字母鏈表的頭部 p=q ; 14、己知A、B和C為三個(gè)遞增有序的線性表，現(xiàn)要求對(duì)A表進(jìn)行如下操作：刪去那些既

55、在 B表中出現(xiàn)又在C表中出現(xiàn)的元素。試對(duì)順序表編寫(xiě)實(shí)現(xiàn)上述操作的算法(注：題中未特別指明同一表中的元素值各不相同)0 答：分析：先從B和C中找出共有元素，記為same再在A中從當(dāng)前位置開(kāi)始，凡小于 same的元 素均保留(存到新的位置)，等于same的就跳過(guò)，至U大于same時(shí)就再找下一個(gè)Same SeqList IntersectDelete(SeqList A , SeqList B , SeqList C) /對(duì)順序表A刪去那些既在B表中出現(xiàn)又在C表中出現(xiàn)的元素 i=0 ; j=0 ; k=0; m=0; /i指示A中元素原來(lái)的位置，m為移動(dòng)后的位置 while(i<A.lengt

56、h&&i<B.length&&k<C.length) if(B.dataj<C.datak) j+；else if(B.dataj>C.datak) k+; else same=B.dataj ；/找至U了相同元素 samewhile(B.dataj=same) j+;while(C.datak=same) k+； /j、k 后移到新的元素while(i<A.length&&A.datai<same) A.datam+=A.datai+; /需保留的元素移動(dòng)到新位置while(i<A.1ength&

57、;&A.datai1=same i+; /跳過(guò)相同的元素 while(i<A.length) A.datam+=A.datai+ ;/A的剩余元素重新存儲(chǔ)A.1ength=m ；15 .雙循環(huán)鏈表中，設(shè)計(jì)滿足下列條件的算法。 (1)在值為x的結(jié)點(diǎn)之前插入值為y的結(jié)點(diǎn)。(2)在值為x的結(jié)點(diǎn)之后插入值為y的結(jié)點(diǎn)。(3)刪 除值為x的結(jié)點(diǎn)。 答：分析：在雙循環(huán)鏈表中插入和刪除結(jié)點(diǎn)要注意修改雙向的指針。 typedef struct DLNode DataType data ; struct DLNodeprior, next; DLNode,DLinkedList ;void DLin

58、sertl(DLinkedList L , int x , int y) /在雙循環(huán)鏈表中插入結(jié)點(diǎn) p=L->next ; while(p!=L&&p->data!=x) p=p->next ; /在鏈表中查找值為 x 的結(jié)點(diǎn) if(p->data=x) /找到值為x的結(jié)點(diǎn) q=p->prior ；/q指向值為x的結(jié)點(diǎn)的前驅(qū)s=(DLinkedList)malloc(sizeof(DLNode) ; s->data=y ； s->next=p ； s->prior=q ；/將 y 插入至U q與 p指向的結(jié)點(diǎn)之間p->prior=s ; q->next=s ; elseprintf( " 沒(méi)有值為 x 的結(jié)點(diǎn)”)；exit(0) ； void DLDelete(DLinkedList L , int x) /在雙循環(huán)鏈表中刪除結(jié)點(diǎn) p=L->next ; while(p!=L&am