一、一、單選題（每小題2分，共8分）1、1、在一個(gè)長度為N的順序線性表中順序查找值為X的元素時(shí)，查找成功時(shí)的平均查找長度（即X與元素的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等）為。ANBN/2CN1/2DN1/22、2、在一個(gè)單鏈表中,若Q所指結(jié)點(diǎn)是P所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若在Q與P之間插入一個(gè)S所指的結(jié)點(diǎn),則執(zhí)行。ASLINKPLINKPLINKSBPLINKSSLINKQCPLINKSLINKSLINKPDQLINKSSLINKP3、3、棧的插入和刪除操作在（）進(jìn)行。A棧頂B棧底C任意位置D指定位置4、4、由權(quán)值分別為11，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）A24B71C48D53二、二、填空題（每空1分，共32分）1、1、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為_、_、_和_四種。2、2、一種抽象數(shù)據(jù)類型包括_和_兩個(gè)部分。3、3、在下面的數(shù)組A中鏈接存儲(chǔ)著一個(gè)線性表，表頭指針為AONEXT，則該線性表為_。A012345678DATANEXT4、4、在以HL為表頭指針的帶表頭附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件分別為_和_。5、5、用具有N個(gè)元素的一維數(shù)組存儲(chǔ)一個(gè)循環(huán)隊(duì)列，則其隊(duì)首指針總是指向隊(duì)首元素的_，該循環(huán)隊(duì)列的最大長度為_。6、6、當(dāng)堆棧采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，棧頂元素的值可用表示；當(dāng)堆棧采用鏈接存儲(chǔ)結(jié)構(gòu)時(shí)，棧頂元素的值可用_表示。7、7、一棵高度為5的二叉樹中最少含有_個(gè)結(jié)點(diǎn)，最多含有_個(gè)結(jié)點(diǎn)；一棵高度為5的理想平衡樹中，最少含有_個(gè)結(jié)點(diǎn)，最多含有_個(gè)結(jié)點(diǎn)。8、8、在圖的鄰接表中，每個(gè)結(jié)點(diǎn)被稱為_，通常它包含三個(gè)域一是_；二是_；三是_。60564238742543762019、9、在一個(gè)索引文件的索引表中，每個(gè)索引項(xiàng)包含對(duì)應(yīng)記錄的_和_兩項(xiàng)數(shù)據(jù)。10、10、假定一棵樹的廣義表表示為A（B（C，D（E，F(xiàn)，G），H（I，J），則樹中所含的結(jié)點(diǎn)數(shù)為_個(gè)，樹的深度為_,樹的度為_,結(jié)點(diǎn)H的雙親結(jié)點(diǎn)為_,孩子結(jié)點(diǎn)為_。11、11、在堆排序的過程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為_,整個(gè)堆排序過程的時(shí)間復(fù)雜度為_。12、12、在對(duì)M階的B_樹插入元素的過程中，每向一個(gè)結(jié)點(diǎn)插入一個(gè)索引項(xiàng)（葉子結(jié)點(diǎn)中的索引項(xiàng)為關(guān)鍵字和空指針）后，若該結(jié)點(diǎn)的索引項(xiàng)數(shù)等于_個(gè)，則必須把它分裂為_個(gè)結(jié)點(diǎn)。三、三、運(yùn)算題（每小題6分，共24分）1、1、已知一組記錄的排序碼為（46，79，56，38，40，80,95，24），寫出對(duì)其進(jìn)行快速排序的每一次劃分結(jié)果。2、2、一個(gè)線性表為B（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為HT012，散列函數(shù)為H（KEY）KEY13并用線性探查法解決沖突，請(qǐng)畫出散列表，并計(jì)算等概率情況下查找成功的平均查找長度。3、3、已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECKFGHIJ，中序遍歷的結(jié)果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結(jié)果。4、4、已知一個(gè)圖的頂點(diǎn)集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)它用鄰接矩陣表示和鄰接表表示時(shí)，分別寫出從頂點(diǎn)V0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷等到的頂點(diǎn)序列。假定每個(gè)頂點(diǎn)鄰接表中的結(jié)點(diǎn)是按頂點(diǎn)序號(hào)從大到小的次序鏈接的。圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時(shí)鄰接表表示時(shí)四、四、閱讀算法，回答問題（每小題8分，共16分）1、假定從鍵盤上輸入一批整數(shù)，依次為7863453091341，請(qǐng)寫出輸出結(jié)果。INCLUDEINCLUDECONSSTINTSTACKMAXSIZE30TYPEDEFINTELEMTYPESTRUCTSTACKELEMTYPESTACKSTACKMAXSIZEINTTOPINCLUDE“STACKH”VOIDMAINSTACKAINITSTACKAINTXCINXWHILEX1PUSHA,XCINXWHILESTACKEMPTYACOUTVOIDBINTREEUNKNOWNBINTREENODETBINTREENODEPT,TEMPIFPNULLTEMPPLEFTCHILDPLEFTCHILDPRIGHTCHILDPRIGHTCHILDTEMPUNKNOWNPLEFTCHILDUNDNOWNPRIGHTCHILD該算法的功能是_五、五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容（10分）對(duì)順序存儲(chǔ)的有序表進(jìn)行二分查找的遞歸算法。INTBINSCHELEMTYPEA,INTLOW,INTHIGH,KEYTYPEKIFLOWHIGHINTMID1IFKAMIDKEYRETURNMIDELSEIFKAMIDKEYRETURN2ELSERETURN3ELSERETURN4六、六、編寫算法（10分）編寫算法，將一個(gè)結(jié)點(diǎn)類型為LNODE的單鏈表按逆序鏈接，即若原單鏈表中存儲(chǔ)元素的次序?yàn)锳1，AN1，AN，則逆序鏈接后變?yōu)?AN，AN1，A1。VOIDCONTRARYLNODEHSDATA75318邊結(jié)點(diǎn)、鄰接點(diǎn)域、權(quán)域、鏈域；9索引值域、開始位置域；1010、3、3、B、I和J；11O（LOG2N）、ONLOG2N12M、M1三、運(yùn)算題（每小題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)先序列鄰接矩陣表示