數(shù)據(jù)結(jié)構(gòu)題集答案65692

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

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

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

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

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

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

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

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

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

10、性表的順序?qū)崿F(xiàn)中，算法的時間復雜度為0(1)的操作是【AloA.訪問第i個結(jié)點和求第i個結(jié)點的直接前驅(qū)B.在第i個結(jié)點后插入一個新結(jié)點C.刪除第i個結(jié)點D.以上都不對15 .若長度為n的線性表采用順序存儲結(jié)構(gòu)，在第i個位置插入一個新元素的算法的時間復雜度為【CA.O(0)B.0(1)C.O(n)D.O(n2)16 .對于順序存儲的線性表，訪問結(jié)點和增加、刪除結(jié)點的時間復雜度為【CA.O(n)O(n)B.0(n)0(1)C.0(1)0(n)D.0(1)0(1)17 .線性表以鏈式方式存儲，訪問第i個結(jié)點的時間復雜度為【CA.O(i)B.0(1)C.O(n)D.0(i-1)18 .循環(huán)鏈表H尾結(jié)點

11、p的特點是【A】。A.p->next=HB.p->next=H->nextC.p=HD.p=H->next二、判斷題x1.取線性表的第i個元素的時間同i的大小有關。X2.線性表中每個元素都有一個直接前驅(qū)和一個直接后繼?！綳】3.順序存儲方式只能用于存儲線性結(jié)構(gòu)?！綳】4.線性表采用鏈式存儲時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以不連續(xù)。【X】5.在一個設有頭指針和尾指針的單鏈表中，執(zhí)行刪除單鏈表最后一個結(jié)點的操作與鏈表的長度無關。三、填空題1 .向一個長度為n的順序表中的第i個元素之前插入一個元素時，需要向后移動n-i+1個元素。2 .在一個長度為n的順序表中刪除第i個元素時，

12、需要向前移動n-i個元素。3 .在單鏈表中設置頭結(jié)點的作用是簡化插入、刪除算法。4 .在單鏈中要刪除某一指定結(jié)點，必須找到該結(jié)點的直接前驅(qū)結(jié)點。5 .訪問單鏈表中的結(jié)點，必須沿著指針域依次進行。6 .在雙鏈表中每個結(jié)點有兩個指針域，一個指向直接前驅(qū)結(jié)點，一個指向直接后繼名吉點°7 .在雙向循環(huán)鏈表中,刪除最后一個結(jié)點的算法時間復雜度為0(1)。8 .訪問一個線性表中具有給定值的時間復雜度的數(shù)量級是0(n)。9 .由n個數(shù)據(jù)元素生成一個順序表，若每次都調(diào)用插入算法把一個元素插入到表頭，則整個算法的時間復雜度為0(n),若每次都調(diào)用插入算法把一個元素插入到表尾，則整個算法的時間復雜度為0

13、(n2)。10 .在雙向鏈表中,可以用表尾指針代替表頭指針。11 .根據(jù)n個數(shù)據(jù)元素建立對應的順序表和單鏈表存儲結(jié)構(gòu)，其算法的時間復雜度最好的情況是0(n),最壞的情況是0(n2)。12 .求線性表的順序存儲和鏈式存儲的長度的算法時間復雜度分別是0(1)和0(n)。13 .在一個帶頭結(jié)點的單鏈表中，在表頭插入或刪除與在其他位置插入或刪除，其操作過程是否相同?相同。14 .在一個不帶頭結(jié)點的單鏈表中，在表頭插入或刪除與在其他位置插入或刪除，其操作過程是否相同?不相同。四、簡答題1 .闡述順序表和鏈表存儲方式的特點。答：順序表存儲方式為數(shù)據(jù)分配連續(xù)的存儲單元，數(shù)據(jù)元素按邏輯順序依次存儲到相應存儲單

14、元中，使得邏輯相鄰的數(shù)據(jù)元素物理也相鄰，因此可以實現(xiàn)隨機訪問線性表的數(shù)據(jù)元素，即數(shù)據(jù)訪問的時間復雜度為0(1)。鏈表存儲方式分配的存儲單元可以不連續(xù)，通過每個結(jié)點的指針域來表示數(shù)據(jù)元素之間的邏輯關系，只能順序訪問線性表中的數(shù)據(jù)元素。2 .若頻繁地對一個線性表進行插入和刪除操作，則該線性表宜采用何種存儲結(jié)構(gòu)，為什么？答：若頻繁地對一個線性表進行插入和刪除操作，則該線性表宜采用鏈式存儲結(jié)構(gòu)。因為鏈式存儲結(jié)構(gòu)在插入和刪除數(shù)據(jù)元素時不需要移動數(shù)據(jù)元素，只需要修改結(jié)點的指針域就可以改變數(shù)據(jù)元素之間的邏輯關系。3 .在單鏈表、雙向循環(huán)鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點，不知道頭指針，能否將結(jié)點p

