一、填空題1.數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R），其中D是數(shù)據(jù)元素的有限集合，R是D上的關(guān)系的有限集合。（解析：D代表數(shù)據(jù)元素的集合，R代表元素間的關(guān)系集合。）2.數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運算這三個方面的內(nèi)容。（解析：數(shù)據(jù)結(jié)構(gòu)涵蓋邏輯結(jié)構(gòu)（數(shù)據(jù)間的關(guān)系）、存儲結(jié)構(gòu)（物理存儲方式）和運算（相關(guān)操作）。）3.數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為四大類，它們分別是集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)。（解析：邏輯結(jié)構(gòu)的分類基于元素間的關(guān)系類型。）4.線性結(jié)構(gòu)中元素之間存在一對一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。（解析：線性結(jié)構(gòu)如數(shù)組、鏈表；樹形結(jié)構(gòu)如二叉樹；圖形結(jié)構(gòu)如網(wǎng)絡(luò)圖。）5.在線性結(jié)構(gòu)中，第一個結(jié)點沒有前驅(qū)結(jié)點，其余每個結(jié)點有且只有1個前驅(qū)結(jié)點；最后一個結(jié)點沒有后續(xù)結(jié)點，其余每個結(jié)點有且只有1個后續(xù)結(jié)點。（解析：線性結(jié)構(gòu)嚴格遵循順序，首尾結(jié)點無前驅(qū)或后繼。）6.在樹形結(jié)構(gòu)中，樹根結(jié)點沒有前驅(qū)結(jié)點，其余每個結(jié)點有且只有1個前驅(qū)結(jié)點；葉子結(jié)點沒有后繼結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點數(shù)可以任意多個。（解析：樹根無父結(jié)點（前驅(qū)），葉子無子結(jié)點（后繼），非葉子結(jié)點可有多個子結(jié)點（后繼）。）7.在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以任意多個。（解析：圖結(jié)構(gòu)元素間關(guān)系自由，前驅(qū)和后繼數(shù)量無限制。）8.數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示，它們分別是順序存儲、鏈式存儲、索引存儲、哈希存儲。（解析：存儲方法包括順序（連續(xù)內(nèi)存）、鏈式（指針鏈接）、索引（索引表）、散列（哈希函數(shù)）。）9.一個算法的效率可分為時間效率和空間效率。（解析：算法效率主要從時間復雜度和空間復雜度衡量。）10.數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，以及它們之間的相互關(guān)系，并對與這種結(jié)構(gòu)定義相應(yīng)的操作，設(shè)計出相應(yīng)的算法。（解析：數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)的邏輯關(guān)系、物理存儲及操作算法。）11.下面程序段中帶下劃線的語句的執(zhí)行次數(shù)的數(shù)量級是O(nlogn)。plaintexti=1;while(i<n){for(j=1;j<=n;j++)//語法修正：逗號改為分號x=x+1;//帶下劃線的語句i=i*2;}（解析：外層while循環(huán)執(zhí)行次數(shù)為O(logn)（因i每次乘以2），內(nèi)層for循環(huán)執(zhí)行次數(shù)為O(n)，故總次數(shù)為O(nlogn)，數(shù)量級為O(nlogn)。）二、選擇題C)數(shù)據(jù)元素之間的關(guān)系解析：存儲數(shù)據(jù)時，除了元素值本身，還需存儲元素間的邏輯關(guān)系（如指針、索引），這是數(shù)據(jù)結(jié)構(gòu)的核心。C)邏輯解析：邏輯結(jié)構(gòu)描述數(shù)據(jù)元素間的抽象關(guān)系（如線性、樹形），與計算機無關(guān)；存儲結(jié)構(gòu)和物理結(jié)構(gòu)依賴于具體實現(xiàn)。C)分析算法的效率以求改進解析：算法分析的核心是評估時間/空間效率，優(yōu)化算法性能。B)可行性、確定性和有窮性解析：算法五大特性：輸入、輸出、可行性（能執(zhí)行）、確定性（步驟明確）、有窮性（執(zhí)行終止）。B.(1),(2),(4)解析：(1)錯誤：原地工作指O(1)額外空間，并非完全不需要空間。(2)錯誤：O(n)與O(2n)等價（常數(shù)系數(shù)可忽略），時間復雜度相同。(3)正確：時間復雜度通常指最壞情況的上界。(4)錯誤：語言級別與執(zhí)行效率無直接關(guān)聯(lián)（如C語言高級但高效）。C)線性結(jié)構(gòu)、非線性結(jié)構(gòu)解析：邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)（順序關(guān)系，如鏈表）和非線性結(jié)構(gòu)（樹、圖等）。A)一定連續(xù)解析：連續(xù)存儲（如數(shù)組）要求物理地址嚴格連續(xù)，這是其實現(xiàn)的基礎(chǔ)特性。三、判斷題數(shù)據(jù)元素是數(shù)據(jù)的最小單位。答案：×解析：數(shù)據(jù)的最小單位是數(shù)據(jù)項，數(shù)據(jù)元素是由數(shù)據(jù)項組成的（例如：一條記錄是數(shù)據(jù)元素，其中的字段是數(shù)據(jù)項）。記錄是數(shù)據(jù)處理的最小單位。答案：×解析：數(shù)據(jù)處理的最小單位是數(shù)據(jù)項，記錄由多個數(shù)據(jù)項組成（例如：一條學生記錄包含學號、姓名等數(shù)據(jù)項）。數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關(guān)系。答案：×解析：邏輯結(jié)構(gòu)描述數(shù)據(jù)元素之間的邏輯關(guān)系，而非數(shù)據(jù)項之間的關(guān)系（例如：線性結(jié)構(gòu)中元素的先后關(guān)系）。算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計算機有關(guān)。答案：×解析：算法優(yōu)劣取決于時間/空間復雜度，與描述語言和計算機無關(guān)（復雜度分析是數(shù)學抽象）。健壯的算法不會因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。答案：√解析：健壯性指算法對非法輸入有容錯處理（如返回錯誤提示），避免崩潰或不可控狀態(tài)。算法用高級語言描述后就是程序。答案：×解析：算法是解決問題的步驟，程序是算法的具體實現(xiàn)；算法描述不等同于可執(zhí)行程序（需編譯/解釋）。程序一定是算法。答案：×解析：程序不一定是算法，例如死循環(huán)程序不滿足算法的有窮性（算法必須有限步驟內(nèi)結(jié)束）。數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)的實際存儲形式。答案：√解析：物理結(jié)構(gòu)（存儲結(jié)構(gòu)）是數(shù)據(jù)在內(nèi)存中的具體存儲方式（如順序存儲、鏈式存儲）。順序存儲的優(yōu)點是存儲密度大且插入/刪除效率高。答案：×解析：順序存儲密度大（連續(xù)空間），但插入/刪除需移動大量元素，效率低（時間復雜度O(n)）。數(shù)據(jù)的邏輯結(jié)構(gòu)依賴于計算機的存儲結(jié)構(gòu)。答案：×解析：邏輯結(jié)構(gòu)是抽象的數(shù)據(jù)關(guān)系，獨立于存儲結(jié)構(gòu)（例如：鏈表和數(shù)組邏輯相同，存儲結(jié)構(gòu)不同）。四、分析下列算法的時間復雜度算法1：x=90;y=100;while(y>0)if(x>100){x=x-10;y--;}elsex++;時間復雜度：O(1)無論輸入規(guī)模如何，循環(huán)次數(shù)固定為常數(shù)（約1100次）。原因：y從100遞減到0，每次遞減需固定次數(shù)的x操作（約11次/遞減），總操作數(shù)恒定。算法2：i=1;while(i<=n)i=i*s;//假設(shè)s是大于1的常數(shù)時間復雜度：O(logn)循環(huán)每次將i乘以常數(shù)s，i的值呈指數(shù)增長：1→s→s2→...→s?。循環(huán)結(jié)束條件：s?>n→k≈log?(n)。對數(shù)階復雜度，與底數(shù)s無關(guān)（換底公式）。算法3：for(i=0;i<n;i++)for(j=0;j<m;j++)a[i][j]=0;時間復雜度：O(n×m)外層循環(huán)執(zhí)行n次，內(nèi)層循環(huán)執(zhí)行m次?？偛僮鲾?shù)為n×m，與兩個輸入規(guī)模線性相關(guān)。算法4：x=n;y=0;while(x>=(y+1)*(y+1))y++;時間復雜度：O(√n)循環(huán)條件：x≥(y+1)2（初始x=n）。y從0遞增，直到(y+1)2>n→最大y值≈√n。循環(huán)次數(shù)為√n級別。一、選擇題1.A線性表是n個數(shù)據(jù)元素的有限序列，可以為空（即n=0）。2.C在順序表中刪除第i個元素（索引從0開始），需將第i+1至第n-1個元素前移，移動元素數(shù)為n-i-1。3.D鏈式存儲中，節(jié)點地址不要求連續(xù)，通過指針鏈接，地址可連續(xù)或不連續(xù)。4.C查找成功的平均比較次數(shù)為(n+1)/2（等概率下，平均需遍歷一半節(jié)點）。5.D正確操作順序：s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;6.A刪除p（指向結(jié)點m）的后繼結(jié)點：修改p的next指針，使其指向后繼的后繼，即p->next=p->next->next。7.B在順序表中向第i個元素前插入（索引從1開始），需將第i至第n個元素后移，移動元素數(shù)為n-i+1。8.Bq是p的前驅(qū)，在q和p間插入s：將q的next指向s，s的next指向p，即q->next=s;s->next=p。9.C線性表中，首結(jié)點無直接前趨，尾結(jié)點無直接后繼，故C錯誤。D正確（如空表或單元素表）。10.A順序存儲支持隨機存?。ㄍㄟ^地址計算直接訪問任意元素）。11.D結(jié)點存儲地址=基地址+(索引-1)×結(jié)點大小，需基地址和結(jié)點大小。12.B等概率插入時，平均需移動n/2個結(jié)點（插入位置有n+1種可能，平均移動次數(shù)為n/2）。13.C順序表按序號查找時間復雜度為O(1)（隨機存?。湵頌镺(n)；插入、刪除和按值查找鏈表更優(yōu)。14.B有序單鏈表插入需先查找位置（平均O(n)），插入操作O(1)，總時間復雜度O(n)。15.C進棧次序A,B,C,D,E：A可（A進A出，B進B出，...）。B可（A進B進B出，C進C出，D進D出，E進E出，A出）。D可（A,B,C,D,E全進，E出，D出，C出，B出，A出）。E先出需所有元素已入棧，棧頂為E，出棧后棧頂為D，不能直接出A（需先出D,C,B），故C不可能。16.C棧頂指針top指向棧頂元素，出棧時top減1（向地址低端移動）。17.B鏈棧插入：新結(jié)點s的next指向原棧頂hs，然后hs更新為s，即s->next=hs;hs=s。18.D循環(huán)隊列隊滿條件：(rear+1)%n==front（犧牲一個單元區(qū)分隊空隊滿）。19.C循環(huán)隊列隊空條件：rear==front（無元素時指針相等）。20.A鏈隊列刪除隊首結(jié)點：將front指向front的next，即front=front->next。二、填空題1.線性表是一種典型的_________結(jié)構(gòu)。答案：線性解析：線性表是數(shù)據(jù)元素呈線性排列的數(shù)據(jù)結(jié)構(gòu)。2.在一個長度為n的順序表的第i個元素之前插入一個元素，需要后移____個元素。答案：n-i+1*解析：插入位置為i（從1開始計數(shù)），需將第i個元素及之后的元素后移，共n-i+1個元素。*3.順序表中邏輯上相鄰的元素的物理位置________。答案：相鄰解析：順序存儲中，邏輯相鄰的元素在物理內(nèi)存中連續(xù)存放。4.要從一個順序表刪除一個元素時，被刪除元素之后的所有元素均需_______一個位置，移動過程是從_______向_______依次移動每一個元素。答案：前移；前；后解析：刪除后需將后續(xù)元素前移填補空位，從被刪除元素的下一個位置（前）向表尾（后）逐個移動。5.在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過_______決定的；在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過_______決定的。答案：存儲位置；指針解析：順序存儲通過物理相鄰體現(xiàn)邏輯關(guān)系；鏈式存儲通過指針鏈接體現(xiàn)邏輯關(guān)系。6.在雙向鏈表中，每個結(jié)點含有兩個指針域，一個指向_______結(jié)點，另一個指向_______結(jié)點。答案：前驅(qū)（或直接前驅(qū)）；后繼（或直接后繼）解析：雙向鏈表的結(jié)點包含指向前驅(qū)和后繼的指針。7.當對一個線性表經(jīng)常進行存取操作，而很少進行插入和刪除操作時，則采用_______存儲結(jié)構(gòu)為宜。相反，當經(jīng)常進行的是插入和刪除操作時，則采用_______存儲結(jié)構(gòu)為宜。答案：順序；鏈式*解析：順序存儲支持高效隨機存取（O(1)），鏈式存儲支持高效插入/刪除（O(1)）。*8.順序表中邏輯上相鄰的元素，物理位置____相鄰，單鏈表中邏輯上相鄰的元素，物理位置____相鄰。答案：一定；不一定解析：順序存儲強制物理相鄰；鏈式存儲通過指針鏈接，物理位置可任意。9.線性表、棧和隊列都是_______結(jié)構(gòu)，可以在線性表的______位置插入和刪除元素；對于棧只能在_______位置插入和刪除元素；對于隊列只能在_______位置插入元素和在_______位置刪除元素。答案：線性；任何；棧頂；隊尾；隊頭解析：三者均為線性結(jié)構(gòu)；線性表允許任意位置操作；棧遵循LIFO（棧頂操作）；隊列遵循FIFO（隊尾插入，隊頭刪除）。10.根據(jù)線性表的鏈式存儲結(jié)構(gòu)中每個結(jié)點所含指針的個數(shù)，鏈表可分為_________和_______；而根據(jù)指針的聯(lián)接方式，鏈表又可分為________和_________。答案：單鏈表；雙鏈表；循環(huán)鏈表；非循環(huán)鏈表解析：單鏈表結(jié)點含1個指針（后繼），雙鏈表含2個指針（前驅(qū)和后繼）；循環(huán)鏈表的尾結(jié)點指向頭結(jié)點，非循環(huán)鏈表無此特性。11.在單鏈表中設(shè)置頭結(jié)點的作用是________。答案：簡化邊界處理（或統(tǒng)一空表/非空表操作）解析：頭結(jié)點不存儲數(shù)據(jù)，使首元結(jié)點的操作與其他結(jié)點一致，避免空表特殊處理。12.對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)點p后插入一個新結(jié)點的時間復雜度為______，在給定值為x的結(jié)點后插入一個新結(jié)點的時間復雜度為_______。答案：O(1)；O(n)解析：已知結(jié)點p時插入為O(1)；需先遍歷查找值為x的結(jié)點，平均O(n)。13.對于一個棧作進棧運算時，應(yīng)先判別棧是否為_______，作退棧運算時，應(yīng)先判別棧是否為_______，當棧中元素為m時，作進棧運算時發(fā)生上溢，則說明棧的可用最大容量為_______。為了增加內(nèi)存空間的利用率和減少發(fā)生上溢的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應(yīng)將兩棧的_______分別設(shè)在這片內(nèi)存空間的兩端，這樣只有當_______時才產(chǎn)生上溢。答案：滿；空；m；棧底；兩個棧頂相鄰解析：進棧前檢查棧滿（避免上溢），出棧前檢查棧空（避免下溢）；棧滿時元素數(shù)為最大容量m；共享棧時兩棧底在兩端，棧頂相向生長，棧頂相遇時上溢。14.設(shè)有一空棧，現(xiàn)有輸入序列1，2，3，4，5，經(jīng)過push,push,pop,push,pop,push,push后，輸出序列是_________。答案：2,3解析：操作步驟：push→棧：[1]push→棧：[1,2]pop→輸出2，棧：[1]push→棧：[1,3]pop→輸出3，棧：[1]push→棧：[1,4]push→棧：[1,4,5]輸出序列為2,3。15.無論對于順序存儲還是鏈式存儲的棧和隊列來說，進行插入或刪除運算的時間復雜度均相同為__________。答案：O(1)*解析：棧的入棧/出棧（O(1)），隊列的入隊/出隊（O(1)），無論順序（循環(huán)隊列）或鏈式存儲。*三、簡答題1.頭指針、頭結(jié)點、表頭結(jié)點的區(qū)別頭指針：指向鏈表第一個結(jié)點的指針（無論是否存在頭結(jié)點）。若鏈表為空，頭指針為NULL。頭結(jié)點：附加在鏈表首元素之前的結(jié)點（不存儲數(shù)據(jù)），其指針域指向首元素結(jié)點。用于統(tǒng)一空表和非空表的操作。表頭結(jié)點：鏈表中第一個存儲實際數(shù)據(jù)的結(jié)點（又稱首元結(jié)點）。總結(jié)：頭指針指向頭結(jié)點（若有）或表頭結(jié)點；頭結(jié)點是數(shù)據(jù)域為空的輔助結(jié)點；表頭結(jié)點是實際數(shù)據(jù)的第一個結(jié)點。2.線性表兩種存儲結(jié)構(gòu)的優(yōu)缺點順序存儲（順序表）：優(yōu)點：隨機存取（O(1)時間訪問任意元素）；存儲密度高（無額外指針開銷）。缺點：插入/刪除需移動大量元素（O(n)時間）；預分配固定空間，可能浪費或溢出。鏈式存儲（鏈表）：優(yōu)點：插入/刪除靈活（O(1)時間）；動態(tài)分配空間，無需預定義長度。缺點：只能順序存取（訪問元素需O(n)時間）；存儲密度低（指針占用額外空間）。3.多表動態(tài)變化場景下的存儲結(jié)構(gòu)選擇選擇鏈式存儲結(jié)構(gòu)。理由：表長度動態(tài)變化時，鏈表可高效插入/刪除（O(1)時間）。表總數(shù)自動改變時，鏈表動態(tài)分配內(nèi)存，避免順序表連續(xù)空間的限制。4.穩(wěn)定表快速存取場景下的存儲結(jié)構(gòu)選擇選擇順序存儲結(jié)構(gòu)。理由：順序表支持隨機存?。∣(1)時間訪問元素）。表總數(shù)穩(wěn)定且少插入/刪除，順序表的缺點影響小。5.單循環(huán)鏈表設(shè)置尾指針的優(yōu)勢優(yōu)于設(shè)置頭指針。理由：尾指針tail可直接訪問尾結(jié)點（tail）和頭結(jié)點（tail->next）。合并鏈表時：兩鏈表合并僅需修改尾指針（O(1)時間），而頭指針需遍歷到尾結(jié)點（O(n)時間）。6.四個元素的所有出棧序列可能的出棧序列（共14種）：A,B,C,DA,B,D,CA,C,B,DA,C,D,BA,D,C,BB,A,C,DB,A,D,CB,C,A,DB,C,D,AB,D,C,AC,B,A,DC,B,D,AC,D,B,AD,C,B,A注：序列需滿足棧的LIFO特性（如D,A,B,C不可能）。7.隊列的上溢現(xiàn)象及解決方法上溢現(xiàn)象：隊列滿時仍進行入隊操作導致空間溢出。解決方法：循環(huán)隊列：利用模運算重用數(shù)組空間（需犧牲一個單元區(qū)分隊空/隊滿）。鏈式隊列：動態(tài)分配結(jié)點，無固定大小限制（除非內(nèi)存耗盡）。動態(tài)擴容：順序隊列滿時分配更大空間并遷移數(shù)據(jù)（時間復雜度高）。8.算法功能分析LinkList*Demo(LinkList*L){LinkList*q,*p;if(L&&L->next){//至少有兩個結(jié)點q=L;//q指向首結(jié)點L=L->next;//L指向第二個結(jié)點（新頭）p=L;//p從新頭開始遍歷while(p->next)//找到尾結(jié)點p=p->next;p->next=q;//原首結(jié)點鏈到尾結(jié)點后q->next=NULL;//原首結(jié)點成為新尾結(jié)點}returnL;//返回新頭指針}功能：將無頭結(jié)點的單鏈表首結(jié)點移至表尾，返回新的表頭指針。示例：鏈表1→2→3→4變?yōu)?→3→4→1，返回指向2的指針。四、算法設(shè)計題1.無頭結(jié)點單鏈表中刪除第i個結(jié)點voidDeleteNode(LinkList*L,inti){if(i<1)return;//位置無效LinkList*p=L,*q;//刪除第1個結(jié)點if(i==1){if(L==NULL)return;//空表q=L;L=L->next;//修改頭指針free(q);return;}//尋找第i-1個結(jié)點intj=1;while(p&&j<i-1){p=p->next;j++;}//檢查位置有效性if(p==NULL||p->next==NULL)return;//刪除第i個結(jié)點q=p->next;p->next=q->next;free(q);}2.單鏈表求表長intListLength(LinkList*L){intlen=0;LinkList*p=L;while(p!=NULL){len++;p=p->next;}returnlen;}3.帶表頭鏈表逆置voidReverseList(LinkList*L){LinkList*p,*q;p=L->next;//p指向首元結(jié)點L->next=NULL;//頭結(jié)點next域置空while(p!=NULL){q=p->next;//保存下一個結(jié)點p->next=L->next;//頭插法插入pL->next=p;p=q;}}4.鏈表按值排序（使用prior域）voidSortList(LinkList*head){LinkList*p,*min_pre,*min_node,*sorted=NULL;while(head->next!=NULL){//尋找最小值結(jié)點min_pre=head;p=head->next;while(p->next!=NULL){if(p->next->data<min_pre->next->data)min_pre=p;p=p->next;}//移除最小值結(jié)點min_node=min_pre->next;min_pre->next=min_node->next;//將結(jié)點插入有序鏈min_node->prior=sorted;sorted=min_node;}//重建鏈表head->next=sorted;p=head->next;LinkList*prev=NULL;while(p!=NULL){p->next=prev;//反轉(zhuǎn)next指針prev=p;p=p->prior;}}5.有序表刪除范圍元素voidDeleteRange(LinkList*L,intmin,intmax){LinkList*p=L->next,*pre=L,*q;while(p!=NULL){if(p->data>min&&p->data<max){//刪除滿足條件的結(jié)點q=p;pre->next=p->next;p=p->next;free(q);}else{pre=p;p=p->next;}}}6.無序表刪除范圍元素voidDeleteRange(LinkList*L,intmin,intmax){LinkList*p=L->next,*pre=L,*q;while(p!=NULL){if(p->data>min&&p->data<max){//刪除滿足條件的結(jié)點q=p;pre->next=p->next;p=p->next;free(q);}else{pre=p;p=p->next;}}}7.循環(huán)隊列操作（單循環(huán)鏈表，只設(shè)隊尾指針）//(1)插入元素voidEnQueue(LinkList*rear,ElemTypex){LinkList*s=(LinkList*)malloc(sizeof(LinkList));s->data=x;if(*rear==NULL){//空隊列s->next=s;//自環(huán)*rear=s;}else{s->next=(*rear)->next;//新結(jié)點指向隊頭(*rear)->next=s;//原隊尾指向新結(jié)點*rear=s;//更新隊尾指針}}//(2)刪除元素voidDeQueue(LinkList*rear,ElemType*x){if(*rear==NULL)return;//空隊列LinkList*p=(*rear)->next;//p指向隊頭*x=p->data;if(p==*rear){//只有一個結(jié)點free(p);*rear=NULL;}else{(*rear)->next=p->next;//隊尾指向新的隊頭free(p);}}8.遞減有序表插入元素voidInsertDesc(SqList*L,ElemTypex){if(L->length>=L->listsize){//擴容處理（此處省略具體實現(xiàn)）}inti=L->length-1;//從后向前查找插入位置while(i>=0&&L->data[i]<x){L->data[i+1]=L->data[i];//元素后移i--;}L->data[i+1]=x;//插入元素L->length++;//表長增加}一、選擇題1.答案：C.dceab解析：棧的特點是后進先出（LIFO）。選項A、B、D的輸出序列可以通過合理的入棧和出棧操作實現(xiàn)，而選項C中的“dceab”無法實現(xiàn)，因為在“d”出棧后，“c”和“e”必須連續(xù)出棧，無法在“e”之前出棧“a”和“b”。2.答案：C.n-i+1解析：如果第一個出棧的元素是n，則棧中的元素是按n,n-1,...,1的順序入棧的。因此，第i個出棧的元素是n-i+1。3.答案：A.順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)解析：棧通常采用順序存儲結(jié)構(gòu)（數(shù)組）或鏈式存儲結(jié)構(gòu)（鏈表）實現(xiàn)。4.答案：C.棧解析：Push和Pop是棧的典型操作，分別用于入棧和出棧。5.答案：C.s->next=HS;HS=s;解析：在鏈棧中，新結(jié)點s插入到棧頂，因此s的next指向當前棧頂HS，然后將HS更新為s。6.答案：B.1,2,3,4解析：隊列的特點是先進先出（FIFO），因此出隊順序與入隊順序一致。7.答案：C.只允許在端點處插入和刪除元素解析：棧和隊列的共同點是插入和刪除操作都限制在端點進行，但棧是同一端（棧頂），隊列是兩端（隊尾插入，隊頭刪除）。8.答案：C.棧頂解析：棧的插入和刪除操作只能在棧頂進行。9.答案：C.插入和刪除解析：棧頂可以進行插入（Push）和刪除（Pop）操作。10.答案：D.D解析：元素按A、B、C、D順序入棧，Pop操作會取出棧頂元素D。11.答案：B.后進先出解析：棧的特點是后進先出（LIFO）。12.答案：B.可變的解析：棧中元素的個數(shù)是動態(tài)變化的，取決于入棧和出棧操作。13.答案：B.B解析：元素按A、B、C、D順序入棧，兩次Pop操作后，棧頂元素是B。14.答案：A.必須一致解析：棧內(nèi)元素的類型必須一致，這是由棧的同構(gòu)性決定的。15.答案：A.已固定解析：順序棧的空間大小在定義時已固定。16.答案：B.加了限制的解析：棧是一種操作受限的線性表，只能在棧頂進行插入和刪除。17.答案：D.插入、刪除元素的位置解析：棧與一般線性表的區(qū)別在于插入和刪除操作的位置受限。18.答案：D.棧解析：棧適合用于檢查括號匹配問題，因為可以方便地檢查最近的左括號和右括號是否配對。19.答案：C.棧解析：遞歸調(diào)用時，參數(shù)和返回地址通過棧來管理。20.答案：A.(rear-front+m)%m解析：循環(huán)隊列中，元素個數(shù)的計算公式為(rear-front+m)%m，可以正確處理隊列環(huán)繞的情況。---二、名詞解釋1.棧棧是一種線性數(shù)據(jù)結(jié)構(gòu)，遵循后進先出（LIFO）的原則。插入和刪除操作只能在棧頂進行，主要操作包括Push（入棧）和Pop（出棧）。2.隊列隊列是一種線性數(shù)據(jù)結(jié)構(gòu)，遵循先進先出（FIFO）的原則。插入操作在隊尾進行，刪除操作在隊頭進行，主要操作包括Enqueue（入隊）和Dequeue（出隊）。3.循環(huán)隊列循環(huán)隊列是隊列的一種實現(xiàn)方式，通過將隊列的首尾相連形成一個環(huán)形結(jié)構(gòu)，以解決順序隊列中“假溢出”的問題。循環(huán)隊列通過模運算實現(xiàn)指針的循環(huán)移動。一、單項選擇題1.答案：C.模式匹配是串的一種重要運算解析：-A錯誤：串是字符的有限序列，不是無限序列。-B錯誤：空串是長度為0的串，不包含任何字符（包括空格）。-C正確：模式匹配是串的核心運算之一，用于查找子串在主串中的位置。-D錯誤：串可以采用順序存儲（如數(shù)組）或鏈式存儲（如塊鏈結(jié)構(gòu)）。2.答案：B.數(shù)據(jù)元素是一個字符解析：串的特殊性在于其數(shù)據(jù)元素是單個字符，而普通線性表的數(shù)據(jù)元素可以是任意類型。3.答案：B.串中所含字符的個數(shù)解析：串的長度是指串中字符的總數(shù)，包括空格和其他符號。4.答案：C.模式匹配解析：模式匹配是用于查找子串在主串中首次出現(xiàn)位置的算法，如KMP算法或BF算法。5.答案：B.11解析：串s="data"的長度為4，子串個數(shù)為\(\frac{n(n+1)}{2}+1=\frac{4\times5}{2}+1=11\)（包括空串和所有連續(xù)字符組合）。---二、填空題1.答案：空串；字符解析：-空串是長度為0的串，不含任何字符。-串的長度是指串中字符的總數(shù)。2.答案：由空格組成的串；空格的數(shù)量解析：-空格串是由一個或多個空格組成的串（如""）。-其長度是空格的數(shù)量，與空串（長度為0）不同。3.答案：長度；相同；子；主解析：-兩個串相等的條件是長度相同且對應(yīng)字符完全相同。-子串是串中任意連續(xù)字符組成的序列，原串稱為主串。4.答案：3解析：-BF算法（暴力匹配）從主串"structure"的第一個字符開始匹配子串"truc"。-首次匹配成功的位置是第3個字符開始（"struc"中的"truc"），因此返回3（假設(shè)下標從0開始則為2，但通常題目描述為從1開始）。5.答案：2解析：-模式串P="abaabc"的next數(shù)組計算如下：-next[0]=-1（通常定義為-1或0，視實現(xiàn)而定）-next[1]=0-next[2]=0（"ab"無公共前后綴）-next[3]=1（"aba"的最長公共前后綴為"a"，長度1）-next[4]=1（"abaa"的最長公共前后綴為"a"）-next[5]=2（"abaab"的最長公共前后綴為"ab"，長度2）-因此next[5]=2。一、選擇題1.正確答案：C.a[3-1][3]解析：數(shù)組

a

定義為

inta[3][4]，表示有3行（行下標范圍0到2）和4列（列下標范圍0到3）。數(shù)組下標從0開始，最大值為n-1。2.正確答案：B.1032解析：根據(jù)元素

a[i][j]

的地址計算公式為：基地址+(i*列數(shù)+j)*元素大小。在a[2][4]之前，總計12+4=16個元素。偏移量16*2=32，地址1000+32=1032。因此，地址為1032。3.正確答案：D.n(n+1)/2解析：根據(jù)對稱矩陣壓縮存儲的特點，數(shù)組B中總元素數(shù)=1+2+...+n=n(n+1)/2。4.正確答案：B.隨機存儲解析：稀疏矩陣壓縮存儲（如三元組）通常只存儲非零元素及其位置（如(行,列,值)），元素存儲非連續(xù)，失去隨機存儲特性。二、應(yīng)用題參考答案：壓縮存儲原理：利用連續(xù)相同元素重復出現(xiàn)的特性，用(元素值,重復次數(shù))的二元組序列代替原數(shù)組。存儲結(jié)構(gòu)：創(chuàng)建一個新的結(jié)構(gòu)數(shù)組B[]，每個元素包含：value：原始數(shù)組中的元素值。count：該值連續(xù)重復的次數(shù)。示例：原數(shù)組A=[5,5,5,8,8,3,3,3,3]壓縮后B=[(5,3),(8,2),(3,4)]?？臻g節(jié)省：原數(shù)組空間：O(n)。壓縮后空間：O(k)（k為連續(xù)重復段的段數(shù)）。當重復段遠少于n時（如全相同元素時k=1），空間大幅優(yōu)化。參考答案：x；分析：Head操作取第一個元素x（原子元素）。（2）((x,y),z)分析：Tail操作移除廣義表第一個元素(a,b)，剩余元素組成的子表為((x,y),z)。參考答案：算法步驟：初始化累加器sum=0。遍歷三元組表中的每個元素：若當前三元組的行號row等于列號col：將value加入sum。返回sum。代碼實現(xiàn)（C/C++）：typedefstruct{//三元組結(jié)構(gòu)introw,col;floatvalue;//假設(shè)元素為浮點型}Triple;typedefstruct{//三元組表Tripledata[MAXSIZE];intlen;//非零元素個數(shù)}TSMatrix;floatdiagonalSum(TSMatrixM){floatsum=0.0;for(inti=0;i<M.len;i++){Triplet=M.data[i];if(t.row==t.col){//判斷是否在對角線上sum+=t.value;}}returnsum;}時間復雜度：O(len)，其中l(wèi)en為非零元素個數(shù)，遠小于n2。一、選擇題1.正確答案：B解析：樹中結(jié)點總數(shù)N=度數(shù)之和+1。給定度為4的結(jié)點20個、度為3的結(jié)點10個、度為2的結(jié)點1個、度為1的結(jié)點10個，度數(shù)之和為4×20+3×10+2×1+1×10=80+30+2+10=122。因此，總結(jié)點數(shù)N=122+1=123。葉子結(jié)點個數(shù)為123-20-10-1-10=82個。2.正確答案：C解析：葉子結(jié)點個數(shù)n0=n2+1=8，結(jié)點總數(shù)N=n0+n1+n2=8+5+7=20。3.正確答案：C解析：該完全二叉樹，n0=8，n2=n0-1=7，則n=n0+n1+n2=15+n1。完全二叉樹中n1=0或n1=1，則n1=1時結(jié)點個數(shù)最多，此時n=16。最大高度h==5。4.正確答案：C解析：完全二叉樹的葉子結(jié)點只能在最下兩層，對于本題，結(jié)點最多的情況是第6層為倒數(shù)第二層，即1～6層構(gòu)成一個滿二叉樹，其結(jié)點總數(shù)為26-1=63。其中第6層有25=32個結(jié)點，含8個葉子結(jié)點，則另外有32-8=24個非葉子結(jié)點，它們中每個結(jié)點有兩個孩子結(jié)點（均為第7層的葉子結(jié)點），計48個葉子結(jié)點。這樣最多的結(jié)點個數(shù)=63+48=111。5.正確答案：A解析：森林轉(zhuǎn)二叉樹時，第一棵樹的根作為二叉樹的根，其左子樹是第一棵樹去除根后的子樹（結(jié)點數(shù)為a?1)，右子樹是其余樹轉(zhuǎn)換的二叉樹（結(jié)點數(shù)為b+c+d)。故二叉樹根結(jié)點的左子樹結(jié)點數(shù)為a?1。6.正確答案：C森林轉(zhuǎn)二叉樹后，無右孩子的結(jié)點對應(yīng)原森林中是其父結(jié)點最后一個孩子的結(jié)點或最后一棵樹的根。森林中有n個非葉子結(jié)點，每個非葉子結(jié)點恰好有一個最后一個孩子，共n個結(jié)點；加上最后一棵樹的根（無右孩子），總計n+1個無右孩子的結(jié)點。7.正確答案：D解析：高度為3的滿二叉樹有7個結(jié)點：根A，左孩子B，右孩子C；B有左孩子D、右孩子E；C有左孩子F、右孩子G。還原為森林：A為第一棵樹根，其左子樹轉(zhuǎn)換為子樹（B為根，D、E為子），右子樹轉(zhuǎn)換為子樹（C為根，F(xiàn)、G為子）。包含A的樹有結(jié)點A、B、D、E，共4個。二、填空題第一個空：11第二個空：6解析：三次樹度數(shù)之和為3×2+2×1+1×2=6+2+2=10，總結(jié)點數(shù)=10+1=11，葉子結(jié)點數(shù)=11?2?1?2=6。第一個空：14解析：根據(jù)樹的性質(zhì)，度數(shù)之和+1=結(jié)點總數(shù)，可得樹的結(jié)點總數(shù)N為3×2+2×3+2×4+1=21。葉子結(jié)點個數(shù)=21-3-2-2=14。3.第一個空：A第二個空：B、E、G、D第三個空：4第四個空：E、F第五個空：A解析：括號表示A(B,C(E,F(G)),D)對應(yīng)樹結(jié)構(gòu)：根：AA的孩子：B、C、DC的孩子：E、FF的孩子：G葉子：B、E、G、D（無孩子）C的孩子：E、FC的雙親：A應(yīng)用題參考答案：樹形表示形式為：對應(yīng)的先序序列為：abcedfhgij解析：由后序序列echfjigdba（根為a），中序序列ecbhfdjiga（左子樹中序ecbhfdjig，右子樹空）。遞歸構(gòu)建：-左子樹后序echfjigdb（根b），中序ecbhfdjig（左子樹中序ec，右子樹中序hfdjig）。-左子樹：中序ec，后序ec（根c，左e）。-右子樹：中序hfdjig，后序hfjigd（根d），左子樹中序hf（根f，左h），右子樹中序jig（根g，左i，i左j）。參考答案：typedefstructnode{chardata;structnode*lchild，*rchild;}BTNode;intNodeNum(BTNode*b){if(b==NULL)return0;elsereturnNodeNum(b->lchild)+NodeNum(b->rchild)+1;}參考答案：typedefstructnode{chardata;structnode*lchild，*rchild;}BTNode;intcount=0; voidLnodenum(BTNode*b，inth，intk){if(b==NULL) return0;else {if(h==k)count++; elseif(h<k) {Lnodenum1(b->lchild，h+1，k);Lnodenum1(b->rchild，h+1，k);}}}參考答案：voidfindMinNode(BTNode*b,char*min_val){if(b==NULL)return;if(b->data<*min_val)*min_val=T->data;findMinNode(b->lchild,min_val);findMinNode(b->rchild,min_val);}charfindMin(BTNode*b){if(b==NULL)return'\0';charmin_val=b->data;findMinNode(b,&min_val);returnmin_val;}參考答案：構(gòu)造的哈夫曼樹為：帶權(quán)路徑長度為：WPL=8+12+12+14+16+18=80哈夫曼編碼（左0右1）：a：1010b：1011c：100d：00e：01f：11第7章習題答案一、單項選擇題在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的____倍。

答案：C.2

解析：在無向圖中，每條邊貢獻兩個度數(shù)（每個端點一個），因此度數(shù)之和是邊數(shù)的兩倍。在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的__倍。

答案：B.1

解析：在有向圖中，每條邊對應(yīng)一個入度和一個出度，因此入度之和等于出度之和，且都等于邊數(shù)。有8個結(jié)點的無向圖最多有__條邊。

答案：B.28

解析：無向完全圖的邊數(shù)為

n(n?1)/2?，代入

n=8得

8×7/2=28。有8個結(jié)點的無向連通圖最少有___條邊。

答案：C.7

解析：無向連通圖的最少邊數(shù)為生成樹的邊數(shù)，即

n?1=8?1=7。有8個結(jié)點的有向完全圖有__條邊。

答案：C.56

解析：有向完全圖的邊數(shù)為

n(n?1)，代入

n=8

得

8×7=56。用鄰接表表示圖進行廣度優(yōu)先遍歷時，通常是采用___來實現(xiàn)算法的。

答案：B.隊列

解析：廣度優(yōu)先遍歷（BFS）使用隊列管理待訪問頂點，確保按層次遍歷。用鄰接表表示圖進行深度優(yōu)先遍歷時，通常是采用____來實現(xiàn)算法的。

答案：A.棧

解析：深度優(yōu)先遍歷（DFS）通常使用棧（或遞歸調(diào)用棧）實現(xiàn)，以探索路徑深度。深度優(yōu)先遍歷類似于二叉樹的

答案：A.先序遍歷

解析：DFS的訪問順序（根-子節(jié)點）與二叉樹的先序遍歷（根-左-右）相似。廣度優(yōu)先遍歷類似于二叉樹的

答案：D.層次遍歷

解析：BFS按層次訪問頂點，與二叉樹的層次遍歷一致。任何一個無向連通圖的最小生成樹

答案：B.一棵或多棵

解析：最小生成樹可能不唯一（例如，圖中存在相同權(quán)重的邊時可能有多個），但一定存在。二、填空題圖有

鄰接矩陣、鄰接表

等存儲結(jié)構(gòu)，遍歷圖有

深度優(yōu)先遍歷、廣度優(yōu)先遍歷

等方法。有向圖G用鄰接矩陣存儲，其第i行的所有元素之和等于頂點i的

出度。如果n個頂點的圖是一個環(huán)，則它有

n

棵生成樹。(以任意一頂點為起點，得到n-1條邊)n個頂點e條邊的圖，若采用鄰接矩陣存儲，則空間復雜度為

O(n2)。n個頂點e條邊的圖，若采用鄰接表存儲，則空間復雜度為

O(n+e)。設(shè)有一稀疏圖G，則G采用

鄰接表

存儲較省空間。設(shè)有一稠密圖G，則G采用

鄰接矩陣

存儲較省空間。圖的逆鄰接表存儲結(jié)構(gòu)只適用于

有向

圖。已知一個圖的鄰接矩陣表示，刪除所有從第i個頂點出發(fā)的方法是

將鄰接矩陣的第i行全部置為0。圖的深度優(yōu)先遍歷序列

不唯一。第8章習題答案一、單項選擇題如果要求一個線性表既能較快的查找，又能適應(yīng)動態(tài)變化的要求，最好采用()查找法。

答案：C.分塊查找

解析：分塊查找結(jié)合了順序查找和折半查找的優(yōu)點，塊內(nèi)可無序（適應(yīng)動態(tài)插入/刪除），塊間有序（支持較快查找）。對22個記錄的有序表作折半查找，當查找失敗時，至少需要比較（）次關(guān)鍵字。

答案：C.5

*解析：n=22時，折半查找樹的最大高度為5（因

24<22≤25），查找失敗時至少需比較5次（最壞情況）。*在平衡二叉樹中插入一個結(jié)點后造成了不平衡，設(shè)最低的不平衡結(jié)點為A，并已知A的左孩子的平衡因子為0，右孩子的平衡因子為1，則應(yīng)作（）型調(diào)整以使其平衡。

答案：D.RR

解析：A的右孩子平衡因子為1（右重），且插入發(fā)生在右子樹的右子樹，故需RR旋轉(zhuǎn)。已知一個有序表(13,18,24,35,47,50,62,83,90,115,134)，當二分查找值為90的元素時，查找成功的比較次數(shù)為()。

答案：B.2

*解析：第一次mid=5（值50<90），第二次mid=8（值90），共2次比較。*下面關(guān)于哈希查找的說法，不正確的是（）。

答案：A.采用鏈地址法處理沖突時，查找一個元素的時間是相同的

解析：查找時間取決于鏈表長度，不同關(guān)鍵字的哈希沖突鏈長度可能不同，查找時間不一定相同。設(shè)哈希表長為14，哈希函數(shù)是H(key)=key%11，表中已有數(shù)據(jù)的關(guān)鍵字為15,38,61,84共四個，現(xiàn)要將關(guān)鍵字為49的元素加到表中，用二次探測法解決沖突，則放入的位置是（）。

答案：D.9

*解析：H(49)=5（沖突），探測序列：*(5+12)%14=6（沖突，有61）(5?12)%14=4（沖突，有15）(5+22)%14=9（空閑，成功放置）。采用線性探測法處理沖突，可能要探測多個位置，在查找成功的情況下，所探測的這些位置上的關(guān)鍵字()。

答案：A.不一定都是同義詞

解析：線性探測可能引發(fā)“堆積”，探測路徑上可能包含非同義詞（不同哈希地址的關(guān)鍵字）。由n個數(shù)據(jù)元素組成的兩個表：一個遞增有序，一個無序。采用順序查找算法，對有序表從頭開始查找，發(fā)現(xiàn)當前元素已不小于待查元素時，停止查找，確定查找不成功，已知查找任一元素的概率是相同的，則在兩種表中成功查找()。

答案：B.平均時間兩者相同

解析：成功查找時，有序表提前停止僅減少失敗比較次數(shù)，成功查找的平均比較次數(shù)均為

（n+1）/2。對長度為3的順序表進行查找，若查找第一個元素的概率為1/2，查找第二個元素的概率為1/3,查找第三個元素的概率為1/6,則查找任一元素的平均查找長度為()。

答案：A.5/3

解析：ASL=

(1/2×1)+(1/3×2)+(1/6×3)=1/2+2/3+1/2=5/3?.具有