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

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

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

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

4、點(diǎn)的左子樹上所有結(jié)點(diǎn)的值一定(A)該結(jié)點(diǎn)的值。A.小于B.大于C.不小于D.大于等于19 .對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹，該樹中所有結(jié)點(diǎn)的度數(shù)之和為(A)。A.n-1B.nC.n+1D.2n20.某程序的時(shí)間復(fù)雜度為(3n+100xlog2n+nlog2n),其數(shù)量級(jí)表示為(B)。A.O(n)B.O(nlog2n)C.O(100)D.O(log2n)21 .設(shè)一組初始記錄關(guān)鍵字序列(5,2,6,3,8),以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為(C)。A.2,3,5,8,6B.3,2,5,8,6C.32568D.2365822 .根據(jù)n個(gè)元素建立一棵二叉搜索樹時(shí)，其時(shí)間復(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.動(dòng)態(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ù)組存儲(chǔ)二叉樹，總是以先序順序遍歷各結(jié)點(diǎn)25 .在計(jì)算機(jī)的存儲(chǔ)器中表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為BA.邏輯結(jié)構(gòu)B.順序存儲(chǔ)結(jié)構(gòu)C鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.以上都不對(duì)26 .以下關(guān)于算法特性的描述中，B是正確的。(1)算法

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

7、密度小于順序存儲(chǔ)結(jié)構(gòu)B.邏輯上相鄰的結(jié)點(diǎn)物理上不必鄰接C可以通過計(jì)算直接確定第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址D.插入、刪除操作方便，不必移動(dòng)結(jié)點(diǎn)31 .設(shè)依次進(jìn)入一個(gè)棧的元素序列為d,a,c,b彳導(dǎo)不到出棧的元素序列為DA.dcbaB.acdbC.abcdD.cbda32 .將新元素插入到鏈?zhǔn)疥?duì)列中時(shí)，新元素只能插入到B。A.鏈頭B.鏈尾C.鏈中D.第i個(gè)位置，i大于等于1,大于等于表長加133 .設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素el、e2、e3、e4、e5和e6依次通過棧S,一個(gè)元素出棧后即進(jìn)入隊(duì)列Q,若6個(gè)元素出隊(duì)的順序是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分別以行序?yàn)橹餍蚝鸵粤行驗(yàn)橹餍蝽樞虼鎯?chǔ)時(shí),其首地址相同，那么以行序?yàn)橹餍驎r(shí)元素a3,5的地址與以列序?yàn)橹餍驎r(shí)C元素相同。A. a7,3B. a83C. a1,4D. ABC者B不對(duì)36 .數(shù)組A05,06的每個(gè)元素占5個(gè)字節(jié)，將其按列優(yōu)先次序存儲(chǔ)在起始地址為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 .在一個(gè)單鏈表中，若q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q與p之間插入一個(gè)s所指的結(jié)點(diǎn)，則執(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個(gè)度為1的結(jié)點(diǎn)，b個(gè)度為2的結(jié)點(diǎn)，c個(gè)度為3的結(jié)點(diǎn)，則該樹有D個(gè)葉結(jié)點(diǎn)。A.1+2b+3cB.a+2b+3cC.2b+3cD.1+b+2c40 .若一棵二叉樹有102片葉子結(jié)點(diǎn)，則度二叉樹度為2的結(jié)點(diǎn)數(shù)是BA.100B

10、.101C.102D.10341 .在有n個(gè)葉子結(jié)點(diǎn)的霍夫曼樹中，其結(jié)點(diǎn)總數(shù)為：D。A.nB.2nC.2n+1D.2n-142.具有12個(gè)結(jié)點(diǎn)的完全二叉樹有BB.5個(gè)度為2的結(jié)點(diǎn)A.5個(gè)葉子結(jié)點(diǎn)C.7個(gè)分支結(jié)點(diǎn)D.2個(gè)度為1的結(jié)點(diǎn)43.設(shè)結(jié)點(diǎn)x和y是二叉樹中的任意兩結(jié)點(diǎn)，若在先根序列中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é)點(diǎn)無左子樹的二叉樹B.根結(jié)點(diǎn)無右子樹的二叉樹C.只有根結(jié)點(diǎn)的二叉樹或非葉子結(jié)點(diǎn)只有左子樹的二叉樹D.只有根結(jié)點(diǎn)的二叉樹或非葉子結(jié)點(diǎn)

