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

數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)202３年12月期末綜合練習(xí)一一、單項(xiàng)選擇題1．?dāng)?shù)據(jù)的物理結(jié)構(gòu)(）。A．與數(shù)據(jù)的邏輯結(jié)構(gòu)無(wú)關(guān)Ｂ.僅僅涉及數(shù)據(jù)元素的表達(dá)C．只涉及數(shù)據(jù)元素間關(guān)系的表達(dá)D．涉及數(shù)據(jù)元素的表達(dá)和關(guān)系的表達(dá)2.深度為5的完全二叉樹共有２０個(gè)結(jié)點(diǎn),則第5層上有()個(gè)結(jié)點(diǎn)(根所在結(jié)點(diǎn)為第一層)。A.３B．8C.5D3.從ｎ個(gè)數(shù)中選取最大元素（）。Ａ．基本操作是數(shù)據(jù)元素間的互換B.算法的時(shí)間復(fù)雜度是O(ｎ2)C.算法的時(shí)間復(fù)雜度是O(n）D．需要進(jìn)行(n+1)次數(shù)據(jù)元素間的比較4．已知一個(gè)圖的邊數(shù)為m，則該圖的所有頂點(diǎn)的度數(shù)之和為(）。A．2mB．mC.2ｍ+１D.m/25．線性表的順序結(jié)構(gòu)中,（)。A.邏輯上相鄰的元素在物理位置上不一定相鄰Ｂ．?dāng)?shù)據(jù)元素是不能隨機(jī)訪問(wèn)的Ｃ.邏輯上相鄰的元素在物理位置上也相鄰D．進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高6.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的()結(jié)構(gòu)。A.物理B.存儲(chǔ)C.邏輯與物理Ｄ.邏輯７．帶頭結(jié)點(diǎn)的單向鏈表為空的判斷條件是()（設(shè)頭指針為hｅaｄ）。A.ｈead==NULＬB．head->nexｔ==NULＬC.head－＞neｘt=＝headD.heaｄ!=ＮULL8.鏈表所具有的特點(diǎn)是(）。Ａ．可以隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B.占用連續(xù)的存儲(chǔ)空間C.插入刪除不需要移動(dòng)元素結(jié)點(diǎn)D.可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)行直接訪問(wèn)9．線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在(）的關(guān)系。A.一對(duì)一B.一對(duì)多C.多對(duì)多Ｄ．每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼10.線性表只要以()方式存儲(chǔ)就能進(jìn)行折半查找。A．鏈接Ｂ．順序Ｃ．關(guān)鍵字有序的順序D．二叉樹11.設(shè)順序存儲(chǔ)的線性表長(zhǎng)度為n，要?jiǎng)h除第i個(gè)元素,按課本的算法,當(dāng)i＝()時(shí),移動(dòng)元素的次數(shù)為3A.3Ｂ.n/2C．n-3D12.散列查找的原理是（）。A．在待查記錄的關(guān)鍵字值與該記錄的存儲(chǔ)位置之間建立擬定的相應(yīng)關(guān)系B．按待查記錄的關(guān)鍵字有序的順序方式存儲(chǔ)C．按關(guān)鍵字值的比較進(jìn)行查找Ｄ.基于二分查找的方法1３.以下說(shuō)法不對(duì)的的是（)。Ａ.棧的特點(diǎn)是后進(jìn)先出B.隊(duì)列的特點(diǎn)是先進(jìn)先出C．棧的刪除操作在棧底進(jìn)行，插入操作在棧頂進(jìn)行Ｄ．隊(duì)列的插入操作在隊(duì)尾進(jìn)行,刪除操作在隊(duì)頭進(jìn)行１4.對(duì)ｎ個(gè)元素進(jìn)行冒泡排序若某趟冒泡中只進(jìn)行了（)次元素間的互換,則表白序列已經(jīng)排好序。A.１B.2Ｃ.0D15．一個(gè)棧的進(jìn)棧序列是a,ｂ,c，ｄ,則棧的不也許的出棧序列是（）。A．a(chǎn)dbcB．bcadＣ．cbaｄＤ.ｄcba16.排序過(guò)程中,每一趟從無(wú)序子表中將一個(gè)待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到所有排好序?yàn)橹?，該排序算法?)。A．直接插入排序Ｂ.快速排序C．冒泡排序Ｄ．選擇排序1７.設(shè)top是一個(gè)鏈棧的棧頂指針,棧中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域ｄata和指針域ｎｅｘt組成,設(shè)用x接受棧頂元素，則出棧操作為()。A．x=top->ｄata;top=ｔｏp->neｘt;B.tｏp=tｏp－>nexｔ；ｘ=toｐ－>data；C．ｘ＝top->nｅxt;ｔop=top－＞data;D．toｐ->next=toｐ；x＝top－＞ｄata;18．在對(duì)一組元素（64,48，106,３3,25,8２，7０，55，９3)進(jìn)行直接插入排序時(shí)，當(dāng)進(jìn)行到要把第７個(gè)元素７０插入到已經(jīng)排好序的子表時(shí)，為找到插入位置,需進(jìn)行（)次元素間的比較(指由小到大排序）。A．6Ｂ．２C.３D１9.設(shè)有一個(gè)帶頭結(jié)點(diǎn)的鏈隊(duì)列,隊(duì)列中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域data和指針域nｅｘｔ組成，ｆroｎt和rear分別為鏈隊(duì)列的頭指針和尾指針,要執(zhí)行出隊(duì)操作,用x保存出隊(duì)元素的值,p為指向結(jié)點(diǎn)類型的指針，可執(zhí)行如下操作:p=frｏnｔ->next;x＝p－>daｔa;然后執(zhí)行(）。A.fronｔ=p->next;B．front->ｎext=p->next;Ｃ.ｆｒont=p；D．fｒont-＞nｅxt=p;20.采用順序查找法對(duì)長(zhǎng)度為n的線性表進(jìn)行查找(不采用表尾設(shè)監(jiān)視哨的方法),最壞的情況下要進(jìn)行（)次元素間的比較。A．n+２B．ｎC．n－1Ｄ．ｎ/221．以下說(shuō)法對(duì)的的是（）。A．隊(duì)列是后進(jìn)先出Ｂ.棧的特點(diǎn)是后進(jìn)后出C．棧的刪除和插入操作都只能在棧頂進(jìn)行D.隊(duì)列的刪除和插入操作都只能在隊(duì)頭進(jìn)行abecabecdfgＡ．a(chǎn)cebｄｇｆＢ.abecdｇfC．a(chǎn)cfedgbD.ａｂecfdｇ圖１23．空串的長(zhǎng)度為(）。A．０B．１C.２24．元素2，4，6,8按順序依次進(jìn)棧，則該棧的不也許輸出序列是（)（進(jìn)棧出棧可以交替進(jìn)行)。A.８，6，4,2B．2,4，6，8Ｃ．4,2,8，6Ｄ．８,6,２，425.串函數(shù)ＳtrCmp(“abA”,”aba”)的值為()。A．1B.0C．“ａbAaba”D２６．排序方法中,從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法,稱為（）排序。Ａ.歸并Ｂ.插入C.選擇D．快速２7．設(shè)有一個(gè)10階的對(duì)稱矩陣Ａ，采用壓縮存儲(chǔ)方式將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組b中。(矩陣A的第一個(gè)元素為a1,1,數(shù)組ｂ的下標(biāo)從1開始),則矩陣元素a5,３相應(yīng)一維數(shù)組b的數(shù)組元素是（)。A．ｂ[１8]Ｂ．b[8]Ｃ．b[13]Ｄ.b[1０]2８.一棵哈夫曼樹總共有２3個(gè)結(jié)點(diǎn),該樹共有(）個(gè)葉結(jié)點(diǎn)（終端結(jié)點(diǎn))A．10B.13C.1129．已知如圖２所示的一個(gè)圖,若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則也許得到的一種頂點(diǎn)序列為（)。A.ａbecｄfB.ａcfebdC.aeｂcfdD．a(chǎn)eｄfcbbbdfeca圖230．隊(duì)列的插入操作在()進(jìn)行。A．隊(duì)頭B.隊(duì)尾C.隊(duì)頭或隊(duì)尾Ｄ.在任意指定位置二、填空題１.通常數(shù)據(jù)的邏輯結(jié)構(gòu)涉及集合、線性、____、__＿＿四種類型。2．一棵二叉樹沒(méi)有單分支結(jié)點(diǎn)，有６個(gè)葉結(jié)點(diǎn)，則該樹總共有_＿_(dá)__＿_(dá)_個(gè)結(jié)點(diǎn)。3.通?？梢园涯吵鞘兄懈鞴徽军c(diǎn)間的線路圖抽象成______＿＿結(jié)構(gòu)。４.設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點(diǎn)的編號(hào)為奇數(shù),該葉節(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為１0,該完全二叉樹一共有＿＿_(dá)_____個(gè)結(jié)點(diǎn)。5.設(shè)有一個(gè)單向鏈表,結(jié)點(diǎn)的指針域?yàn)椋頴xt，頭指針為ｈead，p指向尾結(jié)點(diǎn)，為了使該單向鏈表改為單向循環(huán)鏈表,可用語(yǔ)句___＿_(dá)___。6.按照二叉樹的遞歸定義,對(duì)二叉樹遍歷的常用算法有__＿_(dá)、____、___＿三種。7.循環(huán)隊(duì)列的隊(duì)頭指針為ｆ,隊(duì)尾指針為r,當(dāng)＿_(dá)_____＿時(shí)表白隊(duì)列已空。8.數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱為__＿_(dá)__＿_(dá)結(jié)構(gòu)。９.設(shè)有一個(gè)鏈棧,棧頂指針為hs,現(xiàn)有一個(gè)s所指向的結(jié)點(diǎn)要入棧,則可執(zhí)行操作___＿_(dá)___和hs=ｓ;10.把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為___＿_(dá)___結(jié)構(gòu)。1１.在一個(gè)鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針,隊(duì)結(jié)點(diǎn)的指針域?yàn)閚ext,則插入一個(gè)ｓ所指結(jié)點(diǎn)的操作為________；r=s；12.結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)一的關(guān)系稱為_＿_(dá)_＿_(dá)＿_(dá)結(jié)構(gòu)。13.串的兩種最基本的存儲(chǔ)方式分別是＿_(dá)_____和__＿＿＿＿＿＿。14.如圖3所示的二叉樹，其后序遍歷序列為。eefgibachd圖31５.一棵二叉樹中順序編號(hào)為ｉ的結(jié)點(diǎn)，若它存在左、右孩子，則左、右孩子編號(hào)分別為＿_(dá)_＿＿_(dá)_＿、＿_(dá)____＿_(dá)。１6.n個(gè)元素進(jìn)行冒泡法排序,通常需要進(jìn)行____＿_(dá)__趟冒泡。1７，兩個(gè)串相等的充足必要條件是。18.二叉樹為二叉排序的充足必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說(shuō)法是______＿_(dá)__的。(回答對(duì)的或不對(duì)的）１9．一棵二叉樹葉結(jié)點(diǎn)(終端結(jié)點(diǎn))數(shù)為5,單分支結(jié)點(diǎn)數(shù)為2,該樹共有＿_(dá)____個(gè)結(jié)點(diǎn)。2０．圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是______的。（回答對(duì)的或不對(duì)的)21.根據(jù)搜索方法的不同,圖的遍歷有_＿_(dá)_、__＿＿兩種方法。2２.根據(jù)搜索方法的不同,圖的遍歷有_＿_(dá)_、____兩種方法2３．一個(gè)有序表{３,4,10,１4，34,４3，46，64,75,78,90，96，130}用折半查找法查找值為90的結(jié)點(diǎn)，經(jīng)_＿_(dá)____＿次比較后查找成功。２4.按某關(guān)鍵字對(duì)記錄序列排序，若關(guān)鍵字的記錄在排序前和排序后仍保持它們的前后關(guān)系,則排序算法是穩(wěn)定的,否則是不穩(wěn)定的。三、綜合題１.(1）已知某二叉樹的后序遍歷序列是debｃa，中序遍歷序列是dbeaｃ，試畫出該二叉樹(2)若上述二叉樹的各個(gè)結(jié)點(diǎn)的字符分別代表不同的整數(shù)(其中沒(méi)有相等的),并恰好使該樹成為一棵二叉排序樹，試給出ａ、b、c、d、e的大小關(guān)系。（３)給出該樹的前序遍歷序列2．（1)運(yùn)用篩選過(guò)程把序列{42，82,６7，102,16，３２,5７，52}建成堆（小根堆)，畫出該堆（不規(guī)定中間過(guò)程)。(2）寫出對(duì)上述堆相應(yīng)的完全二叉樹進(jìn)行中序遍歷得到的序列。３.（1）一組記錄的關(guān)鍵字序列為{4５,40，65,４３，3５，9５}，寫出運(yùn)用快速排序的方法,以第一個(gè)記錄為基準(zhǔn)得到的一趟劃分的結(jié)果（規(guī)定給出一趟劃分中每次掃描和互換的結(jié)果)（2)對(duì)序列{４5，40,65，4３,３5,9５}運(yùn)用直接插入排序,寫出逐次插入過(guò)程（從第一個(gè)元素一直到第六個(gè)元素)。4.設(shè)查找表為(１6，15,20,５3,64,7）,（１）用冒泡法對(duì)該表進(jìn)行排序(規(guī)定升序排列）,規(guī)定寫出每一趟的排序過(guò)程。(2)在排序后的有序表的基礎(chǔ)上,畫出對(duì)其進(jìn)行折半查找所相應(yīng)的鑒定樹.(規(guī)定以數(shù)據(jù)元素作為樹結(jié)點(diǎn))（3)求在等概率條件下,對(duì)上述有序表成功查找的平均查找長(zhǎng)度.5．(1)設(shè)有查找表{5，14,2,6,１8,7,４,１6，3},依次取表中數(shù)據(jù),構(gòu)造一棵二叉排序樹．（2)說(shuō)明如何通過(guò)序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果。6．(１）設(shè)有一個(gè)整數(shù)序列｛50，38，16，82，１10,1３,64},依次取出序列中的數(shù),構(gòu)造一棵二叉排序樹（2)運(yùn)用上述二叉排序樹,為了查找11０,經(jīng)多少次元素間的比較能成功查到，為了查找1５，經(jīng)多少次元素間的比較可知道查找失敗四、程序填空題1.以下函數(shù)在a［0]到a[n-1]中，用折半查找算法查找關(guān)鍵字等于ｋ的記錄，查找成功返回該記錄的下標(biāo),失敗時(shí)返回-1，完畢程序中的空格typedｅfstruct{intｋeｙ;……}ＮOＤＥ;intBinarｙ_Seａrch(ＮODEa[],intn,iｎtｋ){ｉntlow，mid,high;ｌow=０;ｈigh=n-１;ｗhilｅ（___(１）_＿_(dá)__){mid＝(loｗ＋hiｇh)/2;iｆ（a[mid].key＝＝ｋ）ｒeturn＿_(dá)（２)____＿_(dá); ｅlsｅｉf(___（3)_____)low=ｍid+１; elsｅ__(４)______;?}__＿（5)__＿_(dá)_;?}2．以下函數(shù)為鏈隊(duì)列的入隊(duì)操作，x為要入隊(duì)的結(jié)點(diǎn)的數(shù)據(jù)域的值,front、rear分別是鏈隊(duì)列的隊(duì)頭、隊(duì)尾指針ｓtｒuctnodｅ{ＥlemTyｐｅdatａ;stｒucｔnode*next;};structｎｏde*froｎt，*ｒｅar；vｏｉdInＱｕeｕe(EleｍTｙpeｘ){stｒuctnｏde*p;ｐ=(ｓｔruｃtnodｅ*）＿＿_(dá)（１)__＿＿_(dá);p->daｔａ=ｘ；p->nexｔ＝NUＬL;__＿(2)_＿_(dá)_＿;rｅaｒ＝_＿＿(3）___＿_(dá)；}３．以下函數(shù)為鏈棧的進(jìn)棧操作,x是要進(jìn)棧的結(jié)點(diǎn)的數(shù)據(jù)域，toｐ為棧頂指針strｕctnode｛ElemTｙpｅdaｔa;structnode*neｘt;};structnode*tｏp;voiｄPush(ElｅmTypex){sｔｒuctｎoｄe*p；ｐ=(stｒuｃtnode＊)ｍalｌoc（___（1)_____)；p->ｄaｔa=ｘ;_＿_(dá)(2)_____;_＿＿_(dá)_(3)__＿;}4．以下函數(shù)在heａd為頭指針的具有頭結(jié)點(diǎn)的單向鏈表中刪除第i個(gè)結(jié)點(diǎn)，ｓtruｃtnoｄｅ{ｉｎtｄata;ｓｔrｕｃｔｎｏdｅ*next;};typedeｆstructnodｅNODEintdeleｔe（ＮOＤE＊head，inti){NODＥ*p,*q;iｎtｊ;q=heａd;j＝０；whｉｌe((q!＝NULL）&&(__＿(１)__＿_(dá)_)）｛___(2)＿_(dá)_＿_(dá);j+＋；}if(q==ＮＵLL）reｔurｎ（0）;ｐ=__＿(3)__＿_(dá)_;___(4)＿_(dá)_＿_(dá)＝p－>ｎｅxｔ;freｅ(＿_(dá)＿(５)__＿_(dá)＿);rｅtｕｒn（1);}答案一、單項(xiàng)選擇題1．D２．C3．Ｃ4.A５.C6．D7.B8.C9．A１0．C11.C1２．Ａ1３.C14.Ｃ15.Ａ16.A１7.Ａ18.Ｃ19.B20.Ｂ21.Ｄ22.Ｂ２3.Ａ24.Ｄ25.D２６．C２7.C28.D２9．D3０．Ｂ二、填空題1．樹形;圖狀2.11３．圖狀4．215.ｐ->nexｔ=head；6.先序;中序;后序7.r＝f8.樹形9.ｓ－>ｎexｔ=hs;10．物理（存儲(chǔ)）１1.r->ｎexｔ＝s12.線性1３．順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)14．gdｂeihfcａ１５．2ｉ和２i+1１6．n-１17．串長(zhǎng)度相等且相應(yīng)位置的字符相等１8.不對(duì)的19．1１20.對(duì)的21.深度優(yōu)先搜索遍歷廣度優(yōu)先搜索遍歷22．深度優(yōu)先搜索遍歷廣度優(yōu)先搜索遍歷2３．４24．相等三、綜合應(yīng)用題abced1abced圖4(２)d<b＜e＜ａ<c(３）abdeｃ2．（1）1616423252576782102圖5（2）１02，52,42，82，16，６７,32，573．(1)4５406543３59５3540654３359535406５43６595３５40434３6595３5404３４565９５(2）40４5６543３5954０４3456535953５404３４５65９54．（1)原序列1615205364７1516205３76４15162０75３6４15１67２０5364１57１620536471５16２05３6４715715206416535圖６(3)平均查找長(zhǎng)度=(1*1＋２*2+３*3）/6=14/65.（1)22461673185145圖７（2)中序遍歷50503882131106416圖８（2)三次；四次四、程序填空題１.(1)lｏw<=hiｇh(2）ｍid（3)a[miｄ]．key<k;(4)high=mid-1（５)retｕrn－1;2．(１）ｍalloc(siｚeoｆ(strｕctnoｄe）)(2)rear－>nexｔ=p(3）p3.（1）sizeof（sｔrｕctnode)(２)ｐ->ｎext＝top（3）ｔop=p4.(1)j<i－1（2)q=ｑ->nｅxt(3）q->next(4）q－>ｎｅｘｔ(5）p期末綜合練習(xí)二一、單項(xiàng)選擇題1．同一種邏輯結(jié)構(gòu)()。A.只能有唯一的存儲(chǔ)結(jié)構(gòu)Ｂ.可以有不同的存儲(chǔ)結(jié)構(gòu)Ｃ．只能表達(dá)某一種數(shù)據(jù)元素之間的關(guān)系D.以上三種說(shuō)法均不對(duì)的2．在C語(yǔ)言中，順序存儲(chǔ)長(zhǎng)度為３的字符串，需要占用（)個(gè)字節(jié)。Ａ.4B.3C3．鏈表所具有的特點(diǎn)是（)。Ａ.可以隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B.占用連續(xù)的存儲(chǔ)空間C.插入刪除元素的操作不需要移動(dòng)元素結(jié)點(diǎn)Ｄ．可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)行直接訪問(wèn)4．串函數(shù)StrＣaｔ（a，b)的功能是進(jìn)行串（)。A．比較B．復(fù)制C．賦值D.連接5.數(shù)據(jù)的物理結(jié)構(gòu)（）。A.與數(shù)據(jù)的邏輯結(jié)構(gòu)無(wú)關(guān)B.僅僅涉及數(shù)據(jù)元素的表達(dá)C．只涉及數(shù)據(jù)元素間關(guān)系的表達(dá)Ｄ.涉及數(shù)據(jù)元素的表達(dá)和關(guān)系的表達(dá)6.一棵有n個(gè)結(jié)點(diǎn)采用鏈?zhǔn)酱鎯?chǔ)的二叉樹中，共有（)個(gè)指針域?yàn)榭铡．n＋1B．nＣ．n－1D.n-27.線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在()的關(guān)系。A．一對(duì)一B．一對(duì)多C.多對(duì)多Ｄ．每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼8．設(shè)一棵哈夫曼樹共有ｎ個(gè)非葉結(jié)點(diǎn)，則該樹有(）個(gè)葉結(jié)點(diǎn)。Ａ．ｎB.n+1C9.以下表中可以隨機(jī)訪問(wèn)的是（)。A．單向鏈表B.雙向鏈表Ｃ.單向循環(huán)鏈表D．順序表１0.從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用變量x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（)。A.x＝top-＞data;toｐ=topｎｅxt;B．x＝top->datａ;C．ｔop=top->neｘt;x＝toｐ->ｄaｔa;D．ｔop=tｏp－>ｎext;x=dａt(yī)a;1１．算法的時(shí)間復(fù)雜度與（）有關(guān)。A.所使用的計(jì)算機(jī)B.與計(jì)算機(jī)的操作系統(tǒng)C．與算法自身D.與數(shù)據(jù)結(jié)構(gòu)１２.一棵完全二叉樹共有5層,且第5層上有六個(gè)結(jié)點(diǎn)，該樹共有（）個(gè)結(jié)點(diǎn)。A．３0Ｂ．20C13.設(shè)有一個(gè)長(zhǎng)度為ｎ的順序表，要?jiǎng)h除第ｉ個(gè)元素需移動(dòng)元素的個(gè)數(shù)為()。A.ｎ-i＋１B．ｎ-ｉC．n-i-1Ｄ.i14．在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的(）倍。A.3B.2.5C１５.在一個(gè)單鏈表中，ｐ、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除ｑ所指結(jié)點(diǎn)，可用的語(yǔ)句是()。A．p＝q－>nextＢ．p->nexｔ=qＣ．ｐ->ｎext=ｑnｅｘtＤ.q->ｎexｔ＝NULL１6.已知如圖1所示的一個(gè)圖,若從頂點(diǎn)V１出發(fā),按深度優(yōu)先搜索法進(jìn)行遍歷,則也許得到的一種頂點(diǎn)序列為（)。A．Ｖ１Ｖ2V4V８V5V3V6V7B．V1Ｖ2V4V５Ｖ８V３Ｖ6Ｖ７C.V1Ｖ2V4V8V３Ｖ5V6V7D．V1V3Ｖ6V7V2V4V5V８V6V6V7V1V2V3V8V4V5圖１17．從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用變量x保存被刪結(jié)點(diǎn)的值,則執(zhí)行(）。A.x=top-＞ｄatａ;ｔop=ｔｏp－＞ｎext；B.ｘ=tｏp->datａ；C．tｏp=ｔop－＞next;ｘ＝top－>datａ；Ｄ．top=top-＞ｎext;x=ｄata；18．已知如圖2所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則也許得到的一種頂點(diǎn)序列為（)。A.ａｂcedfB．a(chǎn)bcefdC.aebｃｆdD.acfdｅbbdbdfeca圖219.在一個(gè)鏈隊(duì)中，假設(shè)ｆ和ｒ分別為隊(duì)頭和隊(duì)尾指針,則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為(）。A．r=ｆ－>nｅxt;B.ｒ＝r->next;C.f=ｆ->next;D.f=r－>ｎeｘt;20.對(duì)二叉排序樹進(jìn)行（)遍歷，可以使遍歷所得到的序列是有序序列。Ａ．按層次B.后序C.中序D．前序21.一個(gè)棧的進(jìn)棧序列是a,ｂ，c，ｄ,e，則棧的不也許輸出序列是()(進(jìn)棧出棧可以交替進(jìn)行）。A.dceabＢ.edcbaC.decbaＤ.abｃｄe22.在有序表｛2，4，7,14，34，43,47,64,75,８0，90,9７,１20}中,用折半查找法查找值8０時(shí)，經(jīng)（）次比較后查找成功。A．4B．2C23.有一個(gè)長(zhǎng)度為10的有序表，按折半查找對(duì)該表進(jìn)行查找,在等概率情況下查找成功的平均比較次數(shù)為()。A．26/1０B.29/102４．有一個(gè)長(zhǎng)度為9的有序表,按折半查找對(duì)該表進(jìn)行查找,在等概率情況下查找成功的平均比較次數(shù)為（）。Ａ．25／10B．25/9C２5.排序算法中，從未排序序列中依次取出元素與已排序序列（初始為空)中的元素進(jìn)行比較（規(guī)定比較次數(shù)盡量少),然后將其放入已排序序列的對(duì)的位置的方法是（)。Ａ．冒泡B.直接插入C.折半插入D．選擇排序2６.排序算法中,從未排序序列中依次取出元素與已排序序列（初始為空)中的元素進(jìn)行比較（規(guī)定比較次數(shù)盡量少），然后將其放入已排序序列的對(duì)的位置的方法是()。A.冒泡B.直接插入C．折半插入D．選擇排序27．設(shè)有一個(gè)10階的對(duì)稱矩陣Ａ,采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹鞔鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從１開始),則矩陣中元素Ａ8,5在一維數(shù)組B中的下標(biāo)是(）。A.3３B.3２C．852８.一組記錄的關(guān)鍵字序列為（4６,79，56,38，４0,８４),運(yùn)用快速排序,以第一個(gè)關(guān)鍵字為分割元素，通過(guò)一次劃分后結(jié)果為()。A.４0,38,46，７9，5６,84Ｂ．4０,３8，46,５6,7９，84C.40，３8，４６，８４，５６,79D．3８，40,46，56,７9，8429．在一個(gè)無(wú)向圖中,所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的（）倍。Ａ．３B．2.５C3０.排序方法中，從尚未排序序列中挑選元素,并將其依次放入已排序序列（初始為空）的一端的方法,稱為（）排序。A．歸并B．插入Ｃ.快速D.選擇二、填空題1．棧和隊(duì)列的操作特點(diǎn)分別是＿_(dá)__＿_(dá)_和＿_(dá)______。2．在二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，通常每個(gè)結(jié)點(diǎn)中設(shè)立三個(gè)域,它們是______＿、、右指針。3.結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為＿_(dá)_____＿結(jié)構(gòu)。４．一棵二叉樹中順序編號(hào)為i的結(jié)點(diǎn),若它存在左、右孩子，則左、右孩子編號(hào)分別為＿_(dá)＿＿_(dá)_、____＿_(dá)__。5．根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性,通?？煞譃榧?、線性、、四類基本結(jié)構(gòu)。6.串的兩種最基本的存儲(chǔ)方式是＿＿_(dá)_＿_(dá)__和＿_(dá)______。7．規(guī)定在n個(gè)數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時(shí)間復(fù)雜度分別為＿＿_(dá)_＿＿_(dá)_和__＿＿＿＿_(dá)_。8．一棵有2n-1個(gè)結(jié)點(diǎn)的二叉樹，其每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為２，則該樹共有_______個(gè)葉結(jié)點(diǎn)。9.在一個(gè)單向鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)ｓ所指向的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行＿＿＿＿_(dá)___和p-＞next=s;的操作。１0．對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，其相應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中共有____＿_(dá)__個(gè)指針域?yàn)榭铡?１．在二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，通常每個(gè)結(jié)點(diǎn)中設(shè)立三個(gè)域，它們是值域、。1２.＿＿_(dá)__＿_(dá)_遍歷二叉排序樹可得到一個(gè)有序序列。1３．一棵二叉樹中順序編號(hào)為ｉ的結(jié)點(diǎn)，若它存在左、右孩子，則左、右孩子編號(hào)分別為________、_＿_(dá)____＿。１4．如圖３所示的二叉樹，其后序遍歷序列為。eefgibachd圖315．向一個(gè)棧頂指針為h的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，可執(zhí)行s-＞next＝h;和____＿_(dá)__。16.如圖4所示的二叉樹，其先序遍歷序列為_________。ggfabdec圖4１7．在一個(gè)鏈隊(duì)中,設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針,則插入s所指結(jié)點(diǎn)的操作為_＿_(dá)＿_(dá)___和r=ｓ;(結(jié)點(diǎn)的指針域?yàn)椋頴xt)18.圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是＿＿_(dá)_＿_(dá)的。(回答對(duì)的或不對(duì)的）1９．設(shè)有一棵深度為4的完全二叉樹，第四層上有5個(gè)結(jié)點(diǎn)，該樹共有＿_(dá)______＿個(gè)結(jié)點(diǎn)。(根所在結(jié)點(diǎn)為第１層)２0．二叉樹為二叉排序的充足必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說(shuō)法是______＿＿_(dá)_的。（回答對(duì)的或不對(duì)的)21.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素相應(yīng)的三元組涉及該元素的＿_(dá)＿_(dá)_＿_(dá)、_______和___＿_(dá)_＿三項(xiàng)信息。2２.對(duì)記錄序列排序是指按記錄的某個(gè)關(guān)鍵字排序，記錄序列按＿＿_(dá)＿_(dá)___＿排序結(jié)果是唯一的。23．在對(duì)一組記錄(55,39，97,2２，１6,73，6５,47,8８）進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄65插入到有序表時(shí)，為尋找插入位置需比較_______＿＿次。24．按某關(guān)鍵字對(duì)記錄序列排序,若在排序前和排序后仍保持它們的前后關(guān)系，則排序算法是穩(wěn)定的,否則是不穩(wěn)定的。三、綜合題1.（1)以2，3,４,7,８,9作為葉結(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)一棵哈夫曼樹有ｎ個(gè)葉結(jié)點(diǎn),它一共有多少個(gè)結(jié)點(diǎn)?簡(jiǎn)述理由？2．設(shè)查找表為（16,１5，20,53,6４,7）,(1)用冒泡法對(duì)該表進(jìn)行排序(規(guī)定升序排列),寫出每一趟的排序過(guò)程，通常對(duì)n個(gè)元素進(jìn)行冒泡排序要進(jìn)行多少趟冒泡？第j趟要進(jìn)行多少次元素間的比較？(2)在排序后的有序表的基礎(chǔ)上，畫出對(duì)其進(jìn)行折半查找所相應(yīng)的鑒定樹.（規(guī)定以數(shù)據(jù)元素作為樹結(jié)點(diǎn))3.一組記錄的關(guān)鍵字序列為(46，79，56，3８，４0,8４）（1）運(yùn)用快速排序的方法,給出以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果(給出逐次互換元素的過(guò)程，規(guī)定以升序排列)（２)對(duì)上述序列用堆排序的方法建立大根堆,規(guī)定以二叉樹逐次描述建堆過(guò)程。4.（1)設(shè)有查找表｛５,1４,2,6,18,7，４,16,３｝，依次取表中數(shù)據(jù),構(gòu)造一棵二叉排序樹。(2）說(shuō)明如何由序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果，對(duì)上述二叉排序給出中序遍歷的結(jié)果。5.設(shè)查找表為（５0，６0,7５,85,96,98,１０５,110,120，130）(1)說(shuō)出進(jìn)行折半查找成功查找到元素１20需要進(jìn)行多少次元素間的比較?(2)為了折半查找元素95,通過(guò)多少次元素間的比較才干擬定不能查到?（３）畫出對(duì)上述有序表進(jìn)行折半查找所相應(yīng)的鑒定樹(規(guī)定以數(shù)據(jù)元素作為樹結(jié)點(diǎn))６.(1）對(duì)給定權(quán)值２，1,3,３，4，5，構(gòu)造哈夫曼樹。(2)同樣用上述權(quán)值構(gòu)造另一棵哈夫曼樹,使兩棵哈夫曼樹有不同的高度，并分別求兩棵樹的帶權(quán)途徑長(zhǎng)度。四、程序填空題1.以下是用尾插法建立帶頭結(jié)點(diǎn)且有n個(gè)結(jié)點(diǎn)的單向鏈表的程序，結(jié)點(diǎn)中的數(shù)據(jù)域從前向后依次為1,2,3,……,ｎ,完畢程序中空格部分。NODE*create（n)｛ＮＯＤＥ*heaｄ,＊p,*q;inti；p＝（ＮODE*)ｍalloｃ(sｉzeof（NＯDE));heａd=（1)；（2)；ｐnexｔ=NULＬ;/＊建立頭結(jié)點(diǎn)*／for(i=1;i<＝n；i++)｛p=（3);pdata＝ｉ；pnext=NULL;qneｘt＝(4);（5）;}retuｒn(head）;}2．設(shè)線性表為(6，１0，16,4)，以下程序用說(shuō)明結(jié)構(gòu)變量的方法建立單向鏈表,并輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)。#deｆiｎeNＵＬL0voｉdmain(){ＮODEa,b，c,d,*head,*p；a.dａt(yī)ａ＝６;ｂ．data=10；c.ｄatａ=16;ｄ.ｄata=4;/*ｄ是尾結(jié)點(diǎn)＊/ｈｅad=(1）；a.next=&b;b.next=&ｃ；c．next=&d；(2）;/*以上結(jié)束建表過(guò)程＊/ｐ=heaｄ；／*ｐ為工作指針,準(zhǔn)備輸出鏈表＊／do{printf(“%d\n”，(3)）;（４）；}while((5))；｝3．以下程序是中序遍歷二叉樹的遞歸算法的程序,完畢程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為lｅft和right，數(shù)據(jù)域daｔa為字符型，BT指向根結(jié)點(diǎn))。voidIｎｏrdｅr(strucｔBTreeNｏde＊BT)｛if(ＢT!=NＵLL)｛(１）;(2）;（３);｝}4．以下程序是后序遍歷二叉樹的遞歸算法的程序，完畢程序中空格部分(樹結(jié)構(gòu)中,左、右指針域分別為lefｔ和riｇht，數(shù)據(jù)域daｔa為字符型，ＢＴ指向根結(jié)點(diǎn))。ｖoidＰostordeｒ(struｃｔBTreeNode*ＢT){if（BT!=ＮUＬL){(１);（2）;（３)