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

數(shù)據(jù)結(jié)構(gòu)(本)期末綜合練習(xí)２023年6月本課程期末考試題型及試卷結(jié)構(gòu)為：單項(xiàng)選擇題（每小題２分,共30分)、填空題（每小題2分,共２4分）、綜合題（每小題10分,共30分）、程序填空題（每空2分,共16分)。以下各套期末綜合練習(xí),請同學(xué)們認(rèn)真完畢。期末綜合練習(xí)一一、單項(xiàng)選擇題1．（)是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。Ａ、數(shù)據(jù)元素Ｂ．?dāng)?shù)據(jù)對象Ｃ．?dāng)?shù)據(jù)結(jié)構(gòu)Ｄ．?dāng)?shù)據(jù)項(xiàng)2.數(shù)據(jù)的物理結(jié)構(gòu)()。A．與數(shù)據(jù)的邏輯結(jié)構(gòu)無關(guān)Ｂ.僅僅涉及數(shù)據(jù)元素的表達(dá)C．只涉及數(shù)據(jù)元素間關(guān)系的表達(dá)Ｄ.涉及數(shù)據(jù)元素的表達(dá)和關(guān)系的表達(dá)３.設(shè)鏈表中的結(jié)點(diǎn)是NＯＤE類型的結(jié)構(gòu)體變量,且有NＯDE＊p;為了申請一個(gè)新結(jié)點(diǎn),并由p指向該結(jié)點(diǎn)，可用以下語句()。A．p=(ＮODE*）mａlloc（sｉｚeof（NＯＤE));B.p=（＊NODE）malｌｏc(sｉzeof(NODE));Ｃ.ｐ=(ＮＯDＥ)mallｏc（sizｅof(ｐ））;Ｄ.p=（ＮODE*)maｌloc(sizeof（p)）;４.從n個(gè)數(shù)中選取最大元素()。A．基本操作是數(shù)據(jù)元素間的互換B．算法的時(shí)間復(fù)雜度是O(n2）C．算法的時(shí)間復(fù)雜度是O(n)D.需要進(jìn)行（n＋1)次數(shù)據(jù)元素間的比較5.設(shè)順序存儲的線性長度為ｎ，要在第i個(gè)元素之前插入一個(gè)新元素,按課本的算法當(dāng)i＝()時(shí),移動元素次數(shù)為2Ａ.n／2B.nC．1D．n－16．線性表的順序結(jié)構(gòu)中，()。Ａ．邏輯上相鄰的元素在物理位置上不一定相鄰B.數(shù)據(jù)元素是不能隨機(jī)訪問的C．邏輯上相鄰的元素在物理位置上也相鄰D.進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高７.一個(gè)棧的進(jìn)棧序列是１,2，３，４,則棧的不也許的出棧序列是（）（進(jìn)出棧操作可以交替進(jìn)行)A.３，2，4,1B．1,4,2，3C.4，3，2,1D．3,2,1,48．帶頭結(jié)點(diǎn)的單向鏈表為空的判斷條件是(）(設(shè)頭指針為hｅａd）。A.heaｄ==NＵＬＬB.ｈeaｄ->neｘt==ＮULＬＣ．hｅad->ｎext==headＤ.hｅad!=ＮUＬL9．設(shè)有一個(gè)帶頭結(jié)點(diǎn)的鏈隊(duì)列,隊(duì)列中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域data和指針域next組成，frｏnt和rear分別為鏈隊(duì)列的頭指針和尾指針。設(shè)p指向要入隊(duì)的新結(jié)點(diǎn)(該結(jié)點(diǎn)已被賦值),則入隊(duì)操作為（)。A．rear－>neｘｔ=p;ｒｅaｒ=p;B.reaｒ－＞nexｔ=p;p=rｅar；C．p＝rｅar－＞ｎext;reaｒ＝p；Ｄ.rear=p;rear－>ｎext=p;10.線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在()的關(guān)系。Ａ．一對一Ｂ.一對多C．多對多Ｄ.每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼11．以下說法不對的的是（）。A.順序棧中，棧滿時(shí)再進(jìn)行進(jìn)棧操作稱為“上溢”B．順序棧中，?？諘r(shí)再作出棧棧操作稱為“下溢”C.順序隊(duì)列中，當(dāng)尾指針已經(jīng)超越隊(duì)列存儲空間的上界,則一定是隊(duì)列已滿D．順序隊(duì)列中,隊(duì)列的頭指針和尾指針均超越隊(duì)列存儲空間的上界，則隊(duì)列已空12.設(shè)順序存儲的線性表長度為n,要刪除第ｉ個(gè)元素,按課本的算法，當(dāng)i=()時(shí)，移動元素的次數(shù)為3Ａ.3B．n/２C.n-３D１3．設(shè)有一個(gè)20階的對稱矩陣A，采用壓縮存儲方式，將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組中（矩陣A的第一個(gè)元素為a1１,數(shù)組ｂ的下標(biāo)從1開始），則矩陣元素a8,5在一維數(shù)組b中的下標(biāo)是（)。A.30B.２8C.40D14.以下說法不對的的是（）。A．棧的特點(diǎn)是后進(jìn)先出B．隊(duì)列的特點(diǎn)是先進(jìn)先出Ｃ.棧的刪除操作在棧底進(jìn)行，插入操作在棧頂進(jìn)行D.隊(duì)列的插入操作在隊(duì)尾進(jìn)行，刪除操作在隊(duì)頭進(jìn)行15．深度為5的完全二叉樹第5層上有4個(gè)結(jié)點(diǎn)，該樹一共有(）個(gè)結(jié)點(diǎn)。Ａ．28B．30C．３1D１6.一個(gè)棧的進(jìn)棧序列是a,b,c，d，則棧的不也許的出棧序列是()。A．a(chǎn)dｂcB.ｂｃadC．cbadD．dcba1７.已知一個(gè)圖的所有頂點(diǎn)的度數(shù)之和為m，則m一定不也許是（）。A.４Ｂ．8Ｃ．１２D18.設(shè)tｏp是一個(gè)鏈棧的棧頂指針，棧中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域daｔa和指針域next組成,設(shè)用x接受棧頂元素,則出棧操作為()。Ａ．x=top－>dａt(yī)a；top=top－>neｘt;B.ｔop=top->next;x=ｔop－>data;C．x=top->next;top=ｔop->daｔa;D.ｔoｐ－>next=tｏｐ;x=top->ｄata;19.以下說法對的的是()。Ａ.連通圖G的生成樹中可以包含回路Ｂ．連通圖G的生成樹可以是不連通的C．連通圖G的生成樹一定是唯一的D．連通圖G的生成樹一定是連通而不包含回路的20.設(shè)有一個(gè)帶頭結(jié)點(diǎn)的鏈隊(duì)列，隊(duì)列中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域ｄaｔa和指針域neｘt組成，ｆronｔ和reaｒ分別為鏈隊(duì)列的頭指針和尾指針,要執(zhí)行出隊(duì)操作,用x保存出隊(duì)元素的值，ｐ為指向結(jié)點(diǎn)類型的指針，可執(zhí)行如下操作：p＝frｏnt－＞next;ｘ=ｐ->data;然后執(zhí)行(）。Ａ.ｆroｎt=p->neｘt；B．front－>next=p->next;C.fｒoｎt=ｐ;D．fｒont->nｅxt＝ｐ;２１．對n個(gè)元素進(jìn)行冒泡排序，通常要進(jìn)行n-１趟冒泡，在第j趟冒泡中共要進(jìn)行（）次元素間的比較。A.jB.ｊ-1C．ｎ－ｊD2２．在排序過程中，可以有效地減少一趟排序過程中元素間的比較次數(shù)的算法是（）。Ａ.冒泡B．選擇Ｃ．直接插入D.折半插入２3．空串的長度為(）。A.0B．1Ｃ.２Ｄ2４.如圖1所示，若從頂點(diǎn)a出發(fā)按深度優(yōu)先搜索法進(jìn)行遍歷,則也許得到的頂點(diǎn)序列為()。abecdfabecdfB．a(chǎn)beｄcｆC．a(chǎn)cｅbdfＤ.acfbde圖125.串函數(shù)StrCmp(“abA”,”ａba”)的值為（）。A.1Ｂ．0Ｃ．“ａbAaba”D26.一棵哈夫曼樹有n個(gè)葉子結(jié)點(diǎn)(終端結(jié)點(diǎn)),該樹總共有()個(gè)結(jié)點(diǎn)。Ａ.2n-2B.2n-1C．2ｎD．227.設(shè)有一個(gè)10階的對稱矩陣A,采用壓縮存儲方式將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組b中。（矩陣A的第一個(gè)元素為ａ1,1，數(shù)組b的下標(biāo)從1開始),則矩陣元素a５,３相應(yīng)一維數(shù)組b的數(shù)組元素是（）。A．b［18]B.b[8]C.b[13]D.ｂ[１０]28.數(shù)據(jù)的（）結(jié)構(gòu)與所使用的計(jì)算機(jī)無關(guān)。A．邏輯B.物理C．存儲D.邏輯與存儲２9．已知如圖2所示的一個(gè)圖,若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷,則也許得到的一種頂點(diǎn)序列為（）。A.abeｃdfＢ.aｃfebdC.aebcｆdD．a(chǎn)edｆcbbbdfeca圖2二、填空題１．通?？梢园岩槐揪哂胁煌鹿?jié)的書的目錄結(jié)構(gòu)抽象成_＿_(dá)_____結(jié)構(gòu)。2.通常數(shù)據(jù)的邏輯結(jié)構(gòu)涉及集合、線性、____、____四種類型。３.要在一個(gè)單向鏈表中p所指向的結(jié)點(diǎn)之后插入一個(gè)s所指向的新結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)閚exｔ，可執(zhí)行_＿＿_(dá)＿_(dá)__和p-＞next＝s;的操作。4.通?？梢园涯吵鞘兄懈鞴徽军c(diǎn)間的線路圖抽象成________結(jié)構(gòu)。5.設(shè)有一個(gè)非空的鏈棧，棧頂指針為hs,要進(jìn)行出棧操作,用x保存出棧結(jié)點(diǎn)的值，棧結(jié)點(diǎn)的指針域?yàn)閚eｘt,則可執(zhí)行x＝hs－>data;___＿_(dá)___。6．設(shè)有一個(gè)單向鏈表，結(jié)點(diǎn)的指針域?yàn)閚eｘt,頭指針為hｅaｄ,p指向尾結(jié)點(diǎn),為了使該單向鏈表改為單向循環(huán)鏈表,可用語句_____＿_(dá)＿。7.在一個(gè)不帶頭結(jié)點(diǎn)的非空鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針,隊(duì)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閐ata，指針域?yàn)閚ｅxt,若要進(jìn)行出隊(duì)操作,并用變量x存放出隊(duì)元素的數(shù)據(jù)值，則相關(guān)操作為x=f－>data;__＿_(dá)____。8.循環(huán)隊(duì)列的隊(duì)頭指針為f，隊(duì)尾指針為r,當(dāng)_______＿時(shí)表白隊(duì)列已空。９．循環(huán)隊(duì)列的最大存儲空間為MａxSiｚｅ=８,采用少用一個(gè)元素空間以有效的判斷?？栈驐M，若隊(duì)頭指針fｒoｎｔ=4，則當(dāng)隊(duì)尾指針rｅar=_＿＿_(dá)____時(shí),隊(duì)列為空,當(dāng)ｒｅar=_____＿_(dá)_時(shí),隊(duì)列有6個(gè)元素。10．設(shè)有一個(gè)鏈棧，棧頂指針為hｓ,現(xiàn)有一個(gè)s所指向的結(jié)點(diǎn)要入棧，則可執(zhí)行操作＿_(dá)_＿_(dá)___和hs=s；11．稀疏矩陣存儲時(shí),采用一個(gè)由___＿、＿_(dá)_＿、____3部分信息組成的三元組唯一擬定矩陣中的一個(gè)非零元素。1２.在一個(gè)鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的指針域?yàn)閚ｅxt，則插入一個(gè)s所指結(jié)點(diǎn)的操作為＿_(dá)__＿_(dá)＿_(dá)；ｒ=s;13.一棵二叉樹順序編號為6的結(jié)點(diǎn)(樹中各結(jié)點(diǎn)的編號與等深度的完全二叉中相應(yīng)位置上結(jié)點(diǎn)的編號相同），若它存在右孩子,則右孩子的編號為＿＿_(dá)＿_(dá)__＿。14.串的兩種最基本的存儲方式分別是__＿＿_(dá)＿_(dá)和________。15.結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為_＿_(dá)_____結(jié)構(gòu)。16．一棵二叉樹中順序編號為i的結(jié)點(diǎn),若它存在左、右孩子，則左、右孩子編號分別為______＿＿、_＿_(dá)___＿＿。1７．結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為__＿_(dá)____結(jié)構(gòu)。18,兩個(gè)串相等的充足必要條件是。19．如圖3所示的二叉樹，其前序遍歷序列為_________。ggfabdec圖３20．一棵二叉樹葉結(jié)點(diǎn)(終端結(jié)點(diǎn))數(shù)為5,單分支結(jié)點(diǎn)數(shù)為2，該樹共有_＿＿＿_(dá)_個(gè)結(jié)點(diǎn)。21．在隊(duì)列的順序存儲結(jié)構(gòu)中,當(dāng)插入一個(gè)新的隊(duì)列元素時(shí)，指針的值增1,當(dāng)刪除一個(gè)元素隊(duì)列時(shí),指針的值增1。22．根據(jù)搜索方法的不同,圖的遍歷有＿＿_(dá)_、___＿兩種方法。2３．循環(huán)隊(duì)列的引入，目的是為了克服。24．一個(gè)有序表{３，4，10，14，34,4３,46，6４，75，78，９0，96,１3０}用折半查找法查找值為90的結(jié)點(diǎn)，經(jīng)_＿_(dá)_____次比較后查找成功。三、綜合題１．(1)設(shè)heａd1和p１分別是不帶頭結(jié)點(diǎn)的單向鏈表A的頭指針和尾指針，hｅad2和ｐ２分別是不帶頭結(jié)點(diǎn)的單向鏈表B的頭指針和尾指針，若要把B鏈表接到A鏈表之后，得到一個(gè)以hｅad1為頭指針的單向循環(huán)鏈表，寫出其中兩個(gè)關(guān)鍵的賦值語句（不用完整程序,結(jié)點(diǎn)的鏈域?yàn)閚exｔ)。(2)單向鏈表的鏈域?yàn)閚ext,設(shè)指針p指向單向鏈表中的某個(gè)結(jié)點(diǎn),指針ｓ指向一個(gè)要插入鏈表的新結(jié)點(diǎn)，現(xiàn)要把ｓ所指結(jié)點(diǎn)插入p所指結(jié)點(diǎn)之后,某學(xué)生采用以下語句:p－>next=s;s->neｘｔ=p->next;這樣做對的嗎？若對的則回答對的,若不對的則說明應(yīng)如何改寫。２.(1）已知某二叉樹的后序遍歷序列是dｅｂca，中序遍歷序列是dｂeac,試畫出該二叉樹（２)若上述二叉樹的各個(gè)結(jié)點(diǎn)的字符分別代表不同的整數(shù)（其中沒有相等的），并恰好使該樹成為一棵二叉排序樹,試給出a、b、c、d、e的大小關(guān)系。(3）給出該樹的前序遍歷序列3．（1)畫出對長度為1０的有序表進(jìn)行折半查找的鑒定樹（以序號1，2，……１0表達(dá)樹結(jié)點(diǎn)）（2）對上述序列進(jìn)行折半查找,求等概率條件下，成功查找的平均查找長度4.(1）一組記錄的關(guān)鍵字序列為{４5，40，6５,４3，35,95}，寫出運(yùn)用快速排序的方法,以第一個(gè)記錄為基準(zhǔn)得到的一趟劃分的結(jié)果(規(guī)定給出一趟劃分中每次掃描和互換的結(jié)果)(２)對序列{45，4０，65,43，3５,９5}運(yùn)用直接插入排序,寫出逐次插入過程(從第一個(gè)元素一直到第六個(gè)元素）。5.(1）運(yùn)用篩選法，把序列{３7,７7,62，9７,1１，27,52,4７}建成堆（小根堆)，畫出相應(yīng)的完全二叉樹（2）寫出對上述堆所相應(yīng)的二叉樹進(jìn)行前序遍歷得到的序列６.(1）設(shè)有查找表{5,14,2,6,1８,７,4,16,3},依次取表中數(shù)據(jù),構(gòu)造一棵二叉排序樹.（２）說明如何通過序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果。四、程序填空題1．以下函數(shù)為直接選擇排序算法，對a[1］,a［2],…a[ｎ]中的記錄進(jìn)行直接選擇排序，完畢程序中的空格typedｅfｓtruct{ｉntｋey;……}NOＤＥ;ｖoｉｄseｌsort(NＯDEa[],inｔn){?inti,j,k; ＮODＥtemp; ｆｏr(i=１;i<＝___(1)_____;i++)?｛? k=i; ?for(j＝ｉ+1;j<=_＿＿(2)＿_(dá)＿＿_(dá);j＋＋)? iｆ(a[j].key<a[ｋ].kｅy）＿_(dá)(３)____＿_(dá); if(i!=ｋ) ?{? ｔemｐ=a[i];? ?__＿(4)__＿_(dá)_; ____(５)__＿_(dá)；? }?}}2．以下函數(shù)在ａ[0]到ａ［ｎ-1]中,用折半查找算法查找關(guān)鍵字等于ｋ的記錄，查找成功返回該記錄的下標(biāo)，失敗時(shí)返回－1，完畢程序中的空格typedeｆstrｕct｛intｋey;……}ＮOＤＥ;iｎｔBinaｒy_Search(NＯＤＥa[],intn,intk){ｉntlow，ｍiｄ，ｈｉgh;lｏw=０;hｉgh=n-１;whｉlｅ(_＿_(dá)（1)_____){miｄ＝（low+high)／2;if(ａ[mid]．ｋeｙ==k）retｕrｎ__(2)_____＿； elseiｆ(＿_(dá)＿(３)_＿_(dá)_＿）low=mid＋１; eｌse＿_(dá)(４)___＿_(dá)_;?｝___(5）＿_(dá)___;?}３．以下程序是中序遍歷二叉樹的遞歸算法的程序,完畢程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和ｒｉght,數(shù)據(jù)域data為字符型,BT指向根結(jié)點(diǎn))。voｉｄIｎoｒder(strｕctBTｒeeNｏde*BT）{ｉｆ(BT！=NＵLL){(1）;（２）;(３)；}}4．以下函數(shù)為鏈棧的進(jìn)棧操作,ｘ是要進(jìn)棧的結(jié)點(diǎn)的數(shù)據(jù)域，ｔoｐ為棧頂指針ｓtｒucｔｎｏdｅ{ElｅmTypedaｔa；structnode*nｅxt;｝；strｕcｔｎode*tｏｐ;voidPush(ＥlｅmＴｙpex)｛structｎodｅ*p;ｐ＝（sｔructnｏde*)malｌoc(___(1）_____）;p->ｄata＝ｘ;_＿_(dá)(２)＿_(dá)___;_____(3)___;}期末綜合練習(xí)一答案一、單項(xiàng)選擇題1．B２．Ｄ3.A4.C５．D6．C7．B8．Ｂ９．A10.Ａ1１.C12.Ｃ13．D14.Ｃ1５．D16.Ａ17.Ｄ１８．A19.D20．B２１.Ｃ22．D２3．A２4．B25．D26.Ｂ27．C28．A2９．Ｄ二、填空題１.樹形２.樹形;圖狀３．s－>neｘt＝p-＞nｅxｔ;4．圖狀5．hs=hs-＞nｅxｔ;6.p->nｅxt＝heaｄ;７.ｆ=f－>next;8．r=f9.4；21０.s－>next=hｓ；11.行號;列號；非零元12．r->nexｔ=s13.13１４．順序存儲鏈?zhǔn)酱鎯?5.圖狀16.2i和2i+１1７.樹形18．串長度相等且相應(yīng)位置的字符相等19．a(chǎn)ｂdeｆcg20．11２１．尾頭22．深度優(yōu)先搜索遍歷廣度優(yōu)先搜索遍歷2３.假上溢2４.4三、綜合應(yīng)用題1．(1）p1->nｅxｔ=hｅad2；p２->next=ｈeaｄ1;(2）不對,s－>next=ｐ-＞next；p－>nexｔ=ｓ;abceabced(2）ｄ<ｂ＜e<a<c(3）abdeｃ5284952849631071(２)ASL=（1x1+2ｘ2+3x4＋4x3)/1０=2９/10４.(１)4540654335９５３５40654３35９53540６543６５95３540４34365９5３5４043４５6５９5（2)404565433５954043４5653595３54０4345659５初始樹堆11372747初始樹堆11372747526277973777624752271197(2)11,3７,47，97,７7,27,６2，526.（1）22461673185145（２）中序遍歷四、程序填空題1.(１)n-１（２)ｎ（3）k=j(４）a［i]=ａ[k]（5)a［k]=ｔｅmp2.（1）low＜＝ｈigh（2)mid(３）a[ｍid］.kｅy<ｋ;（4）high＝mid-１(5)return－1；3．(1）Ｉnoｒｄｅr(ＢT-＞ｌeft)（２）pｒintf(“%c”,ＢＴ->daｔａ）(3)Iｎordeｒ(BT－>rｉgｈt)4.（1)sizｅof(sｔrｕctnoｄe)（2)p->nｅxt=ｔop(3）tｏp=p期末綜合練習(xí)二一、單項(xiàng)選擇題1.深度為５的完全二叉樹共有20個(gè)結(jié)點(diǎn)，則第5層上有（）個(gè)結(jié)點(diǎn)(根所在結(jié)點(diǎn)為第一層）。Ａ．3B．8C．5D２.同一種邏輯結(jié)構(gòu)（）。A．只能有唯一的存儲結(jié)構(gòu)B．可以有不同的存儲結(jié)構(gòu)C.只能表達(dá)某一種數(shù)據(jù)元素之間的關(guān)系D．以上三種說法均不對的3.已知一個(gè)圖的邊數(shù)為m，則該圖的所有頂點(diǎn)的度數(shù)之和為(）。A．2mB.mC．２m+1D.ｍ／24．鏈表所具有的特點(diǎn)是(）。A．可以隨機(jī)訪問任一結(jié)點(diǎn)B.占用連續(xù)的存儲空間C．插入刪除元素的操作不需要移動元素結(jié)點(diǎn)D．可以通過下標(biāo)對鏈表進(jìn)行直接訪問５．?dāng)?shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（)結(jié)構(gòu)。A.物理Ｂ．存儲C.邏輯與物理D.邏輯６.數(shù)據(jù)的物理結(jié)構(gòu)()。A.與數(shù)據(jù)的邏輯結(jié)構(gòu)無關(guān)B.僅僅涉及數(shù)據(jù)元素的表達(dá)C.只涉及數(shù)據(jù)元素間關(guān)系的表達(dá)Ｄ．涉及數(shù)據(jù)元素的表達(dá)和關(guān)系的表達(dá)7．線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（)的關(guān)系。A.一對一B．一對多C.多對多D．每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼8．線性表只要以（)方式存儲就能進(jìn)行折半查找。Ａ.鏈接B．順序Ｃ.關(guān)鍵字有序的順序Ｄ．二叉樹9．以下表中可以隨機(jī)訪問的是（)。Ａ．單向鏈表B.雙向鏈表C．單向循環(huán)鏈表Ｄ．順序表１0.散列查找的原理是()。A.在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立擬定的相應(yīng)關(guān)系B．按待查記錄的關(guān)鍵字有序的順序方式存儲Ｃ.按關(guān)鍵字值的比較進(jìn)行查找Ｄ.基于二分查找的方法11．算法的時(shí)間復(fù)雜度與（）有關(guān)。Ａ.所使用的計(jì)算機(jī)B．與計(jì)算機(jī)的操作系統(tǒng)C.與算法自身D．與數(shù)據(jù)結(jié)構(gòu)12.對ｎ個(gè)元素進(jìn)行冒泡排序若某趟冒泡中只進(jìn)行了（）次元素間的互換，則表白序列已經(jīng)排好序。A.1B．2C.０D１３.設(shè)有一個(gè)長度為n的順序表，要刪除第ｉ個(gè)元素需移動元素的個(gè)數(shù)為（)。Ａ.n-ｉ+1Ｂ．ｎ-iC.n-ｉ－１D．i１4.排序過程中,每一趟從無序子表中將一個(gè)待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到所有排好序?yàn)橹?該排序算法是()。A.直接插入排序B.快速排序C.冒泡排序D.選擇排序１5．在一個(gè)單鏈表中,p、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼，現(xiàn)要刪除q所指結(jié)點(diǎn)，可用的語句是()。A.ｐ＝ｑ-＞neｘtB.p－>nｅxt＝qC．ｐ->nｅxt＝qnextD.q->next=ＮUＬL16.在對一組元素(６4，48,106，33，2５,８2，70，55,93）進(jìn)行直接插入排序時(shí),當(dāng)進(jìn)行到要把第7個(gè)元素７０插入到已經(jīng)排好序的子表時(shí)，為找到插入位置，需進(jìn)行（)次元素間的比較（指由小到大排序）。A．6B．2Ｃ.3D1７.從一個(gè)棧頂指針為toｐ的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí),用變量x保存被刪結(jié)點(diǎn)的值,則執(zhí)行(）。A．x=ｔop->data;top=ｔop-＞nｅｘｔ;Ｂ.x＝top->datａ;C．toｐ＝ｔoｐ-＞next;x=ｔｏｐ->dａt(yī)a;Ｄ.top=toｐ->nｅｘt;ｘ=dａt(yī)a;18．采用順序查找法對長度為n的線性表進(jìn)行查找（不采用表尾設(shè)監(jiān)視哨的方法）,最壞的情況下要進(jìn)行(）次元素間的比較。A．n＋2B．nC．n－１D.n/２１9．在一個(gè)鏈隊(duì)中,假設(shè)ｆ和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為(）。A．ｒ＝f->neｘｔ;Ｂ.r=r->nｅxｔ；C.f=f->neｘt;Ｄ.f=r->neｘt;20．如圖1，若從頂點(diǎn)a出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷，則也許得到的頂點(diǎn)序列為（）。abecdfgabecdfgB．a(chǎn)becdgfＣ．a(chǎn)ｃfedgbＤ．a(chǎn)becｆdg圖121.一個(gè)棧的進(jìn)棧序列是a,b,ｃ,d,ｅ,則棧的不也許輸出序列是()（進(jìn)棧出?？梢越惶孢M(jìn)行)。Ａ.ｄceaｂB.edcbａC.decbaD．ａbcｄe22.元素2,４，6，8按順序依次進(jìn)棧，則該棧的不也許輸出序列是()（進(jìn)棧出?？梢越惶孢M(jìn)行）。A.8,6,4,２B．2,4，6,8C.4，2,8，6Ｄ．８,6，２,423.有一個(gè)長度為１０的有序表,按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（)。Ａ.26/10B．29／１０24.排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列(初始為空)的一端的方法，稱為（）排序。A.歸并Ｂ．插入C．選擇D.快速２5.排序算法中，從未排序序列中依次取出元素與已排序序列(初始為空)中的元素進(jìn)行比較(規(guī)定比較次數(shù)盡量少）,然后將其放入已排序序列的對的位置的方法是(）。A.冒泡B.直接插入C．折半插入Ｄ.選擇排序26．一棵哈夫曼樹總共有23個(gè)結(jié)點(diǎn),該樹共有（)個(gè)葉結(jié)點(diǎn)(終端結(jié)點(diǎn)）Ａ.10Ｂ.1３Ｃ．1127．設(shè)有一個(gè)1０階的對稱矩陣A，采用壓縮存儲的方式,將其下三角部分以行序?yàn)橹鞔鎯Φ揭痪S數(shù)組B中（數(shù)組下標(biāo)從1開始）,則矩陣中元素Ａ8,５在一維數(shù)組B中的下標(biāo)是()。A.33B．32Ｃ．8５28．隊(duì)列的插入操作在（）進(jìn)行。A.隊(duì)頭Ｂ.隊(duì)尾C．隊(duì)頭或隊(duì)尾Ｄ．在任意指定位置2９．在一個(gè)無向圖中,所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的（）倍。A．3B.２.5C二、填空題１.一棵二叉樹沒有單分支結(jié)點(diǎn)，有６個(gè)葉結(jié)點(diǎn),則該樹總共有____＿_(dá)__個(gè)結(jié)點(diǎn)。2.棧和隊(duì)列的操作特點(diǎn)分別是_＿＿_(dá)___和_＿_(dá)___＿＿。3.設(shè)一棵完全二叉樹,其最高層上最右邊的葉結(jié)點(diǎn)的編號為奇數(shù),該葉節(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為10，該完全二叉樹一共有＿_(dá)＿_(dá)___＿個(gè)結(jié)點(diǎn)。4．結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為__＿＿_(dá)＿_(dá)＿結(jié)構(gòu)。5.按照二叉樹的遞歸定義,對二叉樹遍歷的常用算法有____、____、___＿三種。6．根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性,通?？煞譃榧?、線性、、四類基本結(jié)構(gòu)。7.數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為＿＿_(dá)___＿_(dá)結(jié)構(gòu)。8．規(guī)定在n個(gè)數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時(shí)間復(fù)雜度分別為__＿_(dá)_＿_(dá)_和＿_(dá)_＿_(dá)___。9．把數(shù)據(jù)存儲到計(jì)算機(jī)中，并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_＿＿_(dá)__＿_(dá)結(jié)構(gòu)。10.在一個(gè)單向鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指向的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行___＿_(dá)___和p－>neｘt=ｓ;的操作。1１．結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系稱為______＿＿結(jié)構(gòu)。12．在二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，通常每個(gè)結(jié)點(diǎn)中設(shè)立三個(gè)域，它們是值域、。13.如圖2所示的二叉樹，其后序遍歷序列為。eefgibachd圖214．一棵二叉樹中順序編號為i的結(jié)點(diǎn)，若它存在左、右孩子,則左、右孩子編號分別為________、_＿_(dá)___＿_(dá)。1５．n個(gè)元素進(jìn)行冒泡法排序,通常需要進(jìn)行_＿＿＿＿_(dá)＿_(dá)趟冒泡。16．向一個(gè)棧頂指針為h的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí),可執(zhí)行ｓ－>next=h;和_＿_(dá)_____。17．二叉樹為二叉排序的充足必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說法是__________的。（回答對的或不對的）18．在一個(gè)鏈隊(duì)中,設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為____＿＿_(dá)＿和r=ｓ；(結(jié)點(diǎn)的指針域?yàn)閚ｅｘt)19．圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是__＿_(dá)__的。(回答對的或不對的）２0.設(shè)有一棵深度為4的完全二叉樹，第四層上有5個(gè)結(jié)點(diǎn),該樹共有＿_(dá)＿_(dá)___＿_(dá)個(gè)結(jié)點(diǎn)。(根所在結(jié)點(diǎn)為第1層)2１.根據(jù)搜索方法的不同，圖的遍歷有＿_(dá)__、_＿_(dá)_兩種方法22.對稀疏矩陣進(jìn)行壓縮存儲，矩陣中每個(gè)非零元素相應(yīng)的三元組涉及該元素的_＿_(dá)__＿_(dá)、__＿＿_(dá)__和＿＿_(dá)____三項(xiàng)信息。23．按某關(guān)鍵字對記錄序列排序,若關(guān)鍵字的記錄在排序前和排序后仍保持它們的前后關(guān)系,則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。2４.在對一組記錄(55,39，97,２2,16,７3,６5,４7，88)進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄6５插入到有序表時(shí),為尋找插入位置需比較______＿_(dá)_次。三、綜合題1.（1）運(yùn)用篩選過程把序列｛42，82，６7,1０2,16，32,57,52}建成堆（小根堆）,畫出該堆（不規(guī)定中間過程)。(2）寫出對上述堆相應(yīng)的完全二叉樹進(jìn)行中序遍歷得到的序列。２.(１)以2，3,4，７，8，９作為葉結(jié)點(diǎn)的權(quán),構(gòu)造一棵哈夫曼樹(規(guī)定每個(gè)結(jié)點(diǎn)的左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán)),給出相應(yīng)權(quán)重值葉結(jié)點(diǎn)的哈夫曼編碼。(2)一棵哈夫曼樹有n個(gè)葉結(jié)點(diǎn),它一共有多少個(gè)結(jié)點(diǎn)?簡述理由?3.設(shè)查找表為(1６，15,20，５３，64,7）,(1）用冒泡法對該表進(jìn)行排序（規(guī)定升序排列）,規(guī)定寫出每一趟的排序過程。(2）在排序后的有序表的基礎(chǔ)上,畫出對其進(jìn)行折半查找所相應(yīng)的鑒定樹.（規(guī)定以數(shù)據(jù)元素作為樹結(jié)點(diǎn))(3)求在等概率條件下,對上述有序表成功查找的平均查找長度.４.一組記錄的關(guān)鍵字序列為（４6,７9，56，38,40，8４）（１）運(yùn)用快速排序的方法，給出以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果(給出逐次互換元素的過程，規(guī)定以升序排列）(2)對上述序列用堆排序的方法建立大根堆,規(guī)定以二叉樹逐次描述建堆過程。5.(1）設(shè)有一個(gè)整數(shù)序列{50,38,16,8２,110,1３,64},依次取出序列中的數(shù),構(gòu)造一棵二叉排序樹（2）運(yùn)用上述二叉排序樹,為了查找１1０，經(jīng)多少次元素間的比較能成功查到，為了查找15，經(jīng)多少次元素間的比較可知道查找失敗6．設(shè)查找表為(5０,60,７5,8５，96,９８,105,1１０，120,1３0）(1）說出進(jìn)行折半查找成功查找到元素120需要進(jìn)行多少次元素間的比較？（２）為了折半查找元素95,通過多少次元素間的比較才干擬定不能查到?（3)畫出對上述有序表進(jìn)行折半查找所相應(yīng)的鑒定樹（規(guī)定以數(shù)據(jù)元素作為樹結(jié)點(diǎn))四、程序填空題1.以下函數(shù)為鏈隊(duì)列的入隊(duì)操作，x為要入隊(duì)的結(jié)點(diǎn)的數(shù)據(jù)域的值，front、ｒｅａr分別是鏈隊(duì)列的隊(duì)頭、隊(duì)尾指針structｎｏde｛ＥｌemＴyｐeｄatａ;ｓtructｎｏｄｅ＊ｎext；};struｃtnｏde*fronｔ,*reａr;voidInQｕeue(EleｍTypex){strucｔnode*p；p＝(ｓtrucｔnｏde*)___（１）____＿;ｐ->data=x;p->neｘt=ＮUＬL;＿_(dá)_（2)＿_(dá)＿_(dá)_；rear=__＿(3)＿_(dá)_＿_(dá);}２.以下是用尾插法建立帶頭結(jié)點(diǎn)且有ｎ個(gè)結(jié)點(diǎn)的單向鏈表的程序，結(jié)點(diǎn)中的數(shù)據(jù)域從前向后依次為１,2，3，……,n，完畢程序中空格部分。ＮOＤE＊cｒeate（ｎ){NODE＊ｈeａd，*ｐ,*q;inti;p=（NODE*)malloｃ(siｚeof(ＮＯDＥ));ｈead=(1）;（２）;ｐneｘt＝ＮUＬL;/*建立頭結(jié)點(diǎn)＊/ｆoｒ(i=1;i<＝n;ｉ++）{p＝(3);pｄaｔａ=i;pnｅxt=NULＬ;qnext=（4);(5);｝rｅｔurｎ(hｅad）;}３.以下函數(shù)在heaｄ為頭指針的具有頭結(jié)點(diǎn)的單向鏈表中刪除第i個(gè)結(jié)點(diǎn)，ｓｔrｕctnode{ｉntdaｔa;ｓtrｕcｔnodｅ*ｎｅxt；｝;tｙpｅdefstructnoｄeＮODEintdeleｔe(NODE*head,ｉｎti){NODＥ*p,*q;intj;q=heaｄ;j=0;whilｅ((q!=NＵLＬ)&＆(___（1)_____)）{__＿(２)_____；j+＋;}if(ｑ==ＮＵLL)reｔｕｒn(０);ｐ=＿_(dá)_(3）_____;___(4)_＿＿_(dá)_＝ｐ－>next;fｒｅe(_＿_(dá)(5)＿_(dá)＿_(dá)_)；return（１）;}4．以下程序是中序遍歷二叉樹的遞歸算法的程序，完畢程序中空格部分(樹結(jié)構(gòu)中左、右指針域分別為leｆt和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn))。ｖoidInorｄeｒ(structBTreｅＮode*ＢT）{if（ＢＴ?。絅UＬL){（1);(2)；(3）;}}期末綜合練習(xí)二答案一、單項(xiàng)選擇題１．C2．B3.Ａ4．C5．Ｄ6．D7．A8.C9．Ｄ１0．A11．C１２．C13.Ｂ1４．A１5．C16．C17.A18．B19．C20.Ｂ2１．A２2．D23．B24.Ｃ25.C26.D2７．A2８．B２9．D二、填空題1.1１2.后進(jìn)先出、先進(jìn)先出3.２１4.圖狀(網(wǎng)狀)5．先序；中序；后序6．樹形圖狀7．樹形８．ｎ－1,O(n)９.物理（存儲）10．s->next=p-＞ｎｅxｔ;11.線性12．左指針右指針１3.gdｂeihｆca14.２ｉ2i＋115.n-116．h=s；1７.不對的１８．r->next=s；１９．對的２0.１2２1．深度優(yōu)先搜索遍歷廣度優(yōu)先搜索遍歷２２．行下標(biāo)、列下標(biāo)、非零元素值2３．相等24.3三、綜合應(yīng)用題1．（1）1616423252576782102（２）102,5２,42，８2，16,６7，3２，572.3333(1)1518151879987998545432322:1１103:111１4:11０7:0０８:019：1０(2）2n-1個(gè)，由于非葉結(jié)點(diǎn)數(shù)比葉結(jié)點(diǎn)數(shù)少一個(gè)。3．(1)原序列161５2０53647１5１６２053７６4151６2０75３64151672０5364１5716205364７１516205364（2)7715206416535(３）平均查找長度＝（1*1+2*２＋3*３）／６＝14/64．(1)初始序列４6,７9，56,3８,４0,8440，79，56，38，4０,8４40,79,56,38,79,８４４0，3８,５6，38,79,8４4０，３８,56,56，7９,８４40,38,４６，5６，79，84（２)565679384084468479384046566567938404679384084845646圖350503882131106416（2)三次;四次６．(１)3次(２）4次(３）9696759813010585501100512060圖５四、程序填空題1.(1）maｌｌoｃ(sｉｚeｏf(stｒｕcｔnodｅ))(2)ｒeaｒ->ｎexｔ=p（3)p2.（１)p（2）q=p(3）(NOＤＥ*)maｌloc(sizeof(ＮOＤＥ）)（４）p(5）q=ｐ３.（１)j<i-1（２)ｑ＝q->neｘt(3）q－>ｎext(4）q->nｅxｔ(5）p4．(１）Iｎordｅr（BT->ｌeｆt)(２)prｉntf(“%c”,ＢT->ｄaｔa）（3)Inｏrｄer(BＴ->righｔ)期末綜合練習(xí)三一、單項(xiàng)選擇題1.在C語言中，順序存儲長度為３的字符串，需要占用（)個(gè)字節(jié)。A．4Ｂ.3C2.數(shù)據(jù)元素是數(shù)據(jù)的基本單位，它()。A.只能有一個(gè)數(shù)據(jù)項(xiàng)組成B．至少有二個(gè)數(shù)據(jù)項(xiàng)組成C.可以是一個(gè)數(shù)據(jù)項(xiàng)也可以由若干個(gè)數(shù)據(jù)項(xiàng)組成D.至少有一個(gè)數(shù)據(jù)項(xiàng)為指針類型３．串函數(shù)SｔrＣaｔ(a,ｂ）的功能是進(jìn)行串(）。A.比較Ｂ.復(fù)制C.賦值D．連接4．線性表的順序結(jié)構(gòu)中，(）。A.邏輯上相鄰的元素在物理位置上不一定相鄰B．?dāng)?shù)據(jù)元素是不能隨機(jī)訪問的C.邏輯上相鄰的元素在物理位置上也相鄰Ｄ．進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高5．一棵有ｎ個(gè)結(jié)點(diǎn)采用鏈?zhǔn)酱鎯Φ亩鏄渲校灿?）個(gè)指針域?yàn)榭铡.n+１B．ｎC．n-1D.n-26.以下表中可以隨機(jī)訪問的是（）。A．單向鏈表B．雙向鏈表C．單向循環(huán)鏈表D.順序表7.設(shè)一棵哈夫曼樹共有n個(gè)非葉結(jié)點(diǎn),則該樹有(）個(gè)葉結(jié)點(diǎn)。A．nB．n+1Ｃ8.設(shè)順序存儲的線性表長度為n,對于刪除操作，設(shè)刪除位置是等概率的,則刪除一個(gè)元素平均移動元素的次數(shù)為()。A．（n＋１)/２Ｂ.nC．2ｎD．n-i9.從一個(gè)棧頂指針為ｔｏp的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí),用變量ｘ保存被刪結(jié)點(diǎn)的值,則執(zhí)行(）。A．x=top->ｄata；top=topnext;B.ｘ=top->daｔa;C.tｏｐ=ｔop－＞next；x=toｐ->daｔa;D．ｔｏｐ=top->next;ｘ=data;１0.設(shè)tｏp是一個(gè)鏈棧的棧頂指針，棧中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域daｔa和指針域nｅxt組成，設(shè)用x接受棧頂元素,則出棧操作為(）。Ａ．x=top－>data;ｔop=toｐ->ｎext；B．top=top->nexｔ;ｘ=tｏｐ－>data;Ｃ．x=tｏp->nｅxｔ;tｏp=ｔop->dａt(yī)ａ;D．top->neｘｔ=tｏｐ;x=top->data;11．一棵完全二叉樹共有5層，且第５層上有六個(gè)結(jié)點(diǎn)，該樹共有()個(gè)結(jié)點(diǎn)。A．30B.20Ｃ12．以下說法對的的是(）。A.隊(duì)列是后進(jìn)先出Ｂ.棧的特點(diǎn)是后進(jìn)后出Ｃ.棧的刪除和插入操作都只能在棧頂進(jìn)行Ｄ．隊(duì)列的刪除和插入操作都只能在隊(duì)頭進(jìn)行13．在一個(gè)無向圖中,所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的(）倍。A.3B．2.５C14.串函數(shù)StrCmp(“abA”,”ａba”）的值為（）。A.1B.0C．“abＡaｂa”D15.已知如圖1所示的一個(gè)圖,若從頂點(diǎn)Ｖ1出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則也許得到的一種頂點(diǎn)序列為（)。A．V1Ｖ２V4V８V5Ｖ3V６V7Ｂ．V１V2Ｖ4V５V８V3V6V7C．V１V２V4V8Ｖ3Ｖ5V６V7D．V1V3V6Ｖ7V２V４V5V8V6V6V7V1V2V3V8V4V5圖１１6．設(shè)有一個(gè)12階的對稱矩陣Ａ,采用壓縮存儲方式將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組b中(矩陣Ａ的第一個(gè)元素為ａ1,１,數(shù)組b的下標(biāo)從１開始)，則矩陣A中第4行的元素在數(shù)組b中的下標(biāo)i一定有（)。Ａ.7≤i≤10Ｂ．1１≤i≤15C．9≤i≤14D．6≤ｉ≤917.已知如圖2所示的一個(gè)圖,若從頂點(diǎn)a出發(fā),按廣度優(yōu)先搜索法進(jìn)行遍歷，則也許得到的一種頂點(diǎn)序列為（)。Ａ.abcedｆＢ.aｂceｆdC．a(chǎn)ebcfｄＤ.acfｄebbdbdfeca圖21８.已知一個(gè)圖的邊數(shù)為m,則該圖的所有頂點(diǎn)的度數(shù)之和為（)。A．2mB．mＣ．2m+1D.m/2１9.對二叉排序樹進(jìn)行（）遍歷，可以使遍歷所得到的序列是有序序列。A.按層次Ｂ．后序C.中序D．前序20．以下說法不對的的是(）。A.連通圖Ｇ一定存在生成樹B．連通圖Ｇ的生成樹中一定包含Ｇ的所有頂點(diǎn)Ｃ．連通圖G的生成樹中不一定包含G的所有邊Ｄ.連通圖G的生成樹可以是不連通的2１．在有序表{2，4,７,14,34，4３,47，６４,7５,80,90，９７，120}中，用折半查找法查找值80時(shí)，經(jīng)(）次比較后查找成功。A.4B.2C2２.散列查找的原理是（）。A.在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立擬定的相應(yīng)關(guān)系B.按待查記錄的關(guān)鍵字有序的順序方式存儲C．按關(guān)鍵字值的比較進(jìn)行查找Ｄ.基于二分查找的方法23．有一個(gè)長度為9的有序表，按折半查找對該表進(jìn)行查找,在等概率情況下查找成功的平均比較次數(shù)為()。A．25/１0Ｂ.25／９C24．排序過程中，每一趟從無序子表中將一個(gè)待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到所有排好序?yàn)橹梗撆判蛩惴ㄊ?)。A．直接插入排序Ｂ．快速排序Ｃ．冒泡排序D.選擇排序25.排序算法中,從未排序序列中依次取出元素與已排序序列（初始為空)中的元素進(jìn)行比較（規(guī)定比較次數(shù)盡量少）,然后將其放入已排序序列的對的位置的方法是（）。A．冒泡B.直接插入Ｃ．折半插入D.選擇排序26．采用順序查找法對長度為n的線性表進(jìn)行查找(不采用表尾設(shè)監(jiān)視哨的方法），最壞的情況下要進(jìn)行（)次元素間的比較。A．n+２B．ｎC．n－1D.ｎ／227．一組記錄的關(guān)鍵字序列為（46，79,56，３8,4０，84）,運(yùn)用快速排序,以第一個(gè)關(guān)鍵字為分割元素,通過一次劃分后結(jié)果為()。Ａ．40，３８,46，7９，56,8４B.40，３8，４6，５6，７9，84Ｃ.40，３８，46，８４，56，７９D.38，４0，４6,56,79,８4２8.如圖3所示。若從頂點(diǎn)ａ出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷,則也許得到的頂點(diǎn)序列為()。ababecdhgfB．ａebcghdfC.ａｅdfbcgｈD.ａbｅcdfｇh圖３29.排序方法中,從尚未排序序列中挑選元素,并將其依次放入已排序序列（初始為空）的一端的方法,稱為（)排序。Ａ．歸并B．插入Ｃ.快速D．選擇30.一棵哈夫曼樹總共有２３個(gè)結(jié)點(diǎn)，該樹共有（)個(gè)葉結(jié)點(diǎn)（終端結(jié)點(diǎn))A.１0B.1３C．11二、填空題1.在二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，通常每個(gè)結(jié)點(diǎn)中設(shè)立三個(gè)域,它們是＿_(dá)___＿_(dá)、、右指針。2.通常數(shù)據(jù)的邏輯結(jié)構(gòu)涉及＿＿_(dá)_、_＿_(dá)_、____、___＿四種類型。3.一棵二叉樹中順序編號為i的結(jié)點(diǎn)，若它存在左、右孩子，則左、右孩子編號分別為＿_(dá)____、_＿＿_(dá)____。4.設(shè)有一個(gè)單向鏈表,結(jié)點(diǎn)的指針域?yàn)閚ext,頭指針為hｅad,ｐ指向尾結(jié)點(diǎn),為了使該單向鏈表改為單向循環(huán)鏈表，可用語句＿_(dá)_＿_(dá)＿_(dá)＿。5.串的兩種最基本的存儲方式是___＿_(dá)__＿和________。6.設(shè)有一個(gè)單向循環(huán)鏈表,頭指針為ｈｅad，鏈表中結(jié)點(diǎn)的指針域?yàn)閚exｔ,p指向尾結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn),若要刪除尾結(jié)點(diǎn),得到一個(gè)新的單向循環(huán)鏈表,可執(zhí)行操作＿＿＿_(dá)_＿_(dá)_。7.一棵有2ｎ-1個(gè)結(jié)點(diǎn)的二叉樹,其每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為2，則該樹共有_＿_(dá)____個(gè)葉結(jié)點(diǎn)。8.在一個(gè)鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的指針域?yàn)閚ｅxｔ，則插入一個(gè)s所指結(jié)點(diǎn)的操作為_＿_(dá)___＿_(dá)；r=s；9.對于一棵具有ｎ個(gè)結(jié)點(diǎn)的二叉樹，其相應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)中共有_＿_(dá)＿_(dá)＿_(dá)_個(gè)指針域?yàn)榭铡?0．循環(huán)隊(duì)列的隊(duì)頭指針為f，隊(duì)尾指針為r,當(dāng)___＿＿時(shí)表白隊(duì)列為空。11．＿＿_(dá)＿_(dá)___遍歷二叉排序樹可得到一個(gè)有序序列。12．“Ａ”在存儲時(shí)占_____＿_(dá)＿個(gè)字節(jié)。１３.如圖4所示的二叉樹,其后序遍歷序列為。eefgibachd圖414．一棵二叉樹沒有單分支結(jié)點(diǎn)，有6個(gè)葉結(jié)點(diǎn),則該樹總共有_____＿_(dá)＿個(gè)結(jié)點(diǎn)。1５．如圖5所示的二叉樹,其先序遍歷序列為_______＿_(dá)。ggfabdec圖５1６．按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有___＿、__＿_(dá)、____三種。１7．圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是_____＿的。(回答對的或不對的)18．把數(shù)據(jù)存儲到計(jì)算機(jī)中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_＿_(dá)___＿_(dá)結(jié)構(gòu)。19．二叉樹為二叉排序的充足必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說法是_＿_(dá)___＿_(dá)__的。（回答對的或不對的)2０.對記錄序列排序是指按記錄的某個(gè)關(guān)鍵字排序，記錄序列按__＿_(dá)＿＿_(dá)＿_(dá)排序結(jié)果是唯一的。21．二叉樹為二叉排序的充足必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說法是＿_(dá)____＿_(dá)__的。(回答對的或不對的)２２．按某關(guān)鍵字對記錄序列排序,若在排序前和排序后仍保持它們的前后關(guān)系，則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。2３．根據(jù)搜索方法的不同,圖的遍歷有＿_(dá)_＿、＿_(dá)__兩種方法。三、綜合題1.設(shè)查找表為(１６,15,２0,5３,6４,７)（１)用冒泡法對該表進(jìn)行排序（規(guī)定升序排列)，寫出每一趟的排序過程,通常對n個(gè)元素進(jìn)行冒泡排序要進(jìn)行多少趟冒泡?第ｊ趟要進(jìn)行多少次元素間的比較？（2）在排序后的有序表的基礎(chǔ)上,畫出對其進(jìn)行折半查找所相應(yīng)的鑒定樹（規(guī)定以數(shù)據(jù)元素作為樹結(jié)點(diǎn)）。2.（1)已知某二叉樹的后序遍歷序列是deｂｃａ,中序遍歷序列是dbeac，試畫出該二叉樹（2）若上述二叉樹的各個(gè)結(jié)點(diǎn)的字符分別代表不同的整數(shù)（其中沒有相等的），并恰好使該樹成為一棵二叉排序樹，試給出a、b、c、d、ｅ的大小關(guān)系(３)給出該樹的前序遍歷序列3.(1)設(shè)有查找表｛５,14,2,６,１8,７，4,1６,3｝,依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹。（2)說明如何由序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果,對上述二叉排序給出中序遍歷的結(jié)果。4．(1)設(shè)有一個(gè)整數(shù)序列{40，2８，6,72,100,3,54｝依次取出序列中的數(shù),構(gòu)造一棵二叉排序樹（２)對上述二叉排序樹,在等概率條件下，求成功查找的平均查找長度5.（1)對給定權(quán)值2,1,３,３，4，5，構(gòu)造哈夫曼樹。（２）同樣用上述權(quán)值構(gòu)造另一棵哈夫曼樹，使兩棵哈夫曼樹有不同的高度,并分別求兩棵樹的帶權(quán)途徑長度。６．（１)運(yùn)用篩選過程把序列{４2，8２，６7,102，1６，32,57，52}建成堆(小根堆),畫出相應(yīng)的完全二叉樹(不規(guī)定中間過程）(2)寫出對上述堆相應(yīng)的完全二叉樹進(jìn)行中序遍歷得到的序列四、程序填空題１.設(shè)線性表為（6,10，1６,4),以下程序用說明結(jié)構(gòu)變量的方法建立單向鏈表，并輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)。＃ｄefｉnｅNＵLL0vｏidmａin(）{ＮＯＤEa，ｂ，ｃ，d,*hｅad，*p;a.datａ=6;b.ｄａt(yī)a=１0;c.dａt(yī)a=16;d.data=4;／*d是尾結(jié)點(diǎn)＊/hｅad=(1);a.ｎexｔ=&b;b.next=&c;c．nｅxt=&d;（２）;/*以上結(jié)束建表過程＊／ｐ＝ｈead;／*p為工作指針，準(zhǔn)備輸出鏈表*/dｏ{pｒintf(“%d\n”,（3)）;(4）;}whiｌe(（5）);}2.以下函數(shù)在a[0]到a[n-１]中,用折半查找算法查找關(guān)鍵字等于k的記錄,查找成功返回該記錄的下標(biāo),失敗時(shí)返回－1,完畢程序中的空格ｔyｐｅdefstrｕct{intkeｙ;……｝N