2023年數(shù)據(jù)結(jié)構(gòu)期末考試題及答案

20２３年數(shù)據(jù)結(jié)構(gòu)期末考試題及答案一、選擇題１．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為C。A．動態(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)存中的表達是指A。A．數(shù)據(jù)的存儲結(jié)構(gòu)B．數(shù)據(jù)結(jié)構(gòu)C．數(shù)據(jù)的邏輯結(jié)構(gòu)D．數(shù)據(jù)元素之間的關(guān)系3.在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的A結(jié)構(gòu)。A．邏輯B．存儲C.邏輯和存儲D.物理4．在存儲數(shù)據(jù)時,通常不僅要存儲各數(shù)據(jù)元素的值，并且還要存儲C。Ａ．數(shù)據(jù)的解決方法B.數(shù)據(jù)元素的類型C．數(shù)據(jù)元素之間的關(guān)系D．數(shù)據(jù)的存儲方法5．在決定選取何種存儲結(jié)構(gòu)時,一般不考慮Ａ。Ａ．各結(jié)點的值如何B．結(jié)點個數(shù)的多少C.對數(shù)據(jù)有哪些運算D.所用的編程語言實現(xiàn)這種結(jié)構(gòu)是否方便。６.以下說法對的的是D。A.數(shù)據(jù)項是數(shù)據(jù)的基本單位B．數(shù)據(jù)元素是數(shù)據(jù)的最小單位C.數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項的集合D．一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)7．算法分析的目的是C,算法分析的兩個重要方面是A。（１)A．找出數(shù)據(jù)結(jié)構(gòu)的合理性Ｂ．研究算法中的輸入和輸出的關(guān)系Ｃ．分析算法的效率以求改善C．分析算法的易讀性和文檔性（2）Ａ.空間復雜度和時間復雜度Ｂ.對的性和簡明性Ｃ.可讀性和文檔性D．數(shù)據(jù)復雜性和程序復雜性8.下面程序段的時間復雜度是O(n2）。s=0;for（Ｉ＝０；i＜n；i＋+）foｒ(j＝0；j＜n；ｊ++）s＋＝B［i］［ｊ]；ｓｕm＝ｓ;9．下面程序段的時間復雜度是O(n*m）。ｆoｒ(i＝0;ｉ<n；i+＋）ｆｏｒ(j＝0；j<m；ｊ＋＋)A[ｉ][j］＝０;10.下面程序段的時間復雜度是O(ｌog3n）。i=０;ｗhｉle（i<=n）ｉ=ｉ*３；11.在以下的敘述中，對的的是B。A.線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)B.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C.棧的操作方式是先進先出D.隊列的操作方式是先進后出12．通常規(guī)定同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性,這意味著B。A.數(shù)據(jù)元素具有同一特點Ｂ．不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，并且相應的數(shù)據(jù)項的類型要一致C．每個數(shù)據(jù)元素都同樣D．數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等１３．鏈表不具有的特點是A。A.可隨機訪問任一結(jié)點B.插入刪除不需要移動元素Ｃ．不必事先估計存儲空間D．所需空間與其長度成正比14．不帶頭結(jié)點的單鏈表hｅad為空的鑒定條件是A。ｎext==ＮULLC．head－＞ｎｅxt==heａdDhead！=NUＬL15．帶頭結(jié)點的單鏈表hｅaｄ為空的鑒定條件是B。neｘt==NULLC．ｈead－>next=＝ｈeadDhｅad!=NULL16．若某表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點，則采用D存儲方式最節(jié)省運算時間。A．單鏈表Ｂ．給出表頭指針的單循環(huán)鏈表C．雙鏈表D．帶頭結(jié)點的雙循環(huán)鏈表１７.需要分派較大空間,線插入和刪除不需要移動元素的性表，其存儲結(jié)構(gòu)是Ｂ。Ａ．單鏈表Ｂ.靜態(tài)鏈表C.線性鏈表D.順序存儲結(jié)構(gòu)18.非空的循環(huán)單鏈表head的尾結(jié)點(由p所指向）滿足C。A．ｐ－＞nexｔ==NULＬB．p＝=ＮULLC．ｐ->nｅｘt==ｈeａdＤ.p==ｈead19．在循環(huán)雙鏈表的p所指的結(jié)點之前插入s所指結(jié)點的操作是D。Ａ．p－＞pｒioｒ－＞priorB.p－>pｒｉｏr－>ｐriorC．s->ｐriｏr－>ｎext=sD．ｓ-＞prioｒ->priｏｒ＝s20.假如最常用的操作是取第ｉ個結(jié)點及其前驅(qū),則采用Ｄ存儲方式最節(jié)省時間。A．單鏈表B.雙鏈表C．單循環(huán)鏈表D.順序表21.在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然保持有序的時間復雜度是B。A.O（1）B.O（n)C．O(n2）Ｄ.O（nlｏg２n）２2．在一個長度為n(n＞1）的單鏈表上，設(shè)有頭和尾兩個指針,執(zhí)行Ｂ操作與鏈表的長度有關(guān)。Ａ.刪除單鏈表中的第一個元素B．刪除單鏈表中的最后一個元素C．在單鏈表第一個元素前插入一個新元素D．在單鏈表最后一個元素后插入一個新元素２3．與單鏈表相比，雙鏈表的優(yōu)點之一是Ｄ。Ａ．插入、刪除操作更簡樸B．可以進行隨機訪問Ｃ.可以省略表頭指針或表尾指針D.順序訪問相鄰結(jié)點更靈活2４.假如對線性表的操作只有兩種,即刪除第一個元素，在最后一個元素的后面插入新元素，則最佳使用Ｂ。A．只有表頭指針沒有表尾指針的循環(huán)單鏈表B．只有表尾指針沒有表頭指針的循環(huán)單鏈表C．非循環(huán)雙鏈表D．循環(huán)雙鏈表25.在長度為n的順序表的第i個位置上插入一個元素（１≤i≤n+1）,元素的移動次數(shù)為：A。A.ｎ–ｉ+１B.n–iC．ｉD.i–1２6．對于只在表的首、尾兩端進行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為C。A.順序表B．用頭指針表達的循環(huán)單鏈表Ｃ．用尾指針表達的循環(huán)單鏈表D．單鏈表２7.下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點?C。A插入運算方便B可方便地用于各種邏輯結(jié)構(gòu)的存儲表達C存儲密度大D刪除運算方便2８.下面關(guān)于線性表的敘述中，錯誤的是哪一個?B。A線性表采用順序存儲,必須占用一片連續(xù)的存儲單元B線性表采用順序存儲，便于進行插入和刪除操作。Ｃ線性表采用鏈式存儲，不必占用一片連續(xù)的存儲單元Ｄ線性表采用鏈式存儲,便于進行插入和刪除操作。29．線性表是具有ｎ個B的有限序列。A．字符B.數(shù)據(jù)元素C．數(shù)據(jù)項Ｄ．表元素30.在ｎ個結(jié)點的線性表的數(shù)組實現(xiàn)中,算法的時間復雜度是O(1）的操作是Ａ。A.訪問第i（1＜＝i＜＝ｎ)個結(jié)點和求第i個結(jié)點的直接前驅(qū)(1＜i＜=n）B．在第i(1＜=i<=n)個結(jié)點后插入一個新結(jié)點Ｃ．刪除第i（1＜=ｉ<＝n)個結(jié)點D.以上都不對31．若長度為n的線性表采用順序存儲結(jié)構(gòu),在其第i個位置插入一個新元素的算法的時間復雜度為Ｃ。A．O（０)Ｂ．O(1）C.O（n）D.Ｏ(n2）３2．對于順序存儲的線性表,訪問結(jié)點和增長、刪除結(jié)點的時間復雜度為C。A.O（n）Ｏ(n）B.O(n）O(1）Ｃ.Ｏ（1）O(ｎ)D.O(１)O(1）33.線性表（a1,a2，…，aｎ）以鏈式方式存儲,訪問第ｉ位置元素的時間復雜度為Ｃ。A．Ｏ（0)Ｂ.O(1)C．Ｏ（ｎ）D.O(n2）３4．單鏈表中，增長一個頭結(jié)點的目的是為了C。A.使單鏈表至少有一個結(jié)點B．標記表結(jié)點中首結(jié)點的位置Ｃ.方面運算的實現(xiàn)Ｄ.說明單鏈表是線性表的鏈式存儲35.在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點,對的的操作是Ｂ。Ａ.p-＞ｎext＝p->nｅxt＝ｐ－>ｎeｘt=s;Ｃ.p-＞nexｔ＝s－＞next＝s-＞ｎｅｘt；ｐ-＞next=ｓ３6．線性表的順序存儲結(jié)構(gòu)是一種A。A.隨機存取的存儲結(jié)構(gòu)Ｂ.順序存取的存儲結(jié)構(gòu)C.索引存取的存儲結(jié)構(gòu)D．Haｓh存取的存儲結(jié)構(gòu)３７.棧的特點是B，隊列的特點是A。Ａ．先進先出B.先進后出３8．棧和隊列的共同點是Ｃ。A．都是先進后出B.都是先進先出C．只允許在端點處插入和刪除元素D．沒有共同點３9．一個棧的進棧序列是a,b，c,ｄ,e,則棧的不也許的輸出序列是C。Ａ.edcbａB.decbaＣ.dceabD.abcｄe４0.設(shè)有一個棧，元素依次進棧的順序為A、Ｂ、C、D、Ｅ。下列C是不也許的出棧序列。A.A，B，C，Ｄ,ＥB．B,Ｃ,Ｄ,E，AＣ.Ｅ，A,Ｂ，C,DＤ.E,D,C,B,A41.以下B不是隊列的基本運算?A．從隊尾插入一個新元素B．從隊列中刪除第i個元素C.判斷一個隊列是否為空D．讀取隊頭元素的值４2．若已知一個棧的進棧序列是1，2,3,,n,其輸出序列為ｐ1，ｐ2，p３，…,ｐn,若ｐ１＝ｎ,則ｐi為C。A.iB．n-ｉC．n-i＋1D．不擬定43．鑒定一個順序棧st(最多元素為MaxSize)為空的條件是B。A.sｔ->top!toｐ＝＝－1C.st->toｐ！ｔoｐ=＝MａxＳize44．鑒定一個順序棧st(最多元素為MaｘSｉｚｅ)為滿的條件是D。A．ｓｔ－>toｐ!top=＝－1C.ｓｔ->toｐ!top＝＝MaｘSiｚe４5．一個隊列的入隊序列是1，2，3,4,則隊列的輸出序列是B。A.4，3，２,１B.１,２,３,4C.1,4，3，2D．3,２，4,１46.鑒定一個循環(huán)隊列ｑu(最多元素為MａｘＳize)為空的條件是C。Ａ．qu－＞reaｒ–qu－＞ｒeaｒ–ｑu-＞front－1＝=MaｘSiｚｅＣ.qｕ－>ｆront－１47．在循環(huán)隊列中，若frｏnt與rear分別表達對頭元素和隊尾元素的位置,則判斷循環(huán)隊列空的條件是C。A．frｏnt=＝rｅａr+１B．reａｒ＝=froｎt+1C.front＝=rearD．front＝＝0４8.向一個棧頂指針為h的帶頭結(jié)點的鏈棧中插入指針s所指的結(jié)點時,應執(zhí)行D操作。A.h-＞ｎext＝h；C.s->next=h->next＝s；4９．輸入序列為ABC，可以變?yōu)椋肂Ａ時，通過的棧操作為B。Ａ.ｐｕｓｈ,pop，pｕsh,pｏp，push，pｏｐB(yǎng).puｓｈ,ｐuｓh，ｐｕsh，pop，pop,pｏpC．ｐush，ｐush，ｐop,pop，pｕsh,popD．pｕsh,pop,pｕsh，ｐush,pｏｐ,ｐｏp50.若棧采用順序存儲方式存儲,現(xiàn)兩棧共享空間V[1ｍ]，ｔop[１]、top[2］分別代表第1和第2個棧的棧頂,棧１的底在V[1],棧2的底在V[ｍ]，則棧滿的條件是B。A．|top[２]-ｔoｐ[1]｜＝0B．top[1]＋１=ｔoｐ[2]C．tｏp[1]＋ｔop[２]=ｍD.ｔop[1］=tｏp[２]51．設(shè)計一個判別表達式中左、右括號是否配對出現(xiàn)的算法，采用Ｄ數(shù)據(jù)結(jié)構(gòu)最佳。A.線性表的順序存儲結(jié)構(gòu)B.隊列C.線性表的鏈式存儲結(jié)構(gòu)D.棧52．允許對隊列進行的操作有D。Ａ．對隊列中的元素排序B．取出最近進隊的元素Ｃ．在隊頭元素之前插入元素D.刪除隊頭元素５3.對于循環(huán)隊列D。Ａ.無法判斷隊列是否為空B．無法判斷隊列是否為滿C.隊列不也許滿D．以上說法都不對54.若用一個大小為６的數(shù)值來實現(xiàn)循環(huán)隊列，且當前rｅar和frｏnt的值分別為0和3,當從隊列中刪除一個元素，再加入兩個元素后,reaｒ和front的值分別為Ｂ。Ａ．１和5B．2和4C.4和２Ｄ.5和１５５．隊列的“先進先出”特性是指D。Ａ.最早插入隊列中的元素總是最后被刪除B.當同時進行插入、刪除操作時,總是插入操作優(yōu)先C．每當有刪除操作時,總是要先做一次插入操作D．每次從隊列中刪除的總是最早插入的元素56.和順序棧相比，鏈棧有一個比較明顯的優(yōu)勢是Ａ。A.通常不會出現(xiàn)棧滿的情況B．通常不會出現(xiàn)?？盏那闆rC.插入操作更容易實現(xiàn)D．刪除操作更容易實現(xiàn)57．用不帶頭結(jié)點的單鏈表存儲隊列，其頭指針指向隊頭結(jié)點,尾指針指向隊尾結(jié)點，則在進行出隊操作時C。A．僅修改隊頭指針Ｂ.僅修改隊尾指針C.隊頭、隊尾指針都也許要修改D．隊頭、隊尾指針都要修改58．若串S＝‘ｓoftwarｅ’，其子串的數(shù)目是B。N（n+１)／2+1個空串=A.8B.３7C.３6D．９59．串的長度是指B。Ａ．串中所含不同字母的個數(shù)B．串中所含字符的個數(shù)Ｃ.串中所含不同字符的個數(shù)Ｄ．串中所含非空格字符的個數(shù)60．串是一種特殊的線性表,其特殊性體現(xiàn)在Ｂ。A.可以順序存儲Ｂ．數(shù)據(jù)元素是一個字符C.可以鏈式存儲Ｄ．數(shù)據(jù)元素可以是多個字符61．設(shè)有兩個串p和q,求q在p中初次出現(xiàn)的位置的運算稱為B。A.連接B.模式匹配C．求子串D．求串長62.數(shù)組A中,每個元素的長度為3個字節(jié)，行下標i從1到８，列下標j從1到１0，從首地址ＳA開始連續(xù)存放的存儲器內(nèi),該數(shù)組按行存放,元素A[8]［5]的起始地址為C。[(8-１）*10+（５-1）］*3A．ＳA+141B.SＡ＋14４C．SA＋222D．ＳA＋22５6３.數(shù)組A中，每個元素的長度為3個字節(jié),行下標ｉ從1到８,列下標j從1到１0,從首地址ＳＡ開始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素A[5］[8]的起始地址為Ｃ。Ａ．SA+14１B．ＳＡ＋180C．ＳA＋２22Ｄ．SA＋２2564.若聲明一個浮點數(shù)數(shù)組如下：ｆｒoatavｅrage[]=newflｏａt(yī)[30］；假設(shè)該數(shù)組的內(nèi)存起始位置為200,averａge[15]的內(nèi)存地址是C。Ａ.214B.2１5Ｃ．26０Ｄ.2566５．設(shè)二維數(shù)組A[1…ｍ,１…n]按行存儲在數(shù)組B中，則二維數(shù)組元素A[i,j］在一維數(shù)組Ｂ中的下標為A。A.n＊（i－1)＋jB．ｎ*（i－1）+ｊ-1C．i*（ｊ-１)Ｄ．j*ｍ＋i－1６6．有一個100×9０的稀疏矩陣,非０元素有1０,設(shè)每個整型數(shù)占２個字節(jié),則用三元組表達該矩陣時,所需的字節(jié)數(shù)是B。A.20B．66Ｃ.18000Ｄ．３36７．數(shù)組A[0…４，－1…-３，5…7]中具有的元素個數(shù)是A。A.５5B．4５Ｃ．36D.１６６8．對矩陣進行壓縮存儲是為了Ｄ。A．方便運算B.方便存儲Ｃ．提高運算速度D．減少存儲空間69.設(shè)有一個10階的對稱矩陣A,采用壓縮存儲方式,以行序為主存儲，a1,1為第一個元素,其存儲地址為1,每個元素占１個地址空間,則a8，5的地址為Ｂ。A.13B．33C．18D．4０70.稀疏矩陣一般的壓縮存儲方式有兩種，即C。A．二維數(shù)組和三維數(shù)組B．三元組和散列C.三元組和十字鏈表D．散列和十字鏈表71．樹最適合用來表達C。A.有序數(shù)據(jù)元素B．無序數(shù)據(jù)元素C．元素之間具有分支層次關(guān)系的數(shù)據(jù)Ｄ．元素之間無聯(lián)系的數(shù)據(jù)72．深度為５的二叉樹至多有C個結(jié)點。2的n方-1A．1６B．3２Ｃ．3１Ｃ.１０73．對一個滿二叉樹,m個葉子，n個結(jié)點,深度為h，則D。A.ｎ＝h＋mBｈ+m＝2ｎCm＝ｈ－１Dn=2h－1７４.任何一棵二叉樹的葉子結(jié)點在前序、中序和后序遍歷序列中的相對順序A。Ａ.不發(fā)生改變B．發(fā)生改變C.不能擬定D.以上都不對７５．在線索化樹中,每個結(jié)點必須設(shè)立一個標志來說明它的左、右鏈指向的是樹結(jié)構(gòu)信息,還是線索化信息,若0標記樹結(jié)構(gòu)信息，１標記線索,相應葉結(jié)點的左右鏈域,應標記為__D__。Ａ.0０B.01C.10D．1176．在下述論述中，對的的是D。①只有一個結(jié)點的二叉樹的度為０；②二叉樹的度為2；③二叉樹的左右子樹可任意互換；④深度為K的順序二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。A．①②③B.②③④C.②④D．①④77.設(shè)森林Ｆ相應的二叉樹為Ｂ,它有m個結(jié)點，B的根為p,p的右子樹的結(jié)點個數(shù)為ｎ，森林F中第一棵樹的結(jié)點的個數(shù)是A。A．ｍ－nＢ.m-ｎ－１C.n+1D．不能擬定7８.若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點,則度為0的結(jié)點的個數(shù)是B。A．9B．11C.15Ｄ．不能擬定79．具有10個葉子結(jié)點的二叉樹中有B個度為２的結(jié)點。性質(zhì)310-1=９A.8B.9C．１0Ｄ.11８０．在一個無向圖中,所有頂點的度數(shù)之和等于所有邊數(shù)的C倍。A．1/2Ｂ1C2D481．在一個有向圖中,所有頂點的入度之和等于所有頂點的出度之和的B倍。Ａ．1/2B1Ｃ２Ｄ482．某二叉樹結(jié)點的中序序列為ＡBCDＥFG,后序序列為BDＣＡＦGE，則其左子樹中結(jié)點數(shù)目為：ＣA．３B.2C．4D.583.已知一算術(shù)表達式的中綴形式為A＋Ｂ＊Ｃ–D/E,后綴形式為ABC*+DＥ／–,其前綴形式為D。Ａ．–A+B*C/DEB.–Ａ＋B*CＤ/ＥC–+＊ＡＢＣ/DED．–+A*BC／ＤＥ84.已知一個圖,如圖所示，若從頂點a出發(fā)按深度搜索法進行遍歷,則也許得到的一種頂點序列為__＿＿D＿__；按廣度搜索法進行遍歷,則也許得到的一種頂點序列為___Ａ＿＿＿；①A．a(chǎn)，b，ｅ,ｃ,ｄ,ｆB.a,c，f，e,b,ｄＣ.a,ｅ,b，c,f,d,D.a,ｅ，ｄ，f,c,b②Ａ.a,ｂ,c,e，d,fB.ａ，b,ｃ,e,f，ｄＣ.a,e,b，c,f,d，D.a,c,f，d,e,b85.采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的___Ａ＿__＿。Ａ.先序遍歷B．中序遍歷C．后序遍歷Ｄ.按層遍歷86.采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的_＿＿D____。A．先序遍歷B．中序遍歷C.后序遍歷D.按層遍歷８7．具有n個結(jié)點的連通圖至少有Ａ條邊。Ａ.n-1B．nC.n(n－１）／2D.2n88．廣義表（（a),ａ）的表頭是C，表尾是C。A.ａB(）C(a)D(（a）)89.廣義表((a))的表頭是Ｃ,表尾是Ｂ。A．a(chǎn)B(）Ｃ（ａ)D（（ａ)）9０．順序查找法適合于存儲結(jié)構(gòu)為B的線性表。Ａ散列存儲B順序存儲或鏈式存儲C壓縮存儲D索引存儲91.對線性表進行折半查找時，規(guī)定線性表必須B。A以順序方式存儲B以順序方式存儲，且結(jié)點按關(guān)鍵字有序排列C以鏈式方式存儲Ｄ以鏈式方式存儲,且結(jié)點按關(guān)鍵字有序排列92.采用折半查找法查找長度為ｎ的線性表時，每個元素的平均查找長度為D。AＯ（n2)BO（nloｇ２n)CＯ（ｎ)DＯ(log２n）93．有一個有序表為｛１，3,９，12，32,41,45,6２,75，77，８2,９5，100｝,當折半查找值為８2的結(jié)點時,Ｃ次比較后查找成功。A．11B５Ｃ4D89４．二叉樹為二叉排序樹的充足必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。這種說法Ｂ。A對的Ｂ錯誤95.下面關(guān)于Ｂ樹和B+樹的敘述中,不對的的結(jié)論是A。AB樹和B＋樹都能有效的支持順序查找BＢ樹和B＋樹都能有效的支持隨機查找CＢ樹和B＋樹都是平衡的多叉樹DB樹和B＋樹都可用于文獻索引結(jié)構(gòu)96．以下說法錯誤的是B。A．散列法存儲的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲地址B.散列表的結(jié)點中只包含數(shù)據(jù)元素自身的信息，不包含指針。C.負載因子是散列表的一個重要參數(shù)，它反映了散列表的飽滿限度。D.散列表的查找效率重要取決于散列表構(gòu)造時選取的散列函數(shù)和解決沖突的方法。９7.查找效率最高的二叉排序樹是C。Ａ．所有結(jié)點的左子樹都為空的二叉排序樹。B．所有結(jié)點的右子樹都為空的二叉排序樹。Ｃ．平衡二叉樹。D.沒有左子樹的二叉排序樹。9８.排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進行比較,將其放入已排序序列的對的位置上的方法,稱為C。Ａ.希爾排序Ｂ。冒泡排序C插入排序D。選擇排序99．在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列順序無關(guān)的是D。A．希爾排序B．冒泡排序Ｃ.直接插入排序D.直接選擇排序100.堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列D是一個堆。Ａ.94，31,５３，2３，16，7２B.94,53，３1，72，16，23C．１6，53，23，94,３1，７2D.16,３1，23，94，5３,７２101.堆排序是一種B排序。A.插入B．選擇Ｃ.互換Ｄ．歸并102.D在鏈表中進行操作比在順序表中進行操作效率高。A．順序查找B.折半查找Ｃ.分塊查找Ｄ．插入103．直接選擇排序的時間復雜度為D。（ｎ為元素個數(shù))A．O（n）B．O（log2n)C.O(nlog2ｎ）Ｄ.O(n２）二、填空題。１.數(shù)據(jù)邏輯結(jié)構(gòu)涉及線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)三種類型，樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱非線性結(jié)構(gòu)。2.數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)4種。3．在線性結(jié)構(gòu)中,第一個結(jié)點沒有前驅(qū)結(jié)點，其余每個結(jié)點有且只有1個前驅(qū)結(jié)點;最后一個結(jié)點沒有后續(xù)結(jié)點,其余每個結(jié)點有且只有1個后續(xù)結(jié)點。4.線性結(jié)構(gòu)中元素之間存在一對一關(guān)系,樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系,圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。５．在樹形結(jié)構(gòu)中,樹根結(jié)點沒有前驅(qū)結(jié)點,其余每個結(jié)點有且只有1個前驅(qū)結(jié)點;葉子結(jié)點沒有后續(xù)結(jié)點，其余每個結(jié)點的后續(xù)結(jié)點可以任意多個。6．數(shù)據(jù)結(jié)構(gòu)的基本存儲方法是順序、鏈式、索引和散列存儲。7．衡量一個算法的優(yōu)劣重要考慮對的性、可讀性、健壯性和時間復雜度與空間復雜度。8．評估一個算法的優(yōu)劣,通常從時間復雜度和空間復雜度兩個方面考察。9．算法的5個重要特性是有窮性、擬定性、可行性、輸入和輸出。10.在一個長度為n的順序表中刪除第i個元素時，需向前移動n－i－1個元素。11.在單鏈表中,要刪除某一指定的結(jié)點，必須找到該結(jié)點的前驅(qū)結(jié)點。12.在雙鏈表中，每個結(jié)點有兩個指針域，一個指向前驅(qū)結(jié)點,另一個指向后繼結(jié)點。１3.在順序表中插入或刪除一個數(shù)據(jù)元素,需要平均移動n個數(shù)據(jù)元素，移動數(shù)據(jù)元素的個數(shù)與位置有關(guān)。１4.當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作,但規(guī)定以最快的速度存取線性表的元素是,應采用順序存儲結(jié)構(gòu)。１5.根據(jù)線性表的鏈式存儲結(jié)構(gòu)中每一個結(jié)點包含的指針個數(shù)，將線性鏈表提成單鏈表和雙鏈表。16.順序存儲結(jié)構(gòu)是通過下標表達元素之間的關(guān)系的;鏈式存儲結(jié)構(gòu)是通過指針表達元素之間的關(guān)系的。1７．帶頭結(jié)點的循環(huán)鏈表Ｌ中只有一個元素結(jié)點的條件是Ｌ－>nexｔ->nexｔ=L。１8.棧是限定僅在表尾進行插入或刪除操作的線性表，其運算遵循后進先出的原則。19.空串是零個字符的串,其長度等于零?？瞻状怯梢粋€或多個空格字符組成的串,其長度等于其包含的空格個數(shù)。2０．組成串的數(shù)據(jù)元素只能是單個字符。21.一個字符串中任意個連續(xù)字符構(gòu)成的部分稱為該串的子串。22．子串”str”在主串”dａt(yī)ａstrｕcture”中的位置是5。23．二維數(shù)組Ｍ的每個元素是6個字符組成的串,行下標i的范圍從0到8,列下標ｊ的范圍從１到1０,則存放Ｍ至少需要５40個字節(jié);M的第8列和第5行共占１０8個字節(jié)。24．稀疏矩陣一般的壓縮存儲方法有兩種，即三元組表和十字鏈表。２５.廣義表((a），(（b),c），((（d）)））的長度是3，深度是４。26.在一棵二叉樹中，度為零的結(jié)點的個數(shù)為n0,度為2的結(jié)點的個數(shù)為ｎ２，則有n０＝ｎ2＋1。27.在有ｎ個結(jié)點的二叉鏈表中，空鏈域的個數(shù)為__n+1__。28.一棵有n個葉子結(jié)點的哈夫曼樹共有__２n－1_個結(jié)點。２9．深度為5的二叉樹至多有３１個結(jié)點。30．若某二叉樹有20個葉子結(jié)點，有3０個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點個數(shù)為69。3１.某二叉樹的前序遍歷序列是aｂdｇceｆh，中序序列是dｇbaechf，其后序序列為gdｂeｈfｃa。32．線索二叉樹的左線索指向其遍歷序列中的前驅(qū),右線索指向其遍歷序列中的后繼。33．在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是散列查找法。３4.在分塊索引查找方法中,一方面查找索引表,然后查找相應的塊表。３5.一個無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個有序序列,構(gòu)造樹的過程即為對無序序列進行排序的過程。36.具有10個頂點的無向圖,邊的總數(shù)最多為__4５__。37．已知圖G的鄰接表如圖所示，其從頂點v１出發(fā)的深度優(yōu)先搜索序列為_v1v2ｖ３v6ｖ5v４_，其從頂點v1出發(fā)的廣度優(yōu)先搜索序列為_v１v2ｖ5ｖ4v3v6_＿。38．索引是為了加快檢索速度而引進的一種數(shù)據(jù)結(jié)構(gòu)。一個索引從屬于某個數(shù)據(jù)記錄集,它由若干索引項組成，索引項的結(jié)構(gòu)為關(guān)鍵字和關(guān)鍵字相應記錄的地址。39.Prim算法生成一個最小生成樹每一步選擇都要滿足邊的總數(shù)不超過n-1,當前選擇的邊的權(quán)值是候選邊中最小的，選中的邊加入樹中不產(chǎn)生回路三項原則。40.在一棵m階Ｂ樹中,除根結(jié)點外,每個結(jié)點最多有m棵子樹，最少有m／2棵子樹。三、判斷題。1．在決定選取何種存儲結(jié)構(gòu)時，一般不考慮各結(jié)點的值如何。（√)2.抽象數(shù)據(jù)類型（ADT)涉及定義和實現(xiàn)兩方面,其中定義是獨立于實現(xiàn)的，定義僅給出一個ADT的邏輯特性，不必考慮如何在計算機中實現(xiàn)。(√)3．抽象數(shù)據(jù)類型與計算機內(nèi)部表達和實現(xiàn)無關(guān)。(√）4.順序存儲方式插入和刪除時效率太低,因此它不如鏈式存儲方式好。(×)５．線性表采用鏈式存儲結(jié)構(gòu)時,結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。（×