11、只有右子樹的二叉樹45 .若二叉樹T的前序遍歷序列和中序遍歷序列分別是bdcaef和cdeabf,則其后序遍歷序列為A。A.ceadfbB.feacdbC.eacdfbD.以上都不對(duì)46 .設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n,則該圖最多有C條邊。A.n-1B.n(n-1)C.n(n-1)/2D.N47 .對(duì)于一個(gè)有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表表示，鄰接表中的結(jié)點(diǎn)總數(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)。對(duì)該圖進(jìn)行深度優(yōu)先遍歷，下面不能得到的序列

12、是D。A.acfdebB.aebdfcC.aedfcbD.abecdf49 .直接插入排序在最好情況下的時(shí)間復(fù)雜度為B。A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)50 .對(duì)有n個(gè)記錄的表作快速排序，在最壞情況，算法的時(shí)間復(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ù)的存儲(chǔ)結(jié)構(gòu)C.相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合D.一組性質(zhì)相同的數(shù)據(jù)元素的集合52 .在線性表的下列運(yùn)算中，不改變數(shù)據(jù)元素之

13、間結(jié)構(gòu)關(guān)系的運(yù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)先順序存儲(chǔ)，若數(shù)組元素A23的存儲(chǔ)地址為1087,A47的存儲(chǔ)地址為1153,則數(shù)組元素A67的存儲(chǔ)地址為(A)B.1209D.1213B.計(jì)算方法A.1207C.121155 .算法指的是(D)A.計(jì)算機(jī)程序C.排序算法D.解決問題的有限運(yùn)算序列56 .在一個(gè)單鏈表中，若q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q與

14、p之間插入一個(gè)s所指的結(jié)點(diǎn)，則執(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階對(duì)稱矩陣壓縮存儲(chǔ)到一維數(shù)組A中，則數(shù)組A的長度最少為（C）。A.100B.40C.55D.8059 .將含100個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每層從左至右依次對(duì)結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn)的編號(hào)為1。編號(hào)為47的結(jié)點(diǎn)X的雙親的編號(hào)為（C）A.24B.25C.23D.2無法確定60 .在含n個(gè)頂點(diǎn)和e條邊的

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

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

17、的1的個(gè)數(shù)為（A）A.圖中每個(gè)頂點(diǎn)的入度B.圖中每個(gè)頂點(diǎn)的出度C.圖中弧的條數(shù)D.圖中連通分量的數(shù)目69 .圖的鄰接矩陣表示法適用于表示（D）B.有向圖D.稀疏圖A.無向圖C.稠密圖70 .在n個(gè)關(guān)鍵字進(jìn)行直接選擇排序的過程中，每一趟都要從無序區(qū)選出最小關(guān)鍵字元素,則在進(jìn)行第i趟排序之前，無序區(qū)中關(guān)鍵字元素的個(gè)數(shù)為（D）A.iB.i+1C.n-iD.n-i+113.1. n(n>0)個(gè)元素的順序棧中刪除1個(gè)元素的時(shí)間復(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)中哪一個(gè)是非線性結(jié)構(gòu)？(D)A.隊(duì)列B.棧C.線性表D.二叉樹73 .若某線性表的常用操作是取第i個(gè)元素及其前趨元素，則采用(A)存儲(chǔ)方式最節(jié)省時(shí)間A.順序表B.單鏈表C雙鏈表D.單向循環(huán)74 .設(shè)數(shù)組Data0.m作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作的語句為(B)A.front=(front+1)%(m+1)B.front=(front+1)%mC.rear=(rear+1)%mD.front=front+175 .設(shè)有

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