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

數(shù)據(jù)結(jié)構(gòu)題集第一章緒論一、單項選擇題1.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上能夠把數(shù)據(jù)結(jié)構(gòu)分紅【C】。A.動向結(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)存中的表示是指【A】。A.數(shù)據(jù)的儲存結(jié)構(gòu)B.數(shù)據(jù)結(jié)構(gòu)C.數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)D.數(shù)據(jù)元素之間的關(guān)系【A】是數(shù)據(jù)的最小單位，【B】是數(shù)據(jù)的基本單位。A.數(shù)據(jù)項B.數(shù)據(jù)元素C.信息項D.表元素4.計算機所辦理數(shù)據(jù)一般擁有某種內(nèi)在聯(lián)系，這是指【B】。A.數(shù)據(jù)與數(shù)據(jù)之間存在某種關(guān)系B.數(shù)據(jù)元素與數(shù)據(jù)元素之間存在某種關(guān)系C.元素內(nèi)部存在某種結(jié)構(gòu)D.數(shù)據(jù)項與數(shù)據(jù)項之間存在某種關(guān)系5.算法剖析的目的是【C】。A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究輸入和輸出的關(guān)系C.剖析算法的效率以求改良D.剖析算法的易懂性6.在儲存數(shù)據(jù)時，不單要考慮儲存各數(shù)據(jù)元素的值，并且還要儲存【A.數(shù)據(jù)辦理的方法B.數(shù)據(jù)元素的種類C.數(shù)據(jù)元素之間的關(guān)系D.數(shù)據(jù)的儲存方法7.算法剖析的主要任務是剖析【D】。

C】。算法能否擁有較好的可讀性算法中能否儲存語法錯誤和邏輯錯誤算法的功能能否切合設計要求算法的履行時間與問題規(guī)模之間的關(guān)系。8.數(shù)據(jù)的運算【A】。效率與采納何種儲存結(jié)構(gòu)有關(guān)是依據(jù)儲存結(jié)構(gòu)來定義的有算術(shù)運算和關(guān)系運算兩大類一定用程序設計語言來描繪9.算法的計算量的大小稱為算法的【B】。A.效率B.時間復雜度C.現(xiàn)實性10.連續(xù)儲存分派時，儲存單元的地點【A】。A.必定連續(xù)B.必定不連續(xù)C.不必定連續(xù)D.部分連續(xù)，部分不連續(xù)

D.難度二、判斷題1.數(shù)據(jù)元素是數(shù)據(jù)結(jié)構(gòu)的最小單位【.×】。2.數(shù)據(jù)的邏輯結(jié)構(gòu)說明數(shù)據(jù)元素之間的次序關(guān)系，它依靠于計算機的儲存結(jié)構(gòu)【×.】。3.數(shù)據(jù)的邏輯結(jié)構(gòu)指數(shù)據(jù)元素的各數(shù)據(jù)項之間的邏輯關(guān)系【×.】。4.算法的好壞與算法的描繪語言沒關(guān)，但與使用的計算機有關(guān)【.×】。5.數(shù)據(jù)結(jié)構(gòu)的抽象操作的定義與詳細實現(xiàn)有關(guān)【.×】。三、填空題1.數(shù)據(jù)的邏輯結(jié)構(gòu)指數(shù)據(jù)元素之間的邏輯關(guān)系。2.一個數(shù)據(jù)結(jié)構(gòu)在計算機中的表示稱為儲存結(jié)構(gòu)。3.數(shù)據(jù)的物理結(jié)構(gòu)主要包含次序儲存結(jié)構(gòu)的表示和鏈式儲存結(jié)構(gòu)4.數(shù)據(jù)邏輯結(jié)構(gòu)包含會合、線性結(jié)構(gòu)、樹和圖圖結(jié)構(gòu)統(tǒng)稱為非線性結(jié)構(gòu)。

的表示。四種，樹結(jié)構(gòu)和5.次序儲存方法把邏輯上邏輯上相鄰的元素鏈式儲存方法中結(jié)點間的邏輯關(guān)系是由指針域6、數(shù)據(jù)結(jié)構(gòu)研究的是邏輯結(jié)構(gòu)和物理結(jié)構(gòu)這類結(jié)構(gòu)定義相應的運算，設計出相應的

儲存在物理地點相鄰的儲存單元里；表示的。以及它們之間的互相關(guān)系，并對于算法。7.算法的履行時間是問題規(guī)模n的函數(shù)。8.以下是4個算法所有語句頻度之和的表達式，此中的復雜度同樣的是

A和

B

。A.TA(n)=2n3+3n2+1000

B.TB(n)=n3-n2log2n-1000C.TC(n)=n2log2n+n2