15、從相應的鏈表中刪除？若可以，時間復雜度各為多少。答：要實現(xiàn)刪除p結(jié)點的操作，必須找到其前驅(qū)結(jié)點，修改其指針域的值使其指向p的后繼結(jié)點，以實現(xiàn)刪除結(jié)點p。單鏈表不行，因為不知道頭指針就無法找到結(jié)點p的前驅(qū)結(jié)點。雙向循環(huán)鏈表和單循環(huán)鏈表可以可以實現(xiàn)刪除p結(jié)點。單循環(huán)鏈表刪除p結(jié)點的時間復雜度為0(n),雙循環(huán)鏈表刪除P結(jié)點的時間復雜度為0(1)。4 .對鏈表設置頭結(jié)點的作用是什么？答：對帶頭結(jié)點的鏈表，在表的任何結(jié)點之前插入結(jié)點或刪除任何位置的結(jié)點，所要做的都是修改前一個結(jié)點的指針域，因為在帶頭結(jié)點的鏈表中任何元素結(jié)點都有前驅(qū)結(jié)點。如果沒有頭結(jié)點，在首元結(jié)點前插入結(jié)點或刪除首元結(jié)點都要修改頭指針，

16、其算法要比帶頭結(jié)點的算法復雜些。其次，帶頭結(jié)點的鏈表結(jié)構(gòu)，初始化后的頭指針就固定了，除撤銷算法外，所有算法都不會修改頭指針，可以減少出錯的可能性。五、算法設計題1 .已知一個線性表用含頭結(jié)點的單鏈表做存儲結(jié)構(gòu)，寫一個算法求單鏈表的長度。解：算法基本思想：從頭結(jié)點的下一個結(jié)點開發(fā)，遍歷單鏈表的每個結(jié)點，每遇到一個結(jié)點，結(jié)點計算器加1。intlistlenght(linklistL)intlength=0;P=L->next;while(p)length+;p=p->next;return(length);2 .已知一個順序表L,其中的元素按值遞增有序排列，設計一個算法插入一個值為0(

17、1)o的元素后保持該順序表仍然遞增有序，且空間復雜度為voidinsertsq(sqlistL,elemtypex)n=L.length-1;while(n>=0&&LT(x,L.elemn)L.elemn+1=L.elemn;n-;L.elemn+1=x;L.lenght+;return;3 .寫一個算法，從順序表中刪除值為x的所有元素。voiddelallsq(Sqlist&L)inti=0,j=0;while(j<L.length)if(L.elemj!=x)L.elemi+=L.elemj;j+;L.longth=i;第三章棧和隊列一、單選題1 .對

18、于棧操作數(shù)據(jù)的原則是【C】。A.先進先出B.后進后出C.后進先出D.不分順序2 .隊列的先進先出特征是指【AA.最后插入隊列的元素總是最后被刪除B.當同時進行插入、刪除操作時，總是插入操作優(yōu)先C.每當有刪除操作時，總要先做一次插入操作D.每次從隊中刪除的元素總是最早插入的元素3 .與順序棧相比較，鏈棧有一個比較明顯的優(yōu)勢是【A】。A.通常不會出現(xiàn)棧滿的情況B.插入操作更容易實現(xiàn)C.通常不會出現(xiàn)?？盏那闆rD.刪除操作更容易實現(xiàn)4 .棧和隊列的共同點是【CA.都是先進先出B.都是后進后出C.只允許在端點處進行插入和刪除D.無共同點5 .棧的特點是B,隊列的特點是【A】；棧和隊列都是【C】若入棧序列

19、是1,2,3,4,則A是不可能的出棧序列；若進隊列的序列是1,2,3,4,則【D】是可能的出隊序列。A.先進先出B.后進先出C.進優(yōu)先于出D.出優(yōu)先于進A.順序存儲的線結(jié)構(gòu)B.鏈式存儲的線性結(jié)構(gòu)C.限制存取點的線性結(jié)構(gòu)D.限制存取點的非線性結(jié)構(gòu)A.3,2,1,4B.3,2,4,1C.4,2,3,1D.1,2,3,46 .用單鏈表表示的鏈隊列的隊頭在鏈表的【AA.鏈頭B.鏈尾C.鏈中D.都不是7 .設入棧序列為1,2,3,4,5,則可能得到的出棧序列為【CA.1,2,5,3,4B.3,1,2,5,4C.3,2,5,4,1D.1,4,2,3,58 .輸入序列是ABC,若輸出序列變?yōu)镃BA,經(jīng)過的棧

