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

數(shù)據(jù)結(jié)構(gòu)(本）期末綜合練習202３年6月為了幫助同學們進行期末復習,特擬定以下兩套期末綜合練習題,望同學們逐個認真完畢。數(shù)據(jù)結(jié)構(gòu)(本)期末綜合練習一一、單項選擇題1．數(shù)據(jù)元素是數(shù)據(jù)的基本單位,它（)。A．只能有一個數(shù)據(jù)項組成B.至少有二個數(shù)據(jù)項組成C.至少有一個數(shù)據(jù)項為指針類型D．可以是一個數(shù)據(jù)項也可以由若干個數(shù)據(jù)項組成２．（）是性質(zhì)相同的數(shù)據(jù)元素的集合,是數(shù)據(jù)的子集。A．數(shù)據(jù)對象Ｂ．數(shù)據(jù)元素C．數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)項3.線性表的順序結(jié)構(gòu)中，（）。A.邏輯上相鄰的元素在物理位置上不一定相鄰B．邏輯上相鄰的元素在物理位置上也相鄰C.數(shù)據(jù)元素是不能隨機訪問的D.進行數(shù)據(jù)元素的插入、刪除效率較高4．設鏈表中的結(jié)點是ＮＯＤＥ類型的結(jié)構(gòu)體變量,且有ＮＯＤE＊p；為了申請一個新結(jié)點,并由p指向該結(jié)點,可用以下語句()。A.p＝(NODＥ*)malloc（sｉzｅof(p))；B.ｐ=(*NODE)maｌloc(sizeoｆ(ＮＯDE））；C．p=(NODＥ)mａlｌoc(sizeof(p));Ｄ.ｐ=(NＯDE*)ｍalｌoc(sｉzｅｏf(ＮODE））;5.以下表中可以隨機訪問的是（）。A.單向鏈表B．順序表Ｃ．單向循環(huán)鏈表D.雙向鏈表6．設順序存儲的線性長度為ｎ,要在第ｉ個元素之前插入一個新元素,按課本的算法當i=(）時,移動元素次數(shù)為２A．n/２B.nC．n-1C．17.設順序存儲的線性表長度為n，對于刪除操作，設刪除位置是等概率的,則刪除一個元素平均移動元素的次數(shù)為(）。A.(n+１）/２B.nC．2nD．ｎ－i8．一個棧的進棧序列是1,2,3，４，則棧的不也許的出棧序列是（）（進出棧操作可以交替進行)A．3,2，４，１B．３,2，1，4Ｃ.4，３,２，1D．1，4，2，39.設ｔop是一個鏈棧的棧頂指針,棧中每個結(jié)點由一個數(shù)據(jù)域ｄata和指針域ｎeｘｔ組成，設用x接受棧頂元素,則出棧操作為（)。Ａ.ｔoｐ＝ｔop-＞nｅxt;ｘ=tｏp->data;B．ｘ=top->ｄata;top=toｐ－＞ｎext；C.x=top－>nｅxt;top＝toｐ->data;D．top->next=top；x=ｔｏp-＞datａ;1０．設有一個帶頭結(jié)點的鏈隊列，隊列中每個結(jié)點由一個數(shù)據(jù)域ｄata和指針域next組成,fronｔ和reａｒ分別為鏈隊列的頭指針和尾指針。設p指向要入隊的新結(jié)點(該結(jié)點已被賦值)，則入隊操作為（）。A.rｅａｒ->next=p;rｅar=p；B.reaｒ－>neｘｔ=ｐ;p=reａr;Ｃ.p=rｅaｒ->ｎext;ｒear=ｐ;D.reａr=p;rear－>next=p;１1．以下說法對的的是()。A．隊列是后進先出B.棧的特點是后進后出C.棧的刪除和插入操作都只能在棧頂進行Ｄ.隊列的刪除和插入操作都只能在隊頭進行12.以下說法不對的的是()。A．順序棧中,棧滿時再進行進棧操作稱為“上溢”B.順序棧中,?？諘r再作出棧棧操作稱為“下溢”C．順序隊列中，隊列的頭指針和尾指針均超越隊列存儲空間的上界,則隊列已空Ｄ．順序隊列中,當尾指針已經(jīng)超越隊列存儲空間的上界，則一定是隊列已滿13.串函數(shù)SｔｒCmp（“ａbA”,”aba”)的值為（)。Ａ．1B.0C.“aｂAaba”D1４．設有一個2０階的對稱矩陣A，采用壓縮存儲方式,將其下三角部分以行序為主序存儲到一維數(shù)組中（矩陣A的第一個元素為a11,數(shù)組ｂ的下標從1開始），則矩陣元素a8,５在一維數(shù)組b中的下標是()。A．30B．28Ｃ．４0Ｄ15．設有一個12階的對稱矩陣Ａ，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組ｂ中（矩陣Ａ的第一個元素為a1，1，數(shù)組b的下標從1開始)，則矩陣Ａ中第4行的元素在數(shù)組ｂ中的下標i一定有（)。A．７≤ｉ≤1０Ｂ.１1≤ｉ≤15Ｃ.9≤i≤１４D．６≤i≤９1６．深度為5的完全二叉樹第5層上有4個結(jié)點，該樹一共有(）個結(jié)點。A．２８B．３0C.３1Ｄ17.已知一個圖的邊數(shù)為m，則該圖的所有頂點的度數(shù)之和為()。A．2mＢ.mC.2m+１D.m/２1８．已知一個圖的所有頂點的度數(shù)之和為m,則ｍ一定不也許是()。Ａ.4B.8C．1２D1９．以下說法不對的的是（）。A．連通圖G一定存在生成樹Ｂ．連通圖Ｇ的生成樹中一定包含G的所有頂點Ｃ.連通圖G的生成樹中不一定包含Ｇ的所有邊D.連通圖G的生成樹可以是不連通的20.以下說法對的的是（）。A．連通圖G的生成樹中可以包含回路B．連通圖G的生成樹可以是不連通的Ｃ.連通圖G的生成樹一定是連通而不包含回路的D.連通圖G的生成樹一定是唯一的21.散列查找的原理是(）。Ａ.在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立擬定的相應關(guān)系B．按待查記錄的關(guān)鍵字有序的順序方式存儲Ｃ．按關(guān)鍵字值的比較進行查找Ｄ.基于二分查找的方法22．對n個元素進行冒泡排序，通常要進行ｎ-1趟冒泡,在第j趟冒泡中共要進行（)次元素間的比較。A.jＢ．ｊ-1C.n-ｊD2３．排序過程中，每一趟從無序子表中將一個待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當位置，直到所有排好序為止,該排序算法是(）。A.直接插入排序Ｂ．快速排序C．冒泡排序D．選擇排序２4.在排序過程中，可以有效地減少一趟排序過程中元素間的比較次數(shù)的算法是(）。A.冒泡B.選擇Ｃ．折半插入Ｄ.直接插入２5．采用順序查找法對長度為n的線性表進行查找（不采用表尾設監(jiān)視哨的方法）,最壞的情況下要進行()次元素間的比較。A.ｎ+２B.nC．n-１D．n／２26．如圖若從頂點a出發(fā)按深度優(yōu)先搜索法進行遍歷，則也許得到的頂點序列為（)。abecabecdfB．a(chǎn)beｄcfＣ.acebdfD．a(chǎn)cｆbde圖1２７.如圖若從頂點a出發(fā)按廣度優(yōu)先搜索法進行遍歷,則也許得到的頂點序列為()。ababecdhgfB.ａebcghdfC．a(chǎn)eｄfbｃghD.abｅcｄfgh圖２28.一棵哈夫曼樹有ｎ個葉子結(jié)點(終端結(jié)點），該樹總共有(）個結(jié)點。Ａ．2n-2B．２n-１C.２nD．29.一棵哈夫曼樹總共有２3個結(jié)點，該樹共有()個葉結(jié)點（終端結(jié)點)Ａ.１０B.1１C．1２D.133０.數(shù)據(jù)的()結(jié)構(gòu)與所使用的計算機無關(guān)。A.邏輯Ｂ．物理Ｃ．存儲D.邏輯與存儲二、填空題1．通常數(shù)據(jù)的邏輯結(jié)構(gòu)涉及＿__＿、____、____、____四種類型。２.通?？梢园岩槐揪哂胁煌鹿?jié)的書的目錄結(jié)構(gòu)抽象成_＿__＿___結(jié)構(gòu)。３.設有一個單向鏈表,結(jié)點的指針域為nｅxt,頭指針為heａd,p指向尾結(jié)點，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句＿_____＿＿。4.要在一個單向鏈表中p所指向的結(jié)點之后插入一個s所指向的新結(jié)點,若鏈表中結(jié)點的指針域為next，可執(zhí)行__＿＿＿___和p－＞ｎeｘt=ｓ;的操作。5．設有一個單向循環(huán)鏈表，頭指針為ｈeａd，鏈表中結(jié)點的指針域為next，p指向尾結(jié)點的直接前驅(qū)結(jié)點,若要刪除尾結(jié)點，得到一個新的單向循環(huán)鏈表,可執(zhí)行操作___＿__＿_。6.設有一個非空的鏈棧，棧頂指針為hs,要進行出棧操作，用x保存出棧結(jié)點的值,棧結(jié)點的指針域為nｅxｔ,則可執(zhí)行x=hｓ->daｔa;＿_______。7．在一個鏈隊中，f和r分別為隊頭和隊尾指針,隊結(jié)點的指針域為ｎｅxｔ,則插入一個s所指結(jié)點的操作為＿__＿＿__＿；r＝s;8.在一個不帶頭結(jié)點的非空鏈隊中，ｆ和r分別為隊頭和隊尾指針,隊結(jié)點的數(shù)據(jù)域為datａ,指針域為ｎexｔ,若要進行出隊操作,并用變量x存放出隊元素的數(shù)據(jù)值,則相關(guān)操作為x=f->datａ;＿___＿_＿_。9.循環(huán)隊列的隊頭指針為f，隊尾指針為r,當＿___＿時表白隊列為空。１0．循環(huán)隊列的最大存儲空間為MaｘSize=8,采用少用一個元素空間以有效的判斷?？栈驐M,若隊頭指針ｆront=４，則當隊尾指針rear=___＿＿＿__時，隊列為空,當rear=________時,隊列有６個元素。11．“Ａ”在存儲時占＿__＿_＿__個字節(jié)。12.稀疏矩陣存儲時,采用一個由＿_＿_、____、＿_＿_3部分信息組成的三元組唯一擬定矩陣中的一個非零元素。１3.一棵二叉樹沒有單分支結(jié)點,有6個葉結(jié)點，則該樹總共有_＿___＿_＿個結(jié)點。14．一棵二叉樹順序編號為6的結(jié)點(樹中各結(jié)點的編號與等深度的完全二叉樹中相應位置上結(jié)點的編號相同），若它存在右孩子，則右孩子的編號為__＿____＿。15.按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有____、____、＿___三種。16．結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為＿＿__＿___結(jié)構(gòu)。１7.把數(shù)據(jù)存儲到計算機中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_＿___＿__結(jié)構(gòu)。18.結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為______＿_結(jié)構(gòu)。１9.如圖3所示的二叉樹,其后序遍歷序列為。eefgibachd圖320．如圖４所示的二叉樹,其前序遍歷序列為＿＿__＿＿_＿＿。ggfabdec圖４21．二叉樹為二叉排序的充足必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。這種說法是＿_______＿＿的。(回答對的或不對的）22．在隊列的順序存儲結(jié)構(gòu)中，當插入一個新的隊列元素時，指針的值增1，當刪除一個元素隊列時，指針的值增1。23．根據(jù)搜索方法的不同，圖的遍歷有_＿__、____兩種方法2４．循環(huán)隊列的引入，目的是為了克服。三、綜合題1.（1)已知某二叉樹的后序遍歷序列是debca,中序遍歷序列是dbeａc，試畫出該二叉樹(2）若上述二叉樹的各個結(jié)點的字符分別代表不同的整數(shù)(其中沒有相等的)，并恰好使該樹成為一棵二叉排序樹，試給出a、b、c、d、e的大小關(guān)系（3)給出該樹的前序遍歷序列2．(1）設head1和p１分別是不帶頭結(jié)點的單向鏈表Ａ的頭指針和尾指針,ｈｅaｄ2和p2分別是不帶頭結(jié)點的單向鏈表B的頭指針和尾指針，若要把B鏈表接到A鏈表之后，得到一個以ｈeａd１為頭指針的單向循環(huán)鏈表，寫出其中兩個關(guān)鍵的賦值語句（不用完整程序，結(jié)點的鏈域為ｎext)。(2）單向鏈表的鏈域為nｅｘｔ，設指針p指向單向鏈表中的某個結(jié)點,指針s指向一個要插入鏈表的新結(jié)點,現(xiàn)要把ｓ所指結(jié)點插入ｐ所指結(jié)點之后，某學生采用以下語句:ｐ->next＝s；s->ｎext＝p->next；這樣做對的嗎?若對的則回答對的，若不對的則說明應如何改寫3.(１）設有一個整數(shù)序列{4０,2８,6,7２，100,3,５4｝依次取出序列中的數(shù)，構(gòu)造一棵二叉排序樹(2）對上述二叉排序樹，在等概率條件下，求成功查找的平均查找長度４.（1）畫出對長度為１０的有序表進行折半查找的鑒定樹(以序號1，２，……１0表達樹結(jié)點）(2)對上述序列進行折半查找,求等概率條件下，成功查找的平均查找長度５.（1)運用篩選過程把序列{４2,82，67,102，16，32，57，52}建成堆(小根堆),畫出相應的完全二叉樹（不規(guī)定中間過程）(2）寫出對上述堆相應的完全二叉樹進行中序遍歷得到的序列6.(１)運用篩選法，把序列{37，77，６2,97,11,27，52，４7}建成堆(小根堆），畫出相應的完全二叉樹（2)寫出對上述堆所相應的二叉樹進行前序遍歷得到的序列四、程序填空題１.以下函數(shù)在a[0］到a［ｎ-1］中,用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標,失敗時返回-1，完畢程序中的空格ｔｙpｅｄｅfsｔrｕｃt{iｎtkey;……}ＮOＤE;intBinaｒy_Search(NODEa［],intn,ｉnｔk){ｉｎtloｗ，mid，hｉgｈ;ｌｏw=0;hiｇh＝n-1;wｈｉlｅ(＿__(1)_____){ｍｉd=（low＋high)/2;if（a[ｍiｄ].kｅy==k)reｔurn＿_(２)___＿__;?elseiｆ(___(3)＿__＿＿)lｏｗ=mid+1;?ｅlse__(４）_＿___＿； ｝_＿_(5)____＿；?}2．以下函數(shù)為直接選擇排序算法,對a[1］，a[2］,…a[n]中的記錄進行直接選擇排序,完畢程序中的空格ｔypedeｆstrucｔ{intkey；……｝ＮODE;voiｄｓelsｏrt(NODEａ[],intn){ inti，j,k; NODEtemp； ｆｏｒ（i=１;ｉ<=_＿_（1)_____；i+＋)?{ ?k=ｉ;? ｆｏr(ｊ＝i＋1;j<=＿__（２)_＿___;j++)?? iｆ（a[j].keｙ<a［k].ｋey)＿＿(３)＿＿_＿__；? if(i!=k) { ｔemp=ａ[i]； ?＿_＿（4)___＿_; ? ＿＿_＿(5)＿___;??} }}3.以下函數(shù)為鏈隊列的入隊操作，x為要入隊的結(jié)點的數(shù)據(jù)域的值，front、rear分別是鏈隊列的隊頭、隊尾指針ｓtｒuｃtnｏde｛EleｍTｙpedata;structnode*nexｔ;};strｕｃｔnodｅ*frｏnt,＊ｒｅar；vｏidＩｎQuｅuｅ(ＥlemTｙpex){stｒuctｎｏdｅ＊p;p=（strｕｃｔnｏde＊）＿__（1)＿__＿_；p->data=x;p－>nｅxt=NUＬL;＿__(2)_____；ｒeａr=_＿_(3)＿_＿__;｝4.以下程序是中序遍歷二叉樹的遞歸算法的程序,完畢程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為ｌｅｆt和right,數(shù)據(jù)域data為字符型,BT指向根結(jié)點)。voidInordｅr(ｓtructＢTｒeeNoｄｅ*BＴ)｛if(ＢT!＝NUＬＬ){(１）;(2）;(３)；}}答案一、單項選擇題１.Ｄ2．Ａ3.B4.D５.Ｂ6.C７．A8．Ｄ９．B１0.A1１．Ｃ１2.D13.D14.Ｄ15.A16.D17.Ａ1８．D19.D２0．C2１．A22.C23.A2４．C2５.Ｂ26．B27.D28.B29．C3０.A二、填空題1.集合;線性；樹形；圖狀2.樹形３.p－＞nｅxt=heａd;4．s->nexｔ=p-＞neｘｔ；5.ｐ->next=hｅad;６.hs＝ｈs->neｘt;7.ｒ-＞next＝ｓ８.f＝f－>nｅxt；９.r==ｆ1０．4；211．1;２12．行號；列號；非零元13.11１4.1３1５.先序；中序；后序１6．圖狀1７.物理(存儲)18．樹形１９.gdbeihfca2０.ａｂdｅfcg21．錯誤2２．尾頭２3.深度優(yōu)先廣度優(yōu)先24.假上溢三、綜合應用題abceabced（2）d<b<e<ａ<c（3)ａbｄｅc2．(1）p１-＞nｅxt=heaｄ２；p2->next=hｅａd1；(2）不對，s-＞next＝p->neｘｔ;p－>nｅxｔ=s；4028723100544028723100546(2)AＳL=(1x１＋2x2+3x3＋4)／７=１８/7528452849631071(2）ASＬ=(1x1+2x2+3x4+4x３）/1０＝29／105.16423252571642325257678242826752573216102102初始樹堆102初始樹堆(2)102,52,42，82,16,67，３2，5７初始樹堆11372747初始樹堆11372747526277973777624752271197（2）１1，37,47,97,77，27，62,５2四、程序填空題１．（1)low<=higｈ(2）mｉd(3)a[mid].keｙ<k;（4)high=mid-１(5）reｔｕrn-1;2.(1）n-１(2)n(３）ｋ＝j(4)a[i]=a[k](5)a[k]=temｐ３.（1）malｌoｃ(sizeof(ｓtrｕctｎodｅ))(2)reａｒ->nｅxｔ＝p(3）p4．（1）Iｎoｒder(BＴ->ｌeft)(２)priｎtf(“%c”，ＢT->dａｔa)(3)Inｏrder(BT-＞rｉgｈt)數(shù)據(jù)結(jié)構(gòu)(本)期末綜合練習二一、單項選擇題1．從n個數(shù)中選取最大元素(）。A．基本操作是數(shù)據(jù)元素間的互換B．算法的時間復雜度是Ｏ(n)C．算法的時間復雜度是O(ｎ2)D.需要進行（n＋１)次數(shù)據(jù)元素間的比較2.線性表采用鏈式存儲時，其地址（）。Ａ.一定是不連續(xù)的B.必須是連續(xù)的C．部分地址必須是連續(xù)的D．可以連續(xù)也可以不連續(xù)3．設heａｄ為非空的單向循環(huán)鏈表頭指針，ｐ指向鏈表的尾結(jié)點，則滿足邏輯表達式（）的值為真。Ａ.p-＞neｘt=ＮUＬＬB.ｐ-＞nｅxt=＝hｅaｄＣ.p->neｘｔ＝headD.p==NＵLL4．帶頭結(jié)點的單向鏈表的頭指針為heａd，該鏈表為空的鑒定條件是(）的值為真。A．head==NULＬB.ｈｅaｄ-＞ｎext==heａｄＣ．heａd==head->nexｔD.head->nｅxt＝=NUＬL5．設順序存儲的線性表長度為n，要刪除第i個元素，按課本的算法,當i=(）時，移動元素的次數(shù)為3A.3Ｂ．n／2C.n-3D6.設順序存儲的線性表長度為ｎ，對于插入操作，設插入位置是等概率的,則插入一個元素平均移動元素的次數(shù)為（)。Ａ.nB.n/２C．n-１D．n-i+17.一個棧的進棧序列是a,b，c,d,則棧的不也許的出棧序列是(）。A．ｄｃbaB.bcadC．cbaｄＤ.ａｄbｃ8．一個棧的進棧序列是5,6，7，８,則棧的不也許的出棧序列是（）(進出棧操作可以交替進行）A.7,6,８，5B.5,8，６,7Ｃ．7，6，５，8D．８,7，６，５9.設有一個帶頭結(jié)點的鏈隊列,隊列中每個結(jié)點由一個數(shù)據(jù)域daｔａ和指針域ｎext組成,fｒonｔ和rear分別為鏈隊列的頭指針和尾指針,要執(zhí)行出隊操作，用x保存出隊元素的值，p為指向結(jié)點類型的指針,可執(zhí)行如下操作:ｐ=fｒoｎｔ->nexｔ;x＝p->dａt(yī)a；然后指行（)。A.fronｔ=p－>next;B．ｆront－>next=p;C．fｒｏnｔ＝p;Ｄ.ｆront-＞ｎext=p－>neｘt;１0．棧和隊列的相同點是(）。A.都是后進先出Ｂ.都是后進后出Ｃ．邏輯結(jié)構(gòu)與線性表不同D.邏輯結(jié)構(gòu)與線性表相同，都是操作規(guī)則受到限制的線性表11．在C語言中，存儲字符串“ＡＢCD”需要占用()字節(jié)。A.4B.2Ｃ．５D１2．在Ｃ語言中,運用數(shù)組ａ存放字符串“Ｈellｏ”,以下語句中對的的是(）。A.ｃｈａra[10］＝“Hello”;B.chara［１0］；ａ=“Hellｏ”;C．chａra［10］＝‘Ｈｅlｌｏ’;D．chara［１0]={‘Ｈ’,’e’,’l’,’l’，’ｏ’}；13．設有一個1０階的對稱矩陣A,采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組ｂ中。（矩陣Ａ的第一個元素為a１，1,數(shù)組b的下標從1開始），則矩陣元素a5,3相應一維數(shù)組b的數(shù)組元素是(）。Ａ．b[18]Ｂ．b[8]C．b［1３]D．b[10]１4．設有一個15階的對稱矩陣A,采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中。(矩陣A的第一個元素為a1,1,數(shù)組b的下標從1開始）,則數(shù)組元素b［１3］相應A的矩陣元素是（）。A．ａ5,3Ｂ．a(chǎn)6,４C．a(chǎn)7,2Ｄ15.深度為5的完全二叉樹共有20個結(jié)點,則第5層上有（)個結(jié)點(根所在結(jié)點為第一層)。A．３B.８C16.一棵完全二叉樹共有３０個結(jié)點，則該樹一共有()層(根結(jié)點所在層為第一層)。A．6B.4Ｃ．3D１7.已知一個圖的所有頂點的度數(shù)之和為ｍ,且m是以下4中情況之一，則ｍ只也許是(）。A．９B．７C．1５D１8.以下說法對的的是（）。A．連通圖G的生成樹中不一定包含G的所有頂點Ｂ.連通圖G的生成樹中一定要包含G的所有邊C.連通圖G一定存在生成樹Ｄ.連通圖G的生成樹一定是唯一的19．線性表只要以（）方式存儲就能進行折半查找。A.鏈接B．順序C.關(guān)鍵字有序的順序D．二叉樹2０．對二叉排序樹進行(）遍歷,遍歷所得到的序列是有序序列。Ａ.按層次Ｂ.前序Ｃ．中序D.后序21．對n個元素進行冒泡排序若某趟冒泡中只進行了()次元素間的互換,則表白序列已經(jīng)排好序。A．1B．２Ｃ.0D22.以下排序算法中,在一趟排序過程中,除了其它相關(guān)操作外，只進行一次元素間的互換的算法是（）。A.冒泡B.直接選擇C．直接插入D．折半插入２3.在對一組元素(６4,4８,1０6,33,25，82，70,55，９３）進行直接插入排序時，當進行到要把第7個元素７0插入到已經(jīng)排好序的子表時，為找到插入位置，需進行（）次元素間的比較(指由小到大排序）。A．６B.2C.3D2４．對長度為n的線性表進行順序查找,在等概率情況下,平均查找長度為（)。A.nＢ．（n＋1）/2C.2ｎD．ｎ-１ＳHAＰE\＊MERGEFORMＡT25．如圖，若從頂點a出發(fā)按廣度優(yōu)先搜索法進行遍歷,則也許得到的頂點序列為（）。abecdfgabecdfgB．a(chǎn)ｃｆedｇbC.abecｄgfD.ａｂecfdg26.如圖若從頂點a出發(fā)按深度優(yōu)先搜索法進行遍歷,則也許得到的頂點序列為（)。ababecdfgＢ．a(chǎn)eｄcbｇfC．a(chǎn)cfebdｇD.aeｃｂdgf27．一棵哈夫曼樹有10個非葉子結(jié)點(非終端結(jié)點）,該樹總共有（）個結(jié)點。A．21B．20C．２2８．一棵哈夫曼樹有１2個葉子結(jié)點（終端結(jié)點）,該樹總共有(）個結(jié)點。A．21B．2２C.23Ｄ．２４29.隊列的插入操作在（）進行。A.隊頭B.隊尾C．隊頭或隊尾D.在任意指定位置３0．隊列的刪除操作在（)進行。A.隊尾B.隊頭C.隊頭或隊尾D.在任意指定位置二、填空題1.通?？梢园涯吵鞘兄懈鞴徽军c間的線路圖抽象成________結(jié)構(gòu)。２.結(jié)構(gòu)中的元素之間存在多對多的關(guān)系稱為＿_______結(jié)構(gòu)。3.要在一個單向鏈表中刪除p所指向的結(jié)點，已知ｑ指向p所指結(jié)點的直接前驅(qū)結(jié)點,若鏈表中結(jié)點的指針域為nexｔ，則可執(zhí)行___＿___＿。4.設有一個單向循環(huán)鏈表,結(jié)點的指針域為ｎext,頭指針為heaｄ,指針ｐ指向表中某結(jié)點，若邏輯表達式＿__＿＿___的結(jié)果為真，則p所指結(jié)點為尾結(jié)點。5．設有一個鏈棧，棧頂指針為hs，現(xiàn)有一個s所指向的結(jié)點要入棧,則可執(zhí)行操作_______＿和hｓ=s;６．設有一個鏈棧，棧頂指針為hｓ,現(xiàn)有一個s所指向的結(jié)點要入棧,則可執(zhí)行操作s->next=hs；_____＿__。7.在一個不帶頭結(jié)點的非空鏈隊中，ｆ和r分別為隊頭和隊尾指針，隊結(jié)點的數(shù)據(jù)域為ｄaｔa，指針域為next，若要進行出隊操作，并用變量x存放出隊元素的數(shù)據(jù)值,則相關(guān)操作為___＿_＿_＿;____＿＿__。8.在一個鏈隊中，f和ｒ分別為隊頭和隊尾指針,隊結(jié)點的指針域為ｎｅxt,ｓ指向一個要入隊的結(jié)點，則入隊操作為__＿_____;________；９.順序存儲字符串“ABＣD”需要占用_＿＿__＿＿_個字節(jié)。10.循環(huán)隊列的最大存儲空間為MaxSize＝6，采用少用一個元素空間以有效地判斷?？栈驐M,若隊頭指針fｒｏnt＝4,當隊尾指針rear=_＿＿_＿___時隊滿，隊列中共有＿_______個元素。1１.一棵二叉樹葉結(jié)點（終端結(jié)點)數(shù)為5，單分支結(jié)點數(shù)為2，該樹共有＿＿__＿_個結(jié)點１2．程序段chａｒ＊s=”aBcＤ”；n=０;ｗhile(*s?。健痋0’{if(＊s>=’a’&＆＊s<＝’ｚ’)n＋+；ｓ++;}執(zhí)行后ｎ＝___＿___＿13.設一棵完全二叉樹,其最高層上最右邊的葉結(jié)點的編號為奇數(shù),該葉節(jié)點的雙親結(jié)點的編號為１0,該完全二叉樹一共有＿__＿____個結(jié)點。１4.一棵二叉樹中順序編號為5的結(jié)點（樹中各結(jié)點的編號與等深度的完全二叉中相應位置上結(jié)點的編號相同)，若它存在左孩子，則左孩子的編號為______＿＿。１５．結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為＿＿______結(jié)構(gòu)。１6.根據(jù)搜索方法的不同,圖的遍歷有＿_______兩種方法。1７.結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系稱為__＿_____結(jié)構(gòu)。18．結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為_______＿結(jié)構(gòu)。19.如圖所示的二叉樹,其后序遍歷序列為。eefgibachd20．一棵有n個葉結(jié)點的二叉樹，其每一個非葉結(jié)點的度數(shù)都為2,則該樹共有_______個結(jié)點。２1.圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是____＿_的。(回答對的或不對的)22.串的兩種最基本的存儲方式分別是＿_＿____和____＿__＿。23．按某關(guān)鍵字對記錄序列排序,若關(guān)鍵字的記錄在排序前和排序后仍保持它們的前后關(guān)系，則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。24.按某關(guān)鍵字對記錄序列排序，若關(guān)鍵字的記錄在排序前和排序后仍保持它們的前后關(guān)系,則排序算法是穩(wěn)定的,否則是不穩(wěn)定的。三、綜合題1.（1）一組記錄的關(guān)鍵字序列為｛45，40，６5,４3,35,95}寫出運用快速排序的方法,以第一個記錄為基準得到的一趟劃分的結(jié)果(規(guī)定給出一趟劃分中每次掃描和互換的結(jié)果）（2)同樣對序列{45，40,65,43,3５，95}運用直接插入排序，寫出逐次插入過程（從第一個元素一直到第六個元素)。２．設有一個不帶頭結(jié)點的單向鏈表,頭指針為head,結(jié)點類型為NOＤＥ，每個結(jié)點包含一個數(shù)據(jù)域data和一個指針域next,該鏈表有兩個結(jié)點，ｐ指向第二個結(jié)點(尾結(jié)點）,按以下規(guī)定寫出相應語句(不規(guī)定完整程序，（1）、（２）、(3）、（4)是一個連續(xù)的過程)。(1)新開辟一個結(jié)點,使指針s指向該結(jié)點，結(jié)點的數(shù)據(jù)成員daｔa賦值為１(2）把該結(jié)點插入鏈表的尾部,釋放指針s的指向（3）刪除鏈表的第一個結(jié)點(4)已知p1指向另一個新結(jié)點，把它插入到ｐ所指結(jié)點和尾結(jié)點之間３.（1）運用篩選過程把序列{4２,82,6７,102,16,32，5７,52}建成堆(小根堆），畫出相應的完全二叉樹（不規(guī)定中間過程)(２)寫出對上述堆相應的完全二叉樹進行中序遍歷得到的序列4.（１)設有序列{10，１2,15,19,22，25,１０0，1３０,1５０,２００｝畫出對上述序列進行折半查找的鑒定樹(以序列中的元素作為樹的結(jié)點）（2)為了成功查找到１０0需要進行多少次元素間的比較?為了查找9，通過多少次元素間的比較可知道查找失??？5．(1)設有一個整數(shù)序列{50，38,16,８2，11０，1３，6４｝，依次取出序列中的數(shù)，構(gòu)造一棵二叉排序樹（２)運用上述二叉排序樹，為了查找11０，經(jīng)多少次元素間的比較能成功查到,為了查找15，經(jīng)多少次元素間的比較可知道查找失敗6.(１）設有查找表{５，１4,2,6,18，７,4，1６,3},依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹。(2)說明如何由序列的二叉排序樹得到相應序列的排序結(jié)果，對上述二叉排序給出中序遍歷的結(jié)果。四、程序填空題1．以下函數(shù)為鏈棧的進棧操作，x是要進棧的結(jié)點的數(shù)據(jù)域，top為棧頂指針sｔrｕctｎｏdｅ{EｌemＴypedata;strｕcｔnode*nｅｘt；}；sｔruｃtｎode*tｏｐ；ｖｏiｄＰｕsh(ＥlｅmTｙpｅx）{struｃｔnｏdｅ*p;ｐ＝(ｓtｒuｃtnode*）mａlｌoｃ（___（1)__＿__)；ｐ－>data＝x；___（２）___＿_;_____(3）___;}2.設線性表為(6,10,16，４），以下程序用說明結(jié)構(gòu)變量的方法建立單向鏈表，并輸出鏈表中各結(jié)點中的數(shù)據(jù)。＃ｄeｆｉｎｅＮULL0vｏidmain(){ＮOＤEａ，b,c,d,*head,*ｐ；a．datａ＝6；ｂ．data=10;c.data=16;d.daｔa=4;/*d是尾結(jié)點*/hｅad=(1);a.ｎｅｘt=&b;ｂ．ｎeｘt=＆c；ｃ.ｎext＝&d；(2）;／*以上結(jié)束建表過程*/p＝heａd；/*ｐ為工作指針,準備輸出鏈表*/dｏ{printf(“%d＼n”,(3))；(4)；}ｗhilｅ（（５）);}3.以下函數(shù)在hｅad為頭指針的具有頭結(jié)點的單向鏈表中刪除第i個結(jié)點,structnodｅ{ｉntdata;strｕｃtnoｄe*nexｔ;｝;tyｐedeｆ