數(shù)據(jù)結(jié)構(gòu)與算法復(fù)習(xí)題一、單選題（共86題，每題1分，共86分）1.在計(jì)算機(jī)中存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)()。A、數(shù)據(jù)的處理方法B、數(shù)據(jù)元素之間的關(guān)系C、數(shù)據(jù)元素的類(lèi)型D、數(shù)據(jù)的存儲(chǔ)方法正確答案：B2.下面描述中正確的為()。A、線性表的邏輯順序與物理順序總是一致的B、線性表的順序存儲(chǔ)表示優(yōu)于鏈?zhǔn)酱鎯?chǔ)表示。C、線性表若采用鏈?zhǔn)酱鎯?chǔ)表示時(shí)所有結(jié)點(diǎn)之間的存儲(chǔ)單元地址可連續(xù)可不連續(xù)。D、二維數(shù)組是其數(shù)組元素為線性表的線性表。正確答案：C3.設(shè)n、m為一棵二叉樹(shù)上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m前的條件是A、n在m左方B、n是m子孫C、n在m右方D、n是m祖先正確答案：A4.在單鏈表中，若p所指的結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行A、s->next=p->next;p->next=s;B、p->next=s;s->next=p;C、s->next=p;p->next=s;D、s->next=p->next;p=s;正確答案：A5.若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)。則采用哪種存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間？A、帶頭結(jié)點(diǎn)的雙循環(huán)鏈表B、單循環(huán)鏈表C、單鏈表D、雙鏈表正確答案：A6.如果AVL樹(shù)的深度為6（空樹(shù)的深度定義為?1），則此樹(shù)最少有多少個(gè)結(jié)點(diǎn)？A、12B、20C、33D、64正確答案：C7.斐波那契數(shù)列FN的定義為：F0=0,F1=1,FN=FN?1+FN?2,N=2,3,…。用遞歸函數(shù)計(jì)算FN的時(shí)間復(fù)雜度是：A、O(N!)B、O(logN)C、NlogN2和NlogND、O(N)正確答案：C8.對(duì)于任意一棵高度為5且有10個(gè)結(jié)點(diǎn)的二叉樹(shù)，若采用順序存儲(chǔ)結(jié)構(gòu)保存，每個(gè)結(jié)點(diǎn)占1個(gè)存儲(chǔ)單元（僅存放結(jié)點(diǎn)的數(shù)據(jù)信息），則存放該二叉樹(shù)需要的存儲(chǔ)單元的數(shù)量至少是：A、15B、16C、10D、31正確答案：D9.將M個(gè)元素存入用長(zhǎng)度為S的數(shù)組表示的散列表，則該表的裝填因子為：A、M/SB、M×SC、M?SD、S+M正確答案：A10.求整數(shù)n(n>=0)的階乘的算法如下，其時(shí)間復(fù)雜度為（）。longfact(longn){if(n<=1)return1；returnn*fact(n-1)；}A、Θ(n2)B、Θ(nlog2n)C、Θ(log2n)D、Θ(n)正確答案：D11.若二叉搜索樹(shù)是有N個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，則不正確的說(shuō)法是：A、所有結(jié)點(diǎn)的平均查找效率是O(logN)B、最小值一定在葉結(jié)點(diǎn)上C、最大值一定在葉結(jié)點(diǎn)上D、中位值結(jié)點(diǎn)在根結(jié)點(diǎn)或根的左子樹(shù)上正確答案：C12.對(duì)一組包含10個(gè)元素的非遞減有序序列，采用直接插入排序排成非遞增序列，其可能的比較次數(shù)和移動(dòng)次數(shù)分別是：A、54,63B、100,100C、45,44D、100,54正確答案：C13.堆的形狀是一棵：A、非二叉樹(shù)B、二叉搜索樹(shù)C、完全二叉樹(shù)D、滿(mǎn)二叉樹(shù)正確答案：C14.下列各種數(shù)據(jù)結(jié)構(gòu)中屬于線性結(jié)構(gòu)的有()A、圖B、隊(duì)列C、集合D、樹(shù)正確答案：B15.若數(shù)據(jù)元素序列{11，12，13，7，8，9，23，4，5}是采用下列排序方法之一得到的第二趟排序后的結(jié)果，則該排序算法只能是：A、冒泡排序B、插入排序C、歸并排序D、選擇排序正確答案：B16.已知不相交集合用數(shù)組表示為{4,6,5,2,-3,-4,3}。若集合元素從1到7編號(hào)，則調(diào)用Union(Find(7),Find(1))（按規(guī)模求并，并且?guī)窂綁嚎s）后的結(jié)果數(shù)組為：A、{4,6,5,2,6,-7,3}B、{6,6,5,6,6,-7,5}C、{6,6,5,6,-7,5,5}D、{4,6,5,2,-7,5,3}正確答案：B17.設(shè)一個(gè)堆棧的入棧順序是1、2、3、4、5。若第一個(gè)出棧的元素是4，則最后一個(gè)出棧的元素必定是：A、1或者5B、1C、3D、5正確答案：A18.下列說(shuō)法不正確的是：A、圖的深度遍歷不適用于有向圖B、遍歷的基本算法有兩種：深度遍歷和廣度遍歷C、圖的遍歷是從給定的源點(diǎn)出發(fā)每一個(gè)頂點(diǎn)僅被訪問(wèn)一次D、圖的深度遍歷是一個(gè)遞歸過(guò)程正確答案：A19.對(duì)一棵二叉樹(shù)的結(jié)點(diǎn)從1開(kāi)始順序編號(hào)。要求每個(gè)結(jié)點(diǎn)的編號(hào)都小于其子樹(shù)所有結(jié)點(diǎn)的編號(hào)，且左子樹(shù)所有結(jié)點(diǎn)的編號(hào)都小于右子樹(shù)所有結(jié)點(diǎn)的編號(hào)。可采用▁▁▁▁▁實(shí)現(xiàn)編號(hào)。A、層次遍歷B、后序遍歷C、先序遍歷D、中序遍歷正確答案：C20.在將數(shù)據(jù)序列（6,1,5,9,8,4,7）建成大根堆時(shí)，正確的序列變化過(guò)程是：A、6,1,7,9,8,4,5→6,9,7,1,8,4,5→9,6,7,1,8,4,5→9,8,7,1,6,4,5B、6,9,5,1,8,4,7→9,6,5,1,8,4,7→9,6,7,1,8,4,5→9,8,7,1,6,4,5C、6,9,5,1,8,4,7→6,9,7,1,8,4,5→9,6,7,1,8,4,5→9,8,7,1,6,4,5D、6,1,7,9,8,4,5→7,1,6,9,8,4,5→7,9,6,1,8,4,5→9,7,6,1,8,4,5→9,8,6,1,7,4,5正確答案：A21.適用于壓縮存儲(chǔ)稀疏矩陣的兩種存儲(chǔ)結(jié)構(gòu)是：A、十字鏈表和二叉鏈表B、三元組表和十字鏈表C、鄰接矩陣和十字鏈表D、三元組表和鄰接矩陣正確答案：B22.斐波那契數(shù)列FN的定義為：F0=0,F1=1,FN=FN?1+FN?2,N=2,3,…。用遞歸函數(shù)計(jì)算FN的空間復(fù)雜度是：A、O(FN)B、O(N)C、O(N!)D、O(logN)正確答案：B23.T(n)表示當(dāng)輸入規(guī)模為n時(shí)的算法效率，以下算法中效率最優(yōu)的是()。A、T(n)=2n2B、T(n)=T(n/2)+1,T(1)=1C、T(n)=T(n-1)+1,T(1)=1D、T(n)=3nlog2n正確答案：B24.關(guān)于圖的鄰接矩陣，下列哪個(gè)結(jié)論是正確的？A、有向圖的鄰接矩陣可以是對(duì)稱(chēng)的，也可以是不對(duì)稱(chēng)的B、無(wú)向圖的鄰接矩陣總是不對(duì)稱(chēng)的C、無(wú)向圖的鄰接矩陣可以是不對(duì)稱(chēng)的，也可以是對(duì)稱(chēng)的D、有向圖的鄰接矩陣總是不對(duì)稱(chēng)的正確答案：A25.在一個(gè)有2333個(gè)元素的最小堆中，下列哪個(gè)下標(biāo)不可能是最大元的位置？A、2047B、1116C、2232D、1167正確答案：B26.從一個(gè)具有N個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于X的結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較多少個(gè)結(jié)點(diǎn)？A、N/2B、(N?1)/2C、ND、(N+1)/2正確答案：D27.若棧S1中保存整數(shù)，棧S2中保存運(yùn)算符，函數(shù)F()依次執(zhí)行下述各步操作：（1）從S1中依次彈出兩個(gè)操作數(shù)a和b；（2）從S2中彈出一個(gè)運(yùn)算符op；（3）執(zhí)行相應(yīng)的運(yùn)算bopa；（4）將運(yùn)算結(jié)果壓入S1中。假定S1中的操作數(shù)依次是{5,8,3,2}（2在棧頂），S2中的運(yùn)算符依次是{*,-,+}（+在棧頂）。調(diào)用3次F()后，S1棧頂保存的值是：A、-20B、15C、20D、-15正確答案：B28.已知求平方根函數(shù)sqrt(n)的計(jì)算在O(1)時(shí)間內(nèi)完成，下面算法的時(shí)間復(fù)雜度是（）。AlgorithmPrimalityTestInput：n,n≥2Output：true/falses←sqrt(n)forj←2tosdoif(nmodj==0)thenreturnfalsereturntrueA、O(1)B、O(√￣n)C、Ω(n)D、Ω(n2)正確答案：B29.已知二維數(shù)組A按行優(yōu)先方式存儲(chǔ)，每個(gè)元素占用1個(gè)存儲(chǔ)單元。若元素A[0][0]的存儲(chǔ)地址是100，A[3][3]的存儲(chǔ)地址是220，則元素A[5][5]的存儲(chǔ)地址是：A、295B、300C、301D、306正確答案：B30.二叉樹(shù)的形態(tài)由3個(gè)結(jié)點(diǎn)可以構(gòu)造出▁▁▁▁▁種不同形態(tài)的二叉樹(shù)。A、2B、4C、3D、5正確答案：D31.對(duì)于一個(gè)具有N個(gè)結(jié)點(diǎn)的單鏈表，在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為A、O(1)B、O(N2)C、O(N)D、O(N/2)正確答案：C32.Forthefollowingpieceofcodefor(i=0;i<n;i++)for(j=i;j>0;j/=2)printf(“%d\n”,j);thetimecomplexityis:A、O(N2)B、O(N)C、O(NlogN)D、O(N×i)正確答案：C33.對(duì)于序列{49，38，65，97，76，13，27，50}，按由小到大進(jìn)行排序，下面哪一個(gè)是初始步長(zhǎng)為4的希爾排序法第一趟的結(jié)果？A、49,13,27,50,76,38,65,97B、97,76,65,50,49,38,27,13C、49,76,65,13,27,50,97,38D、13,27,38,49,50,65,76,97正確答案：A34.設(shè)T是非空二叉樹(shù)，若T的后序遍歷和中序遍歷序列相同，則T的形態(tài)是__A、只有一個(gè)根結(jié)點(diǎn)B、沒(méi)有度為1的結(jié)點(diǎn)C、所有結(jié)點(diǎn)只有左孩子D、所有結(jié)點(diǎn)只有右孩子正確答案：C35.利用大小為n的數(shù)組（下標(biāo)從0到n-1）存儲(chǔ)一個(gè)棧時(shí)，假定棧從數(shù)組另一頭開(kāi)始且top==n表示?？眨瑒t向這個(gè)棧插入一個(gè)元素時(shí)，修改top指針應(yīng)當(dāng)執(zhí)行：A、top不變B、top++C、top=0D、top--正確答案：D36.設(shè)每個(gè)d叉樹(shù)的結(jié)點(diǎn)有d個(gè)指針指向子樹(shù)，有n個(gè)結(jié)點(diǎn)的d叉樹(shù)有多少空鏈域？A、n(d?1)+1B、n(d?1)+1C、ndD、n(d?1)正確答案：A37.將兩個(gè)結(jié)點(diǎn)數(shù)都為N且都從小到大有序的單向鏈表合并成一個(gè)從小到大有序的單向鏈表，那么可能的最少比較次數(shù)是：A、NlogNB、NC、1D、2N正確答案：B38.為解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫(xiě)入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是？A、圖B、堆棧C、隊(duì)列D、樹(shù)正確答案：C39.AVL樹(shù)是一種平衡的二叉搜索樹(shù)，樹(shù)中任一結(jié)點(diǎn)具有下列哪一特性：A、左、右子樹(shù)的高度均相同B、左、右子樹(shù)高度差的絕對(duì)值不超過(guò)1C、左子樹(shù)的高度均大于右子樹(shù)的高度D、左子樹(shù)的高度均小于右子樹(shù)的高度正確答案：B40.二叉樹(shù)的高度若根節(jié)點(diǎn)為高度1，一棵具有1025個(gè)結(jié)點(diǎn)的二叉樹(shù)的高度為▁▁▁▁▁。A、11B、11～1025之間C、10D、10～1024之間正確答案：B41.對(duì)N個(gè)記錄進(jìn)行歸并排序，歸并趟數(shù)的數(shù)量級(jí)是：A、O(N)B、O(N2)C、O(NlogN)D、O(logN)正確答案：D42.從棧頂指針為ST的鏈棧中刪除一個(gè)結(jié)點(diǎn)且用X保存被刪結(jié)點(diǎn)的值，則執(zhí)行：A、X=ST->data;B、ST=ST->next;X=ST->data;C、X=ST;ST=ST->next;D、X=ST->data;ST=ST->next;正確答案：D43.將6、4、3、5、8、9順序插入初始為空的最大堆（大根堆）中，那么插入完成后堆頂?shù)脑貫椋篈、5B、6C、9D、3正確答案：C44.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）。A、動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)C、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)D、線性結(jié)構(gòu)和非線性結(jié)構(gòu)正確答案：D45.度量結(jié)果集相關(guān)性時(shí)，如果準(zhǔn)確率很高而召回率很低，則說(shuō)明：A、大部分檢索出的文件都是相關(guān)的，但還有很多相關(guān)文件沒(méi)有被檢索出來(lái)B、大部分檢索出的文件都是相關(guān)的，但基準(zhǔn)數(shù)據(jù)集不夠大C、大部分相關(guān)文件被檢索到，但基準(zhǔn)數(shù)據(jù)集不夠大D、大部分相關(guān)文件被檢索到，但很多不相關(guān)的文件也在檢索結(jié)果里正確答案：A46.設(shè)數(shù)字{4371,1323,6173,4199,4344,9679,1989}在大小為10的散列表中根據(jù)散列函數(shù)h(X)=X%10得到的下標(biāo)對(duì)應(yīng)為{1,3,4,9,5,0,2}。那么繼續(xù)用散列函數(shù)“h(X)=X%表長(zhǎng)”實(shí)施再散列并用線性探測(cè)法解決沖突后，它們的下標(biāo)變?yōu)椋篈、1,3,4,9,5,0,2B、1,12,17,0,13,8,14C、1,12,9,13,20,19,11D、11,3,13,19,4,0,9正確答案：C47.如果A和B都是二叉樹(shù)的葉結(jié)點(diǎn)，那么下面判斷中哪個(gè)是對(duì)的？A、存在一種二叉樹(shù)結(jié)構(gòu)，其前序遍歷結(jié)果是…A…B…，而中序遍歷結(jié)果是…B…A…B、存在一種二叉樹(shù)結(jié)構(gòu)，其中序遍歷結(jié)果是…A…B…，而后序遍歷結(jié)果是…B…A…C、存在一種二叉樹(shù)結(jié)構(gòu)，其前序遍歷結(jié)果是…A…B…，而后序遍歷結(jié)果是…B…A…D、以上三種都是錯(cuò)的正確答案：D48.下列幾組概念中，那一組不完全跟搜索引擎有關(guān)？A、詞干提取，壓縮，召回率B、分布式索引，哈希散列，倒排文件索引C、閾值設(shè)置，動(dòng)態(tài)規(guī)劃，準(zhǔn)確率D、停用詞，倒排表，動(dòng)態(tài)索引正確答案：C49.WhichoneofthefollowingisthelowestupperboundofT(n)forthefollowingrecursionT(n)=2T(n/2)+nlogn?A、O(nlogn)B、O(nlog2n)C、O(n2logn)D、O(n2)正確答案：B50.對(duì)N個(gè)不同的數(shù)據(jù)采用冒泡算法進(jìn)行從大到小的排序，下面哪種情況下肯定交換元素次數(shù)最多？A、從小到大排好的B、元素?zé)o序C、從大到小排好的D、元素基本有序正確答案：A51.在作進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否(①)；在作退棧運(yùn)算時(shí)應(yīng)先判別棧是否(②)。當(dāng)棧中元素為n個(gè)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說(shuō)明該棧的最大容量為(③)。①:A.空B.滿(mǎn)C.上溢D.下溢②:A.空B.滿(mǎn)C.上溢D.下溢③:A.n-1B.nC.n+1D.n/2A、①C②D③BB、①B②A③BC、①B②B③AD、①B②A③A正確答案：B52.具有5個(gè)頂點(diǎn)的有向完全圖有多少條弧？A、20B、10C、25D、16正確答案：A53.將{28,15,42,18,22,5,40}依次插入初始為空的二叉搜索樹(shù)。則該樹(shù)的后序遍歷結(jié)果是：A、5,22,18,15,40,42,28B、5,15,18,22,40,42,28C、28,22,18,42,40,15,5D、5,22,15,40,18,42,28正確答案：A54.給定一個(gè)堆棧的入棧序列為{1,2,?,n}，出棧序列為{p1,p2,?,pn}。如果p2=n，則存在多少種不同的出棧序列？A、n?1B、2C、1D、n正確答案：A55.算法分析的目的是()A、找出數(shù)據(jù)結(jié)構(gòu)的合理性B、研究算法中的輸入和輸出的關(guān)系C、分析算法的效率以求改進(jìn)D、分析算法的易讀性和文檔性正確答案：C56.在拓?fù)渑判蛩惴ㄖ杏枚褩：陀藐?duì)列產(chǎn)生的結(jié)果會(huì)不同嗎？A、是的肯定不同B、肯定是相同的C、有可能會(huì)不同D、以上全不對(duì)正確答案：C57.設(shè)有一個(gè)12×12的對(duì)稱(chēng)矩陣M，將其上三角部分的元素mi,j（1≤i≤j≤12）按行優(yōu)先存入C語(yǔ)言的一維數(shù)組N中，元素m6,6在N中的下標(biāo)是：A、50B、51C、55D、66正確答案：A58.給定散列表大小為11，散列函數(shù)為H(Key)=Key%11。按照線性探測(cè)沖突解決策略連續(xù)插入散列值相同的4個(gè)元素。問(wèn)：此時(shí)該散列表的平均不成功查找次數(shù)是多少？A、不確定B、4/11C、21/11D、1正確答案：C59.采用多項(xiàng)式的非零項(xiàng)鏈?zhǔn)酱鎯?chǔ)表示法，如果兩個(gè)多項(xiàng)式的非零項(xiàng)分別為N1和N2個(gè)，最高項(xiàng)指數(shù)分別為M1和M2，則實(shí)現(xiàn)兩個(gè)多項(xiàng)式相乘的時(shí)間復(fù)雜度是：A、O(M1+M2)B、O(N1×N2)C、O(M1×M2)D、O(N1+N2)正確答案：B60.給定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正確答案：B61.在快速排序的一趟劃分過(guò)程中，當(dāng)遇到與基準(zhǔn)數(shù)相等的元素時(shí)，如果左指針停止移動(dòng)，而右指針在同樣情況下卻不停止移動(dòng)，那么當(dāng)所有元素都相等時(shí)，算法的時(shí)間復(fù)雜度是多少？A、O(N2)B、O(N)C、O(logN)D、O(NlogN)正確答案：A62.輸入105個(gè)只有一位數(shù)字的整數(shù)，可以用O(N)復(fù)雜度將其排序的算法是：A、快速排序B、插入排序C、基數(shù)排序D、希爾排序正確答案：C63.循環(huán)隊(duì)列的隊(duì)滿(mǎn)條件為()。A、(sq.front+1)%maxsize==sq.rearB、sq.rear==sq.frontC、(sq.rear+1)%maxsize==sq.frontD、(sq.rear+1)%maxsize==(sq.front+1)%maxsize正確答案：C64.關(guān)于存儲(chǔ)結(jié)構(gòu)▁▁▁▁▁的特點(diǎn)是借助指示元素存儲(chǔ)地址的指針來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。A、索引存儲(chǔ)結(jié)構(gòu)B、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C、散列存儲(chǔ)結(jié)構(gòu)D、順序存儲(chǔ)結(jié)構(gòu)正確答案：B65.一棵二叉樹(shù)中有7個(gè)度為2的結(jié)點(diǎn)和5個(gè)度為1的結(jié)點(diǎn)，其總共有（）個(gè)結(jié)點(diǎn)。A、18B、30C、16D、20正確答案：D66.下面四種排序算法中，穩(wěn)定的算法是：A、快速排序B、希爾排序C、堆排序D、歸并排序正確答案：D67.對(duì)10TB的數(shù)據(jù)文件進(jìn)行排序，應(yīng)使用的方法是：A、希爾排序B、堆排序C、歸并排序D、快速排序正確答案：C68.一棵度為4的樹(shù)T中，若有20個(gè)度為4的結(jié)點(diǎn)，10個(gè)度為3的結(jié)點(diǎn)，1個(gè)度為2的結(jié)點(diǎn)，10個(gè)度為1的結(jié)點(diǎn)，則樹(shù)T的葉子結(jié)點(diǎn)個(gè)數(shù)是()。A、113B、41C、122D、82正確答案：D69.在有n（n>1000）個(gè)元素的升序數(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ù)組開(kāi)頭處C、當(dāng)x接近數(shù)組開(kāi)頭處D、當(dāng)x位于數(shù)組中間位置正確答案：B70.鏈表-存儲(chǔ)密度鏈表的存儲(chǔ)密度▁▁▁▁▁。A、大于1B、小于1C、不能確定D、等于1正確答案：B71.設(shè)森林F中有三棵樹(shù)，第一、第二、第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為M1，M2和M3。則與森林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是：A、M1B、M1+M2C、M3D、M2+M3正確答案：D72.給定N×N×N的三維數(shù)組A，則在不改變數(shù)組的前提下，查找最小元素的時(shí)間復(fù)雜度是：A、O(N2)B、O(NlogN)C、O(N2logN)D、O(N3)正確答案：D73.設(shè)有1000個(gè)元素的有序序列，如果用二分插入排序再插入一個(gè)元素，則最大比較次數(shù)是：A、1000B、10C、500D、999正確答案：B74.設(shè)有圖的數(shù)據(jù)邏輯結(jié)構(gòu)B=(K,R)，其中頂點(diǎn)集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>}。以下哪個(gè)選項(xiàng)不是對(duì)應(yīng)DAG圖的拓?fù)湫蛄?？A、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正確答案：C75.下面說(shuō)法中哪個(gè)是錯(cuò)誤的：A、任何AVL樹(shù)的中序遍歷結(jié)果是有序的（從小到大）B、任何最小堆的前序遍歷結(jié)果是有序的（從小到大）C、任何搜索樹(shù)中同一層的結(jié)點(diǎn)從左到右是有序的（從小到大）D、任何最小堆中從根結(jié)點(diǎn)到任一葉結(jié)點(diǎn)路徑上的所有結(jié)點(diǎn)是有序的（從小到大）正確答案：B76.已知一棵二叉樹(shù)的前序遍歷結(jié)果為ABCDEFG,中序遍歷結(jié)果為BCAEDGF,則后序遍歷的結(jié)果為（）。A、CBAEGFDB、CBEGFDAC、BCEGFDAD、CBEFGDA正確答案：B77.用二分查找從100個(gè)有序整數(shù)中查找某數(shù)，最壞情況下需要比較的次數(shù)是：A、50B、10C、7D、99正確答案：C78.設(shè)有一順序棧S，元素s1,s2,s3,s4,s5,s6依次進(jìn)棧，如果6個(gè)元素出棧的順序是s2,s3,s4,s6,s5,s1,則棧的容量至少應(yīng)該是()。A、5B、3C、2D、6正確答案：B79.以下說(shuō)法正確的是（）。A、數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合B、一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)C、數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位D、數(shù)據(jù)元素是數(shù)據(jù)的最小單位正確答案：B80.一個(gè)具有1025個(gè)節(jié)點(diǎn)的二叉樹(shù)的高h(yuǎn)為（）A、11～1025B、11C、10D、12～1024正確答案：A81.若采用帶頭、尾指針的單向鏈表表示一個(gè)堆棧，那么該堆棧的棧頂指針top應(yīng)該如何設(shè)置？A、將鏈表尾設(shè)為topB、鏈表頭、尾都不適合作為topC、將鏈表頭設(shè)為topD、隨便哪端作為top都可以正確答案：C82.對(duì)于外排序中的k路歸并，k不取很大值的首要原因是：A、輸入\輸出的時(shí)間會(huì)增多B、k必須是一個(gè)有限的整數(shù)C、k的上界是有序段的個(gè)數(shù)D、歸并時(shí)的比較次數(shù)會(huì)增多正確答案：A83.已知一個(gè)長(zhǎng)度為16的順序表L，其元素按關(guān)鍵字有序排列。若采用二分查找法查找一個(gè)L中不存在的元素，則關(guān)鍵字的比較次數(shù)最多是：A、7B、6C、4D、5正確答案：D84.中位值結(jié)點(diǎn)在根結(jié)點(diǎn)或根的左子樹(shù)上A、4B、2C、1D、3正確答案：B85.設(shè)T是非空二叉樹(shù)，若T的先序遍歷和后序遍歷序列相同，則T的形態(tài)是A、只有一個(gè)根結(jié)點(diǎn)B、沒(méi)有度為1的結(jié)點(diǎn)C、所有結(jié)點(diǎn)只有左孩子D、所有結(jié)點(diǎn)只有右孩子正確答案：A86.下面的程序段違反了算法的（）原則。voidsam(){intn=2;while(n%2==0)n+=2;printf(“%d”,n);}A、有窮性B、可行性C、確定性D、健壯性正確答案：A二、多選題（共3題，每題1分，共3分）1.下面結(jié)構(gòu)中適于表示稀疏有向圖的是（）。A、鄰接矩陣B、鄰接多重表C、鄰接表D、逆鄰接表E、十字鏈表正確答案：CDE2.以下哪些項(xiàng)是棧元素操作的基本特點(diǎn)：A、先進(jìn)先出B、后進(jìn)先出C、先進(jìn)后出D、后進(jìn)后出正確答案：BC3.關(guān)于順序查找算法順序查找算法能適用于▁▁▁▁▁。A、元素有序的鏈表B、元素?zé)o序的鏈表C、元素?zé)o序的順序表D、元素有序的順序表正確答案：ABCD三、判斷題（共26題，每題1分，共26分）1.關(guān)于《數(shù)據(jù)結(jié)構(gòu)》學(xué)科《數(shù)據(jù)結(jié)構(gòu)》是一門(mén)研究數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題的學(xué)科。A、正確B、錯(cuò)誤正確答案：B2.在實(shí)現(xiàn)二項(xiàng)式隊(duì)列時(shí)，每棵二項(xiàng)式樹(shù)的子樹(shù)是按規(guī)模遞增的順序鏈接的。A、正確B、錯(cuò)誤正確答案：B3.將10個(gè)元素散列到100000個(gè)單元的哈希表中，一定不會(huì)產(chǎn)生沖突。A、正確B、錯(cuò)誤正確答案：B4.若圖G有環(huán)，則G不存在拓?fù)渑判蛐蛄?。A、正確B、錯(cuò)誤正確答案：A5.若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用順序表存儲(chǔ)最節(jié)省時(shí)間。A、正確B、錯(cuò)誤正確答案：A6.若一個(gè)棧的輸入序列為{1,2,3,4,5}，則不可能得到{3,