西工大22年4月機(jī)考隨機(jī)試題《數(shù)據(jù)結(jié)構(gòu)》答案

1、試卷總分:100 得分:100一、 單選題 (共 50 道試題,共 100 分)1. 快速排序算法在最好情況下的時(shí)間復(fù)雜度為（ ）。A.O(n)B.O(nlog2n)C.O(n2)D.O(log2n)正確答案:A2.對(duì)有序表(18，20，25，34，48，62，74，85)用二分查找法查找85，所需的比較次數(shù)為( )。A.1次B.2次C.3次D.4次正確答案:D3.數(shù)據(jù)表A中有10000個(gè)元素，如果僅要求求出其中最大的10個(gè)元素，則采用( )排序算法最節(jié)省時(shí)間。A.堆排序B.希爾排序C.快速排序D.直接選擇排序正確答案:A4.若深度為6的完全二叉樹(shù)的第6層有3個(gè)葉結(jié)點(diǎn)，則該二叉樹(shù)一共有（ ）個(gè)

2、結(jié)點(diǎn)。A.15B.16C.17D.34正確答案:D5.關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（ ）。A.最短的回路B.最長(zhǎng)的回路C.從開(kāi)始結(jié)點(diǎn)到完成結(jié)點(diǎn)的最長(zhǎng)路徑D.從開(kāi)始結(jié)點(diǎn)到完成結(jié)點(diǎn)的最短路徑正確答案:C6.樹(shù)型結(jié)構(gòu)最適合用來(lái)描述 ( )。A.有序的數(shù)據(jù)元素B.無(wú)序的數(shù)據(jù)元素C.數(shù)據(jù)元素之間的具有層次關(guān)系的數(shù)據(jù)D.數(shù)據(jù)元素之間沒(méi)有關(guān)系的數(shù)據(jù)正確答案:C7.在平衡二叉樹(shù)中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為A，并已知A的左孩子的平衡因子為-1，右孩子的平衡因子為0，則應(yīng)作( )型調(diào)整以使其平衡。A.LLB.LRC.RLD.RR正確答案:B8.散列表的平均查找長(zhǎng)度( ) 。A.與處理沖突方法有關(guān)

3、而與表的長(zhǎng)度無(wú)關(guān)B.與處理沖突方法無(wú)關(guān)而與表的長(zhǎng)度有關(guān)C.與處理沖突方法有關(guān)且與表的長(zhǎng)度有關(guān)D.與處理沖突方法無(wú)關(guān)且與表的長(zhǎng)度無(wú)關(guān)正確答案:C9. 下面關(guān)于哈夫曼樹(shù)的說(shuō)法，不正確的是（ ）。A.對(duì)應(yīng)于一組權(quán)值構(gòu)造出的哈夫曼樹(shù)一般不是唯一的B.哈夫曼樹(shù)具有最小帶權(quán)路徑長(zhǎng)度C.哈夫曼樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)D.哈夫曼樹(shù)中除了度為1的結(jié)點(diǎn)外，還有度為2的結(jié)點(diǎn)和葉結(jié)點(diǎn)正確答案:D10.若深度為6的完全二叉樹(shù)的第6層有3個(gè)葉結(jié)點(diǎn)，則該二叉樹(shù)一共有( )個(gè)結(jié)點(diǎn)。A.15B.16C.17D.34正確答案:D11.對(duì)有序表(18，20，25，34，48，62，74，85)用二分查找法查找85，所需的比較次數(shù)為（

4、）。A.1次B.2次C.3次D.4次正確答案:D12.一個(gè)n*n的對(duì)稱(chēng)矩陣，如果以行或列為主序存入內(nèi)存，則其容量為（ ）。A.n*nB.n*(n+1)/2C.(n+1)*(n+1)/2D.(n-1）*n/2正確答案:B13.對(duì)有14個(gè)數(shù)據(jù)元素的有序表R14進(jìn)行折半搜索，搜索到R3的關(guān)鍵碼等于給定值，此時(shí)元素比較順序依次為( )。A.R0，R1，R2，R3B.R0，R13，R2，R3C.R6，R2，R4，R3D.R6，R4，R2，R3正確答案:C14.下列陳述中正確的是（ ）。A.二叉樹(shù)是度為2的有序樹(shù)B.二叉樹(shù)中結(jié)點(diǎn)只有一個(gè)孩子時(shí)無(wú)左右之分C.二叉樹(shù)中必有度為2的結(jié)點(diǎn)D.二叉樹(shù)中最多只有兩棵子

5、樹(shù)，并且有左右之分正確答案:D15. 數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ ）。A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.線(xiàn)性結(jié)構(gòu)和非先性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)正確答案:C16. 算法指的是（ ）。A.計(jì)算機(jī)程序B.解決問(wèn)題的方法C.排序算法D.解決問(wèn)題的有限運(yùn)算序列正確答案:D17.對(duì)有14個(gè)數(shù)據(jù)元素的有序表R14進(jìn)行折半搜索，搜索到R3的關(guān)鍵碼等于給定值，此時(shí)元素比較順序依次為（ ）。A.R0，R1，R2，R3B.R0，R13，R2，R3C.R6，R2，R4，R3D.R6，R4，R2，R3正確答案:C18.散列表的平均查找長(zhǎng)度( )。A.與處理沖突方法有關(guān)而與表的長(zhǎng)度無(wú)關(guān)B

