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

1、數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題、單選題1.A.C.2.A.C.3.A.C.某程序的時間復(fù)雜度為（O（n）O（n2）隊列的插入操作是在（隊首隊前二叉樹上葉結(jié)點數(shù)等于（113n+nlog2n+n2+8）,其數(shù)量級表示為（BDB)進(jìn)行。B.D.C)。O(nlog2n)O(log2n)隊尾對后B,單分支結(jié)點數(shù)加1D.雙分支結(jié)點數(shù)減14.A.C.5.A.C.6.A.C.7.A.C.8.A.C9.AC.C)。每次從無序表中取出一個元素，把它插入到有序表中的適當(dāng)位置，此種排序方法叫做A）排序插入選擇B.交換D.歸并在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（23隊列的刪除操作是在（隊首隊前當(dāng)利用大小為C）語句修改to

2、p+;top-;由權(quán)值分別為5153B.1D.4A）進(jìn)行。B.隊尾D.對后N的數(shù)組順序存儲一個棧時，假定用top指針。B.top=0;D.top=N;3,6,7,2,5的葉子結(jié)點生成一棵哈夫曼樹,在一棵二叉樹中，第3115B.23D744層上的結(jié)點數(shù)最多為（B）B.8D.1610.向堆中插入一個元素的時間復(fù)雜度為（A）。A.O（log2n）B.O（n）CO（1）D16O（nlog2n）A）倍。top=N表示棧空，則退棧時，用它的帶權(quán)路徑長度為（A)。11.在一個長度為n的順序存儲的線性表中，向第i個元素（1wiWn+1）之前插入一個新元素時，需要從后向前依次后移（B）個元素。A.n-iCn-i

3、-112.在線性表的散列存儲中,則裝填因子（等于（A）。B.n-i+1Di若用m表示散列表的長度,n表示待散列存儲的元素的個數(shù),A.n/mCn/(n+m)Bm/nDm/(n+m)13 .從一棵B樹刪除元素的過程中，若最終引起樹根結(jié)點的合并，則新樹高度是(B)。A.原樹高度加1B,原樹高度減1C.原樹高度D.不確定14 .在稀疏矩陣的帶行指針向量的鏈接存儲中，每個行單鏈表中的結(jié)點都具有相同的(A)。A.行號B.列號C.元素值D.地址15 .在一個具有n個頂點的無向圖中，要連通所有頂點則至少需要(C)條邊。A.nB.2nC.n-1D,n+116.17與上邊重復(fù)18 .在一棵二叉搜索樹中，每個分支結(jié)

4、點的左子樹上所有結(jié)點的值一定(A)該結(jié)點的值。A.小于B.大于C.不小于D.大于等于19 .對于一棵具有n個結(jié)點的樹，該樹中所有結(jié)點的度數(shù)之和為(A)。A.n-1B.nC.n+1D.2n20.某程序的時間復(fù)雜度為(3n+100xlog2n+nlog2n),其數(shù)量級表示為(B)。A.O(n)B.O(nlog2n)C.O(100)D.O(log2n)21 .設(shè)一組初始記錄關(guān)鍵字序列(5,2,6,3,8),以第一個記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為(C)。A.2,3,5,8,6B.3,2,5,8,6C.32568D.2365822 .根據(jù)n個元素建立一棵二叉搜索樹時，其時間復(fù)雜度大致為(B)

5、。A.O(n)B,O(log2n)C.O(n2)D.O(nlog2n)23 .按照數(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)24 .下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中正確的是A。A.數(shù)組是同類型值的集合B.遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為復(fù)雜C.樹是一種線性的數(shù)據(jù)結(jié)構(gòu)D.用一維數(shù)組存儲二叉樹，總是以先序順序遍歷各結(jié)點25 .在計算機(jī)的存儲器中表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為BA.邏輯結(jié)構(gòu)B.順序存儲結(jié)構(gòu)C鏈?zhǔn)酱鎯Y(jié)構(gòu)D.以上都不對26 .以下關(guān)于算法特性的描述中，B是正確的。(1)算法

