數(shù)據(jù)結(jié)構(gòu)與算法試題庫與參考答案

數(shù)據(jù)結(jié)構(gòu)與算法試題庫與參考答案一、單選題（共86題，每題1分，共86分）1.數(shù)據(jù)結(jié)構(gòu)討論問題的最小單元為A、數(shù)據(jù)對象B、數(shù)據(jù)項C、數(shù)據(jù)結(jié)構(gòu)D、數(shù)據(jù)元素正確答案：B2.已知一棵二叉樹的先序遍歷結(jié)果是ABC，則以下哪個序列是不可能的中序遍歷結(jié)果：A、ABCB、BACC、CBAD、CAB正確答案：D3.一棵高度為8的完全二叉樹至少有（）葉子節(jié)點A、127B、128C、64D、63正確答案：C4.若一棵二叉樹的后序遍歷序列是{1,3,2,6,5,7,4}，中序遍歷序列是{1,2,3,4,5,6,7}，則下列哪句是錯的？A、2是1和3的父結(jié)點B、7是5的父結(jié)點C、這是一棵完全二叉樹D、這是一棵二叉搜索樹正確答案：C5.某二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹一定是（）A、空或只有一個節(jié)點B、完全二叉樹C、二叉排序樹D、高度等于其節(jié)點數(shù)正確答案：D6.下面代碼段的時間復(fù)雜度是（）。for(i=0;i<n;i++)for(j=0;j<m;j++)a[i][j]=0;A、O(1)B、O(n2)C、O(mn)D、O(m2)正確答案：C7.兩個有相同鍵值的元素具有不同的散列地址A、一定會B、一定不會C、有萬分之一的可能會D、可能會正確答案：D8.適用于壓縮存儲稀疏矩陣的兩種存儲結(jié)構(gòu)是：A、三元組表和十字鏈表B、鄰接矩陣和十字鏈表C、三元組表和鄰接矩陣D、十字鏈表和二叉鏈表正確答案：A9.給定散列表大小為11，散列函數(shù)為H(Key)=Key%11。采用平方探測法處理沖突：hi(k)=(H(k)±i2)%11將關(guān)鍵字序列{6，25，39，61}依次插入到散列表中。那么元素61存放在散列表中的位置是：A、6B、8C、7D、5正確答案：D10.若某二叉樹有5個葉結(jié)點，其權(quán)值分別為10、12、16、21、30，則其最小的帶權(quán)路徑長度（WPL）是：A、89B、289C、208D、200正確答案：D11.在有n（n>1000）個元素的升序數(shù)組A中查找關(guān)鍵字x。查找算法的偽代碼如下所示：k=0;while(k<n且A[k]<x)k=k+3;if(k<n且A[k]==x)查找成功;elseif(k-1<n且A[k-1]==x)查找成功;elseif(k-2<n且A[k-2]==x)查找成功;else查找失敗;本算法與二分查找（折半查找）算法相比，有可能具有更少比較次數(shù)的情形是：A、當(dāng)x不在數(shù)組中B、當(dāng)x接近數(shù)組開頭處C、當(dāng)x接近數(shù)組開頭處D、當(dāng)x位于數(shù)組中間位置正確答案：B12.設(shè)有一組關(guān)鍵字{29，01，13，15，56，20，87，27，69，9，10，74}，散列函數(shù)為H(key)=key%17，采用線性探測方法解決沖突。試在0到18的散列地址空間中對該關(guān)鍵字序列構(gòu)造散列表，則成功查找的平均查找長度為__A、1.25B、1.17C、0.33D、1.33正確答案：D13.現(xiàn)有長度為7、初始為空的散列表HT，散列函數(shù)H(k)=k%7，用線性探測再散列法解決沖突。將關(guān)鍵字22,43,15依次插入到HT后，查找成功的平均查找長度是：A、1.5B、3C、2D、1.6正確答案：C14.下列各種數(shù)據(jù)結(jié)構(gòu)中屬于線性結(jié)構(gòu)的有()A、圖B、集合C、樹D、隊列正確答案：D15.若結(jié)點p與q在二叉樹T的中序遍歷序列中相鄰，且p在q之前，則下列p與q的關(guān)系中，不可能的是I.q是p的雙親II.q是p的右孩子III.q是p的右兄弟IV.q是p的雙親的雙親A、僅II、IIIB、僅IIIC、僅II、IVD、僅I正確答案：B16.以下說法正確的是（）。A、數(shù)據(jù)元素是數(shù)據(jù)的最小單位B、數(shù)據(jù)項是數(shù)據(jù)的基本單位C、一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)D、數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合正確答案：C17.被計算機(jī)加工的數(shù)據(jù)元素不是孤立的，它們彼此之間一般存在某種關(guān)系，通常把數(shù)據(jù)元素之間的這種關(guān)系稱為A、集合B、運(yùn)算C、結(jié)構(gòu)D、規(guī)則正確答案：C18.以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)。A、字符串B、樹C、棧D、隊列正確答案：B19.假定有K個關(guān)鍵字互為同義詞，若用線性探測法把這K個關(guān)鍵字存入散列表中，至少要進(jìn)行多少次探測？A、K+1B、K?1C、K(K+1)/2D、K正確答案：C20.將線性表La和Lb頭尾連接，要求時間復(fù)雜度為O(1)，且占用輔助空間盡量小。應(yīng)該使用哪種結(jié)構(gòu)？A、帶尾指針的單循環(huán)鏈表B、單鏈表C、帶頭結(jié)點的雙循環(huán)鏈表D、單循環(huán)鏈表正確答案：A21.設(shè)一段文本中包含4個對象{a,b,c,d}，其出現(xiàn)次數(shù)相應(yīng)為{4,2,5,1}，則該段文本的哈夫曼編碼比采用等長方式的編碼節(jié)省了多少位數(shù)？A、2B、4C、5D、0正確答案：A22.數(shù)據(jù)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求()A、每個節(jié)點占用一片連續(xù)的存儲區(qū)域B、所有節(jié)點占用一片連續(xù)的存儲區(qū)域C、節(jié)點的最后一個數(shù)據(jù)域一定是指針類型D、每個節(jié)點有多少個后繼就設(shè)多少個指針域正確答案：A23.將{28,15,42,18,22,5,40}依次插入初始為空的二叉搜索樹。則該樹的后序遍歷結(jié)果是：A、5,22,15,40,18,42,28B、5,15,18,22,40,42,28C、5,22,18,15,40,42,28D、28,22,18,42,40,15,5正確答案：C24.對N個記錄進(jìn)行歸并排序，歸并趟數(shù)的數(shù)量級是：A、O(N2)B、O(N)C、O(logN)D、O(NlogN)正確答案：C25.設(shè)有圖的數(shù)據(jù)邏輯結(jié)構(gòu)B=(K,R)，其中頂點集K={k1,k2,?,k9}，有向邊集R={<k1,k3>,<k1,k8>,<k2,k3>,<k2,k4>,<k2,k5>,<k3,k9>,<k5,k6>,<k8,k9>,<k9,k7>,<k4,k7>,<k4,k6>}。以下哪個選項不是對應(yīng)DAG圖的拓?fù)湫蛄校緼、k1,k2,k3,k4,k5,k6,k8,k9,k7B、k2,k5,k1,k4,k6,k8,k3,k9,k7C、k2,k4,k5,k6,k7,k1,k3,k8,k9D、k1,k8,k2,k3,k9,k4,k7,k5,k6正確答案：C26.一棵度為4的樹中有20個度為4的結(jié)點、10個度為3的結(jié)點、1個度為2的結(jié)點和10個度為1的結(jié)點，則樹的葉子結(jié)點數(shù)為▁▁▁▁▁。A、122B、41C、82D、113正確答案：C27.在評價一個搜索引擎時，下列哪項不是我們關(guān)注的要點？A、界面的友好程度B、搜索結(jié)果集的相關(guān)性C、索引的速度D、搜索的速度正確答案：A28.堆的形狀是一棵：A、非二叉樹B、二叉搜索樹C、滿二叉樹D、完全二叉樹正確答案：D29.如果無向圖G必須進(jìn)行兩次廣度優(yōu)先搜索才能訪問其所有頂點，則下列說法中不正確的是：A、G中一定有回路B、G一定不是連通圖C、G有2個連通分量D、G肯定不是完全圖正確答案：A30.將10、12、1、14、6、5、8、15、3、9、7逐個按順序插入到初始為空的最小堆（小根堆）中，然后連續(xù)執(zhí)行兩次刪除最小元素操作（DeleteMin），此后堆頂?shù)脑厥鞘裁?？A、5B、6C、7D、9正確答案：A31.對于一個具有N個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是：A、N2B、N?1C、ND、(N?1)2正確答案：A32.一棵樹有n1個孩子數(shù)為1的結(jié)點，n2個孩子數(shù)為2的結(jié)點，……，nm個孩子數(shù)為m的結(jié)點，則該樹的葉結(jié)點數(shù)為：A、1+∑i=2m(i?1)niB、1+∑i=2m(i)niC、1+∑i=1m?1(i?1)niD、∑i=2m(i?1)ni正確答案：A33.數(shù)組A[0..6,0..5]的每個元素占5個字節(jié)，將其按列優(yōu)先次序存儲在起始地址為1000的內(nèi)存單元中，則元素A[5,5]的地址是()。A、1175B、1180C、1200D、1205正確答案：C34.線性表L在什么情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)？A、L中含有大量的結(jié)點B、L中結(jié)點結(jié)構(gòu)復(fù)雜C、需不斷對L進(jìn)行刪除插入D、需經(jīng)常修改L中的結(jié)點值正確答案：C35.在決定選取何種存儲結(jié)構(gòu)時，一般不考慮（）A、所用的編程語言實現(xiàn)這種結(jié)構(gòu)是否方便B、結(jié)點個數(shù)的多少C、結(jié)點個數(shù)的多少D、各結(jié)點的值如何正確答案：D36.在散列表中，所謂同義詞就是：A、具有相同散列地址的兩個元素B、被映射到不同散列地址的一個元素C、兩個意義相近的單詞D、被不同散列函數(shù)映射到同一地址的兩個元素正確答案：A37.對二叉搜索樹進(jìn)行什么遍歷可以得到從小到大的排序序列？A、前序遍歷B、后序遍歷C、層次遍歷D、中序遍歷正確答案：D38.下列關(guān)于棧的敘述中，錯誤的是：采用非遞歸方式重寫遞歸程序時必須使用棧函數(shù)調(diào)用時，系統(tǒng)要用棧保存必要的信息只要確定了入棧次序，即可確定出棧次序棧是一種受限的線性表，允許在其兩端進(jìn)行操作A、僅1B、僅1、3、4C、僅1、2、3D、僅1、3、4正確答案：B39.給定散列表大小為11，散列函數(shù)為H(Key)=Key%11。按照線性探測沖突解決策略連續(xù)插入散列值相同的4個元素。問：此時該散列表的平均不成功查找次數(shù)是多少？A、1B、21/11C、不確定D、4/11正確答案：B40.如果G是一個有28條邊的非連通無向圖，那么該圖頂點個數(shù)最少為多少？A、9B、10C、8D、7正確答案：A41.利用大小為n的數(shù)組（下標(biāo)從0到n-1）存儲一個棧時，假定棧從數(shù)組另一頭開始且top==n表示?？?，則向這個棧插入一個元素時，修改top指針應(yīng)當(dāng)執(zhí)行：A、top++B、top--C、top=0D、top不變正確答案：B42.AVL樹是一種平衡的二叉搜索樹，樹中任一結(jié)點具有下列哪一特性：A、左、右子樹的高度均相同B、左、右子樹高度差的絕對值不超過1C、左子樹的高度均大于右子樹的高度D、左子樹的高度均小于右子樹的高度正確答案：B43.將1,2,3,6,5,4順序一個個插入一棵初始為空的AVL樹，會經(jīng)歷下列哪些旋轉(zhuǎn)？A、兩個“右-右”旋和一個“右-左”旋B、一個“右-右”旋、一個“右-左”旋、一個“左-右”旋C、一個“右-右”旋和兩個“右-左”旋D、兩個“右-右”旋和一個“左-右”旋正確答案：C44.采用遞歸方式對順序表進(jìn)行快速排序，下列關(guān)于遞歸次數(shù)的敘述中，正確的是：A、每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)B、遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關(guān)C、遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無關(guān)D、每次劃分后，先處理較長的分區(qū)可以減少遞歸次數(shù)正確答案：C45.對于序列{49，38，65，97，76，13，27，50}，按由小到大進(jìn)行排序，下面哪一個是初始步長為4的希爾排序法第一趟的結(jié)果？A、97,76,65,50,49,38,27,13B、13,27,38,49,50,65,76,97C、49,76,65,13,27,50,97,38D、49,13,27,50,76,38,65,97正確答案：D46.一棵滿二叉樹中127個節(jié)點，其中葉子節(jié)點的個數(shù)是（）A、63B、64C、65D、不確定正確答案：B47.對給定序列{110，119，7，911，114，120，122}采用次位優(yōu)先（LSD）的基數(shù)排序，則兩趟收集后的結(jié)果為：A、7,110,119,114,911,120,122B、7,110,119,114,911,122,120C、7,110,911,114,119,120,122D、110,120,911,122,114,7,119正確答案：C48.給定N×N×N的三維數(shù)組A，則在不改變數(shù)組的前提下，查找最小元素的時間復(fù)雜度是：A、O(N2)B、O(NlogN)C、O(N2logN)D、O(N3)正確答案：D49.采用多項式的非零項鏈?zhǔn)酱鎯Ρ硎痉ǎ绻麅蓚€多項式的非零項分別為N1和N2個，最高項指數(shù)分別為M1和M2，則實現(xiàn)兩個多項式相加的時間復(fù)雜度是：A、O(N1×N2)B、O(M1+M2)C、O(M1×M2)D、O(N1+N2)正確答案：D50.已知一棵二叉樹的前序遍歷結(jié)果為ABCDEFG,中序遍歷結(jié)果為BCAEDGF,則后序遍歷的結(jié)果為（）。A、CBAEGFDB、CBEGFDAC、BCEGFDAD、CBEFGDA正確答案：B51.中位值結(jié)點在根結(jié)點或根的左子樹上A、3B、1C、4D、2正確答案：D52.令P代表入棧，O代表出棧。若利用堆棧將中綴表達(dá)式3*2+8/4轉(zhuǎn)為后綴表達(dá)式，則相應(yīng)的堆棧操作序列是：A、PPOOPOB、PPPOOOC、POPOPOD、POPPOO正確答案：D53.若一個棧的入棧序列為1、2、3、…、N，其輸出序列為p1、p2、p3、…、pN。若p1=N，則pi為：A、n?i+1B、不確定C、iD、n?i正確答案：A54.數(shù)據(jù)元素在計算機(jī)存儲器內(nèi)表示時，物理相對位置和邏輯相對位置相同并且是連續(xù)的，稱之為（）。A、邏輯結(jié)構(gòu)B、順序存儲結(jié)構(gòu)C、鏈?zhǔn)酱鎯Y(jié)構(gòu)D、以上都不對正確答案：B55.對一棵二叉樹的結(jié)點從1開始順序編號。要求每個結(jié)點的編號都小于其子樹所有結(jié)點的編號，且左子樹所有結(jié)點的編號都小于右子樹所有結(jié)點的編號?？刹捎猫x▁▁▁▁實現(xiàn)編號。A、后序遍歷B、層次遍歷C、中序遍歷D、先序遍歷正確答案：D56.在計算機(jī)中存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲()。A、數(shù)據(jù)的存儲方法B、數(shù)據(jù)元素之間的關(guān)系C、數(shù)據(jù)元素的類型D、數(shù)據(jù)的處理方法正確答案：B57.將下列數(shù)（88,70,61,96,120,90）按順序插入初始為空的AVL中，所形成的AVL樹的前序遍歷結(jié)果是：A、61,70,88,90,96,120B、90,70,61,88,96,120C、88,70,61,90,96,120D、88,70,61,96,90,120正確答案：D58.如果循環(huán)隊列用大小為m的數(shù)組表示，且用隊頭指針front和隊列元素個數(shù)size代替一般循環(huán)隊列中的front和rear指針來表示隊列的范圍，那么這樣的循環(huán)隊列可以容納的元素個數(shù)最多為：A、m+1B、m-1C、mD、不能確定正確答案：C59.設(shè)森林F中有三棵樹，第一、第二、第三棵樹的結(jié)點個數(shù)分別為M1，M2和M3。則與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是：A、M2+M3B、M1C、M1+M2D、M3正確答案：A60.對初始數(shù)據(jù)序列{8,3,9,11,2,1,4,7,5,10,6}進(jìn)行希爾排序。若第一趟排序結(jié)果為（1,3,7,5,2,6,4,9,11,10,8），第二趟排序結(jié)果為（1,2,6,4,3,7,5,8,11,10,9），則兩趟排序采用的增量（間隔）依次是：A、5,3B、3,1C、3,2D、5,2正確答案：A61.將兩個結(jié)點數(shù)都為N且都從小到大有序的單向鏈表合并成一個從小到大有序的單向鏈表，那么可能的最少比較次數(shù)是：A、2NB、1C、ND、NlogN正確答案：C62.設(shè)我們的內(nèi)存可以一次處理12個數(shù)字，且磁帶上有以下兩條有序段：有序段1:1,3,5,7,8,9,10,12有序段2:2,4,6,15,20,25,30,32采用2路歸并，并設(shè)置4塊輸入緩沖區(qū)和2塊輸出緩沖區(qū)，以便并行操作。則下列哪三個操作是不能并行的？A、將1和2寫入第三條磁帶；將3和4歸并到一塊輸出緩沖區(qū)；將6和15讀入一塊輸入緩沖區(qū)B、將7和8寫入第三條磁帶；將9和15歸并到一塊輸出緩沖區(qū)；將10和12讀入一塊輸入緩沖區(qū)C、將3和4寫入第三條磁帶；將5和6歸并到一塊輸出緩沖區(qū)；將8和9讀入一塊輸入緩沖區(qū)D、將5和6寫入第三條磁帶；將7和8歸并到一塊輸出緩沖區(qū)；將20和25讀入一塊輸入緩沖區(qū)正確答案：B63.已知二維數(shù)組A按行優(yōu)先方式存儲，每個元素占用1個存儲單元。若元素A[0][0]的存儲地址是100，A[3][3]的存儲地址是220，則元素A[5][5]的存儲地址是：A、295B、300C、301D、306正確答案：B64.給定無向圖G，從V0出發(fā)進(jìn)行深度優(yōu)先遍歷訪問的邊集合為：{(V0,V1),(V0,V4),(V1,V2),(V1,V3),(V4,V5),(V5,V6)}。則下面哪條邊不可能出現(xiàn)在G中？A、(V0,V2)B、(V4,V6)C、(V1,V5)D、(V0,V6)正確答案：C65.對N個記錄進(jìn)行快速排序，在最壞的情況下，其時間復(fù)雜度是：A、O(N2)B、O(N2logN)C、O(NlogN)D、O(N)正確答案：A66.關(guān)于圖的鄰接矩陣，下列哪個結(jié)論是正確的？A、無向圖的鄰接矩陣可以是不對稱的，也可以是對稱的B、無向圖的鄰接矩陣總是不對稱的C、有向圖的鄰接矩陣總是不對稱的D、有向圖的鄰接矩陣可以是對稱的，也可以是不對稱的正確答案：D67.任何一個帶權(quán)無向連通圖的最小生成樹——A、有可能不存在B、是唯一的C、有可能不唯一D、是不唯一的正確答案：C68.鏈表不具有的特點是：A、不必事先估計存儲空間B、方便隨機(jī)訪問任一元素C、所需空間與線性長度成正比D、插入、刪除不需要移動元素正確答案：B69.一個有N個頂點的強(qiáng)連通圖至少有多少條邊？A、NB、N+1C、N?1D、N(N?1)正確答案：A70.將M個元素存入用長度為S的數(shù)組表示的散列表，則該表的裝填因子為：A、M?SB、M/SC、M×SD、S+M正確答案：B71.就排序算法所用的輔助空間而言，堆排序、快速排序、歸并排序的關(guān)系是：A、堆排序>歸并排序>快速排序B、堆排序<歸并排序<快速排序C、堆排序>快速排序>歸并排序D、堆排序<快速排序<歸并排序正確答案：D72.二叉樹的高度若根節(jié)點為高度1，一棵具有1025個結(jié)點的二叉樹的高度為▁▁▁▁▁。A、11～1025之間B、11C、10D、10～1024之間正確答案：A73.對一組包含10個元素的非遞減有序序列，采用直接插入排序排成非遞增序列，其可能的比較次數(shù)和移動次數(shù)分別是：A、100,54B、45,44C、100,100D、54,63正確答案：B74.下面描述中正確的為()。A、線性表的邏輯順序與物理順序總是一致的B、線性表的順序存儲表示優(yōu)于鏈?zhǔn)酱鎯Ρ硎?。C、線性表若采用鏈?zhǔn)酱鎯Ρ硎緯r所有結(jié)點之間的存儲單元地址可連續(xù)可不連續(xù)。D、二維數(shù)組是其數(shù)組元素為線性表的線性表。正確答案：C75.由分別帶權(quán)為9、2、5、7的四個葉子結(jié)點構(gòu)成一棵哈夫曼樹，該樹的帶權(quán)路徑長度為：A、46B、44C、23D、37正確答案：B76.給定A[]={46,23,8,99,31,12,85}，調(diào)用非遞歸的歸并排序加表排序執(zhí)行第1趟后，表元素的結(jié)果是：A、1,2,3,4,5,6,7B、1,0,2,3,5,4,6C、3,6,1,5,2,7,4D、0,2,1,4,3,5,6正確答案：B77.對最小堆（小頂堆）{1,3,2,6,7,5,4,15,14,12,9,10,11,13,8}進(jìn)行三次刪除最小元的操作后，結(jié)果序列為：A、4,5,6,12,7,10,8,15,14,13,9,11B、4,5,6,7,8,9,10,11,12,13,14,15C、4,6,5,12,7,10,8,15,14,9,13,11D、4,6,5,13,7,10,8,15,14,12,9,11正確答案：D78.設(shè)一棵非空完全二叉樹T的所有葉節(jié)點均位于同一層，且每個非葉結(jié)點都有2個子結(jié)點。若T有k個葉結(jié)點，則T的結(jié)點總數(shù)是：A、k2B、2k?1C、2k?1D、2k正確答案：B79.程序P1和P2時間復(fù)雜度的遞推公式：P1:T(1)=1,T(N)=T(N/2)+1;P2:T(1)=1,T(N)=2T(N/2)+1;則下列關(guān)于兩程序時間復(fù)雜度的結(jié)論中最準(zhǔn)確的是：A、均為O(logN)B、P1是O(logN)，P2是O(N)C、均為O(N)D、P1是O(logN)，P2是O(NlogN)正確答案：B80.創(chuàng)建一個初始堆，含有N個記錄，其時間復(fù)雜度是：A、O(logN)B、O(N2)C、O(N)D、O(NlogN)正確答案：C81.假設(shè)我們只有2條磁帶Ta和Tb用于做外部排序。假設(shè)內(nèi)存可以一次處理M條記錄。初始狀態(tài)下Ta上存有N條記錄。下列簡單算法的執(zhí)行步驟為：第1步：從Ta一次讀入M條記錄到內(nèi)存，做內(nèi)部排序，然后將有序的結(jié)果寫到Tb。第2步：從Ta一次讀入M條記錄到內(nèi)存，做內(nèi)部排序，然后將其與Tb上存儲的有序列做歸并，將有序的（2M條記錄）結(jié)果寫到Ta。第3步：從Ta一次讀入M條記錄到內(nèi)存，做內(nèi)部排序，然后將其與Tb上存儲的2M條記錄的有序列做歸并，將有序的（3M條記錄）結(jié)果寫到Tb。重復(fù)第2、3步，直到全部記錄有序。上述算法需要執(zhí)行__輪。A、logMNB、?N/M?C、logND、?log(N/M)?正確答案：B82.具有5個頂點的有向完全圖有多少條??？A、16B、10C、20D、25正確答案：C83.下列程序的時間復(fù)雜度為（）。i=0;s=0;while(s<n){i++;s=s+i;}A、Θ(n2)B、Θ(1)C、Θ(n)D、Θ(n?)正確答案：D84.若借助堆棧將中綴表達(dá)式a+b*c+(d*e+f)*g轉(zhuǎn)換為后綴表達(dá)式，當(dāng)讀入f時，堆棧里的內(nèi)容是什么（按堆棧自底向上順序）？A、abcdeB、+(*+C、+(+D、++(+正確答案：C85.下列關(guān)于無向連通圖特征的敘述中，正確的是：所有頂點的度之和為偶數(shù)邊數(shù)大于頂點個數(shù)減1至少有一個頂點的度為1A、1和3B、1和2C、只有1D、只有2正確答案：C86.為解決計算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題，通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是？A、樹B、堆棧C、隊列D、圖正確答案：C二、多選題（共3題，每題1分，共3分）1.以下說法錯誤的是（）。A、哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根較近。B、若一個二叉樹的樹葉是某子樹的中序遍歷序列中的第一個結(jié)點，則它必是該子樹的后序遍歷序列中的第一個結(jié)點C、已知二叉樹的前序遍歷和后序遍歷序列并不能唯一確定這棵樹，因為不知道樹的根結(jié)點是哪一個。D、在前序遍歷二叉樹的序列中，任何結(jié)點的子樹的所有結(jié)點都是直接跟在該結(jié)點之后。正確答案：AC2.根據(jù)數(shù)據(jù)元素之間的關(guān)系的不同特性，通常分為哪幾類基本結(jié)構(gòu)？A、樹形結(jié)構(gòu)B、圖狀結(jié)構(gòu)C、線性結(jié)構(gòu)D、集合正確答案：ABCD3.排序算法的穩(wěn)定性下列關(guān)于順序表的排序算法中，▁▁▁▁▁是穩(wěn)定的。A、快速排序B、冒泡排序C、選擇排序D、歸并排序正確答案：BD三、判斷題（共26題，每題1分，共26分）1.無向連通圖所有頂點的度之和為偶數(shù)。A、正確B、錯誤正確答案：A2.N2logN和NlogN2具有相同的增長速度。A、正確B、錯誤正確答案：B3.一棵有124個結(jié)點的完全二叉樹，其葉結(jié)點個數(shù)是確定的。A、正確B、錯誤正確答案：A4.若圖G有環(huán)，則G不存在拓?fù)渑判蛐蛄?。A、正確B、錯誤正確答案：A5.存在一棵總共有2016個結(jié)點的二叉樹，其中有16個結(jié)點只有一個孩子。A、正確B、