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

數(shù)據(jù)結(jié)構(gòu)試題一、單選題（每題2分，共20分）11對一個算法的評價，不包括如下（）方面的內(nèi)容。A健壯性和可讀性B并行性C正確性D時空復(fù)雜度22在帶有頭結(jié)點的單鏈表HL中，要向表頭插入一個由指針P指向的結(jié)點，則執(zhí)行。APNEXTHLNEXTHLNEXTPBPNEXTHLHLPCPNEXTHLPHLDHLPPNEXTHL33對線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示A經(jīng)常需要隨機地存取元素B經(jīng)常需要進(jìn)行插入和刪除操作C表中元素需要占據(jù)一片連續(xù)的存儲空間D表中元素的個數(shù)不變44一個棧的輸入序列為123，則下列序列中不可能是棧的輸出序列的是A231B321C312D12355AOV網(wǎng)是一種（）。A有向圖B無向圖C無向無環(huán)圖D有向無環(huán)圖66采用開放定址法處理散列表的沖突時，其平均查找長度（）。A低于鏈接法處理沖突B高于鏈接法處理沖突C與鏈接法處理沖突相同D高于二分查找77若需要利用形參直接訪問實參時，應(yīng)將形參變量說明為（）參數(shù)。A值B函數(shù)C指針D引用88在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結(jié)點都具有相同的（）。A行號B列號C元素值D非零元素個數(shù)99快速排序在最壞情況下的時間復(fù)雜度為（）。AOLOG2NBONLOG2NC0ND0N21010從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為。AONBO1COLOG2NDON2二、運算題（每題6分，共24分）11數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的_對應(yīng)關(guān)系_。當(dāng)結(jié)點之間存在M對N（MN）的聯(lián)系時，稱這種結(jié)構(gòu)為_多對多_。22隊列的插入操作是在隊列的_隊尾_進(jìn)行，刪除操作是在隊列的_對頭_進(jìn)行。33當(dāng)用長度為N的數(shù)組順序存儲一個棧時，假定用TOPN表示?？?，則表示棧滿的條件是_TOP0_。44對于一個長度為N的單鏈存儲的線性表，在表頭插入元素的時間復(fù)雜度為_01_，在表尾插入元素的時間復(fù)雜度為_01_。55設(shè)W為一個二維數(shù)組，其每個數(shù)據(jù)元素占用4個字節(jié)，行下標(biāo)I從0到7，列下標(biāo)J從0到3，則二維數(shù)組W的數(shù)據(jù)元素共占用128個字節(jié)。W中第6行的元素和第4列的元素共占用44_個字節(jié)。若按行順序存放二維數(shù)組W，其起始地址為100，則二維數(shù)組元素W6，3的起始地址為124_。66廣義表AA,A,B,A,B,C,則它的深度為_3_，它的長度為_3_。77二叉樹是指度為2的_有序_樹。一棵結(jié)點數(shù)為N的二叉樹，其所有結(jié)點的度的總和是_N1_。88對一棵二叉搜索樹進(jìn)行中序遍歷時，得到的結(jié)點序列是一個_有序序列_。對一棵由算術(shù)表達(dá)式組成的二叉語法樹進(jìn)行后序遍歷得到的結(jié)點序列是該算術(shù)表達(dá)式的_后綴表達(dá)式_。99對于一棵具有N個結(jié)點的二叉樹，用二叉鏈表存儲時，其指針總數(shù)為_2N_個，其中_N1_個用于指向孩子，_N1_個指針是空閑的。1010若對一棵完全二叉樹從0開始進(jìn)行結(jié)點的編號，并按此編號把它順序存儲到一維數(shù)組A中，即編號為0的結(jié)點存儲到A0中。其余類推，則AI元素的左孩子元素為_2I_,右孩子元素為_2I1_，雙親元素為_I/2_。1111在線性表的散列存儲中，處理沖突的常用方法有_開放地址法_和_鏈接法_兩種。1212當(dāng)待排序的記錄數(shù)較大，排序碼較隨機且對穩(wěn)定性不作要求時，宜采用_排序；當(dāng)待排序的記錄數(shù)較大，存儲空間允許且要求排序是穩(wěn)定時，宜采用_排序。二、三、運算題（每題6分，共24分）11已知一個65稀疏矩陣如下所示，試（1）（1）寫出它的三元組線性表；（2）（2）給出三元組線性表的順序存儲表示。22設(shè)有一個輸入數(shù)據(jù)的序列是46,25,78,62,12,80,試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉搜索樹。33對于圖6所示的有向圖若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，試寫出1從頂點出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；2從頂點出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹；44已知一個圖的頂點集V和邊集E分別為V1,2,3,4,5,6,7E,若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，按主教材中介紹的拓樸排序算法進(jìn)行排序，試給出得到的拓樸排序的序列。三、四、閱讀算法（每題7分，共14分）11INTPRIMEINTNINTI1INTXINTSQRTNWHILEIXRETURN1ELSERETURN011指出該算法的功能；22該算法的時間復(fù)雜度是多少07052100圖622寫出下述算法的功能VOIDAJADJLISTGL,INTI,INTNQUEUEQINITQUEUEQCOUTADJVEXIFVISITEDJCOUTNEXT四、五、算法填空（共8分）如下為二分查找的非遞歸算法，試將其填寫完整。INTBINSCHELEMTYPEA,INTN,KEYTYPEKINTLOW0INTHIGHN1WHILELOWNEXTELEMTYPETEMPPDATADELETEPRETURNTEMP課程測試試題（卷）一、單選題（每題2分，共20分）11棧和隊列的共同特點是。A只允許在端點處插入和刪除元素B都是先進(jìn)后出C都是先進(jìn)先出D沒有共同點22用鏈接方式存儲的隊列，在進(jìn)行插入運算時A僅修改頭指針B頭、尾指針都要修改C僅修改尾指針D頭、尾指針可能都要修改33以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)A隊列B棧C線性表D二叉樹44設(shè)有一個二維數(shù)組AMN，假設(shè)A00存放位置在64410，A22存放位置在67610，每個元素占一個空間，問A3310存放在什么位置腳注10表示用10進(jìn)制表示。A688B678C692D69655樹最適合用來表示。A有序數(shù)據(jù)元素B無序數(shù)據(jù)元素C元素之間具有分支層次關(guān)系的數(shù)據(jù)D元素之間無聯(lián)系的數(shù)據(jù)66二叉樹的第K層的結(jié)點數(shù)最多為A2K1B2K1C2K1D2K177若有18個元素的有序表存放在一維數(shù)組A19中，第一個元素放A1中，現(xiàn)進(jìn)行二分查找，則查找A3的比較序列的下標(biāo)依次為A1，2，3B9，5，2，3C9，5，3D9，4，2，388對N個記錄的文件進(jìn)行快速排序，所需要的輔助存儲空間大致為AO（1）BO（N）CO（1OG2N）DO（N2）99對于線性表（7，34，55，25，64，46，20，10）進(jìn)行散列存儲時，若選用H（K）K9作為散列函數(shù)，則散列地址為1的元素有（）個，A1B2C3D41010設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有條邊才能確保是一個連通圖。A5B6C7D8二、二、填空題（每空1分，共26分）11通常從四個方面評價算法的質(zhì)量_、_、_和_。22一個算法的時間復(fù)雜度為N3N2LOG2N14N/N2，其數(shù)量級表示為_。33假定一棵樹的廣義表表示為A（C，D（E，F(xiàn)，G），H（I，J），則樹中所含的結(jié)點數(shù)為_個，樹的深度為_，樹的度為_。44后綴算式923102/的值為_。中綴算式（34X）2Y/3對應(yīng)的后綴算式為_。55若用鏈表存儲一棵二叉樹時，每個結(jié)點除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結(jié)構(gòu)中，N個結(jié)點的二叉樹共有_個指針域，其中有_個指針域是存放了地址，有_個指針是空指針。66對于一個具有N個頂點和E條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點分別有_個和_個。77AOV網(wǎng)是一種_的圖。88在一個具有N個頂點的無向完全圖中，包含有_條邊，在一個具有N個頂點的有向完全圖中，包含有_條邊。99假定一個線性表為12,23,74,55,63,40，若按KEY4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個子表，則得到的四個子表分別為_、_、_和_。1010向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點的分裂，則新樹比原樹的高度_。1111在堆排序的過程中，對任一分支結(jié)點進(jìn)行篩運算的時間復(fù)雜度為_，整個堆排序過程的時間復(fù)雜度為_。1212在快速排序、堆排序、歸并排序中，_排序是穩(wěn)定的。三、三、運算題（每題6分，共24分）11在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A0NEXT，試寫出該線性表。A01234567DATA605078903440NEXT357204122請畫出圖10的鄰接矩陣和鄰接表。33已知一個圖的頂點集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用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。44畫出向小根堆中加入數(shù)據(jù)4,2,5,8,3時，每加入一個數(shù)據(jù)后堆的變化。四、四、閱讀算法（每題7分，共14分）11LINKLISTMYNOTELINKLISTL/L是不帶頭結(jié)點的單鏈表的頭指針I(yè)FLABCBTRIGHTCOUTDATADATAITEMBSTDATA/查找成功RETURN_ELSEIFITEMDATARETURNFIND_,ITEMELSERETURNFIND_,ITEM/IF六、六、編寫算法（共8分）統(tǒng)計出單鏈表HL中結(jié)點的值等于給定值X的結(jié)點數(shù)。INTCOUNTXLNODEHL,ELEMTYPEX參考答案一、一、單選題（每題2分，共20分）1A2D3D4C5C6D7D8C9D10A二、二、填空題（每空1分，共26分）11正確性易讀性強壯性高效率22ON3393344134X2Y3/552NN1N166E2E77有向無回路88NN1/2NN199（12，40）（）（74）（23,55，63）1010增加11111OLOG2NONLOG2N1212歸并三、三、運算題（每題6分，共24分）11線性表為（78，50，40，60，34，90）22鄰接矩陣010010鄰接表如圖11所示圖1133用克魯斯卡爾算法得到的最小生成樹為1,23,4,64,1,35,1,48,2,510,4,72044見圖12圖12四、四、閱讀算法（每題7分，共14分）11（1）查詢鏈表的尾結(jié)點（2）將第一個結(jié)點鏈接到鏈表的尾部，作為新的尾結(jié)點（3）返回的線性表為（A2,A3,AN,A1）22遞歸地后序遍歷鏈?zhǔn)酱鎯Φ亩鏄?。五、五、算法填空（每?分，共8分）TRUEBSTLEFTBSTRIGHT六、六、編寫算法（8分）INTCOUNTXLNODEHL,ELEMTYPEXINTI0LNODEPHL/I為計數(shù)器4444422255522884352834WHILEPNULLIFPDATAXIPPNEXT/WHILE,出循環(huán)時I中的值即為X結(jié)點個數(shù)RETURNI/COUNTX課程測試試題（卷）一、單選題（每小題2分，共8分）1、1、在一個長度為N的順序線性表中順序查找值為X的元素時，查找成功時的平均查找長度（即X與元素的平均比較次數(shù)，假定查找每個元素的概率都相等）為。ANBN/2CN1/2DN1/22、2、在一個單鏈表中,若Q所指結(jié)點是P所指結(jié)點的前驅(qū)結(jié)點,若在Q與P之間插入一個S所指的結(jié)點,則執(zhí)行。ASLINKPLINKPLINKSBPLINKSSLINKQCPLINKSLINKSLINKPDQLINKSSLINKP3、3、棧的插入和刪除操作在（）進(jìn)行。A棧頂B棧底C任意位置D指定位置4、4、由權(quán)值分別為11，8，6，2，5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）A24B71C48D53二、二、填空題（每空1分，共32分）1、1、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為_、_、_和_四種。2、2、一種抽象數(shù)據(jù)類型包括_和_兩個部分。3、3、在下面的數(shù)組A中鏈接存儲著一個線性表，表頭指針為AONEXT，則該線性表為_。A012345678DATANEXT4、4、在以HL為表頭指針的帶表頭附加結(jié)點的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件分別為_和6056423874254376201_。5、5、用具有N個元素的一維數(shù)組存儲一個循環(huán)隊列，則其隊首指針總是指向隊首元素的_，該循環(huán)隊列的最大長度為_。6、6、當(dāng)堆棧采用順序存儲結(jié)構(gòu)時，棧頂元素的值可用表示；當(dāng)堆棧采用鏈接存儲結(jié)構(gòu)時，棧頂元素的值可用_表示。7、7、一棵高度為5的二叉樹中最少含有_個結(jié)點，最多含有_個結(jié)點；一棵高度為5的理想平衡樹中，最少含有_個結(jié)點，最多含有_個結(jié)點。8、8、在圖的鄰接表中，每個結(jié)點被稱為_，通常它包含三個域一是_；二是_；三是_。9、9、在一個索引文件的索引表中，每個索引項包含對應(yīng)記錄的_和_兩項數(shù)據(jù)。10、10、假定一棵樹的廣義表表示為A（B（C，D（E，F(xiàn)，G），H（I，J），則樹中所含的結(jié)點數(shù)為_個，樹的深度為_,樹的度為_,結(jié)點H的雙親結(jié)點為_,孩子結(jié)點為_。11、11、在堆排序的過程中，對任一分支結(jié)點進(jìn)行篩運算的時間復(fù)雜度為_,整個堆排序過程的時間復(fù)雜度為_。12、12、在對M階的B_樹插入元素的過程中，每向一個結(jié)點插入一個索引項（葉子結(jié)點中的索引項為關(guān)鍵字和空指針）后，若該結(jié)點的索引項數(shù)等于_個，則必須把它分裂為_個結(jié)點。三、三、運算題（每小題6分，共24分）1、1、已知一組記錄的排序碼為（46，79，56，38，40，80,95，24），寫出對其進(jìn)行快速排序的每一次劃分結(jié)果。2、2、一個線性表為B（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為HT012，散列函數(shù)為H（KEY）KEY13并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。3、3、已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECKFGHIJ，中序遍歷的結(jié)果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結(jié)果。4、4、已知一個圖的頂點集V各邊集G如下V0，1，2，3，4，5，6，7，8，9；E（0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3，8），（5，6），（5，8），（5，9），（6，7），（7，8），（8，9）當(dāng)它用鄰接矩陣表示和鄰接表表示時，分別寫出從頂點V0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點序列和按廣度優(yōu)先搜索遍歷等到的頂點序列。假定每個頂點鄰接表中的結(jié)點是按頂點序號從大到小的次序鏈接的。四、閱讀算法，回答問題（每小題8分，共16分）1、假定從鍵盤上輸入一批整數(shù)，依次為7863453091341，請寫出輸出結(jié)果。INCLUDEINCLUDECONSSTINTSTACKMAXSIZE30TYPEDEFINTELEMTYPESTRUCTSTACKELEMTYPESTACKSTACKMAXSIZEINTTOPINCLUDE“STACKH”VOIDMAINSTACKAINITSTACKAINTXCINXWHILEX1PUSHA,XCINXWHILESTACKEMPTYACOUTVOIDBINTREEUNKNOWNBINTREENODETBINTREENODEPT,TEMPIFPNULLTEMPPLEFTCHILDPLEFTCHILDPRIGHTCHILDPRIGHTCHILDTEMPUNKNOWNPLEFTCHILDUNDNOWNPRIGHTCHILD該算法的功能是_四、五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容（10分）對順序存儲的有序表進(jìn)行二分查找的遞歸算法。INTBINSCHELEMTYPEA,INTLOW,INTHIGH,KEYTYPEKIFLOWDATEDATERETURN1；IFS1DATES2DATERETURN1；IFRETURN1；IFRETURN1；31閱讀下面的算法LINKLISTMYNOTELINKLISTL/L是不帶頭結(jié)點的單鏈表的頭指針ABCDEIFLRETURN1；33已知二叉樹的存儲結(jié)構(gòu)為二叉鏈表，閱讀下面算法。TYPEDEFSTRUCTNODEDATETYPEDATA；STRUCTNODENEXT；LISTNODE；TYPEDEFLISTNODELINKLIST；LINKLISTLEAFHEADNULL；VOIDINORDERBINTREETLINKLISTS；IFTINORDERTLCHILD；IFTLCHILD。22設(shè)線性表中有N個數(shù)據(jù)元素，則在順序存儲結(jié)構(gòu)上實現(xiàn)順序查找的平均時間復(fù)雜度為_，在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實現(xiàn)順序查找的平均時間復(fù)雜度為_。33設(shè)一棵二叉樹中有N個結(jié)點，則當(dāng)用二叉鏈表作為其存儲結(jié)構(gòu)時，該二叉鏈表中共有_個指針域，_個空指針域。44設(shè)指針變量P指向單鏈表中結(jié)點A，指針變量S指向被插入的結(jié)點B，則在結(jié)點A的后面插入結(jié)點B的操作序列為_。55設(shè)無向圖G中有N個頂點和E條邊，則其對應(yīng)的鄰接表中有_個表頭結(jié)點和_個表結(jié)點。66設(shè)無向圖G中有N個頂點E條邊，所有頂點的度數(shù)之和為M，則E和M有_關(guān)系。77設(shè)一棵二叉樹的前序遍歷序列和中序遍歷序列均為ABC，則該二叉樹的后序遍歷序列為_。88設(shè)一棵完全二叉樹中有21個結(jié)點，如果按照從上到下、從左到右的順序從1開始順序編號，則編號為8的雙親結(jié)點的編號是_，編號為8的左孩子結(jié)點的編號是_。99下列程序段的功能實現(xiàn)子串T在主串S中位置的算法，要求在下劃線處填上正確語句。INTINDEXCHARS,CHARTIJ0WHILEINEXTPNEXTSNEXTS45N,2E56M2E67CBA784，1689IJ1，0910N1三、應(yīng)用題11鏈?zhǔn)酱鎯Y(jié)構(gòu)略，前序ABDEC，中序DBEAC，后序DEBCA。22哈夫曼樹略，WPL783318,5,16,19,21,23，5，16，21，19，18，2344線性探測68273510842鏈地址法2768351084320HH55深度125364，廣度123456，最小生成樹T的邊集為E1，4，1，3，3，5，5，6，5,6四、算法設(shè)計題11設(shè)計判斷單鏈表中結(jié)點是否關(guān)于中心對稱算法。TYPEDEFSTRUCTINTS100INTTOPSQSTACKINTLKLISTSYMMETRYLKLISTHEADSQSTACKSTACKSTACKTOP1LKLISTPFORPHEADP0PPNEXTSTACKTOPSTACKSSTACKTOPPDATAFORPHEADP0PPNEXTIFPDATASTACKSSTACKTOPSTACKTOPSTACKTOP1ELSERETURN0RETURN122設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉樹的算法。TYPEDEFCHARDATATYPETYPEDEFSTRUCTNODEDATATYPEDATASTRUCTNODELCHILD,RCHILDBITREEVOIDCREATEBITREEBITREESCANF“C“,IFCHBT0RETURNBTBITREEMALLOCSIZEOFBITREEBTDATACHCREATEBITREEBTLCHILDCREATEBITREEBTRCHILD33設(shè)計判斷一棵二叉樹是否是二叉排序樹的算法。INTMINNUM32768,FLAG1TYPEDEFSTRUCTNODEINTKEYSTRUCTNODELCHILD,RCHILDBITREEVOIDINORDERBITREEBTIFBT0INORDERBTLCHILDIFMINNUMBTKEYFLAG0MINNUMBTKEYINORDERBTRCHILD數(shù)據(jù)結(jié)構(gòu)試卷（二）一、選擇題24分1下面關(guān)于線性表的敘述錯誤的是（）。A線性表采用順序存儲必須占用一片連續(xù)的存儲空間B線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間C線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實現(xiàn)D線性表采用順序存儲便于插入和刪除操作的實現(xiàn)2設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為M，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有（）個空指針域。A2M1B2MC2M1D4M3設(shè)順序循環(huán)隊列Q0M1的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當(dāng)前位置，則該循環(huán)隊列中的元素個數(shù)為（）。ARFBFRCRFMMDFRMM4設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（）。ABADCBBCDACCDABDCBDA5設(shè)某完全無向圖中有N個頂點，則該完全無向圖中有（）條邊。ANN1/2BNN1CN2DN216設(shè)某棵二叉樹中有2000個結(jié)點，則該二叉樹的最小高度為（）。A9B10C11D127設(shè)某有向圖中有N個頂點，則該有向圖對應(yīng)的鄰接表中有（）個表頭結(jié)點。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分11為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個問題是_和_。22下面程序段的功能實現(xiàn)數(shù)據(jù)X進(jìn)棧，要求在下劃線處填上正確的語句。TYPEDEFSTRUCTINTS100INTTOPSQSTACKVOIDPUSHSQSTACKELSE_33中序遍歷二叉排序樹所得到的序列是_序列（填有序或無序）。44快速排序的最壞時間復(fù)雜度為_，平均時間復(fù)雜度為_。55設(shè)某棵二叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為N1，則該二叉樹中度數(shù)為2的結(jié)點數(shù)為_；若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有_個空指針域。66設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為N和E，所有頂點的度數(shù)之和為D，則E_。77設(shè)一組初始記錄關(guān)鍵字序列為55，63，44，38，75，80，31，56，則利用篩選法建立的初始堆為_。88設(shè)某無向圖G的鄰接表為31244321V，則從頂點V1開始的深度優(yōu)先遍歷序列為_；廣度優(yōu)先遍歷序列為_。三、應(yīng)用題36分11設(shè)一組初始記錄關(guān)鍵字序列為45，80，48，40，22，78，則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。22設(shè)指針變量P指向雙向鏈表中結(jié)點A，指針變量Q指向被插入結(jié)點B，要求給出在結(jié)點A的后面插入結(jié)點B的操作序列（設(shè)雙向鏈表中結(jié)點的兩個指針域分別為LLINK和RLINK）。33設(shè)一組有序的記錄關(guān)鍵字序列為13，18，24，35，47，50，62，83，90，查找方法用二分查找，要求計算出查找關(guān)鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長度。44設(shè)一棵樹T中邊的集合為A，B，A，C，A，D，B，E，C，F(xiàn)，C，G，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。55設(shè)有無向圖G（如右圖所示），要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。66設(shè)有一組初始記錄關(guān)鍵字為45，80，48，40，22，78，要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。四、算法設(shè)計題16分11設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，KN），要求設(shè)計一個算法能夠在ON的時間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于KI，右半部分的每個關(guān)鍵字均大于等于KI。22設(shè)有兩個集合A和集合B，要求設(shè)計生成集合CAB的算法，其中集合A、B和C用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示。數(shù)據(jù)結(jié)構(gòu)試卷（二）參考答案一、選擇題1D2B3C4A5A6C7B8C二、填空題11構(gòu)造一個好的HASH函數(shù)，確定解決沖突的方法22STACKTOP，STACKSSTACKTOPX33有序44ON2，ONLOG2N55N01，2N0N166D/27731，38，54，56，75，80，55，63881，3，4，2，1，3，2，4三、應(yīng)用題1122，40，45，48，80，78，40，45，48，80，22，7822QLLINKPQRLINKPRLINKPRLINKLLINKQPRLINKQ332,ASL91122344225/944樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)略，二叉樹略55E1，3，1，2，3，5，5，6，6，466略四、算法設(shè)計題11設(shè)有一組初始記錄關(guān)鍵字序列（K1，K2，KN），要求設(shè)計一個算法能夠在ON的時間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于KI，右半部分的每個關(guān)鍵字均大于等于KI。VOIDQUICKPASSINTR,INTS,INTTINTIS,JT,XRSWHILEIXJJ1IFINEXTFORQHBQ0QQNEXTIFQDATAPDATABREAKIFQ0TLKLISTMALLOCSIZEOFLKLISTTDATAPDATATNEXTHCHCT數(shù)據(jù)結(jié)構(gòu)試卷（三）一、選擇題30分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下面程序的時間復(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é)點，則在二叉排序樹的平均平均查找長度為（）。AO1BOLOG2NCDON27設(shè)無向圖G中有N個頂點E條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點和表結(jié)點的個數(shù)分別為（）。AN，EBE，NC2N，EDN，2E8設(shè)某強連通圖中有N個頂點，則該強連通圖中至少有（）條邊。ANN1BN1CNDNN19設(shè)有5000個待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個記錄關(guān)鍵字，則用下列（）方法可以達(dá)到此目的。A快速排序B堆排序C歸并排序D插入排序10下列四種排序中（）的空間復(fù)雜度最大。A插入排序B冒泡排序C堆排序D歸并排序二、填空殖48分，其中最后兩小題各6分11數(shù)據(jù)的物理結(jié)構(gòu)主要包括_和_兩種情況。22設(shè)一棵完全二叉樹中有500個結(jié)點，則該二叉樹的深度為_；若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有_個空指針域。33設(shè)輸入序列為1、2、3，則經(jīng)過棧的作用后可以得到_種不同的輸出序列。44設(shè)有向圖G用鄰接矩陣ANN作為存儲結(jié)構(gòu)，則該鄰接矩陣中第I行上所有元素之和等于頂點I的_，第I列上所有元素之和等于頂點I的_。55設(shè)哈夫曼樹中共有N個結(jié)點，則該哈夫曼樹中有_個度數(shù)為1的結(jié)點。66設(shè)有向圖G中有N個頂點E條有向邊，所有的頂點入度數(shù)之和為D，則E和D的關(guān)系為_。77_遍歷二叉排序樹中的結(jié)點可以得到一個遞增的關(guān)鍵字序列（填先序、中序或后序）。88設(shè)查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較_次就可以斷定數(shù)據(jù)元素X是否在查找表中。99不論是順序存儲結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧，其入棧和出棧操作的時間復(fù)雜度均為_。1010設(shè)有N個結(jié)點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第I個結(jié)點的雙親結(jié)點編號為_，右孩子結(jié)點的編號為_。1111設(shè)一組初始記錄關(guān)鍵字為72，73，71，23，94，16，5，則以記錄關(guān)鍵字72為基準(zhǔn)的一趟快速排序結(jié)果為_。1212設(shè)有向圖G中有向邊的集合E，則該圖的一種拓?fù)湫蛄袨開。1313下列算法實現(xiàn)在順序散列表中查找值為X的關(guān)鍵字，請在下劃線處填上正確的語句。STRUCTRECORDINTKEYINTOTHERSINTHASHSQSEARCHSTRUCTRECORDHASHTABLE,INTKINTI,JJIKPWHILEHASHTABLEJKEYKIFIJRETURN1IF_RETURNJELSERETURN11414下列算法實現(xiàn)在二叉排序樹上查找關(guān)鍵值K，請在下劃線處填上正確的語句。TYPEDEFSTRUCTNODEINTKEYSTRUCTNODELCHILDSTRUCTNODERCHILDBITREEBITREEBSTSEARCHBITREET,INTKIFT0RETURN0ELSEWHILET0IFTKEYK_ELSEIFTKEYKTTLCHILDELSE_三、算法設(shè)計題22分11設(shè)計在單鏈表中刪除值相同的多余結(jié)點的算法。22設(shè)計一個求結(jié)點X在二叉樹中的雙親結(jié)點算法。數(shù)據(jù)結(jié)構(gòu)試卷（三）參考答案一、選擇題1B2B3A4A5A6B7D8C9B10D第3小題分析首先用指針變量Q指向結(jié)點A的后繼結(jié)點B，然后將結(jié)點B的值復(fù)制到結(jié)點A中，最后刪除結(jié)點B第9小題分析9快速排序、歸并排序和插入排序必須等到整個排序結(jié)束后才能夠求出最小的10個數(shù)，而堆排序只需要在初始堆的基礎(chǔ)上再進(jìn)行10次篩選即可，每次篩選的時間復(fù)雜度為OLOG2N。二、填空題11順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)229，50133544出度，入度55066ED77中序88799O11010I/2，2I111115，16，71，23，72，94，7312121，4，3，21313J1，HASHTABLEJKEYK1414RETURNT，TTRCHILD第8小題分析二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進(jìn)行二分查找時的查找長度不超過二叉判定樹的高度1LOG2N。三、算法設(shè)計題11設(shè)計在單鏈表中刪除值相同的多余結(jié)點的算法。TYPEDEFINTDATATYPETYPEDEFSTRUCTNODEDATATYPEDATASTRUCTNODENEXTLKLISTVOIDDELREDUNDANTLKLISTFORPHEADP0PPNEXTFORQPNEXT,SQQ0IFQDATAPDATASNEXTQNEXTFREEQQSNEXTELSESQ,QQNEXT22設(shè)計一個求結(jié)點X在二叉樹中的雙親結(jié)點算法。TYPEDEFSTRUCTNODEDATATYPEDATASTRUCTNODELCHILD,RCHILDBITREEBITREEQ20INTR0,F0,FLAG0VOIDPREORDERBITREEBT,CHARXIFBT0RETURNELSERR120QRBTPREORDERBTLCHILD,XPREORDERBTRCHILD,XVOIDPARENTBITREEBT,CHARXINTIPREORDERBT,XFORIF1ILCHILDDATAX|QIRCHILDDATABREAKIFFLAG0PRINTF“NOTFOUNDXN“ELSEIFIDATAELSEPRINTF“NOTPARENT“數(shù)據(jù)結(jié)構(gòu)試卷（四）一、選擇題30分1設(shè)一維數(shù)組中有N個數(shù)組元素，則讀取第I個數(shù)組元素的平均時間復(fù)雜度為（）。AONBONLOG2NCO1DON22設(shè)一棵二叉樹的深度為K，則該二叉樹中最多有（）個結(jié)點。A2K1B2KC2K1D2K13設(shè)某無向圖中有N個頂點E條邊，則該無向圖中所有頂點的入度之和為（）。ANBEC2ND2E4在二叉排序樹中插入一個結(jié)點的時間復(fù)雜度為（）。AO1BONCOLOG2NDON25設(shè)某有向圖的鄰接表中有N個表頭結(jié)點和M個表結(jié)點，則該圖中有（）條有向邊。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é)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為NL，度數(shù)為2的結(jié)點數(shù)為N2，則下列等式成立的是（）。AN0N11BN0NLN2CN0N21DN02N1L10設(shè)有序順序表中有N個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過（）。ALOG2N1BLOG2N1CLOG2NDLOG2N1二、填空題42分11設(shè)有N個無序的記錄關(guān)鍵字，則直接插入排序的時間復(fù)雜度為_，快速排序的平均時間復(fù)雜度為_。22設(shè)指針變量P指向雙向循環(huán)鏈表中的結(jié)點X，則刪除結(jié)點X需要執(zhí)行的語句序列為_（設(shè)結(jié)點中的兩個指針域分別為LLINK和RLINK）。33根據(jù)初始關(guān)鍵字序列19，22，01，38，10建立的二叉排序樹的高度為_。44深度為K的完全二叉樹中最少有_個結(jié)點。55設(shè)初始記錄關(guān)鍵字序列為K1，K2，KN，則用篩選法思想建堆必須從第_個元素開始進(jìn)行篩選。66設(shè)哈夫曼樹中共有99個結(jié)點，則該樹中有_個葉子結(jié)點；若采用二叉鏈表作為存儲結(jié)構(gòu)，則該樹中有_個空指針域。77設(shè)有一個順序循環(huán)隊列中有M個存儲單元，則該循環(huán)隊列中最多能夠存儲_個隊列元素；當(dāng)前實際存儲_個隊列元素（設(shè)頭指針F指向當(dāng)前隊頭元素的前一個位置，尾指針指向當(dāng)前隊尾元素的位置）。88設(shè)順序線性表中有N個數(shù)據(jù)元素，則第I個位置上插入一個數(shù)據(jù)元素需要移動表中_個數(shù)據(jù)元素；刪除第I個位置上的數(shù)據(jù)元素需要移動表中_個元素。99設(shè)一組初始記錄關(guān)鍵字序列為20，18，22，16，30，19，則以20為中軸的一趟快速排序結(jié)果為_。1010設(shè)一組初始記錄關(guān)鍵字序列為20，18，22，16，30，19，則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為_。1111設(shè)某無向圖G中有N個頂點，用鄰接矩陣A作為該圖的存儲結(jié)構(gòu)，則頂點I和頂點J互為鄰接點的條件是_。1212設(shè)無向圖對應(yīng)的鄰接矩陣為A，則A中第I上非0元素的個數(shù)_第I列上非0元素的個數(shù)（填等于，大于或小于）。1313設(shè)前序遍歷某二叉樹的序列為ABCD，中序遍歷該二叉樹的序列為BADC，則后序遍歷該二叉樹的序列為_。1414設(shè)散列函數(shù)HKKMODP，解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表HASHTALBE中查找關(guān)鍵字值等于K的結(jié)點，成功時返回指向關(guān)鍵字的指針，不成功時返回標(biāo)志0。TYPEDEFSTRUCTNODEINTKEYSTRUCTNODENEXTLKLISTVOIDCREATELKHASHLKLISTHASHTABLEINTI,KLKLISTSFORI0IKEYAIKAIPSNEXTHASHTABLEK_三、算法設(shè)計題28分11設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素大寫字母、數(shù)字和其它字符，要求利用原單鏈表中結(jié)點空間設(shè)計出三個單鏈表的算法，使每個單鏈表只包含同類字符。22設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點左右子樹的算法。33在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉排序樹。數(shù)據(jù)結(jié)構(gòu)試卷（四）參考答案一、選擇題1C2D3D4B5C6A7B8A9C10A二、填空題11ON2，ONLOG2N22PLLINKRLINKPRLINKPRLINKLLINKPRLINK333442K155N/26650，5177M1，RFMM88N1I，NI9919，18，16，20，30，22101016，18，19，20，32，221111AIJ11212等于1313BDCA1414HASHTABLEI0，HASHTABLEKS三、算法設(shè)計題11設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素大寫字母、數(shù)字和其它字符，要求利用原單鏈表中結(jié)點空間設(shè)計出三個單鏈表的算法，使每個單鏈表只包含同類字符。TYPEDEFCHARDATATYPETYPEDEFSTRUCTNODEDATATYPEDATASTRUCTNODENEXTLKLISTVOIDSPLITLKLISTHEAD,LKLISTHA0,HB0,HC0FORPHEADP0PHEADHEADPNEXTPNEXT0IFPDATAAHAPELSEIFPDATA0HBPELSEPNEXTHCHCP22設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上交換二叉樹中所有結(jié)點左右子樹的算法。TYPEDEFSTRUCTNODEINTDATASTRUCTNODELCHILD,RCHILDBITREEVOIDSWAPBITREEBITREEBTBITREEPIFBT0RETURNSWAPBITREEBTLCHILDSWAPBITREEBTRCHILDPBTLCHILDBTLCHILDBTRCHILDBTRCHILDP33在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉排序樹。DEFINEN10TYPEDEFSTRUCTNODEINTKEYSTRUCTNODELCHILD,RCHILDBITREEVOIDBSTINSERTBITREEBTKEYKEYBTLCHILDBTRCHILD0ELSEIFBTKEYKEYBSTINSERTBTLCHILD,KEYELSEBSTINSERTBTRCHILD,KEYVOIDCREATEBSTTREEBITREEFORI1IRJ1TEMPRJ1_RJTEMPEXCHANGE1IFEXCHANGE0RETURN；1010下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。STRUCTRECORDINTKEYINTOTHERSINTBISEARCHSTRUCTRECORDR,INTKINTLOW0,MID,HIGHN1WHILELOWK三、應(yīng)用題11DEBCA22E1,5,5,2,5,3,3,4,W1033ASL112234/717/744ASL17/6，ASL24/3四、算法設(shè)計題11設(shè)計判斷兩個二叉樹是否相同的算法。TYPEDEFSTRUCTNODEDATATYPEDATASTRUCTNODELCHILD,RCHILDBITREEINTJUDGEBITREEBITREEBT1,BITREEBT2IFBT10ELSEIFBT10|BT20|BT1DATABT2DATARETURN0ELSERETURNJUDGEBITREEBT1LCHILD,BT2LCHILDJUDGEBITREEBT1RCHILD,BT2RCHILD22設(shè)計兩個有序單鏈表的合并排序算法。VOIDMERGELKLISTLKLISTHA,LKLISTHB,LKLISTWHILEHA0ELSESNEXTHASHAHAHANEXTELSEIFS0HCSHBELSESNEXTHBSHBHBHBNEXTIFHA0SNEXTHBELSESNEXTHA數(shù)據(jù)結(jié)構(gòu)試卷（六）一、選擇題30分1設(shè)一組權(quán)值集合W2，3，4，5，6，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和為（）。A20B30C40D452執(zhí)行一趟快速排序能夠得到的序列是（）。A41，12，34，45，275572，63B45，34，12，415572，63，27C6