20、操作為【B】。A.push,pop,push,pop,push,popB. push,push,push,pop,pop,popC. push,push,pop,pop,push,popD. push,pop,push,push,pop,pop9 .棧在【D】應用。A.遞歸調(diào)用B.函數(shù)調(diào)用C.表達式求值D.A,B,C10 .設計一個判別表達式中左、右括號是否配對的算法，采用【D】數(shù)據(jù)結(jié)構(gòu)最佳。A.線性表的順序存儲結(jié)構(gòu)B.隊列C.線性表的鏈式存儲結(jié)構(gòu)D.棧11 .允許對隊列進行的操作有【DA.對隊列中的元素排序B.取出最近進隊的元素C.在隊頭之前插入元素D.刪除隊頭元素12 .對于循環(huán)隊列【DA

21、.無法判斷隊列是否為空C.隊列不可能滿13 .隊列存放在A0.M-1A.rear=rear+1C.rear=(rear+1)%(M+1)14 .隊列存放在A0.M-1A.front=front+1B.無法判斷隊列是否為滿D.以上說法都不對中，則入隊時的操作為【B.rear=(rear+1)%MD.rear=(rear+1)%(M-1)中，則出隊時的操作為【B.front=(front+1)%MB】。B】。C.front=(front+1)%(M+1)D.front=(front+1)%(M-1)15 .循環(huán)隊列的最大容量為A.rear=frontC.rear+1=front16 .循環(huán)隊列的最

22、大容量為A.rear=frontC.rear+1=front二、判斷題M,則隊空的條件是【B.(rear+1)%M=frontD.(rear-1)%M=frontM,則隊滿的條件是【B.(rear+1)%M=frontD.(rear-1)%M=frontAoBoX1.隊列在函數(shù)調(diào)用時必不可少，因此遞歸離不開隊列。V2.棧和隊列的存儲方式，既可以是順序方式，又可以是鏈式方式。IV】3.設尾指針的循環(huán)鏈表表示隊列，則入隊和出隊算法的時間復雜度為0(1)?！綳】4.隊列邏輯上是一個上端和下端既能增加又能減少的線性表。V55.在鏈隊列中，即使不設置尾指針也能進行入隊操作。V66.棧和隊列度是限制存取點

23、的線性結(jié)構(gòu)。X7.即使對不含相同元素的同一輸入序列進行兩組不同的合法的入棧和出棧操作，所得的輸出序列一定相同。V88.棧是實現(xiàn)函數(shù)調(diào)用所必需的數(shù)據(jù)結(jié)構(gòu)。IV】9.順序隊列中的元素個數(shù)，可以根據(jù)隊首指針和隊尾指針的值計算出來。三、填空題1 .循環(huán)隊列的引入，目的是為了克服順序隊列的假溢出。2 .區(qū)分循環(huán)隊列的空與滿有3種方法，它們是少用一個元素、設空滿標志、用計數(shù)器記錄隊列中元素個數(shù)。3 .棧和隊列的區(qū)別是棧只能在表一端進行插入和刪除操作，隊列限制在表的一端進行插入操作，在另一端進行刪除操作。4 .一個棧的輸入序列是12345,則棧的輸出序列43512是錯誤的。5 .設棧采取順序存儲結(jié)構(gòu)，棧中已

24、有i-1個元素，則第i個元素進棧操作的算法時間復雜度是O(1)。6 .若用不帶頭結(jié)點的單鏈表表示棧，則創(chuàng)建一個空棧要執(zhí)行的操作是top=NULL。Q.front=(Q.front+1)%QSizeQ.rear=(Q.rear+1)%QSizeQ.front->next=Q.rear鏈棧。7 .從循環(huán)隊列中刪除一個元素的操作是8 .從循環(huán)隊列中插入一個元素的操作是9 .判斷鏈隊列中只有一個結(jié)點的條件是10 .如果棧的最大長度難以估計，最好使用四、簡答題1 .為什么說棧是一種后進先出表?答：因為棧是限定在表的一端進行插入和刪除操作，所以后入棧的數(shù)據(jù)元素總是先出棧，所以說棧是一種后進先出表。2

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

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