6、.與處理沖突方法無(wú)關(guān)而與表的長(zhǎng)度有關(guān)C.與處理沖突方法有關(guān)且與表的長(zhǎng)度有關(guān)D.與處理沖突方法無(wú)關(guān)且與表的長(zhǎng)度無(wú)關(guān)正確答案:C19.設(shè)有向圖有n個(gè)頂點(diǎn)和e條邊，進(jìn)行拓?fù)渑判驎r(shí)總的計(jì)算時(shí)間為（ ）。A.O(loge)B.O(en)C.O(elogn)D.O(n+e)正確答案:D20.設(shè)有向圖G中頂點(diǎn)數(shù)為n，圖G最多有（ ）條邊。A.nB. n-1 C.n*(n-1)/2D.n*(n-1)正確答案:D21.常采用下面幾種方式解決散列法中出現(xiàn)的沖突問(wèn)題（ ）。A.數(shù)字分析法、除余法、平方取中法B.數(shù)字分析法、除余法、線(xiàn)性探測(cè)法C.數(shù)字分析法、線(xiàn)性探測(cè)法、多重散列法D.線(xiàn)性探測(cè)法、多重散列法、鏈地址法正

7、確答案:D22.廣義表運(yùn)算式tail(a,b),(c,d)的結(jié)果為（ ）A.c,dB.(c,d)C.(c,d)D.d,c正確答案:C23.若二叉樹(shù)中度為2的結(jié)點(diǎn)有15個(gè)，度為1的結(jié)點(diǎn)有10個(gè)該樹(shù)有( )個(gè)結(jié)點(diǎn)。A.25B.30C.31D.41正確答案:D24.散列表的平均查找長(zhǎng)度（ ）。A.與處理沖突方法有關(guān)而與表的長(zhǎng)度無(wú)關(guān)B.與處理沖突方法無(wú)關(guān)而與表的長(zhǎng)度有關(guān)C.與處理沖突方法有關(guān)且與表的長(zhǎng)度有關(guān)D.與處理沖突方法無(wú)關(guān)且與表的長(zhǎng)度無(wú)關(guān)正確答案:C25.線(xiàn)索二叉樹(shù)是一種（ ）結(jié)構(gòu)。A.邏輯B.邏輯和存儲(chǔ)C.物理D.線(xiàn)性正確答案:C26.若二叉樹(shù)中度為2的結(jié)點(diǎn)有15個(gè)，度為1的結(jié)點(diǎn)有10個(gè)該樹(shù)有

