計(jì)算機(jī)軟件技術(shù)基礎(chǔ)自學(xué)

1、數(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)的類型要一致 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操作對(duì)象 B計(jì)算方法 C邏輯存儲(chǔ) D數(shù)據(jù)映像(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ù)元素

2、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索引存取 DHash存取6算法分析的目的是( )。A找出數(shù)據(jù)結(jié)構(gòu)的合理性 B研究算法中的輸入和輸出的關(guān)系 *C分析算法的效率以求改進(jìn) D分析算法的易懂性和文檔性7計(jì)算機(jī)算法指的是( (1) )，它必須具備輸入、輸出和( (2) )等五個(gè)特征。 (1) A計(jì)算方法 B排序方法 *C解決某一問題的有限運(yùn)算序列 D調(diào)度方法 (

3、2) 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ù)元素之間關(guān)系的不同特性，以下四類基本的邏輯結(jié)構(gòu)反映了四類基本的數(shù)據(jù)組織形式，其中解釋錯(cuò)誤的是( )。*A集合中任何兩個(gè)結(jié)點(diǎn)之間都有邏輯關(guān)系但組織形式松散 B線

4、性結(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ù)的最小單位。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ī)中的映像分別稱為存儲(chǔ)結(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ì)

5、算機(jī)中實(shí)際的存儲(chǔ)形式。7算法和程序沒有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的。8順序存儲(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)系_。2，數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，它包括三方面的內(nèi)容_數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、對(duì)數(shù)據(jù)施加的操作_。3數(shù)據(jù)的邏輯結(jié)構(gòu)包括_集合結(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é)

6、點(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）_。 S=0； for(i=1；i=n；i+) for(j=1；j=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)看，通常所說的“數(shù)據(jù)”應(yīng)分成三個(gè)不同的層次，即_數(shù)據(jù)_、_數(shù)據(jù)元素_和_數(shù)據(jù)項(xiàng)_。12根據(jù)需要，數(shù)據(jù)元素又被稱為_結(jié)點(diǎn)_、_記錄_、

7、_元素_或_頂點(diǎn)_。13通常，存儲(chǔ)結(jié)點(diǎn)之間可以有_順序存儲(chǔ)_、_鏈?zhǔn)酱鎯?chǔ)_、_索引存儲(chǔ)_、_散列存儲(chǔ)_四種關(guān)聯(lián)方式，稱為四種基本存儲(chǔ)方式。14通常從_確定性_、_可讀性_、_健壯性_、_高效性_等幾方面評(píng)價(jià)算法(包括程序)的質(zhì)量。15一個(gè)算法的時(shí)空性能是指該算法的_時(shí)間復(fù)雜度_和_空間復(fù)雜度_，前者是算法包含的_計(jì)算量_，后者是算法需要的_存儲(chǔ)量_。16在一般情況下，一個(gè)算法的時(shí)間復(fù)雜度是_問題規(guī)模_的函數(shù)。17常見時(shí)間復(fù)雜度的量級(jí)有：常數(shù)階O(_1_)、對(duì)數(shù)階O(_log2n_)、線性階O(_n_)、平方階O(_n2_)和指數(shù)階O(_2n_)。通常認(rèn)為，具有指數(shù)階量級(jí)的算法是_不可行_的。1

8、8數(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ù)類型是指一個(gè)_數(shù)學(xué)模型_以及定義在該模型上的一組操作。四、應(yīng)用題1分析下列程序段的時(shí)間復(fù)雜度。 i=1； WHILE (i=n) i=i*2； 答：O(log2n)2敘述算法的定義及其重要特性。答：算法是對(duì)特定問題求解步驟的一種描述，是指令的有限序列。其中每一條指令表示一個(gè)或多個(gè)操作。算法應(yīng)該具有下列特性：可行性、確定性、有窮性、輸入和輸出。3簡述下列術(shù)語：數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)對(duì)象。答：數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符，以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序識(shí)別和處理

9、的符號(hào)的集合。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(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ù)元素之間的邏輯關(guān)系。邏輯結(jié)構(gòu)與計(jì)算機(jī)無關(guān)，存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中的表示。5將數(shù)量級(jí)210，n，n2，n3，nlog2n，log2n，2n，n!，(23)n，n23按增長率進(jìn)行排列。答：(23)n，210，log2n，n23，n，nlog2n，n2，n3，

