數(shù)據(jù)結構題集答案復習過程

1、數(shù)據(jù)結構題集答案數(shù)據(jù)結構題集第一章緒論一、單選題1 .在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成C0A.動態(tài)結構和靜態(tài)結構B.緊湊結構和非緊湊結構C.線性結構和非線性結構D.內部結構和外部結構2 .數(shù)據(jù)結構在計算機內存中的表示是指AoA.數(shù)據(jù)的存儲結構B.數(shù)據(jù)結構C.數(shù)據(jù)結構的邏輯結構D.數(shù)據(jù)元素之間的關系3 .【A】是數(shù)據(jù)的最小單位，【B】是數(shù)據(jù)的基本單位。A.數(shù)據(jù)項B.數(shù)據(jù)元素C.信息項D.表元素4 .計算機所處理數(shù)據(jù)一般具有某種內在聯(lián)系，這是指BoA.數(shù)據(jù)與數(shù)據(jù)之間存在某種關系B.數(shù)據(jù)元素與數(shù)據(jù)元素之間存在某種關系C.元素內部存在某種結構D.數(shù)據(jù)項與數(shù)據(jù)項之間存在某種關系5 .算法分析的目

2、的是【C】。A.找出數(shù)據(jù)結構的合理性B.研究輸入和輸出的關系C.分析算法的效率以求改進D.分析算法的易懂性6 .在存儲數(shù)據(jù)時，不僅要考慮存儲各數(shù)據(jù)元素的值，而且還要存儲【C】。A.數(shù)據(jù)處理的方法B.數(shù)據(jù)元素的類型C.數(shù)據(jù)元素之間的關系D.數(shù)據(jù)的存儲方法7 .算法分析的主要任務是分析DoA.算法是否具有較好的可讀性8 .算法中是否存儲語法錯誤和邏輯錯誤C.算法的功能是否符合設計要求D.算法的執(zhí)行時間與問題規(guī)模之間的關系。8 .數(shù)據(jù)的運算AoA.效率與采用何種存儲結構有關B.是根據(jù)存儲結構來定義的C.有算術運算和關系運算兩大類D.必須用程序設計語言來描述9 .算法的計算量的大小稱為算法的BoA.效

3、率B.時間復雜度C.現(xiàn)實性D.難度10 .連續(xù)存儲分配時，存儲單元的地址【A】。A.一定連續(xù)B.一定不連續(xù)C.不一定連續(xù)D.部分連續(xù)，部分不連續(xù)二、判斷題1 .數(shù)據(jù)元素是數(shù)據(jù)結構的最小單位【.X】。2 .數(shù)據(jù)的邏輯結構說明數(shù)據(jù)元素之間的順序關系，它依賴于計算機的存儲結構X.03 .數(shù)據(jù)的邏輯結構指數(shù)據(jù)元素的各數(shù)據(jù)項之間的邏輯關系【X.】。4 .算法的優(yōu)劣與算法的描述語言無關，但與使用的計算機有關【.X】。5 .數(shù)據(jù)結構的抽象操作的定義與具體實現(xiàn)有關【.X】。三、填空題1 .數(shù)據(jù)的邏輯結構指數(shù)據(jù)元素之間的邏輯關系。2 .一個數(shù)據(jù)結構在計算機中的表示稱為存儲結構。3 .數(shù)據(jù)的物理結構主要包括順序存

