《數(shù)據(jù)結(jié)構(gòu)》-一3

一、一、單選題（每小題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、棧的插入和刪除操作在（）進行。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)單鏈表中，判斷鏈表為空的條件分別為_和_。5、5、用具有N個元素的一維數(shù)組存儲一個循環(huán)隊列，則其隊首指針總是指向隊首元素的_，該循環(huán)隊列的最大長度為_。6、6、當堆棧采用順序存儲結(jié)構(gòu)時，棧頂元素的值可用表示；當堆棧采用鏈接存儲結(jié)構(gòu)時，棧頂元素的值可用_表示。7、7、一棵高度為5的二叉樹中最少含有_個結(jié)點，最多含有_個結(jié)點；一棵高度為5的理想平衡樹中，最少含有_個結(jié)點，最多含有_個結(jié)點。8、8、在圖的鄰接表中，每個結(jié)點被稱為_，通常它包含三個域一是_；二是_；三是_。60564238742543762019、9、在一個索引文件的索引表中，每個索引項包含對應記錄的_和_兩項數(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é)點進行篩運算的時間復雜度為_,整個堆排序過程的時間復雜度為_。12、12、在對M階的B_樹插入元素的過程中，每向一個結(jié)點插入一個索引項（葉子結(jié)點中的索引項為關(guān)鍵字和空指針）后，若該結(jié)點的索引項數(shù)等于_個，則必須把它分裂為_個結(jié)點。三、三、運算題（每小題6分，共24分）1、1、已知一組記錄的排序碼為（46，79，56，38，40，80,95，24），寫出對其進行快速排序的每一次劃分結(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）當它用鄰接矩陣表示和鄰接表表示時，分別寫出從頂點V0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點序列和按廣度優(yōu)先搜索遍歷等到的頂點序列。假定每個頂點鄰接表中的結(jié)點是按頂點序號從大到小的次序鏈接的。圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時鄰接表表示時四、四、閱讀算法，回答問題（每小題8分，共16分）1、假定從鍵盤上輸入一批整數(shù)，依次為7863453091341，請寫出輸出結(jié)果。INCLUDEINCLUDECONSSTINTSTACKMAXSIZE30TYPEDEFINTELEMTYPESTRUCTSTACKELEMTYPESTACKSTACKMAXSIZEINTTOPINCLUDE“STACKH”VOIDMAINSTACKAINITSTACKAINTXCINXWHILEX1PUSHA,XCINXWHILESTACKEMPTYACOUTVOIDBINTREEUNKNOWNBINTREENODETBINTREENODEPT,TEMPIFPNULLTEMPPLEFTCHILDPLEFTCHILDPRIGHTCHILDPRIGHTCHILDTEMPUNKNOWNPLEFTCHILDUNDNOWNPRIGHTCHILD該算法的功能是_五、五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容（10分）對順序存儲的有序表進行二分查找的遞歸算法。INTBINSCHELEMTYPEA,INTLOW,INTHIGH,KEYTYPEKIFLOWHIGHINTMID1IFKAMIDKEYRETURNMIDELSEIFKAMIDKEYRETURN2ELSERETURN3ELSERETURN4六、六、編寫算法（10分）編寫算法，將一個結(jié)點類型為LNODE的單鏈表按逆序鏈接，即若原單鏈表中存儲元素的次序為A1，AN1，AN，則逆序鏈接后變?yōu)?AN，AN1，A1。VOIDCONTRARYLNODEHSDATA75318邊結(jié)點、鄰接點域、權(quán)域、鏈域；9索引值域、開始位置域；1010、3、3、B、I和J；11O（LOG2N）、ONLOG2N12M、M1三、運算題（每小題6分，共24分）1、劃分次序劃分結(jié)果第一次3824404656809579第二次2438404656809579第三次2438404656809579第四次2438404656809579第五次2438404656798095第六次24384046567980952、78150357452031233612查找成功的平均查找長度ASLSUCC14/10143、此二叉樹的后序遍歷結(jié)果是EDCBIHJGFA4、四、閱讀算法，回答問題（每小題8分，共16分）1、1、該算法的輸入結(jié)果是3491304563782、2、該算法的功能是交換二叉樹的左右子樹的遞歸算法。五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容（10分）1、1是（LOWHIGH）/22是BINSCHA,LOW,MID1,K3是BINSCHA,MID1,HIGH,K4是1；六、編寫算法（10分）根據(jù)編程情況，酌情給分。LNODEPHL圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示