10、2n，n!6設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為：D=k1，k2，k3，k9，R=，畫出這個(gè)邏輯結(jié)構(gòu)的圖示，并確定相對(duì)于關(guān)系R，哪些結(jié)點(diǎn)是開始結(jié)點(diǎn)，哪些結(jié)點(diǎn)是終端結(jié)點(diǎn)？答：圖略。開始結(jié)點(diǎn)k1、k2，終端結(jié)點(diǎn)k6、k7。7設(shè)有如圖1.1所示的邏輯結(jié)構(gòu)圖，給出它的邏輯結(jié)構(gòu)，并說出它是什么類型的邏輯結(jié)構(gòu)。答：數(shù)據(jù)邏輯結(jié)構(gòu)為：D=k1，k2，k3，k8，R=，其邏輯結(jié)構(gòu)類型為樹型結(jié)構(gòu)。8分析下列程序的時(shí)間復(fù)雜度(設(shè)n為正整數(shù))。 (1)int rec(int n) if(n=1)return(1)； else return(n*rec(n-1)； (2)x=91；y=100； While (y0) if(x10) y-

11、； (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ù)。試確定下列各程序段中前面加記號(hào)的語句的頻度： (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 Chead-next=head Dhead!=NULL10非空單循環(huán)鏈表head的尾結(jié)點(diǎn)*p滿足( )。 Ap-next=NULL Bp=NULL

12、*Cp-next=head Dp=head11在雙循環(huán)鏈表的*p結(jié)點(diǎn)之后插入*s結(jié)點(diǎn)的操作是( )。 Ap-next=s；s-prior=p；p-next-prior=s；s-next=p-next； Bp-next=s；p-next-prior=s；s-prior=p：s-next=p-next； Cs-prior=p；s-next=p-next；p-next=s；p-next-prior=s； *Ds-prior=p；s-next=p-next；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í)行(

13、)。 As-next=p-next；p-next=s； Bp-next=s-next；s-next=p； *Cq-next=s; s-next=p； Dp-next=s; s-next=q；13. 在一個(gè)單鏈表中，若*p結(jié)點(diǎn)不是最后結(jié)點(diǎn)。在*p之后插入結(jié)點(diǎn)*s，則執(zhí)行( )。 As-next=p；p-next=s; *Bs-next=p-next；p-next=s； Cs-next=p-next； p=s； Dp-next=s； s-next=p;14. 若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前驅(qū)元素，則采用( )存儲(chǔ)方式最節(jié)省時(shí)間。 *A順序表 B. 單鏈表 C雙鏈表 D單循

14、環(huán)鏈表15設(shè)rear是指向非空帶頭結(jié)點(diǎn)的單循環(huán)鏈表的尾指針，則刪除表頭結(jié)點(diǎn)的操作可表示為( )。 Ap=rear；rear=rear-next； free(p) Brear=rear-next；free(rear)； Crear=rear-next-next； free(rear)； *Dp=rear-next-next；rear-next-next=p-next；free(p)；16在一個(gè)單鏈表中，若刪除*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行( )。 *Aq=p-next；p-next=q-next；free(q)； Bp=p-next；p-next=p-next-next；free(p)； Cp-ne

15、xt=p-next；free(p-next)； Dp=p-next-next；free(p-next)；17設(shè)指針p指向雙鏈表的某一結(jié)點(diǎn)，則雙鏈表結(jié)構(gòu)的對(duì)稱性可用( )式來刻畫。 Ap-prior-next-=p-next-next Bp-prior-prior=p-next-prior *Cp-prior-next-=p-next-prior Dp-next-next=p-prior-prior18在循環(huán)鏈表中，將頭指針改設(shè)為尾指針rear后，其頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的存儲(chǔ)位置分別是( )。 Arear和rear-next-next *Brear-next和rear Crear-next-next和

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

17、，邏輯上相鄰的兩個(gè)元素在物理位置上不一定相鄰。5在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。6在單鏈表中，可以從頭結(jié)點(diǎn)開始查找任何一個(gè)元素。7線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。8在線性表的順序存儲(chǔ)結(jié)構(gòu)中，插入和刪除元素時(shí)，移動(dòng)元素的個(gè)數(shù)與該元素的位置有關(guān)。9在單鏈表中，要取得某個(gè)元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。10順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(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在線性表中的

18、_位置_。對(duì)任意一對(duì)相鄰結(jié)點(diǎn)ai、ai+1(1inext；p-next=q-next；free(q)；_6非空的單循環(huán)鏈表head的尾結(jié)點(diǎn)(由指針p所指)滿足_ p-next= head _。7rear是指向非空帶頭結(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ù)雜度為_ O(n)_。9單鏈表表示法的基本思想是用_指針_表示結(jié)點(diǎn)間的邏輯關(guān)系。10在順序表中插入或刪除一個(gè)元素

19、，平均需要移動(dòng)_一半_元素，具體移動(dòng)的元素個(gè)數(shù)與_元素的位置_有關(guān)。11在一個(gè)長度為n的向量的第i(1in+1)個(gè)元素之前插入一個(gè)元素時(shí)，需向后移動(dòng)_ n-i+1_個(gè)元素。12在一個(gè)長度為n的向量中刪除第i(1in)個(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在單鏈

20、表中，若p和s是兩個(gè)指針，且滿足p-next與s相同，則語句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í)行的三條語句是_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)行

21、下列操作： 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))。答：首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)的線性表中的第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。為了操作方便，通常在鏈表的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)。頭指針是指向鏈表中的第一個(gè)結(jié)點(diǎn)的指針。2何時(shí)選用順序表，何時(shí)選用鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)為宜？答：從空間上來看，當(dāng)線性表的長度變化較大、難以估計(jì)其規(guī)模時(shí)，選用動(dòng)態(tài)的鏈表作為存儲(chǔ)結(jié)構(gòu)比較合適，但鏈表除了需要設(shè)置數(shù)據(jù)域外，還要額外設(shè)置