4、儲結構的表示和鏈式存儲結構的表示。4 .數(shù)據(jù)邏輯結構包括集合、線性結構、樹和圖四種,樹結構和圖結構統(tǒng)稱為非線性結構。5 .順序存儲方法把邏輯上邏輯上相鄰的元素存儲在物理位置相鄰的存儲單五里；鏈式存儲方法中結點間的邏輯關系是由指針域表示的。6、數(shù)據(jù)結構研究的是邏輯結構和物理結構以及它們之間的相互關系、并對于這種結構定義相應的運算，設計出相應的算法。7 .算法的執(zhí)行時間是問題規(guī)模n的函數(shù)。8 .以下是4個算法所有語句頻度之和的表達式，其中的復雜度相同的是A和B。A.TA(n)=2n3+3n2+1000B.TB(n尸n3-n210g2n-1000C.Tc(n)=n210g2n+n2D.TD(n)=n

5、2+1000四、解答題1 .簡述數(shù)據(jù)的邏輯結構和存儲結構的關系。答：在數(shù)據(jù)結構中，邏輯結構和存儲結構是密切相關的，存儲結構不僅將數(shù)據(jù)元素存儲到計算機中，而且還要表示各數(shù)據(jù)元素之間的邏輯關系。邏輯結構與計算機無關，存儲結構是數(shù)據(jù)元素之間的關系在計算機中的表示。通常情況下，一種邏輯結構可以有多種存儲結構，例如，線性結構可以采取順序存儲結構或鏈式存粗結構表示。2 .數(shù)據(jù)結構和數(shù)據(jù)類型有什么區(qū)別？答：數(shù)據(jù)結構是相互間存在一種或多種特定關系的數(shù)據(jù)元素的集合，一般包括三個方面的內容：數(shù)據(jù)的邏輯結構、存儲結構和多數(shù)據(jù)的運算。數(shù)據(jù)類型是一個值得集合和定義在這個值集上的一組操作的總稱。數(shù)據(jù)結構重點考慮元素之間的

6、關系，數(shù)據(jù)類型重點考慮數(shù)據(jù)的個體特征。3 .當為解決某一問題已經(jīng)選定其數(shù)據(jù)的邏輯結構后，選擇數(shù)據(jù)的存儲結構時,應從哪些方面考慮？答：通常從兩個方面考慮：第一是算法實現(xiàn)的存儲空間復雜度；第二是算法執(zhí)行的時間復雜度。若存儲空間難以確定，宜選擇鏈式存儲結構，否則選擇順序存儲結構。若插入、刪除操作頻繁，則選鏈式存儲結構，否則選擇順序存儲結構。第二章線性表一、單選題1 .鏈表不具備的特點是【A】。A.可隨機訪問任一結點B.插入刪除不需要移動元素C.不必事先估算存儲空間D.所需空間與其長度成正比2 .設線性表有n個元素，以下操作中，【A】在順序表上實現(xiàn)比在鏈表上實現(xiàn)效率更高。A.輸出第i(1&iwn)個元

7、素的值B.順序輸出這n個元素C.交換第1個與第2個元素的值D.輸出與給定值x相等的元素在線性表中的序號3 .如果最常用的操作是取第i個結點及其前驅，則采用【D】存儲方法最節(jié)省時間。A.單鏈表B.雙鏈表C.線性鏈表D.順序表4 .線性表是具有口個C的有限序列(n10)。A.表元素B.字符C.數(shù)據(jù)元素D.數(shù)據(jù)項5 .下面關于線性表的敘述中，錯誤的是BoA.線性表采用順序存儲，則必須占用一片連續(xù)的存儲單元B.線性表采用順序存儲，則便于插入和刪除操作C.線性表采用鏈式存儲，則不必占用一片連續(xù)的存儲單元D.線性表采用鏈式存儲，則便于插入和刪除操作6 .線性表的順序存儲結構是一種AoA.隨機存取的存儲結構

8、B.順序存取的存儲結構C.索引存取的存儲結構D.Hash存取的存儲結構7 .單鏈表中增加一個頭結點的目的是為了【CloA.使單鏈表至少有一個結點B.標識表首結點的位置C.方便運算的實現(xiàn)D.說明單鏈表是線性表的鏈式存儲8 .不帶頭結點的單鏈表（頭指針為h）為空的條件是AoA.h=NULLB.h-next=NULLC.h-next=hD.h!=NULL9 .帶頭結點的單鏈表（頭指針為h）為空的條件是BoA.h=NULLB.h-next=NULLC.h-next=hD.h!=NULL10 .帶頭結點的循環(huán)雙向鏈表（頭指針為L）為空的條件是DoA.L=NULLB.L-next-prior=NULLC.

9、L-prior=NULLD.L-next=L11 .非空的循環(huán)單鏈表（頭指針為head）的尾結點（由p指向）滿足【C】。A.p-next=NULLB.p=NULLC.p-next=headD.p=head12 .設一個鏈表最常用的操作是在末尾插入結點和刪除尾結點，則選用【A】最節(jié)省時間。A.帶頭結點的雙循環(huán)鏈表B.單循環(huán)鏈表C.帶尾指針的單循環(huán)鏈表D.單鏈表13 .若某線性表最常用的操作存取任意指定序號的元素和在表尾進行插入和刪除，則選用【A】的存儲方式最節(jié)省時間。A.順序表B.雙鏈表C.帶頭結點的雙循環(huán)鏈表D.單循環(huán)鏈表14 .在n個結點的線性表的順序實現(xiàn)中，算法的時間復雜度為O的操作是【A

10、loA.訪問第i個結點和求第i個結點的直接前驅B.在第i個結點后插入一個新結點C.刪除第i個結點D.以上都不對15 .若長度為n的線性表采用順序存儲結構，在第i個位置插入一個新元素的算法的時間復雜度為【C】。A.O(0)B.O(1)C.O(n)D.O(n2)16 .對于順序存儲的線性表，訪問結點和增加、刪除結點的時間復雜度為CoA.O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)17 .線性表以鏈式方式存儲，訪問第i個結點的時間復雜度為CoA.O(i)B.O(1)C.O(n)D.O(i-1)18 .循環(huán)鏈表H尾結點p的特點是AoA.p-next=HB.p-next=

