數據結構題集答案

數據結構題集第一章緒論一、 單選題在數據結構中，從邏輯上可以把數據結構分成【C】。動態(tài)結構和靜態(tài)結構B.緊湊結構和非緊湊結構C.線性結構和非線性結構D.內部結構和外部結構數據結構在計算機內存中的表示是指【A】。數據的存儲結構 B.數據結構C.數據結構的邏輯結構 D.數據元素之間的關系【A】是數據的最小單位，【B】是數據的基本單位。數據項 B.數據元素C.信息項 D.表元素計算機所處理數據一般具有某種內在聯(lián)系，這是指【B】。數據與數據之間存在某種關系 B.數據元素與數據元素之間存在某種關系C.元素內部存在某種結構 D.數據項與數據項之間存在某種關系算法分析的目的是【C】。找出數據結構的合理性B.研究輸入和輸出的關系C.分析算法的效率以求改進D.分析算法的易懂性在存儲數據時，不僅要考慮存儲各數據元素的值，而且還要存儲【C】。A.數據處理的方法 B.數據元素的類型C.數據元素之間的關系 D.數據的存儲方法算法分析的主要任務是分析【D】。算法是否具有較好的可讀性算法中是否存儲語法錯誤和邏輯錯誤算法的功能是否符合設計要求算法的執(zhí)行時間與問題規(guī)模之間的關系。數據的運算【A】。效率與采用何種存儲結構有關是根據存儲結構來定義的有算術運算和關系運算兩大類必須用程序設計語言來描述算法的計算量的大小稱為算法的【B】。A.效率 B.時間復雜度 C.現(xiàn)實性D.難度連續(xù)存儲分配時，存儲單元的地址【A】。A.一定連續(xù) B.一定不連續(xù)C.不一定連續(xù)D.部分連續(xù)，部分不連續(xù)二、 判斷題數據元素是數據結構的最小單位【.X】。數據的邏輯結構說明數據元素之間的順序關系，它依賴于計算機的存儲結構【X.】。數據的邏輯結構指數據元素的各數據項之間的邏輯關系【X.】。算法的優(yōu)劣與算法的描述語言無關，但與使用的計算機有關【.X】。數據結構的抽象操作的定義與具體實現(xiàn)有關【.X】。三、 填空題數據的邏輯結構指 。一個數據結構在計算機中的表示 稱為存儲結構。數據的物理結構主要包括順序存儲結構的表示和鏈式存儲結構 的表示。數據邏輯結構包括集合、線性結構、樹和圖 四種，樹結構和圖結構統(tǒng)稱為 。順序存儲方法把邏輯匕邏輯上相鄰的元素存儲在物理位置相鄰的存儲單元里；鏈式存儲方法中結點間的邏輯關系是由指針域 表示的。數據結構研究的是邏輯結構 和物理結構 以及它們之間的相互關系，并對于這種結構定義相應的運算 ，設計出相應的。算法的執(zhí)行時間是問題規(guī)模n的函數。以下是4個算法所有語句頻度之和的表達式，其中的復雜度相同的是A和B。TA(n)=2n3+3n2+1000 B.TB(n)=n3-n2log2n-1000C.TC(n)=n2log2n+n2 D.TD(n)=n2+1000四、 解答題簡述數據的邏輯結構和存儲結構的關系。答：在數據結構中，邏輯結構和存儲結構是密切相關的，存儲結構不僅將數據元素存儲到計算機中，而且還要表示各數據元素之間的邏輯關系。邏輯結構與計算機無關，存儲結構是數據元素之間的關系在計算機中的表示。通常情況下，一種邏輯結構可以有多種存儲結構，例如，線性結構可以采取順序存儲結構或鏈式存粗結構表示。數據結構和數據類型有什么區(qū)別？答：數據結構是相互間存在一種或多種特定關系的數據元素的集合，一般包括三個方面的內容：數據的邏輯結構、存儲結構和多數據的運算。數據類型是一個值得集合和定義在這個值集上的一組操作的總稱。數據結構重點考慮元素之間的關系，數據類型重點考慮數據的個體特征。當為解決某一問題已經選定其數據的邏輯結構后，選擇數據的存儲結構時，應從哪些方面考慮？答：通常從兩個方面考慮：第一是算法實現(xiàn)的存儲空間復雜度；第二是算法執(zhí)行的時間復雜度。若存儲空間難以確定，宜選擇鏈式存儲結構，否則選擇順序存儲結構。若插入、刪除操作頻繁，則選鏈式存儲結構，否則選擇順序存儲結構。第二章線性表一、單選題鏈表不具備的特點是【A】?？呻S機訪問任一結點 8.插入刪除不需要移動元素C.不必事先估算存儲空間D.所需空間與其長度成正比設線性表有n個元素，以下操作中，【A】在順序表上實現(xiàn)比在鏈表上實現(xiàn)效率更高。輸出第i（IWiWn）個元素的值順序輸出這n個元素交換第1個與第2個元素的值輸出與給定值x相等的元素在線性表中的序號如果最常用的操作是取第i個結點及其前驅，則采用【D】存儲方法最節(jié)省時間。A.單鏈表 8.雙鏈表 C.線性鏈表D.順序表線性表是具有n個【C】的有限序列（nN0）。A.表元素 B.字符C.數據元素D.數據項下面關于線性表的敘述中，錯誤的是【B】。線性表采用順序存儲，則必須占用一片連續(xù)的存儲單元線性表采用順序存儲，則便于插入和刪除操作線性表采用鏈式存儲，則不必占用一片連續(xù)的存儲單元線性表采用鏈式存儲，則便于插入和刪除操作線性表的順序存儲結構是一種【A】。A.隨機存取的存儲結構B.順序存取的存儲結構C.索引存取的存儲結構D.Hash存取的存儲結構單鏈表中增加一個頭結點的目的是為了【C】。A.使單鏈表至少有一個結點 B.標識表首結點的位置方便運算的實現(xiàn)說明單鏈表是線性表的鏈式存儲不帶頭結點的單鏈表（頭指針為h）為空的條件是【A】。A.h==NULLB.h->next==NULLC.h->next==hD.h!=NULL帶頭結點的單鏈表（頭指針為h）為空的條件是【B】。A.h==NULLB.h->next==NULLC.h->next==hD.h!=NULL帶頭結點的循環(huán)雙向鏈表（頭指針為L）為空的條件是【D】。A.L==NULL B.L->next->prior==NULLC.L->prior==NULL D.L->next==L非空的循環(huán)單鏈表（頭指針為head）的尾結點（由p指向）滿足【C】。A.p->next==NULLB.p==NULLC.p->next==headD.p==head設一個鏈表最常用的操作是在末尾插入結點和刪除尾結點，則選用【A】最節(jié)省時間。A.帶頭結點的雙循環(huán)鏈表B.單循環(huán)鏈表C.帶尾指針的單循環(huán)鏈表 D.單鏈表若某線性表最常用的操作存取任意指定序號的元素和在表尾進行插入和刪除，則選用【A】的存儲方式最節(jié)省時間。A.順序表 8.雙鏈表C.帶頭結點的雙循環(huán)鏈表 D.單循環(huán)鏈表在n個結點的線性表的順序實現(xiàn)中，算法的時間復雜度為0(1)的操作是【A】。訪問第i個結點和求第i個結點的直接前驅在第i個結點后插入一個新結點刪除第i個結點 D.以上都不對若長度為n的線性表采用順序存儲結構，在第i個位置插入一個新元素的算法的時間復雜度為【C】。A.O(0) B.0(1) C.0(n) D.0(n2)對于順序存儲的線性表，訪問結點和增加、刪除結點的時間復雜度為【C】。A.O(n)O(n)B.0(n)0(1) C.0(1)0(n) D.0(1)0(1)線性表以鏈式方式存儲，訪問第i個結點的時間復雜度為【C】。A.0(i) B.0(1) C.0(n) D.0(i-1)循環(huán)鏈表H尾結點p的特點是【A】。A.p->next==HB.p->next==H->nextC.p==H D.p==H->next二、 判斷題【X】1.取線性表的第i個元素的時間同i的大小有關?！綳】2.線性表中每個元素都有一個直接前驅和一個直接后繼?！綳】3.順序存儲方式只能用于存儲線性結構?！綳】4.線性表采用鏈式存儲時，結點和結點內部的存儲空間可以不連續(xù)?！綳】5.在一個設有頭指針和尾指針的單鏈表中，執(zhí)行刪除單鏈表最后一個結點的操作與鏈表的長度無關。三、 填空題向一個長度為n的順序表中的第i個元素之前插入一個元素時，需要向后移動_M+1個元素。在一個長度為n的順序表中刪除第i個元素時，需要向前移動n-i個元素。在單鏈表中設置頭結點的作用是簡化插入、刪除算法 。在單鏈中要刪除某一指定結點，必須找到該結點的直接前驅結點。訪問單鏈表中的結點，必須沿著指針域依次進行。在雙鏈表中每個結點有兩個指針域，一個指向直接前驅結點 ，一個指向直接后繼結點。在 —鏈表中，刪除最后一個結點的算法時間復雜度為0(1)。訪問一個線性表中具有給定值的時間復雜度的數量級。由n個數據元素生成一個順序表，若每次都調用插入算法把一個元素插入到表頭，則TOC\o"1-5"\h\z整個算法的時間復雜度為，若每次都調用插入算法把一個元素插入到表尾，則整個算法的時間復雜度為0(n2) 。在 鏈表中，可以用表尾指針代替表頭指針。根據n個數據元素建立對應的順序表和單鏈表存儲結構，其算法的時間復雜度最好的情況是 ，最壞的情況是 。求線性表的順序存儲和鏈式存儲的長度的算法時間復雜度分別是 0(1) 和0(n)。在一個帶頭結點的單鏈表中，在表頭插入或刪除與在其他位置插入或刪除，其操作過程是否相同？ 。在一個不帶頭結點的單鏈表中，在表頭插入或刪除與在其他位置插入或刪除，其操作過程是否相同？ 。四、 簡答題闡述順序表和鏈表存儲方式的特點。答：順序表存儲方式為數據分配連續(xù)的存儲單元，數據元素按邏輯順序依次存儲到相應存儲單元中，使得邏輯相鄰的數據元素物理也相鄰，因此可以實現(xiàn)隨機訪問線性表的數據元素，即數據訪問的時間復雜度為0(1)。鏈表存儲方式分配的存儲單元可以不連續(xù)，通過每個結點的指針域來表示數據元素之間的邏輯關系，只能順序訪問線性表中的數據元素。若頻繁地對一個線性表進行插入和刪除操作，則該線性表宜采用何種存儲結構，為什么？答：若頻繁地對一個線性表進行插入和刪除操作，則該線性表宜采用鏈式存儲結構。因為鏈式存儲結構在插入和刪除數據元素時不需要移動數據元素，只需要修改結點的指針域就可以改變數據元素之間的邏輯關系。在單鏈表、雙向循環(huán)鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結點，不知道頭指針，能否將結點p從相應的鏈表中刪除？若可以，時間復雜度各為多少。答：要實現(xiàn)刪除p結點的操作，必須找到其前驅結點，修改其指針域的值使其指向p的后繼結點，以實現(xiàn)刪除結點p。單鏈表不行，因為不知道頭指針就無法找到結點p的前驅結點。雙向循環(huán)鏈表和單循環(huán)鏈表可以可以實現(xiàn)刪除p結點。單循環(huán)鏈表刪除p結點的時間復雜度為0(n)，雙循環(huán)鏈表刪除P結點的時間復雜度為0(1)。對鏈表設置頭結點的作用是什么？答：對帶頭結點的鏈表，在表的任何結點之前插入結點或刪除任何位置的結點，所要做的都是修改前一個結點的指針域，因為在帶頭結點的鏈表中任何元素結點都有前驅結點。如果沒有頭結點，在首元結點前插入結點或刪除首元結點都要修改頭指針，其算法要比帶頭結點的算法復雜些。其次，帶頭結點的鏈表結構，初始化后的頭指針就固定了，除撤銷算法外，所有算法都不會修改頭指針，可以減少出錯的可能性。五、 算法設計題已知一個線性表用含頭結點的單鏈表做存儲結構，寫一個算法求單鏈表的長度。解：算法基本思想：從頭結點的下一個結點開發(fā)，遍歷單鏈表的每個結點，每遇到一個結點，結點計算器加1。intlistlenght(linklistL)(intlength=0;P=L->next;while(p)(length++;p=p->next;}return(length);}已知一個順序表L，其中的元素按值遞增有序排列，設計一個算法插入一個值為x的元素后保持該順序表仍然遞增有序，且空間復雜度為0(1)。voidinsertsq(sqlistL,elemtypex)(n=L.length-1;while(n>=0&<(x,L.elem[n])(L.elem[n+1]=L.elem[n];n--;}L.elem[n+1]=x;}L.lenght++;return;}寫一個算法，從順序表中刪除值為x的所有元素。voiddelallsq(Sqlist&L)(inti=0,j=0;while(j<L.length)(if(L.elem[j]!=x)L.elem[i++]=L.elem[j];j++;}L.longth=i;}第三章棧和隊列一、單選題對于棧操作數據的原則是【C】。A.先進先出 B.后進后出C.后進先出 D.不分順序隊列的先進先出特征是指【A】。最后插入隊列的元素總是最后被刪除當同時進行插入、刪除操作時，總是插入操作優(yōu)先每當有刪除操作時，總要先做一次插入操作每次從隊中刪除的元素總是最早插入的元素與順序棧相比較，鏈棧有一個比較明顯的優(yōu)勢是【A】。A.通常不會出現(xiàn)棧滿的情況8.插入操作更容易實現(xiàn)C.通常不會出現(xiàn)?？盏那闆rD.刪除操作更容易實現(xiàn)棧和隊列的共同點是【C】。A.都是先進先出 B.都是后進后出C.只允許在端點處進行插入和刪除D.無共同點棧的特點是【①B】，隊列的特點是【②A】；棧和隊列都是【③C】若入棧序列是1，2,3,4，則【④A】是不可能的出棧序列；若進隊列的序列是1，2,3,4,則【⑤D】是可能的出隊序列。①②A.先進先出B.后進先出C.進優(yōu)先于出D.出優(yōu)先于進③A.順序存儲的線性結構 B.鏈式存儲的線性結構C.限制存取點的線性結構D.限制存取點的非線性結構④⑤A.3,2,1,4B.3,2,4,1C.4,2,3,1 D.1,2,3,4用單鏈表表示的鏈隊列的隊頭在鏈表的【A】。A.鏈頭B.鏈尾 C.鏈中 D.都不是設入棧序列為1,2,3,4,5,則可能得到的出棧序列為【C】。A.1,2,5,3,4B.3,1,2,5,4C.3,2,5,4,1D.1,4,2,3,5輸入序列是ABC，若輸出序列變?yōu)镃BA，經過的棧操作為【B】。push,pop,push,pop,push,poppush,push,push,pop,pop,poppush,push,pop,pop,push,poppush,pop,push,push,pop,pop棧在【D】應用。A.遞歸調用 B.函數調用C.表達式求值D.A,B,C設計一個判別表達式中左、右括號是否配對的算法，采用【D】數據結構最佳。A.線性表的順序存儲結構 B.隊列C.線性表的鏈式存儲結構 D.棧允許對隊列進行的操作有【D】。A.對隊列中的元素排序B.取出最近進隊的元素C.在隊頭之前插入元素D.刪除隊頭元素對于循環(huán)隊列【D】。無法判斷隊列是否為空 B.無法判斷隊列是否為滿C.隊列不可能滿 D.以上說法都不對隊列存放在A[0..M-1]中，則入隊時的操作為【B】。A.rear=rear+1 B.rear=(rear+1)%MC.rear=(rear+1)%(M+1)D.rear=(rear+1)%(M-1)隊列存放在A[0..M-1]中，則出隊時的操作為【B】。A.front=front+1 B.front=(front+1)%MC.front=(front+1)%(M+1)D.front=(front+1)%(M-1)循環(huán)隊列的最大容量為M，則隊空的條件是【A】。A.rear==front B.(rear+1)%M==frontC.rear+1==front D.(rear-1)%M==front循環(huán)隊列的最大容量為M，則隊滿的條件是【B】。A.rear==front B.(rear+1)%M==frontC.rear+1==front D.(rear-1)%M==front二、判斷題【X】1.隊列在函數調用時必不可少，因此遞歸離不開隊列?！尽薄?.棧和隊列的存儲方式，既可以是順序方式，又可以是鏈式方式?！尽薄?.設尾指針的循環(huán)鏈表表示隊列，則入隊和出隊算法的時間復雜度為0(1)?！綳】4.隊列邏輯上是一個上端和下端既能增加又能減少的線性表?！?】5.在鏈隊列中，即使不設置尾指針也能進行入隊操作?！尽薄?.棧和隊列度是限制存取點的線性結構。【X】7.即使對不含相同元素的同一輸入序列進行兩組不同的合法的入棧和出棧操作，所得的輸出序列一定相同?！尽薄?.棧是實現(xiàn)函數調用所必需的數據結構。【”】9.順序隊列中的元素個數，可以根據隊首指針和隊尾指針的值計算出來。三、 填空題TOC\o"1-5"\h\z循環(huán)隊列的引入，目的是為了克月 。區(qū)分循環(huán)隊列的空與滿有3種方法，它們是少用一個元素、設空滿標志、用計數器記錄隊列中元素個數 。棧和隊列的區(qū)別是棧只能在表一端進行插入和刪除操作，隊列限制在表的一端進行插入操作，在另一端進行刪除操作 。一個棧的輸入序列是12345,則棧的輸出序列43512是 。設棧采取順序存儲結構，棧中已有i-1個元素，則第i個元素進棧操作的算法時間復雜度是O(1) 。若用不帶頭結點的單鏈表表示棧，則創(chuàng)建一個空棧要執(zhí)行的操作 —。從循環(huán)隊列中刪除一個元素的操作是 。從循環(huán)隊列中插入一個元素的操作是 。判斷鏈隊列中只有一個結點的條件是 。如果棧的最大長度難以估計，最好使用鏈棧。四、 簡答題為什么說棧是一種后進先出表？答：因為棧是限定在表的一端進行插入和刪除操作，所以后入棧的數據元素總是先出棧，所以說棧是一種后進先出表。對于一個棧，其輸入序列是A,B,C,試給出全部可能的輸出序列。答：可能的出棧序列是：ABC、ACB、BAC、BCA、CBA。何謂隊列上溢？何為假溢出現(xiàn)象？有哪些解決假溢出問題的方法，并分別闡述其工作原理。答：隊列上溢指在隊列的順序存儲分配中，所有單元中已有元素，再進行插入操作時稱為隊列上溢。假溢出指在隊列的順序存儲分配中，分配給隊列的存儲空間有存儲單元未被占用，但按照操作規(guī)則而使進隊的數據元素無法進隊的現(xiàn)象。解決假溢出問題的方法是在隊列的順序存儲分配中，分配給隊列的存儲空間可以循環(huán)使用，其進本原理是用表示隊頭和隊尾指針與分配給隊列的存儲空間長度進行取模運算。即:入隊操作：Q.rear=(Q.rear+1)%MSize出隊操作：Q.front=(Q.front+1)%MSize隊列可以用單循環(huán)鏈表來實現(xiàn)，故可以只設一個頭指針或只設一個尾指針，請分析用哪種方案最合適。答：使用循環(huán)鏈表來表示隊列，設置尾指針比較合適，因為入隊操作可以直接在尾結點后進行插入操作，出隊操作時可以根據尾指針很容易找到鏈表的頭結點，入隊出隊操作的算法時間復雜度均為O(1)。若只設頭指針，則出隊操作的算法時間復雜度為O(1)，入隊操作的算法時間復雜度為O(n)。簡述線性表、棧和隊列的異同？答：棧和隊列都是操作位置受限的線性表，即對插入和刪除操作的位置加以限制。棧是僅允許在表的一端進行插入和刪除操作的線性表，因而是后進先出表。隊列是允許在表的一端進行插入，在表的另一端進行刪除的線性表，因而是先進先出表。線性表可以在任何位置進行插入和刪除操作。五、算法設計題設計一個算法，利用棧和隊列的基本運算將指定棧中的元素順序逆轉。解：算法基本思想：先將棧中元素出棧運算移至隊列中，再將隊列中元素出隊列移至棧中。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);}設計一個算法，利用棧的基本運算返回指定棧中棧底元素。解：先將棧中元素依次移至另一個臨時棧中，最后一個元素即為棧底元素，設為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，才能保留棧底元素在x中Push(st,y);}DestroyStack(tmpst);return(x);}設計一個算法，利用棧來實現(xiàn)帶頭結點的單鏈表h的逆序。解：算法基本思想：將單鏈表結點依次放入鏈棧中，鏈棧本身就是一個單鏈表，即實現(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;}第四章串一、 單選題串是任意有限個【D】。A.符號構成的集合 B.符號構成的序列C.字符構成的集合 D.字符構成的序列串是一種特殊的線性表，其特殊性體現(xiàn)在【B】。A.可以順序存儲 B.數據元素是一個字符C.數據元素可以使多個字符 D.可以鏈接存儲兩個串相等必有串長度相等且【B】。A.串的各位置字符任意 B.串中各位置字符均對應相等C.兩個串含有相同的字符 D.兩個串所含字符任意設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱著【B】。A.連接 B.模式匹配C.求子串 D.求串長二、 填空空串是 。一個串中 任意連續(xù)字符組成的子序列 稱為該串的子串。設s="abcd”，則執(zhí)行語句s2=Substr(s,2,2)后，s2= “bc”?？瞻状怯梢粋€或多個空格字符組成的串 ，其長度等于其所包含的空格字符的個數。第五章數組一、 單選題一維數組與線性表的區(qū)別是【A】。前者長度固定，后者長度可變后進長度固定，前者長度可變兩者長度均固定 D.兩者長度均可變多維數組的數組元素之間的關系，【A】。A.是線性的B.是樹型的既是線性的，又是樹型的既不是線性的，也不是樹型的設有數組A[8][10]，每個元素占3個存儲單元，存放該數組的存儲單元數為【C】。A,80B.100C.240D.270設有數組A[8][10]，每個元素占3個存儲單元，首地址為SA，則元素[7][5]的起始地址是【D】。A.SA+141 B.SA+144 C.SA+222D.SA+225設有一個n*n的對稱矩陣，采用壓縮存儲，則存入內存的元素個數為【C】。A.n*nB.n*n/2 C.n*(n+1)/2 D,(n+1)2/2設A是一個n*n的對稱矩陣，壓縮存儲到一個一維數組B[0..n(n+1)/2-1]中，則下三角部分元素ai,j在B中的位置是【A】。A.i(i-1)/2+j-1 B.i(i-1)/2+jC.i(i+1)/2+j-1 D.i(i+1)/2+j稀疏矩陣一般的壓縮方法有兩種，即【C】。A.二維數組和三維數組B.三元組和散列C.三元組和十字鏈表 D.散列和十字鏈表設有一個10*10的對稱矩陣A，以行主次序進行壓縮存儲，每個元素占一個存儲單元，a11的地址是1，則A8,5的起始地址是【B】。 ’A.13 B.33 C.18 D.40二、 解答題1.設數組A[50][80]，其基地址為2000，每個元素占2個存儲單元，以行序位主序順序存儲，回答下列問題：該數據組由多少元素？該數組占用多少存儲單元？數組元素a[30][30]的存儲地址是多少？答：該數組有：50*80=4000個元素該數組占用4000*4=8000個存儲單元loc(30,30)=2000+(30*80+30)*2=2000+4860=6860第六章樹與二叉樹一、單選題有關二叉樹下列說法正確的是【B】。A.二叉樹的度為2 B.一棵二叉樹的度可以小于2C.一棵二叉樹至少有一個結點的度為2 D.二叉樹中任何一個結點的度為2利用二叉鏈表存儲樹，則根結點的右指針是【C】。A.指向最左孩子 B.指向最右孩子C.空 D.非空若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點個數為【B】。TOC\o"1-5"\h\zA.9 B.11C.15 D.不確定一棵二叉樹有1001個結點，其中葉結點的個數為【D】。A.250 B.490C.254 D.不確定一棵完全二叉樹有1001個結點，其中葉結點的個數為【D】。A.250 B.500C.254 D.以上答案均不對一棵具有1025個結點的二叉樹的高h為【C】。A.11 B.11C.11至1025之間D.10至1024之間一棵124個葉結點的完全樹，最多具有【B】個結點。A.247 B.248C.249 D.251一棵具有10個葉結點的二叉樹具有【B】度為2的結點。A.8 B.9C.10 D.11已知一棵完全二叉樹有625個結點，葉結點的個數為【C】。A.311 B.312C.313 D.其它一棵具有n個結點的完全二叉樹的高h為【AB】。A.Llog2n」+1 B.「log2n+1]C.log2n+1 D.log2n-1由8個權值構造一棵哈夫曼樹，該哈夫曼樹有【A】個結點。TOC\o"1-5"\h\zA.15 B.16C.17 D.14由3個結點可以構造【D】種不同的二叉樹。A.2 B.3C.4 D.5樹最適合用來表示【C】。A.有序數據元素 B.無序數據元素C.元素間具有分支層次關系的數據 D.元素間無聯(lián)系的數據下圖中4棵二叉樹中，【C】不是完全二叉樹。A. B. C. D.某二叉樹的先序遍歷序列和后序便利序列正好相反，則該二叉樹一定是【A】。A.空或只有一個結點 B.完全二叉樹C.二叉排序樹 D.高度等于其結點數在一棵非空二叉樹的中序遍歷序列中，根結點的右邊【A】。A.只有右子樹上的所有結點 B.只有右子樹上的部分結點C.只有左子樹上的部分結點 D.只有左子樹上的所有結點任何一棵二叉樹的葉子結點在先序、中序和后序遍歷序列中的相對次序【A】。A.不發(fā)生上改變 B.發(fā)生改變C.不能確定 D.以上都不對一棵滿二叉樹，m個葉結點，n個結點，深度為^則【D】。A.n=h+m B.h+m=2nC.m=h-1 D.n=2h-1設n，m是二叉樹上的兩個結點，在中序遍歷時，n在m之前的條件是【C】。A.n在m右方 B.n是m的祖先C.n在m左方 D.n是m的子孫設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中包含的結點數最少為【B】。A.2h B.2h-1 C.2h+1 D.h+1二、 判斷題【X】1.二叉樹是一般樹的特殊樹型?！尽薄?.樹與二叉樹是兩種不同的樹形結構?！綳】3.對于有n個結點的二叉樹，其高度為log2n?！尽薄?.完全二叉樹中，若一個沒有左孩子，則它必定是葉結點?！尽薄?.一棵具有n個結點的完全二叉樹，從上到下、從左到右用自然數對結點進行編號，結點為i的結點的左孩子的編號為2i(2i<n)?！綳】6.一棵樹中的葉結點數一定等于與其對應的二叉樹的葉結點數?！尽薄?.哈夫曼樹是帶權路徑長度最短的樹，路經上權值較大的結點離根最近?！尽薄?.哈夫曼樹的結點個數不偶數。三、 填空題深度為k的完全二叉樹至少有 個結點，至多有個結點。在一棵二叉樹中，度為0的結點個數為n0，度為2的結點個數為n2,則有n0=n2+1 。一棵二叉樹第i層最多有2i-1 個結點，一棵有n個結點的滿二叉樹共有31個結點，共有2K-1 個葉結點。根據二叉樹的定義，具有3個結點的二叉樹共有 5 種不同形態(tài)，它們分別是.