D.TD(n)=n2+1000四、解答題1.簡述數(shù)據(jù)的邏輯結(jié)構(gòu)和儲存結(jié)構(gòu)的關(guān)系。答：在數(shù)據(jù)結(jié)構(gòu)中，邏輯結(jié)構(gòu)和儲存結(jié)構(gòu)是親密有關(guān)的，儲存結(jié)構(gòu)不單將數(shù)據(jù)元素存儲到計算機中，并且還要表示各數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯結(jié)構(gòu)與計算機沒關(guān)，儲存結(jié)構(gòu)是數(shù)據(jù)元素之間的關(guān)系在計算機中的表示。往常狀況下，一種邏輯結(jié)構(gòu)能夠有多種儲存結(jié)構(gòu)，比如，線性結(jié)構(gòu)能夠采納次序儲存結(jié)構(gòu)或鏈式存粗結(jié)構(gòu)表示。2.數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)種類有什么差異？答：數(shù)據(jù)結(jié)構(gòu)是互相間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的會合，一般包含三個方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、儲存結(jié)構(gòu)和多半據(jù)的運算。數(shù)據(jù)種類是一個值得會合和定義在這個值集上的一組操作的總稱。數(shù)據(jù)結(jié)構(gòu)要點考慮元素之間的關(guān)系，數(shù)據(jù)種類要點考慮數(shù)據(jù)的個體特色。3.當為解決某一問題已經(jīng)選定其數(shù)據(jù)的邏輯結(jié)構(gòu)后，選擇數(shù)據(jù)的儲存結(jié)構(gòu)時，應從哪些方面考慮？答：往常從兩個方面考慮：第一是算法實現(xiàn)的儲存空間復雜度；第二是算法履行的時間復雜度。若儲存空間難以確立，宜選擇鏈式儲存結(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（1≤i≤n）個元素的值B.次序輸出這n個元素C.互換第1個與第2個元素的值D.輸出與給定值x相等的元素在線性表中的序號3.假如最常用的操作是取第i個結(jié)點及其前驅(qū)，則采納【A.單鏈表B.雙鏈表C.線性鏈表D.次序表4.線性表是擁有n個【C】的有限序列（n≥0）。A.表元素B.字符C.數(shù)據(jù)元素D.數(shù)據(jù)項5.下邊對于線性表的表達中，錯誤的選項是【B】。

D】儲存方法最節(jié)儉時間。線性表采納次序儲存，則一定占用一片連續(xù)的儲存單元線性表采納次序儲存，則便于插入和刪除操作線性表采納鏈式儲存，則不用占用一片連續(xù)的儲存單元線性表采納鏈式儲存，則便于插入和刪除操作線性表的次序儲存結(jié)構(gòu)是一種【A】。A.隨機存取的儲存結(jié)構(gòu)B.次序存取的儲存結(jié)構(gòu)C.索引存取的儲存結(jié)構(gòu)D.Hash存取的儲存結(jié)構(gòu)7.單鏈表中增添一個頭結(jié)點的目的是為了【C】。A.使單鏈表起碼有一個結(jié)點B.表記表首結(jié)點的地點C.方便運算的實現(xiàn)說明單鏈表是線性表的鏈式儲存8.不帶頭結(jié)點的單鏈表（頭指針為h）為空的條件是【A】。A.h==NULLB.h->next==NULLC.h->next==hD.h!=NULL帶頭結(jié)點的單鏈表（頭指針為h）為空的條件是【B】。A.h==NULLB.h->next==NULLC.h->next==hD.h!=NULL10.帶頭結(jié)點的循環(huán)雙向鏈表（頭指針為L）為空的條件是【D】。A.L==NULL

B.L->next->prior==NULLC.L->prior==NULL

D.L->next==L11.非空的循環(huán)單鏈表（頭指針為

head）的尾結(jié)點（由

p指向）知足【

C】。A.p->next==NULL

B.p==NULLC.p->next==head

D.p==head12.設一個鏈表最常用的操作是在末端插入結(jié)點和刪除尾結(jié)點，則采納【A.帶頭結(jié)點的雙循環(huán)鏈表B.單循環(huán)鏈表C.帶尾指針的單循環(huán)鏈表D.單鏈表

A】最節(jié)儉時間。13.若某線性表最常用的操作存取隨意指定序號的元素和在表尾進行插入和刪除，則采納【A】的儲存方式最節(jié)儉時間。A.次序表B.雙鏈表C.帶頭結(jié)點的雙循環(huán)鏈表D.單循環(huán)鏈表14.在n個結(jié)點的線性表的次序?qū)崿F(xiàn)中，算法的時間復雜度為A.接見第i個結(jié)點和求第i個結(jié)點的直接前驅(qū)B.在第i個結(jié)點后插入一個新結(jié)點C.刪除第i個結(jié)點D.以上都不對

O(1)的操作是【

A】。15.若長度為n的線性表采納次序儲存結(jié)構(gòu)，在第i個地點插入一個新元素的算法的時間復雜度為【C】。A.O(0)

B.O(1)

C.O(n)

D.O(n2)16.對于次序儲存的線性表，接見結(jié)點和增添、刪除結(jié)點的時間復雜度為【

C】。A.O(n)O(n)

B.O(n)O(1)

C.O(1)O(n)

D.O(1)O(1)17.線性表以鏈式方式儲存，接見第

i個結(jié)點的時間復雜度為【

C】。A.O(i)

B.O(1)

C.O(n)

D.O(i-1)18.循環(huán)鏈表

H尾結(jié)點

p的特色是【