11、H-nextC.p=HD.p=H-next二、判斷題x1.取線性表的第i個元素的時間同i的大小有關。X2.線性表中每個元素都有一個直接前驅和一個直接后繼。X3.順序存儲方式只能用于存儲線性結構。X4.線性表采用鏈式存儲時，結點和結點內部的存儲空間可以不連續(xù)。X5.在一個設有頭指針和尾指針的單鏈表中，執(zhí)行刪除單鏈表最后一個結點的操作與鏈表的長度無關。三、填空題1 .向一個長度為n的順序表中的第i個元素之前插入一個元素時，需要向后移動n-i+1個元素。2 .在一個長度為n的順序表中刪除第i個元素時，需要向前移動上L個元素3 .在單鏈表中設置頭結點的作用是簡化插入、刪除算法。4 .在單鏈中要刪除某一

12、指定結點,必須找到該結點的直接前驅結點。5 .訪問單鏈表中的結點，必須沿著指針域依次進行。6 .在雙鏈表中每個結點有兩個指針域，一個指向直接前驅結點，一個指向直接后繼結點。7 .在雙向循環(huán)鏈表中、刪除最后一個結點的算法時間復雜度為0(1)。8 .訪問一個線性表中具有給定值的時間復雜度的數(shù)量級是0(n)。9 .由n個數(shù)據(jù)元素生成一個順序表，若每次都調用插入算法把一個元素插入到表頭，則整個算法的時間復雜度為0(n)、若每次都調用插入算法把一個元素插入到表尾，則整個算法的時間復雜度為0(n2)。10 .在雙向鏈表中、可以用表尾指針代替表頭指針。11 .根據(jù)n個數(shù)據(jù)元素建立對應的順序表和單鏈表存儲結構

13、，其算法的時間復雜度最好的情況是0(n)、最壞的情況是0(n2)。12 .求線性表的順序存儲和鏈式存儲的長度的算法時間復雜度分別是_0W和0(n)。13 .在一個帶頭結點的單鏈表中，在表頭插入或刪除與在其他位置插入或刪除，其操作過程是否相同？相同。14 .在一個不帶頭結點的單鏈表中，在表頭插入或刪除與在其他位置插入或刪除，其操作過程是否相同？不相同。四、簡答題15 闡述順序表和鏈表存儲方式的特點。答：順序表存儲方式為數(shù)據(jù)分配連續(xù)的存儲單元，數(shù)據(jù)元素按邏輯順序依次存儲到相應存儲單元中，使得邏輯相鄰的數(shù)據(jù)元素物理也相鄰，因此可以實現(xiàn)隨機訪問線性表的數(shù)據(jù)元素，即數(shù)據(jù)訪問的時間復雜度為0(1)。鏈表存

14、儲方式分配的存儲單元可以不連續(xù)，通過每個結點的指針域來表示數(shù)據(jù)元素之間的邏輯關系，只能順序訪問線性表中的數(shù)據(jù)元素。16 若頻繁地對一個線性表進行插入和刪除操作，則該線性表宜采用何種存儲結構，為什么？答：若頻繁地對一個線性表進行插入和刪除操作，則該線性表宜采用鏈式存儲結構。因為鏈式存儲結構在插入和刪除數(shù)據(jù)元素時不需要移動數(shù)據(jù)元素，只需要修改結點的指針域就可以改變數(shù)據(jù)元素之間的邏輯關系。17 在單鏈表、雙向循環(huán)鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結點，不知道頭指針，能否將結點p從相應的鏈表中刪除？若可以，時間復雜度各為多少。答：要實現(xiàn)刪除p結點的操作，必須找到其前驅結點，修改其指針域的值使其指

15、向p的后繼結點，以實現(xiàn)刪除結點p。單鏈表不行，因為不知道頭指針就無法找到結點p的前驅結點。雙向循環(huán)鏈表和單循環(huán)鏈表可以可以實現(xiàn)刪除p結點。單循環(huán)鏈表刪除p結點的時間復雜度為0(n),雙循環(huán)鏈表刪除P結點的時間復雜度為0(1)。18 對鏈表設置頭結點的作用是什么？答：對帶頭結點的鏈表，在表的任何結點之前插入結點或刪除任何位置的結點，所要做的都是修改前一個結點的指針域，因為在帶頭結點的鏈表中任何元素結點都有前驅結點。如果沒有頭結點，在首元結點前插入結點或刪除首元結點都要修改頭指針，其算法要比帶頭結點的算法復雜些。其次，帶頭結點的鏈表結構，初始化后的頭指針就固定了，除撤銷算法外，所有算法都不會修改頭

