一、選擇題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)（隨機存取），鏈表為O(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.在單鏈表中設置頭結(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.對于一個棧作進棧運算時，應先判別棧是否為_______，作退棧運算時，應先判別棧是否為_______，當棧中元素為m時，作進棧運算時發(fā)生上溢，則說明棧的可用最大容量為_______。為了增加內(nèi)存空間的利用率和減少發(fā)生上溢的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應將兩棧的_______分別設在這片內(nèi)存空間的兩端，這樣只有當_______時才產(chǎn)生上溢。答案：滿；空；m；棧底；兩個棧頂相鄰解析：進棧前檢查棧滿（避免上溢），出棧前檢查?？眨ū苊庀乱纾粭M時元素數(shù)為最大容量m；共享棧時兩棧底在兩端，棧頂相向生長，棧頂相遇時上溢。14.設有一空棧，現(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)分配空間，無需預定義長度。缺點：只能順序存?。ㄔL問元素需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)鏈表設置尾指針的優(yōu)勢優(yōu)于設置頭指針。理由：尾指針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的指針。四、算法設計題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)鏈表，只設隊尾指針）//(1)插入元素voidEnQueue(LinkList*rear,ElemTypex){LinkList*s=(LinkList*)malloc(sizeof(LinkList));s->data=x;if(*rear==NULL){//空隊列s->next=s;//自環(huán)*rear=