單鏈表題目和答案_第1頁
單鏈表題目和答案_第2頁
單鏈表題目和答案_第3頁
單鏈表題目和答案_第4頁
單鏈表題目和答案_第5頁
已閱讀5頁,還剩2頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

1、丙度文厲.1第2章自測卷答案一、填空1順序表中邏輯上相鄰的元素的物理位置相互相鄰。單鏈表中邏輯上相鄰的元素的物理位置丕相鄰。2. 在單鏈表中,除了首元結點外,任一結點的存儲位宜由其直接前驅結點值域指示。3. 在n個結點的單鏈表中要刪除已知結點*p,需找到它的地址。二、判斷正誤(在正確的說法后面打勾,反之打叉)1. 鏈表的每個結點中都恰好包含一個指針。X2. 鏈表的物理存儲結構具有同鏈表一樣的順序。X3. 鏈表的刪除算法很簡單,因為當刪除鏈中某個結點后,il算機會自動地將后續(xù)的各個單元向前移動。X4. 線性表的每個結點只能是一個簡單類型,而鏈表的每個結點可以是一個復雜類型。Y5. 順序表結構適宜

2、于進行順序存取,而鏈表適宜于進行隨機存取。Y6. 順序存儲方式的優(yōu)點是存儲密度大,且插入、刪除運算效率高。X7. 線性表在物理存儲空間中也一定是連續(xù)的。X&線性表在順序存儲時,邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。X9. 順序存儲方式只能用于存儲線性結構。X10. 線性表的邏輯順序與存儲順序總是一致的。X三、單項選擇題(A)1.鏈接存儲的存儲結構所占存儲空間:(A)分兩部分,一部分存放結點值,另一部分存放表示結點間關系的指針(B)只有一部分,存放結點值(C)只有一部分,存儲表示結點間關系的指針(D)分兩部分,一部分存放結點值,另一部分存放結點所占單元數(B ) 2.鏈表是一種

3、采用存儲結構存儲的線性表:(A)順序 (B)鏈式(C)星式(D)網狀(D ) 3.線性表若采用鏈式存儲結構時,要求內存中可用存儲單元的地址:(A)必須是連續(xù)的(B)部分地址必須是連續(xù)的(C) 一定是不連續(xù)的(D)連續(xù)或不連續(xù)都可以(B ) 4.線性表L在情況下適用于使用鏈式結構實現。(B)需不斷對L進行刪除插入(D) L中結點結構復雜(C)小于1:(D)不能確定(A)需經常修改L中的結點值(C)L中含有大量的結點C) 5.單鏈表的存儲密度(A)大于1:(B)等于1:A) 6、在單鏈表的一個結點中有個指針。A、1B、2C、3D、4(D ) 7、設一個鏈表最常用的操作是在末尾插入結點和刪除尾結點,

4、則選用最節(jié)省時間。A、單鏈表B、單循環(huán)鏈表C、帶尾指針的單循環(huán)鏈表D、帶頭結點的雙循環(huán)鏈表(B ) 8、在單鏈表指針為p的結點之后插入指針為s的結點,正確的操作是。A、p->next=s;s->next=p->next; Bs->next=p->next;p->next=s;C、p->next=s;p->next=s->next;D、p->next=s->next;p->next=s;(C ) 9、對于一個頭指針為head的帶頭結點的單鏈表,判泄該表為空表的條件是。A、head=NULLB、head-*next=NULLC

5、、head-*next=headD.head!=NULL (head 指向誰的)(c ) 10、在雙向鏈表指針p的結點前插入一個指針q的結點操作是。A、p->prior=q;q->next=p;p->prior->next=q:q->prior=q;B、p->prior=q:p->prior->next=q:q->next=p;q->prior=p->prior;C、q->next=p;q->prior=p->prior;p->Prior->next=q;p->prior=q;D、q->

6、prior=p->prior;q->next=q:p->prior=q;p->prior=q;(A) 11、在一個單鏈表中,若刪除P所指結點的后續(xù)結點,則執(zhí)行。A p-next=p->next->next;B、p=p->next;p->next=p->next->next;C p->next=p->next;D、p=p->next->next;(A ) 12、不帶頭結點的單鏈表head為空的判定條件是。A> head=NULLB、head->next=NULLhead->next=headD、

7、head!=NULL(B ) 13、鏈表不具有的特點是。A、插入、刪除不需要移動元素B、可隨機訪問任一元素C、不必事先估計存儲空間D、所需空間與線性長度成正比X ) 1.鏈表的每個結點中都恰好包含一個指針。答:錯誤。鏈表中的結點可含多個指針域,分別存放多個指針。例如,雙向鏈表中的結點可 以含有兩個指針域,分別存放指向其直接前趨和直接后繼結點的指針。(X )2.鏈表的物理存儲結構具有同鏈表一樣的順序。錯,鏈表的存儲結構特點是無序, 而鏈表的示意圖有序。(X ) 3.鏈表的刪除算法很簡單,因為當刪除鏈中某個結點后,計算機會自動地將后續(xù) 的各個單元向前移動。錯,鏈表的結點不會移動,只是指針內容改變。

