《計算機軟件技術(shù)基礎(chǔ)》課后題答案

數(shù)據(jù)結(jié)構(gòu)習(xí)題答案第一節(jié)概論一\選擇題.要求同一邏輯結(jié)構(gòu)的所有數(shù)據(jù)元素具有相同的特性,這意味著（）〇A,數(shù)據(jù)元素具有同一的特點?B.不僅數(shù)據(jù)元素包含的數(shù)據(jù)項的個數(shù)要相同,而且對應(yīng)數(shù)據(jù)項的類型要一致C,每個數(shù)據(jù)元素都一樣D.數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等.數(shù)據(jù)結(jié)構(gòu)是ー門研究非數(shù)值計算的程序設(shè)計問題中計算機的（（1））以及它們之間的（（2））和運算的學(xué)科。（1）A,操作對象 B.計算方法?C.物理存儲D,數(shù)據(jù)映像⑵A.結(jié)構(gòu)?B.關(guān)系 C.運算 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.動態(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.隨機存取 B.順序存取C.索引存取D.Hash存取.算法分析的目的是（）〇A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B,研究算法中的輸入和輸出的關(guān)系?C.分析算法的效率以求改進D,分析算法的易懂性和文檔性.計算機算法指的是（（1））,它必須具備輸入、輸出和（（2））等五個特征。A.計算方法 B,排序方法 ?C.解決某ー問題的有限運算序列 D.調(diào)度方法A.可行性、可移植性和可擴充性?B.可行性、確定性和有窮性C,確定性,有窮性和穩(wěn)定性D.易讀性、穩(wěn)定性和安全性.線性表若采用鏈表存儲結(jié)構(gòu),要求內(nèi)存中可用存儲單元的地址（）〇A,必須是連續(xù)的 B,部分必須是連續(xù)的 C.—定是不連續(xù)的 ?D.連續(xù)不連續(xù)都可以.在以下的敘述中,正確的是（）〇A.線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu)*B.二維數(shù)組是它的每個數(shù)據(jù)元素為ー個線性表的線性表C.棧的操作方式是先進先出D?隊列的操作方式是先進后出10.根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性,以下四類基本的邏輯結(jié)構(gòu)反映了四類基本的數(shù)據(jù)組織形式,其中解釋錯誤的是（）〇*A.集合中任何兩個結(jié)點之間都有邏輯關(guān)系但組織形式松散B.線性結(jié)構(gòu)中結(jié)點按邏輯關(guān)系依次排列形成一條“鎖鏈”C,樹形結(jié)構(gòu)具有分支、層次特性,其形態(tài)有點像自然界中的樹D.圖狀結(jié)構(gòu)中的各個結(jié)點按邏輯關(guān)系互相纏繞,任何兩個結(jié)點都可以鄰接11.以下說法正確的是（）〇A,數(shù)據(jù)元素是數(shù)據(jù)的最小單位B,數(shù)據(jù)項是數(shù)據(jù)的基本單位C,數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合?D.數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合二、判斷題X1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。丿2.數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。V3,數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、數(shù)據(jù)項在計算機中的映像分別稱為存儲結(jié)構(gòu)、結(jié)點、數(shù)據(jù)域。X4.數(shù)據(jù)項是數(shù)據(jù)的基本單位。V5,數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系,是用戶按使用需要建立的。V6.數(shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù)在計算機中實際的存儲形式。X7.算法和程序沒有區(qū)別,所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的。V8.順序存儲結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu),鏈?zhǔn)酱鎯Y(jié)構(gòu)屬于動態(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ù)施加的操作ー〇.數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合結(jié)構(gòu)ー、線性結(jié)構(gòu)ー、ー樹型結(jié)構(gòu)和一圖狀結(jié)構(gòu)四種類型。.在線性結(jié)構(gòu)中,開始結(jié)點ー沒有一前驅(qū)結(jié)點,其余每個結(jié)點有且只有——個ー個前驅(qū)結(jié)點。.在樹形結(jié)構(gòu)中,根結(jié)點只有一ー個ー,其余每個結(jié)點有且只有一ー個一前驅(qū)結(jié)點;葉結(jié)點沒有一后繼結(jié)點,其余每個結(jié)點的后繼結(jié)點可以有—任意個.在圖形結(jié)構(gòu)中,每個結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點可以有一任意個ー〇.算法的五個重要特性是一可行性一、ー確定性ー、一有窮性一、ー輸入—、ー輸出—。.下列程序段的時間復(fù)雜度是ー。（n）ー〇for（i=l；i<=n；i++）A[i,i]=0；.下列程序段的時間復(fù)雜度是ー0（n2）ー〇S=0；for（i=l；i〈=n；i++）for（j=l；j<=n；j++） s=s+B[i,j]；sum=s；.存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)的一物理—實現(xiàn)。11.從數(shù)據(jù)結(jié)構(gòu)的觀點看,通常所說的“數(shù)據(jù)”應(yīng)分成三個不同的層次,即—數(shù)據(jù)—、—數(shù)據(jù)元素一和—數(shù)據(jù)項ー〇12,根據(jù)需要,數(shù)據(jù)元素又被稱為—結(jié)點—、—記錄、元素_或ー頂點ー。13,通常,存儲結(jié)點之間可以有一順序存儲_、鏈?zhǔn)酱鎯Α⑺饕鎯Α?、一散列存?四種關(guān)聯(lián)方式,稱為四種基本存儲方式。.通常從ー確定性一、一可讀性一、ー健壯性一、一高效性一等幾方面評價算法(包括程序)的質(zhì)量。.ー個算法的時空性能是指該算法的ー時間復(fù)雜度一和一空間復(fù)雜度ー,前者是算法包含的ー計算量—,后者是算法需要的ーーー存儲量—。.在一般情況下,ー個算法的時間復(fù)雜度是ー問題規(guī)模—的函數(shù)。.常見時間復(fù)雜度的量級有:常數(shù)階0(_1一)、對數(shù)階0(ーーlog2n)、線性階0(—n—)、平方階0(_n2_)和指數(shù)階0(_21)。通常認為,具有指數(shù)階量級的算法是ー不可行一的。.數(shù)據(jù)結(jié)構(gòu)的基本任務(wù)是數(shù)據(jù)結(jié)構(gòu)的—設(shè)計—和—實現(xiàn)ー。.數(shù)據(jù)對象是性質(zhì)相同的ー數(shù)據(jù)元素一的集合。.抽象數(shù)據(jù)類型是指ー個ー數(shù)學(xué)模型一以及定義在該模型上的ー組操作。四、應(yīng)用題1.分析下列程序段的時間復(fù)雜度。1=1;WHILE(i<=n) i=i*2；答:0(log2n)2,敘述算法的定義及其重要特性。答:算法是對特定問題求解步驟的ー種描述,是指令的有限序列。其中每一條指令表示一個或多個操作。算法應(yīng)該具有下列特性:可行性、確定性、有窮性、輸入和輸出。.簡述下列術(shù)語:數(shù)據(jù),數(shù)據(jù)元素,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)對象。答：數(shù)據(jù)是信息的載體,是描述客觀事物的數(shù)、字符,以及所有能輸入到計算機中并被計算機程序識別和處理的符號的集合。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。在不同的條件下,數(shù)據(jù)元素又可稱為元素、結(jié)點、頂點、記錄等。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著ー種或多種關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合。.邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是什么關(guān)系?答:在數(shù)據(jù)結(jié)構(gòu)中,邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是密切相關(guān)的,存儲結(jié)構(gòu)不僅將數(shù)據(jù)元素存儲到計算機中,而且還要表示各數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯結(jié)構(gòu)與計算機無關(guān),存儲結(jié)構(gòu)是數(shù)據(jù)元素之間的關(guān)系在計算機中的表示。.將數(shù)量級ク°,n,n2,n\nlog2n,log2n,2'\n!,(2/3)、帯/3按增長率進行排列。答:(2/3)n,210,log2n,n,n,nlog2n,n2,n3,2'\n!.設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為:D={kl,k2,k3,…，k9},R={<kl,k3>,<kl,k8>,<k2,k3>,<k2,k4>,<k2,k5>,<k3,k9>,<k5,k6>,<k8,k9>,<k9,k7>,<k4,k6>},畫出這個邏輯結(jié)構(gòu)的圖示,并確定相對于關(guān)系R,哪些結(jié)點是開始結(jié)點,哪些結(jié)點是終端結(jié)點?答:圖略。開始結(jié)點kl、k2,終端結(jié)點k6、k7o.設(shè)有如圖1.1所示的邏輯結(jié)構(gòu)圖,給出它的邏輯結(jié)構(gòu),并說出它是什么類型的邏輯結(jié)構(gòu)。答:數(shù)據(jù)邏輯結(jié)構(gòu)為:D={kl,k2,k3,…，k8},R={<kl,k2>,<kl,k3>,<k3,k5>,<k3,k4>,<k4,k7>,<k4,k6>,<k5,k8>},其邏輯結(jié)構(gòu)類型為樹型結(jié)構(gòu)。.分析下列程序的時間復(fù)雜度(設(shè)n為正整數(shù))。(1)intrec(intn){if(n=l)return(1) ； elsereturn(n*rec(n-l))； }(2)x=91；y=100；While(y>0)if(x>10)y--；⑶i=1；j=0；while(i+j〈=n)if(i〉j)j++;elsei++;(4)x=n；yニ〇;while(x>=(y+1)*(y+1)) y++；答:⑴O(n)(2)0(1) (3)0(n) (4)0(n1/2).設(shè)n為正數(shù)。試確定下列各程序段中前面加記號@的語句的頻度:(l)i=l；kニ〇;while(i<=n-l) {@k+=10*i； i++； )k=0；for(i=l；i<=n；i++)for(j=i；j<=n：j++) @k++；答:(l)n-l(2)n+(n-l)+……+l=n(n+l)/2第二節(jié)線性表ー、選擇題.線性結(jié)構(gòu)中的ー個結(jié)點代表一個()〇*A.數(shù)據(jù)元素 B.數(shù)據(jù)項C.數(shù)據(jù)D.數(shù)據(jù)結(jié)構(gòu).線性表L=(al,a2,???,ai,??,an),下列說法正確的是()〇A,每個元素都有一個直接前驅(qū)和直接后繼 B.線性表中至少要有一個元素C,表中諸元素的排列順序必須是由小到大或由大到小的D.?除第一個元素和最后ー個元素外其余每個元素都有一個且僅有ー個直接前驅(qū)和直接后繼.順序表是線性表的（）〇A?鏈?zhǔn)酱鎯Y(jié)構(gòu)?B.順序存儲結(jié)構(gòu)C.索引存儲結(jié)構(gòu)D,散列存儲結(jié)構(gòu).對于順序表,以下說法錯誤的是（）〇*A.順序表是用ー維數(shù)組實現(xiàn)的線性表,數(shù)組的下標(biāo)可以看成是元素的絕對地址B.順序表的所有存儲結(jié)點按相應(yīng)數(shù)據(jù)元素間的邏輯關(guān)系決定的次序依次排列C.順序表的特點是:邏輯結(jié)構(gòu)中相鄰的結(jié)點在存儲結(jié)構(gòu)中仍相鄰D.順序表的特點是:邏輯上相鄰的元素,存儲在物理位置也相鄰的單元中.對順序表上的插入、刪除算法的時間復(fù)雜度分析來說,通常以（）為標(biāo)準(zhǔn)操作。A,條件判斷*B.結(jié)點移動C,算術(shù)表達式D.賦值語句.對于順序表的優(yōu)缺點,以下說法錯誤的是（）〇A.無需為表示結(jié)點間的邏輯關(guān)系而增加額外的存儲空間B.可以方便地隨機存取表中的任一結(jié)點*C.插入和刪除操作較方便D.由于順序表要求占用連續(xù)的空間,存儲分配只能預(yù)先進行（靜態(tài)分配）.在含有n個結(jié)點的順序存儲的線性表中,在任ー結(jié)點前插入ー個結(jié)點所需移動結(jié)點的平均次數(shù)為（）〇A.n*B.n/2C.(n-l)/2D.(n+l)/28,在含有n個結(jié)點的順序存儲的線性表中,刪除ー個結(jié)點所需移動結(jié)點的平均次數(shù)為()〇A.nB.n/2 *C.(n'l)/2D.(n+l)/29.帶頭結(jié)點的單鏈表為空的條件是()〇A.head=NULL*B. headー〉next二NULLC.headー〉next二headD.head!=NULL10.非空單循環(huán)鏈表head的尾結(jié)點?p滿足()〇A. p一〉next二NULL B.p=NULL*C.p-〉next二head D.p二head11.在雙循環(huán)鏈表的?P結(jié)點之后插入?s結(jié)點的操作是()〇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；pー〉next-〉pror=s；p-〉next二s；12,在ー個單鏈表中,已知?q結(jié)點是?p結(jié)點的前驅(qū)結(jié)點,若在?q和?p之間插入結(jié)點?s,則執(zhí)行()〇A. s-〉next=p-〉next ； pー〉next二s ；p-〉next=s-〉next；sー〉next二p；*C?q-〉next二s;sー〉next=p； D.p-〉next二s;sー〉next二q；13,在ー個單鏈表中,若?p結(jié)點不是最后結(jié)點。在*p之后插入結(jié)點?s,則執(zhí)行()〇A.s->next=p；p->next=s;*B.s->next=p->next；pー〉next二s；sー〉next=p-〉next； p=s；D.p->next二s；sー〉next二p;14.若某線性表中最常用的操作是取第i個元素和找第i個元素的前驅(qū)元素,則采用()存儲方式最節(jié)省時間。*A.順序表B.單鏈表C.雙鏈表D.單循環(huán)鏈表15.設(shè)rear是指向非空帶頭結(jié)點的單循環(huán)鏈表的尾指針,則刪除表頭結(jié)點的操作可表示為()〇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-〉next；free(p)；16.在ー個單鏈表中,若刪除?p結(jié)點的后繼結(jié)點,則執(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é)點,則雙鏈表結(jié)構(gòu)的對稱性可用()式來刻畫。A. p-〉prior-〉nextー〉ニニpー〉next-〉nextB ? pー〉prior-〉priorニニpー〉nextー〉prior*C ? pー〉priorー〉next-〉ニニpー〉next->priorD.p-〉next-〉nextニニp-〉prior-〉prior18,在循環(huán)鏈表中,將頭指針改設(shè)為尾指針rear后,其頭結(jié)點和尾結(jié)點的存儲位置分別是（）〇A.rearネロrear-〉nextー〉next*B.rear-〉next外口rearC.rearー〉nextー〉nextネロrearD.rearネロrear->next.循環(huán)鏈表的主要優(yōu)點是（）〇A.不再需要頭指針了B.已知某個結(jié)點的位置后,容易找到它的直接前驅(qū)C.在進行插入、刪除操作時,能更好地保證鏈表不斷開?D.從表中任一結(jié)點出發(fā)都能掃描到整個鏈表.在線性表的下列存儲結(jié)構(gòu)中,讀取元素花費時間最少的是（）〇A.單鏈表B.雙鏈表C.循環(huán)鏈表?D.順序表二、判斷題VI.順序存儲的線性表可以隨機存取。X2.順序存儲的線性表的插入和刪除操作不需要付出很大的代價,因為平均每次操作只有近一半的元素需要移動。V3.線性表中的元素可以是各種各樣的,但同一線性表中的數(shù)據(jù)元素具有相同的特性,因此是屬于同一數(shù)據(jù)對象。X4.在線性表的順序存儲結(jié)構(gòu)中,邏輯上相鄰的兩個元素在物理位置上不一定相鄰。V5.在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中,邏輯上相鄰的元素在物理位置上不一定相鄰。V6.在單鏈表中,可以從頭結(jié)點開始查找任何ー個元素。X7.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。V8,在線性表的順序存儲結(jié)構(gòu)中,插入和刪除元素時,移動元素的個數(shù)與該元素的位置有關(guān)。X9.在單鏈表中,要取得某個元素,只要知道該元素的指針即可,因此,單鏈表是隨機存取的存儲結(jié)構(gòu)。X10.順序存儲方式只能用于存儲線性結(jié)構(gòu)。三、填空題.為了便于討論,有時將含n(n>0)個結(jié)點的線性結(jié)構(gòu)表示成(al,a2,an),其中每個ai代表ー個ー結(jié)點ー。al稱為ー第一個ー結(jié)點,an稱為—最后ー個ー結(jié)點,i稱為ai在線性表中的一位置ー。對任意ー對相鄰結(jié)點ai、ai+1(l^i<n),ai稱為ai+1的直接一前驅(qū)_,ai+1稱為ai的直接ー后繼 。.線性結(jié)構(gòu)的基本特征是:若至少含有一個結(jié)點,則除起始結(jié)點沒有直接一前驅(qū)一外,其他結(jié)點有且僅有一個直接一前驅(qū)」除終端結(jié)點沒有直接ー后繼一外,其他結(jié)點有且僅有一個直接一后繼_。.所有結(jié)點按ー對ー的鄰接關(guān)系構(gòu)成的整體就是ー線性一結(jié)構(gòu)。.線性表的邏輯結(jié)構(gòu)是ー線性，吉構(gòu),其所含結(jié)點的個數(shù)稱為線性表的ー長度ー。.在單鏈表中,刪除p所指結(jié)點的直接后繼的操作是q=p-〉next；pー〉next=q->next；free(q)；?.非空的單循環(huán)鏈表head的尾結(jié)點(由指針p所指)滿足_pー〉next二head〇.rear是指向非空帶頭結(jié)點的單循環(huán)鏈表的尾指針,則刪除起始結(jié)點的操作可表示為ーーp二rear-〉next；q=p-〉next；p-〉next=q-〉next；free(q)；〇.對于ー個具有n個結(jié)點的單鏈表,在p所指結(jié)點后插入一個結(jié)點的時間復(fù)雜度為在給定值為x的結(jié)點后插入新結(jié)點的時間復(fù)雜度為_0(n)_o.單鏈表表示法的基本思想是用一指針ー一表示結(jié)點間的邏輯關(guān)系。.在順序表中插入或刪除ー個元素,平均需要移動一一半一元素,具體移動的元素個數(shù)與一元素的位置一有.在ー個長度為n的向量的第i(lくiWn+1)個元素之前插入ー個元素時,需向后移動n-i+1ー個元素。12,在一個長度為n的向量中刪除第i(lWiくn)個元素時,需向前移動ーn-iー個元素。.在雙鏈表中,每個結(jié)點有兩個指針域,ー個指向一前驅(qū)—,另ー個指向ー后繼ー一〇.在ー個帶頭結(jié)點的單循環(huán)鏈表中,p指向尾結(jié)點的直接前驅(qū),則指向頭結(jié)點的指針head可用p表示為head=_pー〉next-〉next；〇.設(shè)head指向單鏈表的表頭,p指向單鏈表的表尾結(jié)點,則執(zhí)行pー〉next二head后,該單鏈表構(gòu)成一單循環(huán)鏈表ー〇16,在單鏈表中,若p和s是兩個指針,且滿足p->next與s相同,則語句p-〉next二sー〉next的作用是ー刪除—s指向的結(jié)點。.設(shè)r指向單循環(huán)鏈表的最后ー個結(jié)點,要在最后ー個結(jié)點之后插入s所指的結(jié)點,需執(zhí)行的三條語句是s-〉next=r-〉next—；r-〉next=s；r=s；.在單鏈表中,指針p所指結(jié)點為最后一個結(jié)點的條件是—pー〉next二NULL〇.在雙循環(huán)鏈表中,若要在指p所指結(jié)點前插入s所指的結(jié)點,則需執(zhí)行下列語句:sー〉next二p；sー〉prior=p-〉prior；p-〉prior-〉next二s；pー〉prior二s；.在單鏈表中,若要在p所指結(jié)點之前插入s所指的結(jié)點,可進行下列操作:sー〉next=pー〉next； pー〉next二s；temp=p-〉data；pー〉data=一s->data； s-〉data=temp四、應(yīng)用題.描述以下三個概念的區(qū)別：頭指針,頭結(jié)點,首元結(jié)點（第一個元素結(jié)點）。答:首元結(jié)點是指鏈表中存儲的線性表中的第一個數(shù)據(jù)元素的結(jié)點。為了操作方便,通常在鏈表的首元結(jié)點之前附設(shè)ー個結(jié)點,稱為頭結(jié)點。頭指針是指向鏈表中的第一個結(jié)點的指針。.何時選用順序表,何時選用鏈表作為線性表的存儲結(jié)構(gòu)為宜?答:從空間上來看,當(dāng)線性表的長度變化較大、難以估計其規(guī)模時,選用動態(tài)的鏈表作為存儲結(jié)構(gòu)比較合適,但鏈表除了需要設(shè)置數(shù)據(jù)域外,還要額外設(shè)置指針域,因此當(dāng)線性表長度變化不大、易于事先確定規(guī)模時,為了節(jié)約存儲空間,宜采用順序存儲結(jié)構(gòu)。從時間上來看,若線性表的操作主要是查找,很少進行插入和刪除操作時,應(yīng)選用順序表。對于頻繁進行插入和刪除操作的線性表,宜采用鏈表作為存儲結(jié)構(gòu)。.在順序表中插入和刪除ー個結(jié)點需平均移動多少個結(jié)點?具體的移動次數(shù)取決于哪兩個因素?答：平均移動表中大約一半的結(jié)點,插入操作平均移動n/2個結(jié)點,刪除操作平均移動(nT)/2個結(jié)點。具體移動的次數(shù)取決于表長和插入、刪除的結(jié)點的位置。.為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好?答:單循環(huán)鏈表中無論設(shè)置尾指針還是頭指針都可以遍歷表中任一個結(jié)點,但設(shè)置尾指針時,若在表尾進行插入或刪除操作可在。(1)時間內(nèi)完成,同樣在表頭進行插入或刪除操作也可在0(1)時間內(nèi)完成。但若設(shè)置的是頭指針,表尾進行插入或刪除操作,需要遍歷整個鏈表,時間復(fù)雜度為o(n)。.雙鏈表和單循環(huán)鏈表中,若僅知道指針P指向某個結(jié)點,不知道頭指針,能否將結(jié)點?P從相應(yīng)的鏈表中刪除?若可以,其時間復(fù)雜度各為多少?答:能刪除。雙鏈表上刪除P所指向的結(jié)點的時間復(fù)雜度為0(1),單循環(huán)鏈表上刪除P所指向的結(jié)點的時間復(fù)雜度為0(n)。.下列算法的功能是什么?LinkList*testl(LinkList*L){//L是無頭結(jié)點的單鏈表LinkList*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；}returnL；}答:如果長度大于1,則將首元結(jié)點刪除并插入到表尾。7.如果有n個線性表同時共存,并且在處理過程中各表的長度會發(fā)生動態(tài)變化,線性表的總長度也會自動地改變。在此情況下,應(yīng)選擇哪ー種存儲結(jié)構(gòu)?為什么?答:應(yīng)選用鏈?zhǔn)酱鎯Y(jié)構(gòu)。因為順序表是靜態(tài)存儲結(jié)構(gòu),只能預(yù)先分配,不能隨著線性表長度的改變而變化。而鏈表則可根據(jù)需要動態(tài)地申請空間,因此適用于動態(tài)變化表長的線性表。8.若線性表的總數(shù)基本穩(wěn)定,且很少進行插入、刪除操作,但要求以最快的方式存取線性表的元素,應(yīng)該用哪種存儲結(jié)構(gòu)?為什么?答:應(yīng)選用順序存儲結(jié)構(gòu)。因為順序存儲結(jié)構(gòu)存取元素操作的時間復(fù)雜度為0(1)。五、算法設(shè)計題假設(shè)算法中用到的順序表和鏈表結(jié)構(gòu)如下:#definemaxsize100;Typedefstructnodel{datatypedata[maxsize];intlength)SeqList;Typedefstructnode2{datatypedata;structnode2*next}LinkedList;.試用順序表作為存儲結(jié)構(gòu),實現(xiàn)將線性表(a0,al,a2,…an-1)就地逆置的操作,所謂“就地”是指輔助空間為0(1)。答：(1)順序表的就地逆置分析:分別用兩個整型變量指向順序表的兩端,同時向中間移動,移動的同時互換兩個下標(biāo)指示的元素的值。voidSeqreverse(SeqList*L){/Z順序表的就地逆置for(i=0；j=L->length-l；i<j；i++,j--){t=Lー〉data[i]; Lー〉data[i]=L.data[j];Lー〉data]j]=t;} }(2)鏈表的就地逆置分析:本算法的思想是逐個地把L的當(dāng)前元素r插入到新的鏈表頭部。voidLinkedreverse(LinkedList*L){/Z鏈表的就地逆置p=L->next；L->next=NULL；while(p!=NULL){r=p,p=p->next；//r指向當(dāng)前待逆置的結(jié)點,P記下下ー個結(jié)點r-〉next二L一>next；L-〉next二r； //放到表頭}}.設(shè)順序表L是ー個遞增(允許有相同的值)有序表,試寫ー算法將x插入L中,并使L仍為ー個有序表。答:分析:先找到x的正確插入位置,然后將大于x的元素從后向前依次向下移動,最后將x插入到其位置上,同時順序表長度增1。voidSeqListinsert(SeqList*L,intx){//x插入到遞增有序的順序表L中i二〇;while((i〈=L-〉length-1)&&(x>=L->data[i]))i++; //找正確的插入位置for(k=L->length-l;k>=i；k—) //元素從后往前依次后移L->data[k+1]=L->data[k]；Lー〉data[i]=x； //x插入到正確位置L->length++；)3.設(shè)單鏈表L是ー個遞減有序表,試寫ー個算法將x插入其中后仍保持L的有序性。答:分析:此問題的關(guān)鍵是在鏈表中找到x的插入位置,因此需要兩個指針一前ー后地依次向后移動。voidLinkListinsert(LinkedList*L,intx){//x插入有序鏈表L中q=L；p=q->next；while(p!=NULL&&P—>data>x) //找到插入的位置{q=p；p=p—>next；}s二(LinkedList*)malloc(sizeof(LinkedList))；/Z生成新結(jié)點S->data=x；S一>next=p；qー〉next二s；)4.試寫出在不帶頭結(jié)點的單鏈表的第i個元素之前插入ー個元素的算法。答:分析:對不帶頭結(jié)點的鏈表操作時,要注意對第ー個結(jié)點和其他結(jié)點操作的不同。voidLinkedListlnsert(LinkedList*L,intx,inti){//不帶頭結(jié)點的單鏈表的第i個元素之前插入ー個元素P=L：j=1;while(p!=NULL&&j<i-l)/Z找到第iT個元素{p=P—>next；j++；}if(i<=0||p==NULL)printf(v插入位置不正確、n”)；else{q=(LinkedList*)malloc(sizeof(LinkedList))；q一>data=x；if(i=l){q一〉next=L；L=q；} //在第一個元素之前插入else{q一>next=p一>next；p->next=q；} //在其他位置插入})5.設(shè)A、B是兩個線性表,其表中元素遞增有序,長度分別為m和no試寫ー算法分別以順序存儲和鏈?zhǔn)酱鎯和B歸并成一個仍按元素值遞增有序的線性表Co答:(1)分析:用三個變量i、j、k分別指示A、B、C三個順序表的當(dāng)前位置,將A、B表中較小的元素寫入C中,直到有一個表先結(jié)束。最后將沒結(jié)束的表的剩余元素寫入C表中。SeqList*Seqmerge(SeqListA,SeqListB,SeqList*C){/Z有序順序表A和B歸并成有序順序表Ci=0；j=0；k=0； //i,i,k分別為順序表A,B,C的下標(biāo)while(i<m&&j<n){if(A.data[i]<B.data[j]) //A中當(dāng)前元素較小{C->data[k]=A.data[il；i++；]TOC\o"1-5"\h\zelse{C->data[k]=B.data[j];j++；} //B中當(dāng)前元素較小k++； }if(i==m)for(t=j；t<n； t++){C~>data[k]=B.data[t];k++；} //B表長度大于Aelsefor(t=i；t<m；t++){C-〉data[k]=A.data[t]；k++；} //A表長度大于B表Cー〉length=m+n； returnC;}(2)VOidLinkmerge(LinkedList*A,LinkedList*B,LinkedList*C){//有序鏈表A和B歸并成有序鏈表Cpa=A一>next；pb=B—>next;〇A；pc=C；while(pa&&pb)//A和B都不為空時{if(pa->data<pb一>data) //A當(dāng)前結(jié)點值較小{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é)點值較小}if(pa)pc一>next=pa； //A沒有結(jié)束,將A表剩余元素鏈接到C表if(pb)pc—>next=pb； //B沒有結(jié)束,將B表剩余元素鏈接到C表free(B)； //釋放B表的頭結(jié)點}本算法需要遍歷兩個線性表,因此時間復(fù)雜度為0(m+n)〇.設(shè)指針!a和1b分別指向兩個不帶頭結(jié)點的單鏈表的首結(jié)點,設(shè)計從表la中刪除第i個元素起共len個元素,并將這些元素插入到1b中第j個結(jié)點之前的算法。答:分析:先在la中找到第i個結(jié)點,分別用兩個指針pre和p指向第iT和第i個結(jié)點,然后用指針q從第i個結(jié)點起向后走len個元素,使q指向此位置。然后在1b中找到第j個結(jié)點,將p所指向的la表中的第i個及q所指向的最后ー個共len個結(jié)點插入到1b中。voidDeletelnsert(LinkedList*la,LinkedList*lb,inti,intj,intlen){//刪除不帶頭結(jié)點的單鏈表la中第i個元素起共len個元素,并將這峰元素插入到單鏈表1b中第j個結(jié)點之前if(i<0|Ij<0||len<0)exit(O)；p=1a；k=l；pre=NULL；while(p&&k<i) //在la表中查找第i個結(jié)點{pre=p； p=p-〉next;k++；)if(!p)exit(0)；q=P;k=l；//P指向la表中第i個結(jié)點while(q&&k<len){q=q—>next； k++；} //查找la表中第i+len-1個結(jié)點if(!q)exit(0)；if(preニニla)la=q——>next； //i=l的キ青況elsepre一〉next二q—>next； /Z完成刪除//將從la中刪除的結(jié)點插入到1b中if(j=l) {q->next=lb； lb=p；} //j=l時else{r=lb;k二1； //J>!時while(r&&k<j-1){r二r一>next； k++；}//查找Lb表中第i—1個元素if(!r)exit(0)；qー〉next二r一>next；rー〉next二p； //元成插入}).單鏈表L是ー個遞減有序表,試寫一高效算法,刪除表中值大于min且小于max的結(jié)點(若表中有這樣的結(jié)點),同時釋放被刪結(jié)點空間,這里min和max是兩個給定的參數(shù)。答:LinkedListdelete(LinkedList*L,intmin,intmax){/Z刪除遞減有序單鏈表L中值大于min且小于max的結(jié)點q二L；if(min>max){printf(nmin>max'n")；exit(0)；}elsep=L一>next； //q始終指向p的前驅(qū)while(p-〉data〉=max) /Z當(dāng)前元素大于或等于max,則p、q依次向后移動{q=p；p=p->next；}while((p!二NULL)&&(p->data>min)){//當(dāng)前元素的值比min大同時比max小,刪除P指向的結(jié)點q->next=p一>next,free(p)；p=q一>next； }returnL；}..編寫ー個算法將一個頭結(jié)點指針為pa的單鏈表A分解成兩個單鏈表A和B,其頭結(jié)點指針分別為pa和pb,使得A鏈表中含有原鏈表A中序號為奇數(shù)的元素,而B鏈表中含有原鏈表A中序號為偶數(shù)的元素,且保持原來的相對順序。答:分析:用兩個工作指針P和q分別指示序號為奇數(shù)和序號為偶數(shù)的結(jié)點,將q所指向的結(jié)點從A表刪除,并鏈接到B表。voiddecompose(LinkedList*A,LinkedList*B){//單鏈表A分解成元素序號為奇數(shù)的單鏈表A和元素序號為偶數(shù)的單鏈表Bp=A->next ；B二(LinkedList*)malloc(sizeof(LinkedList))；r=B；while(p!=NULL&&Pー〉next!=NULL){q二P—>next； //q指向偶數(shù)序號的結(jié)點P->next=q一>next； //將q從A表中刪除rー〉next二q； //將q結(jié)點鏈接到B鏈表的末尾r=q；//r總是指向B鏈表的最后一?個結(jié)點P二P—>next；//p指向原鏈表A中的奇數(shù)序號的結(jié)點)rー〉next二NULL； //將生成B鏈表中的最后一個結(jié)點的next域置為空).假設(shè)以兩個元素值遞增有序排列的線性表A、B分別表示兩個集合,要求另辟空間構(gòu)造一個線性表C,其元素為兩集合的交集,且表C中的元素值也遞增有序排列。用順序表實現(xiàn)并寫出C的算法。答:分析:用三個變量i、j、k分別指示A、B、C三個順序表的當(dāng)前位置,若A、B表中當(dāng)前元素值相同,則寫入C中,并使i、j、k值增!;若A表元素值較小,則使i增1;若B表元素值較小,則使j增1,直到有ー個表先結(jié)束。SeqLiSt*intersection(SeqListA,SeqListB,SeqList*C){/Z求元素依值遞增有序排列的順序表A、B的交集Ci=0； j=0；k=0；while((i<=A.length-1)&&(j<=B.length-1)){if(A.data[i]=B.data[j]) //找到值相同的元素{C->data[k]=A.data[i]； //相同元素寫入C表中k++；i++；j++； }elseif(A.data[i]<B.data[j])i++；//A、B表當(dāng)前元素不等,值較小的下標(biāo)增1elsej++； }C->length二k； returnC；}.假設(shè)在長度大于1的單循環(huán)鏈表中,既無頭結(jié)點也無頭指針。s為指向鏈表中某個結(jié)點的指針,試編寫算法刪除結(jié)點?s的直接前驅(qū)結(jié)點。答:分析:因為既不知道此單循環(huán)鏈表的頭指針,也不知道其尾指針,所以找S的前驅(qū)就只能從S開始,順次向后尋找。voidDeletePre(Linkedlist*s){/Z刪除單循環(huán)鏈表中結(jié)點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)； ).計算帶頭結(jié)點的循環(huán)鏈表的結(jié)點個數(shù)。答:intnumber(Linkedlist*head){//計算單循環(huán)鏈表中結(jié)點的個數(shù)p=head—>next； i二〇;while(p!=head){i++；p=p-〉next；}returni；}.已知由單鏈表表示的線性表中,含有三類字符的數(shù)據(jù)元素(如:字母字符、數(shù)字字符和其他字符),試編寫算法構(gòu)造三個以循環(huán)鏈表表示的線性表,使得每個表中只含有同一類的字符,且利用原表中的結(jié)點空間作為這三個表的結(jié)點空間,頭結(jié)點可另辟空間。答:分析:P指向待處理的單鏈表的首元結(jié)點,構(gòu)造三個空的單循環(huán)鏈表,分別存儲三類字符,其中一個表可使用原來的單鏈表。q指向P的下ー個結(jié)點,根據(jù)?P的數(shù)據(jù)域的值將其插入到不同的鏈表上。再把q的值給P,處理下ー個結(jié)點。voidchange(LinkedList*L,LinkedList*pa,LinkedList*pb,LinkedList*pc){//分解含有三類字符的單鏈表為三個以循環(huán)鏈表表示的線性表,使其分別含有三