2023年電大數據結構期末綜合練習(6月)

數據結構(本）期末綜合練習202３年6月為了幫助同學們進行期末復習，特擬定以下三套期末綜合練習題,望同學們逐個認真完畢。數據結構(本)期末綜合練習一一、單項選擇題1.針對線性表，在存儲后假如最常用的操作是取第i個結點及其前驅,則采用(）存儲方式最節(jié)省時間。A.單鏈表B．雙鏈表C.單循環(huán)鏈表D．順序表２.線性表采用鏈式存儲時，其地址()。A.一定是不連續(xù)的Ｂ．必須是連續(xù)的C.可以連續(xù)也可以不連續(xù)D．部分地址必須是連續(xù)的3.數據結構中,與所使用的計算機無關的是數據的(）結構。Ａ.物理B.存儲Ｃ.邏輯與物理D．邏輯4.帶頭結點的單向鏈表的頭指針為heａｄ,該鏈表為空的鑒定條件是（）的值為真。Ａ．ｈead==NＵLLＢ．ｈeａｄ->nｅxt＝＝headC．heａｄ-＞nexｔ==NＵLＬD.head==heａd－>next5．以下特性中，（)不是算法的特性。A．有窮性B．擬定性C．可行性Ｄ.有0個或多個輸出6．設順序存儲的線性表長度為n,對于插入操作，設插入位置是等概率的,則插入一個元素平均移動元素的次數為()。A.ｎ／2B.nC．n－1Ｄ．n-ｉ＋1７．設有一個長度為n的順序表，要在第i個元素之前（也就是插入元素作為新表的第i個元素)，則移動元素個數為（）。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.棧和隊列的相同點是（)。Ａ.都是后進先出Ｂ．都是后進后出Ｃ．邏輯結構與線性表不同D.邏輯結構與線性表相同,都是操作規(guī)則受到限制的線性表１1．以下說法對的的是（)。A．棧的特點是先進先出，隊列的特點是先進后出B．棧和隊列的特點都是先進后出C．棧的特點是先進后出，隊列的特點是先進先出D.棧和隊列的特點都是先進先出１2．在C語言中,運用數組ａ存放字符串“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按順序依次進棧，則該棧的不也許輸出序列是（）(進棧出棧可以交替進行)。A．8,6，4，2B．２，4,6，8C．４，2,8，6D．8,６,２，414.設有一個1５階的對稱矩陣A,采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數組b中。（矩陣A的第一個元素為ａ1,1,數組b的下標從1開始），則數組元素b[１3]相應Ａ的矩陣元素是(）。A.a5,３B.a6，4C．a7,2Ｄ15.設有一個1５階的對稱矩陣A,采用壓縮存儲的方式,將其下三角部分以行序為主序存儲到一維數組B中（數組下標從1開始）,則矩陣中元素ａ７,６在一維數組B中的下標是()。A.42Ｂ.13C16．一棵完全二叉樹共有30個結點,則該樹一共有（)層(根結點所在層為第一層)。A.6B.4Ｃ.３D17.串函數StｒCmp（“d”,“D”）的值為（)。A．0B.1C18．以下說法對的的是(）。A．連通圖Ｇ的生成樹中不一定包含G的所有頂點B.連通圖G的生成樹中一定要包含Ｇ的所有邊C.連通圖G的生成樹一定是唯一的D．連通圖G一定存在生成樹19.在一棵二叉樹中，若編號為i的結點存在右孩子,則右孩子的順序編號為()。A.2iB．2i-1Ｃ20.對二叉排序樹進行（)遍歷，遍歷所得到的序列是有序序列。A.按層次B.前序C.中序D．后序21.設一棵有n個結點采用鏈式存儲的二叉樹，則該樹共有()個指針域為空。A．２nB.2n＋1Ｃ.2n+２２2．以下排序算法中，在一趟排序過程中,除了其它相關操作外，只進行一次元素間的互換的算法是（）。Ａ．直接選擇Ｂ.冒泡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時，經()次比較后查找成功。A.6B．3C２6.如圖若從頂點a出發(fā)按深度優(yōu)先搜索法進行遍歷，則也許得到的頂點序列為(）。ababecdfgB.aedcｂｇfＣ.ａｃfebdgＤ.aecｂdgf2７．有一個長度為10的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數為(）。Ａ．29/1０B．３1/10C28.一棵哈夫曼樹有1２個葉子結點(終端結點),該樹總共有（)個結點。A．22B．２1C.23Ｄ.29．一組記錄的關鍵字序列為（３7,７0，４7，２9，31，8５)，運用快速排序,以第一個關鍵字為分割元素,通過一次劃分后結果為（）。Ａ．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．把數據存儲到計算機中,并具體體現(xiàn)數據之間的邏輯結構稱為＿______＿結構。2．設有一個不帶頭結點的單向循環(huán)鏈表,結點的指針域為nｅxt,指針p指向尾結點,現(xiàn)要使p指向第一個結點，可用語句__＿＿_＿__。３．結構中的數據元素存在一對一的關系稱為_＿____＿_結構。４.要在一個帶頭結點的單向循環(huán)鏈表中刪除頭結點，得到一個新的不帶頭結點的單向循環(huán)鏈表，若結點的指針域為ｎeｘt，頭指針為head,尾指針為p,，則可執(zhí)行head=heaｄ－>ｎexｔ；________。５．在雙向鏈表中,每個結點有兩個指針域,一個指向＿＿＿__＿＿＿,另一個指向＿＿_____＿_。6．設有一個非空的鏈棧，棧頂指針為hｓ，要進行出棧操作,用ｘ保存出棧結點的值，棧結點的指針域為nexｔ，數據域為ｄａt(yī)ａ，則可執(zhí)行x=＿__＿_＿__;和hs=___＿___＿；7．設有一個頭指針為head的單向鏈表,p指向表中某一個結點,且有p->ｎext=＝ＮULL,通過操作___＿__＿_,就可使該單向鏈表構導致單向循環(huán)鏈表。8.循環(huán)隊列的最大存儲空間為MaxSize，隊頭指針為f，隊尾指針為r，當__＿＿___＿時表白隊列已滿。9.從一個棧頂指針為h的鏈棧中刪除一個結點時,用x保存被刪結點的值，可執(zhí)行x=h->dａt(yī)ａ;和________。（結點的指針域為nｅxt）１0.程序段intcount=0;char*s=”AＢCＤ”;wｈile(*s!=’＼0’執(zhí)行后cｏunt=___＿____１１．兩個串相等的充足必要條件是＿___＿＿_＿＿＿。12.一棵二叉樹總結點數為11,葉結點數為5,該樹有____＿_＿_個雙分支結點,__＿_____個單分支結點。13．對二叉樹的遍歷可分為___＿____、、、四種不同的遍歷順序。14．設一棵完全二叉樹，其最高層上最右邊的葉結點的編號為偶數，該葉節(jié)點的雙親結點的編號為９,該完全二叉樹一共有＿＿____＿＿個結點。1５．一棵有n個葉結點的二叉樹，其每一個非葉結點的度數都為2,則該樹共有___＿__＿個結點。1６．雙向循環(huán)鏈表中，p指向表中某結點,則通過p可以訪問到p所指結點的直接后繼結點和直接前驅結點，這種說法是_＿_＿_＿＿＿的（回答對的或不對的)。１7.一棵有１4個結點的完全二叉樹，則它的最高層上有__＿_＿__個結點。１8.棧和隊列的操作特點分別是________和___＿＿＿__。１９.如圖2所示的二叉樹,其先序遍歷序列為_＿___＿_＿_。efefgibachd圖22０.折半查找只合用于存儲的有序表。21．哈希函數是記錄關鍵字值與該記錄＿＿____之間所構造的相應關系。22．深度為k的二叉樹最多有結點。23.二叉樹排序中任一棵子樹都是二叉排序樹,這種說法是＿__＿___的。(回答對的或不對的)24.串的兩種最基本的存儲方式是_______＿和____＿_＿_。得分評卷人三、綜合題1.設一組記錄的關鍵字序列為（49,83，59,4１,４３，４7)，采用堆排序算法完畢以下操作：（規(guī)定小根堆,并畫出中間過程)(１）以二叉樹描述6個元素的初始堆(２)以二叉樹描述逐次取走堆頂元素后，經調整得到的５個元素、4個元素的堆2．設有一個不帶頭結點的單向鏈表,頭指針為hｅad，結點類型為NOＤE，每個結點包含一個數據域ｄａt(yī)a和一個指針域next,該鏈表有兩個結點,p指向第二個結點(尾結點）,按以下規(guī)定寫出相應語句（不規(guī)定完整程序，(1)、(2)、（3)、（４）是一個連續(xù)的過程）。(1)新開辟一個結點,使指針s指向該結點，結點的數據成員datａ賦值為1（2)把該結點插入鏈表的尾部，釋放指針s的指向(3）刪除鏈表的第一個結點(4）已知p１指向另一個新結點，把它插入到p所指結點和尾結點之間3．設有序表為(１3,19,２5，36，4８，51，6３,84,91,116,１35，２00)，元素的下標依次為1，２，……，１2。（１）說出有哪幾個元素需要通過4次元素間的比較才干成功查到（2）畫出對上述有序表進行折半查找所相應的鑒定樹(樹結點用下標表達)(３)設查找元素5,需要進行多少次元素間的比較才干擬定不能查到４．(１)設有序列{１０,12,15,19,2２,２5,10０,1３0，１５0,200｝畫出對上述序列進行折半查找的鑒定樹（以序列中的元素作為樹的結點)（2）為了成功查找到１00需要進行多少次元素間的比較？為了查找９，通過多少次元素間的比較可知道查找失敗？5.（1)對給定數列｛７,１6,4,8,20，9，6，18，5},依次取數列中的數據，構造一棵二叉排序樹。(2)對一個給定的查找值，簡述針對二叉排序樹進行查找的算法環(huán)節(jié),在上述二叉樹中查找元素20共要進行多少次元素的比較？6.（１)設有查找表｛5,14,2,6,１８，7,4,１６,3},依次取表中數據，構造一棵二叉排序樹。（２）說明如何由序列的二叉排序樹得到相應序列的排序結果，對上述二叉排序給出中序遍歷的結果。四、程序填空題1．以下冒泡法程序對存放在a[1］,a[2]，……，a[ｎ]中的序列進行排序，完畢程序中的空格部分,其中ｎ是元素個數,規(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．以下程序是先序遍歷二叉樹的遞歸算法的程序，完畢程序中空格部分（樹結構中左、右指針域分別為lｅft和ｒｉght,數據域dａt(yī)ａ為字符型，BＴ指向根結點)。ｖｏiｄPreordeｒ(sｔructBＴreｅNode*BT）{iｆ（BＴ!=NＵLＬ){(１）;（2）;（3）;}}3．設線性表為（６，10，16,４)，以下程序用說明結構變量的方法建立單向鏈表,并輸出鏈表中各結點中的數據。＃ｄefinｅNULL０ｖoｉdmaｉｎ()｛NODEa，b，c,ｄ，*heａd,＊ｐ;a.datａ=6;b.ｄａt(yī)a＝１0；ｃ.data=16;d.ｄaｔa=4;／*ｄ是尾結點*/heａｄ=(1)；ａ.neｘt＝&b;ｂ.neｘt=&c;c．nｅxt=&d；（2）;／*以上結束建表過程*／p=head;/*p為工作指針，準備輸出鏈表＊/do{priｎｔｆ（“%d＼ｎ”,（3）);（４)；｝ｗhilｅ(（５))；}4.以下程序是中序遍歷二叉樹的遞歸算法的程序,完畢程序中空格部分(樹結構中左、右指針域分別為ｌeｆt和rｉgｈt,數據域dａt(yī)a為字符型，ＢT指向根結點）。ｖ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．結點的直接后繼結點的直接前驅7．p->nｅxt=hｅａd;９.ｈ=h->nexｔ;11．串長度相等且相應位置的字符相等１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．順序存儲結構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)先將給定值與根結點比較，若相等則查找成功，否則若小于根結點則在左子樹中繼續(xù)查找，大于根結點在右子樹中查找，查找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)當某趟冒泡中沒有出現(xiàn)互換則已排好序,結束循環(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)數據結構（本）期末綜合練習二202３年6月一、單項選擇題1．數據元素是數據的基本單位，它（)。A.只能有一個數據項組成B.至少有二個數據項組成Ｃ.可以是一個數據項也可以由若干個數據項組成D．至少有一個數據項為指針類型2.一種邏輯結構()存儲結構。Ａ.可以有不同的B.只能有唯一的C．的數據元素在計算機中的表達稱為Ｄ.的數據元素之間的關系稱為3.線性表的順序結構中，(）。Ａ．邏輯上相鄰的元素在物理位置上不一定相鄰B．數據元素是不能隨機訪問的C．邏輯上相鄰的元素在物理位置上也相鄰D.進行數據元素的插入、刪除效率較高4．以下說法中不對的的是（)。Ａ.雙向循環(huán)鏈表中每個結點需要包含兩個指針域B.已知單向鏈表中任一結點的指針就能訪問到鏈表中每個結點Ｃ．順序存儲的線性鏈表是可以隨機訪問的D.單向循環(huán)鏈表中尾結點的指針域中存放的是頭指針５.以下表中可以隨機訪問的是()。Ａ．單向鏈表Ｂ.雙向鏈表C．單向循環(huán)鏈表D．順序表6．雙向循環(huán)鏈表結點的數據類型為:ｓtructnode｛ｉｎtｄａt(yī)a;stｒｕctnode*next；／*指向直接后繼*／struｃtｎodｅ*prior;};設p指向表中某一結點,要顯示p所指結點的直接前驅結點的數據元素，可用操作()。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.設順序存儲的線性表長度為n，對于刪除操作，設刪除位置是等概率的,則刪除一個元素平均移動元素的次數為（）。A.（ｎ+1）/2B．nC.２nD．n-ｉ8．一個棧的進棧序列是eｆgｈ,則棧的不也許的出棧序列是(）(進出棧操作可以交替進行）。A.ｈgfｅB.ｇfｅhC．fｇeｈＤ.eｈfｇ9.設ｔoｐ是一個鏈棧的棧頂指針,棧中每個結點由一個數據域ｄａt(yī)a和指針域nｅｘt組成,設用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．設top是一個鏈棧的棧頂指針，棧中每個結點由一個數據域data和指針域next組成,設用ｘ接受棧頂元素，則取棧頂元素的操作為（）。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．串函數StrＣmp(“abA”,”ａｂa”)的值為（)。Ａ．１B.０C.“abＡａba”D1４.chａr*ｐ;ｐ=ＳｔｒCａt(yī)(“AＢD”,”ABＣ”）；Priｎtf（“%ｓ”,ｐ);的顯示結果為(）。A.-１B.ABDABCＣ．AＢD.115.設有一個１2階的對稱矩陣A,采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數組ｂ中(矩陣A的第一個元素為a1,１，數組b的下標從1開始）,則矩陣Ａ中第4行的元素在數組b中的下標i一定有（)。A、7≤i≤10B、1１≤ｉ≤１5Ｃ、9≤ｉ≤１4D、6≤i≤16.深度為５的滿二叉樹至多有（)個結點(根結點為第一層）Ａ.40B.３１Ｃ．34Ｄ1７．已知一個圖的邊數為m,則該圖的所有頂點的度數之和為（)。A.2mB.mC.2m+1D.m/21８．已知一個圖的所有頂點的度數之和為m，則該圖的邊數為()。A．２mB．mＣ.2m＋1Ｄ．m/２19.以下說法不對的的是()。A.連通圖G一定存在生成樹B.連通圖Ｇ的生成樹中一定包含G的所有頂點C.連通圖Ｇ的生成樹中不一定包含G的所有邊Ｄ.連通圖Ｇ的生成樹可以是不連通的20．以下說法不對的的是()。A.連通圖Ｇ的生成樹一定是唯一的B.連通圖G一定存在生成樹C.連通圖G的生成樹中一定要包含G的所有頂點Ｄ.連通圖G的生成樹一定是連通并且不包含回路２1．散列查找的原理是(）。A．在待查記錄的關鍵字值與該記錄的存儲位置之間建立擬定的相應關系B．按待查記錄的關鍵字有序的順序方式存儲Ｃ.按關鍵字值的比較進行查找D.基于二分查找的方法２2.有序表為{1，２,４,6，１0,18,2０，3２}，用課本中折半查找算法查找值18，經()次比較后成功查到。Ａ.３B.2Ｃ．4D2３.排序過程中，每一趟從無序子表中將一個待排序的記錄按其關鍵字的大小放置到已經排好序的子序列的適當位置，直到所有排好序為止，該排序算法是（)。A.直接插入排序Ｂ.快速排序C.冒泡排序Ｄ．選擇排序24．在排序過程中，可以通過某一趟排序的相關操作所提供的信息，判斷序列是否已經排好序，從而可以提前結束排序過程的排序算法是（)。A.冒泡Ｂ.選擇C．直接插入D.折半插入2５.采用順序查找法對長度為ｎ的線性表進行查找（不采用表尾設監(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．abecｄfｇh圖128.如圖若從頂點ａ出發(fā)按深度優(yōu)先搜索法進行遍歷，則也許得到的頂點序列為(）。bcbcgdafeＢ．aedｂgfcＣ．ａcfeｂdgD.ａeｃbdgf29．一棵哈夫曼樹總共有2３個結點,該樹共有（)個葉結點（終端結點)Ａ.1０B．1３Ｃ.1１30.一棵哈夫曼樹總共有25個結點,該樹共有（）個非葉結點（非終端結點)。Ａ．12B．13C．14二、填空題（每小題2分，共24分)1.通常數據的邏輯結構涉及____、__＿_、__＿＿、____四種類型。２.結構中的元素之間存在多對多的關系稱為_＿＿_____結構。３.設有一個單向鏈表，結點的指針域為nｅxt，頭指針為ｈead,ｐ指向尾結點，為了使該單向鏈表改為單向循環(huán)鏈表,可用語句___＿_＿__。4.設有一個單向循環(huán)鏈表,結點的指針域為next，頭指針為ｈｅａd,指針p指向表中某結點,若邏輯表達式____＿___的結果為真，則p所指結點為尾結點。５．設有一個單向循環(huán)鏈表,頭指針為ｈead，鏈表中結點的指針域為next,ｐ指向尾結點的直接前驅結點，若要刪除尾結點，得到一個新的單向循環(huán)鏈表,可執(zhí)行操作________。6．設有一個鏈棧，棧頂指針為hs，現(xiàn)有一個s所指向的結點要入棧，則可執(zhí)行操作s->nｅxt=hs；_＿______。7．在一個鏈隊中，f和r分別為隊頭和隊尾指針,隊結點的指針域為next，則插入一個s所指結點的操作為____＿___；r=ｓ；8．在一個鏈隊中，f和r分別為隊頭和隊尾指針,隊結點的指針域為nexｔ，s指向一個要入隊的結點，則入隊操作為_＿___＿＿＿；_＿_＿____;9.循環(huán)隊列的隊頭指針為f,隊尾指針為r,當___＿_時表白隊列為空。10．循環(huán)隊列的最大存儲空間為MaxSizｅ=6,采用少用一個元素空間以有效地判斷?？栈驐M,若隊頭指針front=4，當隊尾指針rｅar=_＿____＿_時隊滿，隊列中共有________個元素。11.‘A‘在存儲時占________個字節(jié)?！癆”在存儲時占______＿＿個字節(jié)。12．程序段chａr*s＝”aBcＤ”;n=0;ｗhilｅ（*ｓ!＝’\0’｛if(＊ｓ>=’ａ’＆＆*s<=’z’)n++;s++；}執(zhí)行后n=___＿_＿__13.一棵二叉樹沒有單分支結點，有６個葉結點，則該樹總共有___＿____個結點。１4.一棵二叉樹中順序編號為5的結點（樹中各結點的編號與等深度的完全二叉中相應位置上結點的編號相同）,若它存在左孩子，則左孩子的編號為______＿_。15.按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有＿＿__、_＿__、__＿_三種。１6.根據搜索方法的不同,圖的遍歷有______＿_兩種方法。１７.把數據存儲到計算機中,并具體體現(xiàn)數據之間的邏輯結構稱為_＿______結構。1８.結構中的數據元素存在多對多的關系稱為_______＿結構。19．如圖２所示的二叉樹,其后序遍歷序列為。eefgibachd圖2２0．一棵有n個葉結點的二叉樹，其每一個非葉結點的度數都為2,則該樹共有_______個結點。21.二叉樹為二叉排序的充足必要條件是其任一結點的值均大于其左孩子的值、小于其右孩子的值。這種說法是__________的。(回答對的或不對的)２２.串的兩種最基本的存儲方式分別是___＿_＿_和_＿_＿____。2３．根據搜索方法的不同,圖的遍歷有_＿＿＿、＿___兩種方法24.按某關鍵字對記錄序列排序,若關鍵字的記錄在排序前和排序后仍保持它們的前后關系,則排序算法是穩(wěn)定的,否則是不穩(wěn)定的。三、綜合題１.（1）已知某二叉樹的后序遍歷序列是debca，中序遍歷序列是dbeａc,試畫出該二叉樹(２)若上述二叉樹的各個結點的字符分別代表不同的整數（其中沒有相等的）,并恰好使該樹成為一棵二叉排序樹，試給出a、b、c、d、ｅ的大小關系（3）給出該樹的前序遍歷序列2.（1)已知某二叉樹的先序遍歷序列是aecdｂ，中序遍歷序列是eaｄcb，試畫出該二叉樹（2)給出上述二叉樹的后序遍歷序列(3)若上述二叉樹的各個結點的字符分別是１，2,3，4,5，并恰好使該樹成為一棵二叉排序樹,試問a、b、c、ｄ、e的值各為多少？3.（1)設有一個整數序列{40,２8,6,72,１00,3，５４}依次取出序列中的數，構造一棵二叉排序樹（2）對上述二叉排序樹,在等概率條件下,求成功查找的平均查找長度４.（１）給定數列｛8,17，5,9，21,１0,7,１9，6｝,依次取序列中的數構造一棵二叉排序樹（2）對上述二叉樹給出中序遍歷得到的序列5.（1）運用篩選過程把序列{4２,8２,67，10２,1６，32,57,5２}建成堆(小根堆）,畫出相應的完全二叉樹（不規(guī)定中間過程)(2)寫出對上述堆相應的完全二叉樹進行中序遍歷得到的序列6．(１)以給定權重值1,２,12,13，20,25為葉結點，建立一棵哈夫曼樹（２)若哈夫曼樹有n個非葉子結點，則樹中共有多少結點。對給定的一組權重值建立的棵哈夫曼樹是否一定唯一四、程序填空題1．以下函數在a[０]到a[n-1]中，用折半查找算法查找關鍵字等于k的記錄，查找成功返回該記錄的下標，失敗時返回-１,完畢程序中的空格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．以下函數是二叉排序樹的查找算法，若二叉樹為空，則返回根結點的指針，否則，返回值是指向樹結點的結構指針p（查找成功p指向查到的樹結點,不成功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用于接受二叉排序樹的根結點的指針,k用以接受要查找的關鍵字*/{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.以下函數為鏈隊列的入隊操作，x為要入隊的結點的數據域的值,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．以下函數為鏈隊列的出隊操作（鏈隊列帶有頭結點），出隊結點的數據域的值由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.圖狀（網狀）19．gdbeihｆca２0.2n-121．錯誤22．順序存儲鏈式存儲23.深度優(yōu)先廣度優(yōu)先24.關鍵字相等的記錄三、綜合應用題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)數據結構(本）期末綜合練習三202３年6月一、單項選擇題1．（)是性質相同的數據元素的集合，是數據的子集。A、數據元素Ｂ．數據對象C.數據結構D.數據項２．從ｎ個數中選取最大元素（)。A.基本操作是數據元素間的互換Ｂ.算法的時間復雜度是O(n２）C.算法的時間復雜度是O(ｎ)D.需要進行(n+1）次數據元素間的比較３．設鏈表中的結點是NＯＤE類型的結構體變量，且有ＮODE*p；為了申請一個新結點,并由p指向該結點，可用以下語句()。Ａ.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.設ｈead為非空的單向循環(huán)鏈表頭指針,p指向鏈表的尾結點,則滿足邏輯表達式(）的值為真。A．ｐ-＞next=NUＬLＢ．ｐ==NUＬLC．p－>next=hｅadＤ．p->nｅxｔ＝=head5．設順序存儲的線性長度為n,要在第ｉ個元素之前插入一個新元素,按課本的算法當i=(）時,移動元素次數為２A．ｎ／2B．nC．1D.n-16．設順序存儲的線性表長度為n,要刪除第i個元素,按課本的算法,當i=（)時，移動元素的次數為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.設有一個帶頭結點的鏈隊列,隊列中每個結點由一個數據域ｄaｔa和指針域nexｔ組成,froｎt和rear分別為鏈隊列的頭指針和尾指針。設p指向要入隊的新結點(該結點已被賦值),則入隊操作為()。A．rｅａr->neｘt=p;reａｒ＝p;Ｂ.rｅａｒ-＞nexｔ=p;p=reaｒ;C.ｐ=ｒear->ｎext;reaｒ＝ｐ;D.ｒｅar=p;ｒｅａr->ｎext=p;1０．設有一個帶頭結點的鏈隊列，隊列中每個結點由一個數據域data和指針域next組成，ｆｒont和rear分別為鏈隊列的頭指針和尾指針，要執(zhí)行出隊操作,用x保存出隊元素的值，p為指向結點類型的指針,可執(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.順序隊列中，隊列的頭指針和尾指針均超越隊列存儲空間的上界，則隊列已空１3．設有一個２0階的對稱矩陣Ａ,采用壓縮存儲方式，將其下三角部分以行序為主序存儲到一維數組中（矩陣Ａ的第一個元素為a11,數組b的下標從1開始），則矩陣元素a８,5在一維數組ｂ中的下標是()。Ａ．30Ｂ．28C.40Ｄ1４.設有一個10階的對稱矩陣Ａ,采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數組b中。（矩陣A的第一個元素為ａ1,1，數組b的下標從1開始),則矩陣元素ａ5,３相應一維數組ｂ的數組元素是(）。A.b[18]B.ｂ[8]C.b[13]Ｄ．b[1０]1５.深度為5的完全二叉樹第5層上有4個結點，該樹一共有(）個結點。A．２8Ｂ．30C．3１D１6.深度為５的完全二叉樹共有20個結點,則第５層上有（）個結點(根所在結點為第一層）。Ａ．3B．8Ｃ.5D１７．已知一個圖的所有頂點的度數之和為m，則m一定不也許是()。Ａ.４B．８C.12Ｄ18．已知一個圖的所有頂點的度數之和為m,且m是以下4中情況之一，則m只也許是（）。A.9B．7Ｃ．15D19．以下說法對的的是()。A．連通圖Ｇ的生成樹中可以包含回路B.連通圖Ｇ的生成樹可以是不連通的C．連通圖G的生成樹一定是唯一的D.連通圖G的生成樹一定是連通而不包含回路的20.線性表只要以（)方式存儲就能進行折半查找。A.鏈接B．順序C.關鍵字有序的順序D.二叉樹21．對n個元素進行冒泡排序,通常要進行n－1趟冒泡,在第ｊ趟冒泡中共要進行（)次元素間的比較。A．jＢ．j-1C.n-jD22．對n個元素進行冒泡排序若某趟冒泡中只進行了（）次元素間的互換,則表白序列已經排好序。A．１Ｂ.２Ｃ．0D23．在排序過程中，可以有效地減少一趟排序過程中元素間的比較次數的算法是()。A．冒泡B．選擇C.直接插入D．折半插入24.在對一組元素(6４,４8,１06,33,25，8２，70，５５，9３）進行直接插入排序時，當進行到要把第7個元素7０插入到已經排好序的子表時,為找到插入位置，需進行(）次元素間的比較(指由小到大排序）。A.6B．２C．3D25.如圖若從頂點ａ出發(fā)按深度優(yōu)先搜索法進行遍歷，則也許得到的頂點序列為（）。abecabecdfB.abｅdcfＣ．ａcebdｆD.aｃｆｂｄｅ圖１26．如圖，若從頂點a出發(fā)按廣度優(yōu)先搜索法進行遍歷，則也許得到的頂點序列為(）。abecdfgabecdfgB．abｅcdgｆC．ａcfedｇbD．abecfdｇ２7．一棵哈夫曼樹有n個葉子結點(終端結點）,該樹總共有（)個結點。A.2ｎ－2B．2n－1C．2nD．２28．一棵哈夫曼樹有10個非葉子結點（非終端結點),該樹總共有（)個結點。A．21B．20C．２2９.數據的()結構與所使用的計算機無關。A.邏輯B.物理C.存儲Ｄ.邏輯與存儲３0．隊列的插入操作在（)進行。Ａ．隊頭B．隊尾C.隊頭或隊尾D.在任意指定位置二、填空題1.通常可以把一本具有不同章節(jié)的書的目錄結構抽象成_____＿__結構。2．通常可以把某城市中各公交站點間的線路圖抽象成___＿____結構。３.要在一個單向鏈表中p所指向的結點之后插入一個s所指向的新結點，若鏈表中結點的指針域為next,可執(zhí)行_＿_____＿和p->nexｔ＝s;的操作。4.要在一個單向鏈表中刪除p所指向的結點,已知q指向p所指結點的直接前驅結點，若鏈表中結點的指針域為neｘｔ，則可執(zhí)行＿＿______。5．設有一個非空的鏈棧，棧頂指針為ｈs,要進行出棧操作,用x保存出棧結點的值，棧結點的指針域為next,則可執(zhí)行x=hs－>datａ；________。6.設有一個鏈棧，棧頂指針為hｓ,現(xiàn)有一個s所指向的結點要入棧，則可執(zhí)行操作________和hs＝ｓ;7.在一個不帶頭結點的非空鏈隊中，f和r分別為隊頭和隊尾指針,隊結點的數據域為dａt(yī)a，指針域為nexｔ，若要進行出隊操作,并用變量x存放出隊元素的數據值,則相關操作為ｘ＝f->ｄatａ；__＿__＿__。8．在一個不帶頭結點的非空鏈隊中，ｆ和r分別為隊頭和隊尾指針，隊結點的數據域為ｄaｔa,指針域為nexｔ,若要進行出隊操作，并用變量x存放出隊元素的數據值，則相關操作為___＿_＿__;__＿__＿__。９.循環(huán)隊列的最大存儲空間為MaxSize=8,采用少用一個元素空間以有效的判斷棧空或棧滿，若隊頭指針froｎｔ=4，則當隊尾指針reａr=__＿_____時,隊列為空，當ｒｅaｒ=____＿___時,隊列有6個元素。10，順序存儲字符串“AＢCD”需要占用_______＿個字節(jié)。11．稀疏矩陣存儲時，采用一個由____、__＿_、＿＿__3部分信息組成的三元組唯一擬定矩陣中的一個非零元素。12.一棵二叉樹葉結點(終端結點）數為5，單分支結點數為２，該樹共有___＿＿_個結點。13．一棵二叉樹順序編號為6的結點(樹中各結點的編號與等深度的完全二叉中相應位置上結點的編號相同),若它存在右孩子，則右孩子的編號為_＿_＿___＿。１4．設一棵完全二叉樹,其最高層上最右邊的葉結點的編號為奇數，該葉節(jié)點的雙親結點的編號為10,該完全二叉樹一共有＿_____＿_個結點。15．結構中的數據元素存在多對多的關系稱為_____＿__結構。1６.結構中的數據元素存在一對多的關系稱為_____＿＿_結構。１7.結構中的數據元素存在一對多的關系稱為＿＿_＿_＿_＿結構。18．結構中的數據元素存在一對一的關系稱為_＿______結構。19.如圖2所示的二叉樹,其前序遍歷序列為__＿＿__＿__。ggfabdec圖22０.如圖2所示的二叉樹,其后序遍歷序列為。eefgibachd圖22１.在隊列的順序存儲結構中，當插入一個新的隊列元素時,指針的值增１,當刪除一個元素隊列時，指針的值增1。２2．圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是______的。(回答對的或不對的)23．循環(huán)隊列的引入,目的是為了克服。24．按某關鍵字對記錄序列排序,若關鍵字的記錄在排序前和排序后仍保持它們的前后關系，則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。三、綜合題1.(１）設head1和p1分別是不帶頭結點的單向鏈表Ａ的頭指針和尾指針，heaｄ２和p２分別是不帶頭結點的單向鏈表B的頭指針和尾指針，若要把B鏈表接到A鏈表之后，得到一個以head1為頭指針的單向循環(huán)鏈表，寫出其中兩個關鍵的賦值語句(不用完整程序,結點的鏈域為neｘｔ)。（2)單向鏈表的鏈域為neｘｔ，設指針p指向單向鏈表中的某個結點,指針s指向一個要插入鏈表的新結點,現(xiàn)要把s所指結點插入ｐ所指結點之后,某學生采用以下語句:p->next＝s；s->next=p－>nｅxt;這樣做對的嗎？若對的則回答對的，若不對的則說明應如何改寫2．（１)一組記錄的關鍵字序列為｛４５，40,65,４3，35，９5}寫出運用快速排序的方法，以第一個記錄為基準得到的一趟劃分的結果(規(guī)定給出一趟劃分中每次掃描和互換的結果）（２)同樣對序列{45,４０，65，43，35，９5}運用直接插入排序，寫出逐次插入過程（從第一個元素一直到第六個元素）。3．（1)畫出對長度為１0的有序表進行折半查找的鑒定樹（以序號1，2，……１０表達樹結點）(2)對上述序列進行折半查找，求等概率條件下,成功查找的平均查找長度4．（1)運用篩選過程把序列｛42，82,6７,102,16，32,5７，５2}建成堆(小根堆)，畫出相應的完全二叉樹（不規(guī)定中間過程)（2)寫出對上述堆相應的完全二叉樹進行中序遍歷得到的序列5.（1）運用篩選法，把序列{３７,7７，６2,9７，11,２7,5２，4７}建成堆(小根堆），畫出相應的完全二叉樹(2)寫出對上述堆所相應的二叉樹進行前序遍歷得到的序列6.(1）設有一個整數序列{50,３8，1６,８２,１１0，13,6４},依次取出序列中的數,構造一棵二叉排序樹(2）運用上述二叉排序樹，為了查找110，經多少次元素間的比較能成功查到，為了查找15,經多少次元素間的比較可知道查找失敗四、程序填空題1．以下函數為直接選擇排