8、(X )4.線性表的每個結點只能是一個簡單類型,而鏈表的每個結點可以是一個復雜類 型。錯,混淆了邏輯結構與物理結構,鏈表也是線性表!且即使是順序表,也能存放記錄型數據。(X ) 5.順序表結構適宜于進行順序存取,而鏈表適宜于進行隨機存取。錯,正好說反了。順序表才適合隨機存取,鏈表恰恰適于“順藤摸瓜”(X ) 6.順序存儲方式的優(yōu)點是存儲密度大,且插入、刪除運算效率高。錯,前一半正確,但后一半說法錯誤,那是鏈式存儲的優(yōu)點。順序存儲方式插入、刪除運算 效率較低,在表長為n的順序表中,插入和刪除一個數據元素,平均需移動表長一半個數的 數據元素。(X ) 7.線性表在物理存儲空間中也一定是連續(xù)的。錯,

9、線性表有兩種存儲方式,順序存儲和鏈式存儲。后者不要求連續(xù)存放。3百度文庫-讓毎個人平等地提升自我(x ) 8.線性表在順序存儲時,邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。錯誤。線性表有兩種存儲方式,在順序存儲時,邏輯上相鄰的元素在存儲的物理位置次序上 也相鄰。(X ) 9.順序存儲方式只能用于存儲線性結構。錯誤。順序存儲方式不僅能用于存儲線性結構,還可以用來存放非線性結構,例如完全二義 樹是屬于非線性結構,但其最佳存儲方式是順序存儲方式。(后一節(jié)介紹)(X ) 10.線性表的邏輯順序與存儲順序總是一致的。錯,理曲同7。鏈式存儲就無需一致。三、填空題1、在帶頭結點的單鏈表L中,若要刪除第

10、一個元素,則需要執(zhí)行下列三條語句::next =Unext; free (U)。2、在單鏈表L中,若要在指針P所指結點之后插入由指針S所指的結點,則需執(zhí)行下列語句:S->next二P->next; :3、在帶有頭結點的單鏈表L中,第一個元素結點的指針是°4、雙循環(huán)鏈表L中由指針P所指向的某結點為尾結點的條件是1. 【嚴題集2. 2】在順序表中插入或刪除一個元素,需要平均移動 表中一半元素,具體 移動的元素個數與表長和該元素在表中的位置有關。2. 線性表中結點的集合是有限的,結點間的關系是一對一 的。3. 向一個長度為n的向量的第i個元素(lWiWn+1)之前插入一個元素時

11、,需向后移動 n-i+l 個元素。4. 向一個長度為n的向量中刪除第i個元素(lWiWn)時,需向前移動個元素。5. 在順序表中訪問任意一結點的時間復雜度均為0,因此,順序表也稱為隨機存 取的數據結構。6. 【嚴題集2. 2】順序表中邏輯上相鄰的元素的物理位置 必定相鄰。單鏈表中邏輯上相 鄰的元素的物理位置不一定相鄰。7. 【嚴題集2. 2】在單鏈表中,除了首元結點外,任一結點的存儲位置山其直接前驅結 點的鏈域的值指示。8. 在n個結點的單鏈表中要刪除已知結點*p,需找到它的前驅結點的地址,其時間復雜度為 0 (n) odatanext1、設有兩個單鏈表L和L1,各結點結構如下:試畫出該鏈表的

12、結構圖,并編寫算法,判斷單鏈表L1是否與單鏈表L相同,相同返回 1,不同返回0。五、簡答題1.【嚴題集2. 3】試比較順序存儲結構和鏈式存儲結構的優(yōu)缺點。在什么情況下用順序表 比鏈表好?答:順序存儲時,相鄰數據元素的存放地址也相鄰(邏輯與物理統一);要求內存中可用 存儲單元的地址必須是連續(xù)的。優(yōu)點:存儲密度大( = 1?),存儲空間利用率高。缺點:插入或刪除元素時不方便。鏈式存儲時,相鄰數據元素可隨意存放,但所占存儲空間分兩部分,一部分存放結點值, 另一部分存放表示結點間關系的指針優(yōu)點:插入或刪除元素時很方便,使用靈活。缺點:存儲密度小«1),存儲空間利用率低。順序表適宜于做査找這樣

13、的靜態(tài)操作;鏈表宜于做插入、刪除這樣的動態(tài)操作。若線性表的長度變化不大,且其主要操作是查找,則采用順序表;若線性表的長度變化較大,且其主要操作是插入、刪除操作,則采用鏈表。2 .【嚴題集2.1】描述以下三個概念的區(qū)別:頭指針、頭結點、首元結點(第一個元素結 點)。在單鏈表中設置頭結點的作用是什么?首元結點答:苴元結點是指鏈表中存儲線性表中第一個數據元素6的結點。為了操作方便,通常在鏈 表的首元結點之前附設一個結點,稱為頭結點,該結點的數據域中不存儲線性表的數據元素, 其作用是為了對鏈表進行操作時,可以對空表.非空表的情況以及對首元結點進行統一處理。 頭指針是指向鏈表中第一個結點(或為頭結點或為首元結點)的指針。若鏈表中附設頭結點, 則不管線性表是否為空表,頭指針均不為空。否則表示空表的鏈表

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論