A】。A.p->next==HB.p->next==H->nextC.p==HD.p==H->next二、判斷題【×】1.取線性表的第i個元素的時間同i的大小有關(guān)?！尽痢?.線性表中每個元素都有一個直接前驅(qū)和一個直接后繼?！尽痢?.次序儲存方式只好用于儲存線性結(jié)構(gòu)?！尽痢?.線性表采納鏈式儲存時，結(jié)點和結(jié)點內(nèi)部的儲存空間能夠不連續(xù)?！尽痢?.在一個設有頭指針和尾指針的單鏈表中，履行刪除單鏈表最后一個結(jié)點的操作與鏈表的長度沒關(guān)。三、填空題1.向一個長度為n的次序表中的第i個元素以前插入一個元素時，需要向后挪動n-i+1個元素。2.在一個長度為n的次序表中刪除第i個元素時，需要向前挪動n-i個元素。3.在單鏈表中設置頭結(jié)點的作用是簡化插入、刪除算法。4.在單鏈中要刪除某一指定結(jié)點，一定找到該結(jié)點的直接前驅(qū)結(jié)點。5.接見單鏈表中的結(jié)點，一定沿著指針域挨次進行。6.在雙鏈表中每個結(jié)點有兩個指針域，一個指向直接前驅(qū)結(jié)點，一個指向直接后繼結(jié)點。7.在雙向循環(huán)鏈表中，刪除最后一個結(jié)點的算法時間復雜度為O(1)。8.接見一個線性表中擁有給定值的時間復雜度的數(shù)目級是O(n)。9.由n個數(shù)據(jù)元素生成一個次序表，若每次都調(diào)用插入算法把一個元素插入到表頭，則整個算法的時間復雜度為O(n)，若每次都調(diào)用插入算法把一個元素插入到表尾，則2整個算法的時間復雜度為O(n)。10.在11.依據(jù)

雙向鏈表中，能夠用表尾指針取代表頭指針。n個數(shù)據(jù)元素成立對應的次序表和單鏈表儲存結(jié)構(gòu)，

其算法的時間復雜度最好的狀況是

O(n)

，最壞的狀況是

O(n2)

。12.求線性表的次序儲存和鏈式儲存的長度的算法時間復雜度分別是O(n)。

O(1)

和13.在一個帶頭結(jié)點的單鏈表中，在表頭插入或刪除與在其余地點插入或刪除，其操作過程能否同樣？同樣。14.在一個不帶頭結(jié)點的單鏈表中，在表頭插入或刪除與在其余地點插入或刪除，其操作過程能否同樣？不同樣。四、簡答題1.論述次序表和鏈表儲存方式的特色。答：次序表儲存方式為數(shù)據(jù)分派連續(xù)的儲存單元，數(shù)據(jù)元素按邏輯次序挨次儲存到相應儲存單元中，使得邏輯相鄰的數(shù)據(jù)元素物理也相鄰，所以能夠?qū)崿F(xiàn)隨機接見線性表的數(shù)據(jù)元素，即數(shù)據(jù)接見的時間復雜度為O(1)。鏈表儲存方式分派的儲存單元能夠不連續(xù)，經(jīng)過每個結(jié)點的指針域來表示數(shù)據(jù)元素之間的邏輯關(guān)系，只好次序接見線性表中的數(shù)據(jù)元素。若屢次地對一個線性表進行插入和刪除操作，則該線性表宜采納何種儲存結(jié)構(gòu)，為什么？答：若屢次地對一個線性表進行插入和刪除操作，則該線性表宜采納鏈式儲存結(jié)構(gòu)。由于鏈式儲存結(jié)構(gòu)在插入和刪除數(shù)據(jù)元素時不需要挪動數(shù)據(jù)元素，只需要改正結(jié)點的指針域就能夠改變數(shù)據(jù)元素之間的邏輯關(guān)系。3.在單鏈表、雙向循環(huán)鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點，不知道頭指針，可否將結(jié)點p從相應的鏈表中刪除？若能夠，時間復雜度各為多少。答：要實現(xiàn)刪除p結(jié)點的操作，一定找到其前驅(qū)結(jié)點，改正其指針域的值使其指向p的后繼結(jié)點，以實現(xiàn)刪除結(jié)點p。單鏈表不可以，由于不知道頭指針就沒法找到結(jié)點p的前驅(qū)結(jié)點。雙向循環(huán)鏈表和單循環(huán)鏈表能夠能夠?qū)崿F(xiàn)刪除p結(jié)點。單循環(huán)鏈表刪除p結(jié)點的時間復雜度為O(n)，雙循環(huán)鏈表刪除P結(jié)點的時間復雜度為O(1)。4.對鏈表設置頭結(jié)點的作用是什么？答：對帶頭結(jié)點的鏈表，在表的任何結(jié)點以前插入結(jié)點或刪除任何地點的結(jié)點，所要做的都是改正前一個結(jié)點的指針域，由于在帶頭結(jié)點的鏈表中任何元素結(jié)點都有前驅(qū)結(jié)點。如果沒有頭結(jié)點，在首元結(jié)點前插入結(jié)點或刪除首元結(jié)點都要改正頭指針，其算法要比帶頭結(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，此中的元素按值遞加有序擺列，設計一個算法插入一個值為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;}3.寫一個算法，從次序表中刪除值為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;}第三章棧和行列一、單項選擇題1.對于棧操作數(shù)據(jù)的原則是【C】。A.先進先出B.后進后出C.后進先出D.不分次序2.行列的先進先出特色是指【A】。最后插入行列的元素老是最后被刪除當同時進行插入、刪除操作時，老是插入操作優(yōu)先每當有刪除操作時，總要先做一次插入操作每次從隊中刪除的元素老是最早插入的元素3.與次序棧對比較，鏈棧有一個比較顯然的優(yōu)勢是【A.往常不會出現(xiàn)棧滿的狀況B.插入操作更簡單實現(xiàn)C.往常不會出現(xiàn)棧空的狀況D.刪除操作更簡單實現(xiàn)

