《數(shù)據(jù)結(jié)構(gòu)》-十套數(shù)據(jù)結(jié)構(gòu)試題及答案

數(shù)據(jù)結(jié)構(gòu)試卷（一）1數(shù)據(jù)結(jié)構(gòu)試卷（二）4數(shù)據(jù)結(jié)構(gòu)試卷（三）6數(shù)據(jù)結(jié)構(gòu)試卷（四）8數(shù)據(jù)結(jié)構(gòu)試卷（五）11數(shù)據(jù)結(jié)構(gòu)試卷（六）14數(shù)據(jù)結(jié)構(gòu)試卷（七）16數(shù)據(jù)結(jié)構(gòu)試卷（八）18數(shù)據(jù)結(jié)構(gòu)試卷（九）20數(shù)據(jù)結(jié)構(gòu)試卷（十）23數(shù)據(jù)結(jié)構(gòu)試卷（一）參考答案26數(shù)據(jù)結(jié)構(gòu)試卷（二）參考答案27數(shù)據(jù)結(jié)構(gòu)試卷（三）參考答案28數(shù)據(jù)結(jié)構(gòu)試卷（四）參考答案30數(shù)據(jù)結(jié)構(gòu)試卷（五）參考答案32數(shù)據(jù)結(jié)構(gòu)試卷（六）參考答案33數(shù)據(jù)結(jié)構(gòu)試卷（七）參考答案36數(shù)據(jù)結(jié)構(gòu)試卷（八）參考答案37數(shù)據(jù)結(jié)構(gòu)試卷（九）參考答案38數(shù)據(jù)結(jié)構(gòu)試卷（十）參考答案39數(shù)據(jù)結(jié)構(gòu)試卷（一）一、單選題（每題2分，共20分）1棧和隊(duì)列的共同特點(diǎn)是。A只允許在端點(diǎn)處插入和刪除元素B都是先進(jìn)后出C都是先進(jìn)先出D沒有共同點(diǎn)2用鏈接方式存儲的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)A僅修改頭指針B頭、尾指針都要修改C僅修改尾指針D頭、尾指針可能都要修改3以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)A隊(duì)列B棧C線性表D二叉樹4設(shè)有一個二維數(shù)組AMN，假設(shè)A00存放位置在64410，A22存放位置在67610，每個元素占一個空間，問A3310存放在什么位置腳注10表示用10進(jìn)制表示。A688B678C692D6965樹最適合用來表示。A有序數(shù)據(jù)元素B無序數(shù)據(jù)元素C元素之間具有分支層次關(guān)系的數(shù)據(jù)D元素之間無聯(lián)系的數(shù)據(jù)6二叉樹的第K層的結(jié)點(diǎn)數(shù)最多為A2K1B2K1C2K1D2K17若有18個元素的有序表存放在一維數(shù)組A19中，第一個元素放A1中，現(xiàn)進(jìn)行二分查找，則查找A3的比較序列的下標(biāo)依次為A1，2，3B9，5，2，3C9，5，3D9，4，2，38對N個記錄的文件進(jìn)行快速排序，所需要的輔助存儲空間大致為AO（1）BO（N）CO（1OG2N）DO（N2）9對于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲時(shí)，若選用H（K）K9作為散列函數(shù)，則散列地址為1的元素有（）個，A1B2C3D410設(shè)有6個結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有條邊才能確保是一個連通圖。A5B6C7D8二、填空題（每空1分，共26分）1通常從四個方面評價(jià)算法的質(zhì)量_、_、_和_。2一個算法的時(shí)間復(fù)雜度為N3N2LOG2N14N/N2，其數(shù)量級表示為_。3假定一棵樹的廣義表表示為A（C，D（E，F(xiàn)，G），H（I，J），則樹中所含的結(jié)點(diǎn)數(shù)為_個，樹的深度為_，樹的度為_。4后綴算式923102/的值為_。中綴算式（34X）2Y/3對應(yīng)的后綴算式為_。5若用鏈表存儲一棵二叉樹時(shí)，每個結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結(jié)構(gòu)中，N個結(jié)點(diǎn)的二叉樹共有_個指針域，其中有_個指針域是存放了地址，有_個指針是空指針。6對于一個具有N個頂點(diǎn)和E條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有_個和_個。7AOV網(wǎng)是一種_的圖。8在一個具有N個頂點(diǎn)的無向完全圖中，包含有_條邊，在一個具有N個頂點(diǎn)的有向完全圖中，包含有_條邊。9假定一個線性表為12,23,74,55,63,40，若按KEY4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個子表，則得到的四個子表分別為_、_、_和_。10向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點(diǎn)的分裂，則新樹比原樹的高度_。11在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為_，整個堆排序過程的時(shí)間復(fù)雜度為_。12在快速排序、堆排序、歸并排序中，_排序是穩(wěn)定的。三、計(jì)算題（每題6分，共24分）1在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A0NEXT，試寫出該線性表。A01234567DATA605078903440NEXT35720412請畫出下圖的鄰接矩陣和鄰接表。3已知一個圖的頂點(diǎn)集V和邊集E分別為V1,2,3,4,5,6,7E1,23,1,35,1,48,2,510,2,36,3,415,3,512,3,69,4,64,4,720,5,618,6,725用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。4畫出向小根堆中加入數(shù)據(jù)4,2,5,8,3時(shí)，每加入一個數(shù)據(jù)后堆的變化。四、閱讀算法（每題7分，共14分）1LINKLISTMYNOTELINKLISTL/L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針I(yè)FLABCBTRIGHTCOUTDATADATAITEMBSTDATA/查找成功RETURN_ELSEIFITEMDATARETURNFIND_,ITEMELSERETURNFIND_,ITEM/IF六、編寫算法（共8分）統(tǒng)計(jì)出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。INTCOUNTXLNODEHL,ELEMTYPEX數(shù)據(jù)結(jié)構(gòu)試卷（一）參考答案一、選擇題（每題2分，共20分）1A2D3D4C5C6D7D8C9D10A二、填空題（每空1分，共26分）1正確性易讀性強(qiáng)壯性高效率2ON39334134X2Y3/52NN1N16E2E7有向無回路8NN1/2NN19（12，40）（）（74）（23,55，63）10增加111OLOG2NONLOG2N12歸并三、計(jì)算題（每題6分，共24分）1線性表為（78，50，40，60，34，90）2鄰接矩陣010010鄰接表如圖11所示圖113用克魯斯卡爾算法得到的最小生成樹為1,23,4,64,1,35,1,48,2,510,4,7204見圖12圖12四、讀算法（每題7分，共14分）1（1）查詢鏈表的尾結(jié)點(diǎn)（2）將第一個結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)（3）返回的線性表為（A2,A3,AN,A1）2遞歸地后序遍歷鏈?zhǔn)酱鎯Φ亩鏄?。五、法填空（每?分，共8分）TRUEBSTLEFTBSTRIGHT六、編寫算法（8分）INTCOUNTXLNODEHL,ELEMTYPEXINTI0LNODEPHL/I為計(jì)數(shù)器WHILEPNULLIFPDATAXIPPNEXT/WHILE,出循環(huán)時(shí)I中的值即為X結(jié)點(diǎn)個數(shù)RETURNI/COUNTX4444422255522884352834數(shù)據(jù)結(jié)構(gòu)試卷（二）一、選擇題24分1下面關(guān)于線性表的敘述錯誤的是（）。A線性表采用順序存儲必須占用一片連續(xù)的存儲空間B線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間C線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實(shí)現(xiàn)D線性表采用順序存儲便于插入和刪除操作的實(shí)現(xiàn)2設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為M，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（）個空指針域。A2M1B2MC2M1D4M3設(shè)順序循環(huán)隊(duì)列Q0M1的頭指針和尾指針分別為F和R，頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個數(shù)為（）。ARFBFRCRFMMDFRMM4設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（）。ABADCBBCDACCDABDCBDA5設(shè)某完全無向圖中有N個頂點(diǎn)，則該完全無向圖中有（）條邊。ANN1/2BNN1CN2DN216設(shè)某棵二叉樹中有2000個結(jié)點(diǎn)，則該二叉樹的最小高度為（）。A9B10C11D127設(shè)某有向圖中有N個頂點(diǎn)，則該有向圖對應(yīng)的鄰接表中有（）個表頭結(jié)點(diǎn)。AN1BNCN1D2N18設(shè)一組初始記錄關(guān)鍵字序列5，2，6，3，8，以第一個記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（）。A2，3，5，8，6B3，2，5，8，6C3，2，5，6，8D2，3，6，5，8二、填空題24分1為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個問題是_和_。2下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)X進(jìn)棧，要求在下劃線處填上正確的語句。TYPEDEFSTRUCTINTS100INTTOPSQSTACKVOIDPUSHSQSTACKELSE_3中序遍歷二叉排序樹所得到的序列是_序列（填有序或無序）。4快速排序的最壞時(shí)間復(fù)雜度為_，平均時(shí)間復(fù)雜度為_。5設(shè)某棵二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為N1，則該二叉樹中度數(shù)為2的結(jié)點(diǎn)數(shù)為_；若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有_個空指針域。6設(shè)某無向圖中頂點(diǎn)數(shù)和邊數(shù)分別為N和E，所有頂點(diǎn)的度數(shù)之和為D，則E_。7設(shè)一組初始記錄關(guān)鍵字序列為55，63，44，38，75，80，31，56，則利用篩選法建立的初始堆為_。8已知一有向圖的鄰接表存儲結(jié)構(gòu)如下從頂點(diǎn)1出發(fā)，DFS遍歷的輸出序列是，BFS遍歷的輸出序列是三、應(yīng)用題36分1設(shè)一組初始記錄關(guān)鍵字序列為45，80，48，40，22，78，則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。2設(shè)指針變量P指向雙向鏈表中結(jié)點(diǎn)A，指針變量Q指向被插入結(jié)點(diǎn)B，要求給出在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列（設(shè)雙向鏈表中結(jié)點(diǎn)的兩個指針域分別為LLINK和RLINK）。3設(shè)一組有序的記錄關(guān)鍵字序列為13，18，24，35，47，50，62，83，90，查找方法用二分查找，要求計(jì)算出查找關(guān)鍵字62時(shí)的比較次數(shù)并計(jì)算出查找成功時(shí)的平均查找長度。4設(shè)一棵樹T中邊的集合為A，B，A，C，A，D，B，E，C，F(xiàn)，C，G，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。5設(shè)有無向圖G，要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。6設(shè)有一組初始記錄關(guān)鍵字為45，80，48，40，22，78，要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。四、算法設(shè)計(jì)題16分1設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，KN），要求設(shè)計(jì)一個算法能夠在ON的時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于KI，右半部分的每個關(guān)鍵字均大于等于KI。2設(shè)有兩個集合A和集合B，要求設(shè)計(jì)生成集合CAB的算法，其中集合A、B和C用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。數(shù)據(jù)結(jié)構(gòu)試卷（二）參考答案一、選擇題1D2B3C4A5A6C7B8C二、填空題1構(gòu)造一個好的HASH函數(shù)，確定解決沖突的方法2STACKTOP，STACKSSTACKTOPX3有序4ON2，ONLOG2N5N01，2N0N16D/2731，38，54，56，75，80，55，6381，3，4，5，2，1，3，2，4，5三、應(yīng)用題122，40，45，48，80，78，40，45，48，80，22，782QLLINKPQRLINKPRLINKPRLINKLLINKQPRLINKQ32,ASL91122344225/94樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)略，二叉樹略5E1，3，1，2，3，5，5，6，6，46略四、算法設(shè)計(jì)題1設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，KN），要求設(shè)計(jì)一個算法能夠在ON的時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于KI，右半部分的每個關(guān)鍵字均大于等于KI。VOIDQUICKPASSINTR,INTS,INTTINTIS,JT,XRSWHILEIXJJ1IFINEXTFORQHBQ0QQNEXTIFQDATAPDATABREAKIFQ0TLKLISTMALLOCSIZEOFLKLISTTDATAPDATATNEXTHCHCT數(shù)據(jù)結(jié)構(gòu)試卷（三）一、選擇題每題1分，共20分1設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為AD，R，D01，02，03，04，05，06，07，08，09，RR，R，則數(shù)據(jù)結(jié)構(gòu)A是（）。A線性結(jié)構(gòu)B樹型結(jié)構(gòu)C物理結(jié)構(gòu)D圖型結(jié)構(gòu)2下面程序的時(shí)間復(fù)雜為（）FOR（I1，S0；INEXT；PDATAQDATA；PNEXTQNEXT；FREEQ；BQPNEXT；QDATAPDATA；PNEXTQNEXT；FREEQ；CQPNEXT；PNEXTQNEXT；FREEQ；DQPNEXT；PDATAQDATA；FREEQ；4設(shè)有N個待排序的記錄關(guān)鍵字，則在堆排序中需要（）個輔助記錄單元。A1BNCNLOG2NDN25設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為20，15，14，18，21，36，40，10，則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為。A10，15，14，18，20，36，40，21B10，15，14，18，20，40，36，21C10，15，14，20，18，40，36，2LD15，10，14，18，20，36，40，216設(shè)二叉排序樹中有N個結(jié)點(diǎn)，則在二叉排序樹的平均平均查找長度為（）。AO1BOLOG2NCDON27設(shè)無向圖G中有N個頂點(diǎn)E條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個數(shù)分別為（）。AN，EBE，NC2N，EDN，2E8設(shè)某強(qiáng)連通圖中有N個頂點(diǎn)，則該強(qiáng)連通圖中至少有（）條邊。ANN1BN1CNDNN19設(shè)有5000個待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個記錄關(guān)鍵字，則用下列（）方法可以達(dá)到此目的。A快速排序B堆排序C歸并排序D插入排序10下列四種排序中（）的空間復(fù)雜度最大。A插入排序B冒泡排序C堆排序D歸并排序二、填空殖每空1分共20分1數(shù)據(jù)的物理結(jié)構(gòu)主要包括_和_兩種情況。2設(shè)一棵完全二叉樹中有500個結(jié)點(diǎn)，則該二叉樹的深度為_；若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有_個空指針域。3設(shè)輸入序列為1、2、3，則經(jīng)過棧的作用后可以得到_種不同的輸出序列。4設(shè)有向圖G用鄰接矩陣ANN作為存儲結(jié)構(gòu)，則該鄰接矩陣中第I行上所有元素之和等于頂點(diǎn)I的_，第I列上所有元素之和等于頂點(diǎn)I的_。5設(shè)哈夫曼樹中共有N個結(jié)點(diǎn)，則該哈夫曼樹中有_個度數(shù)為1的結(jié)點(diǎn)。6設(shè)有向圖G中有N個頂點(diǎn)E條有向邊，所有的頂點(diǎn)入度數(shù)之和為D，則E和D的關(guān)系為_。7_遍歷二叉排序樹中的結(jié)點(diǎn)可以得到一個遞增的關(guān)鍵字序列（填先序、中序或后序）。8設(shè)查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較_次就可以斷定數(shù)據(jù)元素X是否在查找表中。9不論是順序存儲結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧，其入棧和出棧操作的時(shí)間復(fù)雜度均為_。10設(shè)有N個結(jié)點(diǎn)的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第I個結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號為_，右孩子結(jié)點(diǎn)的編號為_。11設(shè)一組初始記錄關(guān)鍵字為72，73，71，23，94，16，5，則以記錄關(guān)鍵字72為基準(zhǔn)的一趟快速排序結(jié)果為_。12設(shè)有向圖G中有向邊的集合E，則該圖的一種拓?fù)湫蛄袨開。13下列算法實(shí)現(xiàn)在順序散列表中查找值為X的關(guān)鍵字，請?jiān)谙聞澗€處填上正確的語句。STRUCTRECORDINTKEYINTOTHERSINTHASHSQSEARCHSTRUCTRECORDHASHTABLE,INTKINTI,JJIKPWHILEHASHTABLEJKEYKIFIJRETURN1IF_RETURNJELSERETURN114下列算法實(shí)現(xiàn)在二叉排序樹上查找關(guān)鍵值K，請?jiān)谙聞澗€處填上正確的語句。TYPEDEFSTRUCTNODEINTKEYSTRUCTNODELCHILDSTRUCTNODERCHILDBITREEBITREEBSTSEARCHBITREET,INTKIFT0RETURN0ELSEWHILET0IFTKEYK_ELSEIFTKEYKTTLCHILDELSE_三、計(jì)算題每題10分，共30分1已知二叉樹的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCHKIJD，畫出此二叉樹，并畫出它的后序線索二叉樹。2已知待散列的線性表為（36，15，40，63，22），散列用的一維地址空間為06，假定選用的散列函數(shù)是H（K）KMOD7，若發(fā)生沖突采用線性探查法處理，試（1）計(jì)算出每一個元素的散列地址并在下圖中填寫出散列表0123456（2）求出在查找每一個元素概率相等情況下的平均查找長度。3已知序列（10，18，4，3，6，12，1，9，18，8）請用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果。四、算法設(shè)計(jì)題每題15分，共30分1設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。2設(shè)計(jì)一個求結(jié)點(diǎn)X在二叉樹中的雙親結(jié)點(diǎn)算法。數(shù)據(jù)結(jié)構(gòu)試卷（三）參考答案一、選擇題1B2B3A4A5A6B7D8C9B10D第3小題分析首先用指針變量Q指向結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B，然后將結(jié)點(diǎn)B的值復(fù)制到結(jié)點(diǎn)A中，最后刪除結(jié)點(diǎn)B。第9小題分析9快速排序、歸并排序和插入排序必須等到整個排序結(jié)束后才能夠求出最小的10個數(shù)，而堆排序只需要在初始堆的基礎(chǔ)上再進(jìn)行10次篩選即可，每次篩選的時(shí)間復(fù)雜度為OLOG2N。二、填空題1順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)29，501354出度，入度506ED7中序879O110I/2，2I1115，16，71，23，72，94，73121，4，3，213J1，HASHTABLEJKEYK14RETURNT，TTRCHILD第8小題分析二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進(jìn)行二分查找時(shí)的查找長度不超過二叉判定樹的高度1LOG2N。三、計(jì)算題1AEBFGCDHKJNUL2、H3636MOD71H2211MOD72沖突H1515MOD71沖突H22221MOD73H1511MOD72H4040MOD75H6363MOD70H2222MOD71沖突（1）01234566336152240（2）ASL653、8,9,4,3,6,1,10,12,18,181,6,4,3,8,9,10,12,18,181,3,4,6,8,9,10,12,18,181,3,4,6,8,9,10,12,18,181,3,4,6,8,9,10,12,18,18四、算法設(shè)計(jì)題1設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。TYPEDEFINTDATATYPETYPEDEFSTRUCTNODEDATATYPEDATASTRUCTNODENEXTLKLISTVOIDDELREDUNDANTLKLISTFORPHEADP0PPNEXTFORQPNEXT,SQQ0IFQDATAPDATASNEXTQNEXTFREEQQSNEXTELSESQ,QQNEXT2設(shè)計(jì)一個求結(jié)點(diǎn)X在二叉樹中的雙親結(jié)點(diǎn)算法。TYPEDEFSTRUCTNODEDATATYPEDATASTRUCTNODELCHILD,RCHILDBITREEBITREEQ20INTR0,F0,FLAG0VOIDPREORDERBITREEBT,CHARXIFBT0RETURNELSERR120QRBTPREORDERBTLCHILD,XPREORDERBTRCHILD,XVOIDPARENTBITREEBT,CHARXINTIPREORDERBT,XFORIF1ILCHILDDATAX|QIRCHILDDATABREAKIFFLAG0PRINTF“NOTFOUNDXN“ELSEIFIDATAELSEPRINTF“NOTPARENT“數(shù)據(jù)結(jié)構(gòu)試卷（四）一、選擇題每題1分共20分1設(shè)一維數(shù)組中有N個數(shù)組元素，則讀取第I個數(shù)組元素的平均時(shí)間復(fù)雜度為（）。AONBONLOG2NCO1DON22設(shè)一棵二叉樹的深度為K，則該二叉樹中最多有（）個結(jié)點(diǎn)。A2K1B2KC2K1D2K13設(shè)某無向圖中有N個頂點(diǎn)E條邊，則該無向圖中所有頂點(diǎn)的入度之和為（）。ANBEC2ND2E4在二叉排序樹中插入一個結(jié)點(diǎn)的時(shí)間復(fù)雜度為（）。AO1BONCOLOG2NDON25設(shè)某有向圖的鄰接表中有N個表頭結(jié)點(diǎn)和M個表結(jié)點(diǎn)，則該圖中有（）條有向邊。ANBN1CMDM16設(shè)一組初始記錄關(guān)鍵字序列為345，253，674，924，627，則用基數(shù)排序需要進(jìn)行（）趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。A3B4C5D87設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（）。A必須判別棧是否為滿B必須判別棧是否為空C判別棧元素的類型D對棧不作任何判別8下列四種排序中（）的空間復(fù)雜度最大。A快速排序B冒泡排序C希爾排序D堆9設(shè)某二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為NL，度數(shù)為2的結(jié)點(diǎn)數(shù)為N2，則下列等式成立的是（）。AN0N11BN0NLN2CN0N21DN02N1L10設(shè)有序順序表中有N個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過（）。ALOG2N1BLOG2N1CLOG2NDLOG2N1二、填空題每空1分共20分1設(shè)有N個無序的記錄關(guān)鍵字，則直接插入排序的時(shí)間復(fù)雜度為_，快速排序的平均時(shí)間復(fù)雜度為_。2設(shè)指針變量P指向雙向循環(huán)鏈表中的結(jié)點(diǎn)X，則刪除結(jié)點(diǎn)X需要執(zhí)行的語句序列為_（設(shè)結(jié)點(diǎn)中的兩個指針域分別為LLINK和RLINK）。3根據(jù)初始關(guān)鍵字序列19，22，01，38，10建立的二叉排序樹的高度為_。4深度為K的完全二叉樹中最少有_個結(jié)點(diǎn)。5設(shè)初始記錄關(guān)鍵字序列為K1，K2，KN，則用篩選法思想建堆必須從第_個元素開始進(jìn)行篩選。6設(shè)哈夫曼樹中共有99個結(jié)點(diǎn)，則該樹中有_個葉子結(jié)點(diǎn)；若采用二叉鏈表作為存儲結(jié)構(gòu)，則該樹中有_個空指針域。7設(shè)有一個順序循環(huán)隊(duì)列中有M個存儲單元，則該循環(huán)隊(duì)列中最多能夠存儲_個隊(duì)列元素；當(dāng)前實(shí)際存儲_個隊(duì)列元素（設(shè)頭指針F指向當(dāng)前隊(duì)頭元素的前一個位置，尾指針指向當(dāng)前隊(duì)尾元素的位置）。8設(shè)順序線性表中有N個數(shù)據(jù)元素，則第I個位置上插入一個數(shù)據(jù)元素需要移動表中_個數(shù)據(jù)元素；刪除第I個位置上的數(shù)據(jù)元素需要移動表中_個元素。9設(shè)一組初始記錄關(guān)鍵字序列為20，18，22，16，30，19，則以20為中軸的一趟快速排序結(jié)果為_。10設(shè)一組初始記錄關(guān)鍵字序列為20，18，22，16，30，19，則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為_。11設(shè)某無向圖G中有N個頂點(diǎn)，用鄰接矩陣A作為該圖的存儲結(jié)構(gòu)，則頂點(diǎn)I和頂點(diǎn)J互為鄰接點(diǎn)的條件是_。12設(shè)無向圖對應(yīng)的鄰接矩陣為A，則A中第I上非0元素的個數(shù)_第I列上非0元素的個數(shù)（填等于，大于或小于）。13設(shè)前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷該二叉樹的序列為_。14設(shè)散列函數(shù)HKKMODP，解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表HASHTALBE中查找關(guān)鍵字值等于K的結(jié)點(diǎn)，成功時(shí)返回指向關(guān)鍵字的指針，不成功時(shí)返回標(biāo)志0。TYPEDEFSTRUCTNODEINTKEYSTRUCTNODENEXTLKLISTVOIDCREATELKHASHLKLISTHASHTABLEINTI,KLKLISTSFORI0IKEYAIKAIPSNEXTHASHTABLEK_三、計(jì)算題每題10分，共30分1、畫出廣義表LS,E,A,B,C,D的頭尾鏈表存儲結(jié)構(gòu)。2、下圖所示的森林1求樹（A）的先根序列和后根序列；2求森林先序序列和中序序列；（3）將此森林轉(zhuǎn)換為相應(yīng)的二叉樹；ABCDEFGHIJKAB3、設(shè)散列表的地址范圍是09，散列函數(shù)為H（KEY）（KEY22）MOD9,并采用鏈表處理沖突，請畫出元素7、4、5、3、6、2、8、9依次插入散列表的存儲結(jié)構(gòu)。四、算法設(shè)計(jì)題每題10分，共30分1設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素大寫字母、數(shù)字和其它字符，要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個單鏈表的算法，使每個單鏈表只包含同類字符。2設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。3在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉排序樹。數(shù)據(jù)結(jié)構(gòu)試卷（五）一、選擇題20分1數(shù)據(jù)的最小單位是（）。A數(shù)據(jù)項(xiàng)B數(shù)據(jù)類型C數(shù)據(jù)元素D數(shù)據(jù)變量2設(shè)一組初始記錄關(guān)鍵字序列為50，40，95，20，15，70，60，45，則以增量D4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為（）。A40，50，20，95B15，40，60，20C15，20，40，45D45，40，15，203設(shè)一組初始記錄關(guān)鍵字序列為25，50，15，35，80，85，20，40，36，70，其中含有5個長度為2的有序子表，則用歸并排序的方法對該記錄關(guān)鍵字序列進(jìn)行一趟歸并后的結(jié)果為（）。A15，25，35，50，20，40，80，85，36，70B15，25，35，50，80，20，85，40，70，36C15，25，35，50，80，85，20，36，40，70D15，25，35，50，80，20，36，40，70，854函數(shù)SUBSTR“DATASTRUCTURE”，5，9的返回值為（）。A“STRUCTURE”B“DATA”C“ASTRUCTUR”D“DATASTRUCTURE”5設(shè)一個有序的單鏈表中有N個結(jié)點(diǎn)，現(xiàn)要求插入一個新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時(shí)間復(fù)雜度為（）。AOLOG2NBO1CON2DON6設(shè)一棵M叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為NL，度數(shù)為M的結(jié)點(diǎn)數(shù)為NM，則N0（）。ANLN2NMBLN22N33N4M1NMCN22N33N4M1NMD2NL3N2M1NM7設(shè)有序表中有1000個元素，則用二分查找查找元素X最多需要比較（）次。A25B10C7D18設(shè)連通圖G中的邊集EA，B，A，E，A，C，B，E，E，D，D，F(xiàn)，F(xiàn)，C，則從頂點(diǎn)A出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為（）。AABEDFCBACFEBDCAEBDFCDAEDFCB9設(shè)輸入序列是1、2、3、N，經(jīng)過棧的作用后輸出序列的第一個元素是N，則輸出序列中第I個輸出元素是（）。ANIBN1ICN1ID不能確定10設(shè)一組初始記錄關(guān)鍵字序列為45，80，55，40，42，85，則以第一個記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是（）。A40，42，45，55，80，83B42，40，45，80，85，88C42，40，45，55，80，85D42，40，45，85，55，80二、填空題共20分1設(shè)有一個順序共享?xiàng)0N1，其中第一個棧項(xiàng)指針TOP1的初值為1，第二個棧頂指針TOP2的初值為N，則判斷共享?xiàng)M的條件是_。2在圖的鄰接表中用順序存儲結(jié)構(gòu)存儲表頭結(jié)點(diǎn)的優(yōu)點(diǎn)是_。3設(shè)有一個N階的下三角矩陣A，如果按照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽蔷€上元素）存放在NN1個連續(xù)的存儲單元中，則AIJ與A00之間有_個數(shù)據(jù)元素。4棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱為_表；隊(duì)列的插入和刪除運(yùn)算分別在隊(duì)列的兩端進(jìn)行，先進(jìn)隊(duì)列的元素必定先出隊(duì)列，所以又把隊(duì)列稱為_表。5設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF，則該二叉樹的前序遍歷序列為_，中序遍歷序列為_，后序遍歷序列為_。6設(shè)一棵完全二叉樹有128個結(jié)點(diǎn)，則該完全二叉樹的深度為_，有_個葉子結(jié)點(diǎn)。7設(shè)有向圖G的存儲結(jié)構(gòu)用鄰接矩陣A來表示，則A中第I行中所有非零元素個數(shù)之和等于頂點(diǎn)I的_，第I列中所有非零元素個數(shù)之和等于頂點(diǎn)I的_。8設(shè)一組初始記錄關(guān)鍵字序列K1，K2，KN是堆，則對I1，2，N/2而言滿足的條件為_。9下面程序段的功能是實(shí)現(xiàn)冒泡排序算法，請?jiān)谙聞澗€處填上正確的語句。VOIDBUBBLEINTRNFORI1IRJ1TEMPRJ1_RJTEMPEXCHANGE1IFEXCHANGE0RETURN；10下面程序段的功能是實(shí)現(xiàn)二分查找算法，請?jiān)谙聞澗€處填上正確的語句。STRUCTRECORDINTKEYINTOTHERSINTBISEARCHSTRUCTRECORDR,INTKINTLOW0,MID,HIGHN1WHILELOWNEXT0CHEADNEXTHEADDHEAD04時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為ONLOG2N的是（）。A堆排序B冒泡排序C希爾排序D快速排序5設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（）。A空或只有一個結(jié)點(diǎn)B高度等于其結(jié)點(diǎn)數(shù)C任一結(jié)點(diǎn)無左孩子D任一結(jié)點(diǎn)無右孩子6一趟排序結(jié)束后不一定能夠選出一個元素放在其最終位置上的是（）。A堆排序B冒泡排序C快速排序D希爾排序7設(shè)某棵三叉樹中有40個結(jié)點(diǎn)，則該三叉樹的最小高度為（）。A3B4C5D68順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間復(fù)雜度為（）。AONBON2CON1/2DO1OG2N9二路歸并排序的時(shí)間復(fù)雜度為（）。AONBON2CONLOG2NDO1OG2N10深度為K的完全二叉樹中最少有（）個結(jié)點(diǎn)。A2K11B2K1C2K11D2K111設(shè)指針變量FRONT表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量REAR表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量S指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X，則入隊(duì)列的操作序列為（）。AFRONTNEXTS；FRONTS；BSNEXTREAR；REARS；CREARNEXTS；REARS；DSNEXTFRONT；FRONTS；12設(shè)某無向圖中有N個頂點(diǎn)E條邊，則建立該圖鄰接表的時(shí)間復(fù)雜度為（）。AONEBON2CONEDON313設(shè)某哈夫曼樹中有199個結(jié)點(diǎn)，則該哈夫曼樹中有（）個葉子結(jié)點(diǎn)。A99B100C101D10214設(shè)二叉排序樹上有N個結(jié)點(diǎn)，則在二叉排序樹上查找結(jié)點(diǎn)的平均時(shí)間復(fù)雜度為（）。AONBON2CONLOG2NDO1OG2N15設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點(diǎn)I的入度為（）。A第I行非0元素的個數(shù)之和B第I列非0元素的個數(shù)之和C第I行0元素的個數(shù)之和D第I列0元素的個數(shù)之和二、判斷題20分1調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點(diǎn)。（）2分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。（）3冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（）4滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（）5設(shè)一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（）6層次遍歷初始堆可以得到一個有序的序列。（）7設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT，則二叉樹BT中一定沒有右子樹。（）8線性表的順序存儲結(jié)構(gòu)比鏈?zhǔn)酱鎯Y(jié)構(gòu)更好。（）9中序遍歷二叉排序樹可以得到一個有序的序列。（）10快速排序是排序算法中平均性能最好的一種排序。（）三、填空題30分1FORI1，T1，S0；I，則給出該圖的一種拓?fù)渑判蛐蛄衉。4設(shè)無向圖G中有N個頂點(diǎn)，則該無向圖中每個頂點(diǎn)的度數(shù)最多是_。5設(shè)二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為50，度數(shù)為1的結(jié)點(diǎn)數(shù)為30，則該二叉樹中總共有_個結(jié)點(diǎn)數(shù)。6設(shè)F和R分別表示順序循環(huán)隊(duì)列的頭指針和尾指針，則判斷該循環(huán)隊(duì)列為空的條件為_。7設(shè)二叉樹中結(jié)點(diǎn)的兩個指針域分別為LCHILD和RCHILD，則判斷指針變量P所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是_。8簡單選擇排序和直接插入排序算法的平均時(shí)間復(fù)雜度為_。9快速排序算法的空間復(fù)雜度平均情況下為_，最壞的情況下為_。10散列表中解決沖突的兩種方法是_和_。四、算法設(shè)計(jì)題20分設(shè)計(jì)在順序有序表中實(shí)現(xiàn)二分查找的算法。設(shè)計(jì)判斷二叉樹是否為二叉排序樹的算法。在鏈?zhǔn)酱鎯Y(jié)構(gòu)上設(shè)計(jì)直接插入排序算法數(shù)據(jù)結(jié)構(gòu)試卷（七）一、選擇題30分1設(shè)某無向圖有N個頂點(diǎn)，則該無向圖的鄰接表中有（）個表頭結(jié)點(diǎn)。A2NBNCN/2DNN12設(shè)無向圖G中有N個頂點(diǎn)，則該無向圖的最小生成樹上有（）條邊。ANBN1C2ND2N13設(shè)一組初始記錄關(guān)鍵字序列為60，80，55，40，42，85，則以第一個關(guān)鍵字45為基準(zhǔn)而得到的一趟快速排序結(jié)果是（）。A40，42，60，55，80，85B42，45，55，60，85，80C42，40，55，60，80，85D42，40，60，85，55，804（）二叉排序樹可以得到一個從小到大的有序序列。A先序遍歷B中序遍歷C后序遍歷D層次遍歷5設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進(jìn)行順序編號，則編號為I結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號為（）。A2I1B2ICI/2D2I16程序段SI0；DOII1；SSI；WHILEINEXT0CHEADNEXTHEADDHEAD08設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點(diǎn)最多有（）。A20B256C512D10249設(shè)一組初始記錄關(guān)鍵字序列為13，18，24，35，47，50，62，83，90，115，134,則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個數(shù)為（）。A1B2C3D410設(shè)指針變量TOP指向當(dāng)前鏈?zhǔn)綏５臈ｍ敚瑒t刪除棧頂元素的操作序列為（）。ATOPTOP1BTOPTOP1CTOPNEXTTOPDTOPTOPNEXT二、判斷題20分1不論是入隊(duì)列操作還是入棧操作，在順序存儲結(jié)構(gòu)上都需要考慮“溢出”情況。（）2當(dāng)向二叉排序樹中插入一個結(jié)點(diǎn)，則該結(jié)點(diǎn)一定成為葉子結(jié)點(diǎn)。（）3設(shè)某堆中有N個結(jié)點(diǎn)，則在該堆中插入一個新結(jié)點(diǎn)的時(shí)間復(fù)雜度為OLOG2N。（）4完全二叉樹中的葉子結(jié)點(diǎn)只可能在最后兩層中出現(xiàn)。（）5哈夫曼樹中沒有度數(shù)為1的結(jié)點(diǎn)。（）6對連通圖進(jìn)行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點(diǎn)。（）7先序遍歷一棵二叉排序樹得到的結(jié)點(diǎn)序列不一定是有序的序列。（）8由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。（）9線性表中的所有元素都有一個前驅(qū)元素和后繼元素。（）10帶權(quán)無向圖的最小生成樹是唯一的。（）三、填空題30分1設(shè)指針變量P指向雙向鏈表中的結(jié)點(diǎn)A，指針變量S指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為_P；SRIGHTPRIGHT；_S；PRIGHTLEFTS；（設(shè)結(jié)點(diǎn)中的兩個指針域分別為LEFT和RIGHT）。2設(shè)完全有向圖中有N個頂點(diǎn)，則該完全有向圖中共有_條有向條；設(shè)完全無向圖中有N個頂點(diǎn)，則該完全無向圖中共有_條無向邊。3設(shè)關(guān)鍵字序列為KL，K2，KN，則用篩選法建初始堆必須從第_個元素開始進(jìn)行篩選。4解決散列表沖突的兩種方法是_和_。5設(shè)一棵三叉樹中有50個度數(shù)為0的結(jié)點(diǎn)，21個度數(shù)為2的結(jié)點(diǎn)，則該二叉樹中度數(shù)為3的結(jié)點(diǎn)數(shù)有_個。6高度為H的完全二叉樹中最少有_個結(jié)點(diǎn)，最多有_個結(jié)點(diǎn)。7設(shè)有一組初始關(guān)鍵字序列為24，35，12，27，18，26，則第3趟直接插入排序結(jié)束后的結(jié)果的是_。8設(shè)有一組初始關(guān)鍵字序列為24，35，12，27，18，26，則第3趟簡單選擇排序結(jié)束后的結(jié)果的是_。9設(shè)一棵二叉樹的前序序列為ABC，則有_種不同的二叉樹可以得到這種序列。10下面程序段的功能是實(shí)現(xiàn)一趟快速排序，請?jiān)谙聞澗€處填上正確的語句。STRUCTRECORDINTKEYDATATYPEOTHERSVOIDQUICKPASSSTRUCTRECORDR,INTS,INTT,INTSTRUCTRECORDXRSISWHILEIXKEYJJ1IFIDATAKTLCHILDTRCHILD0ELSEIFTDATAKBSTINSERTTLCHILD,KELSE_3設(shè)指針變量P指向單鏈表中結(jié)點(diǎn)A，指針變量S指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X需要執(zhí)行的語句序列SNEXTPNEXT_。4設(shè)指針變量HEAD指向雙向鏈表中的頭結(jié)點(diǎn)，指針變量P指向雙向鏈表中的第一個結(jié)點(diǎn)，則指針變量P和指針變量HEAD之間的關(guān)系是P_和HEAD_（設(shè)結(jié)點(diǎn)中的兩個指針域分別為LLINK和RLINK）。5設(shè)某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為_。6完全二叉樹中第5層上最少有_個結(jié)點(diǎn)，最多有_個結(jié)點(diǎn)。7設(shè)有向圖中不存在有向邊，則其對應(yīng)的鄰接矩陣A中的數(shù)組元素AIJ的值等于_。8設(shè)一組初始記錄關(guān)鍵字序列為49，38，65，97，76，13，27，50，則第4趟直接選擇排序結(jié)束后的結(jié)果為_。9設(shè)連通圖G中有N個頂點(diǎn)E條邊，則對應(yīng)的最小生成樹上有_條邊。10設(shè)有一組初始記錄關(guān)鍵字序列為50，16，23，68，94，70，73，則將它們調(diào)整成初始堆只需把16與_相互交換即可。四、算法設(shè)計(jì)題20分1設(shè)計(jì)一個在鏈?zhǔn)酱鎯Y(jié)構(gòu)上統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)個數(shù)的算法。2設(shè)計(jì)一個算法將無向圖的鄰接矩陣轉(zhuǎn)為對應(yīng)鄰接表的算法。數(shù)據(jù)結(jié)構(gòu)試卷（九）一、選擇題30分1下列程序段的時(shí)間復(fù)雜度為（）。FORI0；IRIGHTS；SLEFTP；PRIGHTLEFTS；SRIGHTPRIGHT；BSLEFTP；SRIGHTPRIGHT；PRIGHTS；PRIGHTLEFTS；CPRIGHTS；PRIGHTLEFTS；SLEFTP；SRIGHTPRIGHT；DSLEFTP；SRIGHTPRIGHT；PRIGHTLEFTS；PRIGHTS；6下列各種排序算法中平均時(shí)間復(fù)雜度為ON2是（）。A快速排序B堆排序C歸并排序D冒泡排序7設(shè)輸入序列1、2、3、N經(jīng)過棧作用后，輸出序列中的第一個元素是N，則輸出序列中的第I個輸出元素是（）。ANIBN1ICNLID不能確定8設(shè)散列表中有M個存儲單元，散列函數(shù)HKEYKEYP，則P最好選擇（）。A小于等于M的最大奇數(shù)B小于等于M的最大素?cái)?shù)C小于等于M的最大偶數(shù)D小于等于M的最大合數(shù)9設(shè)在一棵度數(shù)為3的樹中，度數(shù)為3的結(jié)點(diǎn)數(shù)有2個，度數(shù)為2的結(jié)點(diǎn)數(shù)有1個，度數(shù)為1的結(jié)點(diǎn)數(shù)有2個，那么度數(shù)為0的結(jié)點(diǎn)數(shù)有（）個。A4B5C6D710設(shè)完全無向圖中有N個頂點(diǎn)，則該完全無向圖中有（）條邊。ANN1/2BNN1CNN1/2DN1/211設(shè)順序表的長度為N，則順序查找的平均比較次數(shù)為（）。ANBN/2CN1/2DN1/212設(shè)有序表中的元素為13，18，24，35，47，50，62，則在其中利用二分法查找值為24的元素需要經(jīng)過（）次比較。A1B2C3D413設(shè)順序線性表的長度為30，分成5塊，每塊6個元素，如果采用分塊查找，則其平均查找長度為（）。A6B11C5D6514設(shè)有向無環(huán)圖G中的有向邊集合E，則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖牵ǎ?。A1，2，3，4B2，3，4，1C1，4，2，3D1，2，4，315設(shè)有一組初始記錄關(guān)鍵字序列為34，76，45，18，26，54，92，則由這組記錄關(guān)鍵字生成的二叉排序樹的深度為（）。A4B5C6D7二、填空題30分1設(shè)指針P指向單鏈表中結(jié)點(diǎn)A，指針S指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的前面插入結(jié)點(diǎn)X時(shí)的操作序列為1SNEXT_；2PNEXTS；3TPDATA；4PDATA_；5SDATAT；2設(shè)某棵完全二叉樹中有100個結(jié)點(diǎn)，則該二叉樹中有_個葉子結(jié)點(diǎn)。3設(shè)某順序循環(huán)隊(duì)列中有M個元素，且規(guī)定隊(duì)頭指針F指向隊(duì)頭元素的前一個位置，隊(duì)尾指針R指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中最多存儲_隊(duì)列元素。4對一組初始關(guān)鍵字序列（40，50，95，20，15，70，60，45，10）進(jìn)行冒泡排序，則第一趟需要進(jìn)行相鄰記錄的比較的次數(shù)為_，在整個排序過程中最多需要進(jìn)行_趟排序才可以完成。5在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮應(yīng)最好選擇_排序，如果從節(jié)省存儲空間的角度來考慮則最好選擇_排序。6設(shè)一組初始記錄關(guān)鍵字序列為20，12，42，31，18，14，28，則根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹的平均查找長度是_。7設(shè)一棵二叉樹的中序遍歷序列為BDCA，后序遍歷序列為DBAC，則這棵二叉樹的前序序列為_。8設(shè)用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為7、19、2、6、32、3、21、10，根據(jù)這些頻率作為權(quán)值構(gòu)造哈夫曼樹，則這棵哈夫曼樹的高度為_。9設(shè)一組記錄關(guān)鍵字序列為80，70，33，65，24，56，48，則用篩選法建成的初始堆為_。10設(shè)無向圖G（如右圖所示），則其最小生成樹上所有邊的權(quán)值之和為_