6、至少有一個輸入和一個輸出(2)算法至少有一個輸出但是可以沒有輸入(3)算法可以永遠(yuǎn)運行下去A.(1)B.(2)C.(3)D.(2)和(3)27 .對順序存儲的線性表(a1,a2,an)進(jìn)行插入操作的時間復(fù)雜度是C。A.O(n)B.O(n-i)C.(n/2)D.O(n-1)28 .鏈表不具有的特點是AB.插入和刪除時不需要移動元素D.所需空間與線性表的長度成正比C。B.部分地址必須連續(xù)A.可隨機(jī)訪問任一元素C不必事先估計存儲空間29 .線性鏈表中各鏈結(jié)點之間的地址A.必須連續(xù)C不一定連續(xù)D.連續(xù)與否無關(guān)30 .以下關(guān)于鏈?zhǔn)酱鎯Y(jié)構(gòu)的敘述中，C是不正確的。A.結(jié)點除自身信息外還包括指針域，因此存儲

7、密度小于順序存儲結(jié)構(gòu)B.邏輯上相鄰的結(jié)點物理上不必鄰接C可以通過計算直接確定第i個結(jié)點的存儲地址D.插入、刪除操作方便，不必移動結(jié)點31 .設(shè)依次進(jìn)入一個棧的元素序列為d,a,c,b彳導(dǎo)不到出棧的元素序列為DA.dcbaB.acdbC.abcdD.cbda32 .將新元素插入到鏈?zhǔn)疥犃兄袝r，新元素只能插入到B。A.鏈頭B.鏈尾C.鏈中D.第i個位置，i大于等于1,大于等于表長加133 .設(shè)棧S和隊列Q的初始狀態(tài)為空，元素el、e2、e3、e4、e5和e6依次通過棧S,一個元素出棧后即進(jìn)入隊列Q,若6個元素出隊的順序是e2、e4、e3、e6、e5、和e1,則棧S容量至少應(yīng)該是CoA.6B.4C.