27、操作的線性表，因而是后進先出表。隊列是允許在表的一端進行插入，在表的另一端進行刪除的線性表，因而是先進先出表。線性表可以在任何位置進行插入和刪除操作。五、算法設計題1 .設計一個算法，利用棧和隊列的基本運算將指定棧中的元素順序逆轉(zhuǎ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

28、);DestroyQueue(sq);2 .設計一個算法，利用棧的基本運算返回指定棧中棧底元素。解：先將棧中元素依次移至另一個臨時棧中，最后一個元素即為棧底元素，設為x.。再將臨時棧中元素移至原棧中，即恢復棧內(nèi)容。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);)DestroyS

29、tack(tmpst);return(x);)3 .設計一個算法，利用棧來實現(xiàn)帶頭結(jié)點的單鏈表h的逆序。解：算法基本思想：將單鏈表結(jié)點依次放入鏈棧中，鏈棧本身就是一個單鏈表，即實現(xiàn)了原單鏈表的逆序。假設鏈棧不帶頭結(jié)點，再加上原來的頭結(jié)點，就完成了原單鏈表的逆序。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 .串是任意有限個【DA.符號構(gòu)成的集合C.字符構(gòu)成的集合第四章串B.符號構(gòu)成的序列D.字符構(gòu)成的序列2 .串

30、是一種特殊的線性表，A.可以順序存儲C.數(shù)據(jù)元素可以使多個字符3 .兩個串相等必有串長度相等且【A.串的各位置字符任意C.兩個串含有相同的字符4 .設有兩個串A.連接C.求子串其特殊性體現(xiàn)在【BB.數(shù)據(jù)元素是一個字符D.可以鏈接存儲B】。8 .串中各位置字符均對應相等D.兩個串所含字符任意B】。p和q,求q在p中首次出現(xiàn)的位置的運算稱著【B.模式匹配D.求串長二、填空1 .空串是長度為0的串。2 .一個串中任意連續(xù)字符組成的子序列稱為該串的子串。3 .設s="abcd",則執(zhí)行語句s2=Substr(s,2,2)后，s2="bc”。4 .空白串是由一個或多個空格字

31、符組成的串，其長度等于其所包含的空格字符的個數(shù)。第五章數(shù)組一、單選題1.一維數(shù)組與線性表的區(qū)別是【A】。A.前者長度固定，后者長度可變B.后進長度固定，前者長度可變C.兩者長度均固定D.兩者長度均可變2 .多維數(shù)組的數(shù)組元素之間的關系，【AA.是線性的B.是樹型的C.既是線性的，又是樹型的D.既不是線性的，也不是樹型的3 .設有數(shù)組A810,每個元素占3個存儲單元，存放該數(shù)組的存儲單元數(shù)為【CA.80B.100C.240D.2704 .設有數(shù)組A810,每個元素占3個存儲單元，首地址為SA,則元素75的起始地址是【DA.SA+141B.SA+144C.SA+222D.SA+2255 .設有一個

32、n*n的對稱矩陣，采用壓縮存儲，則存入內(nèi)存的元素個數(shù)為【CA.n*nB.n*n/2C.n*(n+1)/2D.(n+1)2/26 .設A是一個n*n的對稱矩陣，壓縮存儲到一個一維數(shù)組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 .稀疏矩陣一般的壓縮方法有兩種，即【CA.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組和十字鏈表D.散列和十字鏈表8 .設有一個10*10的對稱矩陣A,以行主次序進行壓縮存儲，每個元素占一個存儲單元，a1,1的地址是1,則A8,5的起始

33、地址是【B】。A.13B.33C.18D.40二、解答題1 .設數(shù)組A5080,其基地址為2000,每個元素占2個存儲單元，以行序位主序順序存儲，回答下列問題：(1)該數(shù)據(jù)組由多少元素？(2)該數(shù)組占用多少存儲單元？(3)數(shù)組元素a3030的存儲地址是多少？答：(1)該數(shù)組有：50*80=4000個元素(2)該數(shù)組占用4000*4=8000個存儲單元(3)loc(30,30)=2000+(30*80+30)*2=2000+4860=6860第六章樹與二叉樹一、單選題1 .有關二叉樹下列說法正確的是【B】。A.二叉樹的度為2B.一棵二叉樹的度可以小于2C.一棵二叉樹至少有一個結(jié)點的度為2D.二叉