A】。4.棧和行列的共同點是【C】。A.都是先進先出B.都是后進后出C.只同意在端點處進行插入和刪除D.無共同點5.棧的特色是【①B】，行列的特色是【②A】；棧和行列都是【③1，2，3，4，則【④A】是不可以能的出棧序列；若進行列的序列是

C】若入棧序列是1，2，3，4，則【⑤】是可能的出隊序列。①②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.用單鏈表表示的鏈行列的隊頭在鏈表的【A】。A.鏈頭B.鏈尾C.鏈中D.都不是7.設入棧序列為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,58.輸入序列是ABC，若輸出序列變?yōu)镃BA，經(jīng)過的棧操作為【B】。A.push,pop,push,pop,push,poppush,push,push,pop,pop,poppush,push,pop,pop,push,poppush,pop,push,push,pop,pop棧在【D】應用。遞歸調(diào)用B.函數(shù)調(diào)用C.表達式求值D.A,B,C10.設計一個鑒別表達式中左、右括號能否配對的算法，采納【A.線性表的次序儲存結(jié)構(gòu)B.行列C.線性表的鏈式儲存結(jié)構(gòu)D.棧11.同意對行列進行的操作有【D】。A.對行列中的元素排序B.拿出近來進隊的元素C.在隊頭以前插入元素D.刪除隊頭元素

D】數(shù)據(jù)結(jié)構(gòu)最正確。12.對于循環(huán)行列【

D】。A.沒法判斷行列能否為空C.行列不可以能滿

B.沒法判斷行列能否為滿D.以上說法都不對13.行列寄存在

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)14.行列寄存在

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)15.循環(huán)行列的最大容量為

M，則隊空的條件是【

A】。A.rear==frontB.(rear+1)%M==frontC.rear+1==frontD.(rear-1)%M==front16.循環(huán)行列的最大容量為M，則隊滿的條件是【B】。A.rear==frontB.(rear+1)%M==frontC.rear+1==frontD.(rear-1)%M==front二、判斷題【×】1.行列在函數(shù)調(diào)用時必不可以少，所以遞歸離不開行列?！尽獭?.棧和行列的儲存方式，既能夠是次序方式，又能夠是鏈式方式?！尽獭?.設尾指針的循環(huán)鏈表表示行列，則入隊和出隊算法的時間復雜度為0(1)。【×】4.行列邏輯上是一個上端和下端既能增添又能減少的線性表?！尽獭?.在鏈行列中，即便不設置尾指針也能進行入隊操作?！尽獭?.棧和行列度是限制存取點的線性結(jié)構(gòu)?！尽痢?.即便對不含同樣元素的同一輸入序列進行兩組不一樣的合法的入棧和出棧操作，所得的輸出序列必定同樣?！尽獭?.棧是實現(xiàn)函數(shù)調(diào)用所必要的數(shù)據(jù)結(jié)構(gòu)。【√】9.次序行列中的元素個數(shù)，能夠依據(jù)隊首指針和隊尾指針的值計算出來。三、填空題1.循環(huán)行列的引入，目的是為了戰(zhàn)勝次序行列的假溢出。2.劃分循環(huán)行列的空與滿有3種方法，它們是少用一個元素、設空滿標記、用計數(shù)器記錄行列中元素個數(shù)。3.棧和行列的差異是棧只好在表一端進行插入和刪除操作，行列限制在表的一端進行插入操作，在另一端進行刪除操作。4.一個棧的輸入序列是12345，則棧的輸出序列43512是錯誤的。5.設棧采納次序儲存結(jié)構(gòu)，棧中已有i-1個元素，則第i個元素進棧操作的算法時間復雜度是O（1）。6.若用不帶頭結(jié)點的單鏈表表示棧，則創(chuàng)立一個空棧要履行的操作是7.從循環(huán)行列中刪除一個元素的操作是Q.front=(Q.front+1)%QSize8.從循環(huán)行列中插入一個元素的操作是Q.rear=(Q.rear+1)%QSize9.判斷鏈行列中只有一個結(jié)點的條件是Q.front->next==Q.rear10.假如棧的最大長度不可以估量，最好使用鏈棧。

top=NULL。。。