TOC\o"1-5"\h\z在在一棵完全二叉樹中，編號i和j的兩個結點處于同一層的條件是」logi==JlogjI o^2 ^2具有n個結點的二叉樹采用二叉鏈表存儲結構，共有 個空指針域。具有n個結點的二叉樹中，如果有m個葉結點，則一定有m-1個度為2的結點，有 一個度為1的結點。在二叉樹的鏈式存儲結構中，指針p所指結點為葉結點的條件是p->lchild=NULL&&p->rchild==NULL。TOC\o"1-5"\h\z二叉樹的先序序列和中序序列相等的條件是任何結點至多只有右子樹 。有一棵如下圖所示的樹，回答下列問題：這棵樹的根結點是 a。這棵樹的葉子結點是 。結點c的度為—2 o這棵樹的深度是 4 。結點c的孩子結點是e,f。結點c的雙親結點是 a。這棵樹的度是 。樹中結點的最大度沒有限制，二叉樹結點的最大樹與二叉樹的兩個主要差別是度限定為2、樹的結點無左右之分，二叉樹的的結點有左右之分。樹中結點的最大度沒有限制，二叉樹結點的最大樹中任一結點允許有0個或多個孩子個孩子結點，除根結點之外，其余結點有1個雙親結點。四、簡答題設有如下圖所示的二叉樹，給出其前序、中序和后序遍歷結果。答：前序序列：eadcbifghj中序序列：abcdiefhgj后序序列：bcidahjgfe2.給出下圖所示的樹的二叉樹表示。答：下圖為其樹的二叉樹表示。3.有一份電文共有5個字符：a,b,c,d,e,它們出現(xiàn)的頻率依次為4,7,5,2,9,構造對應的哈夫曼樹，求哈夫曼樹的帶權路徑長度和每個字符的哈夫曼編碼。字符編碼：a：011b：10c：00d：010e：114.假設一棵二叉樹采用順序存儲結構，如下圖所示。0 5 10 15 20eafdgcjhib回答些列問題：①畫出二叉樹表示。