8、3D.234.下面D是abcd321ABCD'的子串。A.abcdB.321abC.'abcABC'D.21AB'35.假設(shè)8行10列的二維數(shù)組A18,110分別以行序為主序和以列序為主序順序存儲時,其首地址相同，那么以行序為主序時元素a3,5的地址與以列序為主序時C元素相同。A. a7,3B. a83C. a1,4D. ABC者B不對36 .數(shù)組A05,06的每個元素占5個字節(jié)，將其按列優(yōu)先次序存儲在起始地址為1000的內(nèi)存單元中，則元素A5,5的地址為A。A.1175B.1180C.1205D.121037 .下列廣義表中，長度為3的廣義表為BD.()A.(

9、a,b,c,()B.(g),(a,b,c,d,f),()C.(a,(b,(d)38 .在一個單鏈表中，若q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點，若在q與p之間插入一個s所指的結(jié)點，則執(zhí)行（D）。A.sflink=pflink;pflink=s;B.pflink=s;sflink=q;C.pTink=slink;sflink=p;D.qflink=s;sflink=p;39 .若樹T有a個度為1的結(jié)點，b個度為2的結(jié)點，c個度為3的結(jié)點，則該樹有D個葉結(jié)點。A.1+2b+3cB.a+2b+3cC.2b+3cD.1+b+2c40 .若一棵二叉樹有102片葉子結(jié)點，則度二叉樹度為2的結(jié)點數(shù)是BA.100B

10、.101C.102D.10341 .在有n個葉子結(jié)點的霍夫曼樹中，其結(jié)點總數(shù)為：D。A.nB.2nC.2n+1D.2n-142.具有12個結(jié)點的完全二叉樹有BB.5個度為2的結(jié)點A.5個葉子結(jié)點C.7個分支結(jié)點D.2個度為1的結(jié)點43.設(shè)結(jié)點x和y是二叉樹中的任意兩結(jié)點，若在先根序列中x在y之前，而后根序列中x在y之后，則x和y的關(guān)系是C。A.x是y的左兄弟B.x是y的右兄弟C.x是y的祖先D.x是y的后代44 .先序遍歷序列與中序遍歷序列相同的二叉樹為D。A.根結(jié)點無左子樹的二叉樹B.根結(jié)點無右子樹的二叉樹C.只有根結(jié)點的二叉樹或非葉子結(jié)點只有左子樹的二叉樹D.只有根結(jié)點的二叉樹或非葉子結(jié)點

11、只有右子樹的二叉樹45 .若二叉樹T的前序遍歷序列和中序遍歷序列分別是bdcaef和cdeabf,則其后序遍歷序列為A。A.ceadfbB.feacdbC.eacdfbD.以上都不對46 .設(shè)無向圖的頂點個數(shù)為n,則該圖最多有C條邊。A.n-1B.n(n-1)C.n(n-1)/2D.N47 .對于一個有n個頂點和e條邊的無向圖，若采用鄰接表表示，鄰接表中的結(jié)點總數(shù)是CA.e/2B.eC.n+2eD.n+e48 .無向圖G=(V,E),其中V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)。對該圖進(jìn)行深度優(yōu)先遍歷，下面不能得到的序列

12、是D。A.acfdebB.aebdfcC.aedfcbD.abecdf49 .直接插入排序在最好情況下的時間復(fù)雜度為B。A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)50 .對有n個記錄的表作快速排序，在最壞情況，算法的時間復(fù)雜度是D。A.O(n3)B.O(n)C.O(nlog2n)D.O(n2)30.下面的排序算法中,穩(wěn)定是AoA.直接插入排序法B.快速排序法C.直接選擇排序法D.堆排序法51.數(shù)據(jù)結(jié)構(gòu)是(C)A.一種數(shù)據(jù)類型B.數(shù)據(jù)的存儲結(jié)構(gòu)C.相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合D.一組性質(zhì)相同的數(shù)據(jù)元素的集合52 .在線性表的下列運算中，不改變數(shù)據(jù)元素之

13、間結(jié)構(gòu)關(guān)系的運算是(D)A.插入B.刪除C.排序D,定位53 .若進(jìn)棧序列為1,2,3,4,5,6,且進(jìn)棧和出棧可以穿插進(jìn)行，則可能出現(xiàn)的出棧序列為(A)A.3,2,6,1,4,5B.3,4,2,1,6,5C.1,2,5,3,4,6D.5,6,4,2,3,154.二維數(shù)組A89按行優(yōu)先順序存儲，若數(shù)組元素A23的存儲地址為1087,A47的存儲地址為1153,則數(shù)組元素A67的存儲地址為(A)B.1209D.1213B.計算方法A.1207C.121155 .算法指的是(D)A.計算機(jī)程序C.排序算法D.解決問題的有限運算序列56 .在一個單鏈表中，若q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點，若在q與

14、p之間插入一個s所指的結(jié)點，則執(zhí)行（D）。Asflink=pflink;pflink=s;Bp-link=s;sflink=q;Cpflink=sflink;sflink=p;Dq-link=s;sflink=p;57 .棧的插入和刪除操作在（A）進(jìn)行。A棧頂B棧底C任意位置D指定位置58 .將10階對稱矩陣壓縮存儲到一維數(shù)組A中，則數(shù)組A的長度最少為（C）。A.100B.40C.55D.8059 .將含100個結(jié)點的完全二叉樹從根這一層開始，每層從左至右依次對結(jié)點編號，根結(jié)點的編號為1。編號為47的結(jié)點X的雙親的編號為（C）A.24B.25C.23D.2無法確定60 .在含n個頂點和e條邊的

15、無向圖的鄰接矩陣中，零元素的個數(shù)為（D）A.eB.2eC.n2eD.n22e61 .折半查找要求被查找的表是（C）A.鍵值有序的鏈接表B.鏈接表但鍵值不一定有序表C鍵值有序的順序表D.順序表但鍵值不一定有序表62 .設(shè)一組初始記錄關(guān)鍵字序列（5,2,6,3,8）,以第一個記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（C）。A.2,3,5,8,6B.3,2,5,8,6C.32568D.2365863 .線性表采用鏈?zhǔn)酱鎯r，結(jié)點的存儲地址（B）A.必須是不連續(xù)的B.連續(xù)與否均可C.必須是連續(xù)的D.和頭結(jié)點的存儲地址相連續(xù)64 .設(shè)有一個無向圖G=（V,E和G'=（V',E'

