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

數(shù)據(jù)結(jié)構(gòu)(本)期末期末綜合練習(xí)一一、單項選擇題1.數(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á)2.數(shù)據(jù)元素是數(shù)據(jù)的基本單位,它（)。Ａ.只能有一個數(shù)據(jù)項組成B.至少有二個數(shù)據(jù)項組成Ｃ.可以是一個數(shù)據(jù)項也可以由若干個數(shù)據(jù)項組成D.至少有一個數(shù)據(jù)項為指針類型3.從n個數(shù)中選取最大元素，()。A.基本操作是數(shù)據(jù)元素間的互換B.算法的時間復(fù)雜度是Ｏ(n2)C.算法的時間復(fù)雜度是O(n)Ｄ．需要進(jìn)行（ｎ+１）次數(shù)據(jù)元素間的比較4．線性表的順序結(jié)構(gòu)中，（）。Ａ.邏輯上相鄰的元素在物理位置上不一定相鄰Ｂ.數(shù)據(jù)元素是不能隨機訪問的C．邏輯上相鄰的元素在物理位置上也相鄰D．進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高５．以下表中可以隨機訪問的是（)。A．單向鏈表Ｂ．雙向鏈表C.單向循環(huán)鏈表D.順序表6.帶頭結(jié)點的單向鏈表為空的判斷條件是(）(設(shè)頭指針為head）。A．head==NULＬB．ｈｅad->neｘt==NULLC．hｅａｄ->ｎext==hｅａdD.heａd!=NＵLL7.設(shè)順序存儲的線性表長度為n，對于刪除操作,設(shè)刪除位置是等概率的，則刪除一個元素平均移動元素的次數(shù)為(）。A.（n+1）／２B.nC．2nＤ．ｎ-i8．線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（)的關(guān)系。A．一對一B．一對多C.多對多Ｄ．每一個元素都有一個直接前驅(qū)和一個直接后繼9．設(shè)tｏｐ是一個鏈棧的棧頂指針,棧中每個結(jié)點由一個數(shù)據(jù)域ｄata和指針域nexｔ組成，設(shè)用x接受棧頂元素,則出棧操作為()。Ａ.ｘ=tｏｐ->ｄata;top=ｔop->next;Ｂ.ｔoｐ=top－＞ｎeｘt;ｘ=ｔｏp-＞data；C.x＝top－>ｎext;top=toｐ－>ｄatａ;Ｄ.top->nexｔ=tｏp;ｘ＝top-＞ｄata;10.設(shè)順序存儲的線性表長度為n,要刪除第i個元素，按課本的算法,當(dāng)i=（)時,移動元素的次數(shù)為３A．3B.n/2Ｃ.ｎ-3Ｄ1１.以下說法對的的是(）。A．隊列是后進(jìn)先出Ｂ.棧的特點是后進(jìn)后出C．棧的刪除和插入操作都只能在棧頂進(jìn)行D．隊列的刪除和插入操作都只能在隊頭進(jìn)行12.以下說法不對的的是（)。A．棧的特點是后進(jìn)先出Ｂ．隊列的特點是先進(jìn)先出Ｃ.棧的刪除操作在棧底進(jìn)行，插入操作在棧頂進(jìn)行Ｄ．隊列的插入操作在隊尾進(jìn)行,刪除操作在隊頭進(jìn)行13．串函數(shù)ＳtrＣmp（“ａｂＡ”,”abａ”)的值為()。A.１B.0Ｃ.“abＡaba”D1４．一個棧的進(jìn)棧序列是a,b，c，d,則棧的不也許的出棧序列是（）。A.ａｄbcB．bｃａｄC．cbadD．ｄｃba1５.設(shè)有一個1２階的對稱矩陣Ａ，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中（矩陣A的第一個元素為a1,1，數(shù)組b的下標(biāo)從1開始)，則矩陣A中第4行的元素在數(shù)組b中的下標(biāo)i一定有(）。A．７≤i≤１０B.1１≤i≤1５Ｃ.9≤i≤14D．６≤ｉ≤１６．已知一個圖的邊數(shù)為m，則該圖的所有頂點的度數(shù)之和為()。A.2mB.ｍＣ．2m+1D.m/217.設(shè)有一個帶頭結(jié)點的鏈隊列，隊列中每個結(jié)點由一個數(shù)據(jù)域data和指針域neｘt組成，frｏｎt和rear分別為鏈隊列的頭指針和尾指針，要執(zhí)行出隊操作，用x保存出隊元素的值，ｐ為指向結(jié)點類型的指針,可執(zhí)行如下操作：p=fronｔ->nｅxt;x＝p->dａt(yī)a;然后執(zhí)行（)。A.froｎt＝p->nｅｘt;B.frｏnｔ->next=p->neｘt;C．front＝p;D.frｏnt-＞next＝p;18．以下說法不對的的是(）。A.連通圖Ｇ一定存在生成樹B.連通圖Ｇ的生成樹中一定包含Ｇ的所有頂點C．連通圖G的生成樹中不一定包含G的所有邊D．連通圖G的生成樹可以是不連通的19．散列查找的原理是(）。Ａ.在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立擬定的相應(yīng)關(guān)系B.按待查記錄的關(guān)鍵字有序的順序方式存儲C.按關(guān)鍵字值的比較進(jìn)行查找Ｄ.基于二分查找的方法２0.空串的長度為（）。A.0B．1C.2Ｄ21.排序過程中,每一趟從無序子表中將一個待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置,直到所有排好序為止,該排序算法是（)。A.選擇排序B．快速排序C．冒泡排序Ｄ．直接插入排序22.采用順序查找法對長度為n的線性表進(jìn)行查找(不采用表尾設(shè)監(jiān)視哨的方法），最壞的情況下要進(jìn)行()次元素間的比較。A.ｎ＋２B．nＣ．n-１Ｄ.n／223．設(shè)有一個１0階的對稱矩陣A,采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中。(矩陣A的第一個元素為a1,1,數(shù)組ｂ的下標(biāo)從1開始），則矩陣元素a5,3相應(yīng)一維數(shù)組b的數(shù)組元素是()。A．b[18]Ｂ．b[8]C．ｂ[1３］D.b[１0]２4.如圖1若從頂點a出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷,則也許得到的頂點序列為()。ababecdhgfＢ.ａebｃｇｈdfC．ａeｄfbｃgｈD.aｂecｄfgｈ圖125．已知如圖２所示的一個圖，若從頂點ａ出發(fā),按深度優(yōu)先搜索法進(jìn)行遍歷,則也許得到的一種頂點序列為()。A.ａbecdfＢ．a(chǎn)cｆeｂｄC．a(chǎn)ebcfdＤ．a(chǎn)ｅｄfcbbbdfeca圖226.一棵哈夫曼樹總共有2３個結(jié)點，該樹共有()個葉結(jié)點（終端結(jié)點）。A．10B.１３Ｃ．1１二、填空題1.通常數(shù)據(jù)的邏輯結(jié)構(gòu)涉及集合、線性、____、___＿四種類型。２．通?？梢园涯吵鞘兄懈鞴徽军c間的線路圖抽象成_＿＿_(dá)__＿_(dá)結(jié)構(gòu)。3．設(shè)有一個單向鏈表，結(jié)點的指針域為nexｔ,頭指針為hｅad,ｐ指向尾結(jié)點，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句__＿_(dá)＿_(dá)__。４．設(shè)有一個單向循環(huán)鏈表,頭指針為ｈeaｄ，鏈表中結(jié)點的指針域為next,p指向尾結(jié)點的直接前驅(qū)結(jié)點,若要刪除尾結(jié)點，得到一個新的單向循環(huán)鏈表，可執(zhí)行操作＿_(dá)____＿_(dá)。５.循環(huán)隊列的隊頭指針為f,隊尾指針為r,當(dāng)_＿_(dá)_＿_(dá)__時表白隊列已空。6.在一個鏈隊中，f和ｒ分別為隊頭和隊尾指針,隊結(jié)點的指針域為neｘｔ，則插入一個s所指結(jié)點的操作為＿_(dá)__＿_(dá)__;r=ｓ;7．設(shè)有一個鏈棧,棧頂指針為hs，現(xiàn)有一個s所指向的結(jié)點要入棧，則可執(zhí)行操作______＿_(dá)和hs=ｓ；８．循環(huán)隊列的隊頭指針為ｆ,隊尾指針為r，當(dāng)_＿＿＿_(dá)時表白隊列為空。9.在一個鏈隊中,f和r分別為隊頭和隊尾指針,隊結(jié)點的指針域為nｅxt,則插入一個s所指結(jié)點的操作為_＿＿＿_(dá)＿_(dá)_；ｒ=s;１0．“A”在存儲時占＿_(dá)＿＿＿_(dá)__個字節(jié)。１１．串的兩種最基本的存儲方式分別是_______和___＿_(dá)___。1２.一棵二叉樹沒有單分支結(jié)點,有6個葉結(jié)點,則該樹總共有___＿＿_(dá)＿_(dá)個結(jié)點。１3.一棵二叉樹中順序編號為i的結(jié)點，若它存在左、右孩子,則左、右孩子編號分別為___＿_(dá)_＿_(dá)、________。1４．按照二叉樹的遞歸定義,對二叉樹遍歷的常用算法有____、____、____三種。15.兩個串相等的充足必要條件是。１6.把數(shù)據(jù)存儲到計算機中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為＿_(dá)______結(jié)構(gòu)。17．一棵二叉樹葉結(jié)點（終端結(jié)點）數(shù)為５,單分支結(jié)點數(shù)為2，該樹共有_____＿個結(jié)點。１8.如圖３所示的二叉樹，其后序遍歷序列為。eefgibachd圖319．根據(jù)搜索方法的不同，圖的遍歷有＿＿＿_(dá)、＿＿_(dá)＿兩種方法。20.二叉樹為二叉排序的充足必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。這種說法是__________的。(回答對的或不對的)21.一個有序表{3，4,１０，14，34,４3,４6,6４，7５，78,９0，９6，13０｝用折半查找法查找值為90的結(jié)點，經(jīng)____＿_(dá)__次比較后查找成功。三、綜合題1．(1）已知某二叉樹的后序遍歷序列是debcａ，中序遍歷序列是dｂeａc,試畫出該二叉樹(2)若上述二叉樹的各個結(jié)點的字符分別代表不同的整數(shù)(其中沒有相等的)，并恰好使該樹成為一棵二叉排序樹,試給出ａ、b、c、d、ｅ的大小關(guān)系。（３)給出該樹的前序遍歷序列2．（1)一組記錄的關(guān)鍵字序列為{4５,40,65，４３，35，９5}，寫出運用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一趟劃分的結(jié)果（規(guī)定給出一趟劃分中每次掃描和互換的結(jié)果)（2)對序列{45,40，65，4３，３5,９５}運用直接插入排序，寫出逐次插入過程（從第一個元素一直到第六個元素)。3.(１）設(shè)有一個整數(shù)序列{40,2８，６,72，1０0，３,5４｝依次取出序列中的數(shù)，構(gòu)造一棵二叉排序樹(2）對上述二叉排序樹，在等概率條件下，求成功查找的平均查找長度4.（1)設(shè)有查找表{5,14，２,6,18，７，4,1６,3},依次取表中數(shù)據(jù),構(gòu)造一棵二叉排序樹.(２)說明如何通過序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果。５.(1）運用篩選過程把序列｛4２,82,67,１0２，１6,32，57,5２}建成堆（小根堆），畫出相應(yīng)的完全二叉樹（不規(guī)定中間過程)（2）寫出對上述堆相應(yīng)的完全二叉樹進(jìn)行中序遍歷得到的序列四、程序填空題1．以下函數(shù)在a[０]到a[n-1]中,用折半查找算法查找關(guān)鍵字等于ｋ的記錄,查找成功返回該記錄的下標(biāo)，失敗時返回－1，完畢程序中的空格typｅdeｆｓtruct{ｉｎtkｅy；……}ＮODＥ;intBiｎarｙ_Seaｒch(NＯDEa[],intn,intk){ｉntlｏw,mｉd，high;ｌow=０;higｈ=n-１;while(___(1)＿_(dá)_＿_(dá)){ｍｉd＝(ｌow+hiｇｈ）/2；iｆ(a[mid］.ｋey＝=k)ｒeturn__(2)______;?elseif(___(3)_＿_(dá)＿_(dá))low=mid+1;?elsｅ__（4)__＿_(dá)_＿;?｝_＿＿（5)_＿_(dá)__;?}2．以下函數(shù)為鏈棧的進(jìn)棧操作,x是要進(jìn)棧的結(jié)點的數(shù)據(jù)域，tｏp為棧頂指針ｓtｒuctｎode{ElemTypedaｔa;structnode*neｘt；};strucｔnｏde*ｔop;voidPush（EｌemTyｐex)｛stｒucｔｎoｄe*p;p=（ｓｔｒｕctnode*)maｌloc(_＿_(dá)（1)＿_(dá)＿_(dá)_）;p->data＝x;___(２)__＿_(dá)_;____＿(３)___；}3．以下函數(shù)為鏈隊列的入隊操作，x為要入隊的結(jié)點的數(shù)據(jù)域的值，fｒｏnｔ、rear分別是鏈隊列的隊頭、隊尾指針stｒuctnode{ＥｌｅmTypeｄａt(yī)ａ;structnode＊nｅxt;};stｒucｔnodｅ*fｒonｔ，＊rｅar;voidＩnQuｅuｅ（EｌeｍＴypeｘ)｛stｒuｃtnoｄｅ＊p;p=(structnoｄe*)___(1)＿_(dá)___;p－>daｔa＝x；p->nexｔ=NUＬL；_＿_(dá)(２)_____;reａｒ=＿_(dá)_（3)__＿＿＿;}期末綜合練習(xí)一答案一、單項選擇題１．Ｄ2．C3．C4．Ｃ5．D６.B7．A８.A９.Ａ10.C11．C１２．C１3.Ｄ１4.A15.A1６.Ａ１7．Ｂ18.D19.A20.A2１.D２２．B２3.C24．D2５.D2６．D二、填空題1.樹形；圖狀2.圖狀3.p->next＝head;4.p－>nｅxt=head;５.r=f6．r－>next=s7．s->next=hｓ;8.r==f9.r->neｘt=s10.２1１．順序存儲鏈?zhǔn)酱鎯?２.1113.2i和２i+１14.先序；中序；后序１５.串長度相等且相應(yīng)位置的字符相等16．物理(存儲)17.1118．gdbeihfca1９．深度優(yōu)先搜索遍歷廣度優(yōu)先搜索遍歷20．錯誤２１．４三、綜合應(yīng)用題(每小題10分，共30分）abceabced(２)d<ｂ<e<ａ<ｃ（３）aｂdec２．(1）4５４065433595３540654３3595354065４36595354043436595３54０4３4565９5（2)40４56５４33５９540434５65３59５354０4345659５4028723100544028723100546(2)AＳL=（１ｘ1+2ｘ2＋３ｘ３+4）／７=18/7４．(1)22461673185145（2）中序遍歷５．16423252571642325257678242826752573216102102初始樹堆102初始樹堆(2)102,52，４2,82，16，67,32,5７四、程序填空題1．（1)lｏw<＝hｉgh(2）mid（3)ａ[ｍｉd]．keｙ<k;（４)high=ｍid－1(5)reｔurn-1；2.(１)lｏw＜=ｈｉgｈ(2）mｉd（３)a[mｉd].keｙ<k;（４)high=miｄ-1（5)ｒｅtｕrn－1;３.(1)siｚeｏf(ｓｔrｕctnode)(2)p－>nｅｘt＝top（3）ｔop=p4.（1）maｌｌoｃ(sｉzｅoｆ（structnode）)(2)reａｒ->next＝p（3）ｐ期末綜合練習(xí)二一、單項選擇題１．（)是性質(zhì)相同的數(shù)據(jù)元素的集合,是數(shù)據(jù)的子集。A.數(shù)據(jù)元素B.數(shù)據(jù)對象Ｃ．?dāng)?shù)據(jù)結(jié)構(gòu)D．?dāng)?shù)據(jù)項2．同一種邏輯結(jié)構(gòu)()。Ａ．只能有唯一的存儲結(jié)構(gòu)B．可以有不同的存儲結(jié)構(gòu)C．只能表達(dá)某一種數(shù)據(jù)元素之間的關(guān)系Ｄ.以上三種說法均不對的3.設(shè)鏈表中的結(jié)點是NODE類型的結(jié)構(gòu)體變量,且有NODE＊ｐ；為了申請一個新結(jié)點,并由p指向該結(jié)點,可用以下語句（)。A.p=(NODE*)ｍalｌoｃ(ｓizeｏf（NODＥ));Ｂ．p=（*NODE)ｍalloc（sizeof(NODE）);C.p＝(NOＤE)mａllｏc(sizeof(ｐ));D．p=(NODＥ*)ｍａｌloc（sizｅoｆ（p）);４．鏈表所具有的特點是（)。A.可以隨機訪問任一結(jié)點B．占用連續(xù)的存儲空間C.插入刪除元素的操作不需要移動元素結(jié)點D．可以通過下標(biāo)對鏈表進(jìn)行直接訪問5.設(shè)順序存儲的線性長度為n，要在第ｉ個元素之前插入一個新元素，按課本的算法當(dāng)i=（)時，移動元素次數(shù)為２Ａ.ｎ/2B.nC.1D.n-１６.數(shù)據(jù)的物理結(jié)構(gòu)(）。A．與數(shù)據(jù)的邏輯結(jié)構(gòu)無關(guān)B.僅僅涉及數(shù)據(jù)元素的表達(dá)C.只涉及數(shù)據(jù)元素間關(guān)系的表達(dá)D．涉及數(shù)據(jù)元素的表達(dá)和關(guān)系的表達(dá)7.一個棧的進(jìn)棧序列是1,２，3，4,則棧的不也許的出棧序列是(）（進(jìn)出棧操作可以交替進(jìn)行)A．3，２，4,1Ｂ.1，４，2，3C．4,3,2，1D.3,2，1，４8．線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在()的關(guān)系。A．一對一B．一對多Ｃ．多對多D．每一個元素都有一個直接前驅(qū)和一個直接后繼9．設(shè)有一個帶頭結(jié)點的鏈隊列，隊列中每個結(jié)點由一個數(shù)據(jù)域ｄaｔa和指針域ｎext組成，ｆrｏnt和rear分別為鏈隊列的頭指針和尾指針。設(shè)p指向要入隊的新結(jié)點(該結(jié)點已被賦值)，則入隊操作為()。A.reaｒ->next=ｐ;rear＝p;Ｂ.ｒear-＞next=p;ｐ＝reaｒ;C.p＝ｒeaｒ->ｎeｘt；ｒｅar＝p;D．rｅaｒ＝p;ｒeａr-＞next＝p;1０.以下表中可以隨機訪問的是（)。A．單向鏈表B.雙向鏈表Ｃ．單向循環(huán)鏈表D.順序表11．以下說法不對的的是(）。A．順序棧中,棧滿時再進(jìn)行進(jìn)棧操作稱為“上溢”Ｂ．順序棧中,?？諘r再作出棧棧操作稱為“下溢”Ｃ.順序隊列中，當(dāng)尾指針已經(jīng)超越隊列存儲空間的上界，則一定是隊列已滿D.順序隊列中，隊列的頭指針和尾指針均超越隊列存儲空間的上界,則隊列已空１2.算法的時間復(fù)雜度與（）有關(guān)。A.所使用的計算機B.與計算機的操作系統(tǒng)C.與算法自身D.與數(shù)據(jù)結(jié)構(gòu)13．設(shè)有一個2０階的對稱矩陣A,采用壓縮存儲方式,將其下三角部分以行序為主序存儲到一維數(shù)組中（矩陣A的第一個元素為a11,數(shù)組ｂ的下標(biāo)從1開始)，則矩陣元素a8，5在一維數(shù)組b中的下標(biāo)是(）。A．30B.28C.40Ｄ１4．設(shè)有一個長度為n的順序表,要刪除第i個元素需移動元素的個數(shù)為()。A.n-i+1B.n-ｉC.ｎ-i-1D．i15．深度為５的完全二叉樹第５層上有4個結(jié)點，該樹一共有(）個結(jié)點。A．28B.30C．31Ｄ１6．在一個單鏈表中,p、q分別指向表中兩個相鄰的結(jié)點，且q所指結(jié)點是ｐ所指結(jié)點的直接后繼，現(xiàn)要刪除q所指結(jié)點，可用的語句是（）。A.p=q－＞nextB.p->next=qC．p-＞ｎext＝qｎexｔＤ.q-＞nｅｘt=NＵLL17.已知一個圖的所有頂點的度數(shù)之和為m,則m一定不也許是（）。A.4Ｂ.8C.１２Ｄ１8.從一個棧頂指針為toｐ的鏈棧中刪除一個結(jié)點時，用變量x保存被刪結(jié)點的值，則執(zhí)行(）。Ａ.x=top－>data;ｔｏｐ=toｐ－>next;B.ｘ=tｏp－＞data;Ｃ.ｔoｐ=top->ｎeｘt;x=ｔop－>daｔａ;D.top=toｐ->neｘt；x=dａt(yī)a;19.以下說法對的的是()。A．連通圖G的生成樹中可以包含回路Ｂ.連通圖G的生成樹可以是不連通的C．連通圖Ｇ的生成樹一定是唯一的Ｄ.連通圖G的生成樹一定是連通而不包含回路的20.在一個鏈隊中,假設(shè)f和r分別為隊頭和隊尾指針,則刪除一個結(jié)點的運算為（）。Ａ.ｒ=f->nｅxt；B．r=r->ｎext；C.f=f->ｎｅxt;Ｄ．f=r->neｘt;21．對n個元素進(jìn)行冒泡排序，通常要進(jìn)行n-1趟冒泡,在第j趟冒泡中共要進(jìn)行()次元素間的比較。Ａ.jB.ｊ-1C.ｎ-jD2２．一個棧的進(jìn)棧序列是a,ｂ，ｃ，d,e，則棧的不也許輸出序列是（)(進(jìn)棧出棧可以交替進(jìn)行)。A．dceaｂＢ．edcｂaC.decbaD．a(chǎn)bcｄe２3.在排序過程中,可以有效地減少一趟排序過程中元素間的比較次數(shù)的算法是（）。A．冒泡B.選擇Ｃ．直接插入D．折半插入24．有一個長度為１0的有序表,按折半查找對該表進(jìn)行查找,在等概率情況下查找成功的平均比較次數(shù)為（)。A.２6/10Ｂ.29/1025.如圖１若從頂點a出發(fā)按深度優(yōu)先搜索法進(jìn)行遍歷,則也許得到的頂點序列為(）。abecabecdfB.abedcfC．ａcｅbdfＤ．a(chǎn)ｃfｂde圖12６.排序算法中,從未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn)行比較（規(guī)定比較次數(shù)盡量少）,然后將其放入已排序序列的對的位置的方法是(）。A．冒泡Ｂ.直接插入C.折半插入D.選擇排序27．一棵哈夫曼樹有n個葉子結(jié)點（終端結(jié)點)，該樹總共有(）個結(jié)點。A.2n-2B.２n－1C．2nＤ．22８.設(shè)有一個1０階的對稱矩陣A，采用壓縮存儲的方式,將其下三角部分以行序為主存儲到一維數(shù)組B中（數(shù)組下標(biāo)從１開始)，則矩陣中元素A８,5在一維數(shù)組B中的下標(biāo)是（)。A.３3B．32C．８5２9.數(shù)據(jù)的（）結(jié)構(gòu)與所使用的計算機無關(guān)。Ａ．邏輯B.物理Ｃ.存儲Ｄ.邏輯與存儲30．在一個無向圖中，所有頂點的度數(shù)之和等于邊數(shù)的(）倍。Ａ.３Ｂ.2.5C二、填空題1．通?？梢园岩槐揪哂胁煌鹿?jié)的書的目錄結(jié)構(gòu)抽象成_＿_(dá)_____結(jié)構(gòu)。２.棧和隊列的操作特點分別是_＿_(dá)____和____＿_(dá)__。3．要在一個單向鏈表中p所指向的結(jié)點之后插入一個ｓ所指向的新結(jié)點,若鏈表中結(jié)點的指針域為nexｔ,可執(zhí)行__＿＿_(dá)＿_(dá)＿和p->nｅｘt=s;的操作。4.結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為＿_(dá)__＿_(dá)__結(jié)構(gòu)。5.設(shè)有一個非空的鏈棧，棧頂指針為hｓ，要進(jìn)行出棧操作，用ｘ保存出棧結(jié)點的值,棧結(jié)點的指針域為ｎext,則可執(zhí)行x=hs->data;＿_(dá)_＿_(dá)___。6.根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性,通?？煞譃榧?、線性、、四類基本結(jié)構(gòu)。7．在一個不帶頭結(jié)點的非空鏈隊中，f和r分別為隊頭和隊尾指針,隊結(jié)點的數(shù)據(jù)域為data,指針域為next,若要進(jìn)行出隊操作,并用變量x存放出隊元素的數(shù)據(jù)值，則相關(guān)操作為x=f->dａt(yī)a;_______＿。8.規(guī)定在ｎ個數(shù)據(jù)元素中找其中值最大的元素,設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時間復(fù)雜度分別為_____＿_(dá)_和________。9．循環(huán)隊列的最大存儲空間為MaxＳｉze=8,采用少用一個元素空間以有效的判斷棧空或棧滿,若隊頭指針front=４,則當(dāng)隊尾指針rear=____＿_(dá)__時，隊列為空，當(dāng)ｒｅａr=________時，隊列有6個元素。１０.稀疏矩陣存儲時，采用一個由____、____、____3部分信息組成的三元組唯一擬定矩陣中的一個非零元素。11．在二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，通常每個結(jié)點中設(shè)立三個域，它們是值域、。1２.一棵二叉樹順序編號為6的結(jié)點（樹中各結(jié)點的編號與等深度的完全二叉中相應(yīng)位置上結(jié)點的編號相同）,若它存在右孩子,則右孩子的編號為__＿＿＿_(dá)__。13．向一個棧頂指針為h的鏈棧中插入一個s所指結(jié)點時,可執(zhí)行s－＞nｅxt=h;和_＿_(dá)_＿_(dá)_＿。１4.在一個鏈隊中,設(shè)f和ｒ分別為隊頭和隊尾指針,則插入s所指結(jié)點的操作為＿_(dá)__＿_(dá)__和ｒ=s;(結(jié)點的指針域為nｅxt)15．如圖２所示的二叉樹，其前序遍歷序列為_＿_(dá)___＿_(dá)_。ggfabdec圖2１6．設(shè)有一棵深度為4的完全二叉樹，第四層上有5個結(jié)點，該樹共有_____＿＿_(dá)＿個結(jié)點。（根所在結(jié)點為第1層）1７．在隊列的順序存儲結(jié)構(gòu)中，當(dāng)插入一個新的隊列元素時，指針的值增1,當(dāng)刪除一個元素隊列時,指針的值增1。１8.對稀疏矩陣進(jìn)行壓縮存儲,矩陣中每個非零元素相應(yīng)的三元組涉及該元素的_＿_(dá)____、____＿_(dá)＿和_______三項信息。1９.循環(huán)隊列的引入,目的是為了克服。20．在對一組記錄（５5，3９，97，22,16，73,６５,47,88)進(jìn)行直接插入排序時,當(dāng)把第7個記錄65插入到有序表時，為尋找插入位置需比較＿＿_(dá)___＿＿_(dá)次。三、綜合題１．（1)設(shè)hｅａd1和p1分別是不帶頭結(jié)點的單向鏈表Ａ的頭指針和尾指針,heaｄ2和p2分別是不帶頭結(jié)點的單向鏈表B的頭指針和尾指針,若要把B鏈表接到A鏈表之后，得到一個以heaｄ１為頭指針的單向循環(huán)鏈表,寫出其中兩個關(guān)鍵的賦值語句（不用完整程序，結(jié)點的鏈域為nｅxｔ)。(2)單向鏈表的鏈域為ｎｅxt，設(shè)指針p指向單向鏈表中的某個結(jié)點，指針ｓ指向一個要插入鏈表的新結(jié)點,現(xiàn)要把s所指結(jié)點插入ｐ所指結(jié)點之后，某學(xué)生采用以下語句：ｐ->next＝s;s－＞next=p->ｎexｔ;這樣做對的嗎？若對的則回答對的，若不對的則說明應(yīng)如何改寫2.(1)以2，3,4,７,8,9作為葉結(jié)點的權(quán),構(gòu)造一棵哈夫曼樹(規(guī)定每個結(jié)點的左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán))，給出相應(yīng)權(quán)重值葉結(jié)點的哈夫曼編碼。(2）一棵哈夫曼樹有n個葉結(jié)點，它一共有多少個結(jié)點？簡述理由?3.（1）畫出對長度為１0的有序表進(jìn)行折半查找的鑒定樹（以序號1,2，……10表達(dá)樹結(jié)點）(２)對上述序列進(jìn)行折半查找,求等概率條件下,成功查找的平均查找長度4.一組記錄的關(guān)鍵字序列為(46,79，56,38，4０,84)（1)運用快速排序的方法,給出以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果(給出逐次互換元素的過程,規(guī)定以升序排列）（２）對上述序列用堆排序的方法建立大根堆,規(guī)定以二叉樹逐次描述建堆過程。5.（1）運用篩選法,把序列{３7，77，62，97，１1,27，52,4７}建成堆（小根堆)，畫出相應(yīng)的完全二叉樹（2)寫出對上述堆所相應(yīng)的二叉樹進(jìn)行前序遍歷得到的序列6．設(shè)查找表為(50，60，75,8５,９6，98，10５，１10,12０,13０)(1)說出進(jìn)行折半查找成功查找到元素120需要進(jìn)行多少次元素間的比較?(2)為了折半查找元素95,通過多少次元素間的比較才干擬定不能查到？（３）畫出對上述有序表進(jìn)行折半查找所相應(yīng)的鑒定樹(規(guī)定以數(shù)據(jù)元素作為樹結(jié)點)四、程序填空題1.以下函數(shù)為直接選擇排序算法，對a[1］,a［２],…ａ[n]中的記錄進(jìn)行直接選擇排序,完畢程序中的空格tyｐeｄefstｒuct{intｋey;……}ＮODE；vｏidsｅｌsoｒｔ(NODEａ[],intn){ iｎtｉ,j，k; NODEtｅｍｐ；?foｒ(i=1;i<=___(1)_____;i++) ｛ ?k=i; ?foｒ(ｊ=ｉ+1;j＜＝_＿＿(2)___＿_(dá);j++) ??if(ａ[j].key＜ａ[k].ｋey)__（３)______； ｉf(i!=ｋ）? { ??temp=ａ[ｉ];?? _＿_(dá)(４)_＿_(dá)＿_(dá); ? _＿_(dá)_（5)____; }?｝}2．以下是用尾插法建立帶頭結(jié)點且有n個結(jié)點的單向鏈表的程序，結(jié)點中的數(shù)據(jù)域從前向后依次為１,2,3,……，n,完畢程序中空格部分。NODE*cｒeaｔe(n）｛ＮOＤE*head,*ｐ,＊ｑ;inti;p＝（NＯDE＊)ｍaｌloｃ(sｉzeof(NODE));heaｄ=(1);(2）;pｎｅxt=ＮULL;/*建立頭結(jié)點＊／fｏr（ｉ=１;i<=n;i＋+){ｐ=（3）；ｐｄatａ=i;ｐnext=NULL;qnext＝（4）;（5）；｝retuｒn(heａd）;｝3.以下程序是中序遍歷二叉樹的遞歸算法的程序,完畢程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和rigｈt，數(shù)據(jù)域datａ為字符型,BT指向根結(jié)點)。voidＩｎorder(ｓtｒuｃtBTreｅNｏde*ＢT){iｆ(BＴ!=ＮULL){（1);（2）;(3）；}}期末綜合練習(xí)二答案一、單項選擇題1．B2．B3．A4．C5.D6．D7.B８.A９.Ａ10．D11．C1２.C13.Ｄ1４．Ｂ15.D16．Ｃ17．Ｄ１8.A19.Ｄ２0.C21.Ｃ22.A23.Ｄ24.B25．B26.C２7.B2８．A29.A３0.D二、填空題1．樹形2.先進(jìn)后出、先進(jìn)先出３．s->nｅxt＝p-＞ｎeｘt；４.圖狀(網(wǎng)狀)５.hｓ=ｈs-＞nｅxt;6．樹形圖狀7.f=f－>ｎｅxｔ;８.n-1，O(n)９．4;210.行號;列號;非零元1１.左指針右指針12.131３．h=s;14.r->ｎｅxt=s；１５．ａbdｅｆcｇ１6.1２１7．尾頭18．行下標(biāo)、列下標(biāo)、非零元素值１9.假上溢20．3三、綜合應(yīng)用題1.(１)p1－>neｘｔ=heaｄ2;p2->nｅｘt＝heａd１；(2)不對,ｓ－>ｎexｔ=p－>ｎexｔ;p－>ｎext=s；2．3333(1)151815187998799854543232２:11103:11114：11０7：008:０1９:１０（2)2n-１個，由于非葉結(jié)點數(shù)比葉結(jié)點數(shù)少一個。5284952849631071(2)ASL=(1x1+2x2+３x4+4x3）/10=2９/１04.（1)初始序列４6,79,56,38,４0,8４4０,79,５6，38，40，844０，79,５6,38,79,８4４0,３8，56，38，７9,8440,３８,５6，5６，７9,8４4０，38,4６,5６,７９，8456795679384084468479384046566567938404679384084845646圖3初始樹堆11372747初始樹堆11372747526277973777624752271197(２)1１,37，47,9７,77，27,6２,526.(1)3次(２)４次967596759813010585501100512060圖5四、程序填空題1.（１)ｎ－1(2）n(3）k=j(４)ａ[i］=a[k]（5)ａ[k]＝temｐ2.(1）p(２）q=p（3）(NODE＊）ｍａlloｃ（ｓizｅｏf(ＮＯDＥ))（4)p（5）ｑ=p３.(1)Inｏrｄer（ＢT->leｆt）（２)printｆ（“％c”,BT－>daｔa)(３）Inｏrｄer（BT->right)期末綜合練習(xí)三一、單項選擇題1.深度為5的完全二叉樹共有２０個結(jié)點,則第5層上有（）個結(jié)點（根所在結(jié)點為第一層）。A．3B．8C．5Ｄ2．在C語言中，順序存儲長度為３的字符串,需要占用（)個字節(jié)。A.4B.3Ｃ3.已知一個圖的邊數(shù)為m,則該圖的所有頂點的度數(shù)之和為()。Ａ.2ｍB．mＣ.2m+1D．m/24．串函數(shù)ＳｔｒCａt(yī)（a,ｂ)的功能是進(jìn)行串（）。Ａ.比較B．復(fù)制Ｃ．賦值Ｄ．連接５.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的（）結(jié)構(gòu)。A.物理B.存儲Ｃ．邏輯與物理D.邏輯6．一棵有n個結(jié)點采用鏈?zhǔn)酱鎯Φ亩鏄渲?，共有?個指針域為空。A.n+１B．nC．ｎ-１D.n-2７．鏈表所具有的特點是(）。Ａ．可以隨機訪問任一結(jié)點B.占用連續(xù)的存儲空間C．插入刪除不需要移動元素結(jié)點D．可以通過下標(biāo)對鏈表進(jìn)行直接訪問8．設(shè)一棵哈夫曼樹共有ｎ個非葉結(jié)點，則該樹有(）個葉結(jié)點。A．ｎB.n＋1C９.線性表只要以()方式存儲就能進(jìn)行折半查找。A．鏈接B．順序C．關(guān)鍵字有序的順序D.二叉樹1０．從一個棧頂指針為ｔop的鏈棧中刪除一個結(jié)點時，用變量ｘ保存被刪結(jié)點的值,則執(zhí)行（)。A.x=toｐ－>datａ；top=topｎext;Ｂ．ｘ＝top－>data;Ｃ.ｔop=tｏp->nexｔ；x＝top->dａｔａ;D．toｐ＝top-＞next;x＝ｄata；11.散列查找的原理是(）。Ａ．在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立擬定的相應(yīng)關(guān)系Ｂ．按待查記錄的關(guān)鍵字有序的順序方式存儲C.按關(guān)鍵字值的比較進(jìn)行查找D．基于二分查找的方法12.一棵完全二叉樹共有5層，且第５層上有六個結(jié)點,該樹共有()個結(jié)點。A．３0B．20C13．對ｎ個元素進(jìn)行冒泡排序若某趟冒泡中只進(jìn)行了(）次元素間的互換，則表白序列已經(jīng)排好序。A．1B.2C．０D14．在一個無向圖中，所有頂點的度數(shù)之和等于邊數(shù)的（）倍。A.3B.2．５C1５．排序過程中,每一趟從無序子表中將一個待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置,直到所有排好序為止,該排序算法是（)。A．直接插入排序B.快速排序C.冒泡排序D．選擇排序16．已知如圖1所示的一個圖,若從頂點Ｖ1出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷,則也許得到的一種頂點序列為()。A．V1V2Ｖ4V８V5V3Ｖ6V7B．Ｖ１V2V4Ｖ5V８V3V6Ｖ7Ｃ.V1Ｖ２Ｖ4V8V3V5V6V7D.V1V3V6V7Ｖ2V4V5V8V6V6V7V1V2V3V8V4V5圖117.在對一組元素（64，４8，106，33,25,８2,70,55,93）進(jìn)行直接插入排序時,當(dāng)進(jìn)行到要把第7個元素70插入到已經(jīng)排好序的子表時,為找到插入位置,需進(jìn)行（）次元素間的比較（指由小到大排序）。Ａ．6B.2C.3D１8.已知如圖２所示的一個圖，若從頂點a出發(fā),按廣度優(yōu)先搜索法進(jìn)行遍歷,則也許得到的一種頂點序列為（)。A．a(chǎn)bcedfB．a(chǎn)ｂceｆdＣ．a(chǎn)eｂcfdD．a(chǎn)cfｄｅbbdbdfeca圖219.采用順序查找法對長度為n的線性表進(jìn)行查找(不采用表尾設(shè)監(jiān)視哨的方法），最壞的情況下要進(jìn)行（）次元素間的比較。A．n+2Ｂ.ｎC．n-1Ｄ．n/220.對二叉排序樹進(jìn)行（）遍歷,可以使遍歷所得到的序列是有序序列。A.按層次B．后序C．中序Ｄ.前序21．如圖３，若從頂點ａ出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷，則也許得到的頂點序列為（）。A.acebdgfB．a(chǎn)bｅcdｇｆＣ．ａcfedgbD.abecfdｇaabecdfg圖３22．在有序表{２，4，7,1４,３4，４3，47,64,75,80，9０，9７，1２0}中,用折半查找法查找值80時，經(jīng)（）次比較后查找成功。Ａ.４B.2C２３．元素2,4,6,８按順序依次進(jìn)棧，則該棧的不也許輸出序列是（）（進(jìn)棧出?？梢越惶孢M(jìn)行）。Ａ.8，6,4,2B.2，4，6,8C.4,2，８,6D．8,6,２，424.有一個長度為９的有序表,按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為(）。A．2５/１0B．25/9C25.排序方法中，從未排序序列中挑選元素,并將其依次放入已排序序列（初始為空）的一端的方法，稱為（）排序。A.歸并Ｂ．插入C.選擇D.快速26．排序算法中，從未排序序列中依次取出元素與已排序序列（初始為空)中的元素進(jìn)行比較(規(guī)定比較次數(shù)盡量少）,然后將其放入已排序序列的對的位置的方法是(）。Ａ．冒泡B.直接插入C.折半插入D.選擇排序2７.一棵哈夫曼樹總共有23個結(jié)點,該樹共有()個葉結(jié)點（終端結(jié)點)Ａ.10B.１３C．11２8．一組記錄的關(guān)鍵字序列為(46，7９,56,3８,40，８４），運用快速排序，以第一個關(guān)鍵字為分割元素，通過一次劃分后結(jié)果為()。Ａ.40,３8，４6，79，５６,８４Ｂ.40,38，46,56,７9,84C.4０,38，46，８4,５６,79D．38，4０,４６,56，7９，8４２9.隊列的插入操作在（)進(jìn)行。A．隊頭B.隊尾Ｃ．隊頭或隊尾Ｄ.在任意指定位置二、填空題(每小題２分，共24分)1.一棵二叉樹沒有單分支結(jié)點，有6個葉結(jié)點,則該樹總共有___＿_(dá)___個結(jié)點。2．在二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，通常每個結(jié)點中設(shè)立三個域,它們是_______、、右指針。3．設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點的編號為奇數(shù),該葉節(jié)點的雙親結(jié)點的編號為10,該完全二叉樹一共有__＿_(dá)____個結(jié)點。4.一棵二叉樹中順序編號為i的結(jié)點，若它存在左、右孩子,則左、右孩子編號分別為_＿_(dá)__＿、_＿_(dá)_____。5．按照二叉樹的遞歸定義,對二叉樹遍歷的常用算法有_＿_(dá)_、＿＿_(dá)＿、＿＿_(dá)＿三種。6.串的兩種最基本的存儲方式是__＿_(dá)＿_(dá)__和＿＿_(dá)____＿。7.數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為___＿＿_(dá)＿_(dá)結(jié)構(gòu)。8．一棵有2ｎ-1個結(jié)點的二叉樹,其每一個非葉結(jié)點的度數(shù)都為2,則該樹共有_＿_(dá)____個葉結(jié)點。9.把數(shù)據(jù)存儲到計算機中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為___＿_(dá)__＿結(jié)構(gòu)。１０.對于一棵具有n個結(jié)點的二叉樹，其相應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)中共有___＿＿_(dá)＿_(dá)個指針域為空。11.結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系稱為________結(jié)構(gòu)。12．___＿＿_(dá)__遍歷二叉排序樹可得到一個有序序列。1３．如圖4所示的二叉樹,其后序遍歷序列為。eefgibachd圖414.n個元素進(jìn)行冒泡法排序，通常需要進(jìn)行___＿_(dá)_＿_(dá)趟冒泡。15.如圖5所示的二叉樹,其先序遍歷序列為_＿_(dá)＿_(dá)____。ggfabdec圖５16.二叉樹為二叉排序的充足必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。這種說法是＿_(dá)__＿＿_(dá)___的。（回答對的或不對的)17.圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是__＿_(dá)__的。（回答對的或不對的)1８．根據(jù)搜索方法的不同,圖的遍歷有__＿_(dá)、＿＿＿_(dá)兩種方法19．對記錄序列排序是指按記錄的某個關(guān)鍵字排序，記錄序列按____＿_(dá)___排序結(jié)果是唯一的。20.按某關(guān)鍵字對記錄序列排序，若關(guān)鍵字的記錄在排序前和排序后仍保持它們的前后關(guān)系,則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。三、綜合題1.(1)運用篩選過程把序列{42,82,67，102,16，３２，5７，52}建成堆（小根堆）,畫出該堆(不規(guī)定中間過程)。（2)寫出對上述堆相應(yīng)的完全二叉樹進(jìn)行中序遍歷得到的序列。2．設(shè)查找表為(１6，15,2０,５３,64，７),(1)用冒泡法對該表進(jìn)行排序(規(guī)定升序排列），寫出每一趟的排序過程，通常對n個元素進(jìn)行冒泡排序要進(jìn)行多少趟冒泡？第ｊ趟要進(jìn)行多少次元素間的比較?(2)在排序后的有序表的基礎(chǔ)上,畫出對其進(jìn)行折半查找所相應(yīng)的鑒定樹.（規(guī)定以數(shù)據(jù)元素作為樹結(jié)點）3．(1)設(shè)有查找表{５,１4,2,６,1８,７,４,16,3｝,依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹。（2)說明如何由序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果，對上述二叉排序給出中序遍歷的結(jié)果。4.（1)設(shè)有一個整數(shù)序列{５0,38,16,82,110,13，64}，依次取出序列中的數(shù)，構(gòu)造一棵二叉排序樹(２)運用上述二叉排序樹,為了查找１１0，經(jīng)多少次元素間的比較能成功查到,為了查找15,經(jīng)多少次元素間的比較可知道查找失敗5.（1）對給定權(quán)值2,1，3,3，4,５,構(gòu)造哈夫曼樹。(2)同樣用上述權(quán)值構(gòu)造另一棵哈夫曼樹，使兩棵哈夫曼樹有不同的高度，并分別求兩棵樹的帶權(quán)途徑長度。四、程序填空題1．以下函數(shù)為鏈隊列的入隊操作,ｘ為要入隊的結(jié)點的數(shù)據(jù)域的值，froｎt、reａｒ分別是鏈隊列的隊頭、隊尾指針structnodｅ{EleｍTyｐeｄata;sｔructｎode*nｅｘt;};strｕctｎｏｄe*ｆroｎt,＊rｅar;voidInQueue(ElemTypｅｘ）{sｔructnode＊p;ｐ=(ｓtｒuctnoｄe＊）＿_(dá)＿(1)__＿_(dá)_