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

1、2012年數(shù)據(jù)結(jié)構(gòu)期末考試題及答案一、選擇題1在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為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叮部結(jié)構(gòu)和外部結(jié)構(gòu)2數(shù)據(jù)結(jié)構(gòu)在計算機內(nèi)存中的表示是指A叮據(jù)的存儲結(jié)構(gòu)B叮據(jù)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)3在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的ADDDB叮儲C叮輯和存儲DDOO4在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲D叮據(jù)元素之間的關(guān)系結(jié)構(gòu)。CA叮據(jù)的處理方法B叮據(jù)元素的類型C叮據(jù)元素之間的關(guān)系D叮據(jù)的存儲方法5在決定選取何種存儲結(jié)構(gòu)時，一般不考慮A叮結(jié)點的值如何B叮點個數(shù)的多少C叮數(shù)據(jù)有哪些運算D叮用的編程語言實現(xiàn)這種結(jié)構(gòu)是否方

2、便。7算法分析的目的是(1)A叮出數(shù)據(jù)結(jié)構(gòu)的合理性B叮究算法中的輸入和輸出的關(guān)系C叮析算法的效率以求改進C叮析算法的易讀性和文檔性(2DA叮間復雜度和時間復雜度B叮確性和簡明性C叮讀性和文檔性D叮據(jù)復雜性和程序復雜性8下面程序段的時間復雜度是O(n2DsD0；for(ID0；iDn；iDfor(jD0；jDn；jD6以下說法正確的是A叮據(jù)項是數(shù)據(jù)的基本單位B叮據(jù)元素是數(shù)據(jù)的最小單位C叮據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項的集合D叮些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)，算法分析的兩個主要方面是sDBij；sumDs；O(n*mD9下面程序段的時間復雜度是for(iD0；iDn；iDfor(jD0；jDm

3、；jDAijD0；10下面程序段的時間復雜度是O(log3nDiD0；while(iDDnDiDi*3；11在以下的敘述中，正確的是A叮性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)B叮維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C叮的操作方式是先進先出D叮列的操作方式是先進后出12通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著A叮據(jù)元素具有同一特點B叮僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應的數(shù)據(jù)項的類型要一致C叮個數(shù)據(jù)元素都一樣D叮據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等13鏈表不具備的特點是A叮隨機訪問任一結(jié)點B叮入刪除不需要移動元素C叮必事先估計存儲空間D叮需空間與其長度成正比14不帶頭結(jié)點的單

4、鏈表head為空的判定條件是nextDDNULLCDhead叮nextDDheadDhead!口NULL15D帶頭結(jié)點的單鏈表head為空的判定條件是nextDDNULLCDhead叮nextDDheadDhead！DNULL16D若某表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點，則采用存儲方式最節(jié)省運算時間。AD單鏈表BD給出表頭指針的單循環(huán)鏈表CD雙鏈表DD帶頭結(jié)點的雙循環(huán)鏈表17D需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲結(jié)構(gòu)是AD單鏈表BD靜態(tài)鏈表CD線性鏈表DD順序存儲結(jié)構(gòu)18D非空的循環(huán)單鏈表head的尾結(jié)點（由p所指向）滿足ADpDDnextD

5、DNULLBDpDDNULLCDpDDnextDDheadDDpDDhead19D在循環(huán)雙鏈表的p所指的結(jié)點之前插入所指結(jié)點的操作是ADpDDpriorDDpriorBDpDDpriorDDpriorCDsDDpriorDDnextDsDDsDDpriorDDprior20D如果最常用的操作是取第i個結(jié)點及其前驅(qū)，則采用存儲方式最節(jié)省時間。AD單鏈表BD雙鏈表CD單循環(huán)鏈表DD順序表21D在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然保持有序的時間復雜度是ADO（1）BDO（n）CDO（n2）DDO（nlog2n）22D在一個長度為訕nD1）的單鏈表上，設有頭和尾兩個指針，執(zhí)行B操作與鏈

6、表的長度有關(guān)。AD刪除單鏈表中的第一個元素BD刪除單鏈表中的最后一個元素CD在單鏈表第一個元素前插入一個新元素DD在單鏈表最后一個元素后插入一個新元素23D與單鏈表相比，雙鏈表的優(yōu)點之一是AD插入、刪除操作更簡單BD可以進行隨機訪問CD可以省略表頭指針或表尾指針DD順序訪問相鄰結(jié)點更靈活24D如果對線性表的操作只有兩種，即刪除第一個元素，在最后一個元素的后面插入新元素，則最好使用AD只有表頭指針沒有表尾指針的循環(huán)單鏈表BD只有表尾指針沒有表頭指針的循環(huán)單鏈表CD非循環(huán)雙鏈表D叮環(huán)雙鏈表25在長度為n的順序表的第i個位置上插入一個元素D1DiDnD1),元素的移動次數(shù)為：ADn-iD1BDn-i

7、CiDDi-26D對于只在表的首、尾兩端進行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為AD順序表BD用頭指針表示的循環(huán)單鏈表DD單鏈表CD用尾指針表示的循環(huán)單鏈表27D下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點A插入運算方便B可方便地用于各種邏輯結(jié)構(gòu)的存儲表示C存儲密度大D刪除運算方便28D下面關(guān)于線性表的敘述中，錯誤的是哪一個A線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B線性表采用順序存儲，便于進行插入和刪除操作。C線性表采用鏈式存儲，不必占用一片連續(xù)的存儲單元D線性表采用鏈式存儲，便于進行插入和刪除操作。的有限序列。29D線性表是具有AD字符BD數(shù)據(jù)元素CD數(shù)據(jù)項DD表元素30D在n個結(jié)點的線性表的數(shù)組

8、實現(xiàn)中，算法的時間復雜度是0(1)的操作是AD訪問第i(1DDiDDn)個結(jié)點和求第i個結(jié)點的直接前叮1DiDDn)BD在第i(1DDiDDn)個結(jié)點后插入一個新結(jié)點CD刪除第i(1DDiDDn）個結(jié)點DD以上都不對C。31D若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復雜度為AD0（0）BD0（1）CD0（n）DD0（n2）32D對于順序存儲的線性表，訪問結(jié)點和增加、刪除結(jié)點的時間復雜度為AD0（n）0（n）BD0（n）0（1）CD0（1）0（n）DD0（1）0（1）33DD00Da1，a2，,an)以鏈式方式存儲，訪問第i位置元素的時間復雜度為AD0（0）B

9、D0（1）CD0（n）DD0（n2）34D單鏈表中，增加一個頭結(jié)點的目的是為了AD使單鏈表至少有一個結(jié)點BD標識表結(jié)點中首結(jié)點的位置CD方面運算的實現(xiàn)35D在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是DD說明單鏈表是線性表的鏈式存儲ADpDDnextDpDDnextDpDDnextDs；CDpDDnextDsDDnextDsDDnext；pDDnextDsBD順序存取的存儲結(jié)構(gòu)DDHash存取的存儲結(jié)構(gòu)36D線性表的順序存儲結(jié)構(gòu)是一種AD隨機存取的存儲結(jié)構(gòu)CD索引存取的存儲結(jié)構(gòu)37D棧的特點是B,隊列的特點是AD先進先出BD先進后出38D棧和隊列的共同點是AD都是先進后出BD都是

10、先進先出CD只允許在端點處插入和刪除元素DD沒有共同點39D一個棧的進棧序列是a，b，c，d,e,則棧的不可能的輸出序列是ADedcbaBDdecbaCDdceabDDabcde40設有一個棧，元素依次進棧的順序為A、B、CDD、EDOOC是不可能的出棧序列。ADA,B,C,D,EBDB,C,D,E,ACDE,A,B,C,DDE，D，C，B，A41以下B不是隊列的基本運算A叮隊尾插入一個新元素B叮隊列中刪除第i個元素D叮取隊頭元素的值1,2,3,n,其輸出序列為p1，p2，p3，pn,若p1Dn,則piC叮斷一個隊列是否為空49D輸入序列為ABC,可以變?yōu)镃BA時，經(jīng)過的棧操作為ADpush,

11、pop,push,pop,push,popBDpush,push,push,pop,pop,popCDpush,push,pop,pop,push,popDDpush,pop,push,push,pop,pop50D若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V1m,toplDtop2分別代表第1和第2個棧的棧頂,棧1的底在Vl,棧2的底在Vm,則棧滿的條件是AD|top2Dtop1|D0BDtop11Dtop2CDtop1top2DmDDtop1Dtop251D設計一個判別表達式中左、右括號是否配對出現(xiàn)的算法，采用D數(shù)據(jù)結(jié)構(gòu)最佳。AD線性表的順序存儲結(jié)構(gòu)52D允許對隊列進行的操作有AD對隊列中的

12、元素排序CD在隊頭元素之前插入元素53D對于循環(huán)隊列AD無法判斷隊列是否為空BD隊列CD線性表的鏈式存儲結(jié)構(gòu)D。BD取出最近進隊的元素DD刪除隊頭元素D。BD無法判斷隊列是否為滿DD棧CD隊列不可能滿DD以上說法都不對54D若用一個大小為6的數(shù)值來實現(xiàn)循環(huán)隊列,且當前rear和front的值分別為0和3,當從隊列中刪除一個元素,再加入兩個元素后,rear和front的值分別為BAD1和5BD2和4CD4和2DD5和1ADiBDnDiCDnDi1DD不確定43D判定一個順序棧st（最多元素為MaxSize）為空的條件是B。ADstDDtop！topDDD1CDstDDtop！topDDMaxSi

13、ze44D判定一個順序棧st（最多元素為MaxSize）為滿的條件是D。ADstDDtop！topDDD1CDstDDtop！topDDMaxSize45D一個隊列的入隊序列是1,23,4,則隊列的輸出序列是B。AD4,3,2,1BD1,2,3,4CD1,4,3,2DD3,2,4,146D判定一個循環(huán)隊列qu（最多元素為MaxSize）為空的條件是C。ADquDDrear-quDDrear-quDDfrontD1DDMaxSizeCDquDDfrontD147D在循環(huán)隊列中，若front與rear分別表示對頭元素和隊尾元素的位置,則判斷循環(huán)隊列空的條C。ADfrontDDrear1BDrear

14、DDfront1CDfrontDDrearDDfrontDD48D向一個棧頂指針為h的帶頭結(jié)點的鏈棧中插入指針s所指的結(jié)點時，應執(zhí)行D操作。42若已知一個棧的進棧序列是C件是ADhDDnextDhnextDhDDCDsDDnextDs；055D隊列的“先進先出”特性是指AD最早插入隊列中的元素總是最后被刪除BD當同時進行插入、刪除操作時,總是插入操作優(yōu)先CD每當有刪除操作時,總是要先做一次插入操作DD每次從隊列中刪除的總是最早插入的元素56和順序棧相比，鏈棧有一個比較明顯的優(yōu)勢是A操作時A叮常不會出現(xiàn)棧滿的情況C叮入操作更容易實現(xiàn)B通常不會出現(xiàn)?？盏那闆rD叮除操作更容易實現(xiàn)57用不帶頭結(jié)點的單

15、鏈表存儲隊列，其頭指針指向隊頭結(jié)點，尾指針指向隊尾結(jié)點，則在進行出隊A叮修改隊頭指針B叮修改隊尾指針C叮頭、隊尾指針都可能要修改D叮頭、隊尾指針都要修改58D00S叮Software,其子串的數(shù)目是A8B37C36D959串的長度是指A叮中所含不同字母的個數(shù)B叮中所含字符的個數(shù)C叮中所含不同字符的個數(shù)D叮中所含非空格字符的個數(shù)60串是一種特殊的線性表，其特殊性體現(xiàn)在A叮以順序存儲B叮據(jù)元素是一個字符C叮以鏈式存儲D叮據(jù)元素可以是多個字符61設有兩個串p和q,求在p中首次出現(xiàn)的位置的運算稱為ADDOB模式匹配CDOOODDOOD62數(shù)組A中，每個元素的長度為3個字節(jié)，行下標8，列下標1到10，從

16、首地址SAD始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素A85的起始地址為ASA141BSA144CSA222DSA22563數(shù)組A中，每個元素的長度為3個字節(jié)，行下標8，列下標1到10，從首地址SAD始連續(xù)存放的存儲器內(nèi)，該數(shù)組按行存放，元素A58的起始地址為ASA141BSA180CSA222DSA22564若聲明一個浮點數(shù)數(shù)組如下：froataverage口newfloat30；假設該數(shù)組的內(nèi)存起始位置為200,average15的內(nèi)存地址是A214B215C260D25665設二維數(shù)組A1m,1n按行存儲在數(shù)組B中，則二維數(shù)組元素Ai,j在一維數(shù)組B中的下An*（i1）jBn*（i1）j

17、1Ci*（j66有一個100D90的稀疏矩陣,非0元素有10,設每個整型數(shù)占時,所需的字節(jié)數(shù)是B。A20B66C18000D3367數(shù)組A04,13,57中含有的元素個數(shù)是A55B45C36D16標為68對矩陣進行壓縮存儲是為了1）Dj*mi12個字節(jié),則用三元組表示該矩陣ADOODOB方便存儲C叮高運算速度D叮少存儲空間儲地址為69設有一個10階的對稱矩陣A,采用壓縮存儲方式,以行序為主存儲,al,1為第一個元素，其存1,每個元素占1個地址空間,則a8,5的地址為A13B33C18D4070稀疏矩陣一般的壓縮存儲方式有兩種,即A叮維數(shù)組和三維數(shù)組B三元組和散列C叮元組和十字鏈表D散列和十字鏈

18、表71樹最適合用來表示A叮序數(shù)據(jù)元素B叮序數(shù)據(jù)元素72深度為5的二叉樹至多有C個結(jié)點。A16BD32CD31C1073對一個滿二叉樹，m個葉子,n個結(jié)點，深度為h,則ADnDhDmBhDmD2nCmDhD1nD2hD174任何一棵二叉樹的葉子結(jié)點在前序、中序和后序遍歷序列中的相對次序A叮發(fā)生改變B叮生改變CDOODOD叮上都不對75在線索化樹中，每個結(jié)點必須設置一個標志來說明它的左、右鏈指向的是樹結(jié)構(gòu)信息，還是線索化信息，若0標識樹結(jié)構(gòu)信息，1標識線索，對應葉結(jié)點的左右鏈域，應標識為A00B01C10D1176在下述論述中，正確的是只有一個結(jié)點的二叉樹的度為0；二叉樹的度為2；二叉樹的左右子樹

19、可任意交換；深度為K的順序二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。ADDDDB叮CDDDDDDD77設森林F對應的二叉樹為B,它有m個結(jié)點，B的根為p,p的右子樹的結(jié)點個數(shù)為n,森林第一棵樹的結(jié)點的個數(shù)是AmDnBmDnDCnDDOODO78若一棵二叉樹具有10個度為2的結(jié)點,5個度為1的結(jié)點,則度為0的結(jié)點的個數(shù)是A9B11C15DDOODO79具有10個葉子結(jié)點的二叉樹中有B個度為2的結(jié)點。A8B9CD10DD11倍。80在一個無向圖中,所有頂點的度數(shù)之和等于所有邊數(shù)的AD1/2B1B倍。81在一個有向圖中,所有頂點的入度之和等于所有頂點的出度之和的AD1/2B182某二叉樹結(jié)點的中

20、序序列為ABCDEFG,后序序列為BDCAFGE,則其左子樹中結(jié)點數(shù)目為：A3B2C4D83已知一算術(shù)表達式的中綴形式為ADB*C-D/E,后綴形式為ABC*DDE/-,其前綴形式為A-ADB*C/DEB-ADB*CD/EC-D*ABC/DEDD-DA*BC/DEA_；DADa,b,e,c,d,Ba,c,f,e,b,CDa,e,b,c,f,d,DDa,e,d,f,c,bDADa,b,c,e,d,BDa,b,c,e,f,CDa,e,b,c,f,d,DDa,c,f,d,e,84已知一個圖,如圖所示,若從頂點a出發(fā)按深度搜索法進行遍歷，則可能得到的一種頂點序列為D_；按廣度搜索法進行遍歷,則可能得到

21、的一種頂點序列為85D采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的_A_。AD先序遍歷BD中序遍歷CD后序遍歷DD按層遍歷86D采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的D_。AD先序遍歷BD中序遍歷CD后序遍歷DD按層遍歷87D具有n個結(jié)點的連通圖至少有A條邊。ADnD1BDnCDn(nD1)/2DD2n(a),a)的表頭是C,表尾是88D廣義表(AaB（）C（a）D（a）89廣義表（a）的表頭是，表尾是AaB（）a）D（a）90順序查找法適合于存儲結(jié)構(gòu)為B的線性表。A散列存儲B順序存儲或鏈式存儲C壓縮存儲D索引存儲91對線性表進行折半查找時，要求線性表必須A以順序方式存儲以順

22、序方式存儲，且結(jié)點按關(guān)鍵字有序排列C以鏈式方式存儲以鏈式方式存儲，且結(jié)點按關(guān)鍵字有序排列92采用折半查找法查找長度為n的線性表時，每個元素的平均查找長度為AO（n2）BO（nlog2n）CO（n）DO（log2n）93有一個有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當折半查找值為82的結(jié)點時，次比較后查找成功。A11小于其右孩子的值。94二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點的值均大于其左孩子的值、這種說法A正確B錯誤95下面關(guān)于BDOB叮的敘述中，不正確的結(jié)論是ABDOB叮都能有效的支持順序查找BDOB叮都能有效的支持隨機查找CBDOB叮都是平衡

23、的多叉樹BDOB叮都可用于文件索引結(jié)構(gòu)96以下說法錯誤的是A叮列法存儲的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲地址B叮列表的結(jié)點中只包含數(shù)據(jù)元素自身的信息，不包含指針。C叮載因子是散列表的一個重要參數(shù)，它反映了散列表的飽滿程度。D叮列表的查找效率主要取決于散列表構(gòu)造時選取的散列函數(shù)和處理沖突的方法。97叮找效率最高的二叉排序樹是A叮有結(jié)點的左子樹都為空的二叉排序樹。B叮有結(jié)點的右子樹都為空的二叉排序樹。C叮衡二叉樹。D叮有左子樹的二叉排序樹。98排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為C。AD0D00B。冒泡排序C插入排序D。選擇排

24、序99在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是DAD0D00B叮泡排序C叮接插入排序D叮接選擇排序100堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列D是一個堆。A94，31，53，23，16，72B94，53，31，72，16，23C16，53，23，94，31，72D16，31，23，94，53，72101堆排序是一種B排序。AD00B叮擇CD0DDDD0102D在鏈表中進行操作比在順序表中進行操作效率高。ADD0D0B叮半查找CD0DD0DD00103直接選擇排序的時間復雜度為D。（n為元素個數(shù)）AO（n）BO（log2n）CO（nlog2n）DO（n2）二、填空題。合稱

25、非線性結(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)中元素1數(shù)據(jù)邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)三種類型，樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)之間存在多對多關(guān)系。5在樹形結(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)劣主要考慮正確

26、性、可讀性、健壯性和時間復雜度與空間復雜度。8評估一個算法的優(yōu)劣,通常從時間復雜度和空間復雜度兩個方面考察。9算法的5個重要特性是有窮性、確定性、可行性、輸入和輸出。10叮一個長度為n的順序表中刪除第i個元素時，需向前移動ni1個元素。11在單鏈表中，要刪除某一指定的結(jié)點，必須找到該結(jié)點的12在雙鏈表中，每個結(jié)點有兩個指針域，一個指向13在順序表中插入或刪除一個數(shù)據(jù)元素，需要平均移動置有關(guān)。14當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表的元素是，應采用順序存儲結(jié)構(gòu)。15根據(jù)線性表的鏈式存儲結(jié)構(gòu)中每一個結(jié)點包含的指針個數(shù)，將線性鏈表分成表和雙鏈表。16順序

27、存儲結(jié)構(gòu)是通過下標表示元素之間的關(guān)系的；的關(guān)系的。17叮頭結(jié)點的循環(huán)鏈表L中只有一個元素結(jié)點的條件是前驅(qū)結(jié)點。前驅(qū)結(jié)點,另一個指向后繼結(jié)點。n個數(shù)據(jù)元素,移動數(shù)據(jù)元素的個數(shù)與位單鏈鏈式存儲結(jié)構(gòu)是通過指針表示元素之間LDDnextDDnextDL。后進先出的原則。19空串是零個字符的串，其長度等于于其包含的空格個數(shù)。20組成串的數(shù)據(jù)元素只能是單個字符21一個字符串中任意個連續(xù)字符構(gòu)成的部分22子串”str”在主串”datastructure”23叮維數(shù)組M的每個元素是6個字符組成的串，行下標10,則存放M至少需要540個字節(jié)；M的第8列和第24稀疏矩陣一般的壓縮存儲方法有兩種，即25D0D0D(

28、a),(b),c),(dDDDDODOO26在一棵二叉樹中，度為零的結(jié)點的個數(shù)為零?？瞻状怯梢粋€或多個空格字符組成的串,其長度等稱為該串的子串。中的位置是5。i的范圍從0到8,列下標j的范圍從1到5行共占108個字節(jié)。三元組表和十字鏈表。3,深度是4。n0,度為2的結(jié)點的個數(shù)為n2,則有n0D18棧是限定僅在表尾進行插入或刪除操作的線性表，其運算遵循n21。27D00n個結(jié)點的二叉鏈表中，空鏈域的個數(shù)為n1_。28D0D0n個葉子結(jié)點的哈夫曼樹共有2nD1_個結(jié)點。29深度為5的二叉樹至多有31個結(jié)點。30若某二叉樹有20個葉子結(jié)點,有30個結(jié)點僅有一個孩子,則該二叉樹的總結(jié)點個數(shù)為6931

29、某二叉樹的前序遍歷序列是abdgcefh,中序序列是dgbaechf,其后序序列為gdbehfca32線索二叉樹的左線索指向其遍歷序列中的前驅(qū),右線索指向其遍歷序列中的后繼33在各種查找方法中,平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是散列查找法35一個無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個有序序列，構(gòu)造樹的過程即為對無序序列進行排序的過程。36具有10個頂點的無向圖，邊的總數(shù)最多為_45_。37口已知圖G的鄰接表如圖所示，其從頂點vl出發(fā)的深度優(yōu)先搜索序列為_v1v2v3v6v5v4_,其從頂點vl出發(fā)的廣度優(yōu)先搜索序列為_vlv2v5v4v3v6_。34在分塊索引查找方法中，首先查找索

30、引表，然后查找相應的塊表38索引是為了加快檢索速度而引進的一種數(shù)據(jù)結(jié)構(gòu)。一個索引隸屬于某個數(shù)據(jù)記錄集，它由若干索引項組成，索引項的結(jié)構(gòu)為關(guān)鍵字和關(guān)鍵字對應記錄的地址39Prim算法生成一個最小生成樹每一步選擇都要滿足邊的總數(shù)不超過n1當前選擇的邊的權(quán)值是候選邊中最小的，選中的邊加入樹中不產(chǎn)生回路三項原則。40在一棵m階B樹中，除根結(jié)點外，每個結(jié)點最多有棵子樹，最少有m/2棵子樹。三、判斷題。1在決定選取何種存儲結(jié)構(gòu)時，一般不考慮各結(jié)點的值如何。DDD2抽象數(shù)據(jù)類型(ADT)包括定義和實現(xiàn)兩方面，其中定義是獨立于實現(xiàn)的，定義僅給出一個ADT的邏輯特性，不必考慮如何在計算機中實現(xiàn)。3抽象數(shù)據(jù)類型與計算機內(nèi)部表示和實現(xiàn)無關(guān)。DD4順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。5線性表采用鏈式存儲結(jié)構(gòu)時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。6對任何數(shù)據(jù)結(jié)構(gòu)鏈式存儲結(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。7順序存儲方式只能用于存儲線性結(jié)構(gòu)。8集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。9線性表中