34、樹中任何一個結(jié)點的度為22 .利用二叉鏈表存儲樹，則根結(jié)點的右指針是【CA.指向最左孩子B.指向最右孩子C.空D.非空3 .若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)為【BA.9B.11C.15D.不確定4 .一棵二叉樹有1001個結(jié)點，其中葉結(jié)點的個數(shù)為【D】。A.250B.490C.254D.不確定5 .一棵完全二叉樹有1001個結(jié)點，其中葉結(jié)點的個數(shù)為【DA.250B.500C.254D.以上答案均不對6 .一棵具有1025個結(jié)點的二叉樹的高h為【C】。A.11B.11C.11至1025之間D.10至1024之間7 .一棵124個葉結(jié)點的完全樹，最多具有【B

35、】個結(jié)點。A.247B.248C.249D.2518 .一棵具有10個葉結(jié)點的二叉樹具有【B】度為2的結(jié)點。A.8B.9C.10D.119 .已知一棵完全二叉樹有625個結(jié)點，葉結(jié)點的個數(shù)為【CA.311B.312C.313D.其它10 .一棵具有n個結(jié)點的完全二叉樹的高h為【AB】。A.?10g2n?+1B.aog2n+1uC.log2n+1D.log2n-111 .由8個權(quán)值構(gòu)造一棵哈夫曼樹，該哈夫曼樹有1A個結(jié)點。A.15B.16C.17D.1412 .由3個結(jié)點可以構(gòu)造【D】種不同的二叉樹。A.2B.3C.4D.513 .樹最適合用來表示【CA.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素間具

36、有分支層次關系的數(shù)據(jù)D.元素間無聯(lián)系的數(shù)據(jù)14 .下圖中4棵二叉樹中，C不是完全二叉樹。oC.A.B.D.A】。15.某二叉樹的先序遍歷序列和后序便利序列正好相反，則該二叉樹一定是A.空或只有一個結(jié)點C.二叉排序樹B.完全二叉樹D.高度等于其結(jié)點數(shù)16 .在一棵非空二叉樹的中序遍歷序列中，根結(jié)點的右邊【A.只有右子樹上的所有結(jié)點C.只有左子樹上的部分結(jié)點B.只有右子樹上的部分結(jié)點D.只有左子樹上的所有結(jié)點17 .任何一棵二叉樹的葉子結(jié)點在先序、中序和后序遍歷序列中的相對次序【A.不發(fā)生上改變B.發(fā)生改變C.不能確定D.以上都不對18 .一棵滿二叉樹，m個葉結(jié)點，n個結(jié)點，深度為h,則【D】。A

37、.n=h+mB.h+m=2nC.m=h-119.設n,m是二叉樹上的兩個結(jié)點，在中序遍歷時,A.n在m右方C.n在m左方B.n是mD.nD.n=2h-1n在m之前的條件是的祖先的子孫20.設高度為h的二叉樹上只有度為0和度為2的結(jié)點，則此類二叉樹中包含的結(jié)點數(shù)最少為【B】。A.2h二、判斷題B.2h-1C.2h+1D.h+1X1.二叉樹是一般樹的特殊樹型。V2.樹與二叉樹是兩種不同的樹形結(jié)構(gòu)。X3.對于有n個結(jié)點的二叉樹，其高度為log2n。V4.完全二叉樹中，若一個沒有左孩子，則它必定是葉結(jié)點。V5.一棵具有n個結(jié)點的完全二叉樹，從上到下、從左到右用自然數(shù)對結(jié)點進行編號,結(jié)點為i的結(jié)點的左孩

