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

數(shù)據(jù)結(jié)構(gòu)(本）期末綜合練習(xí)202３年6月為了幫助同學(xué)們進行期末復(fù)習(xí)，特擬定以下三套期末綜合練習(xí)題,望同學(xué)們逐個認真完畢。數(shù)據(jù)結(jié)構(gòu)(本)期末綜合練習(xí)一一、單項選擇題1.針對線性表，在存儲后假如最常用的操作是取第i個結(jié)點及其前驅(qū),則采用(）存儲方式最節(jié)省時間。A.單鏈表B．雙鏈表C.單循環(huán)鏈表D．順序表２.線性表采用鏈式存儲時，其地址()。A.一定是不連續(xù)的Ｂ．必須是連續(xù)的C.可以連續(xù)也可以不連續(xù)D．部分地址必須是連續(xù)的3.數(shù)據(jù)結(jié)構(gòu)中,與所使用的計算機無關(guān)的是數(shù)據(jù)的(）結(jié)構(gòu)。Ａ.物理B.存儲Ｃ.邏輯與物理D．邏輯4.帶頭結(jié)點的單向鏈表的頭指針為heａｄ,該鏈表為空的鑒定條件是（）的值為真。Ａ．ｈead==NＵLLＢ．ｈeａｄ->nｅxt＝＝headC．heａｄ-＞nexｔ==NＵLＬD.head==heａd－>next5．以下特性中，（)不是算法的特性。A．有窮性B．?dāng)M定性C．可行性Ｄ.有0個或多個輸出6．設(shè)順序存儲的線性表長度為n,對于插入操作，設(shè)插入位置是等概率的,則插入一個元素平均移動元素的次數(shù)為()。A.ｎ／2B.nC．n－1Ｄ．n-ｉ＋1７．設(shè)有一個長度為n的順序表，要在第i個元素之前（也就是插入元素作為新表的第i個元素)，則移動元素個數(shù)為（）。A．n-i+1Ｂ．n－iC.n-i-1Ｄ.i8．一個棧的進棧序列是５，６，７,８，則棧的不也許的出棧序列是（）（進出棧操作可以交替進行）A.5,8,6,7Ｂ.7，6,8，5C．7，６,５，８Ｄ．８，7，6，５9．棧的插入刪除操作在（)進行。Ａ.棧底B.任意位置C.指定位置D．棧頂１0.棧和隊列的相同點是（)。Ａ.都是后進先出Ｂ．都是后進后出Ｃ．邏輯結(jié)構(gòu)與線性表不同D.邏輯結(jié)構(gòu)與線性表相同,都是操作規(guī)則受到限制的線性表１1．以下說法對的的是（)。A．棧的特點是先進先出，隊列的特點是先進后出B．棧和隊列的特點都是先進后出C．棧的特點是先進后出，隊列的特點是先進先出D.棧和隊列的特點都是先進先出１2．在C語言中,運用數(shù)組ａ存放字符串“Heｌlｏ”，以下語句中對的的是（)。A．ｃhaｒa[1０]=“Hｅllo”;B．ｃhara[10];ａ=“Helｌo”;C.chara[10］＝‘Hello’;Ｄ．chara[1０]=｛‘H’,’e’,’l’,’l’，’o’};1３.元素2,４,６,8按順序依次進棧，則該棧的不也許輸出序列是（）(進棧出?？梢越惶孢M行)。A．8,6，4，2B．２，4,6，8C．４，2,8，6D．8,６,２，414.設(shè)有一個1５階的對稱矩陣A,采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中。（矩陣A的第一個元素為ａ1,1,數(shù)組b的下標(biāo)從1開始），則數(shù)組元素b[１3]相應(yīng)Ａ的矩陣元素是(）。A.a5,３B.a6，4C．a(chǎn)7,2Ｄ15.設(shè)有一個1５階的對稱矩陣A,采用壓縮存儲的方式,將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始）,則矩陣中元素ａ７,６在一維數(shù)組B中的下標(biāo)是()。A.42Ｂ.13C16．一棵完全二叉樹共有30個結(jié)點,則該樹一共有（)層(根結(jié)點所在層為第一層)。A.6B.4Ｃ.３D17.串函數(shù)StｒCmp（“d”,“D”）的值為（)。A．0B.1C18．以下說法對的的是(）。A．連通圖Ｇ的生成樹中不一定包含G的所有頂點B.連通圖G的生成樹中一定要包含Ｇ的所有邊C.連通圖G的生成樹一定是唯一的D．連通圖G一定存在生成樹19.在一棵二叉樹中，若編號為i的結(jié)點存在右孩子,則右孩子的順序編號為()。A.2iB．2i-1Ｃ20.對二叉排序樹進行（)遍歷，遍歷所得到的序列是有序序列。A.按層次B.前序C.中序D．后序21.設(shè)一棵有n個結(jié)點采用鏈式存儲的二叉樹，則該樹共有()個指針域為空。A．２nB.2n＋1Ｃ.2n+２２2．以下排序算法中，在一趟排序過程中,除了其它相關(guān)操作外，只進行一次元素間的互換的算法是（）。Ａ．直接選擇Ｂ.冒泡C.直接插入D．折半插入2３.已知如圖１所示的一個圖，若從頂點a出發(fā),按廣度優(yōu)先搜索法進行遍歷,則也許得到的一種頂點序列為（）。A.aｂcedfB.ａbｃefdC．ａebcfdＤ.acｆdebbbdfeca圖124．對長度為n的線性表進行順序查找，在等概率情況下，平均查找長度為(）。A.nＢ．（n+1)／２C.2n25.在有序表{1，3，８，13,3３，42，46,６３，7６,７８，86,９7,10０}中,用折半查找值86時，經(jīng)()次比較后查找成功。A.6B．3C２6.如圖若從頂點a出發(fā)按深度優(yōu)先搜索法進行遍歷，則也許得到的頂點序列為(）。ababecdfgB.aedcｂｇfＣ.ａｃfebdgＤ.aecｂdgf2７．有一個長度為10的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為(）。Ａ．29/1０B．３1/10C28.一棵哈夫曼樹有1２個葉子結(jié)點(終端結(jié)點),該樹總共有（)個結(jié)點。A．22B．２1C.23Ｄ.29．一組記錄的關(guān)鍵字序列為（３7,７0，４7，２9，31，8５)，運用快速排序,以第一個關(guān)鍵字為分割元素,通過一次劃分后結(jié)果為（）。Ａ．31，２9,37,47，７0,85Ｂ．29，31，３7，47，7０,85Ｃ.31,2９，３７,7０，47，８5D.31,29，37，８5，47,703０.隊列的刪除操作在（）進行。A．隊頭B.隊尾C．隊頭或隊尾D.在任意指定位置得分評卷人二、填空題1．把數(shù)據(jù)存儲到計算機中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為＿______＿結(jié)構(gòu)。2．設(shè)有一個不帶頭結(jié)點的單向循環(huán)鏈表,結(jié)點的指針域為nｅxt,指針p指向尾結(jié)點,現(xiàn)要使p指向第一個結(jié)點，可用語句__＿＿_＿__。３．結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系稱為_＿____＿_結(jié)構(gòu)。４.要在一個帶頭結(jié)點的單向循環(huán)鏈表中刪除頭結(jié)點，得到一個新的不帶頭結(jié)點的單向循環(huán)鏈表，若結(jié)點的指針域為ｎeｘt，頭指針為head,尾指針為p,，則可執(zhí)行head=heaｄ－>ｎexｔ；________。５．在雙向鏈表中,每個結(jié)點有兩個指針域,一個指向＿＿＿__＿＿＿,另一個指向＿＿_____＿_。6．設(shè)有一個非空的鏈棧，棧頂指針為hｓ，要進行出棧操作,用ｘ保存出棧結(jié)點的值，棧結(jié)點的指針域為nexｔ，數(shù)據(jù)域為ｄａt(yī)ａ，則可執(zhí)行x=＿__＿_＿__;和hs=___＿___＿；7．設(shè)有一個頭指針為head的單向鏈表,p指向表中某一個結(jié)點,且有p->ｎext=＝ＮULL,通過操作___＿__＿_,就可使該單向鏈表構(gòu)導(dǎo)致單向循環(huán)鏈表。8.循環(huán)隊列的最大存儲空間為MaxSize，隊頭指針為f，隊尾指針為r，當(dāng)__＿＿___＿時表白隊列已滿。9.從一個棧頂指針為h的鏈棧中刪除一個結(jié)點時,用x保存被刪結(jié)點的值，可執(zhí)行x=h->dａt(yī)ａ;和________。（結(jié)點的指針域為nｅxt）１0.程序段intcount=0;char*s=”AＢCＤ”;wｈile(*s!=’＼0’執(zhí)行后cｏunt=___＿____１１．兩個串相等的充足必要條件是＿___＿＿_＿＿＿。12.一棵二叉樹總結(jié)點數(shù)為11,葉結(jié)點數(shù)為5,該樹有____＿_＿_個雙分支結(jié)點,__＿_____個單分支結(jié)點。13．對二叉樹的遍歷可分為___＿____、、、四種不同的遍歷順序。14．設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點的編號為偶數(shù)，該葉節(jié)點的雙親結(jié)點的編號為９,該完全二叉樹一共有＿＿____＿＿個結(jié)點。1５．一棵有n個葉結(jié)點的二叉樹，其每一個非葉結(jié)點的度數(shù)都為2,則該樹共有___＿__＿個結(jié)點。1６．雙向循環(huán)鏈表中，p指向表中某結(jié)點,則通過p可以訪問到p所指結(jié)點的直接后繼結(jié)點和直接前驅(qū)結(jié)點，這種說法是_＿_＿_＿＿＿的（回答對的或不對的)。１7.一棵有１4個結(jié)點的完全二叉樹，則它的最高層上有__＿_＿__個結(jié)點。１8.棧和隊列的操作特點分別是________和___＿＿＿__。１９.如圖2所示的二叉樹,其先序遍歷序列為_＿___＿_＿_。efefgibachd圖22０.折半查找只合用于存儲的有序表。21．哈希函數(shù)是記錄關(guān)鍵字值與該記錄＿＿____之間所構(gòu)造的相應(yīng)關(guān)系。22．深度為k的二叉樹最多有結(jié)點。23.二叉樹排序中任一棵子樹都是二叉排序樹,這種說法是＿__＿___的。(回答對的或不對的)24.串的兩種最基本的存儲方式是_______＿和____＿_＿_。得分評卷人三、綜合題1.設(shè)一組記錄的關(guān)鍵字序列為（49,83，59,4１,４３，４7)，采用堆排序算法完畢以下操作：（規(guī)定小根堆,并畫出中間過程)(１）以二叉樹描述6個元素的初始堆(２)以二叉樹描述逐次取走堆頂元素后，經(jīng)調(diào)整得到的５個元素、4個元素的堆2．設(shè)有一個不帶頭結(jié)點的單向鏈表,頭指針為hｅad，結(jié)點類型為NOＤE，每個結(jié)點包含一個數(shù)據(jù)域ｄａt(yī)a和一個指針域next,該鏈表有兩個結(jié)點,p指向第二個結(jié)點(尾結(jié)點）,按以下規(guī)定寫出相應(yīng)語句（不規(guī)定完整程序，(1)、(2)、（3)、（４）是一個連續(xù)的過程）。(1)新開辟一個結(jié)點,使指針s指向該結(jié)點，結(jié)點的數(shù)據(jù)成員datａ賦值為1（2)把該結(jié)點插入鏈表的尾部，釋放指針s的指向(3）刪除鏈表的第一個結(jié)點(4）已知p１指向另一個新結(jié)點，把它插入到p所指結(jié)點和尾結(jié)點之間3．設(shè)有序表為(１3,19,２5，36，4８，51，6３,84,91,116,１35，２00)，元素的下標(biāo)依次為1，２，……，１2。（１）說出有哪幾個元素需要通過4次元素間的比較才干成功查到（2）畫出對上述有序表進行折半查找所相應(yīng)的鑒定樹(樹結(jié)點用下標(biāo)表達)(３)設(shè)查找元素5,需要進行多少次元素間的比較才干擬定不能查到４．(１)設(shè)有序列{１０,12,15,19,2２,２5,10０,1３0，１５0,200｝畫出對上述序列進行折半查找的鑒定樹（以序列中的元素作為樹的結(jié)點)（2）為了成功查找到１00需要進行多少次元素間的比較？為了查找９，通過多少次元素間的比較可知道查找失?。?.（1)對給定數(shù)列｛７,１6,4,8,20，9，6，18，5},依次取數(shù)列中的數(shù)據(jù)，構(gòu)造一棵二叉排序樹。(2)對一個給定的查找值，簡述針對二叉排序樹進行查找的算法環(huán)節(jié),在上述二叉樹中查找元素20共要進行多少次元素的比較？6.（１)設(shè)有查找表｛5,14,2,6,１８，7,4,１６,3},依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹。（２）說明如何由序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果，對上述二叉排序給出中序遍歷的結(jié)果。四、程序填空題1．以下冒泡法程序?qū)Υ娣旁赼[1］,a[2]，……，a[ｎ]中的序列進行排序，完畢程序中的空格部分,其中ｎ是元素個數(shù),規(guī)定按升序排列。vｏidbsｏrｔ(ＮOＤEa［],intn)｛ＮOＤEteｍｐ;inti,j,fｌag；for(j=1;（1）；ｊ++);{flａg=０;for(i=１;(2）;i++）iｆ(a[ｉ].key>a[i+1].key）{ｆｌaｇ=1;temp=a［ｉ];(3);(4);}iｆ(ｆlag==0)bｒeaｋ;}}程序中flag的功能是（５）2．以下程序是先序遍歷二叉樹的遞歸算法的程序，完畢程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為lｅft和ｒｉght,數(shù)據(jù)域dａt(yī)ａ為字符型，BＴ指向根結(jié)點)。ｖｏiｄPreordeｒ(sｔructBＴreｅNode*BT）{iｆ（BＴ!=NＵLＬ){(１）;（2）;（3）;}}3．設(shè)線性表為（６，10，16,４)，以下程序用說明結(jié)構(gòu)變量的方法建立單向鏈表,并輸出鏈表中各結(jié)點中的數(shù)據(jù)。＃ｄefinｅNULL０ｖoｉdmaｉｎ()｛NODEa，b，c,ｄ，*heａd,＊ｐ;a.datａ=6;b.ｄａt(yī)a＝１0；ｃ.data=16;d.ｄaｔa=4;／*ｄ是尾結(jié)點*/heａｄ=(1)；ａ.neｘt＝&b;ｂ.neｘt=&c;c．nｅxt=&d；（2）;／*以上結(jié)束建表過程*／p=head;/*p為工作指針，準備輸出鏈表＊/do{priｎｔｆ（“%d＼ｎ”,（3）);（４)；｝ｗhilｅ(（５))；}4.以下程序是中序遍歷二叉樹的遞歸算法的程序,完畢程序中空格部分(樹結(jié)構(gòu)中左、右指針域分別為ｌeｆt和rｉgｈt,數(shù)據(jù)域dａt(yī)a為字符型，ＢT指向根結(jié)點）。ｖoｉdInoｒdｅｒ(strucｔBTreeＮode＊ＢT)｛if(BＴ!=NＵLL)｛(1）;（2);(3）;}}答案一、單項選擇題1．D2.C3.D4.C5.D6．A7.A8.A9．Ｄ10．D11．C1２．A1３．D14.Ａ１５.C16．Ｄ1７．B18.D19.D2０．C２1．Ｄ２２.Ａ23．B2４、B25.D26．A2７.Ａ2８.C29．A30．A二、填空題1.物理（存儲）3．線性5．結(jié)點的直接后繼結(jié)點的直接前驅(qū)7．p->nｅxt=hｅａd;９.ｈ=h->nexｔ;11．串長度相等且相應(yīng)位置的字符相等１3．先序、中序、后序、層次１5．2n-117.719.ａbdgcｅfhi21．存儲地址２3．對的2.p=ｐ->nｅxｔ;4．p->neｘt＝heaｄ；6．hs->data；hs->neｘt;８．（r+1）％MaxSｉｚe=ｆ10.４12.４；２１4．1８16．對的18.先進后出（后進先出)先進先出（后進后出）20．順序存儲結(jié)構(gòu)2２.２k-1２4.順序存儲鏈式存儲三、綜合題4959495983414347834741435949498341434783435949414347834959414759(1)圖3594759474149834347414741835943494347415983494747414383495959594741438349圖42．（1)s＝（NOＤＥ＊）mallｏｃ（sｉzｅoｆ（NODE));s->dａt(yī)a=1;(2）p-＞ｎext=s;s-＞neｘt=NULL;fｒee（ｓ)（３)head=head－>neｘt；(4）p１->nｅxt＝p->nexｔ；ｐ->ｎext=p1；3．（１)19,４8,８4,１１6,200（2)4471285211110639圖５（３）3次2212221213019150251520010010(１）（２）4次;3次５．46468957162018圖６(2)先將給定值與根結(jié)點比較，若相等則查找成功，否則若小于根結(jié)點則在左子樹中繼續(xù)查找，大于根結(jié)點在右子樹中查找，查找20共進行3次比較。６.24246167318514圖6(2)中序遍歷中序2，3,4,5,６，7，14，16，18四、程序填空題１.(1)j<=n-１（2)ｉ<=n-j（3)a［i]＝a[i+１](4）a[i+1]=temp（5)當(dāng)某趟冒泡中沒有出現(xiàn)互換則已排好序,結(jié)束循環(huán)２.(1）pｒiｎtf（“%ｃ”,ＢT->ｄaｔａ）（2）Preorｄer(BＴ->lｅft)(3）Preoｒder(ＢT->rｉght)3．(1)&a(2）ｄｎeｘt=ＮULL（3）ｐ-＞daｔａ(4)p＝ｐ－>next(5)ｐ!=NULL4．(1)Ｉnｏrｄｅr(ＢT->ｌeft)(２)priｎｔf（“%c”,BT->dａt(yī)a)(3）Inoｒder(BT－＞right)數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)二202３年6月一、單項選擇題1．?dāng)?shù)據(jù)元素是數(shù)據(jù)的基本單位，它（)。A.只能有一個數(shù)據(jù)項組成B.至少有二個數(shù)據(jù)項組成Ｃ.可以是一個數(shù)據(jù)項也可以由若干個數(shù)據(jù)項組成D．至少有一個數(shù)據(jù)項為指針類型2.一種邏輯結(jié)構(gòu)()存儲結(jié)構(gòu)。Ａ.可以有不同的B.只能有唯一的C．的數(shù)據(jù)元素在計算機中的表達稱為Ｄ.的數(shù)據(jù)元素之間的關(guān)系稱為3.線性表的順序結(jié)構(gòu)中，(）。Ａ．邏輯上相鄰的元素在物理位置上不一定相鄰B．?dāng)?shù)據(jù)元素是不能隨機訪問的C．邏輯上相鄰的元素在物理位置上也相鄰D.進行數(shù)據(jù)元素的插入、刪除效率較高4．以下說法中不對的的是（)。Ａ.雙向循環(huán)鏈表中每個結(jié)點需要包含兩個指針域B.已知單向鏈表中任一結(jié)點的指針就能訪問到鏈表中每個結(jié)點Ｃ．順序存儲的線性鏈表是可以隨機訪問的D.單向循環(huán)鏈表中尾結(jié)點的指針域中存放的是頭指針５.以下表中可以隨機訪問的是()。Ａ．單向鏈表Ｂ.雙向鏈表C．單向循環(huán)鏈表D．順序表6．雙向循環(huán)鏈表結(jié)點的數(shù)據(jù)類型為:ｓtructnode｛ｉｎtｄａt(yī)a;stｒｕctnode*next；／*指向直接后繼*／struｃtｎodｅ*prior;};設(shè)p指向表中某一結(jié)點,要顯示p所指結(jié)點的直接前驅(qū)結(jié)點的數(shù)據(jù)元素，可用操作()。A.printf(“%ｄ”，ｐ-＞ｎext-＞dａt(yī)ａ);B.ｐrintf(“%d”,p->prｉor->data);C．prｉntf(“％d”,p->priｏr->next);Ｄ.ｐrintf(“％d”,p->data);7.設(shè)順序存儲的線性表長度為n，對于刪除操作，設(shè)刪除位置是等概率的,則刪除一個元素平均移動元素的次數(shù)為（）。A.（ｎ+1）/2B．nC.２nD．n-ｉ8．一個棧的進棧序列是eｆgｈ,則棧的不也許的出棧序列是(）(進出棧操作可以交替進行）。A.ｈgfｅB.ｇfｅhC．fｇeｈＤ.eｈfｇ9.設(shè)ｔoｐ是一個鏈棧的棧頂指針,棧中每個結(jié)點由一個數(shù)據(jù)域ｄａt(yī)a和指針域nｅｘt組成,設(shè)用x接受棧頂元素,則出棧操作為（)。A.x=toｐ->ｄaｔa；top=top->nｅxt;Ｂ.top=ｔｏp->next;ｘ=ｔop->datａ;C.ｘ=toｐ-＞ｎext;toｐ=tｏp->data;D.toｐ->nｅxt=top;ｘ=ｔop－>datａ;１0．設(shè)top是一個鏈棧的棧頂指針，棧中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成,設(shè)用ｘ接受棧頂元素，則取棧頂元素的操作為（）。A.tｏｐ-＞ｄａt(yī)a=x;B.top=top－>next;C.x=top->ｄata;D.ｘ=toｐ->data;ｔｏp=tｏp－>nｅxt;11.以下說法對的的是（）。Ａ.隊列是后進先出Ｂ．棧的特點是后進后出C.棧的刪除和插入操作都只能在棧頂進行D．隊列的刪除和插入操作都只能在隊頭進行12.以下說法不對的的是（)。A．棧的特點是后進先出Ｂ.隊列的特點是先進先出C．棧的刪除操作在棧底進行，插入操作在棧頂進行D.隊列的插入操作在隊尾進行，刪除操作在隊頭進行13．串函數(shù)StrＣmp(“abA”,”ａｂa”)的值為（)。Ａ．１B.０C.“abＡａba”D1４.chａr*ｐ;ｐ=ＳｔｒCａt(yī)(“AＢD”,”ABＣ”）；Priｎtf（“%ｓ”,ｐ);的顯示結(jié)果為(）。A.-１B.ABDABCＣ．AＢD.115.設(shè)有一個１2階的對稱矩陣A,采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組ｂ中(矩陣A的第一個元素為a1,１，數(shù)組b的下標(biāo)從1開始）,則矩陣Ａ中第4行的元素在數(shù)組b中的下標(biāo)i一定有（)。A、7≤i≤10B、1１≤ｉ≤１5Ｃ、9≤ｉ≤１4D、6≤i≤16.深度為５的滿二叉樹至多有（)個結(jié)點(根結(jié)點為第一層）Ａ.40B.３１Ｃ．34Ｄ1７．已知一個圖的邊數(shù)為m,則該圖的所有頂點的度數(shù)之和為（)。A.2mB.mC.2m+1D.m/21８．已知一個圖的所有頂點的度數(shù)之和為m，則該圖的邊數(shù)為()。A．２mB．mＣ.2m＋1Ｄ．m/２19.以下說法不對的的是()。A.連通圖G一定存在生成樹B.連通圖Ｇ的生成樹中一定包含G的所有頂點C.連通圖Ｇ的生成樹中不一定包含G的所有邊Ｄ.連通圖Ｇ的生成樹可以是不連通的20．以下說法不對的的是()。A.連通圖Ｇ的生成樹一定是唯一的B.連通圖G一定存在生成樹C.連通圖G的生成樹中一定要包含G的所有頂點Ｄ.連通圖G的生成樹一定是連通并且不包含回路２1．散列查找的原理是(）。A．在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立擬定的相應(yīng)關(guān)系B．按待查記錄的關(guān)鍵字有序的順序方式存儲Ｃ.按關(guān)鍵字值的比較進行查找D.基于二分查找的方法２2.有序表為{1，２,４,6，１0,18,2０，3２}，用課本中折半查找算法查找值18，經(jīng)()次比較后成功查到。Ａ.３B.2Ｃ．4D2３.排序過程中，每一趟從無序子表中將一個待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到所有排好序為止，該排序算法是（)。A.直接插入排序Ｂ.快速排序C.冒泡排序Ｄ．選擇排序24．在排序過程中，可以通過某一趟排序的相關(guān)操作所提供的信息，判斷序列是否已經(jīng)排好序，從而可以提前結(jié)束排序過程的排序算法是（)。A.冒泡Ｂ.選擇C．直接插入D.折半插入2５.采用順序查找法對長度為ｎ的線性表進行查找（不采用表尾設(shè)監(jiān)視哨的方法）,最壞的情況下要進行（)次元素間的比較。A.n+2B.nC．n－1Ｄ．n/226.用折半查找法,對長度為１2的有序的線性表進行查找,最壞情況下要進行（）次元素間的比較A.４B.3C．5Ｄ2７．如圖若從頂點a出發(fā)按廣度優(yōu)先搜索法進行遍歷，則也許得到的頂點序列為()。ababecdhgfB.ａeｂｃghｄfC.aedｆｂcghD．a(chǎn)becｄfｇh圖128.如圖若從頂點ａ出發(fā)按深度優(yōu)先搜索法進行遍歷，則也許得到的頂點序列為(）。bcbcgdafeＢ．a(chǎn)edｂgfcＣ．ａcfeｂdgD.ａeｃbdgf29．一棵哈夫曼樹總共有2３個結(jié)點,該樹共有（)個葉結(jié)點（終端結(jié)點)Ａ.1０B．1３Ｃ.1１30.一棵哈夫曼樹總共有25個結(jié)點,該樹共有（）個非葉結(jié)點（非終端結(jié)點)。Ａ．12B．13C．14二、填空題（每小題2分，共24分)1.通常數(shù)據(jù)的邏輯結(jié)構(gòu)涉及____、__＿_、__＿＿、____四種類型。２.結(jié)構(gòu)中的元素之間存在多對多的關(guān)系稱為_＿＿_____結(jié)構(gòu)。３.設(shè)有一個單向鏈表，結(jié)點的指針域為nｅxt，頭指針為ｈead,ｐ指向尾結(jié)點，為了使該單向鏈表改為單向循環(huán)鏈表,可用語句___＿_＿__。4.設(shè)有一個單向循環(huán)鏈表,結(jié)點的指針域為next，頭指針為ｈｅａd,指針p指向表中某結(jié)點,若邏輯表達式____＿___的結(jié)果為真，則p所指結(jié)點為尾結(jié)點。５．設(shè)有一個單向循環(huán)鏈表,頭指針為ｈead，鏈表中結(jié)點的指針域為next,ｐ指向尾結(jié)點的直接前驅(qū)結(jié)點，若要刪除尾結(jié)點，得到一個新的單向循環(huán)鏈表,可執(zhí)行操作________。6．設(shè)有一個鏈棧，棧頂指針為hs，現(xiàn)有一個s所指向的結(jié)點要入棧，則可執(zhí)行操作s->nｅxt=hs；_＿______。7．在一個鏈隊中，f和r分別為隊頭和隊尾指針,隊結(jié)點的指針域為next，則插入一個s所指結(jié)點的操作為____＿___；r=ｓ；8．在一個鏈隊中，f和r分別為隊頭和隊尾指針,隊結(jié)點的指針域為nexｔ，s指向一個要入隊的結(jié)點，則入隊操作為_＿___＿＿＿；_＿_＿____;9.循環(huán)隊列的隊頭指針為f,隊尾指針為r,當(dāng)___＿_時表白隊列為空。10．循環(huán)隊列的最大存儲空間為MaxSizｅ=6,采用少用一個元素空間以有效地判斷?？栈驐M,若隊頭指針front=4，當(dāng)隊尾指針rｅar=_＿____＿_時隊滿，隊列中共有________個元素。11.‘A‘在存儲時占________個字節(jié)?！癆”在存儲時占______＿＿個字節(jié)。12．程序段chａr*s＝”aBcＤ”;n=0;ｗhilｅ（*ｓ!＝’\0’｛if(＊ｓ>=’ａ’＆＆*s<=’z’)n++;s++；}執(zhí)行后n=___＿_＿__13.一棵二叉樹沒有單分支結(jié)點，有６個葉結(jié)點，則該樹總共有___＿____個結(jié)點。１4.一棵二叉樹中順序編號為5的結(jié)點（樹中各結(jié)點的編號與等深度的完全二叉中相應(yīng)位置上結(jié)點的編號相同）,若它存在左孩子，則左孩子的編號為______＿_。15.按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有＿＿__、_＿__、__＿_三種。１6.根據(jù)搜索方法的不同,圖的遍歷有______＿_兩種方法。１７.把數(shù)據(jù)存儲到計算機中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_＿______結(jié)構(gòu)。1８.結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為_______＿結(jié)構(gòu)。19．如圖２所示的二叉樹,其后序遍歷序列為。eefgibachd圖2２0．一棵有n個葉結(jié)點的二叉樹，其每一個非葉結(jié)點的度數(shù)都為2,則該樹共有_______個結(jié)點。21.二叉樹為二叉排序的充足必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。這種說法是__________的。(回答對的或不對的)２２.串的兩種最基本的存儲方式分別是___＿_＿_和_＿_＿____。2３．根據(jù)搜索方法的不同,圖的遍歷有_＿＿＿、＿___兩種方法24.按某關(guān)鍵字對記錄序列排序,若關(guān)鍵字的記錄在排序前和排序后仍保持它們的前后關(guān)系,則排序算法是穩(wěn)定的,否則是不穩(wěn)定的。三、綜合題１.（1）已知某二叉樹的后序遍歷序列是debca，中序遍歷序列是dbeａc,試畫出該二叉樹(２)若上述二叉樹的各個結(jié)點的字符分別代表不同的整數(shù)（其中沒有相等的）,并恰好使該樹成為一棵二叉排序樹，試給出a、b、c、d、ｅ的大小關(guān)系（3）給出該樹的前序遍歷序列2.（1)已知某二叉樹的先序遍歷序列是aecdｂ，中序遍歷序列是eaｄcb，試畫出該二叉樹（2)給出上述二叉樹的后序遍歷序列(3)若上述二叉樹的各個結(jié)點的字符分別是１，2,3，4,5，并恰好使該樹成為一棵二叉排序樹,試問a、b、c、ｄ、e的值各為多少？3.（1)設(shè)有一個整數(shù)序列{40,２8,6,72,１00,3，５４}依次取出序列中的數(shù)，構(gòu)造一棵二叉排序樹（2）對上述二叉排序樹,在等概率條件下,求成功查找的平均查找長度４.（１）給定數(shù)列｛8,17，5,9，21,１0,7,１9，6｝,依次取序列中的數(shù)構(gòu)造一棵二叉排序樹（2）對上述二叉樹給出中序遍歷得到的序列5.（1）運用篩選過程把序列{4２,8２,67，10２,1６，32,57,5２}建成堆(小根堆）,畫出相應(yīng)的完全二叉樹（不規(guī)定中間過程)(2)寫出對上述堆相應(yīng)的完全二叉樹進行中序遍歷得到的序列6．(１)以給定權(quán)重值1,２,12,13，20,25為葉結(jié)點，建立一棵哈夫曼樹（２)若哈夫曼樹有n個非葉子結(jié)點，則樹中共有多少結(jié)點。對給定的一組權(quán)重值建立的棵哈夫曼樹是否一定唯一四、程序填空題1．以下函數(shù)在a[０]到a[n-1]中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標(biāo)，失敗時返回-１,完畢程序中的空格tｙpedefstｒuct｛intkey;……}NＯDE;iｎtBinａry＿Ｓeａrｃh（ＮOＤEａ[],intｎ,intk）{inｔlow，mid,hiｇh;loｗ=0;hｉgh=n-１;whiｌe(___(１)_____){mｉd=（lｏｗ+high）/2；if(a[mｉd]．ｋey＝=k)ｒetｕrｎ__(２）__＿＿__; elseiｆ（_＿＿(3)_____)ｌow=mid+１;?eｌｓｅ__（4)______;?}＿__(５)__＿＿_;?}2．以下函數(shù)是二叉排序樹的查找算法，若二叉樹為空，則返回根結(jié)點的指針，否則，返回值是指向樹結(jié)點的結(jié)構(gòu)指針p（查找成功p指向查到的樹結(jié)點,不成功p指向為NULL）完畢程序中的空格typｅｄefstｒuｃｔＢnｏdｅ{ｉntkｅy;sｔｒuｃtＢnｏdｅ*left;ｓｔrｕctBnｏｄｅ*right;｝Ｂnｏdｅ;Bnｏde*BSearcｈ（Ｂｎoｄe*bｔ,ｉnｔk）/＊bt用于接受二叉排序樹的根結(jié)點的指針,k用以接受要查找的關(guān)鍵字*/{Bｎode*ｐ;iｆ(ｂt==___(1)_____)rｅｔurｎ(bｔ);p=bt;ｗhｉlｅ(p－>key!=＿_(２)＿＿____) {if(ｋ<ｐ->kｅｙ） ?___(3)＿＿__＿；else＿＿_(4）__＿__;?ｉf(p==ＮULL)break；}Retuｒn(＿＿_（５)___＿_);}3.以下函數(shù)為鏈隊列的入隊操作，x為要入隊的結(jié)點的數(shù)據(jù)域的值,frｏnt、rｅar分別是鏈隊列的隊頭、隊尾指針stｒuctｎode｛EｌemＴｙpedata;strucｔnode＊ｎext;}；structnode*fｒoｎt，*ｒear;vｏｉdInＱueue(ElｅｍTypeｘ){ｓtrｕctnode*ｐ;p=（stｒuctnoｄｅ*)_＿_（1)__＿__；p->datａ＝ｘ;ｐ-＞ｎexｔ=NＵLＬ；___(2)_____；rｅaｒ=__＿(3)__＿_＿;}4．以下函數(shù)為鏈隊列的出隊操作（鏈隊列帶有頭結(jié)點），出隊結(jié)點的數(shù)據(jù)域的值由x返回,front、rｅar分別是鏈隊列的隊頭、隊尾指針ｓｔrｕctnode{ＥleｍTypedata;structnoｄe＊ｎexｔ;};strｕｃtnode＊ｆrｏnｔ，*rear;ElemTypｅOuｔＱueue(){?ElｅｍＴyｐex；?if(＿__（1)_____)｛priｎｔｆ("隊列下溢錯誤！\n"）;exiｔ(1);}ｅlse{ｓtｒuctnoｄe*p=fronｔ->next;x=p->datａ;fｒoｎt->neｘｔ=___(2)＿__＿_;if（p->ｎｅxt=＝ＮＵLL)ｒear＝frｏnt;frｅe(p);＿__(3)＿_＿_＿;｝｝答案一、單項選擇題1.Ｃ2.A3．C4．B5．Ｄ6.B7.Ａ8.D９．A1０.Ｃ11．C1２．C13.D14.B15．A1６.B17.Ａ18．Ｄ19.D20.Ａ21.A2２.B２3.A24．A25．B26.Ａ27．D２8．B29．D３0.A二、填空題1.集合;線性；樹形；圖狀2．圖狀3.p->neｘt=heaｄ;4．p－>nｅxt==ｈead；5．ｐ->nｅxｔ=hｅad;6.hs=ｓ;7.ｒ－>neｘt=s8．ｒ->next=s；r＝s；9．r==f10.３；５１１．1;212.2１3．１１14.1０15.先序;中序;后序1６.深度優(yōu)先；廣度優(yōu)先17.物理(存儲)18.圖狀（網(wǎng)狀）19．gdbeihｆca２0.2n-121．錯誤22．順序存儲鏈式存儲23.深度優(yōu)先廣度優(yōu)先24.關(guān)鍵字相等的記錄三、綜合應(yīng)用題abceabced(２)d<b＜ｅ<a<c(３)abdｅｃaecbdaecbd(２)eｄbca(3）e=１,ａ=2,d=3,c＝4,ｂ=540287231004028723100546（2)ASL=（1ｘ1+2x2+3x3+4）/7=１8/785176218517621971910(２）５,6，７,8,9,10，１７,1８,１9,215.16423252571642325257678242826752573216102102初始樹堆102初始樹堆(2）102，52,4２,82,１6,67，32,572845284513213573209131525012321（2）2ｎ－1不一定唯一四、程序填空題（每空2分，共16分）1．(1）low<=hiｇh(2）mid（３)a[mid］．kｅy<ｋ；(4）hiｇｈ=miｄ-1(5)reｔｕrn-１;2．（１)ＮULL(2）k(3）p=p－>ｌeft（4)ｐ＝p-＞riｇhｔ(5)p3．（1)malｌoc(siｚeof（strｕcｔnodｅ))(2）rear－＞neｘt=ｐ(3）p4．(1）froｎｔ==reａr（2）p->ｎｅxt(３)ｒeｔurｎ(x)數(shù)據(jù)結(jié)構(gòu)(本）期末綜合練習(xí)三202３年6月一、單項選擇題1．（)是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。A、數(shù)據(jù)元素Ｂ．?dāng)?shù)據(jù)對象C.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)項２．從ｎ個數(shù)中選取最大元素（)。A.基本操作是數(shù)據(jù)元素間的互換Ｂ.算法的時間復(fù)雜度是O(n２）C.算法的時間復(fù)雜度是O(ｎ)D.需要進行(n+1）次數(shù)據(jù)元素間的比較３．設(shè)鏈表中的結(jié)點是NＯＤE類型的結(jié)構(gòu)體變量，且有ＮODE*p；為了申請一個新結(jié)點,并由p指向該結(jié)點，可用以下語句()。Ａ.p＝(NOＤE＊)maｌloｃ(ｓizeｏｆ(NODE）);Ｂ.p=(*ＮODE)malloｃ（sｉzeoｆ(NODE）);C.ｐ=(NOＤE)malloc(sｉｚeof(p）);Ｄ.p＝(NODE＊)ｍalloc（ｓiｚeｏf(p））；4.設(shè)ｈead為非空的單向循環(huán)鏈表頭指針,p指向鏈表的尾結(jié)點,則滿足邏輯表達式(）的值為真。A．ｐ-＞next=NUＬLＢ．ｐ==NUＬLC．p－>next=hｅadＤ．p->nｅxｔ＝=head5．設(shè)順序存儲的線性長度為n,要在第ｉ個元素之前插入一個新元素,按課本的算法當(dāng)i=(）時,移動元素次數(shù)為２A．ｎ／2B．nC．1D.n-16．設(shè)順序存儲的線性表長度為n,要刪除第i個元素,按課本的算法,當(dāng)i=（)時，移動元素的次數(shù)為3A.3Ｂ.n／２C．n-3D7.一個棧的進棧序列是1，２,3，４,則棧的不也許的出棧序列是（）（進出棧操作可以交替進行)A.３，２,4,1B．１,4，2，3C．4，3，2,1D．3,2，1,４8．一個棧的進棧序列是a,b,c，d，則棧的不也許的出棧序列是（）。A.ａｄbｃＢ．bcadC.cbadD．dcｂa9.設(shè)有一個帶頭結(jié)點的鏈隊列,隊列中每個結(jié)點由一個數(shù)據(jù)域ｄaｔa和指針域nexｔ組成,froｎt和rear分別為鏈隊列的頭指針和尾指針。設(shè)p指向要入隊的新結(jié)點(該結(jié)點已被賦值),則入隊操作為()。A．rｅａr->neｘt=p;reａｒ＝p;Ｂ.rｅａｒ-＞nexｔ=p;p=reaｒ;C.ｐ=ｒear->ｎext;reaｒ＝ｐ;D.ｒｅar=p;ｒｅａr->ｎext=p;1０．設(shè)有一個帶頭結(jié)點的鏈隊列，隊列中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，ｆｒont和rear分別為鏈隊列的頭指針和尾指針，要執(zhí)行出隊操作,用x保存出隊元素的值，p為指向結(jié)點類型的指針,可執(zhí)行如下操作:p=fｒont->neｘt;x=p->ｄａt(yī)a;然后指行（)。A.ｆｒｏnt=ｐ->ｎext;B．fｒonｔ->nｅxt＝p－>ｎexｔ;C．front=p;Ｄ.froｎt->next=p;1１.以下說法不對的的是(）。A.順序棧中，棧滿時再進行進棧操作稱為“上溢”B．順序棧中，?？諘r再作出棧棧操作稱為“下溢”C.順序隊列中,當(dāng)尾指針已經(jīng)超越隊列存儲空間的上界，則一定是隊列已滿D.順序隊列中，隊列的頭指針和尾指針均超越隊列存儲空間的上界，則隊列已空１3．設(shè)有一個２0階的對稱矩陣Ａ,采用壓縮存儲方式，將其下三角部分以行序為主序存儲到一維數(shù)組中（矩陣Ａ的第一個元素為a11,數(shù)組b的下標(biāo)從1開始），則矩陣元素a８,5在一維數(shù)組ｂ中的下標(biāo)是()。Ａ．30Ｂ．28C.40Ｄ1４.設(shè)有一個10階的對稱矩陣Ａ,采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中。（矩陣A的第一個元素為ａ1,1，數(shù)組b的下標(biāo)從1開始),則矩陣元素ａ5,３相應(yīng)一維數(shù)組ｂ的數(shù)組元素是(）。A.b[18]B.ｂ[8]C.b[13]Ｄ．b[1０]1５.深度為5的完全二叉樹第5層上有4個結(jié)點，該樹一共有(）個結(jié)點。A．２8Ｂ．30C．3１D１6.深度為５的完全二叉樹共有20個結(jié)點,則第５層上有（）個結(jié)點(根所在結(jié)點為第一層）。Ａ．3B．8Ｃ.5D１７．已知一個圖的所有頂點的度數(shù)之和為m，則m一定不也許是()。Ａ.４B．８C.12Ｄ18．已知一個圖的所有頂點的度數(shù)之和為m,且m是以下4中情況之一，則m只也許是（）。A.9B．7Ｃ．15D19．以下說法對的的是()。A．連通圖Ｇ的生成樹中可以包含回路B.連通圖Ｇ的生成樹可以是不連通的C．連通圖G的生成樹一定是唯一的D.連通圖G的生成樹一定是連通而不包含回路的20.線性表只要以（)方式存儲就能進行折半查找。A.鏈接B．順序C.關(guān)鍵字有序的順序D.二叉樹21．對n個元素進行冒泡排序,通常要進行n－1趟冒泡,在第ｊ趟冒泡中共要進行（)次元素間的比較。A．jＢ．j-1C.n-jD22．對n個元素進行冒泡排序若某趟冒泡中只進行了（）次元素間的互換,則表白序列已經(jīng)排好序。A．１Ｂ.２Ｃ．0D23．在排序過程中，可以有效地減少一趟排序過程中元素間的比較次數(shù)的算法是()。A．冒泡B．選擇C.直接插入D．折半插入24.在對一組元素(6４,４8,１06,33,25，8２，70，５５，9３）進行直接插入排序時，當(dāng)進行到要把第7個元素7０插入到已經(jīng)排好序的子表時,為找到插入位置，需進行(）次元素間的比較(指由小到大排序）。A.6B．２C．3D25.如圖若從頂點ａ出發(fā)按深度優(yōu)先搜索法進行遍歷，則也許得到的頂點序列為（）。abecabecdfB.abｅdcfＣ．ａcebdｆD.aｃｆｂｄｅ圖１26．如圖，若從頂點a出發(fā)按廣度優(yōu)先搜索法進行遍歷，則也許得到的頂點序列為(）。abecdfgabecdfgB．a(chǎn)bｅcdgｆC．ａcfedｇbD．a(chǎn)becfdｇ２7．一棵哈夫曼樹有n個葉子結(jié)點(終端結(jié)點）,該樹總共有（)個結(jié)點。A.2ｎ－2B．2n－1C．2nD．２28．一棵哈夫曼樹有10個非葉子結(jié)點（非終端結(jié)點),該樹總共有（)個結(jié)點。A．21B．20C．２2９.數(shù)據(jù)的()結(jié)構(gòu)與所使用的計算機無關(guān)。A.邏輯B.物理C.存儲Ｄ.邏輯與存儲３0．隊列的插入操作在（)進行。Ａ．隊頭B．隊尾C.隊頭或隊尾D.在任意指定位置二、填空題1.通?？梢园岩槐揪哂胁煌鹿?jié)的書的目錄結(jié)構(gòu)抽象成_____＿__結(jié)構(gòu)。2．通?？梢园涯吵鞘兄懈鞴徽军c間的線路圖抽象成___＿____結(jié)構(gòu)。３.要在一個單向鏈表中p所指向的結(jié)點之后插入一個s所指向的新結(jié)點，若鏈表中結(jié)點的指針域為next,可執(zhí)行_＿_____＿和p->nexｔ＝s;的操作。4.要在一個單向鏈表中刪除p所指向的結(jié)點,已知q指向p所指結(jié)點的直接前驅(qū)結(jié)點，若鏈表中結(jié)點的指針域為neｘｔ，則可執(zhí)行＿＿______。5．設(shè)有一個非空的鏈棧，棧頂指針為ｈs,要進行出棧操作,用x保存出棧結(jié)點的值，棧結(jié)點的指針域為next,則可執(zhí)行x=hs－>datａ；________。6.設(shè)有一個鏈棧，棧頂指針為hｓ,現(xiàn)有一個s所指向的結(jié)點要入棧，則可執(zhí)行操作________和hs＝ｓ;7.在一個不帶頭結(jié)點的非空鏈隊中，f和r分別為隊頭和隊尾指針,隊結(jié)點的數(shù)據(jù)域為dａt(yī)a，指針域為nexｔ，若要進行出隊操作,并用變量x存放出隊元素的數(shù)據(jù)值,則相關(guān)操作為ｘ＝f->ｄatａ；__＿__＿__。8．在一個不帶頭結(jié)點的非空鏈隊中，ｆ和r分別為隊頭和隊尾指針，隊結(jié)點的數(shù)據(jù)域為ｄaｔa,指針域為nexｔ,若要進行出隊操作，并用變量x存放出隊元素的數(shù)據(jù)值，則相關(guān)操作為___＿_＿__;__＿__＿__。９.循環(huán)隊列的最大存儲空間為MaxSize=8,采用少用一個元素空間以有效的判斷?？栈驐M，若隊頭指針froｎｔ=4，則當(dāng)隊尾指針reａr=__＿_____時,隊列為空，當(dāng)ｒｅaｒ=____＿___時,隊列有6個元素。10，順序存儲字符串“AＢCD”需要占用_______＿個字節(jié)。11．稀疏矩陣存儲時，采用一個由____、__＿_、＿＿__3部分信息組成的三元組唯一擬定矩陣中的一個非零元素。12.一棵二叉樹葉結(jié)點(終端結(jié)點）數(shù)為5，單分支結(jié)點數(shù)為２，該樹共有___＿＿_個結(jié)點。13．一棵二叉樹順序編號為6的結(jié)點(樹中各結(jié)點的編號與等深度的完全二叉中相應(yīng)位置上結(jié)點的編號相同),若它存在右孩子，則右孩子的編號為_＿_＿___＿。１4．設(shè)一棵完全二叉樹,其最高層上最右邊的葉結(jié)點的編號為奇數(shù)，該葉節(jié)點的雙親結(jié)點的編號為10,該完全二叉樹一共有＿_____＿_個結(jié)點。15．結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為_____＿__結(jié)構(gòu)。1６.結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為_____＿＿_結(jié)構(gòu)。１7.結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為＿＿_＿_＿_＿結(jié)構(gòu)。18．結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系稱為_＿______結(jié)構(gòu)。19.如圖2所示的二叉樹,其前序遍歷序列為__＿＿__＿__。ggfabdec圖22０.如圖2所示的二叉樹,其后序遍歷序列為。eefgibachd圖22１.在隊列的順序存儲結(jié)構(gòu)中，當(dāng)插入一個新的隊列元素時,指針的值增１,當(dāng)刪除一個元素隊列時，指針的值增1。２2．圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是______的。(回答對的或不對的)23．循環(huán)隊列的引入,目的是為了克服。24．按某關(guān)鍵字對記錄序列排序,若關(guān)鍵字的記錄在排序前和排序后仍保持它們的前后關(guān)系，則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。三、綜合題1.(１）設(shè)head1和p1分別是不帶頭結(jié)點的單向鏈表Ａ的頭指針和尾指針，heaｄ２和p２分別是不帶頭結(jié)點的單向鏈表B的頭指針和尾指針，若要把B鏈表接到A鏈表之后，得到一個以head1為頭指針的單向循環(huán)鏈表，寫出其中兩個關(guān)鍵的賦值語句(不用完整程序,結(jié)點的鏈域為neｘｔ)。（2)單向鏈表的鏈域為neｘｔ，設(shè)指針p指向單向鏈表中的某個結(jié)點,指針s指向一個要插入鏈表的新結(jié)點,現(xiàn)要把s所指結(jié)點插入ｐ所指結(jié)點之后,某學(xué)生采用以下語句:p->next＝s；s->next=p－>nｅxt;這樣做對的嗎？若對的則回答對的，若不對的則說明應(yīng)如何改寫2．（１)一組記錄的關(guān)鍵字序列為｛４５，40,65,４3，35，９5}寫出運用快速排序的方法，以第一個記錄為基準得到的一趟劃分的結(jié)果(規(guī)定給出一趟劃分中每次掃描和互換的結(jié)果）（２)同樣對序列{45,４０，65，43，35，９5}運用直接插入排序，寫出逐次插入過程（從第一個元素一直到第六個元素）。3．（1)畫出對長度為１0的有序表進行折半查找的鑒定樹（以序號1，2，……１０表達樹結(jié)點）(2)對上述序列進行折半查找，求等概率條件下,成功查找的平均查找長度4．（1)運用篩選過程把序列｛42，82,6７,102,16，32,5７，５2}建成堆(小根堆)，畫出相應(yīng)的完全二叉樹（不規(guī)定中間過程)（2)寫出對上述堆相應(yīng)的完全二叉樹進行中序遍歷得到的序列5.（1）運用篩選法，把序列{３７,7７，６2,9７，11,２7,5２，4７}建成堆(小根堆），畫出相應(yīng)的完全二叉樹(2)寫出對上述堆所相應(yīng)的二叉樹進行前序遍歷得到的序列6.(1）設(shè)有一個整數(shù)序列{50,３8，1６,８２,１１0，13,6４},依次取出序列中的數(shù),構(gòu)造一棵二叉排序樹(2）運用上述二叉排序樹，為了查找110，經(jīng)多少次元素間的比較能成功查到，為了查找15,經(jīng)多少次元素間的比較可知道查找失敗四、程序填空題1．以下函數(shù)為直接選擇排