8、 ( )個(gè)葉結(jié)點(diǎn)。A.25B.30C.31D.16正確答案:D27.已知廣義表a=(a,b,c),(d,e,f),從a中取出原子e的運(yùn)算是（ ）A.tail(head(a)B.b.head(tail(a)C.head(tail(tail(head(a)D.head(tail (tail(a)正確答案:D28.下列排序算法中，( )算法可能會(huì)出現(xiàn)下面情況：初始數(shù)據(jù)有序時(shí)，花費(fèi)的時(shí)間反而最多。A.堆排序B.冒泡排C.快速排序D.SHELL排序正確答案:C29.設(shè)有向圖有n個(gè)頂點(diǎn)和e條邊，進(jìn)行拓?fù)渑判驎r(shí)總的計(jì)算時(shí)間為（ ）。A.O(loge)B.O(en)C.O(elogn)D.O(n+e)正確答案

9、:D30.計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的對(duì)象被統(tǒng)稱(chēng)為（ ）。A.數(shù)據(jù)B.數(shù)據(jù)元素C.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)類(lèi)型正確答案:A31. 設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹餍?，A11為第一個(gè)元素，其存儲(chǔ)地址為1，每個(gè)元素占1個(gè)地址空間，則A82的地址為（ ）。 A.13B.30C.18D.0正確答案:B32.下列排序算法中，時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為O(log2n)的是( )。A.堆排序B.冒泡排C.直接選擇排序D.快速排序正確答案:A33.在非空二叉樹(shù)的中序遍歷序列中，二叉樹(shù)的根結(jié)點(diǎn)的左邊應(yīng)該（ ）。A.只有左子樹(shù)上的所有結(jié)點(diǎn)B.只有左子樹(shù)上的部分結(jié)點(diǎn)C.只有右子樹(shù)上的所有結(jié)

10、點(diǎn)D.只有右子樹(shù)上的部分結(jié)點(diǎn)正確答案:A34.廣義表運(yùn)算式tail(a,b),(c,d)的結(jié)果為（ ）。A.c,dB.(c,d)C.(c,d)D.d,c正確答案:C35.線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)是一種（ ）存取結(jié)構(gòu)。A.隨即存取B.順序存取C.索引存取D.散列存取正確答案:A36.對(duì)有14個(gè)數(shù)據(jù)元素的有序表R14進(jìn)行折半搜索，搜索到R3的關(guān)鍵碼等于給定值，此時(shí)元素比較順序依次為( )。A.R0，R1，R2，R3B.R0，R13，R2，R3C.R6，R2，R4，R3D.R6，R4，R2，R3正確答案:C37.下列說(shuō)法中不正確的是（ ）。A.圖的遍歷過(guò)程中每一頂點(diǎn)僅被訪問(wèn)一次B.遍歷圖的基本方法有深度

11、優(yōu)先搜索和廣度優(yōu)先搜索兩種C.圖的深度優(yōu)先搜索的方法不適用于有向圖D.圖的深度優(yōu)先搜索是一個(gè)遞歸過(guò)程正確答案:C38.有一個(gè)10階的對(duì)稱(chēng)矩陣a，采用壓縮存儲(chǔ)方式，以行序?yàn)橹餍?，a11為第一個(gè)元素，其存儲(chǔ)地址為1，每個(gè)元素占1個(gè)地址空間，則a85的地址為（ ）。A.13B.33C.18D.40正確答案:B39.對(duì)于單鏈表形式的隊(duì)列，隊(duì)空的條件是（ ）。A.FRB.FRC.Fnil且RD.RF1正確答案:B40.關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（ ）。A.最短的回路B.最長(zhǎng)的回路C.從開(kāi)始結(jié)點(diǎn)到完成結(jié)點(diǎn)的最長(zhǎng)路徑D.從開(kāi)始結(jié)點(diǎn)到完成結(jié)點(diǎn)的最短路徑正確答案:C41.關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（ ）。A.最短的

12、回路B.最長(zhǎng)的回路C.從開(kāi)始結(jié)點(diǎn)到完成結(jié)點(diǎn)的最長(zhǎng)路徑D.從開(kāi)始結(jié)點(diǎn)到完成結(jié)點(diǎn)的最短路徑正確答案:B42.快速排序算法在最好情況下的時(shí)間復(fù)雜度為( ) 。A.O(n)B.O(nlog2n)C.O(n2)D.O(log2n)正確答案:A43.下述排序算法中，穩(wěn)定的是（ ）。A.直接選擇排序B.表插入排序C.快速排序D.堆排序正確答案:B44.二叉樹(shù)在線(xiàn)索化后，仍不能有效求解的問(wèn)題是（ ）。A.先序線(xiàn)索二叉樹(shù)中求先序后繼B.中序線(xiàn)索二叉樹(shù)中求中序后繼C.中序線(xiàn)索二叉樹(shù)中求中序前趨D.后序線(xiàn)索二叉樹(shù)中求后序后繼正確答案:D45.深度為6的二叉樹(shù)至多有結(jié)點(diǎn)數(shù)為（ ）。A.16B.30C.63D.31正確答案:D46.在含n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接矩陣中，零元素的個(gè)數(shù)為（ ）。A.eB.2eC.n2eD.n22e正確答案:D47.一個(gè)無(wú)向連通圖的生成樹(shù)是含有該連通圖的全部頂點(diǎn)的（ ）。A.極小連通子圖B.極小子圖C.極大連通子圖D.極大子圖正確答案:A48.數(shù)據(jù)表A中有00個(gè)元素，如果僅要求求出其中最大的10個(gè)元素，則采用（ ）排序A.堆排序B.希爾排序C.快速排序D.直接選擇排序正確答案:A49.常采用下面幾種方式解決散列法中出現(xiàn)的沖突問(wèn)題（ ）。A.數(shù)字分析法、除余法、平方取中法B.數(shù)字分析法、除余法、線(xiàn)性探測(cè)法