寫出先序、中序和后序遍歷結果寫出結點c的雙親結點和左、右孩子結點畫出此二叉樹還原成森林的圖答：①二叉樹表示如下圖所示。先序序列為：eadcbjfghi中序序列為：acbdjefhgi后序序列為：bcjdahigfe結點。的雙親結點是d，左孩子為b，無右孩子該二叉樹對應的森林為第七章圖一、 單選題在一個無向圖中，所有頂點的度數之和等于所有邊的【C】倍。TOC\o"1-5"\h\zA.1/2 B.1 C.2 D.4在一個有向圖中，所有頂點的入度數之和等于所有頂點的出度之和的【B】倍。A.1/2 B.1 C.2 D.4一個有n個頂點的無向圖最多有【C】條邊。A.n B.n(n-1) C.n(n-1)/2 D.2n具有4個頂點的無向完全圖有【A】條邊。A.6 B.12 C.16 D.20具有6個頂點的無向圖至少應有【A】條邊才能確保是一個連通圖。A.5 B.6 C.7 D.8一個有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是【D】。A.n B.(n-1)2 C.(n-1) D.n2對某個無向圖的鄰接矩陣來說，【A】。第i行上的非0元素個數等于第i列上非0元素個數矩陣中非0元素個數等于圖中的邊數第i行、第i列上非0元素個數等于頂點vi的度數矩陣中非全0行的行數等于圖中的頂點數對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小為【①A】；所有鄰接表中結點總數為【②C】。A.n B.n+1 C.n-1D.n2A.e/2B.eC.2eD.n+e二、 判斷題【X】1.n個頂點的無向圖至多有n(n-1)條邊?！尽薄?.有向圖中，各頂點的入度之和等于各頂點的出度之和?！尽薄?.鄰接矩陣只存儲了邊的信息，沒有存儲頂點的信息。【X]4.連通分量是無向圖的極小連通子圖。?！綳]5.如果表示有向圖的鄰接矩陣是對稱的，則該有向圖一定是完全有向圖。【X]6.如果表示圖的鄰接矩陣是對稱的，則該圖一定是無向圖?！尽薄?.如果表示圖的鄰接矩陣不是對稱的，則該圖一定是有向圖。三、 填空題有n個頂點的無向圖最多有 條邊。具有n個頂點的強連通有向圖至少有條邊。具有n個頂點的有向圖最多有 條邊。一個圖的臨接矩陣 表示法是唯一的，而鄰接表 表示法是不唯一的。具有10個頂點的無向圖，邊的總數最多為45 。在有n個頂點的有向圖中，每個頂點的度最大可。已知一個有向圖采用鄰接矩陣表示，計算第i個頂點的入度的方法是 求第i列非0元素個數。已知一個有向圖的鄰接矩陣表示，刪除所有從第i個結點出發(fā)的弧的方法是將第i行對應的1置成0 。對于n的頂點的無向圖，采用鄰接矩陣表示，求圖中邊的方法是計算鄰接矩陣中元素值為1的個數 ，判斷任意兩個頂點是否有邊相連的方法是判斷對應鄰接矩陣元素的值是否為1,再除以2 ，求任意頂點的度的方法是求鄰接矩陣中對應頂點所在行值為1的元素個數 。對于n的頂點的有向圖，采用鄰接矩陣表示，求圖中邊的方法是計算鄰接矩陣中元素值為1的個數 ，判斷任意兩個頂點是否有邊相連的方法是判斷對應鄰接矩陣元素的值是否為1 ，求任意頂點的度的方法是求鄰接矩陣中對應頂點所在行和列的元素值為1的個數。無向圖的連通分量指無向圖中最大連通子圖 。若無向圖有m條邊，，則表示該無向圖的鄰接表中有—2m 結點。四、簡答題從占用的存儲空間來看，對于稠密圖和稀疏圖，采用鄰接矩陣和鄰接表那個更好些？答：從占用存儲空間看，稠密圖采用鄰接矩陣更好，稀疏圖采用鄰接表更好。用鄰接矩陣表示圖時，矩陣元素的個數與頂點個數是否相關？與邊的條數是否相關？為什么？。答：用鄰接矩陣表示圖，矩陣元素的個數與圖的頂點個數直接相關，與邊的條數無關。因為假設定點個數為n，則鄰接矩陣的大小為n2。第九章查找一、單選題順序查找法適合于存儲結構為【B】的查找表。散列存儲 B.順序存儲或鏈式存儲C.壓縮存儲 D.索引存儲對查找表進行折半查找時，要求查找表必須【B】。以順序方式存儲以順序方式存儲，且結點按關鍵字有序排列以鏈式方式存儲以鏈式方式存儲，且結點按關鍵字有序排列采用順序查找法查找長度為n的查找表時，每個元素查找的平均查找長度為【C】。A.nB.n/2 C.(n+1)/2 D,(n-1)/2采用折半查找法查找長度為n的查找表時，每個元素查找的平均查找長度為【D】。A.O(n2) B.O(nlog2n)C.O(n) D.O(log2n)采用分塊查找時，若查找表中有625個元素，查找每個元素的概率相同，假設對索引表和塊都采用順序查找，每塊應分【B】個結點最佳。A.10 B.25 C.6 D.625查找n個元素的有序表時，最有效的查找方法是【C】。順序查找 B.分塊查找 C.折半查找 D.二叉排序樹如果要求一個查找表既能快速查找，又能適應動態(tài)變化的要求，可以采用【A】查找方法。A.分塊 B.順序 C.折半 D.散列在關鍵字隨機分布的情況下，用二叉排序樹的方法進行查找，其查找長度與【B】量級相當。順序查找 B.折半查找 C.分塊查找 D.前三個都不正確查找效率最高的二叉排序樹是【C】。所有結點的左子樹都為空的二叉排序樹所有結點的右子樹都為空的二叉排序樹平衡二叉樹沒有左子樹的二叉排序樹假定有k個關鍵字互為同義詞，若用線性探測再散列法把這k個關鍵字的紀錄插入到散列表中，至少要進行【D】次探測。A.k-1B.kC.k+1 D.k(k+1)/2以下說法錯誤的是【B】。散列法存儲的基本思想是由記錄關鍵字決定數據存儲地址散列法的結點中只包含數據元素自身的信息，不包含任何指針裝填因子是散列法的一個重要參數，它反映了散列表的裝填程度散列表的查找效率取決于散列造表是的散列函數和沖突處理的方法散列表的平均查找長度【A】。與沖突處理方法有關而與表的長度無關與沖突處理方法無關而與表的長度有關與沖突處理方法有關且與表的長度有關與沖突處理方法無關且與表的長度無關二、 判斷題【”】1.順序查找法適合于順序或鏈式存儲結構的查找表?！綳】2.順序查找法只能在順序存儲結構上進行?！綳】3.二分查找可以在有序的雙向鏈表上進行?！綳】4.在二叉排序樹中，每個結點的關鍵字比左孩子的關鍵字大，比右孩子的關鍵字小?！綳】5.每個結點的關鍵字都比左孩子的關鍵字大，比右孩子的關鍵字小，這樣的二叉樹都是二叉排序樹?！?】6.哈希存儲法只能存儲數據元素的值，不能存儲數據元素之間的關系?！綳】7.哈希沖突是指同一個關鍵字對應多個不同的哈希地址。三、 填空題順序查找含n個元素的順序表，若查找成功，則比較關鍵字的次數最多為n次；若查找不成功，則比較關鍵字的次數為n+1次。TOC\o"1-5"\h\z在含有n個元素的有序順序表中進行二分查找，最大的比較次數是.1logn+1 。2用二分查找一個查找表，該查找表必須具有的特點是順序存儲且關鍵字有序 。分塊查找發(fā)將待查找的表均勻地分成若干塊且塊中諸記錄的順序可以是任意的，但塊與塊之間 關鍵字有序 。在分塊查找方法中，首先查找關鍵字表，然后再查找相應的對應的塊 。用二叉排序樹在n個元素中進行查找，最壞情況下查找時間復雜度為O(n)，最好情況的查找時間復雜度為 。折半查找的存儲結構僅限于順序存儲結構，且是 。一個無序序列可以通過構造一棵二叉排序 樹而變成有序序列，構造樹的過程即是對無序序列進行排序的過程。用二叉排序樹查找，在最壞的情況下，平均查找長度為(n+1)/2 ，最好的情況下，平均查找長度為 。在哈希函數H(key)=key/p中，p最好取 。哈希表是誦過將關鍵字按選定的哈希函數和沖突處理方法，把記錄按關鍵字轉換為地址進行存儲的存儲表，哈希方法的關鍵是選擇好的哈希函數和沖突處理的方法。一個好的哈希函數其轉換地址應盡可能均勻 ，而且函數運算應盡可能 。四、解答題1、畫出對長度為10的右序表進行折半查找的一棵判定樹，并求