16、指針，可以減少出錯的可能性。五、算法設計題19 已知一個線性表用含頭結點的單鏈表做存儲結構，寫一個算法求單鏈表的長度。解：算法基本思想：從頭結點的下一個結點開發(fā)，遍歷單鏈表的每個結點，每遇到一個結點，結點計算器加1。intlistlenght(linklistL)intlength=0;P=L-next;while(p)length+;p=p-next;return(length);20 已知一個順序表L,其中的元素按值遞增有序排列，設計一個算法插入一個值為x的元素后保持該順序表仍然遞增有序，且空間復雜度為0(1)voidinsertsq(sqlistL,elemtypex)n=L.lengt

17、h-1;while(n=0<(x,L.elemn)L.elemn+1=L.elemn;n-;L.elemn+1=x;L.lenght+;return;)21 寫一個算法，從順序表中刪除值為x的所有元素voiddelallsq(Sqlist&L)inti=0,j=0;while(jnext=Q.rear。10 .如果棧的最大長度難以估計,最好使用鏈棧。四、簡答題1 .為什么說棧是一種后進先出表？答：因為棧是限定在表的一端進行插入和刪除操作，所以后入棧的數(shù)據(jù)元素總是先出棧，所以說棧是一種后進先出表。2 .對于一個棧，其輸入序列是A,B,C,試給出全部可能的輸出序列。答：可能的出棧序列是：ABC

18、、ACB、BAC、BCA、CBA。3 .何謂隊列上溢？何為假溢出現(xiàn)象？有哪些解決假溢出問題的方法，并分別闡述其工作原理。答：隊列上溢指在隊列的順序存儲分配中，所有單元中已有元素，再進行插入操作時稱為隊列上溢。假溢出指在隊列的順序存儲分配中，分配給隊列的存儲空間有存儲單元未被占用，但按照操作規(guī)則而使進隊的數(shù)據(jù)元素無法進隊的現(xiàn)象。解決假溢出問題的方法是在隊列的順序存儲分配中，分配給隊列的存儲空間可以循環(huán)使用，具進本原理是用表示隊頭和隊尾指針與分配給隊列的存儲空間長度進行取模運算。即：入隊操作：Q.rear=(Q.rear+1)%MSize出隊操作：Q.front=(Q.front+1)%MSize

19、4 .隊列可以用單循環(huán)鏈表來實現(xiàn)，故可以只設一個頭指針或只設一個尾指針，請分析用哪種方案最合適。答：使用循環(huán)鏈表來表示隊列，設置尾指針比較合適，因為入隊操作可以直接在尾結點后進行插入操作，出隊操作時可以根據(jù)尾指針很容易找到鏈表的頭結點，入隊出隊操作的算法時間復雜度均為0(1)。若只設頭指針，則出隊操作的算法時間復雜度為0(1),入隊操作的算法時間復雜度為0(n)。5 .簡述線性表、棧和隊列的異同？答：棧和隊列都是操作位置受限的線性表，即對插入和刪除操作的位置加以限制。棧是僅允許在表的一端進行插入和刪除操作的線性表，因而是后進先出表。隊列是允許在表的一端進行插入，在表的另一端進行刪除的線性表，因

20、而是先進先出表。線性表可以在任何位置進行插入和刪除操作。五、算法設計題1 .設計一個算法，利用棧和隊列的基本運算將指定棧中的元素順序逆轉。解：算法基本思想：先將棧中元素出棧運算移至隊列中，再將隊列中元素出隊列移至棧中。voidreverse(Stack&st)Queuesq；ElemTypex;InitQueue(sq)while(!StackEmpty(st)pop(st,x)EnQueue(sq,x);while(!QueueEmpty(sq)DeQueue(sq,x);Push(st,x);DestroyQueue(sq);2 .設計一個算法，利用棧的基本運算返回指定棧中棧底元素。解：先

21、將棧中元素依次移至另一個臨時棧中，最后一個元素即為棧底元素，設為x.。冉將臨時棧中元素移至原棧中，即恢復棧內容。ElemTypebottom(Stack&st)ElemTypex,y;Stacktmpst;InitStack(tmpst)while(!StackEmpty(st)pop(st,x)push(tmpst,x);while(!QueueStack(temst)pop(tmpst,y);/此時必須用另一個變量y,才能保留棧底元素在中Push(st,y);DestroyStack(tmpst);return(x);3 .設計一個算法，利用棧來實現(xiàn)帶頭結點的單鏈表h的逆序。解：算法基本思

22、想：將單鏈表結點依次放入鏈棧中，鏈棧本身就是一個單鏈表，即實現(xiàn)了原單鏈表的逆序。假設鏈棧不帶頭結點，再加上原來的頭結點，就完成了原單鏈表的逆序。Voidrevert(SNode*h)SNode*st=NULL,*p=h-next,q;While(p)q=p-next;p-next=st;st=p;p=q;h-next=st;第四章串一、單選題1 .用是任意有限個【D】。A.符號構成的集合B.符號構成的序列C.字符構成的集合D.字符構成的序列2 .用是一種特殊的線性表，其特殊性體現(xiàn)在BoA.可以順序存儲B.數(shù)據(jù)元素是一個字符C.數(shù)據(jù)元素可以使多個字符D.可以鏈接存儲3 .兩個用相等必有用長度相等

23、且【B】。A.用的各位置字符任意B.用中各位置字符均對應相等C.兩個用含有相同的字符D.兩個用所含字符任意4 .設有兩個用p和q,求q在p中首次出現(xiàn)的位置的運算稱著【B】。A.連接B.模式匹配C.求子用D.求用長二、填空1 .空用是長度為0的4。2 .一個用中任意連續(xù)字符組成的子序列稱為該串的子串。3 .設s=abcd”,貝執(zhí)行語句s2=Substr(s,2,2后，s2=bc。4 .空白串是由一個或多個空格字符組成的串，其長度等于其所包含的空格字符的個數(shù)。第五章數(shù)組一、單選題1.一維數(shù)組與線性表的區(qū)別是【A】。A.前者長度固定，后者長度可變B.后進長度固定，前者長度可變C.兩者長度均固定D.兩

24、者長度均可變2 .多維數(shù)組的數(shù)組元素之間的關系，【A】。A.是線性的B.是樹型的C.既是線性的，又是樹型的D.既不是線性的，也不是樹型的3 .設有數(shù)組A810,每個元素占3個存儲單元，存放該數(shù)組的存儲單元數(shù)為CoA.80B.100C.240D.2704 .設有數(shù)組A810,每個元素占3個存儲單元，首地址為SA,則元素口5的起始地址是【D】。A.SA+141B.SA+144C.SA+222D.SA+2255 .設有一個n*n的對稱矩陣，采用壓縮存儲，則存入內存的元素個數(shù)為CoA.n*nB.n*n/2C.n*(n+1)/2D.(n+1)2/26 .設A是一個n*n的對稱矩陣，壓縮存儲到一個一維數(shù)組

25、B0.n(n+1)/2-1中，則下三角部分元素ai,j在B中的位置是【A】。A.i(i-1)/2+j-1B.i(i-1)/2+jC.i(i+1)/2+j-1D.i(i+1)/2+j7 .稀疏矩陣一般的壓縮方法有兩種，即【CloA.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組和十字鏈表D.散列和十字鏈表8 .設有一個10*10的對稱矩陣A,以行主次序進行壓縮存儲，每個元素占一個存儲單元，a,i的地址是1,則A8,5的起始地址是【B】。A.13B.33C.18D.40二、解答題1.設數(shù)組A5080,其基地址為2000,每個元素占2個存儲單元，以行序位主序順序存儲，回答下列問題：(1)該數(shù)據(jù)組由多少

26、元素？(2)該數(shù)組占用多少存儲單元？(3)數(shù)組元素a3030的存儲地址是多少？答：(1)該數(shù)組有：50*80=4000個元素(2)該數(shù)組占用4000*4=8000個存儲單元(3)10c(30,30)=2000+(30*80+30)*2=2000+4860=6860第六章樹與二叉樹一、單選題1 .有關二叉樹下列說法正確的是【B】。A.二叉樹的度為2B.一棵二叉樹的度可以小于2C.一棵二叉樹至少有一個結點的度為2D.二叉樹中任何一個結點的度為22 .利用二叉鏈表存儲樹，則根結點的右指針是CoA.指向最左孩子B.指向最右孩子C.空D.非空3 .若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則

27、度為0的結點個數(shù)為【B】。A.9B.11C.15D.不確定4 .一棵二叉樹有1001個結點，其中葉結點的個數(shù)為【D】。A.250B.490C.254D不確定5 .一棵完全二叉樹有1001個結點，其中葉結點的個數(shù)為【D】。A.250B.500C.254D.以上答案均不對6 .一棵具有1025個結點的二叉樹的高h為1C】。A.11B.11C.11至1025之間D.10至1024之間7 .一棵124個葉結點的完全樹，最多具有B個結點。A.247B.248C.249D.2518 .一棵具有10個葉結點的二叉樹具有B度為2的結點。A.8B.9C.10D.119 .已知一棵完全二叉樹有625個結點，葉結點

28、的個數(shù)為CoA.311B.312C.313D其它10 .一棵具有n個結點的完全二叉樹的高h為AB0A.log2n+1B.log2n+1C.log2n+1D.log2n-111 .由8個權值構造一棵哈夫曼樹，該哈夫曼樹有A個結點A.15B.16C.17D.1412 .由3個結點可以構造【D】種不同的二叉樹。A.2B.3C.4D.513 .樹最適合用來表示【C】。A.有序數(shù)據(jù)元素B無序數(shù)據(jù)元素C.元素間具有分支層次關系的數(shù)據(jù)D.元素間無聯(lián)系的數(shù)據(jù)15 .某二叉樹的先序遍歷序列和后序便利序列正好相反，則該二叉樹一定是【A1oA.空或只有一個結點B.完全二叉樹C.二叉排序樹D.高度等于其結點數(shù)16 .

29、在一棵非空二叉樹的中序遍歷序列中，根結點的右邊【A】。A.只有右子樹上的所有結點B只有右子樹上的部分結點C.只有左子樹上的部分結點D只有左子樹上的所有結點17 .任何一棵二叉樹的葉子結點在先序、中序和后序遍歷序列中的相對次序AoA.不發(fā)生上改變B發(fā)生改變C.不能確定D.以上都不對18 .一棵滿二叉樹，m個葉結點，n個結點，深度為h,則【D】。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-119 .設n,m是二叉樹上的兩個結點，在中序遍歷時，n在m之前的條件是CoA.n在m右方B.n是m的祖先C.n在m左方D.n是m的子孫20.設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉

30、樹中包含的結點數(shù)最少為【B】。A.2hB.2h-1C.2h+1D.h+1二、判斷題x1.二叉樹是一般樹的特殊樹型。IV】2.樹與二叉樹是兩種不同的樹形結構?！綳】3.對于有n個結點的二叉樹，其高度為10g2n。V4.完全二叉樹中，若一個沒有左孩子，則它必定是葉結點。5.一棵具有n個結點的完全二叉樹，從上到下、從左到右用自然數(shù)對結點進行編號，結點為i的結點的左孩子的編號為2i(2ilchild=NULL&p-rchild=NULL。10 .二叉樹的先序序列和中序序列相等的條件是任何結點至多只有右子樹011 .有一棵如下圖所示的樹，回答下列問題：這棵樹的根結點是a。這棵樹的葉子結點是b,e,g,d

31、。結點c的度為2。這棵樹的深度是4。結點c的孩子結點是ef。結點c的雙親結點是a。這棵樹的度是。12 .樹與二叉樹的兩個主要差別是樹中結點的最大度沒有限制，二叉樹結點的最大度限定為2、樹的結點無左右之分，二叉樹的的結點有左右之分013 .樹中任一結點允許有0個或多個孩子個孩子結點,除根結點之外，其余結點有1個雙親結點。四、簡答題1.設有如下圖所示的二叉樹，給出其前序、中序和后序遍歷結果。答：前序序列：eadcbifghj中序序列：abcdiefhgj后序序列：bcidahjgfe2.給出下圖所示的樹的二叉樹表示。答：下圖為其樹的二叉樹表示3 .有一份電文共有5個字符：a,b,c,d,e它們出現(xiàn)

32、的頻率依次為4,7,5,2,9,構造對應的哈夫曼樹，求哈夫曼樹的帶權路徑長度和每個字符的哈夫曼編碼。字符編碼：a：011b:10c：00d:010e：114 .假設一棵二叉樹采用順序存儲結構，如下圖所示05101520eafdgcjhib回答些列問題：畫出二叉樹表示。寫出先序、中序和后序遍歷結果寫出結點c的雙親結點和左、右孩子結點畫出此二叉樹還原成森林的圖先序序列為：eadcbjfghi中序序列為：acbdjefhgi后序序列為：bcjdahigfe結點c的雙親結點是d,左孩子為b,無右孩子該二叉樹對應的森林為第七章圖一、單選題1 .在一個無向圖中，所有頂點的度數(shù)之和等于所有邊的【C】倍。A.

33、1/2B.1C.2D.42 .在一個有向圖中，所有頂點的入度數(shù)之和等于所有頂點的出度之和的【B】倍。A.1/2B.1C.2D.43 .一個有n個頂點的無向圖最多有C條邊。A.nB.n(n-1)C.n(n-1)/2D.2n4 .具有4個頂點的無向完全圖有A條邊。A.6B.12C.16D.205 .具有6個頂點的無向圖至少應有A)條邊才能確保是一個連通圖。A.5B.6C.7D.86 .一個有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是D0A.nB.(n-1)2C.(n-1)D.n27 .對某個無向圖的鄰接矩陣來說，AoA.第i行上的非0元素個數(shù)等于第i列上非0元素個數(shù)8 .矩陣中非0元素

34、個數(shù)等于圖中的邊數(shù)C.第i行、第i列上非0元素個數(shù)等于頂點vi的度數(shù)D.矩陣中非全0行的行數(shù)等于圖中的頂點數(shù)8.對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為【A；所有鄰接表中結點總數(shù)為Co A.nB.n+1C.n-1D.n2 A.e/2B.eC.2eD.n+e二、判斷題【X】1.n個頂點的無向圖至多有n(n-1)條邊。2.有向圖中，各頂點的入度之和等于各頂點的出度之和?！荆?.鄰接矩陣只存儲了邊的信息，沒有存儲頂點的信息?！綳】4.連通分量是無向圖的極小連通子圖?！綳】5.如果表示有向圖的鄰接矩陣是對稱的，則該有向圖一定是完全有向圖?！綳】6.如果表示圖的鄰接矩

35、陣是對稱的，則該圖一定是無向圖。VJ7.如果表示圖的鄰接矩陣不是對稱的，則該圖一定是有向圖。三、填空題1 .有n個頂點的無向圖最多有n(n-1)/2條邊。2 .具有n個頂點的強連通有向圖至少有_n一條邊。3 .具有n個頂點的有向圖最多有n(n-1)條邊。4 .一個圖的臨接矩陣表示法是唯一的.而鄰接表表示法是不唯一的。5 .具有10個頂點的無向圖，邊的總數(shù)最多為45。6 .在有n個頂點的有向圖中，每個頂點的度最大可達n-1。7 .已知一個有向圖采用鄰接矩陣表示，計算第i個頂點的入度的方法是求第i列非0元素個數(shù)。8 .已知一個有向圖的鄰接矩陣表示，刪除所有從第i個結點出發(fā)的弧的方法是將第i行對應的

36、1置成0。9 .對于n的頂點的無向圖，采用鄰接矩陣表示，求圖中邊的方法是計算鄰接矩陣中元素值為1的個數(shù),判斷任意兩個頂點是否有邊相連的方法是判斷對應鄰接矩陣元素的值是否為1,再除以2,求任意頂點的度的方法是求鄰接矩陣中對應頂點所在行值為1的元素個數(shù)。10 .對于n的頂點的有向圖，采用鄰接矩陣表示，求圖中邊的方法是計算鄰接矩陣中元素值為1的個數(shù),判斷任意兩個頂點是否有邊相連的方法是判斷對應鄰接矩陣元素的值是否為1,求任意頂點的度的方法是求鄰接矩陣中對應頂點所在行和列的元素值為1的個數(shù)。11 .無向圖的連通分量指無向圖中最大連通子圖。12 .若無向圖有m條邊，則表示該無向圖的鄰接表中有2m結點。四

37、、簡答題1 .從占用的存儲空間來看，對于稠密圖和稀疏圖，采用鄰接矩陣和鄰接表那個更好些？答：從占用存儲空間看，稠密圖采用鄰接矩陣更好，稀疏圖采用鄰接表更好。2 .用鄰接矩陣表示圖時，矩陣元素的個數(shù)與頂點個數(shù)是否相關？與邊的條數(shù)是否相關？為什么？。答：用鄰接矩陣表示圖，矩陣元素的個數(shù)與圖的頂點個數(shù)直接相關，與邊的條數(shù)無關。因為假設定點個數(shù)為n,則鄰接矩陣的大小為n20第九章查找一、單選題1 .順序查找法適合于存儲結構為【B】的查找表。A.散列存儲B.順序存儲或鏈式存儲C.壓縮存儲D.索引存儲2 .對查找表進行折半查找時，要求查找表必須【B】。A.以順序方式存儲B.以順序方式存儲，且結點按關鍵字有

38、序排列C.以鏈式方式存儲D.以鏈式方式存儲，且結點按關鍵字有序排列3.采用順序查找法查找長度為n的查找表時，每個元素查找的平均查找長度為C oA.nB.n/2C.(n+1)/2D.(n-1)/24.采用折半查找法查找長度為n的查找表時，每個元素查找的平均查找長度為D 0A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)5 .采用分塊查找時，若查找表中有625個元素，查找每個元素的概率相同，假設對索引表和塊都采用順序查找，每塊應分B個結點最佳。A.10B.25C.6D.6256 .查找n個元素的有序表時，最有效的查找方法是【C】。A.順序查找B.分塊查找C.折半查找D.二叉排序

39、樹7 .如果要求一個查找表既能快速查找，又能適應動態(tài)變化的要求，可以采用A查找方法。A.分塊B.順序C.折半D.散列8 .在關鍵字隨機分布的情況下，用二叉排序樹的方法進行查找，其查找長度與B量級相當。A.順序查找B.折半查找C.分塊查找D.前三個都不正確9 .查找效率最高的二叉排序樹是【C】。A.所有結點的左子樹都為空的二叉排序樹B.所有結點的右子樹都為空的二叉排序樹C.平衡二叉樹D.沒有左子樹的二叉排序樹10 .假定有k個關鍵字互為同義詞，若用線性探測再散列法把這k個關鍵字的紀錄插入到散列表中，至少要進行D次探測。A.k-1B.kC.k+1D.k(k+1)/211 .以下說法錯誤的是【BA.

40、散列法存儲的基本思想是由記錄關鍵字決定數(shù)據(jù)存儲地址B.散列法的結點中只包含數(shù)據(jù)元素自身的信息，不包含任何指針C.裝填因子是散列法的一個重要參數(shù)，它反映了散列表的裝填程度D.散列表的查找效率取決于散列造表是的散列函數(shù)和沖突處理的方法12 .散列表的平均查找長度【A】。A.與沖突處理方法有關而與表的長度無關B.與沖突處理方法無關而與表的長度有關C.與沖突處理方法有關且與表的長度有關D.與沖突處理方法無關且與表的長度無關二、判斷題V1.順序查找法適合于順序或鏈式存儲結構的查找表?！綳】2.順序查找法只能在順序存儲結構上進行。【X】3.二分查找可以在有序的雙向鏈表上進行?！綳】4.在二叉排序樹中，每個

41、結點的關鍵字比左孩子的關鍵字大，比右孩子的關鍵字小。【X】5.每個結點的關鍵字都比左孩子的關鍵字大，比右孩子的關鍵字小，這樣的二叉樹都是二叉排序樹。【V6.哈希存儲法只能存儲數(shù)據(jù)元素的值，不能存儲數(shù)據(jù)元素之間的關系?！綳】7.哈希沖突是指同一個關鍵字對應多個不同的哈希地址。三、填空題1 .順序查找含n個元素的順序表，若查找成功，則比較關鍵字的次數(shù)最多為_次;若查找不成功，則比較關鍵字的次數(shù)為n+1次。2 .在含有n個元素的有序順序表中進行二分查找，最大的比較次數(shù)星.log2n+1。3 .用二分查找一個查找表，該查找表必須具有的特點是順序存儲且關鍵字有ff。4 .分塊查找發(fā)將待查找的表均勻地分成

42、若干塊且塊中諸記錄的順序可以是任意的，但塊與塊之間關鍵享有序。5 .在分塊查找方法中，首先查找關鍵字表，然后再查找相應的對應的6 。6 .用二叉排序樹在n個元素中進行查找，最壞情況下查找時間復雜度為O(n),最好情況的查找時間復雜度為O(log2n)。7 .折半查找的存儲結構僅限于順序存儲結構，且是關鍵字有序排。8 .一個無序序列可以通過構造一棵二叉排序樹而變成有序序列,構造樹的過程即是對無序序列進行排序的過程。9 .用二叉排序樹查找，在最壞的情況下，平均查找長度為(n+1)/2,最好的情況下，平均查找長度為.(log2n+1)-1o10 .在哈希函數(shù)H(key)=key/p中，p最好取小于或

43、等于m的最大質數(shù)。11 .哈希表是通過將關鍵字按選定的哈希函數(shù)和沖突處理方法，把記錄按關鍵字轉換為地址進行存儲的存儲表，哈希方法的關鍵是選擇好的哈希函數(shù)和沖突處理的方法。一個好的哈希函數(shù)其轉換地址應盡可能均勻,而且函數(shù)運算應盡可能簡單。四、解答題1、畫出對長度為10的右序表進行折半查找的一棵判定樹，并求其等概率時查找成功的平均查找長度。平均查找長度=(1+2*2+4*3+3*4)/10=2.92、設有數(shù)據(jù)集合d=1,12,5,8,3,10,7,13,9,回答下列問題:依次取d中各數(shù)據(jù)，構造一棵二叉排序樹bt;如何依據(jù)此二叉排序樹得到d的一個有序序列。答：構造的二叉排序樹如下圖所示。對該二叉排序樹進行中序遍歷，就可以得到d的一個有序序列:1,3,5,7,8,9,10,12,133.若對具有n個元素的有序的順序表和無序的順序表分別