。四、簡答題1.為何說棧是一種后進先出表？答：由于棧是限制在表的一端進行插入和刪除操作，所此后入棧的數(shù)據(jù)元素老是先出棧，所以說棧是一種后進先出表。2.對于一個棧，其輸入序列是A,B,C,試給出所有可能的輸出序列。答：可能的出棧序列是：ABC、ACB、BAC、BCA、CBA。3.何謂行列上溢？何為假溢出現(xiàn)象？有哪些解決假溢出問題的方法，并分別論述其工作原理。答：行列上溢指內(nèi)行列的次序儲存分派中，所有單元中已有元素，再進行插入操作時稱為行列上溢。假溢出指內(nèi)行列的次序儲存分派中，分派給行列的儲存空間有儲存單元未被占用，但依照操作規(guī)則而使進隊的數(shù)據(jù)元素沒法進隊的現(xiàn)象。解決假溢出問題的方法是內(nèi)行列的次序儲存分派中，分派給行列的儲存空間能夠循環(huán)使用，其進來源理是用表示隊頭和隊尾指針與分派給行列的儲存空間長度進行取模運算。即：入隊操作：Q.rear=(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.簡述線性表、棧和行列的異同？答：棧和行列都是操作地點受限的線性表，即對插入和刪除操作的地點加以限制。棧是僅同意在表的一端進行插入和刪除操作的線性表，因此是后進先出表。行列是同意在表的一端進行插入，在表的另一端進行刪除的線性表，因此是先進先出表。線性表能夠在任何地點進行插入和刪除操作。五、算法設計題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);}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);}DestroyStack(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.串是隨意有限個【

D】。A.符號構(gòu)成的會合C.字符構(gòu)成的會合

B.符號構(gòu)成的序列D.字符構(gòu)成的序列2.串是一種特別的線性表，其特別性表此刻【B】。A.能夠次序儲存B.數(shù)據(jù)元素是一個字符C.數(shù)據(jù)元素能夠使多個字符D.能夠鏈接儲存3.兩個串相等必有串長度相等且【B】。A.串的各地點字符隨意B.串中各地點字符均對應相等C.兩個串含有同樣的字符D.兩個串所含字符隨意4.設有兩個串p和q，求q在p中初次出現(xiàn)的地點的運算稱著【A.連結(jié)B.模式般配C.求子串D.求串長

B】。二、填空1.空串是長度為0的串。2.一個串中隨意連續(xù)字符構(gòu)成的子序列稱為該串的子串。3.設s=“abcd”，則履行語句s2=Substr(s,2,2)后，s2=“bc”4.空白串是由一個或多個空格字符構(gòu)成的串，其長度等于個數(shù)。

。其所包含的空格字符的第五章數(shù)組一、單項選擇題1.一維數(shù)組與線性表的差異是【A】。前者長度固定，后者長度可變后進長度固定，前者長度可變二者長度均固定D.二者長度均可變2.多維數(shù)組的數(shù)組元素之間的關(guān)系，【A】。A.是線性的B.是樹型的既是線性的，又是樹型的既不是線性的，也不是樹型的3.設有數(shù)組A[8][10]，每個元素占3個儲存單元，寄存該數(shù)組的儲存單元數(shù)為【

C】。A.80

B.100

C.240

D.2704.設有數(shù)組【D】。

A[8][10]

，每個元素占

3個儲存單元，首地點為

SA，則元素

[7][5]

的開端地點是A.SA+141

B.SA+144

C.SA+222

D.SA+2255.設有一個

n*n

的對稱矩陣，采納壓縮儲存，則存入內(nèi)存的元素個數(shù)為【

C】。A.n*n

B.n*n/2

C.n*(n+1)/2

D.(n+1)2/26.設元素

A是一個ai,j在B

n*n的對稱矩陣，壓縮儲存到一個一維數(shù)組中的地點是【A】。

B[0..n(n+1)/2-1]

中，則下三角部分A.i(i-1)/2+j-1

B.i(i-1)/2+jC.i(i+1)/2+j-1

D.i(i+1)/2+j7.稀少矩陣一般的壓縮方法有兩種，即【C】。A.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組和十字鏈表D.散列和十字鏈表8.設有一個10*10的對稱矩陣A，以行主序次進行壓縮儲存，的地點是1，則A8,5的開端地點是【B】。

每個元素占一個儲存單元，

a1,1A.13

B.33

C.18

D.40二、解答題1.設數(shù)組A[50][80]，其基地點為2000，每個元素占2個儲存單元，以行序位主序次序存儲，回答以下問題：1）該數(shù)據(jù)組由多少元素？2）該數(shù)組占用多少儲存單元？3）數(shù)組元素a[30][30]的儲存地點是多少？答：1）該數(shù)組有：50*80=4000個元素2）該數(shù)組占用4000*4=8000個儲存單元3）loc(30,30)=2000+(30*80+30)*2=2000+4860=6860第六章樹與二叉樹一、單項選擇題1.有關(guān)二叉樹以下說法正確的選項是【B】。A.二叉樹的度為2B.一棵二叉樹的度能夠小于2C.一棵二叉樹起碼有一個結(jié)點的度為2D.二叉樹中任何一個結(jié)點的度為22.利用二叉鏈表儲存樹，則根結(jié)點的右指針是【C】。A.指向最左孩子B.指向最右孩子C.空D.非空3.若一棵二叉樹擁有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)為【B】。A.9B.11C.15D.不確立4.一棵二叉樹有1001個結(jié)點，此中葉結(jié)點的個數(shù)為【D】。A.250B.490C.254D.不確立5.一棵完整二叉樹有1001個結(jié)點，此中葉結(jié)點的個數(shù)為【D】。A.250B.500C.254D.以上答案均不對6.一棵擁有1025個結(jié)點的二叉樹的高h為【C】。A.11B.11C.11至1025之間D.10至1024之間7.一棵124個葉結(jié)點的完整樹，最多擁有【B】個結(jié)點。A.247B.248C.249D.2518.一棵擁有10個葉結(jié)點的二叉樹擁有【B】度為2的結(jié)點。A.8B.9C.10D.119.已知一棵完整二叉樹有625個結(jié)點，葉結(jié)點的個數(shù)為【C】。A.311B.312C.313D.其余10.一棵擁有n個結(jié)點的完整二叉樹的高h為【AB】。A.log2n+1B.log2n+1C.log2n+1D.log2n-111.由8個權(quán)值結(jié)構(gòu)一棵哈夫曼樹，該哈夫曼樹有【A】個結(jié)點。A.15B.16C.17D.1412.由3個結(jié)點能夠結(jié)構(gòu)【D】種不一樣的二叉樹。A.2B.3C.4D.513.樹最適適用來表示【C】。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素間擁有分支層次關(guān)系的數(shù)據(jù)D.元素間無聯(lián)系的數(shù)據(jù)14.以下圖中4棵二叉樹中，【C】不是完整二叉樹。A.B.C.D.15.某二叉樹的先序遍歷序列和后序便利序列正好相反，則該二叉樹必定是【A】。A.空或只有一個結(jié)點B.完整二叉樹C.二叉排序樹D.高度等于其結(jié)點數(shù)16.在一棵非空二叉樹的中序遍歷序列中，根結(jié)點的右側(cè)【A】。A.只有右子樹上的所有結(jié)點B.只有右子樹上的部分結(jié)點C.只有左子樹上的部分結(jié)點D.只有左子樹上的所有結(jié)點17.任何一棵二叉樹的葉子結(jié)點在先序、中序和后序遍歷序列中的相對序次【A】。A.不發(fā)生上改變B.發(fā)生改變C.不可以確立D.以上都不對18.一棵滿二叉樹，m個葉結(jié)點，n個結(jié)點，深度為h，則【D】。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-119.設n，m是二叉樹上的兩個結(jié)點，在中序遍歷時，n在m以前的條件是【C】。A.n在m右方B.n是m的先人C.n在m左方D.n是m的后代20.設高度為h的二叉樹上只有度為0和度為2的結(jié)點，則此類二叉樹中包含的結(jié)點數(shù)最少為【B】。A.2hB.2h-1C.2h+1D.h+1二、判斷題【×】1.二叉樹是一般樹的特別樹型?！尽獭?.樹與二叉樹是兩種不一樣的樹形結(jié)構(gòu)?！尽痢?.對于有n個結(jié)點的二叉樹，其高度為log2n?！尽獭?.完整二叉樹中，若一個沒有左孩子，則它必然是葉結(jié)點?！尽獭?.一棵擁有n個結(jié)點的完整二叉樹，從上到下、從左到右用自然數(shù)對結(jié)點進行編號，結(jié)點為i的結(jié)點的左孩子的編號為2i(2i<n)。【×】6.一棵樹中的葉結(jié)點數(shù)必定等于與其對應的二叉樹的葉結(jié)點數(shù)?！尽獭?.哈夫曼樹是帶權(quán)路徑長度最短的樹，路經(jīng)上權(quán)值較大的結(jié)點離根近來。【√】8.哈夫曼樹的結(jié)點個數(shù)不偶數(shù)。三、填空題1.深度為k的完整二叉樹起碼有2K-1個結(jié)點，至多有2K-1個結(jié)點。2.在一棵二叉樹中，度為0的結(jié)點個數(shù)為n0，度為2的結(jié)點個數(shù)為n2,則有n0=n2+1。3.一棵二叉樹第i層最多有i-1n個結(jié)點的滿二叉樹共有K-12個結(jié)點，一棵有2個結(jié)點，共有2K-1個葉結(jié)點。4.依據(jù)二叉樹的定義，擁有3個結(jié)點的二叉樹共有5種不一樣形態(tài)，它們分別是。5.在一棵完整二叉樹中，結(jié)點個數(shù)為n，則編號最大的分支結(jié)點的編號為.n/2。在一棵完整二叉樹中，編號i和j的兩個結(jié)點處于同一層的條件是.log2i==.log2j。7.擁有n個結(jié)點的二叉樹采納二叉鏈表儲存結(jié)構(gòu)，共有n+1個空指針域。8.擁有n個結(jié)點的二叉樹中，假如有m個葉結(jié)點，則必定有m-1個度為2的結(jié)點，有n-2m+1個度為1的結(jié)點。在二叉樹的鏈式儲存結(jié)構(gòu)中，指針p所指結(jié)點為葉結(jié)點的條件是p->lchild==NULL&&p->rchild==NULL。10.二叉樹的先序序列和中序序列相等的條件是任何結(jié)點至多只有右子樹。11.有一棵以以下圖所示的樹，回答以下問題：①這棵樹的根結(jié)點是a。②這棵樹的葉子結(jié)點是b,e,g,d。③結(jié)點c的度為2。④這棵樹的深度是4。⑤結(jié)點c的孩子結(jié)點是e,f。⑥結(jié)點c的雙親結(jié)點是a。⑦這棵樹的度是3。abcdefg12.樹與二叉樹的兩個主要差異是樹中結(jié)點的最大度沒有限制，二叉樹結(jié)點的最大度限制為2、樹的結(jié)點無左右之分，二叉樹的的結(jié)點有左右之分。13.樹中任一結(jié)點同意有0個或多個孩子個孩子結(jié)點，除根結(jié)點以外，其余結(jié)點有1個雙親結(jié)點。四、簡答題1.設有以以下圖所示的二叉樹，給出其前序、中序和后序遍歷結(jié)果。答：前序序列：eadcbifghj中序序列：abcdiefhgj后序序列：bcidahjgfeeafgdcjhib2.給出以下圖所示的樹的二叉樹表示。eadfcbhgijk答：以下圖為其樹的二叉樹表示。eadcfjbhgk