38、子的編號為2i(2i<n)。X6.一棵樹中的葉結(jié)點數(shù)一定等于與其對應的二叉樹的葉結(jié)點數(shù)。IV】7.哈夫曼樹是帶權(quán)路徑長度最短的樹，路經(jīng)上權(quán)值較大的結(jié)點離根最近。V88.哈夫曼樹的結(jié)點個數(shù)不偶數(shù)。三、填空題1.深度為k的完全二叉樹至少有2K-1個結(jié)點,至多有2K-1個結(jié)點。2.在一棵二叉樹中,度為0的結(jié)點個數(shù)為n0,度為的結(jié)點個數(shù)為n2,則有n0=n2+13. 一棵二叉樹第i個結(jié)點，共有2K-1層最多有2i-1個葉結(jié)點。個結(jié)點，一棵有個結(jié)點的滿二叉樹共有2K-14 .根據(jù)二叉樹的定義，具有3個結(jié)點的二叉樹共有5 種不同形態(tài)，它們分別5.在為.?n/2?oQn,則編號最大的分支結(jié)點的編號6

39、.在一棵完全叉樹中，編號i和j的兩個結(jié)點處于同層的條件.?log2i?=.?log2j?7 .具有n個結(jié)點的二叉樹采用二叉鏈表存儲結(jié)構(gòu),共有8.具有n個結(jié)點的二叉樹中，如果有m個葉結(jié)點，則一定有點，有n-2m+1個度為1的結(jié)點。n+1個空指針域。m-1個度為2的結(jié)9.在叉樹的鏈式存儲結(jié)構(gòu)中，指針p所指結(jié)點為葉結(jié)點的條件是p->lchild=NULL&&p->rchild=NULL10 .二叉樹的先序序列和中序序列相等的條件是11 .有一棵如下圖所示的樹，回答下列問題：O任何結(jié)點至多只有右子樹這棵樹的根結(jié)點是這棵樹的葉子結(jié)點是結(jié)點c的度為2這棵樹的深度是一結(jié)點c的孩子

40、結(jié)點是結(jié)點c的雙親結(jié)點是這棵樹的度是ab,e,g,d4e,fOao12 .樹與二叉樹的兩個主要差別是樹中結(jié)點的最大度沒有限制，二叉樹結(jié)點的最大度限定為2樹的結(jié)點無左右之分,二叉樹的的結(jié)點有左右之分個孩子結(jié)點，除根結(jié)點之外，其余結(jié)13.樹中任一結(jié)點允許有0個或多個孩子點有1個雙親結(jié)點。四、簡答題1.設有如下圖所示的二叉樹，給出其前序、中序和后序遍歷結(jié)果。答：前序序列：eadcbifghj中序序列：abcdiefhgj后序序列：bcidahjgfe答：下圖為其樹的二叉樹表示。3.有一份電文共有5個字符：a,b,c,d,e,它們出現(xiàn)的頻率依次為4,7,5,2,9,構(gòu)造對應的哈夫曼樹，求哈夫曼樹的帶權(quán)

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

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個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是【DA.nB.(n-1)2C.(n-1)D.n27 .對某個無向圖的鄰接矩陣來說，AoA.第i行上的非0元素個數(shù)等于第i列上非0元素個數(shù)8 .矩陣中非0元素個數(shù)等于圖中的邊數(shù)C.第i行、第i列上非

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

44、圖?！綱17.如果表示圖的鄰接矩陣不是對稱的，則該圖一定是有向圖。三、填空題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個結(jié)點出發(fā)的弧的方法是將第i行對應的1置成0。計算鄰接矩陣中9 .

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

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

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

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

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

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

51、但塊與塊之間關鍵字有序。5 .在分塊查找方法中，首先查找關鍵字表，然后再查找相應的對應的塊。6 .用二叉排序樹在n個元素中進行查找，最壞情況下查找時間復雜度為O,最好情況的查找時間復雜度為O(1og2r。7 .折半查找的存儲結(jié)構(gòu)僅限于順序存儲結(jié)構(gòu),且是關鍵字有序排列。8 .一個無序序列可以通過構(gòu)造一棵二叉排序樹而變成有序序列,構(gòu)造樹的過程即是對無序序列進行排序的過程。9 .用二叉排序樹查找，在最壞的情況下，平均查找長度為(n+1)/2,最好的情況下，平均查找長度為.(log2n+1)-1。10 .在哈希函數(shù)H(key)=key/p中，p最好取小于或等于m的最大質(zhì)數(shù)。11 .哈希表是通過將關鍵字按選定的哈希函數(shù)和沖突處理方法，把記錄按關鍵字轉(zhuǎn)換為地址進行存儲的存儲表，哈希方法的關鍵是選擇好的哈希函數(shù)和沖突處理的方法。一個好的哈希函數(shù)其轉(zhuǎn)換地址應盡