數(shù)據(jù)結(jié)構(gòu)試卷（一）一、單選題（每題2分，共20分）1棧和隊列的共同特點是A。A只允許在端點處插入和刪除元素B都是先進后出C都是先進先出D沒有共同點2用鏈接方式存儲的隊列，在進行插入運算時DA僅修改頭指針B頭、尾指針都要修改C僅修改尾指針D頭、尾指針可能都要修改3以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)DA隊列B棧C線性表D二叉樹4設(shè)有一個二維數(shù)組AMN，假設(shè)A00存放位置在64410，A22存放位置在67610，每個元素占一個空間，問A3310存放在什么位置腳注10表示用10進制表示。CA688B678C692D6965樹最適合用來表示C。A有序數(shù)據(jù)元素B無序數(shù)據(jù)元素C元素之間具有分支層次關(guān)系的數(shù)據(jù)D元素之間無聯(lián)系的數(shù)據(jù)6二叉樹的第K層的結(jié)點數(shù)最多為DA2K1B2K1C2K1D2K17若有18個元素的有序表存放在一維數(shù)組A19中，第一個元素放A1中，現(xiàn)進行二分查找，則查找A3的比較序列的下標依次為DA1，2，3B9，5，2，3C9，5，3D9，4，2，38對N個記錄的文件進行快速排序，所需要的輔助存儲空間大致為CAO（1）BO（N）CO（1OG2N）DO（N2）9對于線性表（7，34，55，25，64，46，20，10）進行散列存儲時，若選用H（K）K9作為散列函數(shù)，則散列地址為1的元素有（D）個，A1B2C3D410設(shè)有6個結(jié)點的無向圖，該圖至少應有A條邊才能確保是一個連通圖。A5B6C7D8二、填空題（每空1分，共26分）1通常從四個方面評價算法的質(zhì)量_、_、_和_。2一個算法的時間復雜度為N3N2LOG2N14N/N2，其數(shù)量級表示為_ON_。3假定一棵樹的廣義表表示為A（C，D（E，F(xiàn)，G），H（I，J），則樹中所含的結(jié)點數(shù)為_9_個，樹的深度為_3_，樹的度為_3_。4后綴算式923102/的值為_9（23）10/21_。中綴算式（34X）2Y/3對應的后綴算式為_。5若用鏈表存儲一棵二叉樹時，每個結(jié)點除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結(jié)構(gòu)中，N個結(jié)點的二叉樹共有_2N_個指針域，其中有_N1_個指針域是存放了地址，有_N1_個指針是空指針。6對于一個具有N個頂點和E條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結(jié)點分別有_E_個和_2E_個。7AOV網(wǎng)是一種_有向無回路_的圖。8在一個具有N個頂點的無向完全圖中，包含有_1/2NN1_條邊，在一個具有N個頂點的有向完全圖中，包含有_NN1_條邊。1假定一個線性表為12,23,74,55,63,40，若按KEY4條件進行劃分，使得同一余數(shù)的元素成為一個子表，則得到的四個子表分別為_（12，40）（）（74）（23,55，63）9_、_、_和_。10向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點的分裂，則新樹比原樹的高度_。11在堆排序的過程中，對任一分支結(jié)點進行篩運算的時間復雜度為_OLOGN_，整個堆排序過程的時間復雜度為_ONLOGN_。12在快速排序、堆排序、歸并排序中，_歸并_排序是穩(wěn)定的。三、計算題（每題6分，共24分）1在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A0NEXT，試寫出該線性表。A01234567DATA605078903440NEXT35720412請畫出下圖的鄰接矩陣和鄰接表。3已知一個圖的頂點集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ù)據(jù)后堆的變化。四、閱讀算法（每題7分，共14分）1LINKLISTMYNOTELINKLISTL/L是不帶頭結(jié)點的單鏈表的頭指針I(yè)FLABCBTRIGHTCOUTDATADATAITEMBSTDATA/查找成功RETURN_TURE_ELSEIFITEMDATARETURNFIND_BSTLCHILD_,ITEMELSERETURNFIND_BSTRCHILD_,ITEM/IF六、編寫算法（共8分）統(tǒng)計出單鏈表HL中結(jié)點的值等于給定值X的結(jié)點數(shù)。INTCOUNTXLNODEHL,ELEMTYPEX數(shù)據(jù)結(jié)構(gòu)試卷（二）一、選擇題24分1下面關(guān)于線性表的敘述錯誤的是（D）。A線性表采用順序存儲必須占用一片連續(xù)的存儲空間B線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間C線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)D線性表采用順序存儲便于插入和刪除操作的實現(xiàn)2設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為M，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（B）個空指針域。A2M1B2MC2M1D4M3設(shè)順序循環(huán)隊列Q0M1的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當前位置，則該循環(huán)隊列中的元素個數(shù)為（C）。ARFBFRCRFMMDFRMM4設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（）。ABADCBBCDACCDABDCBDA5設(shè)某完全無向圖中有N個頂點，則該完全無向圖中有（A）條邊。ANN1/2BNN1CN2DN216設(shè)某棵二叉樹中有2000個結(jié)點，則該二叉樹的最小高度為（C）。A9B10C11D127設(shè)某有向圖中有N個頂點，則該有向圖對應的鄰接表中有（B）個表頭結(jié)點。AN1BNCN1D2N18設(shè)一組初始記錄關(guān)鍵字序列5，2，6，3，8，以第一個記錄關(guān)鍵字5為基準進行一趟快速排序的結(jié)果為（C）。A2，3，5，8，6B3，2，5，8，6C3，2，5，6，8D2，3，6，5，8二、填空題24分1為了能有效地應用HASH查找技術(shù)，必須解決的兩個問題是_和_。2下面程序段的功能實現(xiàn)數(shù)據(jù)X進棧，要求在下劃線處填上正確的語句。TYPEDEFSTRUCTINTS100INTTOPSQSTACKVOIDPUSHSQSTACK1ELSE_STACKTOPSTACKSSTACKTOPX3中序遍歷二叉排序樹所得到的序列是_序列（填有序或無序）。4快速排序的最壞時間復雜度為_，平均時間復雜度為_。5設(shè)某棵二叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為N1，則該二叉樹中度數(shù)為2的結(jié)點數(shù)為_；若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有_個空指針域。6設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為N和E，所有頂點的度數(shù)之和為D，則E_。7設(shè)一組初始記錄關(guān)鍵字序列為55，63，44，38，75，80，31，56，則利用篩選法建立的初始堆為_。8已知一有向圖的鄰接表存儲結(jié)構(gòu)如下從頂點1出發(fā)，DFS遍歷的輸出序列是21，3，4，5，2，1，3，2，4，5，BFS遍歷的輸出序列是三、應用題36分1設(shè)一組初始記錄關(guān)鍵字序列為45，80，48，40，22，78，則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。2設(shè)指針變量P指向雙向鏈表中結(jié)點A，指針變量Q指向被插入結(jié)點B，要求給出在結(jié)點A的后面插入結(jié)點B的操作序列（設(shè)雙向鏈表中結(jié)點的兩個指針域分別為LLINK和RLINK）。3設(shè)一組有序的記錄關(guān)鍵字序列為13，18，24，35，47，50，62，83，90，查找方法用二分查找，要求計算出查找關(guān)鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長度。4設(shè)一棵樹T中邊的集合為A，B，A，C，A，D，B，E，C，F(xiàn)，C，G，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應的二叉樹。5設(shè)有無向圖G，要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。6設(shè)有一組初始記錄關(guān)鍵字為45，80，48，40，22，78，要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。四、算法設(shè)計題16分1設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，KN），要求設(shè)計一個算法能夠在ON的時間復雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于KI，右半部分的每個關(guān)鍵字均大于等于KI。2設(shè)有兩個集合A和集合B，要求設(shè)計生成集合CAB的算法，其中集合A、B和C用鏈式存儲結(jié)構(gòu)表示。數(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下面程序的時間復雜為（B）FOR（I1，S0；INEXT；PDATAQDATA；PNEXTQNEXT；FREEQ；BQPNEXT；QDATAPDATA；PNEXTQNEXT；FREEQ；CQPNEXT；PNEXTQNEXT；FREEQ；DQPNEXT；PDATAQDATA；FREEQ；4設(shè)有N個待排序的記錄關(guān)鍵字，則在堆排序中需要（A）個輔助記錄單元。A1BNCNLOG2NDN25設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為20，15，14，18，21，36，40，10，則以20為基準記錄的一趟快速排序結(jié)束后的結(jié)果為A。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é)點，則在二叉排序樹的平均平均查找長度為（B）。AO1BOLOG2NCDON27設(shè)無向圖G中有N個頂點E條邊，則其對應的鄰接表中的表頭結(jié)點和表結(jié)點的個數(shù)分別為（D）。AN，EBE，NC2N，EDN，2E8設(shè)某強連通圖中有N個頂點，則該強連通圖中至少有（）條邊。ANN1BN1CNDNN19設(shè)有5000個待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個記錄關(guān)鍵字，則用下列（）方法可以達到此目的。A快速排序B堆排序C歸并排序D插入排序10下列四種排序中（）的空間復雜度最大。A插入排序B冒泡排序C堆排序D歸并排序二、填空殖每空1分共20分1數(shù)據(jù)的物理結(jié)構(gòu)主要包括_和_兩種情況。2設(shè)一棵完全二叉樹中有500個結(jié)點，則該二叉樹的深度為_；若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有_個空指針域。3設(shè)輸入序列為1、2、3，則經(jīng)過棧的作用后可以得到_種不同的輸出序列。4設(shè)有向圖G用鄰接矩陣ANN作為存儲結(jié)構(gòu)，則該鄰接矩陣中第I行上所有元素之和等于頂點I的_，第I列上所有元素之和等于頂點I的_。5設(shè)哈夫曼樹中共有N個結(jié)點，則該哈夫曼樹中有_個度數(shù)為1的結(jié)點。6設(shè)有向圖G中有N個頂點E條有向邊，所有的頂點入度數(shù)之和為D，則E和D的關(guān)系為_。7_遍歷二叉排序樹中的結(jié)點可以得到一個遞增的關(guān)鍵字序列（填先序、中序或后序）。8設(shè)查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較_次就可以斷定數(shù)據(jù)元素X是否在查找表中。9不論是順序存儲結(jié)構(gòu)的棧還是鏈式存儲結(jié)構(gòu)的棧，其入棧和出棧操作的時間復雜度均為_。10設(shè)有N個結(jié)點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第I個結(jié)點的雙親結(jié)點編號為_，右孩子結(jié)點的編號為_。11設(shè)一組初始記錄關(guān)鍵字為72，73，71，23，94，16，5，則以記錄關(guān)鍵字72為基準的一趟快速排序結(jié)果為_。12設(shè)有向圖G中有向邊的集合E，則該圖的一種拓撲序列為_。13下列算法實現(xiàn)在順序散列表中查找值為X的關(guān)鍵字，請在下劃線處填上正確的語句。STRUCTRECORDINTKEYINTOTHERSINTHASHSQSEARCHSTRUCTRECORDHASHTABLE,INTKINTI,JJIKPWHILEHASHTABLEJKEYKIFIJRETURN1IF_RETURNJELSERETURN114下列算法實現(xiàn)在二叉排序樹上查找關(guān)鍵值K，請在下劃線處填上正確的語句。TYPEDEFSTRUCTNODEINTKEYSTRUCTNODELCHILDSTRUCTNODERCHILDBITREEBITREEBSTSEARCHBITREET,INTKIFT0RETURN0ELSEWHILET0IFTKEYK_ELSEIFTKEYKTTLCHILDELSE_三、計算題每題10分，共30分1已知二叉樹的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCHKIJD，畫出此二叉樹，并畫出它的后序線索二叉樹。2已知待散列的線性表為（36，15，40，63，22），散列用的一維地址空間為06，假定選用的散列函數(shù)是H（K）KMOD7，若發(fā)生沖突采用線性探查法處理，試（1）計算出每一個元素的散列地址并在下圖中填寫出散列表0123456（2）求出在查找每一個元素概率相等情況下的平均查找長度。3已知序列（10，18，4，3，6，12，1，9，18，8）請用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果。四、算法設(shè)計題每題15分，共30分1設(shè)計在單鏈表中刪除值相同的多余結(jié)點的算法。2設(shè)計一個求結(jié)點X在二叉樹中的雙親結(jié)點算法。數(shù)據(jù)結(jié)構(gòu)試卷（四）一、選擇題每題1分共20分1設(shè)一維數(shù)組中有N個數(shù)組元素，則讀取第I個數(shù)組元素的平均時間復雜度為（）。AONBONLOG2NCO1DON22設(shè)一棵二叉樹的深度為K，則該二叉樹中最多有（）個結(jié)點。A2K1B2KC2K1D2K13設(shè)某無向圖中有N個頂點E條邊，則該無向圖中所有頂點的入度之和為（）。ANBEC2ND2E4在二叉排序樹中插入一個結(jié)點的時間復雜度為（）。AO1BONCOLOG2NDON25設(shè)某有向圖的鄰接表中有N個表頭結(jié)點和M個表結(jié)點，則該圖中有（）條有向邊。ANBN1CMDM16設(shè)一組初始記錄關(guān)鍵字序列為345，253，674，924，627，則用基數(shù)排序需要進行（）趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。A3B4C5D87設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（）。A必須判別棧是否為滿B必須判別棧是否為空C判別棧元素的類型D對棧不作任何判別8下列四種排序中（）的空間復雜度最大。A快速排序B冒泡排序C希爾排序D堆9設(shè)某二叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為NL，度數(shù)為2的結(jié)點數(shù)為N2，則下列等式成立的是（）。AN0N11BN0NLN2CN0N21DN02N1L10設(shè)有序順序表中有N個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過（）。ALOG2N1BLOG2N1CLOG2NDLOG2N1二、填空題每空1分共20分1設(shè)有N個無序的記錄關(guān)鍵字，則直接插入排序的時間復雜度為_，快速排序的平均時間復雜度為_。2設(shè)指針變量P指向雙向循環(huán)鏈表中的結(jié)點X，則刪除結(jié)點X需要執(zhí)行的語句序列為_（設(shè)結(jié)點中的兩個指針域分別為LLINK和RLINK）。3根據(jù)初始關(guān)鍵字序列19，22，01，38，10建立的二叉排序樹的高度為_。4深度為K的完全二叉樹中最少有_個結(jié)點。5設(shè)初始記錄關(guān)鍵字序列為K1，K2，KN，則用篩選法思想建堆必須從第_個元素開始進行篩選。6設(shè)哈夫曼樹中共有99個結(jié)點，則該樹中有_個葉子結(jié)點；若采用二叉鏈表作為存儲結(jié)構(gòu)，則該樹中有_個空指針域。7設(shè)有一個順序循環(huán)隊列中有M個存儲單元，則該循環(huán)隊列中最多能夠存儲_個隊列元素；當前實際存儲_個隊列元素（設(shè)頭指針F指向當前隊頭元素的前一個位置，尾指針指向當前隊尾元素的位置）。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個頂點，用鄰接矩陣A作為該圖的存儲結(jié)構(gòu)，則頂點I和頂點J互為鄰接點的條件是_。12設(shè)無向圖對應的鄰接矩陣為A，則A中第I上非0元素的個數(shù)_第I列上非0元素的個數(shù)（填等于，大于或小于）。13設(shè)前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷該二叉樹的序列為_。14設(shè)散列函數(shù)HKKMODP，解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表HASHTALBE中查找關(guān)鍵字值等于K的結(jié)點，成功時返回指向關(guān)鍵字的指針，不成功時返回標志0。TYPEDEFSTRUCTNODEINTKEYSTRUCTNODENEXTLKLISTVOIDCREATELKHASHLKLISTHASHTABLEINTI,KLKLISTSFORI0IKEYAIKAIPSNEXTHASHTABLEK_三、計算題每題10分，共30分1、畫出廣義表LS,E,A,B,C,D的頭尾鏈表存儲結(jié)構(gòu)。2、下圖所示的森林1求樹（A）的先根序列和后根序列；2求森林先序序列和中序序列；（3）將此森林轉(zhuǎn)換為相應的二叉樹；ABCDEFGHIJKAB3、設(shè)散列表的地址范圍是09，散列函數(shù)為H（KEY）（KEY22）MOD9,并采用鏈表處理沖突，請畫出元素7、4、5、3、6、2、8、9依次插入散列表的存儲結(jié)構(gòu)。四、算法設(shè)計題每題10分，共30分1設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素大寫字母、數(shù)字和其它字符，要求利用原單鏈表中結(jié)點空間設(shè)計出三個單鏈表的算法，使每個單鏈表只包含同類字符。2設(shè)計在鏈式存儲結(jié)構(gòu)上交換二叉樹中所有結(jié)點左右子樹的算法。3在鏈式存儲結(jié)構(gòu)上建立一棵二叉排序樹。數(shù)據(jù)結(jié)構(gòu)試卷（五）一、選擇題20分1數(shù)據(jù)的最小單位是（）。A數(shù)據(jù)項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)鍵字序列進行一趟歸并后的結(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é)點，現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序，則該操作的時間復雜度為（）。AOLOG2NBO1CON2DON6設(shè)一棵M叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為NL，度數(shù)為M的結(jié)點數(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，則從頂點A出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為（）。AABEDFCBACFEBDCAEBDFCDAEDFCB9設(shè)輸入序列是1、2、3、N，經(jīng)過棧的作用后輸出序列的第一個元素是N，則輸出序列中第I個輸出元素是（）。ANIBN1ICN1ID不能確定10設(shè)一組初始記錄關(guān)鍵字序列為45，80，55，40，42，85，則以第一個記錄關(guān)鍵字45為基準而得到一趟快速排序的結(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è)有一個順序共享棧S0N1，其中第一個棧項指針TOP1的初值為1，第二個棧頂指針TOP2的初值為N，則判斷共享棧滿的條件是_。2在圖的鄰接表中用順序存儲結(jié)構(gòu)存儲表頭結(jié)點的優(yōu)點是_。3設(shè)有一個N階的下三角矩陣A，如果按照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽蔷€上元素）存放在NN1個連續(xù)的存儲單元中，則AIJ與A00之間有_個數(shù)據(jù)元素。4棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，所以又把棧稱為_表；隊列的插入和刪除運算分別在隊列的兩端進行，先進隊列的元素必定先出隊列，所以又把隊列稱為_表。5設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF，則該二叉樹的前序遍歷序列為_，中序遍歷序列為_，后序遍歷序列為_。6設(shè)一棵完全二叉樹有128個結(jié)點，則該完全二叉樹的深度為_，有_個葉子結(jié)點。7設(shè)有向圖G的存儲結(jié)構(gòu)用鄰接矩陣A來表示，則A中第I行中所有非零元素個數(shù)之和等于頂點I的_，第I列中所有非零元素個數(shù)之和等于頂點I的_。8設(shè)一組初始記錄關(guān)鍵字序列K1，K2，KN是堆，則對I1，2，N/2而言滿足的條件為_。9下面程序段的功能是實現(xiàn)冒泡排序算法，請在下劃線處填上正確的語句。VOIDBUBBLEINTRNFORI1IRJ1TEMPRJ1_RJTEMPEXCHANGE1IFEXCHANGE0RETURN；10下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。STRUCTRECORDINTKEYINTOTHERSINTBISEARCHSTRUCTRECORDR,INTKINTLOW0,MID,HIGHN1WHILELOWNEXT0CHEADNEXTHEADDHEAD04時間復雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為ONLOG2N的是（）。A堆排序B冒泡排序C希爾排序D快速排序5設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（）。A空或只有一個結(jié)點B高度等于其結(jié)點數(shù)C任一結(jié)點無左孩子D任一結(jié)點無右孩子6一趟排序結(jié)束后不一定能夠選出一個元素放在其最終位置上的是（）。A堆排序B冒泡排序C快速排序D希爾排序7設(shè)某棵三叉樹中有40個結(jié)點，則該三叉樹的最小高度為（）。A3B4C5D68順序查找不論在順序線性表中還是在鏈式線性表中的時間復雜度為（）。AONBON2CON1/2DO1OG2N9二路歸并排序的時間復雜度為（）。AONBON2CONLOG2NDO1OG2N10深度為K的完全二叉樹中最少有（）個結(jié)點。A2K11B2K1C2K11D2K111設(shè)指針變量FRONT表示鏈式隊列的隊頭指針，指針變量REAR表示鏈式隊列的隊尾指針，指針變量S指向?qū)⒁腙犃械慕Y(jié)點X，則入隊列的操作序列為（）。AFRONTNEXTS；FRONTS；BSNEXTREAR；REARS；CREARNEXTS；REARS；DSNEXTFRONT；FRONTS；12設(shè)某無向圖中有N個頂點E條邊，則建立該圖鄰接表的時間復雜度為（）。AONEBON2CONEDON313設(shè)某哈夫曼樹中有199個結(jié)點，則該哈夫曼樹中有（）個葉子結(jié)點。A99B100C101D10214設(shè)二叉排序樹上有N個結(jié)點，則在二叉排序樹上查找結(jié)點的平均時間復雜度為（）。AONBON2CONLOG2NDO1OG2N15設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點I的入度為（）。A第I行非0元素的個數(shù)之和B第I列非0元素的個數(shù)之和C第I行0元素的個數(shù)之和D第I列0元素的個數(shù)之和二、判斷題20分1調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。（）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)比鏈式存儲結(jié)構(gòu)更好。（）9中序遍歷二叉排序樹可以得到一個有序的序列。（）10快速排序是排序算法中平均性能最好的一種排序。（）三、填空題30分1FORI1，T1，S0；I，則給出該圖的一種拓撲排序序列_。4設(shè)無向圖G中有N個頂點，則該無向圖中每個頂點的度數(shù)最多是_。5設(shè)二叉樹中度數(shù)為0的結(jié)點數(shù)為50，度數(shù)為1的結(jié)點數(shù)為30，則該二叉樹中總共有_個結(jié)點數(shù)。6設(shè)F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為_。7設(shè)二叉樹中結(jié)點的兩個指針域分別為LCHILD和RCHILD，則判斷指針變量P所指向的結(jié)點為葉子結(jié)點的條件是_。8簡單選擇排序和直接插入排序算法的平均時間復雜度為_。9快速排序算法的空間復雜度平均情況下為_，最壞的情況下為_。10散列表中解決沖突的兩種方法是_和_。四、算法設(shè)計題20分設(shè)計在順序有序表中實現(xiàn)二分查找的算法。設(shè)計判斷二叉樹是否為二叉排序樹的算法。在鏈式存儲結(jié)構(gòu)上設(shè)計直接插入排序算法數(shù)據(jù)結(jié)構(gòu)試卷（七）一、選擇題30分1設(shè)某無向圖有N個頂點，則該無向圖的鄰接表中有（）個表頭結(jié)點。A2NBNCN/2DNN12設(shè)無向圖G中有N個頂點，則該無向圖的最小生成樹上有（）條邊。ANBN1C2ND2N13設(shè)一組初始記錄關(guān)鍵字序列為60，80，55，40，42，85，則以第一個關(guān)鍵字45為基準而得到的一趟快速排序結(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開始對完全二叉樹進行順序編號，則編號為I結(jié)點的左孩子結(jié)點的編號為（）。A2I1B2ICI/2D2I16程序段SI0；DOII1；SSI；WHILEINEXT0CHEADNEXTHEADDHEAD08設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點最多有（）。A20B256C512D10249設(shè)一組初始記錄關(guān)鍵字序列為13，18，24，35，47，50，62，83，90，115，134,則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個數(shù)為（）。A1B2C3D410設(shè)指針變量TOP指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為（）。ATOPTOP1BTOPTOP1CTOPNEXTTOPDTOPTOPNEXT二、判斷題20分1不論是入隊列操作還是入棧操作，在順序存儲結(jié)構(gòu)上都需要考慮“溢出”情況。（）2當向二叉排序樹中插入一個結(jié)點，則該結(jié)點一定成為葉子結(jié)點。（）3設(shè)某堆中有N個結(jié)點，則在該堆中插入一個新結(jié)點的時間復雜度為OLOG2N。（）4完全二叉樹中的葉子結(jié)點只可能在最后兩層中出現(xiàn)。（）5哈夫曼樹中沒有度數(shù)為1的結(jié)點。（）6對連通圖進行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。（）7先序遍歷一棵二叉排序樹得到的結(jié)點序列不一定是有序的序列。（）8由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。（）9線性表中的所有元素都有一個前驅(qū)元素和后繼元素。（）10帶權(quán)無向圖的最小生成樹是唯一的。（）三、填空題30分1設(shè)指針變量P指向雙向鏈表中的結(jié)點A，指針變量S指向被插入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X的操作序列為_P；SRIGHTPRIGHT；_S；PRIGHTLEFTS；（設(shè)結(jié)點中的兩個指針域分別為LEFT和RIGHT）。2設(shè)完全有向圖中有N個頂點，則該完全有向圖中共有_條有向條；設(shè)完全無向圖中有N個頂點，則該完全無向圖中共有_條無向邊。3設(shè)關(guān)鍵字序列為KL，K2，KN，則用篩選法建初始堆必須從第_個元素開始進行篩選。4解決散列表沖突的兩種方法是_和_。5設(shè)一棵三叉樹中有50個度數(shù)為0的結(jié)點，21個度數(shù)為2的結(jié)點，則該二叉樹中度數(shù)為3的結(jié)點數(shù)有_個。6高度為H的完全二叉樹中最少有_個結(jié)點，最多有_個結(jié)點。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下面程序段的功能是實現(xiàn)一趟快速排序，請在下劃線處填上正確的語句。STRUCTRECORDINTKEYDATATYPEOTHERSVOIDQUICKPASSSTRUCTRECORDR,INTS,INTT,INTSTRUCTRECORDXRSISWHILEIXKEYJJ1IFIDATAKTLCHILDTRCHILD0ELSEIFTDATAKBSTINSERTTLCHILD,KELSE_3設(shè)指針變量P指向單鏈表中結(jié)點A，指針變量S指向被插入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X需要執(zhí)行的語句序列SNEXTPNEXT_。4設(shè)指針變量HEAD指向雙向鏈表中的頭結(jié)點，指針變量P指向雙向鏈表中的第一個結(jié)點，則指針變量P和指針變量HEAD之間的關(guān)系是P_和HEAD_（設(shè)結(jié)點中的兩個指針域分別為LLINK和RLINK）。5設(shè)某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為_。6完全二叉樹中第5層上最少有_個結(jié)點，最多有_個結(jié)點。7設(shè)有向圖中不存在有向邊，則其對應的鄰接矩陣A中的數(shù)組元素AIJ的值等于_。8設(shè)一組初始記錄關(guān)鍵字序列為49，38，65，97，76，13，27，50，則第4趟直接選擇排序結(jié)束后的結(jié)果為_。9設(shè)連通圖G中有N個頂點E條邊，則對應的最小生成樹上有_條邊。10設(shè)有一組初始記錄關(guān)鍵字序列為50，16，23，68，94，70，73，則將它們調(diào)整成初始堆只需把16與_相互交換即可。四、算法設(shè)計題20分1設(shè)計一個在鏈式存儲結(jié)構(gòu)上統(tǒng)計二叉樹中結(jié)點個數(shù)的算法。2設(shè)計一個算法將無向圖的鄰接矩陣轉(zhuǎn)為對應鄰接表的算法。數(shù)據(jù)結(jié)構(gòu)試卷（九）一、選擇題30分1下列程序段的時間復雜度為（）。FORI0；IRIGHTS；SLEFTP；PRIGHTLEFTS；SRIGHTPRIGHT；BSLEFTP；SRIGHTPRIGHT；PRIGHTS；PRIGHTLEFTS；CPRIGHTS；PRIGHTLEFTS；SLEFTP；SRIGHTPRIGHT；DSLEFTP；SRIGHTPRIGHT；PRIGHTLEFTS；PRIGHTS；6下列各種排序算法中平均時間復雜度為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的最大素數(shù)C小于等于M的最大偶數(shù)D小于等于M的最大合數(shù)9設(shè)在一棵度數(shù)為3的樹中，度數(shù)為3的結(jié)點數(shù)有2個，度數(shù)為2的結(jié)點數(shù)有1個，度數(shù)為1的結(jié)點數(shù)有2個，那么度數(shù)為0的結(jié)點數(shù)有（）個。A4B5C6D710設(shè)完全無向圖中有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的一種拓撲排序序列的是（）。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é)點A，指針S指向被插入的結(jié)點X，則在結(jié)點A的前面插入結(jié)點X時的操作序列為1SNEXT_；2PNEXTS；3TPDATA；4PDATA_；5SDATAT；2設(shè)某棵完全二叉樹中有100個結(jié)點，則該二叉樹中有_個葉子結(jié)點。3設(shè)某順序循環(huán)隊列中有M個元素，且規(guī)定隊頭指針F指向隊頭元素的前一個位置，隊尾指針R指向隊尾元素的當前位置，則該循環(huán)隊列中最多存儲_隊列元素。4對一組初始關(guān)鍵字序列（40，50，95，20，15，70，60，45，10）進行冒泡排序，則第一趟需要進行相鄰記錄的比較的次數(shù)為_，在整個排序過程中最多需要進行_趟排序才可以完成。5在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮應最好選擇_排序，如果從節(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)值之和為_。三、判斷題20分1有向圖的鄰接表和逆鄰接表中表結(jié)點的個數(shù)不一定相等。2對鏈表進行插入和刪除操作時不必移動鏈表中結(jié)點。3子串“ABC”在主串“AABCABCD”中的位置為2。4若一個葉子結(jié)點是某二叉樹的中序遍歷序列的最后一個結(jié)點，則它必是該二叉樹的先序遍歷序列中的最后一個結(jié)點。5希爾排序算法的時間復雜度為ON2。6用鄰接矩陣作為圖的存儲結(jié)構(gòu)時，則其所占用的存儲空間與圖中頂點數(shù)無關(guān)而與圖中邊數(shù)有關(guān)。7中序遍歷一棵二叉排序樹可以得到一個有序的序列。8入棧操作和入隊列操作在鏈式存儲結(jié)構(gòu)上實現(xiàn)時不需要考慮棧溢出的情況。9順序表查找指的是在順序存儲結(jié)構(gòu)上進行查找。（）10堆是完全二叉樹，完全二叉樹不一定是堆。（）五、算法設(shè)計題20分1設(shè)計計算二叉樹中所有結(jié)點值之和的算法。2設(shè)計將所有奇數(shù)移到所有偶數(shù)之前的算法。3設(shè)計判斷單鏈表中元素是否是遞增的算法。數(shù)據(jù)結(jié)構(gòu)試卷（十）一、選擇題24分1下列程序段的時間復雜度為（）。I0，S0；WHILESNEXTPNEXT；PNEXTS；BQNEXTS；SNEXTP；CPNEXTSNEXT；SNEXTP；DPNEXTS；SNEXTQ；4設(shè)輸入序列為1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為（）。A5，3，4，6，1，2B3，2，5，6，4，1C3，1，2，5，4，6D1，5，4，6，2，35設(shè)有一個10階的下三角矩陣A（包括對角線），按照從上到下、從左到右的順序存儲到連續(xù)