i3.有一份電文共有5個字符：a,b,c,d,e,它們出現(xiàn)的頻次挨次為4，7，5，2，9，結(jié)構(gòu)對應的哈夫曼樹，求哈夫曼樹的帶權(quán)路徑長度和每個字符的哈夫曼編碼。271116579624字符編碼：a：011b：10c：00d：010e：114.假定一棵二叉樹采納次序儲存結(jié)構(gòu)，以以下圖所示。05101520eafdgcjhib回答些列問題：①畫出二叉樹表示。②寫出先序、中序和后序遍歷結(jié)果③寫出結(jié)點c的雙親結(jié)點和左、右孩子結(jié)點④畫出此二叉樹復原成叢林的圖答：①二叉樹表示以以下圖所示。eafdgcjhib②先序序列為：eadcbjfghi中序序列為：acbdjefhgi后序序列為：bcjdahigfe③結(jié)點c的雙親結(jié)點是d，左孩子為b，無右孩子④該二叉樹對應的叢林為efgiadjhcb第七章圖一、單項選擇題1.在一個無向圖中，所有極點的度數(shù)之和等于所有邊的【C】倍。A.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個極點的無向圖，若采納毗鄰矩陣表示，則該矩陣的大小是【D】。A.nB.(n-1)2C.(n-1)D.n27.對某個無向圖的毗鄰矩陣來說，【A】。A.第i行上的非0元素個數(shù)等于第i列上非0元素個數(shù)B.矩陣中非0元素個數(shù)等于圖中的邊數(shù)C.第i行、第i列上非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二、判斷題【×】1.n個極點的無向圖至多有n(n-1)條邊?！尽獭?.有向圖中，各極點的入度之和等于各極點的出度之和?！尽獭?.毗鄰矩陣只儲存了邊的信息，沒有儲存極點的信息?！尽痢?.連通重量是無向圖的極小連通子圖。?！尽痢?.假如表示有向圖的毗鄰矩陣是對稱的，則該有向圖必定是完整有向圖?！尽痢?.假如表示圖的毗鄰矩陣是對稱的，則該圖必定是無向圖?！尽獭?.假如表示圖的毗鄰矩陣不是對稱的，則該圖必定是有向圖。三、填空題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.對于n的極點的無向圖，采納毗鄰矩陣表示，求圖中邊的方法是計算毗鄰矩陣中元素值為1的個數(shù)素的值能否為1，再除以內(nèi)行值為1的元素個數(shù)