22、指針域，因此當(dāng)線性表長度變化不大、易于事先確定規(guī)模時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序存儲(chǔ)結(jié)構(gòu)。從時(shí)間上來看，若線性表的操作主要是查找，很少進(jìn)行插入和刪除操作時(shí)，應(yīng)選用順序表。對(duì)于頻繁進(jìn)行插入和刪除操作的線性表，宜采用鏈表作為存儲(chǔ)結(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í)

23、，若在表尾進(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)的單鏈表 ListNode *q，*p； if(L&L-next)

24、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í)共存，并且在處理過程中各表的長度會(huì)發(fā)生動(dòng)態(tài)變化，線性表的總長度也會(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ù)先分配，不能隨著線性表長度的改變而變化。而鏈表則可根據(jù)需要?jiǎng)討B(tài)地申請(qǐng)空間，因此適用于動(dòng)態(tài)變化表長的線性表。8若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入、刪除操作，但要求以最快的方式存取線性表的元素，應(yīng)該用哪

25、種存儲(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í)現(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!=NULL) r=p，p=p-next； r指向當(dāng)前待逆置的結(jié)點(diǎn)，p記下下個(gè)結(jié)

26、點(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.length-1;k=i；k-) 元素從后往前依次后移 L.datak+1：L.datak； L.data(ix； x插入到正確位置 L.1e

27、ngth+； ) 3.設(shè)單鏈表L是一個(gè)非遞減有序表，試寫一個(gè)算法將x插入其中后仍保持L的有序性。答：分析：此問題的關(guān)鍵是在鏈表中找到x的插入位置，因此需要兩個(gè)指針一前一后地依次向后移動(dòng)。 void LinkListinsert(LinkedList L，int x)x插入有序鏈表L中 q=L；p=qnext； while(p!=NULL&pdatanext； s=(LinkedList)malloc(sizeof(LNode)； 生成新結(jié)點(diǎn) Sdata=x； Snext=p； qnext=s； 4. 試寫出在不帶頭結(jié)點(diǎn)的單鏈表的第i個(gè)元素之前插入一個(gè)元素的算法。答：分析：對(duì)不帶頭結(jié)點(diǎn)的鏈表操作

28、時(shí)，要注意對(duì)第一個(gè)結(jié)點(diǎn)和其他結(jié)點(diǎn)操作的不同。 void LinkedListlnsert(LinkedList head，int x，int i) 不帶頭結(jié)點(diǎn)的單鏈表的第i個(gè)元素之前插入一個(gè)元素 p=L：j=1; while(p!=NULL&jnext；j+； if(idata=x； if(i=1) qnext=L；L=q； 在第一個(gè)元素之前插入 elseqnext=pnext；pnext=q； 在其他位置插入 5設(shè)A、B是兩個(gè)線性表，其表中元素遞增有序，長度分別為m和n。試寫一算法分別以順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)將A和B歸并成一個(gè)仍按元素值遞增有序的線性表C。答：(1)分析：用三個(gè)變量i、j、k分別

29、指示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.datail；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表長度大

30、于A表 else for(t=i；tnext；pb=Bnext；C=A；pc=C； while(pa&pb) A和B都不為空時(shí) if(padatadata) 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)pcnext=pa； A沒有結(jié)束，將A表剩余元素鏈接到C表if(pb)pcnext=pb； B沒有結(jié)束，將B表剩余元素鏈接到C表free(B)； 釋放B表的頭結(jié)點(diǎn)本算法需要遍歷兩個(gè)線性表，因此時(shí)間復(fù)雜度為O(m+n)。6

31、設(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，LinkedList lb，int i，int j, int len)刪除不帶頭結(jié)點(diǎn)的單鏈表la中第i個(gè)元素起共len個(gè)元素,并將這峰元

32、素插入到單鏈表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指向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=qnext； i=1的情況 else prenext=qnext； 完成刪除 將從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&k

33、next； k+； 查找Lb表中第i1個(gè)元素 if(!r) exit(0)； qnext=rnext；rnext=p； 完成插入 7單鏈表L是一個(gè)遞減有序表，試寫一高效算法，刪除表中值大于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(”minmaxn”)； exit(0)； else p=Lnext； q始終指向p的前驅(qū)while(p

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

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

36、置為空 9假設(shè)以兩個(gè)元素依值遞增有序排列的線性表A、B分別表示兩個(gè)集合，要求另辟空間構(gòu)造一個(gè)線性表C，其元素為兩集合的交集，且表C中的元素也依值遞增有序排列。對(duì)順序表編寫求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、B的交集C i=0； j=0；k=0； while(i=A.lengt

37、h-1)&(j=B.length-1) if(A.datai=B.dataj) 找到值相同的元素 C.datak=A.datai； 相同元素寫入C表中 k+；i+；j+； else if(A.datain時(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)把鏈表A和B合并為C，A和B的元素間

38、隔排列，且使用原存儲(chǔ)空間 p=Anext；q=Bnext；C=A；while(p&q) nextp=pnext；pnext=q； 將B的元素插入 if(nextp) nextq=q-next；q-next=nextp；如果A非空，將A的元素插入 p=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)榧炔恢来藛窝h(huán)鏈表的頭指針，也不知道其尾指針，所以找s的前驅(qū)就只能從s開始，順次向后尋找。void DeletePre(LinkedNode *s)刪除單循環(huán)鏈表中結(jié)點(diǎn)s的直接

39、前驅(qū) p=s； while(pnextnext!=s) p=pnext； 找到s的前驅(qū)的前驅(qū)p q=pnext； q是p的后繼，即s的前驅(qū) pnext=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=headnext； i=0； while(p!=head) i+；p=p-next； return i； 13已知由單鏈表表示的線性表中，含有三類字符的數(shù)據(jù)元素(如：字母字符、數(shù)字字符和其他字符)，試編寫算法構(gòu)造三個(gè)以循環(huán)鏈表表示的線性表，使得每個(gè)表中只含有同一類的字符，且利用原表中

40、的結(jié)點(diǎn)空間作為這三個(gè)表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。答：分析：p指向待處理的單鏈表的首元結(jié)點(diǎn)，構(gòu)造三個(gè)空的單循環(huán)鏈表，分別存儲(chǔ)三類字符，其中一個(gè)可使用原來的單鏈表。q指向p的下一個(gè)結(jié)點(diǎn)，根據(jù)*p的數(shù)據(jù)域的值將其插入到不同的鏈表上。再把q的值給p，處理下一個(gè)結(jié)點(diǎn)。void change(LinkedList L，LinkedList pa，LinkedList pb，LinkedList pc)分解含有三類字符的單鏈表為三個(gè)以循環(huán)鏈表表示的線性表，使其分別含有三類字符 p=Lnext； pa=L； panext=pa； 分別構(gòu)造三個(gè)單循環(huán)鏈表 pb=(LinkedList)malloc(size

41、of(LNode)； pc=(LinkedList)malloc(sizeof(LNode)； pbnext=pb；pcnext=pc； while(p!=L) q=pnext； q記下L中下一個(gè)結(jié)點(diǎn)的位置 if(pdatadata=a) 鏈接到字母鏈表的頭部 pnext=panext；panext=p； else if (pdatadata=0) 鏈接到數(shù)字鏈表的頭部 pnext=pbnext；pbnext=p； elsep-next=pc-next；pc-next=p；鏈接到其他字母鏈表的頭部 p=q； 14、己知A、B和C為三個(gè)遞增有序的線性表，現(xiàn)要求對(duì)A表進(jìn)行如下操作：刪去那些既在B表中出現(xiàn)又在C表中出現(xiàn)的元素。試對(duì)順序表編寫實(shí)現(xiàn)上述操作的算法(注：題中未特別指明同一表中的元素值各不相同)。答：分析：先從B和C中找出共有元素，記為same，再在A中從當(dāng)前位置開始，凡小于same的元素均保留(存到新的位置)，等于same的就跳過，到大于same時(shí)就再找下一個(gè)SameSeqList 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中元素原來的位置，m為移動(dòng)后