2023年數(shù)據(jù)結(jié)構(gòu)(本)期末綜合練習(xí)(12月)資料

數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)202３年12月期末綜合練習(xí)一一、單項選擇題1．?dāng)?shù)據(jù)的物理結(jié)構(gòu)(）。A．與數(shù)據(jù)的邏輯結(jié)構(gòu)無關(guān)Ｂ.僅僅涉及數(shù)據(jù)元素的表達C．只涉及數(shù)據(jù)元素間關(guān)系的表達D．涉及數(shù)據(jù)元素的表達和關(guān)系的表達2.深度為5的完全二叉樹共有２０個結(jié)點,則第5層上有()個結(jié)點(根所在結(jié)點為第一層)。A.３B．8C.5D3.從ｎ個數(shù)中選取最大元素（）。Ａ．基本操作是數(shù)據(jù)元素間的互換B.算法的時間復(fù)雜度是O(ｎ2)C.算法的時間復(fù)雜度是O(n）D．需要進行(n+1)次數(shù)據(jù)元素間的比較4．已知一個圖的邊數(shù)為m，則該圖的所有頂點的度數(shù)之和為(）。A．2mB．mC.2ｍ+１D.m/25．線性表的順序結(jié)構(gòu)中,（)。A.邏輯上相鄰的元素在物理位置上不一定相鄰Ｂ．?dāng)?shù)據(jù)元素是不能隨機訪問的Ｃ.邏輯上相鄰的元素在物理位置上也相鄰D．進行數(shù)據(jù)元素的插入、刪除效率較高6.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的()結(jié)構(gòu)。A.物理B.存儲C.邏輯與物理Ｄ.邏輯７．帶頭結(jié)點的單向鏈表為空的判斷條件是()（設(shè)頭指針為hｅaｄ）。A.ｈead==NULＬB．head->nexｔ==NULＬC.head－＞neｘt=＝headD.heaｄ!=ＮULL8.鏈表所具有的特點是(）。Ａ．可以隨機訪問任一結(jié)點B.占用連續(xù)的存儲空間C.插入刪除不需要移動元素結(jié)點D.可以通過下標(biāo)對鏈表進行直接訪問9．線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在(）的關(guān)系。A.一對一B.一對多C.多對多Ｄ．每一個元素都有一個直接前驅(qū)和一個直接后繼10.線性表只要以()方式存儲就能進行折半查找。A．鏈接Ｂ．順序Ｃ．關(guān)鍵字有序的順序D．二叉樹11.設(shè)順序存儲的線性表長度為n，要刪除第i個元素,按課本的算法,當(dāng)i＝()時,移動元素的次數(shù)為3A.3Ｂ.n/2C．n-3D12.散列查找的原理是（）。A．在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立擬定的相應(yīng)關(guān)系B．按待查記錄的關(guān)鍵字有序的順序方式存儲C．按關(guān)鍵字值的比較進行查找Ｄ.基于二分查找的方法1３.以下說法不對的的是（)。Ａ.棧的特點是后進先出B.隊列的特點是先進先出C．棧的刪除操作在棧底進行，插入操作在棧頂進行Ｄ．隊列的插入操作在隊尾進行,刪除操作在隊頭進行１4.對ｎ個元素進行冒泡排序若某趟冒泡中只進行了（)次元素間的互換,則表白序列已經(jīng)排好序。A.１B.2Ｃ.0D15．一個棧的進棧序列是a,ｂ,c，ｄ,則棧的不也許的出棧序列是（）。A．a(chǎn)dbcB．bcadＣ．cbaｄＤ.ｄcba16.排序過程中,每一趟從無序子表中將一個待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到所有排好序為止，該排序算法是()。A．直接插入排序Ｂ.快速排序C．冒泡排序Ｄ．選擇排序1７.設(shè)top是一個鏈棧的棧頂指針,棧中每個結(jié)點由一個數(shù)據(jù)域ｄata和指針域ｎｅｘt組成,設(shè)用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)進行直接插入排序時，當(dāng)進行到要把第７個元素７０插入到已經(jīng)排好序的子表時，為找到插入位置,需進行（)次元素間的比較(指由小到大排序）。A．6Ｂ．２C.３D１9.設(shè)有一個帶頭結(jié)點的鏈隊列,隊列中每個結(jié)點由一個數(shù)據(jù)域data和指針域nｅｘｔ組成，ｆroｎt和rear分別為鏈隊列的頭指針和尾指針,要執(zhí)行出隊操作,用x保存出隊元素的值,p為指向結(jié)點類型的指針，可執(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的線性表進行查找(不采用表尾設(shè)監(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按順序依次進棧，則該棧的不也許輸出序列是（)（進棧出?？梢越惶孢M行)。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．設(shè)有一個10階的對稱矩陣Ａ，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中。(矩陣A的第一個元素為a1,1,數(shù)組ｂ的下標(biāo)從1開始),則矩陣元素a5,３相應(yīng)一維數(shù)組b的數(shù)組元素是（)。A．ｂ[１8]Ｂ．b[8]Ｃ．b[13]Ｄ.b[1０]2８.一棵哈夫曼樹總共有２3個結(jié)點,該樹共有(）個葉結(jié)點（終端結(jié)點)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ù)的邏輯結(jié)構(gòu)涉及集合、線性、____、__＿＿四種類型。2．一棵二叉樹沒有單分支結(jié)點，有６個葉結(jié)點，則該樹總共有_＿___＿__個結(jié)點。3.通?？梢园涯吵鞘兄懈鞴徽军c間的線路圖抽象成______＿＿結(jié)構(gòu)。４.設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點的編號為奇數(shù),該葉節(jié)點的雙親結(jié)點的編號為１0,該完全二叉樹一共有＿＿______個結(jié)點。5.設(shè)有一個單向鏈表,結(jié)點的指針域為ｎext，頭指針為ｈead，p指向尾結(jié)點，為了使該單向鏈表改為單向循環(huán)鏈表,可用語句___＿____。6.按照二叉樹的遞歸定義,對二叉樹遍歷的常用算法有__＿_、____、___＿三種。7.循環(huán)隊列的隊頭指針為ｆ,隊尾指針為r,當(dāng)＿______＿時表白隊列已空。8.數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為__＿___＿_結(jié)構(gòu)。９.設(shè)有一個鏈棧,棧頂指針為hs,現(xiàn)有一個s所指向的結(jié)點要入棧,則可執(zhí)行操作___＿____和hs=ｓ;10.把數(shù)據(jù)存儲到計算機中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為___＿____結(jié)構(gòu)。1１.在一個鏈隊中，f和r分別為隊頭和隊尾指針,隊結(jié)點的指針域為next,則插入一個ｓ所指結(jié)點的操作為________；r=s；12.結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系稱為_＿__＿_＿_結(jié)構(gòu)。13.串的兩種最基本的存儲方式分別是＿______和__＿＿＿＿＿＿。14.如圖3所示的二叉樹，其后序遍歷序列為。eefgibachd圖31５.一棵二叉樹中順序編號為ｉ的結(jié)點，若它存在左、右孩子，則左、右孩子編號分別為＿__＿＿__＿、＿_____＿_。１6.n個元素進行冒泡法排序,通常需要進行____＿___趟冒泡。1７，兩個串相等的充足必要條件是。18.二叉樹為二叉排序的充足必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。這種說法是______＿___的。(回答對的或不對的）１9．一棵二叉樹葉結(jié)點(終端結(jié)點)數(shù)為5,單分支結(jié)點數(shù)為2,該樹共有＿_____個結(jié)點。2０．圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是______的。（回答對的或不對的)21.根據(jù)搜索方法的不同,圖的遍歷有_＿__、__＿＿兩種方法。2２.根據(jù)搜索方法的不同,圖的遍歷有_＿__、____兩種方法2３．一個有序表{３,4,10,１4，34,４3，46，64,75,78,90，96，130}用折半查找法查找值為90的結(jié)點，經(jīng)_＿_____＿次比較后查找成功。２4.按某關(guān)鍵字對記錄序列排序，若關(guān)鍵字的記錄在排序前和排序后仍保持它們的前后關(guān)系,則排序算法是穩(wěn)定的,否則是不穩(wěn)定的。三、綜合題１.(1）已知某二叉樹的后序遍歷序列是debｃa，中序遍歷序列是dbeaｃ，試畫出該二叉樹(2)若上述二叉樹的各個結(jié)點的字符分別代表不同的整數(shù)(其中沒有相等的),并恰好使該樹成為一棵二叉排序樹，試給出ａ、b、c、d、e的大小關(guān)系。（３)給出該樹的前序遍歷序列2．（1)運用篩選過程把序列{42，82,６7，102,16，３２,5７，52}建成堆（小根堆)，畫出該堆（不規(guī)定中間過程)。(2）寫出對上述堆相應(yīng)的完全二叉樹進行中序遍歷得到的序列。３.（1）一組記錄的關(guān)鍵字序列為{4５,40，65,４３，3５，9５}，寫出運用快速排序的方法,以第一個記錄為基準(zhǔn)得到的一趟劃分的結(jié)果（規(guī)定給出一趟劃分中每次掃描和互換的結(jié)果)（2)對序列{４5，40,65，4３,３5,9５}運用直接插入排序,寫出逐次插入過程（從第一個元素一直到第六個元素)。4.設(shè)查找表為(１6，15,20,５3,64,7）,（１）用冒泡法對該表進行排序(規(guī)定升序排列）,規(guī)定寫出每一趟的排序過程。(2)在排序后的有序表的基礎(chǔ)上,畫出對其進行折半查找所相應(yīng)的鑒定樹.(規(guī)定以數(shù)據(jù)元素作為樹結(jié)點)（3)求在等概率條件下,對上述有序表成功查找的平均查找長度.5．(1)設(shè)有查找表{5，14,2,6,１8,7,４,１6，3},依次取表中數(shù)據(jù),構(gòu)造一棵二叉排序樹．（2)說明如何通過序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果。6．(１）設(shè)有一個整數(shù)序列｛50，38，16，82，１10,1３,64},依次取出序列中的數(shù),構(gòu)造一棵二叉排序樹（2)運用上述二叉排序樹,為了查找11０,經(jīng)多少次元素間的比較能成功查到，為了查找1５，經(jīng)多少次元素間的比較可知道查找失敗四、程序填空題1.以下函數(shù)在a［0]到a[n-1]中，用折半查找算法查找關(guān)鍵字等于ｋ的記錄，查找成功返回該記錄的下標(biāo),失敗時返回-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為要入隊的結(jié)點的數(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是要進棧的結(jié)點的數(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為頭指針的具有頭結(jié)點的單向鏈表中刪除第i個結(jié)點，ｓ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３．順序存儲鏈?zhǔn)酱鎯?4．gdｂeihfcａ１５．2ｉ和２i+1１6．n-１17．串長度相等且相應(yīng)位置的字符相等１8.不對的19．1１20.對的21.深度優(yōu)先搜索遍歷廣度優(yōu)先搜索遍歷22．深度優(yōu)先搜索遍歷廣度優(yōu)先搜索遍歷2３．４24．相等三、綜合應(yīng)用題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期末綜合練習(xí)二一、單項選擇題1．同一種邏輯結(jié)構(gòu)()。A.只能有唯一的存儲結(jié)構(gòu)Ｂ.可以有不同的存儲結(jié)構(gòu)Ｃ．只能表達某一種數(shù)據(jù)元素之間的關(guān)系D.以上三種說法均不對的2．在C語言中，順序存儲長度為３的字符串，需要占用（)個字節(jié)。Ａ.4B.3C3．鏈表所具有的特點是（)。Ａ.可以隨機訪問任一結(jié)點B.占用連續(xù)的存儲空間C.插入刪除元素的操作不需要移動元素結(jié)點Ｄ．可以通過下標(biāo)對鏈表進行直接訪問4．串函數(shù)StrＣaｔ（a，b)的功能是進行串（)。A．比較B．復(fù)制C．賦值D.連接5.數(shù)據(jù)的物理結(jié)構(gòu)（）。A.與數(shù)據(jù)的邏輯結(jié)構(gòu)無關(guān)B.僅僅涉及數(shù)據(jù)元素的表達C．只涉及數(shù)據(jù)元素間關(guān)系的表達Ｄ.涉及數(shù)據(jù)元素的表達和關(guān)系的表達6.一棵有n個結(jié)點采用鏈?zhǔn)酱鎯Φ亩鏄渲?，共有?個指針域為空。A．n＋1B．nＣ．n－1D.n-27.線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在()的關(guān)系。A．一對一B．一對多C.多對多Ｄ．每一個元素都有一個直接前驅(qū)和一個直接后繼8．設(shè)一棵哈夫曼樹共有ｎ個非葉結(jié)點，則該樹有(）個葉結(jié)點。Ａ．ｎB.n+1C9.以下表中可以隨機訪問的是（)。A．單向鏈表B.雙向鏈表Ｃ.單向循環(huán)鏈表D．順序表１0.從一個棧頂指針為top的鏈棧中刪除一個結(jié)點時，用變量x保存被刪結(jié)點的值，則執(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１．算法的時間復(fù)雜度與（）有關(guān)。A.所使用的計算機B.與計算機的操作系統(tǒng)C．與算法自身D.與數(shù)據(jù)結(jié)構(gòu)１２.一棵完全二叉樹共有5層,且第5層上有六個結(jié)點，該樹共有（）個結(jié)點。A．３0Ｂ．20C13.設(shè)有一個長度為ｎ的順序表，要刪除第ｉ個元素需移動元素的個數(shù)為()。A.ｎ-i＋１B．ｎ-ｉC．n-i-1Ｄ.i14．在一個無向圖中，所有頂點的度數(shù)之和等于邊數(shù)的(）倍。A.3B.2.5C１５.在一個單鏈表中，ｐ、q分別指向表中兩個相鄰的結(jié)點，且q所指結(jié)點是p所指結(jié)點的直接后繼，現(xiàn)要刪除ｑ所指結(jié)點，可用的語句是()。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的鏈棧中刪除一個結(jié)點時，用變量x保存被刪結(jié)點的值,則執(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.在一個鏈隊中，假設(shè)ｆ和ｒ分別為隊頭和隊尾指針,則刪除一個結(jié)點的運算為(）。A．r=ｆ－>nｅxt;B.ｒ＝r->next;C.f=ｆ->next;D.f=r－>ｎeｘt;20.對二叉排序樹進行（)遍歷，可以使遍歷所得到的序列是有序序列。Ａ．按層次B.后序C.中序D．前序21.一個棧的進棧序列是a,ｂ，c，ｄ,e，則棧的不也許輸出序列是()(進棧出?？梢越惶孢M行）。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．設(shè)有一個10階的對稱矩陣Ａ,采用壓縮存儲的方式，將其下三角部分以行序為主存儲到一維數(shù)組B中（數(shù)組下標(biāo)從１開始),則矩陣中元素Ａ8,5在一維數(shù)組B中的下標(biāo)是(）。A.3３B.3２C．852８.一組記錄的關(guān)鍵字序列為（4６,79，56,38，４0,８４),運用快速排序,以第一個關(guān)鍵字為分割元素，通過一次劃分后結(jié)果為()。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．在二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，通常每個結(jié)點中設(shè)立三個域,它們是______＿、、右指針。3.結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為＿______＿結(jié)構(gòu)。４．一棵二叉樹中順序編號為i的結(jié)點,若它存在左、右孩子，則左、右孩子編號分別為＿_＿＿__、____＿___。5．根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性,通常可分為集合、線性、、四類基本結(jié)構(gòu)。6.串的兩種最基本的存儲方式是＿＿__＿___和＿_______。7．規(guī)定在n個數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時間復(fù)雜度分別為＿＿__＿＿__和__＿＿＿＿__。8．一棵有2n-1個結(jié)點的二叉樹，其每一個非葉結(jié)點的度數(shù)都為２，則該樹共有_______個葉結(jié)點。9.在一個單向鏈表中p所指結(jié)點之后插入一個ｓ所指向的結(jié)點時，應(yīng)執(zhí)行＿＿＿＿____和p-＞next=s;的操作。１0．對于一棵具有n個結(jié)點的二叉樹，其相應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)中共有____＿___個指針域為空。1１．在二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，通常每個結(jié)點中設(shè)立三個域，它們是值域、。1２.＿＿___＿__遍歷二叉排序樹可得到一個有序序列。1３．一棵二叉樹中順序編號為ｉ的結(jié)點，若它存在左、右孩子，則左、右孩子編號分別為________、_＿_____＿。１4．如圖３所示的二叉樹，其后序遍歷序列為。eefgibachd圖315．向一個棧頂指針為h的鏈棧中插入一個s所指結(jié)點時，可執(zhí)行s-＞next＝h;和____＿___。16.如圖4所示的二叉樹，其先序遍歷序列為_________。ggfabdec圖4１7．在一個鏈隊中,設(shè)f和r分別為隊頭和隊尾指針,則插入s所指結(jié)點的操作為_＿_＿____和r=ｓ;(結(jié)點的指針域為ｎext)18.圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是＿＿__＿_的。(回答對的或不對的）1９．設(shè)有一棵深度為4的完全二叉樹，第四層上有5個結(jié)點，該樹共有＿_______＿個結(jié)點。(根所在結(jié)點為第１層)２0．二叉樹為二叉排序的充足必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。這種說法是______＿＿__的。（回答對的或不對的)21.對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素相應(yīng)的三元組涉及該元素的＿_＿__＿_、_______和___＿__＿三項信息。2２.對記錄序列排序是指按記錄的某個關(guān)鍵字排序，記錄序列按＿＿_＿____＿排序結(jié)果是唯一的。23．在對一組記錄(55,39，97,2２，１6,73，6５,47,8８）進行直接插入排序時，當(dāng)把第7個記錄65插入到有序表時，為尋找插入位置需比較_______＿＿次。24．按某關(guān)鍵字對記錄序列排序,若在排序前和排序后仍保持它們的前后關(guān)系，則排序算法是穩(wěn)定的,否則是不穩(wěn)定的。三、綜合題1.（1)以2，3,４,7,８,9作為葉結(jié)點的權(quán)，構(gòu)造一棵哈夫曼樹(規(guī)定每個結(jié)點的左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán))，給出相應(yīng)權(quán)重值葉結(jié)點的哈夫曼編碼。(2)一棵哈夫曼樹有ｎ個葉結(jié)點,它一共有多少個結(jié)點?簡述理由？2．設(shè)查找表為（16,１5，20,53,6４,7）,(1)用冒泡法對該表進行排序(規(guī)定升序排列),寫出每一趟的排序過程，通常對n個元素進行冒泡排序要進行多少趟冒泡？第j趟要進行多少次元素間的比較？(2)在排序后的有序表的基礎(chǔ)上，畫出對其進行折半查找所相應(yīng)的鑒定樹.（規(guī)定以數(shù)據(jù)元素作為樹結(jié)點)3.一組記錄的關(guān)鍵字序列為(46，79，56，3８，４0,8４）（1）運用快速排序的方法,給出以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果(給出逐次互換元素的過程，規(guī)定以升序排列)（２)對上述序列用堆排序的方法建立大根堆,規(guī)定以二叉樹逐次描述建堆過程。4.（1)設(shè)有查找表｛５,1４,2,6,18,7，４,16,３｝，依次取表中數(shù)據(jù),構(gòu)造一棵二叉排序樹。(2）說明如何由序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果，對上述二叉排序給出中序遍歷的結(jié)果。5.設(shè)查找表為（５0，６0,7５,85,96,98,１０５,110,120，130）(1)說出進行折半查找成功查找到元素１20需要進行多少次元素間的比較?(2)為了折半查找元素95,通過多少次元素間的比較才干擬定不能查到?（３）畫出對上述有序表進行折半查找所相應(yīng)的鑒定樹(規(guī)定以數(shù)據(jù)元素作為樹結(jié)點)６.(1）對給定權(quán)值２，1,3,３，4，5，構(gòu)造哈夫曼樹。(2)同樣用上述權(quán)值構(gòu)造另一棵哈夫曼樹,使兩棵哈夫曼樹有不同的高度，并分別求兩棵樹的帶權(quán)途徑長度。四、程序填空題1.以下是用尾插法建立帶頭結(jié)點且有n個結(jié)點的單向鏈表的程序，結(jié)點中的數(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Ｌ;/＊建立頭結(jié)點*／for(i=1;i<＝n；i++)｛p=（3);pdata＝ｉ；pnext=NULL;qneｘt＝(4);（5）;}retuｒn(head）;}2．設(shè)線性表為(6，１0，16,4)，以下程序用說明結(jié)構(gòu)變量的方法建立單向鏈表,并輸出鏈表中各結(jié)點中的數(shù)據(jù)。#deｆiｎeNＵＬL0voｉdmain(){ＮODEa,b，c,d,*head,*p；a.dａt(yī)ａ＝６;ｂ．data=10；c.ｄatａ=16;ｄ.ｄata=4;/*ｄ是尾結(jié)點＊/ｈｅad=(1）；a.next=&b;b.next=&ｃ；c．next=&d；(2）;/*以上結(jié)束建表過程＊/ｐ=heaｄ；／*ｐ為工作指針,準(zhǔn)備輸出鏈表＊／do{printf(“%d\n”，(3)）;（４）；}while((5))；｝3．以下程序是中序遍歷二叉樹的遞歸算法的程序,完畢程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為lｅft和right，數(shù)據(jù)域daｔa為字符型，BT指向根結(jié)點)。voidIｎｏrdｅr(strucｔBTreeNｏde＊BT)｛if(ＢT!=NＵLL)｛(１）;(2）;（３);｝}4．以下程序是后序遍歷二叉樹的遞歸算法的程序，完畢程序中空格部分(樹結(jié)構(gòu)中,左、右指針域分別為lefｔ和riｇht，數(shù)據(jù)域daｔa為字符型，ＢＴ指向根結(jié)點)。ｖoidＰostordeｒ(struｃｔBTreeNode*ＢT){if（BT!=ＮUＬL){(１);（2）;（３)