，判斷隨意兩個極點能否有邊相連的方法是2，求隨意極點的度的方法是。

判斷對應毗鄰矩陣元求毗鄰矩陣中對應極點所10.對于n的極點的有向圖，采納毗鄰矩陣表示，求圖中邊的方法是計算毗鄰矩陣中元素值為1的個數(shù)，判斷隨意兩個極點能否有邊相連的方法是判斷對應毗鄰矩陣元素的值能否為1，求隨意極點的度的方法是求毗鄰矩陣中對應極點所內(nèi)行和列的元素值為1的個數(shù)。11.無向圖的連通重量指無向圖中最大連通子圖12.若無向圖有m條邊，，則表示該無向圖的毗鄰表中有

。2m

結(jié)點。四、簡答題1.從占用的儲存空間來看，對于濃密圖和稀少圖，采納毗鄰矩陣和毗鄰表那個更好些？答：從占用儲存空間看，濃密圖采納毗鄰矩陣更好，稀少圖采納毗鄰表更好。2.用毗鄰矩陣表示圖時，矩陣元素的個數(shù)與極點個數(shù)能否有關(guān)？與邊的條數(shù)能否有關(guān)？為何？。答：用毗鄰矩陣表示圖，矩陣元素的個數(shù)與圖的極點個數(shù)直接有關(guān)，與邊的條數(shù)沒關(guān)。2第九章查找一、單項選擇題1.次序查找法適合于儲存結(jié)構(gòu)為【B】的查找表。A.散列儲存B.次序儲存或鏈式儲存C.壓縮儲存D.索引儲存2.對查找表進行折半查找時，要求查找表一定【B】。以次序方式儲存以次序方式儲存，且結(jié)點按要點字有序擺列以鏈式方式儲存以鏈式方式儲存，且結(jié)點按要點字有序擺列3.采納次序查找法查找長度為n的查找表時，每個元素查找的均勻查找長度為【

