數(shù)據(jù)結構（本）期末綜合練習202３年12月期末綜合練習一一、單項選擇題1．數(shù)據(jù)的物理結構(）。A．與數(shù)據(jù)的邏輯結構無關Ｂ.僅僅涉及數(shù)據(jù)元素的表達C．只涉及數(shù)據(jù)元素間關系的表達D．涉及數(shù)據(jù)元素的表達和關系的表達2.深度為5的完全二叉樹共有２０個結點,則第5層上有()個結點(根所在結點為第一層)。A.３B．8C.5D3.從ｎ個數(shù)中選取最大元素（）。Ａ．基本操作是數(shù)據(jù)元素間的互換B.算法的時間復雜度是O(ｎ2)C.算法的時間復雜度是O(n）D．需要進行(n+1)次數(shù)據(jù)元素間的比較4．已知一個圖的邊數(shù)為m，則該圖的所有頂點的度數(shù)之和為(）。A．2mB．mC.2ｍ+１D.m/25．線性表的順序結構中,（)。A.邏輯上相鄰的元素在物理位置上不一定相鄰Ｂ．數(shù)據(jù)元素是不能隨機訪問的Ｃ.邏輯上相鄰的元素在物理位置上也相鄰D．進行數(shù)據(jù)元素的插入、刪除效率較高6.數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的()結構。A.物理B.存儲C.邏輯與物理Ｄ.邏輯７．帶頭結點的單向鏈表為空的判斷條件是()（設頭指針為hｅaｄ）。A.ｈead==NULＬB．head->nexｔ==NULＬC.head－＞neｘt=＝headD.heaｄ!=ＮULL8.鏈表所具有的特點是(）。Ａ．可以隨機訪問任一結點B.占用連續(xù)的存儲空間C.插入刪除不需要移動元素結點D.可以通過下標對鏈表進行直接訪問9．線性結構中數(shù)據(jù)元素的位置之間存在(）的關系。A.一對一B.一對多C.多對多Ｄ．每一個元素都有一個直接前驅(qū)和一個直接后繼10.線性表只要以()方式存儲就能進行折半查找。A．鏈接Ｂ．順序Ｃ．關鍵字有序的順序D．二叉樹11.設順序存儲的線性表長度為n，要刪除第i個元素,按課本的算法,當i＝()時,移動元素的次數(shù)為3A.3Ｂ.n/2C．n-3D12.散列查找的原理是（）。A．在待查記錄的關鍵字值與該記錄的存儲位置之間建立擬定的相應關系B．按待查記錄的關鍵字有序的順序方式存儲C．按關鍵字值的比較進行查找Ｄ.基于二分查找的方法1３.以下說法不對的的是（)。Ａ.棧的特點是后進先出B.隊列的特點是先進先出C．棧的刪除操作在棧底進行，插入操作在棧頂進行Ｄ．隊列的插入操作在隊尾進行,刪除操作在隊頭進行１4.對ｎ個元素進行冒泡排序若某趟冒泡中只進行了（)次元素間的互換,則表白序列已經(jīng)排好序。A.１B.2Ｃ.0D15．一個棧的進棧序列是a,ｂ,c，ｄ,則棧的不也許的出棧序列是（）。A．a(chǎn)dbcB．bcadＣ．cbaｄＤ.ｄcba16.排序過程中,每一趟從無序子表中將一個待排序的記錄按其關鍵字的大小放置到已經(jīng)排好序的子序列的適當位置，直到所有排好序為止，該排序算法是()。A．直接插入排序Ｂ.快速排序C．冒泡排序Ｄ．選擇排序1７.設top是一個鏈棧的棧頂指針,棧中每個結點由一個數(shù)據(jù)域ｄata和指針域ｎｅｘt組成,設用x接受棧頂元素，則出棧操作為()。A．x=top->ｄata;top=ｔｏp->neｘt;B.tｏp=tｏp－>nexｔ；ｘ=toｐ－>data；C．ｘ＝top->nｅxt;ｔop=top－＞data;D．toｐ->next=toｐ；x＝top－＞ｄata;18．在對一組元素（64,48，106,３3,25,8２，7０，55，９3)進行直接插入排序時，當進行到要把第７個元素７０插入到已經(jīng)排好序的子表時，為找到插入位置,需進行（)次元素間的比較(指由小到大排序）。A．6Ｂ．２C.３D１9.設有一個帶頭結點的鏈隊列,隊列中每個結點由一個數(shù)據(jù)域data和指針域nｅｘｔ組成，ｆroｎt和rear分別為鏈隊列的頭指針和尾指針,要執(zhí)行出隊操作,用x保存出隊元素的值,p為指向結點類型的指針，可執(zhí)行如下操作:p=frｏnｔ->next;x＝p－>daｔa;然后執(zhí)行(）。A.fronｔ=p->next;B．front->ｎext=p->next;Ｃ.ｆｒont=p；D．fｒont-＞nｅxt=p;20.采用順序查找法對長度為n的線性表進行查找(不采用表尾設監(jiān)視哨的方法),最壞的情況下要進行（)次元素間的比較。A．n+２B．ｎC．n－1Ｄ．ｎ/221．以下說法對的的是（）。A．隊列是后進先出Ｂ.棧的特點是后進后出C．棧的刪除和插入操作都只能在棧頂進行D.隊列的刪除和插入操作都只能在隊頭進行abecabecdfgＡ．a(chǎn)cebｄｇｆＢ.abecdｇfC．a(chǎn)cfedgbD.ａｂecfdｇ圖１23．空串的長度為(）。A．０B．１C.２24．元素2，4，6,8按順序依次進棧，則該棧的不也許輸出序列是（)（進棧出棧可以交替進行)。A.８，6，4,2B．2,4，6，8Ｃ．4,2,8，6Ｄ．８,6,２，425.串函數(shù)ＳtrCmp(“abA”,”aba”)的值為()。A．1B.0C．“ａbAaba”D２６．排序方法中,從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法,稱為（）排序。Ａ.歸并Ｂ.插入C.選擇D．快速２7．設有一個10階的對稱矩陣Ａ，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中。(矩陣A的第一個元素為a1,1,數(shù)組ｂ的下標從1開始),則矩陣元素a5,３相應一維數(shù)組b的數(shù)組元素是（)。A．ｂ[１8]Ｂ．b[8]Ｃ．b[13]Ｄ.b[1０]2８.一棵哈夫曼樹總共有２3個結點,該樹共有(）個葉結點（終端結點)A．10B.13C.1129．已知如圖２所示的一個圖,若從頂點a出發(fā)，按深度優(yōu)先搜索法進行遍歷，則也許得到的一種頂點序列為（)。A.ａbecｄfB.ａcfebdC.aeｂcfdD．a(chǎn)eｄfcbbbdfeca圖230．隊列的插入操作在()進行。A．隊頭B.隊尾C.隊頭或隊尾Ｄ.在任意指定位置二、填空題１.通常數(shù)據(jù)的邏輯結構涉及集合、線性、____、__＿＿四種類型。2．一棵二叉樹沒有單分支結點，有６個葉結點，則該樹總共有_＿___＿__個結點。3.通常可以把某城市中各公交站點間的線路圖抽象成______＿＿結構。４.設一棵完全二叉樹，其最高層上最右邊的葉結點的編號為奇數(shù),該葉節(jié)點的雙親結點的編號為１0,該完全二叉樹一共有＿＿______個結點。5.設有一個單向鏈表,結點的指針域為ｎext，頭指針為ｈead，p指向尾結點，為了使該單向鏈表改為單向循環(huán)鏈表,可用語句___＿____。6.按照二叉樹的遞歸定義,對二叉樹遍歷的常用算法有__＿_、____、___＿三種。7.循環(huán)隊列的隊頭指針為ｆ,隊尾指針為r,當＿______＿時表白隊列已空。8.數(shù)據(jù)結構中的數(shù)據(jù)元素存在一對多的關系稱為__＿___＿_結構。９.設有一個鏈棧,棧頂指針為hs,現(xiàn)有一個s所指向的結點要入棧,則可執(zhí)行操作___＿____和hs=ｓ;10.把數(shù)據(jù)存儲到計算機中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結構稱為___＿____結構。1１.在一個鏈隊中，f和r分別為隊頭和隊尾指針,隊結點的指針域為next,則插入一個ｓ所指結點的操作為________；r=s；12.結構中的數(shù)據(jù)元素存在一對一的關系稱為_＿__＿_＿_結構。13.串的兩種最基本的存儲方式分別是＿______和__＿＿＿＿＿＿。14.如圖3所示的二叉樹，其后序遍歷序列為。eefgibachd圖31５.一棵二叉樹中順序編號為ｉ的結點，若它存在左、右孩子，則左、右孩子編號分別為＿__＿＿__＿、＿_____＿_。１6.n個元素進行冒泡法排序,通常需要進行____＿___趟冒泡。1７，兩個串相等的充足必要條件是。18.二叉樹為二叉排序的充足必要條件是其任一結點的值均大于其左孩子的值、小于其右孩子的值。這種說法是______＿___的。(回答對的或不對的）１9．一棵二叉樹葉結點(終端結點)數(shù)為5,單分支結點數(shù)為2,該樹共有＿_____個結點。2０．圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是______的。（回答對的或不對的)21.根據(jù)搜索方法的不同,圖的遍歷有_＿__、__＿＿兩種方法。2２.根據(jù)搜索方法的不同,圖的遍歷有_＿__、____兩種方法2３．一個有序表{３,4,10,１4，34,４3，46，64,75,78,90，96，130}用折半查找法查找值為90的結點，經(jīng)_＿_____＿次比較后查找成功。２4.按某關鍵字對記錄序列排序，若關鍵字的記錄在排序前和排序后仍保持它們的前后關系,則排序算法是穩(wěn)定的,否則是不穩(wěn)定的。三、綜合題１.(1）已知某二叉樹的后序遍歷序列是debｃa，中序遍歷序列是dbeaｃ，試畫出該二叉樹(2)若上述二叉樹的各個結點的字符分別代表不同的整數(shù)(其中沒有相等的),并恰好使該樹成為一棵二叉排序樹，試給出ａ、b、c、d、e的大小關系。（３)給出該樹的前序遍歷序列2．（1)運用篩選過程把序列{42，82,６7，102,16，３２,5７，52}建成堆（小根堆)，畫出該堆（不規(guī)定中間過程)。(2）寫出對上述堆相應的完全二叉樹進行中序遍歷得到的序列。３.（1）一組記錄的關鍵字序列為{4５,40，65,４３，3５，9５}，寫出運用快速排序的方法,以第一個記錄為基準得到的一趟劃分的結果（規(guī)定給出一趟劃分中每次掃描和互換的結果)（2)對序列{４5，40,65，4３,３5,9５}運用直接插入排序,寫出逐次插入過程（從第一個元素一直到第六個元素)。4.設查找表為(１6，15,20,５3,64,7）,（１）用冒泡法對該表進行排序(規(guī)定升序排列）,規(guī)定寫出每一趟的排序過程。(2)在排序后的有序表的基礎上,畫出對其進行折半查找所相應的鑒定樹.(規(guī)定以數(shù)據(jù)元素作為樹結點)（3)求在等概率條件下,對上述有序表成功查找的平均查找長度.5．(1)設有查找表{5，14,2,6,１8,7,４,１6，3},依次取表中數(shù)據(jù),構造一棵二叉排序樹．（2)說明如何通過序列的二叉排序樹得到相應序列的排序結果。6．(１）設有一個整數(shù)序列｛50，38，16，82，１10,1３,64},依次取出序列中的數(shù),構造一棵二叉排序樹（2)運用上述二叉排序樹,為了查找11０,經(jīng)多少次元素間的比較能成功查到，為了查找1５，經(jīng)多少次元素間的比較可知道查找失敗四、程序填空題1.以下函數(shù)在a［0]到a[n-1]中，用折半查找算法查找關鍵字等于ｋ的記錄，查找成功返回該記錄的下標,失敗時返回-1，完畢程序中的空格typedｅfstruct{intｋeｙ;……}ＮOＤＥ;intBinarｙ_Seａrch(ＮODEa[],intn,iｎtｋ){ｉntlow，mid,high;ｌow=０;ｈigh=n-１;ｗhilｅ（___(１）_＿___){mid＝(loｗ＋hiｇh)/2;iｆ（a[mid].key＝＝ｋ）ｒeturn＿_（２)____＿_; ｅlsｅｉf(___（3)_____)low=ｍid+１; elsｅ__(４)______;?}__＿（5)__＿__;?}2．以下函數(shù)為鏈隊列的入隊操作，x為要入隊的結點的數(shù)據(jù)域的值,front、rear分別是鏈隊列的隊頭、隊尾指針ｓtｒuctnodｅ{ＥlemTyｐｅdatａ;stｒucｔnode*next;};structｎｏde*froｎt，*ｒｅar；vｏｉdInＱｕeｕe(EleｍTｙpeｘ){stｒuctnｏde*p;ｐ=(ｓｔruｃtnodｅ*）＿＿_（１)__＿＿_;p->daｔａ=ｘ；p->nexｔ＝NUＬL;__＿(2)_＿__＿;rｅaｒ＝_＿＿(3）___＿_；}３．以下函數(shù)為鏈棧的進棧操作,x是要進棧的結點的數(shù)據(jù)域，toｐ為棧頂指針strｕctnode｛ElemTｙpｅdaｔa;structnode*neｘt;};structnode*tｏp;voiｄPush(ElｅmTypex){sｔｒuctｎoｄe*p；ｐ=(stｒuｃtnode＊)ｍalｌoc（___（1)_____)；p->ｄaｔa=ｘ;_＿_(2)_____;_＿＿__(3)__＿;}4．以下函數(shù)在heａd為頭指針的具有頭結點的單向鏈表中刪除第i個結點，ｓtruｃtnoｄｅ{ｉｎtｄata;ｓｔrｕｃｔｎｏdｅ*next;};typedeｆstructnodｅNODEintdeleｔe（ＮOＤE＊head，inti){NODＥ*p,*q;iｎtｊ;q=heａd;j＝０；whｉｌe((q!＝NULL）&&(__＿(１)__＿__)）｛___(2)＿__＿_;j+＋；}if(q==ＮＵLL）reｔurｎ（0）;ｐ=__＿(3)__＿__;___(4)＿__＿_＝p－>ｎｅxｔ;freｅ(＿_＿(５)__＿_＿);rｅtｕｒn（1);}答案一、單項選擇題1．D２．C3．Ｃ4.A５.C6．D7.B8.C9．A１0．C11.C1２．Ａ1３.C14.Ｃ15.Ａ16.A１7.Ａ18.Ｃ19.B20.Ｂ21.Ｄ22.Ｂ２3.Ａ24.Ｄ25.D２６．C２7.C28.D２9．D3０．Ｂ二、填空題1．樹形;圖狀2.11３．圖狀4．215.ｐ->nexｔ=head；6.先序;中序;后序7.r＝f8.樹形9.ｓ－>ｎexｔ=hs;10．物理（存儲）１1.r->ｎexｔ＝s12.線性1３．順序存儲鏈式存儲14．gdｂeihfcａ１５．2ｉ和２i+1１6．n-１17．串長度相等且相應位置的字符相等１8.不對的19．1１20.對的21.深度優(yōu)先搜索遍歷廣度優(yōu)先搜索遍歷22．深度優(yōu)先搜索遍歷廣度優(yōu)先搜索遍歷2３．４24．相等三、綜合應用題abced1abced圖4(２)d<b＜e＜ａ<c(３）abdeｃ2．（1）1616423252576782102圖5（2）１02，52,42，82，16，６７,32，573．(1)4５406543３59５3540654３359535406５43６595３５40434３6595３5404３４565９５(2）40４5６543３5954０４3456535953５404３４５65９54．（1)原序列1615205364７1516205３76４15162０75３6４15１67２０5364１57１620536471５16２05３6４715715206416535圖６(3)平均查找長度=(1*1＋２*2+３*3）/6=14/65.（1)22461673185145圖７（2)中序遍歷50503882131106416圖８（2)三次；四次四、程序填空題１.(1)lｏw<=hiｇh(2）ｍid（3)a[miｄ]．key<k;(4)high=mid-1（５)retｕrn－1;2．(１）ｍalloc(siｚeoｆ(strｕctnoｄe）)(2)rear－>nexｔ=p(3）p3.（1）sizeof（sｔrｕctnode)(２)ｐ->ｎext＝top（3）ｔop=p4.(1)j<i－1（2)q=ｑ->nｅxt(3）q->next(4）q－>ｎｅｘｔ(5）p期末綜合練習二一、單項選擇題1．同一種邏輯結構()。A.只能有唯一的存儲結構Ｂ.可以有不同的存儲結構Ｃ．只能表達某一種數(shù)據(jù)元素之間的關系D.以上三種說法均不對的2．在C語言中，順序存儲長度為３的字符串，需要占用（)個字節(jié)。Ａ.4B.3C3．鏈表所具有的特點是（)。Ａ.可以隨機訪問任一結點B.占用連續(xù)的存儲空間C.插入刪除元素的操作不需要移動元素結點Ｄ．可以通過下標對鏈表進行直接訪問4．串函數(shù)StrＣaｔ（a，b)的功能是進行串（)。A．比較B．復制C．賦值D.連接5.數(shù)據(jù)的物理結構（）。A.與數(shù)據(jù)的邏輯結構無關B.僅僅涉及數(shù)據(jù)元素的表達C．只涉及數(shù)據(jù)元素間關系的表達Ｄ.涉及數(shù)據(jù)元素的表達和關系的表達6.一棵有n個結點采用鏈式存儲的二叉樹中，共有（)個指針域為空。A．n＋1B．nＣ．n－1D.n-27.線性結構中數(shù)據(jù)元素的位置之間存在()的關系。A．一對一B．一對多C.多對多Ｄ．每一個元素都有一個直接前驅(qū)和一個直接后繼8．設一棵哈夫曼樹共有ｎ個非葉結點，則該樹有(）個葉結點。Ａ．ｎB.n+1C9.以下表中可以隨機訪問的是（)。A．單向鏈表B.雙向鏈表Ｃ.單向循環(huán)鏈表D．順序表１0.從一個棧頂指針為top的鏈棧中刪除一個結點時，用變量x保存被刪結點的值，則執(zhí)行（)。A.x＝top-＞data;toｐ=topｎｅxt;B．x＝top->datａ;C．ｔop=top->neｘt;x＝toｐ->ｄaｔa;D．ｔop=tｏp－>ｎext;x=dａt(yī)a;1１．算法的時間復雜度與（）有關。A.所使用的計算機B.與計算機的操作系統(tǒng)C．與算法自身D.與數(shù)據(jù)結構１２.一棵完全二叉樹共有5層,且第5層上有六個結點，該樹共有（）個結點。A．３0Ｂ．20C13.設有一個長度為ｎ的順序表，要刪除第ｉ個元素需移動元素的個數(shù)為()。A.ｎ-i＋１B．ｎ-ｉC．n-i-1Ｄ.i14．在一個無向圖中，所有頂點的度數(shù)之和等于邊數(shù)的(）倍。A.3B.2.5C１５.在一個單鏈表中，ｐ、q分別指向表中兩個相鄰的結點，且q所指結點是p所指結點的直接后繼，現(xiàn)要刪除ｑ所指結點，可用的語句是()。A．p＝q－>nextＢ．p->nexｔ=qＣ．ｐ->ｎext=ｑnｅｘtＤ.q->ｎexｔ＝NULL１6.已知如圖1所示的一個圖,若從頂點V１出發(fā),按深度優(yōu)先搜索法進行遍歷,則也許得到的一種頂點序列為（)。A．Ｖ１Ｖ2V4V８V5V3V6V7B．V1Ｖ2V4V５Ｖ８V３Ｖ6Ｖ７C.V1Ｖ2V4V8V３Ｖ5V6V7D．V1V3Ｖ6V7V2V4V5V８V6V6V7V1V2V3V8V4V5圖１17．從一個棧頂指針為top的鏈棧中刪除一個結點時，用變量x保存被刪結點的值,則執(zhí)行(）。A.x=top-＞ｄatａ;ｔop=ｔｏp－＞ｎext；B.ｘ=tｏp->datａ；C．tｏp=ｔop－＞next;ｘ＝top－>datａ；Ｄ．top=top-＞ｎext;x=ｄata；18．已知如圖2所示的一個圖，若從頂點a出發(fā)，按廣度優(yōu)先搜索法進行遍歷，則也許得到的一種頂點序列為（)。A.ａｂcedfB．a(chǎn)bcefdC.aebｃｆdD.acfdｅbbdbdfeca圖219.在一個鏈隊中，假設ｆ和ｒ分別為隊頭和隊尾指針,則刪除一個結點的運算為(）。A．r=ｆ－>nｅxt;B.ｒ＝r->next;C.f=ｆ->next;D.f=r－>ｎeｘt;20.對二叉排序樹進行（)遍歷，可以使遍歷所得到的序列是有序序列。Ａ．按層次B.后序C.中序D．前序21.一個棧的進棧序列是a,ｂ，c，ｄ,e，則棧的不也許輸出序列是()(進棧出棧可以交替進行）。A.dceabＢ.edcbaC.decbaＤ.abｃｄe22.在有序表｛2，4，7,14，34，43,47,64,75,８0，90,9７,１20}中,用折半查找法查找值8０時，經(jīng)（）次比較后查找成功。A．4B．2C23.有一個長度為10的有序表，按折半查找對該表進行查找,在等概率情況下查找成功的平均比較次數(shù)為()。A．26/1０B.29/102４．有一個長度為9的有序表,按折半查找對該表進行查找,在等概率情況下查找成功的平均比較次數(shù)為（）。Ａ．25／10B．25/9C２5.排序算法中，從未排序序列中依次取出元素與已排序序列（初始為空)中的元素進行比較（規(guī)定比較次數(shù)盡量少),然后將其放入已排序序列的對的位置的方法是（)。Ａ．冒泡B.直接插入C.折半插入D．選擇排序2６.排序算法中,從未排序序列中依次取出元素與已排序序列（初始為空)中的元素進行比較（規(guī)定比較次數(shù)盡量少），然后將其放入已排序序列的對的位置的方法是()。A.冒泡B.直接插入C．折半插入D．選擇排序27．設有一個10階的對稱矩陣Ａ,采用壓縮存儲的方式，將其下三角部分以行序為主存儲到一維數(shù)組B中（數(shù)組下標從１開始),則矩陣中元素Ａ8,5在一維數(shù)組B中的下標是(）。A.3３B.3２C．852８.一組記錄的關鍵字序列為（4６,79，56,38，４0,８４),運用快速排序,以第一個關鍵字為分割元素，通過一次劃分后結果為()。A.４0,38,46，７9，5６,84Ｂ．4０,３8，46,５6,7９，84C.40，３8，４６，８４，５６,79D．3８，40,46，56,７9，8429．在一個無向圖中,所有頂點的度數(shù)之和等于邊數(shù)的（）倍。Ａ．３B．2.５C3０.排序方法中，從尚未排序序列中挑選元素,并將其依次放入已排序序列（初始為空）的一端的方法,稱為（）排序。A．歸并B．插入Ｃ.快速D.選擇二、填空題1．棧和隊列的操作特點分別是＿___＿__和＿_______。2．在二叉樹的鏈式存儲結構中，通常每個結點中設立三個域,它們是______＿、、右指針。3.結構中的數(shù)據(jù)元素存在多對多的關系稱為＿______＿結構。４．一棵二叉樹中順序編號為i的結點,若它存在左、右孩子，則左、右孩子編號分別為＿_＿＿__、____＿___。5．根據(jù)數(shù)據(jù)元素間關系的不同特性,通常可分為集合、線性、、四類基本結構。6.串的兩種最基本的存儲方式是＿＿__＿___和＿_______。7．規(guī)定在n個數(shù)據(jù)元素中找其中值最大的元素，設基本操作為元素間的比較。則比較的次數(shù)和算法的時間復雜度分別為＿＿__＿＿__和__＿＿＿＿__。8．一棵有2n-1個結點的二叉樹，其每一個非葉結點的度數(shù)都為２，則該樹共有_______個葉結點。9.在一個單向鏈表中p所指結點之后插入一個ｓ所指向的結點時，應執(zhí)行＿＿＿＿____和p-＞next=s;的操作。１0．對于一棵具有n個結點的二叉樹，其相應的鏈式存儲結構中共有____＿___個指針域為空。1１．在二叉樹的鏈式存儲結構中，通常每個結點中設立三個域，它們是值域、。1２.＿＿___＿__遍歷二叉排序樹可得到一個有序序列。1３．一棵二叉樹中順序編號為ｉ的結點，若它存在左、右孩子，則左、右孩子編號分別為________、_＿_____＿。１4．如圖３所示的二叉樹，其后序遍歷序列為。eefgibachd圖315．向一個棧頂指針為h的鏈棧中插入一個s所指結點時，可執(zhí)行s-＞next＝h;和____＿___。16.如圖4所示的二叉樹，其先序遍歷序列為_________。ggfabdec圖4１7．在一個鏈隊中,設f和r分別為隊頭和隊尾指針,則插入s所指結點的操作為_＿_＿____和r=ｓ;(結點的指針域為ｎext)18.圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是＿＿__＿_的。(回答對的或不對的）1９．設有一棵深度為4的完全二叉樹，第四層上有5個結點，該樹共有＿_______＿個結點。(根所在結點為第１層)２0．二叉樹為二叉排序的充足必要條件是其任一結點的值均大于其左孩子的值、小于其右孩子的值。這種說法是______＿＿__的。（回答對的或不對的)21.對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素相應的三元組涉及該元素的＿_＿__＿_、_______和___＿__＿三項信息。2２.對記錄序列排序是指按記錄的某個關鍵字排序，記錄序列按＿＿_＿____＿排序結果是唯一的。23．在對一組記錄(55,39，97,2２，１6,73，6５,47,8８）進行直接插入排序時，當把第7個記錄65插入到有序表時，為尋找插入位置需比較_______＿＿次。24．按某關鍵字對記錄序列排序,若在排序前和排序后仍保持它們的前后關系，則排序算法是穩(wěn)定的,否則是不穩(wěn)定的。三、綜合題1.（1)以2，3,４,7,８,9作為葉結點的權，構造一棵哈夫曼樹(規(guī)定每個結點的左子樹根結點的權小于等于右子樹根結點的權)，給出相應權重值葉結點的哈夫曼編碼。(2)一棵哈夫曼樹有ｎ個葉結點,它一共有多少個結點?簡述理由？2．設查找表為（16,１5，20,53,6４,7）,(1)用冒泡法對該表進行排序(規(guī)定升序排列),寫出每一趟的排序過程，通常對n個元素進行冒泡排序要進行多少趟冒泡？第j趟要進行多少次元素間的比較？(2)在排序后的有序表的基礎上，畫出對其進行折半查找所相應的鑒定樹.（規(guī)定以數(shù)據(jù)元素作為樹結點)3.一組記錄的關鍵字序列為(46，79，56，3８，４0,8４）（1）運用快速排序的方法,給出以第一個記錄為基準得到的一次劃分結果(給出逐次互換元素的過程，規(guī)定以升序排列)（２)對上述序列用堆排序的方法建立大根堆,規(guī)定以二叉樹逐次描述建堆過程。4.（1)設有查找表｛５,1４,2,6,18,7，４,16,３｝，依次取表中數(shù)據(jù),構造一棵二叉排序樹。(2）說明如何由序列的二叉排序樹得到相應序列的排序結果，對上述二叉排序給出中序遍歷的結果。5.設查找表為（５0，６0,7５,85,96,98,１０５,110,120，130）(1)說出進行折半查找成功查找到元素１20需要進行多少次元素間的比較?(2)為了折半查找元素95,通過多少次元素間的比較才干擬定不能查到?（３）畫出對上述有序表進行折半查找所相應的鑒定樹(規(guī)定以數(shù)據(jù)元素作為樹結點)６.(1）對給定權值２，1,3,３，4，5，構造哈夫曼樹。(2)同樣用上述權值構造另一棵哈夫曼樹,使兩棵哈夫曼樹有不同的高度，并分別求兩棵樹的帶權途徑長度。四、程序填空題1.以下是用尾插法建立帶頭結點且有n個結點的單向鏈表的程序，結點中的數(shù)據(jù)域從前向后依次為1,2,3,……,ｎ,完畢程序中空格部分。NODE*create（n)｛ＮＯＤＥ*heaｄ,＊p,*q;inti；p＝（ＮODE*)ｍalloｃ(sｉzeof（NＯDE));heａd=（1)；（2)；ｐnexｔ=NULＬ;/＊建立頭結點*／for(i=1;i<＝n；i++)｛p=（3);pdata＝ｉ；pnext=NULL;qneｘt＝(4);（5）;}retuｒn(head）;}2．設線性表為(6，１0，16,4)，以下程序用說明結構變量的方法建立單向鏈表,并輸出鏈表中各結點中的數(shù)據(jù)。#deｆiｎeNＵＬL0voｉdmain(){ＮODEa,b，c,d,*head,*p；a.dａt(yī)ａ＝６;ｂ．data=10；c.ｄatａ=16;ｄ.ｄata=4;/*ｄ是尾結點＊/ｈｅad=(1）；a.next=&b;b.next=&ｃ；c．next=&d；(2）;/*以上結束建表過程＊/ｐ=heaｄ；／*ｐ為工作指針,準備輸出鏈表＊／do{printf(“%d\n”，(3)）;（４）；}while((5))；｝3．以下程序是中序遍歷二叉樹的遞歸算法的程序,完畢程序中空格部分（樹結構中左、右指針域分別為lｅft和right，數(shù)據(jù)域daｔa為字符型，BT指向根結點)。voidIｎｏrdｅr(strucｔBTreeNｏde＊BT)｛if(ＢT!=NＵLL)｛(１）;(2）;（３);｝}4．以下程序是后序遍歷二叉樹的遞歸算法的程序，完畢程序中空格部分(樹結構中,左、右指針域分別為lefｔ和riｇht，數(shù)據(jù)域daｔa為字符型，ＢＴ指向根結點)。ｖoidＰostordeｒ(struｃｔBTreeNode*ＢT){if（BT!=ＮUＬL){(１);（2）;（３)