數(shù)據(jù)結(jié)構(gòu)與算法 習(xí)題及解答 機(jī)械自考版

第一章緒論一、單項選擇題1．在數(shù)據(jù)結(jié)構(gòu)與算法中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為________。A．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) B．線性結(jié)構(gòu)和非線性結(jié)構(gòu)C．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) D．動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)答案：B。從邏輯角度看，基本的數(shù)據(jù)結(jié)構(gòu)包括4類，分別是集合、線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)。其中，樹結(jié)構(gòu)和圖結(jié)構(gòu)屬于非線性結(jié)構(gòu)。集合也可以使用線性結(jié)構(gòu)表示。2．?dāng)?shù)據(jù)元素可以細(xì)分為________。A．?dāng)?shù)據(jù)項 B．字符 C．二進(jìn)制位 D．?dāng)?shù)據(jù)記錄答案：A。根據(jù)定義，數(shù)據(jù)元素可以細(xì)分為數(shù)據(jù)項。字符和二進(jìn)制位都是表示數(shù)據(jù)的具體單位（選項B和C都是錯誤的）。數(shù)據(jù)元素有時稱為記錄（選項D錯誤）。3．如果說線性結(jié)構(gòu)中元素之間是一對一的關(guān)系，則樹結(jié)構(gòu)中元素之間的關(guān)系是________。A．一對一的 B．一對多的 C．多對多的 D．不確定的答案：B。線性結(jié)構(gòu)中，除首元素和尾元素外，每個元素有唯一的直接前驅(qū)和唯一的直接后繼，所以對于每個元素而言，它對應(yīng)唯一的直接后繼，形成一對一的關(guān)系。在樹結(jié)構(gòu)中，每個元素僅有唯一的直接前驅(qū)，但可以有多個直接后繼，所以是一對多的關(guān)系。當(dāng)然，樹中的根（最前面的元素）和葉結(jié)點（后面的元素）除外。圖結(jié)構(gòu)中是多對多的關(guān)系，每個元素可以有多個直接前驅(qū)，也可以有多個直接后繼。4．在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素之間均為一個對一個的關(guān)系，稱為________。A．線性結(jié)構(gòu) B．樹結(jié)構(gòu) C．圖結(jié)構(gòu) D．集合結(jié)構(gòu)答案：A?；靖拍?。具體說明請參見第一章第3題的答案。5．下列選項中，不屬于數(shù)據(jù)結(jié)構(gòu)常用存儲方式的是________。A．順序存儲方式 B．鏈?zhǔn)酱鎯Ψ绞?C．分布存儲方式 D．散列存儲方式答案：C。數(shù)據(jù)結(jié)構(gòu)與算法課程中沒有討論分布存儲方式，除了選項中給定的A、B和D以外，還討論了索引存儲方式。這是數(shù)據(jù)結(jié)構(gòu)中常用的4種存儲方式。6．算法分析要評估的兩個主要方面是________。A．正確性和簡明性 B．時間復(fù)雜度和空間復(fù)雜度C．可讀性和可維護(hù)性 D．?dāng)?shù)據(jù)復(fù)雜性和程序復(fù)雜性答案：B。算法的正確性是必須的，簡明性、可讀性、可維護(hù)性等都不是算法要評估的內(nèi)容（選項A和選項C均錯誤），它們都屬于算法應(yīng)具備的眾多特性中的內(nèi)容。數(shù)據(jù)復(fù)雜性是數(shù)據(jù)本身的狀態(tài)，也不是算法要評估的，程序復(fù)雜性說得不明確（選項D錯誤）。算法要評估的是時間復(fù)雜度和空間復(fù)雜度。7．下列選項中，定義抽象數(shù)據(jù)類型時不需要做的事情是________。A．給出類型的名字 B．定義類型上的操作C．實現(xiàn)類型上的操作 D．用某種語言描述抽象數(shù)據(jù)類型答案：C。定義抽象數(shù)據(jù)類型時，需要給類型命名（選項A），需要指明相關(guān)的操作有哪些（選項B），需要使用程序語言或是自然語言描述抽象數(shù)據(jù)類型（選項D）。在確定了存儲結(jié)構(gòu)之后才能具體實現(xiàn)操作過程，所以在定義抽象數(shù)據(jù)類型階段，不涉及這些操作的實現(xiàn)。A．O(n) B．O(n2) C．O(2n) D．O(logn)答案：C基本概念。一般而言，算法的效率用算法時間復(fù)雜度進(jìn)行衡量，算法效率從高到低依次是：常數(shù)階O(1)，對數(shù)階O(logn)，線性階O(n)，線性對數(shù)階O(nlogn)，多項式階O(n2)，指數(shù)階O(2n)。9．________。x=2;while(x<n/2) x=2*x;A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)答案：A。n是輸入規(guī)模。x從2開始，每次倍增，達(dá)到或超過n/2時倍增的次數(shù)與log2n的大小相當(dāng)。10．設(shè)n是描述問題規(guī)模的非負(fù)整數(shù)，下列程序片段的時間復(fù)雜度是________。x=1;while(n>=(x+1)*(x+1)) x=x+1;A．O(n1/2) B．O(log2n) C．O(n) D．O(nlog2n)答案：A。11．設(shè)計求斐波那契數(shù)列前n項的算法時，適宜使用的算法策略是________。A．分治法 B．遞推法 C．遞歸法 D．窮舉法答案：B。參見本章算法設(shè)計題2的解答。二、填空題1．在數(shù)據(jù)結(jié)構(gòu)與算法課程中，將所有能輸入計算機(jī)并被計算機(jī)程序處理的符號集合稱為__________。答案：數(shù)據(jù)。基本概念。2．構(gòu)成數(shù)據(jù)的基本單位是__________。答案：數(shù)據(jù)元素?；靖拍睢Ｔ跀?shù)據(jù)結(jié)構(gòu)課程中，數(shù)據(jù)元素是構(gòu)成數(shù)據(jù)的基本單位，同時，也是作為一個整體進(jìn)行研究。3．?dāng)?shù)據(jù)元素及其關(guān)系在計算機(jī)內(nèi)的存儲方式稱為數(shù)據(jù)的__________。答案：存儲結(jié)構(gòu)。數(shù)據(jù)的結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，物理結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示及存儲方式。數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲關(guān)系是無關(guān)的。4．?dāng)?shù)據(jù)結(jié)構(gòu)包括4類，分別是集合、線性結(jié)構(gòu)、樹結(jié)構(gòu)和__________。答案：圖結(jié)構(gòu)?；靖拍?。5．構(gòu)成索引表的基本內(nèi)容是__________。答案：索引項。索引表由索引項組成，索引項指示數(shù)據(jù)元素所在的物理位置。通過索引項，可以加快數(shù)據(jù)元素的查找速度。6．一個算法必須在執(zhí)行有窮步之后結(jié)束，這個特性是算法的__________。答案：有窮性?；靖拍?。算法必須滿足5個重要特性：有0或多個輸入值、有1或多個輸出值、有窮性、確定性和可行性。7．設(shè)A={1,3,-4,5,-6,4,6,-3,-2,6}，調(diào)用MaxSeq(A,n,C);后，C[1]的值是________。答案：9。函數(shù)MaxSeq是求數(shù)組A的最大子數(shù)組，結(jié)果是{4,6,-3,-2,6}，C[1]中保存的這個子數(shù)組最后一個元素在A中的下標(biāo)，得到9。三、解答題1．舉例說明計算機(jī)能處理哪些數(shù)據(jù)？【參考答案】計算機(jī)能處理的數(shù)據(jù)多種多樣，大到可以是一幅地圖、一本書、一部電影，小到可以是一個字符，甚至是計算機(jī)中的一位?？梢允菙?shù)值型的數(shù)據(jù)，也可以是非數(shù)值型的數(shù)據(jù)。既可以是簡單結(jié)構(gòu)的，也可以是復(fù)雜結(jié)構(gòu)的。2．線性結(jié)構(gòu)中，如何理解元素之間是一對一的關(guān)系？【參考答案】線性結(jié)構(gòu)中，除表頭元素和表尾元素外，每個元素有唯一的直接前驅(qū)和唯一的直接后繼。所以對于每個元素而言，當(dāng)有直接后繼時，它與其直接后繼形成一對一的關(guān)系。3．定義代表交通工具的抽象數(shù)據(jù)類型vehicle，添加必要的數(shù)據(jù)和操作?！緟⒖即鸢浮繉τ趘ehicle，可以定義表示其基本屬性的數(shù)據(jù)，包括品牌brand、顏色color、價格price等。相應(yīng)的操作可以是設(shè)置最大速度setSpeed(intspeed)、設(shè)置自重setdeadweight(intweight)等。ADTvehicle{ //交通工具的抽象數(shù)據(jù)類型定義 數(shù)據(jù)部分： brand： //品牌，字符串 color： //顏色，字符串 price： //價格，實型 speed： //最大速度，實型 deadweight： //自重，實型，單位噸 操作部分： setSpeed(speed)： //設(shè)置最大速度 輸入：speed 輸出：是否設(shè)置成功 前提條件：設(shè)置的speed值不能超出限制 setdeadweight(weight)： //設(shè)置自重 輸入：weight 輸出：是否設(shè)置成功 前提條件：設(shè)置的weight值不能超出限制}4．定義表示復(fù)數(shù)的抽象數(shù)據(jù)類型?！緟⒖即鸢浮繌?fù)數(shù)由實部和虛部表示，實部和虛部都是實型值。相應(yīng)的操作有算術(shù)操作。ADTcomplex{ //復(fù)數(shù)的抽象數(shù)據(jù)類型定義 數(shù)據(jù)部分： real： //實部，實型 imaginary： //虛部，實型 操作部分： add(complex1,complex2)： //加法 輸入：兩個復(fù)數(shù) 輸出：它們的和 前提條件：兩個復(fù)數(shù)正確 sub(complex1,complex2)： //減法 輸入：兩個復(fù)數(shù) 輸出：它們的差 前提條件：兩個復(fù)數(shù)正確 multiplication(complex1,complex2)： //乘法 輸入：兩個復(fù)數(shù) 輸出：它們的積 前提條件：兩個復(fù)數(shù)正確 division(complex1,complex2)： //除法 輸入：兩個復(fù)數(shù) 輸出：它們的商 前提條件：兩個復(fù)數(shù)正確}5．為什么不使用算法的絕對運(yùn)行時間來衡量算法的時間效率？【參考答案】同一個算法處理不同數(shù)量的數(shù)據(jù)時，所花費(fèi)的絕對運(yùn)行時間可能不同。同一個算法處理相同數(shù)量的數(shù)據(jù)時，在不同配置的電腦上的絕對運(yùn)行時間也可能不同。所以，使用算法的絕對運(yùn)行時間不能有效衡量算法的時間效率。6．評估算法的空間效率時，需要考慮占用的哪些存儲空間？【參考答案】算法運(yùn)行過程中，臨時占用的空間大小是要考慮的存儲空間。算法代碼占用的空間、算法中初始數(shù)據(jù)占用的存儲空間不考慮在內(nèi)。四、算法設(shè)計題1．試設(shè)計一個算法，使用最少的比較次數(shù)找出三個不同整數(shù)a,b,c的中值?！緟⒖即鸢浮縤ntmiddle(inta,intb,intc){ if(a>b){ if(b>c)returnb; //a>b>c elseif(a>c)returnc; //a>c>b elsereturna; //c>b>a } else{ if(a>c)returna; //b>a>c elseif(b>c)returnc; //b>c>a elsereturnb; //c>b>a }}2．試設(shè)計一個算法，對于給定的正整數(shù)n，列出斐波那契數(shù)列的前n項，要求空間復(fù)雜度為O(1)?！緟⒖即鸢浮快巢瞧鯏?shù)列的前兩項均為1，從第三項開始，每一項都是其前兩項之和。使用整型變量f1、f2和f3表示數(shù)列中相鄰三項的值，初始時，f1和f2的值均為1。然后計算新的項f3=f1+f2，計算后用f2的值更新f1，用f3的值更新f2。voidfibonacci(intn){ intf1=1,f2=1,f3,i; if(n<=0){ printf("n值錯誤\n"); return; } elseif(n==1){ printf("1\n"); return; } else{ printf("11"); for(i=3;i<=n;i++){ f3=f1+f2; printf("%d",f3); f1=f2; f2=f3; } printf("\n"); }}第二章線性表一、單項選擇題1．下列選項中，不屬于鏈表特點的是________。A．插入、刪除時不需要移動元素 B．可隨機(jī)訪問任一元素C．不必事先估計存儲空間 D．所需空間與元素個數(shù)成正比答案：B。鏈表中的元素可以不必保存在相鄰的地址空間中，所以當(dāng)鏈表中的元素個數(shù)有變化時，其他的元素不必像順序表那樣進(jìn)行移動（選項A）。而且鏈表占用的空間隨需分配，隨用隨分配，不必提前預(yù)估數(shù)量（選項C），表中有多少個元素就分配多少個表結(jié)點（選項D）。但要訪問鏈表中的元素時，只能從表頭開始，沿指針的指示逐個結(jié)點地查找下去，所以不能像在數(shù)組中那樣通過下標(biāo)定位到所需的地址，即不能實現(xiàn)隨機(jī)訪問。2．下列關(guān)于線性表的敘述中，錯誤的是________。A．線性表采用鏈?zhǔn)酱鎯Ψ绞剑阌谶M(jìn)行插入和刪除操作B．線性表采用順序存儲方式，便于進(jìn)行插入和刪除操作C．線性表采用鏈?zhǔn)酱鎯Ψ绞?，不必占用一片連續(xù)的存儲單元D．線性表采用順序存儲方式，必須占用一片連續(xù)的存儲單元答案：B。線性表既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。采用順序存儲結(jié)構(gòu)時，各元素要連續(xù)存放（選項D正確），當(dāng)有插入和刪除操作時，通常會導(dǎo)致其他元素的移動（選項B錯誤）。當(dāng)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，因為各結(jié)點的地址并不要求是相鄰的（選項C正確），所以插入和刪除操作不會引起其他元素的移動（選項A正確）。3．若一個線性表分別采用下列存儲結(jié)構(gòu)進(jìn)行存儲中，則讀取一個指定位置（序號）的元素所花費(fèi)時間最少的是________。A．順序表 B．單向鏈表 C．雙向鏈表 D．循環(huán)鏈表答案：A。采用順序存儲結(jié)構(gòu)保存線性表時，要讀取一個指定位置（序號）的元素可以直接通過下標(biāo)訪問，下標(biāo)與元素在內(nèi)存中存儲地址是一個簡單的計算公式，因為可以O(shè)(1)訪問線性表任一位置的元素，是花費(fèi)時間最少的（選項A正確）。對于采用鏈?zhǔn)酱鎯Y(jié)構(gòu)保存的線性表，無論是單向鏈表（選項B）、雙向鏈表（選項C），還是循環(huán)鏈表（選項D），要讀取指定位置（序號）的元素均需要從鏈表首結(jié)點開始進(jìn)行計數(shù)，這樣，操作的時間復(fù)雜度均為O(n)。4．下列關(guān)于線性表的敘述中，錯誤的是________。A．除第一個元素外均有唯一的前驅(qū)B．除最后一個元素外均有唯一的后繼C．元素的個數(shù)可以是0，此時表為空表D．元素的個數(shù)若為無窮，則表為無窮表答案：D。基本概念。在數(shù)據(jù)結(jié)構(gòu)中，線性表是一個有限元素的序列。5．下列關(guān)于線性表L的敘述中，正確的是________。A．L是由n個相同元素組成的離散數(shù)據(jù)序列B．L中任意一個元素有且僅有唯一直接前驅(qū)C．可以在L中進(jìn)行取元素、查找或排序等操作D．不能在L的任意位置插入或刪除一個元素答案：C。基本概念。線性表是由n個相同數(shù)據(jù)類型的數(shù)據(jù)元素組成的有限序列（A錯誤）；L中除第一個元素之外，其他元素有且僅有唯一的直接前驅(qū)，第一個元素沒有直接前驅(qū)（B錯誤）；在線性表中可以進(jìn)行插入、刪除、取元素值、查找或排序等操作，所以C是正確的，D是錯誤的。6．若線性表L最常用的操作是訪問任一位置的元素和在最后進(jìn)行插入和刪除運(yùn)算，為使操作的時間復(fù)雜度好，則下列選項中，為L選擇的存儲結(jié)構(gòu)為________。A．順序表 B．雙向鏈表C．帶頭結(jié)點的雙向循環(huán)鏈表 D．單循環(huán)鏈表答案：A。采用順序存儲結(jié)構(gòu)保存線性表時，能以O(shè)(1)訪問線性表任一位置的元素。要在線性表中間位置進(jìn)行插入和刪除時，會引發(fā)部分元素在數(shù)組中的移動，但如果僅在最后位置進(jìn)行插入和刪除，則避免了元素的移動，操作也能達(dá)到O(1)。選項B、C和D都是鏈?zhǔn)酱鎯Y(jié)構(gòu)，雖然它們進(jìn)行插入和刪除操作時能達(dá)到O(1)，但訪問任一位置元素時，平均情況下，僅能達(dá)到O(n)。綜合來看，選擇順序表更合適。7．線性表L中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，為使操作的時間復(fù)雜度好，則下列選項中，為L選擇的存儲結(jié)構(gòu)為________。A．單鏈表 B．僅有頭指針的單循環(huán)鏈表C．雙向鏈表 D．僅有尾指針的單循環(huán)鏈表答案：D。4個選項給出的都是鏈?zhǔn)酱鎯Y(jié)構(gòu)。根據(jù)題意，操作的位置是表尾和表頭，所以要選擇能快速訪問這兩個位置的結(jié)構(gòu)。單鏈表中僅有表頭指針，能快速訪問表頭，但不能快速訪問表尾。單循環(huán)鏈表中，通過頭指針能快速訪問表頭位置，訪問表尾也是不方便的。雙向鏈表也是類似的。選項D給出的鏈表，通過尾指針可以快速訪問到表尾結(jié)點，實現(xiàn)在其之后的插入，也能通過表尾結(jié)點的next指針快速找到表頭結(jié)點，實現(xiàn)刪除操作。所以，僅有尾指針的單循環(huán)鏈表是最合適的結(jié)構(gòu)。8．為了提供全程對號的高速鐵路售票系統(tǒng)，保證每一位旅客從上車到下車期間都有獨立座位，短途乘客下車后該座位可以銷售給其他乘客，鐵路公司設(shè)計了基于內(nèi)存的系統(tǒng)，系統(tǒng)中需要描述座位信息和每個座位的售票情況。保存座位信息和每個座位售票情況的數(shù)據(jù)結(jié)構(gòu)分別是________。A．?dāng)?shù)組，數(shù)組 B．?dāng)?shù)組，鏈表C．鏈表，數(shù)組 D．鏈表，鏈表答案：B。高鐵上，每節(jié)車廂都有自己固定的座位數(shù)，不變化，所以可以使用數(shù)組來描述座位。但每個座位的售票情況是隨時變化的，應(yīng)當(dāng)使用動態(tài)的結(jié)構(gòu)來描述，故選用鏈表來描述。9．若長度為n的線性表采用順序存儲結(jié)構(gòu)，則在其第i(0≤i≤n)個位置插入一個新元素的算法的時間復(fù)雜度為________。A．O(1) B．O(i) C．O(n) D．O(n2)答案：C。順序表中，插入操作會導(dǎo)致從插入位置至表尾的全部元素依次后移一個位置。平均情況下，要移動一半的元素，所以時間復(fù)雜度是O(n)。10．對于含n個元素采用順序存儲的線性表，訪問位置i（0≤i≤n-1）處的元素和在位置i（0≤i≤n）插入元素的時間復(fù)雜度分別為________。A．O(n)和O(n) B．O(n)和O(1) C．O(1)和O(n) D．O(1)和O(1)答案：C。順序表中，訪問結(jié)點時可以根據(jù)下標(biāo)直接計算地址，所以時間復(fù)雜度是O(1)。而插入結(jié)點的時間復(fù)雜度是O(n)。11．線性表(a0,a1,…,an-1)以鏈接方式存儲時，訪問位置i的元素的時間復(fù)雜度為________。A．O(1) B．O(i-1) C．O(i) D．O(n)答案：D。鏈?zhǔn)酱鎯€性表時，如果要訪問表中的結(jié)點，通常會從表頭開始，逐個結(jié)點依次遍歷過來，平均而言，要訪問表中一半的元素。12．在帶頭結(jié)點的非空單循環(huán)鏈表head中，指向尾結(jié)點的指針p滿足的條件是________。A．p==NULL B．p==headC．p->next==head D．p->next==NULL答案：C。若單循環(huán)鏈表head非空，則必有尾結(jié)點，尾結(jié)點的next指向頭結(jié)點，也就是說，p指向結(jié)點的next值應(yīng)該等于head的值（選項C正確）。若指針p的值是NULL（選項A），則表示指針p沒有指向任何結(jié)點。若p==head（選項B），則表示p與頭指針指向相同，而頭指針指向的是頭結(jié)點（虛擬結(jié)點），在非空鏈表中，尾結(jié)點不是頭結(jié)點。如果不是循環(huán)鏈表，則尾結(jié)點的next值為NULL（選項D）。13．帶頭結(jié)點的單鏈表head為空的判定條件是________。A．head==NULL B．head!=NULLC．head->next==head D．head->next==NULL答案：D。帶頭結(jié)點的空單鏈表是僅含有頭結(jié)點（虛擬結(jié)點）的鏈表，頭結(jié)點的next值為NULL，即它沒有后繼結(jié)點。因為含有頭結(jié)點，故頭指針head在任何時刻都不能為空（選項A錯誤）。對于空表與非空表，head!=NULL（選項B）都是成立的，所以用這個條件不能判定表是否為空。head->next==head表明頭結(jié)點的next指針又指向頭結(jié)點，這是空循環(huán)鏈表的狀態(tài)。head->next==NULL表示的是頭指針指向的結(jié)點沒有后繼結(jié)點，這正是空鏈表要滿足的條件。14．在雙向循環(huán)鏈表中，在指針p所指結(jié)點之后插入指針s所指結(jié)點的操作是________。A．p->next=s;s->prev=p;p->next->prev=s;s->next=p->next;B．p->next=s;p->next->prev=s;s->prev=p;s->next=p->next;C．s->prev=p;s->next=p->next;p->next=s;p->next->prev=s;D．s->prev=p;s->next=p->next;p->next->prev=s;p->next=s;答案：D。解答這樣的題目時，畫圖是個不錯的方法。比如，執(zhí)行了選項A中前兩個語句（p->next=s;s->prev=p;）后，得到的鏈表狀態(tài)如圖2-1所示。pp…AB…Xs圖2-1對應(yīng)于選項A的單鏈表其中，第3個語句“p->next->prev=s;”是將結(jié)點X的prev指針又指回自己，這顯然是錯誤的。其他的3個選項，可以畫出類似的鏈表狀態(tài)。15．在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點，若在q和p之間插入s結(jié)點，則執(zhí)行的操作是________。A．s->next=p->next;p->next=s; B．p->next=s->next;s->next=p;C．q->next=s;s->next=p; D．p->next=s;s->next=q;答案：C。以選項A為例，執(zhí)行了其中的兩條語句后，單鏈表的狀態(tài)如圖2-2所示。這表明，結(jié)點s插入在了結(jié)點p的后面，而不是插入在q和p之間。ppqs………BC…X圖2-2對應(yīng)于選項A的單鏈表16．在一個單鏈表中，若p所指結(jié)點不是終端結(jié)點，在p所指結(jié)點之后插入s所指結(jié)點，則執(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;答案：B。17．下列關(guān)于帶頭結(jié)點的單向循環(huán)鏈表L的敘述中，正確的是________。A．L中最后一個結(jié)點的指針域要指向頭結(jié)點B．循環(huán)鏈表的長度為L中數(shù)據(jù)元素個數(shù)加1C．因為L是環(huán)形的，所以無法計算鏈表長度D．L中最后一個結(jié)點的指針域指向首個數(shù)據(jù)結(jié)點答案：A。帶頭結(jié)點的單向循環(huán)鏈表的基本形態(tài)如圖2-3所示，不論是否有數(shù)據(jù)結(jié)點，最后一個結(jié)點的指針均是指向頭結(jié)點的（選項A正確，選項D錯誤）。鏈表的長度為所包含的數(shù)據(jù)元素的個數(shù)，與鏈表的長度為L中數(shù)據(jù)元素個數(shù)加1是否有頭結(jié)點無關(guān)（選項B錯誤），與鏈表中是否有環(huán)無關(guān)（選項C錯誤）。b)b)帶頭結(jié)點的非空單向循環(huán)鏈表LABCDa)帶頭結(jié)點的空單向循環(huán)鏈表L圖2-3帶頭結(jié)點的單向循環(huán)鏈表18．含6個元素的線性表保存在如下所示的數(shù)組中，它表示的是一個靜態(tài)________。表元素關(guān)鍵字表元素之間的聯(lián)系0631618522051310344501257816691007A．單鏈表 B．雙向鏈表C．單向循環(huán)鏈表 D．雙向循環(huán)鏈表答案：C。靜態(tài)鏈表是使用一維數(shù)組實現(xiàn)的鏈表。在本題中，使用“表元素之間的聯(lián)系”來反映各個結(jié)點之間的關(guān)系（鏈接），其作用類似鏈表中的next。數(shù)組中保存了7個值，線性表中的元素值是6個，表明數(shù)組下標(biāo)0處保存的特殊結(jié)點。根據(jù)給出的表元素之間的關(guān)系，可以畫出如圖2-4所示的鏈表。headhead20516185910078162501103463圖圖2-4帶頭結(jié)點的單向循環(huán)鏈表根據(jù)圖示，鏈表為帶有頭結(jié)點的單向循環(huán)鏈表，頭結(jié)點（虛擬結(jié)點）是下標(biāo)為0的元素。二、填空題1．線性表是一個有限序列，組成線性表的是n（n≥0）個__________。答案：同類型的數(shù)據(jù)元素。線性表的定義要求組成線性表的數(shù)據(jù)元素是同類型的。2．不帶頭結(jié)點的單鏈表L（head為頭指針）為空的判定條件是__________。答案：head==NULL。不帶頭結(jié)點的空單鏈表中一個結(jié)點都沒有，頭指針的值為NULL。3．帶頭結(jié)點的雙向循環(huán)鏈表L（head為頭指針）為空的條件是__________。答案：head->next==head或是head->prev==head帶頭結(jié)點的空雙向循環(huán)鏈表中僅有一個頭結(jié)點，且這個結(jié)點的next指針和prev指針都指向結(jié)點本身，即與head指向相同。4．在帶頭結(jié)點的單鏈表中，當(dāng)刪除某一指定結(jié)點時，必須要找到該結(jié)點的__________。答案：前驅(qū)。被刪除結(jié)點的后繼結(jié)點，變?yōu)楸粍h除結(jié)點原前驅(qū)結(jié)點的后繼，所以要找到前驅(qū)結(jié)點，并修改它的next值。5．在數(shù)組中保存的鏈表稱為__________。答案：靜態(tài)鏈表?；靖拍?。6．設(shè)一個非空的靜態(tài)鏈表保存在數(shù)組中，以-1表示表尾所在結(jié)點為表尾結(jié)點，則含-1的單元個數(shù)最多為__________。答案：2。7．若線性表中每個元素占size個單元，采用順序存儲方式，第一個數(shù)據(jù)元素的存儲位置是1000，則線性表第i個元素的存儲位置Loc(ai)=__________。答案：1000+(i-1)size。在順序存儲方式下，數(shù)組下標(biāo)與線性表元素的位置的對應(yīng)關(guān)系可以通過公式LOC(ai)=LOC(a0)+id（教材公式2-2）進(jìn)行計算。根據(jù)題目，第一個數(shù)據(jù)元素是線性表中的a0，即第1個數(shù)據(jù)元素保存在數(shù)組下標(biāo)為0的位置，公式中的d為size，則第i個元素保存在數(shù)組下標(biāo)為i-1的位置，元素i的存儲位置LOC(ai)=1000+(i-1)size。三、解答題1．在單鏈表中設(shè)置頭結(jié)點的作用是什么？【參考答案】在單鏈表中進(jìn)行插入和刪除操作時，都要找到操作位置結(jié)點的前驅(qū)結(jié)點。但根據(jù)線性表當(dāng)前指針的原始定義，前驅(qū)結(jié)點是不能通過當(dāng)前指針直接找到的。所以，修改當(dāng)前指針指向的結(jié)點，讓其前移一個位置，即指向操作位置的前驅(qū)結(jié)點。這樣修改后，通過當(dāng)前指針很容易訪問到插入和刪除操作所涉及的各個結(jié)點。但當(dāng)操作位置是第一個結(jié)點時，或是單鏈表是空表時，當(dāng)前指針的指向又成為特殊情況，需要單獨處理。為了能統(tǒng)一處理各種情況，給單鏈表添加一個虛擬結(jié)點，即頭結(jié)點，從而減少實現(xiàn)插入和刪除操作時對特殊情況的判定及處理情況。2．什么是單鏈表中的頭結(jié)點、第一個數(shù)據(jù)結(jié)點和頭指針？【參考答案】單鏈表中保存線性表中各數(shù)據(jù)的結(jié)點是數(shù)據(jù)結(jié)點，這些結(jié)點中的第一個是第一個數(shù)據(jù)結(jié)點。它的前面是一個虛擬結(jié)點，稱為頭結(jié)點。一個特殊的指向單鏈表中最前面結(jié)點的指針是頭指針。如果單鏈表中一個結(jié)點都沒有，則頭指針為空。3．假設(shè)線性表L=(51,40,19,15,24,36)，使用線性表ADT中定義的方法，列出刪除19時對應(yīng)的語句序列?！緟⒖即鸢浮縤f(isEmpty(&L)==FALSE){ intpos,x; pos=find(&L,19); if(pos>=0)removeList(&L,pos,&x);}4．已知線性表中一個元素占8個字節(jié)，一個指針占2個字節(jié)，數(shù)組的大小為20個元素。在順序及鏈?zhǔn)絻煞N存儲方式中，線性表應(yīng)該采用哪種方式保存？為什么？【參考答案】設(shè)線性表中元素個數(shù)為n。單純考慮空間復(fù)雜度。采用順序存儲時，占用的空間大小=208=160個字節(jié)。采用鏈?zhǔn)酱鎯r，不妨設(shè)采用單鏈表存儲，占用的空間大小=n(8+2)=10n個字節(jié)。列方程，10n=160，求得n=16。即若線性表中元素個數(shù)少于16個時，采用單鏈表保存更好，元素個數(shù)多于16個時，采用數(shù)組保存更好。等于16個時，兩種方式保存的效果是一樣的。5．在單鏈表和雙向鏈表中，能否從當(dāng)前結(jié)點出發(fā)訪問到表中的任何一個結(jié)點?【參考答案】在單鏈表和雙向鏈表中，如果是從頭結(jié)點或第一個數(shù)據(jù)結(jié)點出發(fā)，能訪問到表中的任一結(jié)點，但從其他結(jié)點出發(fā)，都只能訪問到該結(jié)點及其全部的后繼結(jié)點，它的前驅(qū)結(jié)點是訪問不到的。6．線性表(a0,a1,…,an-1)采用順序存儲方式時，ai和ai+1（0≤i<n-1）的物理位置相鄰嗎？采用鏈?zhǔn)椒绞綍r呢？【參考答案】采用順序存儲方式時，ai和ai+1（0≤i<n-1）的物理位置是相鄰的。采用鏈?zhǔn)酱鎯r，ai和ai+1（0≤i<n-1）的物理位置不一定是相鄰的?？赡芟噜徱部赡懿幌噜?。7．試分析雙向鏈表中插入、刪除、查找等基本操作的時間復(fù)雜度?！緟⒖即鸢浮吭陔p向鏈表中進(jìn)行插入和刪除操作時，如果給定了當(dāng)前指針，則插入操作和刪除操作的時間復(fù)雜度均為O(1)，因為操作過程中不需要進(jìn)行元素的移動，也不需要將當(dāng)前指針從表頭后移到當(dāng)前位置。查找操作的時間復(fù)雜度是根據(jù)查找目標(biāo)在鏈表中的位置而定的。若在雙向鏈表中一定能找到查找目標(biāo)，則最優(yōu)情況下，比較1次就能找到，時間復(fù)雜度為O(1)。最壞的情況下，需要進(jìn)行n次比較，時間復(fù)雜度為O(n)。平均來看，需要查找約一半的鏈表，所以時間復(fù)雜度是O(n)。8．靜態(tài)鏈表中，如何同時保存單鏈表及空閑空間鏈表？【參考答案】：靜態(tài)鏈表采用的一片連續(xù)區(qū)域（數(shù)組）作為鏈表的存儲空間。為有效使用存儲空間，提高空間的使用效率，對于數(shù)組中所有未曾使用過的單元必定是保持一片連續(xù)單元，這樣可以使用整型變量unused記錄這片連續(xù)單元的首位置，凡是下標(biāo)大于等于unused且不越界的單元，均為空閑單元。對于數(shù)組中曾經(jīng)使用過且目前空閑的所有單元，建立一個靜態(tài)的空閑單元鏈表將其鏈接起來，用整型變量available記錄這個鏈表首結(jié)點的下標(biāo)。9．靜態(tài)鏈表中，unused的作用是什么？【參考答案】：靜態(tài)鏈表采用的一片連續(xù)區(qū)域（數(shù)組）作為鏈表的存儲空間。為有效使用存儲空間，提高空間的使用效率，對于數(shù)組中所有未曾使用過的單元必定是保持一片連續(xù)單元，這樣可以使用整型變量unused記錄這片連續(xù)單元的首位置，凡是下標(biāo)大于等于unused且不越界的單元，均為空閑單元。四、算法閱讀題1．在如主教材圖2-13b所示的帶頭結(jié)點的非空循環(huán)鏈表中保存了若干整數(shù)。算法average求出這些整數(shù)的平均值。請在空白處填上適當(dāng)內(nèi)容將算法補(bǔ)充完整。floataverage(LinkListhead){ LinkNode*p; intcounter=0,sum=0; if(head==NULL){ printf("鏈表錯誤\n"); returnFALSE; } if(（1）)printf("這是一個空鏈表\n"); else{ p=head->next; while(（2）){ counter++; sum+=p->data; p=p->next; } } return（3）;}【參考答案】（1）head->next==head（2）p!=head（3）sum*1.0/counter對于（1），根據(jù)后面輸出的內(nèi)容可知，這里需要補(bǔ)上判定空表的條件。帶頭結(jié)點的空循環(huán)鏈表只含有一個頭結(jié)點，且該結(jié)點的next域指向結(jié)點本身。對于（2），根據(jù)題意，循環(huán)體中要對表中的全部結(jié)點進(jìn)行處理。進(jìn)入循環(huán)之前，指針p指向了第一個數(shù)據(jù)結(jié)點。while循環(huán)的結(jié)束條件是什么呢？當(dāng)指針p轉(zhuǎn)回到表頭時，表明已經(jīng)處理完全部的數(shù)據(jù)結(jié)點，此時循環(huán)可以結(jié)束。也就是在p沒有指向頭結(jié)點時，循環(huán)不結(jié)束。當(dāng)p==head時表明p指向頭結(jié)點，當(dāng)p!=head時表明p沒有指向頭結(jié)點。對于（3），返回的是表中元素的平均值。while循環(huán)體中已經(jīng)計算了全部元素的和及元素個數(shù)，兩個值做除法就可以了。注意不要進(jìn)行整除，兩個整數(shù)相除，結(jié)果可能除不盡，是個實型值。2．單鏈表的結(jié)點及鏈表定義如下：typedefstructnode{ intdata; //數(shù)據(jù)域 structnode*next; //指針域}LinkNode;typedefLinkNode*LinkList; //單鏈表算法largest找出這些整數(shù)中的最大值。請在空白處填上適當(dāng)內(nèi)容將算法補(bǔ)充完整。intlargest(LinkListhead){ LinkNode*p; intmaxitem; if(head==NULL){ printf("鏈表錯誤\n"); returnFALSE; } if(（1）)printf("這是一個空鏈表\n"); else{ p=head->next; maxitem=p->data; p=p->next; while(p!=NULL){ if(（2）)（3）; p=p->next; } } returnmaxitem;}【參考答案】（1）head->next==NULL（2）p->data>maxitem（3）maxitem=p->data對于（1），空單鏈表中僅含有一個頭結(jié)點，頭指針指向結(jié)點的next域為NULL。根據(jù)題意，要記錄表中元素的最大值，這由if語句來完成。顯然，if的條件是篩選最大值，后面的語句是將最大值保存下來。return語句中返回的是maxitem的值，意味著這個變量是用來保存最大值的，所以（3）的內(nèi)容很容易寫下來，就是將當(dāng)前結(jié)點中的值賦給maxitem。那么，當(dāng)前結(jié)點需要滿足什么條件呢？是要大于原來保存的maxitem值，這是（2）要填寫的內(nèi)容。3．閱讀程序，并回答下列問題。intcounterofodd(LinkListhead){ LinkNode*p; intcounter=0; if(head==NULL){ printf("鏈表錯誤\n"); returnFALSE; } if(head->next==NULL)printf("這是一個空鏈表\n"); else{ p=head->next; while(p!=NULL){ if(p->data%2!=0)counter++; p=p->next; } } returncounter;}（1）若單鏈表head中保存的是(1,3,5,7,10)，則執(zhí)行counterofodd(head)后，返回的結(jié)果是什么？（2）counterofodd()的功能是什么？【參考答案】（1）返回的結(jié)果是4。（2）counterofodd()的功能是統(tǒng)計單鏈表head中保存的奇數(shù)的個數(shù)。五、算法設(shè)計題1．教材中表2-1給出一個線性表操作示例，請采用順序存儲方式保存線性表，編程使用基本操作驗證表中的結(jié)論?！緟⒖即鸢浮框炞C程序的main函數(shù)實現(xiàn)如下。//采用順序表存儲，驗證基本操作#include<stdio.h>#include"SeqList.h"intmain(intargc,char**argv){ LinearListlisttest; inti,temp; printf("采用順序表保存線性表\n"); if(initList(&listtest)==FALSE){ printf("初始化失敗\n"); return0; }elseprintf("完成初始化\n"); for(i=0;i<6;i++) if(!insertList(&listtest,i,2*i)) printf("插入錯誤\n"); display(&listtest); if(!removeList(&listtest,3,&temp))printf("刪除錯誤\n"); else{ printf("刪除的3號元素是：%d\n",temp); printf("刪除后，"); display(&listtest); } if(!setValue(&listtest,3,-10)) printf("修改值出錯\n"); else{ printf("修改3號元素的值，"); display(&listtest); } if(!getValue(&listtest,3,&temp))printf("獲取值出錯\n"); elseprintf("獲取3號元素的值：%d\n",temp); printf("查找10的結(jié)果:%d\n",find(&listtest,10)); printf("查找9的結(jié)果:%d\n",find(&listtest,9)); return0;}2．教材中表2-1給出一個線性表操作示例，請采用鏈?zhǔn)酱鎯Ψ绞奖４婢€性表，編程使用基本操作驗證表中的結(jié)論?！緟⒖即鸢浮框炞C程序的main函數(shù)實現(xiàn)如下。//采用帶頭結(jié)點的單鏈表驗證基本操作#include<stdio.h>#ifndefLinearList#defineLinearList#include"LinkedList.h"#endif//typedefLinkListLinearList;intmain(intargc,char**argv){ LinkListhead,pre; inti,temp; Positionpos; printf("采用單鏈表保存線性表\n"); if(initList(&head)==FALSE){ printf("初始化失敗\n"); return0; }elseprintf("完成初始化\n"); for(i=0;i<6;i++) if(!insertList(&head,i,2*i)) printf("插入錯誤\n"); display(&head); if(!removeList(&head,3,&temp))printf("刪除錯誤\n"); else{ printf("刪除的3號元素是：%d\n",temp); printf("刪除后，"); display(&head); } if(!setValue(&head,3,-10)) printf("修改值出錯\n"); else{ printf("修改3號元素后："); display(&head); } if(!getValue(&head,3,&temp))printf("獲取值出錯\n"); elseprintf("獲取3號元素的值：%d\n",temp); printf("查找10的結(jié)果:%d\n",find(&head,10)); printf("查找9的結(jié)果:%d\n",find(&head,9)); return0;}3．教材中表2-1給出一個線性表操作示例，請采用靜態(tài)鏈?zhǔn)酱鎯Ψ绞奖４婢€性表，編程使用基本操作驗證表中的結(jié)論?！緟⒖即鸢浮框炞C程序的main函數(shù)實現(xiàn)如下。#include<stdio.h>#include"ArrayList.h"intmain(intargc,char**argv){ ArrayListlisttest; inttemp,i; initList(&listtest); displayList(listtest); for(i=0;i<6;i++) if(!insertArrayList(&listtest,i,2*i)) printf("插入錯誤\n"); displayList(listtest); displayArray(listtest); if(!removeArrayList(&listtest,3,&temp)) printf("刪除錯誤\n"); else{ printf("刪除的元素是：%d\n",temp); printf("刪除后，"); displayList(listtest); } if(!setValue(&listtest,3,-10))printf("修改值出錯\n"); else{ printf("修改3號元素的值，"); displayList(listtest); } if(!getValue(&listtest,3,&temp))printf("獲取值出錯\n"); elseprintf("獲取3號元素的值：%d\n",temp); printf("查找10的結(jié)果:%d\n",find(&listtest,10)); printf("查找9的結(jié)果:%d\n",find(&listtest,9)); displayList(listtest); displayArray(listtest); return0;}4．教材中表2-1給出一個線性表操作示例，請采用帶頭結(jié)點的雙向鏈表存儲方式保存線性表，編程使用基本操作驗證表中的結(jié)論?！緟⒖即鸢浮縤ntmain(intargc,char**argv){ ArrayListlisttest; inttemp,i,a[]={618,205,103,501,781,910}; Positionpos; initList(&listtest); printf("初始化靜態(tài)數(shù)組后的狀態(tài)：\n"); displayArray(listtest); for(i=0;i<6;i++) if(!insertSortArrayList(&listtest,a[i])) printf("插入錯誤\n"); displayList(listtest); displayArray(listtest); if((pos=find(&listtest,501))!=ERROR) { if(!removeArrayList(&listtest,pos,&temp)) printf("刪除錯誤\n"); else{ printf("刪除的元素是：%d\n",temp); printf("刪除501后，"); displayList(listtest); } } if((pos=find(&listtest,103))!=ERROR) { if(!removeArrayList(&listtest,pos,&temp)) printf("刪除錯誤\n"); else{ printf("刪除的元素是：%d\n",temp); printf("刪除103后，"); displayList(listtest); } } printf("靜態(tài)數(shù)組狀態(tài)：\n"); displayArray(listtest); if(!insertSortArrayList(&listtest,301)) printf("插入錯誤\n"); printf("插入301之后："); displayList(listtest); printf("靜態(tài)數(shù)組狀態(tài)：\n"); displayArray(listtest); return0;}5．設(shè)有一個正整數(shù)序列組成的有序單鏈表（按遞增次序有序，且允許有相等的整數(shù)存在），試編寫能實現(xiàn)下列功能的算法：（1）確定在序列中比正整數(shù)x大的數(shù)有幾個（相同的數(shù)只計算一次，如有序序列{10,20,30,30,40,41,50,50,51}中比30大的數(shù)有4個）；（2）將單鏈表中比正整數(shù)x小的數(shù)按遞減次序重排，仍放置在單鏈表中；如保存有序序列{10,20,30,30,40,41,50,50,51}的單鏈表中，將比40小的數(shù)重排后，得到的單鏈表中保存的序列是{30,30,20,10,40,41,50,50,51}。（3）將比x大的偶數(shù)從單鏈表中刪除?！緟⒖即鸢浮浚?）程序?qū)崿F(xiàn)如下所示。intlargerthanx(LinkListhead,intx){ intcounter=0,lastone; LinkNode*p; if(head==NULL){ printf("鏈表錯誤\n"); returnFALSE; } if(head->next==NULL)printf("這是一個空鏈表\n"); else{ p=head->next; lastone=p->data-1; while(p!=NULL){ if(p->data>x){ if(p->data>lastone){ counter++; lastone=p->data; } } p=p->next; } } returncounter;}因為單鏈表有序，所以，如果有相同的整數(shù)，則它們一定是相鄰的。使用變量lastone記錄前一個整數(shù)，如果當(dāng)前整數(shù)與lastone相等，則不計數(shù)。lastone的初值設(shè)為比第一個整數(shù)小的任何數(shù)即可。（2）程序?qū)崿F(xiàn)如下所示。intreversesmallthanx(LinkListhead,intx){ LinkNode*left,*middle,*right,*temp; if(head==NULL){ printf("鏈表錯誤\n"); returnFALSE; } if(head->next==NULL){ printf("這是一個空鏈表\n"); returnTRUE; } else{ temp=left=head->next; if(left!=NULL)middle=left->next; while(middle!=NULL&&middle->data<x){ right=middle->next; middle->next=left; left=middle; middle=right; } if(middle==NULL){ temp->next=NULL; head->next=left; } else{ temp->next=middle; head->next=left; } } returnTRUE;}將單鏈表中比正整數(shù)x小的數(shù)按遞減次序重排，實際上是將單鏈表前面的若干結(jié)點逆置。與教材第二章第五節(jié)中給出的reverse有些類似，但情況更復(fù)雜一些。當(dāng)找不到比x小的元素時，單鏈表維持不變。當(dāng)所有元素均小于x時，整個鏈表逆置。當(dāng)部分元素小于x時，只逆置前面的這些元素，逆置后的子表還要與原來的后半部分子表拼起來。（3）程序?qū)崿F(xiàn)如下所示。intremoveevenlargethanx(LinkListhead,intx){ LinkNode*current; intk,pos=0; if(head==NULL){ printf("鏈表錯誤\n"); returnFALSE; } if(head->next==NULL){ printf("這是一個空鏈表\n"); returnTRUE; } else{ current=head; while(current->next!=NULL){ if(current->next->data>x&¤t->next->data%2==0){ removeList(&head,pos,&k); } else{ current=current->next; pos++; } } } returnTRUE;}刪除滿足條件的元素時，可以調(diào)用單鏈表中實現(xiàn)的remove操作。要注意的是，刪除一個結(jié)點后，當(dāng)前指針current不改變，此時，current不后移，繼續(xù)判斷它指向結(jié)點的后繼結(jié)點。但如果沒有刪除結(jié)點，則current需要后移一個位置。6．在單鏈表L中保存了若干整數(shù)。實現(xiàn)算法將L分為兩個單鏈表L1和L2，其中L1中保存奇數(shù)，L2中保存偶數(shù)?！緟⒖即鸢浮砍绦?qū)崿F(xiàn)如下所示。intpartition(LinkList*L,LinkList*L1,LinkList*L2){ LinkNode*L1curr,*L2curr; LinkNode*temp; if((*L)==NULL){ printf("鏈表錯誤\n"); return0; } initList(L1); initList(L2); if((*L)->next==NULL){ printf("這是一個空鏈表\n"); returnTRUE; } else{ temp=(*L)->next; L1curr=*L1; L2curr=*L2; while(temp!=NULL){ (*L)->next=temp->next; temp->next=NULL; if(temp->data%2==0){ L2curr->next=temp; L2curr=L2curr->next; (*L2)->data++; } else{ L1curr->next=temp; L1curr=L1curr->next; (*L1)->data++; } temp=(*L)->next; } } returnTRUE;}將單鏈表L拆分為兩個單鏈表L1和L2，實際上就是從L中刪除一個結(jié)點，然后根據(jù)結(jié)點中值的奇偶性，或是將結(jié)點添加到L1中，或是將結(jié)點添加到L2中。因為刪除和插入都是依次進(jìn)行的，所以，設(shè)置一個當(dāng)前工作指針記錄三個鏈表的當(dāng)前位置。7．已知帶頭結(jié)點的單鏈表的每個結(jié)點中保存一個整數(shù)，數(shù)據(jù)結(jié)點有n個。請設(shè)計算法以判斷該鏈表中保存的值是否構(gòu)成斐波那契數(shù)列中的前n項。若是算法返回1，否則返回0?！緟⒖即鸢浮砍绦?qū)崿F(xiàn)如下所示。intisFibonacci(LinkListhead){ LinkNode*p1,*p2,*p3; intf1=1,f2=1,f3,i; if(head==NULL){ printf("鏈表錯誤\n"); returnFALSE; } if(head->next==NULL){ printf("這是一個空鏈表\n"); returnFALSE; } if(head->data==1&&head->next->data==1)returnTRUE; if(head->data==2&&head->next->data==1&&head->next->next->data==1) returnTRUE; p1=head->next; if(p1->data!=1)returnFALSE; p2=p1->next; if(p2->data!=1)returnFALSE; p3=p2->next; while(p3!=NULL&&p3->data==p1->data+p2->data){ p1=p2; p2=p3; p3=p3->next; } if(p3==NULL)return1; elsereturnFALSE;}斐波那契數(shù)列中含有多個整數(shù)值，如果整數(shù)的個數(shù)少于3個，則為特殊情況，程序中需要對此進(jìn)行特殊的處理。即單鏈表中數(shù)據(jù)結(jié)點的個數(shù)少于3個時，需要單獨進(jìn)行判定。前兩個結(jié)點中的整數(shù)都是1。當(dāng)結(jié)點個數(shù)大于等于3個時，從第三個結(jié)點開始，一直到尾結(jié)點，判定每個結(jié)點中保存的整數(shù)是否是相鄰的前兩個結(jié)點中值的和。8．實現(xiàn)算法，判斷帶頭結(jié)點的單鏈表中所保存的整數(shù)，是否構(gòu)成遞增有序序列。若是遞增有序序列，則算法返回1；若不是有序序列，則算法返回0?！緟⒖即鸢浮砍绦?qū)崿F(xiàn)如下所示。intisincrease(LinkListhead){ LinkNode*p; intcurrmax; if(head==NULL){ printf("鏈表錯誤\n"); returnFALSE; } if(head->next==NULL){ printf("這是一個空鏈表\n"); returnTRUE; } p=head->next; //第一個數(shù)據(jù)結(jié)點 currmax=p->data; p=p->next; while(p!=NULL&&p->data>=currmax){ currmax=p->data; p=p->next; } if(p==NULL)returnTRUE; elsereturnFALSE; }9．設(shè)線性表元素為整數(shù)，其中可能有相同的元素。試設(shè)計一個算法刪除表中重復(fù)的元素（即相同元素只保留一個），使刪除后表中各元素均不相同。給出在順序存儲和鏈?zhǔn)酱鎯煞N方式下的實現(xiàn)程序。【參考答案】線性表如果有序，則很容易刪除表中的重復(fù)元素。但當(dāng)線性表無序時，需要進(jìn)行更多的比較才能實現(xiàn)。采用順序存儲方式的程序?qū)崿F(xiàn)如下所示。intunique(SeqList*L){ inti,j,k,len; intNA=-65535; //NA用來做標(biāo)記 len=L->n; for(i=1;i<len;i++) for(j=0;j<i;j++){ if(L->element[i]==L->element[j])L->element[i]=NA; } k=1; for(i=1;i<len;i++){ if(L->element[i]!=NA){ L->element[k++]=L->element[i]; } } L->n=k; returnTRUE;}從數(shù)組中刪除一個重復(fù)元素時，后面的元素都要依次向前移動。為避免過多的元素移動，當(dāng)發(fā)現(xiàn)重復(fù)元素時，僅對重復(fù)元素進(jìn)行標(biāo)記，而不是立即進(jìn)行刪除。當(dāng)查找到所有重復(fù)元素后，再將剩余元素依次保存到數(shù)組最前面的若干位置中。使用NA標(biāo)記要刪除的元素。采用鏈?zhǔn)酱鎯Ψ绞降某绦驅(qū)崿F(xiàn)如下所示。voidunique(LinkListhead){ LinkNode*p,*current; intk,pos=0,currpos=0; if(head==NULL){ printf("鏈表錯誤\n"); return; } if(head->next==NULL){ printf("這是一個空鏈表\n"); return; } if(head->data==1)return; current=head; pos=1; currpos=0; while(current!=NULL&¤t->next!=NULL){ p=current; pos=currpos; while(p->next!=NULL){ if(p->next->data==current->data){ removeList(&head,pos,&k); } else{ p=p->next; pos++; } } current=current->next; currpos++; } return; }current是當(dāng)前指針，指示當(dāng)前結(jié)點。使用另一個指針p從當(dāng)前位置開始向后依次掃描結(jié)點。當(dāng)p指向結(jié)點的后繼結(jié)點中的值與current所指結(jié)點中的值相等時，刪除重復(fù)結(jié)點，即刪除p所指結(jié)點的后繼結(jié)點?？梢哉{(diào)用removeList函數(shù)完成刪除操作。因為刪除函數(shù)的第二個參數(shù)是位置，所以使用currpos記錄current指向的結(jié)點的位置值，使用pos記錄p指向結(jié)點的位置值。當(dāng)p指向表尾時，表示一輪掃描完成，current指向下一個結(jié)點，繼續(xù)同樣的查重及刪除操作。10．設(shè)有兩個按元素值遞增有序排列的單鏈表A和B。試實現(xiàn)算法，將它們合并成一個單鏈表C，要求C的元素值仍按遞增有序排列（允許C中有值相同的元素）?！緟⒖即鸢浮砍绦?qū)崿F(xiàn)如下所示。voidmergelist(LinkList*A,LinkList*B,LinkList*C){ LinkNode*pA=*A,*pB=*B,*pC=*C,*temp; while(pA->next!=NULL&&pB->next!=NULL){ if(pA->next->data<pB->next->data){ temp=pA->next; pA->next=temp->next; temp->next=NULL; pC->next=temp; (*A)->data--; } else{ temp=pB->next; pB->next=temp->next; temp->next=NULL; pC->next=temp; (*B)->data--; } pC=pC->next; (*C)->data++; } if(pA->next==NULL){ pC->next=pB->next; pB->next=NULL; (*C)->data+=(*B)->data; } else{ pC->next=pA->next; pA->next=NULL; (*C)->data+=(*A)->data; } return;}因為兩個單鏈表A和B是遞增有序的，合并后的鏈表也要求是遞增有序的，所以可以分別從前向后掃描A和B。使用三個工作指針分別指向A、B和C的當(dāng)前位置。比較A和B當(dāng)前結(jié)點中元素的值，將更小值的結(jié)點移至鏈表C中。這個思想是二路歸并排序中兩個有序歸并段合并的思想?？梢詤⒖嫉?章第五節(jié)的相關(guān)內(nèi)容。11．已知帶頭結(jié)點的單鏈表的結(jié)點定義如下：typedefintELEMType;typedefstructnode{ //單鏈表結(jié)點 ELEMTypedata; //數(shù)據(jù)域 structnode*next; //指針域}LinkNode;typedefLinkNode*LinkList; //單鏈表請編寫函數(shù)intappendList(LinkListhead,ELEMTypex)，將x插入到head指向的單鏈表的表尾?！緟⒖即鸢浮縤ntappendList(LinkList*head,ELEMTypex){ LinkNode*p,*temp; p=(LinkList)malloc(sizeof(LinkNode)); p->data=x; p->next=NULL; temp=*head; while(temp->next!=NULL){ temp=temp->next; } temp->next=p; returnTRUE;}12．已知鏈表結(jié)點及帶頭結(jié)點的單鏈表定義如下：typedefintELEMType;typedefstructnode{ //單鏈表結(jié)點 ELEMTypedata; //數(shù)據(jù)域 structnode*next; //指針域}LinkNode;typedefLinkNode*LinkList; //單鏈表請編寫函數(shù)intdeleteNode(LinkListhead,ElemTypex)，將在head指向的單鏈表中刪除data等于x的結(jié)點，如果刪除成功，函數(shù)返回值為1，刪除失敗，返回值為0。【參考答案】intdeleteNode(LinkList*head,ELEMTypex){ LinkNode*p=*head,*temp; while(p!=NULL&&p->next!=NULL&&p->next->data!=x) { p=p->next; } if(p!=NULL&&p->next!=NULL&&p->next->data==x) { temp=p->next; p->next=p->next->next; free(temp); returnTRUE; } elsereturnFALSE; }13．判定給定的單鏈表中是否存在環(huán)？如果存在，函數(shù)返回1，否則返回0。【參考答案】intisRing(LinkList*head){ LinkNode*p1=*head,*p2=*head; if(*head==NULL){ printf("鏈表錯誤\n"); returnERROR; } if((*head)->next==NULL){ printf("這是一個空鏈表\n"); returnFALSE; } if(p2->next->next!=NULL){ p2=p2->next->next; p1=p1->next; } elsereturnFALSE; while(p1!=p2&&p2!=NULL){ p2=p2->next; if(p2!=NULL){ p1=p1->next; p2=p2->next; } elsereturn FALSE; } if(p1==p2)returnTRUE; elsereturnFALSE;}

第三章棧和隊列一、單項選擇題1．棧操作數(shù)據(jù)的原則是________。A．先進(jìn)先出 B．后進(jìn)先出 C．后進(jìn)后出 D．隨機(jī)處理答案：B。棧的特性是后進(jìn)先出。選項A是隊列的特性。有些情況下，可以將選項C理解為先進(jìn)先出，這也是隊列的特性。選項D既不是棧的特性，也不是隊列的特性。2．入棧序列是a1,a3,a5,a2,a4,a6，出棧序列是a5,a4,a2,a6,a3,a1，則棧的容量最小是________。A．2 B．3 C．4 D．5答案：C。用圖3-1表示棧狀態(tài)的變化情況。a1入棧a3入棧a5入棧a5出棧a2入棧a4入棧a4a5a2a2a3a3a3a3a3a1a1a1a1a1a1a4出棧a2出棧a6入棧a6出棧a3出棧a1出棧a2a6a3a3a3a3a1a1a1a1a1圖圖3-1棧的狀態(tài)可以看到，在a4入棧后，棧中有4個元素，這是棧含元素最多的時刻。所以棧的容量最小是4。3．6個元素6,5,4,3,2,1依次進(jìn)棧，不能得到的出棧序列是________A．5,4,3,6,1,2 B．4,5,3,1,2,6 C．3,4,6,5,2,1 D．2,3,4,1,5,6答案：C?？梢允褂貌僮鬟^程來描述。得到選項A的操作過程是：push(6),push(5),pop(5),push(4),pop(4),push(3),pop(3),pop(6),push(2),push(1),pop(1),pop(2)。得到選項B的操作過程是：push(6),push(5),push(4),pop(4),pop(5),push(3),pop(3),push(2),push(1),pop(1),pop(2),pop(6)。得到選項D的操作過程是：push(6),push(5),push(4),push(3),push(2),pop(2),pop(3),pop(4),push(1),pop(1),pop(5),pop(6)。對于選項C，push(6),push(5),push(4),push(3),pop(3),pop(4)，此時棧頂元素是5，得不到元素6。4．輸入序列為A,B,C，借助于棧將其變?yōu)镃,B,A，經(jīng)過的棧操作為________。A．push,pop,push,pop,push,pop B．push,push,push,pop,pop,popC．push,push,pop,pop,push,pop D．push,pop,push,push,pop,pop答案：B。對應(yīng)于選項A的操作序列，得到的出棧序列是A,B,C。對應(yīng)于選項C的操作序列，得到的出棧序列是B,A,C。對應(yīng)于選項D的操作序列，得到的出棧序列是A,C,B。實際上，出棧序列與入棧序列互逆，所以必然是將所有元素依次入棧，然后依次出棧。5．若一個棧存儲在數(shù)組V[n]中，設(shè)?？諘r棧頂指針top=n-1，則下列選項中，能正確表示x入棧的是________。A．top=top+1;V[top]=x; B．V[top]=x;top=top+1;C．V[top]=x;top=top-1; D．top=top-1;V[top]=x;答案：C。根據(jù)題意，棧頂指針指向的是棧頂元素旁邊的空位置，所以入棧時，元素x直接寫入top所示的位置，然后top移至下一個空位置。又因為?？諘rtop指向的是數(shù)組下標(biāo)最大處，則意味著入棧時top應(yīng)向下標(biāo)減小的方向改變。6．用不帶頭結(jié)點的單鏈表存儲隊列時，隊頭指針指向隊頭結(jié)點，隊尾指針指向隊尾結(jié)點，則在進(jìn)行刪除操作時________。A．僅需要修改隊頭指針，不需要修改隊尾指針B．僅需要修改隊尾指針，不需要修改隊頭指針C．隊頭指針一定要修改，隊尾指針也一定要修改D．隊頭指針一定要修改，隊尾指針可能要修改答案：D。用不帶頭結(jié)點的單鏈表保存隊列時，通常需要兩個指針分別指向隊頭結(jié)點和隊尾結(jié)點。出隊時，要從隊頭刪除一個結(jié)點，此時必須修改隊頭指針，讓它指向被刪結(jié)點的后繼結(jié)點。如果隊列中還有其他結(jié)點，則隊尾指針不會變化。但如果刪除結(jié)點后隊列變?yōu)榭贞犃?，則還需要修改隊尾指針。7．下列鏈隊列的操作中，不可能修改隊尾指針的是________。A．入隊操作 B．清空隊列操作C．出隊操作 D．判隊列是否為空答案：D。入隊操作肯定會修改隊尾指針。出隊操作通常僅修改隊頭指針，但如果出隊后隊列為空，則也會修改隊尾指針。清空隊列的操作既修改隊頭指針，也修改隊尾指針。而判隊列是否為空，僅需要查看指針的值，不會進(jìn)行修改。8．循環(huán)隊列Q（最多元素為MaxSize），front指向隊頭元素所在位置，rear指向隊尾元素后的空位置，則循環(huán)隊列為滿的條件是________。A．Q.rear==Q.front B．Q.rear+1==Q.frontC．Q.rear==Q.front+1 D．(Q.rear+1)%MaxSize==Q.front答案：D?；靖拍?。參考教材中圖3-14及圖3-16。9．用不帶頭結(jié)點的單鏈表存儲隊列，其頭指針指向隊頭結(jié)點，尾指針指向隊尾結(jié)點，則在進(jìn)行出隊操作時應(yīng)進(jìn)行的操作是________。A．僅修改頭指針 B．頭、尾指針均不需要修改C．僅修改尾指針 D．頭、尾指針都可能要修改答案：D。出隊操作肯定要修改隊頭指針，如果出隊后隊列為空，則隊尾指針也要修改。10．假設(shè)以數(shù)組A[0..m-1]存放循環(huán)隊列的元素，隊頭指針front指向隊頭元素，隊尾指針rear指向隊尾元素后的空位置，則當(dāng)前隊列中的元素個數(shù)為________。A．(rear-front+m)%m B．rear-front+1C．(front-rear+m+1)%m D．(rear-front)%m答案：A。循環(huán)隊列有兩種基本形態(tài)，如圖3-2a和圖3-2b示。a0…am-1↑front↑reara)循環(huán)隊列示意圖一…v……u…↑rear↑frontb)循環(huán)隊列示意圖二對于圖3-2a，隊列中的元素個數(shù)=rear-front。對于圖3-2b，隊列中的元素個數(shù)=rear+m-front。兩個表達(dá)式可以統(tǒng)一表示為(rear-front+m)%m。11．棧和隊列的共同點是________。A．都是后進(jìn)先出 B．都是先進(jìn)先出C．只允許在端點處插入和刪除元素 D．沒有共同點答案：C。棧具有后進(jìn)先出的特點，而隊列具有先進(jìn)先出的特點。所以選項A和B都不正確。棧的插入和刪除操作都在表的一端進(jìn)行，隊列的插入和刪除分別在表的兩端進(jìn)行。所以，選項C中概括的特點是棧和隊列共同具有的。12．循環(huán)隊列存儲在數(shù)組A[0..m]中，入隊時修改隊