C】。A.n

B.n/2

C.(n+1)/2

D.(n-1)/24.采納折半查找法查找長度為

n的查找表時，每個元素查找的均勻查找長度為【

D】。A.O(n2)

B.O(nlog2n)

C.O(n)

D.O(log2n)5.采納分塊查找時，若查找表中有

625個元素，查找每個元素的概率同樣，假定對索引表和塊都采納次序查找，每塊應分【

B】個結(jié)點最正確。A.10

B.25

C.6

D.6256.查找n個元素的有序表時，最有效的查找方法是【A.次序查找B.分塊查找C.折半查找

C】。D.二叉排序樹7.假如要求一個查找表既能迅速查找，又能適應動向變化的要求，能夠采納【

A】查找方法。A.分塊

B.次序

C.折半

D.散列8.在要點字隨機散布的狀況下，用二叉排序樹的方法進行查找，其查找長度與【B】量級相當。A.次序查找

B.折半查找

C.分塊查找

D.前三個都不正確9.查找效率最高的二叉排序樹是【C】。所有結(jié)點的左子樹都為空的二叉排序樹所有結(jié)點的右子樹都為空的二叉排序樹均衡二叉樹沒有左子樹的二叉排序樹10.假定有k個要點字互為同義詞，若用線性探測再散列法把這列表中，起碼要進行【D】次探測。

k個要點字的紀錄插入到散A.k-1B.kC.k+1D.k(k+1)/211.以下說法錯誤的選項是【B】。散列法儲存的基本思想是由記錄要點字決定數(shù)據(jù)儲存地點散列法的結(jié)點中只包含數(shù)據(jù)元素自己的信息，不包含任何指針裝填因子是散列法的一個重要參數(shù)，它反應了散列表的裝填程度散列表的查找效率取決于散列造表是的散列函數(shù)和矛盾辦理的方法12.散列表的均勻查找長度【A】。與矛盾辦理方法有關(guān)而與表的長度沒關(guān)與矛盾辦理方法沒關(guān)而與表的長度有關(guān)與矛盾辦理方法有關(guān)且與表的長度有關(guān)與矛盾辦理方法沒關(guān)且與表的長度沒關(guān)二、判斷題【√】1.次序查找法適合于次序或鏈式儲存結(jié)構(gòu)的查找表?！尽痢?.次序查找法只好在次序儲存結(jié)構(gòu)長進行?！尽痢?.二分查找能夠在有序的雙向鏈表長進行。【×】4.在二叉排序樹中，每個結(jié)點的要點字比左孩子的要點字大，比右孩子的要點字小?！尽痢?.每個結(jié)點的要點字都比左孩子的要點字大，比右孩子的要點字小，這樣的二叉樹都是二叉排序樹?！尽獭?.哈希儲存法只好儲存數(shù)據(jù)元素的值，不可以儲存數(shù)據(jù)元素之間的關(guān)系?！尽痢?.哈希矛盾是指同一個要點字對應多個不一樣的哈希地點。三、填空題1.次序查找含n個元素的次序表，若查找成功，則比較要點字的次數(shù)最多為n次；若查找不可以功，則比較要點字的次數(shù)為n+1次。2.在含有n個元素的有序次序表中進行二分查找，最大的比較次數(shù)是.log2n+1。3.用二分查找一個查找表，該查找表一定擁有的特色是次序儲存且要點字有序。4.分塊查找發(fā)將待查找的表均勻地分紅若干塊且塊中諸記錄的次序能夠是隨意的，但塊與塊之間要點字有序。5.在分塊查找方法中，第一查找要點字表，而后再查找相應的對應的塊。6.用二叉排序樹在n個元素中進行查找，最壞狀況下查找時間復雜度為O(n)，最好狀況的查找時間復雜度為O(log2n)。7.折半查找的儲存結(jié)構(gòu)僅限于次序儲存結(jié)構(gòu)，且是要點字有序擺列。8.一個無序序列能夠經(jīng)過結(jié)構(gòu)一棵二叉排序樹而變?yōu)橛行蛐蛄?，結(jié)構(gòu)樹的過程即是對無序序列進行排序的過程。9.用二叉排序樹查找，在最壞的狀況下，均勻查找長度為（n+1）/2，最好的情況下，均勻查找長度為.(log2n+1)-1。10.在哈希函數(shù)H(key)=key/p中，p最好取小于或等于m的最大質(zhì)數(shù)。11.哈希表是經(jīng)過將要點字按選定的哈希函數(shù)和矛盾辦理方法，把記錄按要點字變換為地點進行儲存的儲存表，哈希方法的要點是選擇好的哈希函數(shù)和矛盾辦理的方法。一個好的哈希函數(shù)其變換地點應盡可能均勻，并且函數(shù)運算應盡可能簡單。四、解答題1、畫出對長度為10的右序表進行折半查找的一棵判斷樹，并求其等概