數(shù)據(jù)結(jié)構(gòu)與算法模擬練習(xí)題含答案

數(shù)據(jù)結(jié)構(gòu)與算法模擬練習(xí)題含答案一、單選題（共86題，每題1分，共86分）1.數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理相對(duì)位置和邏輯相對(duì)位置相同并且是連續(xù)的，稱之為（）。A、邏輯結(jié)構(gòu)B、順序存儲(chǔ)結(jié)構(gòu)C、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D、以上都不對(duì)正確答案：B2.對(duì)于給定的有權(quán)無向圖G，下列哪個(gè)說法是正確的？A、G的最小生成樹中，任意一對(duì)頂點(diǎn)間的路徑必是它們?cè)贕中的最短路徑B、設(shè)頂點(diǎn)V到W的最短路徑為P。若我們將G中每條邊的權(quán)重都加1，則P一定仍然是V到W的最短路徑C、單源最短路問題可以用O(∣E∣+∣V∣)的時(shí)間解決D、以上都不對(duì)正確答案：D3.被計(jì)算機(jī)加工的數(shù)據(jù)元素不是孤立的，它們彼此之間一般存在某種關(guān)系，通常把數(shù)據(jù)元素之間的這種關(guān)系稱為A、結(jié)構(gòu)B、運(yùn)算C、集合D、規(guī)則正確答案：A4.若棧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、-15B、15C、-20D、20正確答案：B5.關(guān)于存儲(chǔ)結(jié)構(gòu)▁▁▁▁▁的特點(diǎn)是借助指示元素存儲(chǔ)地址的指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。A、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B、索引存儲(chǔ)結(jié)構(gòu)C、順序存儲(chǔ)結(jié)構(gòu)D、散列存儲(chǔ)結(jié)構(gòu)正確答案：A6.算法分析的目的是()A、找出數(shù)據(jù)結(jié)構(gòu)的合理性B、研究算法中的輸入和輸出的關(guān)系C、分析算法的易讀性和文檔性D、分析算法的效率以求改進(jìn)正確答案：D7.若一個(gè)棧的入棧序列為1、2、3、…、N，輸出序列的第一個(gè)元素是i，則第j個(gè)輸出元素是：A、j?i?1B、i?jC、不確定D、i?j?1正確答案：C8.給定初始待排序列{15，9，7，8，20，-1，4}。如果希爾排序第一趟結(jié)束后得到序列為{15，-1，4，8，20，9，7}，則該趟增量為：A、3B、2C、4D、1正確答案：C9.某二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹一定是（）A、空或只有一個(gè)節(jié)點(diǎn)B、完全二叉樹C、二叉排序樹D、高度等于其節(jié)點(diǎn)數(shù)正確答案：D10.二叉樹的高度若根節(jié)點(diǎn)為高度1，一棵具有1025個(gè)結(jié)點(diǎn)的二叉樹的高度為▁▁▁▁▁。A、11～1025之間B、10C、11D、10～1024之間正確答案：A11.在AOE網(wǎng)中，什么是關(guān)鍵路徑？A、最短回路B、最長(zhǎng)回路C、從第一個(gè)事件到最后一個(gè)事件的最短路徑D、從第一個(gè)事件到最后一個(gè)事件的最長(zhǎng)路徑正確答案：D12.一棵有1001個(gè)結(jié)點(diǎn)的完全二叉樹，其葉子結(jié)點(diǎn)數(shù)為▁▁▁▁▁。A、250B、500C、254D、501正確答案：D13.在將數(shù)據(jù)序列（6,1,5,9,8,4,7）建成大根堆時(shí)，正確的序列變化過程是：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→6,9,7,1,8,4,5→9,6,7,1,8,4,5→9,8,7,1,6,4,5C、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,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正確答案：A14.設(shè)散列表的地址區(qū)間為[0,16]，散列函數(shù)為H(Key)=Key%17。采用線性探測(cè)法處理沖突，并將關(guān)鍵字序列{26，25，72，38，8，18，59}依次存儲(chǔ)到散列表中。元素59存放在散列表中的地址是：A、11B、10C、8D、9正確答案：A15.在下列查找的方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)無關(guān)的查找方法是：A、二分法B、利用二叉搜索樹C、順序查找D、利用哈希（散列）表正確答案：D16.已知不相交集合用數(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,-7,5,3}B、{4,6,5,2,6,-7,3}C、{6,6,5,6,6,-7,5}D、{6,6,5,6,-7,5,5}正確答案：C17.若一棵AVL樹有28個(gè)結(jié)點(diǎn)，則該樹的最大深度為__?？諛涞纳疃榷x為0。A、4B、5C、6D、7正確答案：C18.已知一棵二叉樹的前序遍歷結(jié)果為ABCDEFG,中序遍歷結(jié)果為BCAEDGF,則后序遍歷的結(jié)果為（）。A、CBAEGFDB、CBEGFDAC、BCEGFDAD、CBEFGDA正確答案：B19.有兩個(gè)垃圾郵件檢測(cè)系統(tǒng)，分別用帶有10000封正常郵件和2000封垃圾郵件的數(shù)據(jù)集進(jìn)行測(cè)試。系統(tǒng)A檢測(cè)出了300封正常郵件和1600封垃圾郵件，系統(tǒng)B檢測(cè)出了315封正常郵件和1800封垃圾郵件。如果我們重點(diǎn)關(guān)注的是保證重要郵件的安全，下列哪句陳述是正確的？A、我們應(yīng)重點(diǎn)關(guān)注準(zhǔn)確率，系統(tǒng)A更好一些。B、我們應(yīng)重點(diǎn)關(guān)注召回率，系統(tǒng)B更好一些。C、我們應(yīng)重點(diǎn)關(guān)注準(zhǔn)確率，系統(tǒng)B更好一些。D、我們應(yīng)重點(diǎn)關(guān)注召回率，系統(tǒng)A更好一些。正確答案：C20.已知字符集{a,b,c,d,e,f}，若各字符出現(xiàn)的次數(shù)分別為{6,3,8,2,10,4}，則對(duì)應(yīng)字符集中各字符的哈夫曼編碼可能是：A、00,100,110,000,0010,01B、00,1011,01,1010,11,100C、0011,10,11,0010,01,000D、10,1011,11,0011,00,010正確答案：B21.設(shè)一棵非空完全二叉樹T的所有葉節(jié)點(diǎn)均位于同一層，且每個(gè)非葉結(jié)點(diǎn)都有2個(gè)子結(jié)點(diǎn)。若T有k個(gè)葉結(jié)點(diǎn)，則T的結(jié)點(diǎn)總數(shù)是：A、2k?1B、2kC、k2D、2k?1正確答案：D22.下列幾組概念中，那一組不完全跟搜索引擎有關(guān)？A、分布式索引，回溯法，查詢B、倒排文件索引，停用詞，準(zhǔn)確率C、詞干提取，哈希散列，壓縮D、倒排表，閾值設(shè)置，召回率正確答案：A23.一棵非空二叉樹，若先序遍歷與中序遍歷的序列相同，則該二叉樹▁▁▁▁▁。A、所有結(jié)點(diǎn)均無左孩子B、所有結(jié)點(diǎn)均無右孩子C、只有一個(gè)葉子結(jié)點(diǎn)D、為任意二叉樹正確答案：A24.設(shè)T是非空二叉樹，若T的后序遍歷和中序遍歷序列相同，則T的形態(tài)是__A、只有一個(gè)根結(jié)點(diǎn)B、沒有度為1的結(jié)點(diǎn)C、所有結(jié)點(diǎn)只有左孩子D、所有結(jié)點(diǎn)只有右孩子正確答案：C25.對(duì)N個(gè)記錄進(jìn)行堆排序，最壞的情況下時(shí)間復(fù)雜度是：A、O(logN)B、O(N2)C、O(NlogN)D、O(N)正確答案：C26.將元素序列{18，23，11，20，2，7，27，33，42，15}按順序插入一個(gè)初始為空的、大小為11的散列表中。散列函數(shù)為：H(Key)=Key%11，采用線性探測(cè)法處理沖突。問：當(dāng)?shù)谝淮伟l(fā)現(xiàn)有沖突時(shí)，散列表的裝填因子大約是多少？A、0.27B、0.73C、0.64D、0.45正確答案：D27.已知有向圖G=(V,E)，其中V={v1,v2,v3,v4,v5,v6}，E={<v1,v2>,<v1,v4>,<v2,v6>,<v3,v1>,<v3,v4>,<v4,v5>,<v5,v2>,<v5,v6>}。G的拓?fù)湫蛄惺牵篈、v1,v3,v4,v5,v2,v6B、v1,v3,v4,v5,v2,v6C、v3,v1,v4,v5,v2,v6D、v3,v4,v1,v5,v2,v6正確答案：C28.給定散列表大小為11，散列函數(shù)為H(Key)=Key%11。采用平方探測(cè)法處理沖突：hi(k)=(H(k)±i2)%11將關(guān)鍵字序列{6，25，39，61}依次插入到散列表中。那么元素61存放在散列表中的位置是：A、5B、6C、7D、8正確答案：A29.在下述結(jié)論中，正確的是：①只有2個(gè)結(jié)點(diǎn)的樹的度為1；②二叉樹的度為2；③二叉樹的左右子樹可任意交換；④在最大堆（大頂堆）中，從根到任意其它結(jié)點(diǎn)的路徑上的鍵值一定是按非遞增有序排列的。A、①④B、②③④C、①②③D、②④正確答案：A30.線性表L在什么情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)？A、L中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜B、需不斷對(duì)L進(jìn)行刪除插入C、需經(jīng)常修改L中的結(jié)點(diǎn)值D、L中含有大量的結(jié)點(diǎn)正確答案：B31.對(duì)于先序遍歷與中序遍歷結(jié)果相同的二叉樹為（）A、一般二叉樹B、任一結(jié)點(diǎn)均無右孩子的二叉樹C、任一結(jié)點(diǎn)均無左子樹的二叉樹D、以上都不是正確答案：C32.將元素序列{18,23,4,26,31,33,17,39}按順序插入一個(gè)初始為空的、大小為13的散列表中。散列函數(shù)為：H(Key)=Key%13，采用線性探測(cè)法處理沖突。問：當(dāng)?shù)谝淮伟l(fā)現(xiàn)有沖突時(shí)，散列表的裝填因子大約是多少？A、0.63B、0.62C、0.31D、0.54正確答案：C33.給定散列表大小為11，散列函數(shù)為H(Key)=Key%11。按照線性探測(cè)沖突解決策略連續(xù)插入散列值相同的4個(gè)元素。問：此時(shí)該散列表的平均不成功查找次數(shù)是多少？A、4/11B、1C、不確定D、21/11正確答案：D34.下面代碼段的時(shí)間復(fù)雜度是（）。for(i=0;i<n;i++)for(j=0;j<m;j++)a[i][j]=0;A、O(mn)B、O(n2)C、O(1)D、O(m2)正確答案：A35.下列說法不正確的是：A、遍歷的基本算法有兩種：深度遍歷和廣度遍歷B、圖的深度遍歷不適用于有向圖C、圖的深度遍歷是一個(gè)遞歸過程D、圖的遍歷是從給定的源點(diǎn)出發(fā)每一個(gè)頂點(diǎn)僅被訪問一次正確答案：B36.堆的形狀是一棵：A、滿二叉樹B、完全二叉樹C、二叉搜索樹D、非二叉樹正確答案：B37.將9,8,7,2,3,5,6,4順序插入一棵初始為空的AVL樹。下列句子中哪句是錯(cuò)的？A、5是根結(jié)點(diǎn)B、2和5是兄弟C、有2個(gè)結(jié)點(diǎn)的平衡因子為-1D、最后得到的AVL樹的高度是3正確答案：A38.任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序A、發(fā)生改變B、不發(fā)生改變C、不能確定D、以上都不對(duì)正確答案：B39.在一個(gè)有2333個(gè)元素的最小堆中，下列哪個(gè)下標(biāo)不可能是最大元的位置？A、2047B、1116C、1167D、2232正確答案：B40.將下列數(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正確答案：D41.單鏈表-插入結(jié)點(diǎn)在單鏈表中，將s所指新結(jié)點(diǎn)插入到p所指結(jié)點(diǎn)之后，其語句應(yīng)該為▁▁▁▁▁。A、s->next=p->next;p->next=s->next;B、s->next=p->next;p->next=s;C、p->next=s->next;s->next=p->next;D、p->next=s;s->next=p->next;正確答案：B42.給定N×N×N的三維數(shù)組A，則在不改變數(shù)組的前提下，查找最小元素的時(shí)間復(fù)雜度是：A、O(N2)B、O(NlogN)C、O(N2logN)D、O(N3)正確答案：D43.單鏈表-刪除結(jié)點(diǎn)在單鏈表中，刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)，其語句應(yīng)該為▁▁▁▁▁。A、s=p->next;p->next=s->next;B、s=p;p->next=s;C、s=p->next;p->next=s;D、s=p;p->next=s->next;正確答案：A44.設(shè)有一個(gè)12×12的對(duì)稱矩陣M，將其上三角部分的元素mi,j（1≤i≤j≤12）按行優(yōu)先存入C語言的一維數(shù)組N中，元素m6,6在N中的下標(biāo)是：A、50B、51C、55D、66正確答案：A45.具有N（N>0）個(gè)頂點(diǎn)的無向圖至多有多少個(gè)連通分量？A、N?1B、NC、1D、0正確答案：B46.表達(dá)式3*2^(4+2*2-6*3)-5求值過程中當(dāng)掃描到6時(shí)，對(duì)象棧和算符棧為（），其中^為乘冪。A、3,2,4,2,2；(*^(-B、3,2,4,1,1；(^(+-C、3,2,8；(*^-D、3,2,8；(*^(-正確答案：D47.對(duì)一棵二叉樹的結(jié)點(diǎn)從1開始順序編號(hào)。要求每個(gè)結(jié)點(diǎn)的編號(hào)都大于其子樹所有結(jié)點(diǎn)的編號(hào)，且左子樹所有結(jié)點(diǎn)的編號(hào)都小于右子樹所有結(jié)點(diǎn)的編號(hào)?？刹捎猫x▁▁▁▁實(shí)現(xiàn)編號(hào)。A、后序遍歷B、先序遍歷C、中序遍歷D、層次遍歷正確答案：A48.若AVL樹的深度是6（空樹的深度定義為-1），則該樹的最少結(jié)點(diǎn)數(shù)是：A、13B、17C、20D、33正確答案：D49.設(shè)數(shù)組S[]={93,946,372,9,146,151,301,485,236,327,43,892}，采用最低位優(yōu)先（LSD）基數(shù)排序?qū)排列成升序序列。第1趟分配、收集后，元素372之前、之后緊鄰的元素分別是：A、43，892B、236，301C、301，892D、485，301正確答案：C50.設(shè)有100個(gè)元素的有序序列，如果用二分插入排序再插入一個(gè)元素，則最大比較次數(shù)是：A、50B、10C、7D、25正確答案：C51.任何一個(gè)帶權(quán)無向連通圖的最小生成樹——A、是唯一的B、是不唯一的C、有可能不存在D、有可能不唯一正確答案：D52.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,5A、后序遍歷B、按層遍歷C、中序遍歷D、先序遍歷正確答案：C53.對(duì)N個(gè)記錄進(jìn)行歸并排序，歸并趟數(shù)的數(shù)量級(jí)是：A、O(logN)B、O(N)C、O(N2)D、O(NlogN)正確答案：A54.若采用帶頭、尾指針的單向鏈表表示一個(gè)堆棧，那么該堆棧的棧頂指針top應(yīng)該如何設(shè)置？A、鏈表頭、尾都不適合作為topB、將鏈表尾設(shè)為topC、將鏈表頭設(shè)為topD、隨便哪端作為top都可以正確答案：C55.對(duì)包含N個(gè)元素的散列表進(jìn)行查找，平均查找長(zhǎng)度為：A、O(logN)B、O(N)C、不確定D、O(1)正確答案：C56.在用鄰接表表示有N個(gè)結(jié)點(diǎn)E條邊的圖時(shí)，深度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為：A、O(N2)B、O(N)C、O(N+E)D、O(N2×E)正確答案：C57.設(shè)h為不帶頭結(jié)點(diǎn)的單向鏈表。在h的頭上插入一個(gè)新結(jié)點(diǎn)t的語句是：A、h=t;t->next=h;B、t->next=h->next;h=t;C、h=t;t->next=h->next;D、t->next=h;h=t;正確答案：D58.下列關(guān)于棧的敘述中，錯(cuò)誤的是：采用非遞歸方式重寫遞歸程序時(shí)必須使用棧函數(shù)調(diào)用時(shí)，系統(tǒng)要用棧保存必要的信息只要確定了入棧次序，即可確定出棧次序棧是一種受限的線性表，允許在其兩端進(jìn)行操作A、僅1、3、4B、僅1C、僅1、2、3D、僅1、3、4正確答案：D59.利用大小為n的數(shù)組（下標(biāo)從0到n-1）存儲(chǔ)一個(gè)棧時(shí)，假定棧從數(shù)組另一頭開始且top==n表示棧空，則向這個(gè)棧插入一個(gè)元素時(shí)，修改top指針應(yīng)當(dāng)執(zhí)行：A、top=0B、top++C、top不變D、top--正確答案：D60.WhichoneofthefollowingisthelowestupperboundofT(n)forthefollowingrecursionT(n)=2T(n/2)+nlogn?A、O(nlogn)B、O(n2)C、O(nlog2n)D、O(n2logn)正確答案：C61.下列關(guān)于無向連通圖特征的敘述中，正確的是：所有頂點(diǎn)的度之和為偶數(shù)邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1至少有一個(gè)頂點(diǎn)的度為1A、1和3B、只有1C、1和2D、只有2正確答案：B62.下列幾組概念中，那一組不完全跟搜索引擎有關(guān)？A、字典，準(zhǔn)確率，倒排文件索引B、動(dòng)態(tài)索引，停用詞，回溯法C、分布式索引，搜索樹，倒排表D、閾值設(shè)置，網(wǎng)頁排名，詞干提取正確答案：B63.若用大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前front和rear的值分別為0和4。當(dāng)從隊(duì)列中刪除兩個(gè)元素，再加入兩個(gè)元素后，front和rear的值分別為多少？A、2和2B、2和0C、2和4D、2和6正確答案：B64.對(duì)N個(gè)記錄進(jìn)行快速排序，在最壞的情況下，其時(shí)間復(fù)雜度是：A、O(N2)B、O(N)C、O(N2logN)D、O(NlogN)正確答案：A65.程序P1和P2時(shí)間復(fù)雜度的遞推公式：P1:T(1)=1,T(N)=T(N/2)+1;P2:T(1)=1,T(N)=2T(N/2)+1;則下列關(guān)于兩程序時(shí)間復(fù)雜度的結(jié)論中最準(zhǔn)確的是：A、均為O(logN)B、P1是O(logN)，P2是O(N)C、均為O(N)D、P1是O(logN)，P2是O(NlogN)正確答案：B66.如果AVL樹的深度為5（空樹的深度定義為0），則此樹最少有多少個(gè)結(jié)點(diǎn)？A、12B、20C、33D、64正確答案：A67.給定散列表大小為11，散列函數(shù)為H(Key)=Key%11。按照線性探測(cè)沖突解決策略連續(xù)插入散列值相同的5個(gè)元素。問：此時(shí)該散列表的平均不成功查找次數(shù)是多少？A、1B、26/11C、5/11D、不確定正確答案：B68.現(xiàn)有長(zhǎng)度為7、初始為空的散列表HT，散列函數(shù)H(k)=k%7，用線性探測(cè)再散列法解決沖突。將關(guān)鍵字22,43,15依次插入到HT后，查找成功的平均查找長(zhǎng)度是：A、1.6B、1.5C、3D、2正確答案：D69.將6、4、3、5、8、9順序插入初始為空的最大堆（大根堆）中，那么插入完成后堆頂?shù)脑貫椋篈、6B、9C、3D、5正確答案：B70.對(duì)10TB的數(shù)據(jù)文件進(jìn)行排序，應(yīng)使用的方法是：A、希爾排序B、堆排序C、歸并排序D、快速排序正確答案：C71.下面描述中正確的為()。A、線性表的邏輯順序與物理順序總是一致的B、線性表的順序存儲(chǔ)表示優(yōu)于鏈?zhǔn)酱鎯?chǔ)表示。C、線性表若采用鏈?zhǔn)酱鎯?chǔ)表示時(shí)所有結(jié)點(diǎn)之間的存儲(chǔ)單元地址可連續(xù)可不連續(xù)。D、二維數(shù)組是其數(shù)組元素為線性表的線性表。正確答案：C72.采用遞歸方式對(duì)順序表進(jìn)行快速排序，下列關(guān)于遞歸次數(shù)的敘述中，正確的是：A、遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關(guān)B、每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)C、每次劃分后，先處理較長(zhǎng)的分區(qū)可以減少遞歸次數(shù)D、遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無關(guān)正確答案：D73.若將n個(gè)頂點(diǎn)e條弧的有向圖采用鄰接表存儲(chǔ)，則拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度是：A、O(n)B、O(n2)C、O(n+e)D、O(n×e)正確答案：C74.設(shè)森林F中有三棵樹，第一、第二、第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為M1，M2和M3。則與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是：A、M2+M3B、M1+M2C、M1D、M3正確答案：A75.對(duì)于有向圖，其鄰接矩陣表示比鄰接表表示更易于：A、求一個(gè)頂點(diǎn)的入度B、進(jìn)行圖的深度優(yōu)先遍歷C、求一個(gè)頂點(diǎn)的出邊鄰接點(diǎn)D、進(jìn)行圖的廣度優(yōu)先遍歷正確答案：A76.對(duì)一棵二叉樹的結(jié)點(diǎn)從1開始順序編號(hào)。要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左子樹所有結(jié)點(diǎn)的編號(hào)、但小于右子樹中所有結(jié)點(diǎn)的編號(hào)?？刹捎猫x▁▁▁▁實(shí)現(xiàn)編號(hào)。A、層次遍歷B、先序遍歷C、中序遍歷D、后序遍歷正確答案：C77.設(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正確答案：C78.已知求平方根函數(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)正確答案：B79.用S表示入棧操作，X表示出棧操作，若元素入棧的順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為()。A、SXSSSXXXB、SXSSXSXXC、SSSSXXXXD、SXSXSXSX正確答案：B80.對(duì)給定序列{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正確答案：C81.用二分查找從100個(gè)有序整數(shù)中查找某數(shù)，最壞情況下需要比較的次數(shù)是：A、7B、99C、10D、50正確答案：A82.如果A和B都是二叉樹的葉結(jié)點(diǎn)，那么下面判斷中哪個(gè)是對(duì)的？A、存在一種二叉樹結(jié)構(gòu)，其前序遍歷結(jié)果是…A…B…，而中序遍歷結(jié)果是…B…A…B、存在一種二叉樹結(jié)構(gòu)，其中序遍歷結(jié)果是…A…B…，而后序遍歷結(jié)果是…B…A…C、存在一種二叉樹結(jié)構(gòu)，其前序遍歷結(jié)果是…A…B…，而后序遍歷結(jié)果是…B…A…D、以上三種都是錯(cuò)的正確答案：D83.對(duì)任意給定的含n(n>2)個(gè)字符的有限集S，用二叉樹表示S的哈夫曼編碼集和定長(zhǎng)編碼集，分別得到二叉樹T1和T2。下列敘述中，正確的是：A、T1的高度大于T2的高度B、出現(xiàn)頻次不同的字符在T1中處于不同的層C、出現(xiàn)頻次不同的字符在T2中處于相同的層D、T1與T2的結(jié)點(diǎn)數(shù)相同正確答案：C84.雙鏈表-插入結(jié)點(diǎn)在雙鏈表中，將s所指新結(jié)點(diǎn)插入到p所指結(jié)點(diǎn)之前，其語句應(yīng)該為▁▁▁▁▁。A、s->prev=p->prev;s->next=p;p->prev->next=s;p->prev=s;B、p->prev->next=s;p->prev=s;s->prev=p->prev;s->next=p;C、s->prev=p->prev;s->next=p;p->prev=s;p->prev->next=s;D、p->prev=s;p->prev->next=s;s->prev=p->prev;s->next=p;正確答案：B85.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址A、一定是不連續(xù)的B、部分地址必須是連續(xù)的C、必須是連續(xù)的D、連續(xù)或不連續(xù)都可以正確答案：D86.從棧頂指針為ST的鏈棧中刪除一個(gè)結(jié)點(diǎn)且用X保存被刪結(jié)點(diǎn)的值，則執(zhí)行：A、X=ST->data;B、ST=ST->next;X=ST->data;C、X=ST->data;ST=ST->next;D、X=ST;ST=ST->next;正確答案：C二、多選題（共3題，每題1分，共3分）1.非空線性表的結(jié)構(gòu)特征非空線性表具有哪些結(jié)構(gòu)特征？A、除終端結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)只有一個(gè)后繼結(jié)點(diǎn)B、可擁有多個(gè)的開始結(jié)點(diǎn)和多個(gè)終端結(jié)點(diǎn)C、除開始結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)只有一個(gè)前驅(qū)結(jié)點(diǎn)D、只有唯一的開始結(jié)點(diǎn)和唯一的終端結(jié)點(diǎn)正確答案：ACD2.下面結(jié)構(gòu)中適于表示稀疏有向圖的是（）。A、鄰接多重表B、鄰接表C、十字鏈表D、鄰接矩陣E、逆鄰接表正確答案：BCE3.關(guān)于二分查找算法二分查找算法能適用于▁▁▁▁▁。A、元素有序的順序表B、元素有序的鏈表C、元素?zé)o序的順序表D、元素?zé)o序的鏈表正確答案：A三、判斷題（共26題，每題1分，共26分）1.對(duì)一棵平衡二叉樹，所有非葉結(jié)點(diǎn)的平衡因子都是0，當(dāng)且僅當(dāng)該樹是完全二叉樹。A、正確B、錯(cuò)誤正確答案：B2.任何AVL樹的中序遍歷結(jié)果是有序的（從小到大）。A、正確B、錯(cuò)誤正確答案：A3.在散列表中，所謂同義詞就是具有相同散列地址的兩個(gè)元素。A、正確B、錯(cuò)誤正確答案：A4.若一個(gè)棧的輸入序列為{1,2,3,4,5}，則不可能得到{3,4,1,2,5}這樣的出棧序列。A、正確B、錯(cuò)誤正確答案：A