16、）,如果G'為G的生成樹，下面不正確的說法是（D）A.G'為G的子圖B.G為G的一個無環(huán)子圖C.G為G的極小連通子圖且V'=VD.G'為G的連通分量65 .在按層次遍歷二叉樹的算法中，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是（A）A.隊列B.棧C.線性表D.有序表66 .在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關(guān)系（B）A.不一定相同B,都相同C.都不相同D.互為逆序67 .若采用孩子兄弟鏈表作為樹的存儲結(jié)構(gòu)，則樹的后序遍歷應(yīng)采用二叉樹的（C）A.層次遍歷算法B.前序遍歷算法C.中序遍歷算法D.后序遍歷算法68 .若用鄰接矩陣表示一個有向圖，則其中每一列包含

17、的1的個數(shù)為（A）A.圖中每個頂點的入度B.圖中每個頂點的出度C.圖中弧的條數(shù)D.圖中連通分量的數(shù)目69 .圖的鄰接矩陣表示法適用于表示（D）B.有向圖D.稀疏圖A.無向圖C.稠密圖70 .在n個關(guān)鍵字進(jìn)行直接選擇排序的過程中，每一趟都要從無序區(qū)選出最小關(guān)鍵字元素,則在進(jìn)行第i趟排序之前，無序區(qū)中關(guān)鍵字元素的個數(shù)為（D）A.iB.i+1C.n-iD.n-i+113.1. n(n>0)個元素的順序棧中刪除1個元素的時間復(fù)雜度為(C)不是特別確定！A.A.O(1)B.O/n)C.O(nlog2n)D.O(n)71.若有序表的關(guān)鍵字序列為(b,c,d,e,f,g,q,r,s,t),則在二分查找

18、關(guān)鍵字b的過程中，先后進(jìn)行比較的關(guān)鍵字依次為(A)A.f,c,bB.f,d,bC.g,c,bD.g,d,b72 .以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？(D)A.隊列B.棧C.線性表D.二叉樹73 .若某線性表的常用操作是取第i個元素及其前趨元素，則采用(A)存儲方式最節(jié)省時間A.順序表B.單鏈表C雙鏈表D.單向循環(huán)74 .設(shè)數(shù)組Data0.m作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作的語句為(B)A.front=(front+1)%(m+1)B.front=(front+1)%mC.rear=(rear+1)%mD.front=front+175 .設(shè)有

19、一個二維數(shù)組Amn，假設(shè)A00存放位置在644(10),A22存放位置在676(10),每個元素占一個空間，問A33(10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。(C)A.688B.678C.692D.69676 .深度為6(根的層次為1)的二叉樹至多有(B)結(jié)點A.64B.63C.31D.3277 .設(shè)某完全無向圖中有n個頂點，則該完全無向圖中有(A)條邊。A.n(n-1)/2B.n(n-1)C.n2D.n2-178若有18個元素的有序表存放在一維數(shù)組A19中，第一個元素放A1中，現(xiàn)進(jìn)行折半查找，則查找A3的比較序列的下標(biāo)依次為(D)A.1,2,3B.9,5,2,3C.953D.942379