2023年電大數(shù)據(jù)結(jié)構(gòu)本復(fù)習(xí)題及答案

數(shù)據(jù)結(jié)構(gòu)(本)復(fù)習(xí)題一、單項(xiàng)選擇題(每小題2分，共30分）1．深度為5的完全二叉樹共有20個(gè)結(jié)點(diǎn)，則第5層上有(）個(gè)結(jié)點(diǎn)(根所在結(jié)點(diǎn)為第一層)。A．３ ?? ?? B．８C．5 ????? Ｄ．6２．已知一個(gè)圖的邊數(shù)為ｉi，則該圖的所有頂點(diǎn)的度數(shù)之和為（)。Ａ．2ｍ ? ? B．mＣ.２m+１? ?? D．３.數(shù)據(jù)結(jié)構(gòu)中,與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的(）結(jié)構(gòu)。A.物理? ??? Ｂ．存儲(chǔ)C．邏輯與物理? ?? D．邏輯4．鏈表所具有的特點(diǎn)是()。A．可以隨機(jī)訪問任一結(jié)點(diǎn) ? Ｂ．占用連續(xù)的存儲(chǔ)空間C．插人刪除不需要移動(dòng)元素結(jié)點(diǎn) D．可以通過下標(biāo)對(duì)鏈表進(jìn)行直接訪問５.線性表只要以(）方式存儲(chǔ)就能進(jìn)行折半查找。A.鏈接 ??? ? Ｂ.順序C.關(guān)鍵字有序的順序????Ｄ.二又樹６．散列查找的原理是(）。Ａ.在待查記錄的關(guān)鍵字值與該記錄的存儲(chǔ)位置之間建立擬定的相應(yīng)關(guān)系B.按待查記錄的關(guān)鍵字有序的順序方式存儲(chǔ)C.按關(guān)鍵字值的比較進(jìn)行查找D.基于二分查找的方法7．對(duì)n個(gè)元素進(jìn)行冒泡排序若某趟冒泡中只進(jìn)行了()次元素間的互換，則表白序列已經(jīng)排好序。A．1?? ???Ｂ.2C.0 D．n-１8．排序過程中,每一趟從無序子表中將一個(gè)待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到所有排好序?yàn)橹?，該排序算法?）。A．直接插入排序 ? ?Ｂ.快速排序C.冒泡排序 ?? Ｄ．選擇排序9.在對(duì)一組元素(64,4８,106，33,２5,82,7０，55,93)進(jìn)行直接插入排序時(shí),當(dāng)進(jìn)行到要把第7個(gè)元素70插入到已經(jīng)排好序的子表時(shí),為找到插人位置，需進(jìn)行()次元素n的比較（指由小到大排序)。A．６ ?? B．2C.3? ? ???D．４１0．采用順序查找法對(duì)長度為n的線性表進(jìn)行查找（不采用表尾設(shè)監(jiān)視哨的方法)，最壞的情況下要進(jìn)行()次元素間的比較。A.n+2 ? ??B．nC．n-1 ????? D．ｎ/２１1如圖,若從頂點(diǎn)a出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷，則也許得到的頂點(diǎn)序列為()。A.acebdgf? ? ?B.ａbecdgfC.acｆedｇｂ?? ?D.aｂecfdg12．元素2，4,6,8按順序依次進(jìn)棧，則該棧的不也許輸出序列是()（進(jìn)棧出棧可以交替進(jìn)行)。A.８,6，4，２ ? ?B.2,4,6，8C.4，2，８，6? ?? Ｄ．8，6，2,413.排序方法中,從未排序序列中挑選元素，并將其依次放人已排序序列（初始為空）的一端的方法，稱為()排序。A.歸并?? ? ??B.插人C．選擇 ??? Ｄ．快速I4．一棵哈夫曼樹總共有23個(gè)結(jié)點(diǎn),該樹共有()個(gè)葉結(jié)點(diǎn)（終端結(jié)點(diǎn))。A．10 ?? ? Ｂ.13C.11?? ?? Ｄ.１215.隊(duì)列的插人操作在（)進(jìn)行。A．隊(duì)頭 ?????B.隊(duì)尾C．隊(duì)頭或隊(duì)尾? ? ?Ｄ.在任意指定位置二、填空題（每小題2分。共24分)１6.一棵二又樹沒有單分支結(jié)點(diǎn),有6個(gè)葉結(jié)點(diǎn),則該樹總共有_＿_(dá)_____＿_(dá)_個(gè)結(jié)點(diǎn)。１７．設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點(diǎn)的編號(hào)為奇數(shù)，該葉節(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為10，該完全二又樹一共有_＿＿_(dá)_＿_(dá)＿_(dá)＿_(dá)個(gè)結(jié)點(diǎn)。18．按照二又樹的遞歸定義，對(duì)二叉樹遍歷的常用算法有先序、_＿_(dá)_____＿＿_(dá)、＿_(dá)____＿_(dá)__＿三種。1９.結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱為__＿_(dá)__＿_(dá)＿_(dá)_結(jié)構(gòu)。2０．把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_＿_(dá)＿＿_(dá)_____結(jié)構(gòu)。2１．結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)一的關(guān)系稱為___＿_(dá)______結(jié)構(gòu)。22．如圖2所示的二又樹,其后序遍歷序列為_＿＿＿_(dá)______＿_(dá)＿＿＿_(dá)_＿_(dá)__。2３.n個(gè)元素進(jìn)行冒泡法排序，通常需要進(jìn)行＿_(dá)＿＿_(dá)_＿_(dá)____趟排序。２4．二叉樹為二又排序的充足必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說法是＿＿_(dá)_＿＿_(dá)＿_(dá)___的。(回答對(duì)的或不對(duì)的)25.圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是__＿_(dá)_____＿＿_(dá)的。(回答對(duì)的或不對(duì)的）26．根據(jù)搜索方法的不同,圖的遍歷有____＿_(dá)__________＿＿＿_(dá)__、＿_(dá)__________＿_(dá)________兩種方法。27.按某關(guān)鍵字對(duì)記錄序列排序,若關(guān)鍵字___＿＿_(dá)_____的記錄在排序前和排序后仍保持它們的前后關(guān)系,則排序算法是穩(wěn)定的,否則是不穩(wěn)定的。三、綜合題(每小題10分,共30分)２８．(1)運(yùn)用篩選過程把序列{42，８2，67，102,16,32,57,5２}建成堆(小根堆)，畫出該堆（不規(guī)定中間過程)。(2)寫出對(duì)上述堆相應(yīng)的完全二又樹進(jìn)行中序遍歷得到的序列。２９.設(shè)查找表為(１6，15，20，５3，6４,7），(1)用冒泡法對(duì)該表進(jìn)行排序(規(guī)定升序排列），規(guī)定寫出每一趟的排序過程。(2）在排序后的有序表的基礎(chǔ)上,畫出對(duì)其進(jìn)行折半查找所相應(yīng)的鑒定樹。(規(guī)定以數(shù)據(jù)元素作為樹結(jié)點(diǎn))。(３)求在等概率條件下,對(duì)上述有序表成功查找的平均查找長度。30．(1)設(shè)有一個(gè)整數(shù)序列（5０,38,１6,82,110,１3,64}，依次取出序列中的數(shù)，構(gòu)造一棵二叉排序樹。(２).運(yùn)用上述二叉排序樹,為了查找1１0,經(jīng)多少次元素間的比較能成功查到,為了查找15,經(jīng)多少次元素間的比較可知道查找失敗?四、程序填空題(每空2分，共1６分)31.以下函數(shù)為鏈隊(duì)列的入隊(duì)操作，Ｘ為要人隊(duì)的結(jié)點(diǎn)的數(shù)據(jù)域的值,front，rear分別是鏈隊(duì)列的隊(duì)頭、隊(duì)尾指針32．以下函數(shù)在head為頭指針的具有頭結(jié)點(diǎn)的單向鏈表中刪除第1個(gè)結(jié)點(diǎn)，?參考答案一、單項(xiàng)選擇題(每小題2分,共3０分｝CＡDCCACACBBＤCDB二、填空題(每題２分，共24分)1６.１1１7．2118．中序?后序19.樹形20．物理(存儲(chǔ)）２１.線性22.gdｂeiｈfca23.Ｎ－124.不對(duì)的25．對(duì)的２6．深度優(yōu)先搜索遍歷 廣度優(yōu)先搜索遍歷27．相等三、綜合應(yīng)用題(每小題１0分，共30分)28．（1)（2）.102，52,42,8２,16,6?，32，５７２9．．（１)原序列１６?１5 2０?53?64?7１5 16 20 ５３?７?641５?16 ２０ 7 53?6415?１6?７ 20 ５3 64１５ 7 １6 2０?53 647 15?１6 20 ５3 6４(2)(３)平均查找長度=(1*1+２*2＋3＊3）/6=14／630.(1）（２)三次,四次四、程序填空題(每空2分，共16分)31．（1)ｍalloc(ｓizeoｆ(sｔruct node)）(2）rear－>next=p(3)p32．（1)j<ｉ－１(2)q＝ｑ－>nｅxt(3)q->neｘt(４)q->next(5)p一、單項(xiàng)選擇題(每小題２分,共３0分)１.數(shù)據(jù)的物理結(jié)構(gòu)()。A．與數(shù)據(jù)的邏輯結(jié)構(gòu)無關(guān) ? ?Ｂ．僅僅涉及數(shù)據(jù)元素的表達(dá)C．只涉及數(shù)據(jù)元素間關(guān)系的表達(dá) ???D.涉及數(shù)據(jù)元素的表達(dá)和關(guān)系的表達(dá)2.從n個(gè)數(shù)中選取最大元素()。A．基本操作是數(shù)據(jù)元素間的互換 ? ?B.算法的時(shí)間復(fù)雜度是O(n2)C．算法的時(shí)間復(fù)雜度是Ｏ（n）? ???Ｄ．需要進(jìn)行(n+1)次數(shù)據(jù)元素間的比較3．線性表的順序結(jié)構(gòu)中,（)。A．邏輯上相鄰的元素在物理位置上不一定相鄰B.數(shù)據(jù)元素是不能隨機(jī)訪問的Ｃ．邏輯上相鄰的元素在物理位置上也相鄰D.進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高4.帶頭結(jié)點(diǎn)的單向鏈表為空的判斷條件是（)(設(shè)頭指針為heａd)。Ａ.head=＝NULＬ? ? ? ?B．hｅaｄ-＞ｎext==NＵLLＣ．heａd－>nｅxt=＝heａd ?? D.hｅaｄ?。剑蜺LＬ5.線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在()的關(guān)系。A．一對(duì)一?? ? ? ?Ｂ.一對(duì)多C．多對(duì)多 ? ? ?D.每一個(gè)元素都有－個(gè)直接前驅(qū)和一個(gè)直接后繼6．設(shè)順序存儲(chǔ)的線性表長度為ｎ,要?jiǎng)h除第i個(gè)元素，按課本的算法,當(dāng)ｉ=(），移動(dòng)元素的次數(shù)為3。Ａ．3? ? B．n/2C．ｎ-3? ? D．47．以下說法不對(duì)的的是(）。A．棧的特點(diǎn)是后進(jìn)先出B.隊(duì)列的特點(diǎn)是先進(jìn)先出C棧的刪除操作在棧底進(jìn)行，插入操作在棧頂進(jìn)行B隊(duì)列的插入操作在隊(duì)尾進(jìn)行，刪除操作在隊(duì)頭進(jìn)行８．一個(gè)棧的進(jìn)棧序列是ａ，h，c，d,則棧的不也許的出棧序列是()。A．a(chǎn)dbc ?? ? ?B．bｅadC.cbad??? ? ??? D．dcba9．設(shè)toｐ是一個(gè)鏈榜的棧頂指針,棧中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域ｄata和指針域next組成,設(shè)用x接受棧頂元素，則出棧操作為()。A.x=ｔop-＞datａ;ｔｏp=ｔｏp->ｎext； ?Ｂ．top=top－＞neｘt；x＝tｏp->data；C．x=tｏp－>nｅｘｔ；ｔop=top－＞data；? Ｄ．top－>nexｔ=tｏp;x=top->dａt(yī)ａ;１0．設(shè)有一個(gè)帶頭結(jié)點(diǎn)的鏈隊(duì)列，隊(duì)列中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域datａ和指針域ｎext組成，frｏｎt和ｒear分別為鏈隊(duì)列的頭指針和尾指針，要執(zhí)行出隊(duì)操作,用x保存出隊(duì)元素的值,p為指向結(jié)點(diǎn)類型的指針,可執(zhí)行如下操作:p＝frｏnt->ｎext;x=ｐ->ｄａt(yī)ａ;然后執(zhí)行()。A.frｏｎｔ=p->ｎext; ? ? Ｂ．front->neｘt=p-＞next;C．frｏnt=p; ?????D．froｎt->nｅxt＝p;11．以下說法對(duì)的的是（)。A.隊(duì)列是后進(jìn)先出B．棧的特點(diǎn)是后進(jìn)后出Ｃ.攏的刪除和插入操作都只能在棧頂進(jìn)行D.隊(duì)列的刪除和插入操作都只能在隊(duì)頭進(jìn)行１2.在C語言中，存儲(chǔ)字符串"ABＣD＂需要占用(）字節(jié)。A.4 ? ? ???Ｂ．2C.5? ? ?? ?D．3１3.串函數(shù)ＳｔｒCmp("ａbA",＂ａｂa")的值為(）。A．1? ??? ? ?B.0C．＂abAａba" ???????D.－114.設(shè)有一個(gè)1０階的對(duì)稱矩陣A,采用壓縮存儲(chǔ)方式將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組b中。(矩陣A的第一個(gè)元素為ａl,l,數(shù)組b的下標(biāo)從1開始）,則矩陣元素a5,3相應(yīng)一維數(shù)組b的數(shù)組元素是()。A．b［1８]??? ??? B．b[8]Ｃ.b[１3] ? ? D.b[lＯ]1５．已知如圖１所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則也許得到的一種頂點(diǎn)序列為()。A.abeｃdf ???? ???Ｂ.ａcfebdc.aｅbcｆｄ? ??D.aeｄfcｂ二、填空題{每小黯２分，共2４分}1６.通常數(shù)據(jù)的邏輯結(jié)構(gòu)涉及集合、線性、_＿_(dá)____＿_(dá)___＿＿＿_(dá)、__＿_(dá)＿＿_(dá)＿＿＿_(dá)＿_(dá)__＿四種類型。１７．通?？梢园涯吵鞘兄懈鞴徽军c(diǎn)間的線路圖抽象成__＿＿_(dá)_＿＿_(dá)__＿_(dá)_＿_(dá)_結(jié)構(gòu)。18.設(shè)有一個(gè)單向鏈表,結(jié)點(diǎn)的指針域?yàn)椋頴xt，頭指針為head，ｐ指向尾結(jié)點(diǎn),為了使該單向鏈表改為單向循環(huán)鏈表,可用語句＿＿＿_(dá)__________＿_(dá)＿。19.循環(huán)隊(duì)列的隊(duì)頭指針為f,隊(duì)尾指針為ｒ，當(dāng)___＿_(dá)＿_(dá)＿_(dá)_____＿_(dá)＿時(shí)表白隊(duì)列已空。2０．設(shè)有一個(gè)鏈錢,棧頂指針為hs,現(xiàn)有一個(gè)s所指向的結(jié)點(diǎn)要入棧，則可執(zhí)行操作_＿_(dá)＿_(dá)＿_(dá)＿_(dá)_＿_(dá)＿＿_(dá)_＿和hs＝s。２1.在-個(gè)鏈隊(duì)中,f和r分別為隊(duì)頭和隊(duì)尾指針,隊(duì)結(jié)點(diǎn)的指針域?yàn)閚ext，則插入一個(gè)s所指結(jié)點(diǎn)的操作為＿_(dá)＿_(dá)_＿_(dá)＿_(dá)__＿_(dá)＿_(dá)__;r=s。2２．串的兩種最基本的存儲(chǔ)方式分別是____＿_(dá)＿_(dá)＿_(dá)＿_(dá)_____和＿＿＿_(dá)＿_(dá)_＿＿_(dá)_______。23.一棵二叉樹中順序編號(hào)為i的結(jié)點(diǎn)，若它存在左、右孩子，則左、右孩子編號(hào)分別為__＿＿_(dá)_＿＿_(dá)_______＿、____＿＿_(dá)_＿_(dá)__＿＿_(dá)__。2４．兩個(gè)串相等的充足必要條件是_＿_(dá)_＿_(dá)___＿＿_(dá)_＿_(dá)＿＿＿_(dá)_______＿_(dá)__＿_(dá)_＿_(dá)_＿＿_(dá)__＿_(dá)__＿_(dá)___＿。2５.一棵二叉樹葉結(jié)點(diǎn)〈終端結(jié)點(diǎn)〉數(shù)為5，單分支結(jié)點(diǎn)數(shù)為2，該樹共有_＿_(dá)＿_(dá)__＿_(dá)_＿_(dá)個(gè)結(jié)點(diǎn)。26．根據(jù)搜索方法的不同,圖的遍歷有__________＿_(dá)＿_(dá)__＿＿_(dá)__＿_(dá)__＿_(dá)___＿_(dá)__、_____＿_(dá)_＿_(dá)＿_(dá)_＿_(dá)_＿_(dá)_＿＿_(dá)__＿_(dá)___＿_(dá)_＿_(dá)兩種方法。27．一個(gè)有序表{３，4,１0，14,３４,43,46,64,７5,78，9０，9６,130｝用折半查找法查找值為9０的結(jié)點(diǎn),經(jīng)_＿_(dá)_______＿_(dá)__＿＿_(dá)次比較后查找成功。三、綜合題（每小題１0分，共30分)２8.(1）已知某二叉樹的后序遍歷序列是debca,中序遍歷序列是dbeac，試畫出該二叉樹。(２)若上述二叉樹的各個(gè)結(jié)點(diǎn)的字符分別代表不同的整數(shù)(其中沒有相等的),并恰好使該樹成為一棵二叉排序樹,試給出a、b、c、d、ｅ的大小關(guān)系。（3）給出該樹的前序遍歷序列。29．(1)一組記錄的關(guān)鍵字序列為{４5,４0，65，43，３5，9５｝,寫出運(yùn)用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一趟劃分的結(jié)果(規(guī)定給出一趟劃分中每次掃描和互換的結(jié)果〉。(2)對(duì)序列{45,40,65,４3,３5，95}運(yùn)用直接插入排序,寫出逐次插入過程（從第一個(gè)元素一直到第六個(gè)元素〉。30.(1)設(shè)有查找表{5,14，2,6，１8，7,４，16，3｝,依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹。(２)說明如何通過序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果。四、程序填空題（每空2分,共1６分）３１．以下函數(shù)在ａ[O]到a［n－1］中,用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標(biāo),失敗時(shí)返回-1，完畢程序中的空格。３2．以下函數(shù)為鏈棧的進(jìn)棧操作，ｘ是要進(jìn)棧的結(jié)點(diǎn)的數(shù)據(jù)域,tｏp為錢頂指針

參考答案一、單項(xiàng)選擇題（每小題2芳，共３0分)ＤCCBACCAABCCDCD二、填空題（每題2分，共24分}1６．樹形、圖狀１7．圖狀18．p->nｅxt＝heａd;19．r=f２0.在＞ｎext=hｓ；21．r-＞next＝的2２．順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)23.2i、2i＋１２4.串長度相等且相應(yīng)位置的字符相等26.深度優(yōu)先搜索遍歷、廣度優(yōu)先搜索遍歷2７.４三、結(jié)合應(yīng)用題(每小題10分,共３0分）28．(1)(2）d＜b<e<a<c(3)ａｂｄｅｃ四、程序填空題(每空2分,共１6分）一、單項(xiàng)選擇題（每小題2分，共30分)1．()是性質(zhì)相同的數(shù)據(jù)元素的集合,是數(shù)據(jù)的子集。Ａ.數(shù)據(jù)元素? ? ??B.數(shù)據(jù)對(duì)象C．?dāng)?shù)據(jù)結(jié)構(gòu)?? D.數(shù)據(jù)項(xiàng)2．設(shè)鏈表中的結(jié)點(diǎn)是NOＤE類型的結(jié)構(gòu)體變量，且有NODE頭P;為了申請(qǐng)一個(gè)新結(jié)點(diǎn)，并由p指向該結(jié)點(diǎn)，可用以下語句(）。Ａ.ｐ=(NＯＤＥ＊)mallｏC{sｉzeof(NOＤE); ?B.p=(*OＤE)malｌoC(siｚeof(NOＤE）);C．p=（NＯDE)malloC(sｉｚeof(p)) ? D.p=(NＯＤE*)ｍallｏC(ｓiｚeof(p））;3．設(shè)順序存儲(chǔ)的線性表長度為n,要在第i個(gè)元素之前插入一個(gè)新元素,按課本的算法當(dāng)ｉ=()時(shí),移動(dòng)元素次數(shù)為２。A.n／2?? ? B.nC.1??? ? ? D．n-l４.一個(gè)棧的進(jìn)棧序列是1，2，3，４，則棧的不也許的出棧序列是()(進(jìn)出棧操作可以交替進(jìn)行)。A．3,2,4,１ ? ? B.1,４,２,３Ｃ.4,3,2,1? ? D.3,2,1,4５．設(shè)有一個(gè)帶頭結(jié)點(diǎn)的鏈隊(duì)列，隊(duì)列中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域daｔa和指針域next組成,ｆront和reaｒ分別為鏈隊(duì)列的頭指針和尾指針。設(shè)ｐ指向要入隊(duì)的新結(jié)點(diǎn)（該結(jié)點(diǎn)已被賦值),則入隊(duì)操作為()。A.reａr－＞next＝p；reａｒ=p;?? ?B.rear->ｎeｘｔ=ｐ;ｐ=rear;C.ｐ=ｒear->ｎexｔ;ｒeaｒ=p;??? D.ｒear=p;ｒeａr－>nexｔ=p;6.以下說法不對(duì)的的是()。A.順序校中，錢滿時(shí)再進(jìn)行進(jìn)校操作稱為"上溢"Ｂ．順序校中,找空時(shí)再作出校校操作稱為"下溢＂Ｃ.順序隊(duì)列中，當(dāng)尾指針已經(jīng)超越隊(duì)列存儲(chǔ)空間的上界,則一定是隊(duì)列已滿D.順序隊(duì)列中,隊(duì)列的頭指針和尾指針均超越隊(duì)列存儲(chǔ)空間的上界,則隊(duì)列已空７．設(shè)有一個(gè)2０階的對(duì)稱矩陣A,采用壓縮存儲(chǔ)方式,將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組中(矩陣A的第一個(gè)元素為a１1，數(shù)組b的下標(biāo)從１開始)，則矩陣元素a8,5在一維數(shù)組b中的下標(biāo)是()。A.30 ?? Ｂ．28C.40? ? ?? D.33８.深度為5的完全二叉樹第5層上有4個(gè)結(jié)點(diǎn)，該樹一共有()個(gè)結(jié)點(diǎn)。A.２8?? ? Ｂ.３0C．３１ ? ? ?Ｄ.19９.已知一個(gè)圖的所有頂點(diǎn)的度數(shù)之和為m，則m一定不也許是(）。A．4 ? ?B．8C．12 ?? ??D.９10.以下說法對(duì)的的是（)。A.連通圖G的生成樹中可以包含回路 B.連通圖G的生成樹可以是不連通的C.連通圖Ｇ的生成樹一定是唯一的? Ｄ.連通圖G的生成樹一定是連通而不包含回路的１1．對(duì)ｎ個(gè)元素進(jìn)行冒泡排序,通常要進(jìn)行n－l趟冒泡,在第j趟冒泡中共要進(jìn)行()次元素間的比較。A．j? ?? ????Ｂ．j-lC.n－ｊ ? ?? ??D.n-j-ｌ12．在排序過程中，可以有效地減少一趟排序過程中元素間的比較次數(shù)的算法是()。Ａ.冒泡 ??? B.選擇C.直接插入 ? ?D.折半插入13．如圖若從頂點(diǎn)a出發(fā)按深度優(yōu)先搜索法進(jìn)行遍歷,則也許得到的頂點(diǎn)序列為()。Ａ.aｅbCfd ? ?? Ｂ.ａbｅdＣfC.ａCebdf? ? ???Ｄ.aCfbde14.一棵哈夫曼樹有n個(gè)葉子結(jié)點(diǎn)(終端結(jié)點(diǎn))，該樹總共有()個(gè)結(jié)點(diǎn)。A．2n-2 ??? ? B.２n-lＣ.2ｎ ? ??D.2n十215.數(shù)據(jù)的(）結(jié)構(gòu)與所使用的計(jì)算機(jī)無關(guān)。A.邏輯 ?????Ｂ.物理C．存儲(chǔ) ?????? Ｄ.邏輯與存儲(chǔ)二、填空題(每小題2分,共2４分）１.通常可以把一本具有不同章節(jié)的書的目錄結(jié)構(gòu)抽象成_____＿＿_(dá)____結(jié)構(gòu)。2.要在一個(gè)單向鏈表中ｐ所指向的結(jié)點(diǎn)之后插入一個(gè)Ｓ所指向的新結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)椋頴ｘt，可執(zhí)行_________＿_(dá)_和p->next＝=s的操作。3．設(shè)有一個(gè)非空的鏈棧,棧頂指針為hs，要進(jìn)行出棧操作,用ｘ保存出棧結(jié)點(diǎn)的值,找結(jié)點(diǎn)的指針域?yàn)椋頴xt,則可執(zhí)行x=hｓ一>daｔa；_＿_(dá)__＿_(dá)_＿_(dá)____＿_(dá)_＿＿_(dá)_＿_(dá)_。4.在一個(gè)不帶頭結(jié)點(diǎn)的非空鏈隊(duì)中,f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閐aｔa,指針域?yàn)椋頴xｔ,若要進(jìn)行出隊(duì)操作，并用變量ｘ存放出隊(duì)元素的數(shù)據(jù)值,則相關(guān)操作為ｘ=f->dａt(yī)ａ;＿_(dá)_______＿_(dá)_＿_(dá)____＿_(dá)____。5.循環(huán)隊(duì)列的最大存儲(chǔ)空間為MａxＳize＝８,采用少用一個(gè)元素空間以有效的判斷?？栈驐M,若隊(duì)頭指針frｏｎt=４，則當(dāng)隊(duì)尾指針reａr=_＿_(dá)______＿_(dá)＿時(shí),隊(duì)列為空，當(dāng)reａｒ＝_＿_(dá)_____＿_(dá)__時(shí)，隊(duì)列有６個(gè)元素。6．稀疏矩陣存儲(chǔ)時(shí),采用一個(gè)由_______＿＿_(dá)__、＿_(dá)_______＿_(dá)＿、非零元3部分信息組成的三元組唯一擬定矩陣中的一個(gè)非零元素。７.一棵二叉樹順序編號(hào)為6的結(jié)點(diǎn)(樹中各結(jié)點(diǎn)的編號(hào)與等深度的完全二叉中相應(yīng)位置上結(jié)點(diǎn)的編號(hào)相同)，若它存在右孩子，則右孩子的編號(hào)為___＿_(dá)_＿_(dá)__＿_(dá)。8.數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為＿_(dá)_＿_(dá)＿_(dá)＿_(dá)___結(jié)構(gòu)o9.數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱為＿_(dá)____＿_(dá)____結(jié)構(gòu)。10.如下圖所示的二叉樹,其前序遍歷序列為_＿_(dá)_＿_(dá)＿_(dá)__＿_(dá)1１．在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中,當(dāng)插入一個(gè)新的隊(duì)列元素時(shí),_＿＿_(dá)____＿_(dá)__指針的值增1,當(dāng)刪除一個(gè)元素隊(duì)列時(shí)，____＿_(dá)______指針的值增1。12.循環(huán)隊(duì)列的引入,目的是為了克服__________________＿_(dá)_＿_(dá)_________＿_(dá)__。三、綜合題（每小題1０分，共3０分)1．(1)設(shè)head1和P1分別是不帶頭結(jié)點(diǎn)的單向鏈表A的頭指針和尾指針，heaｄ２和P2分別是不帶頭結(jié)點(diǎn)的單向鏈表B的頭指針和尾指針,若要把B鏈表接到A鏈表之后，得到一個(gè)以ｈead１為頭指針的單向循環(huán)鏈表，寫出其中兩個(gè)關(guān)鍵的賦值語句(不用完整程序,結(jié)點(diǎn)的鏈域?yàn)椋頴xt)(2)單向鏈表的鏈域?yàn)閚ext,設(shè)指針p指向單向鏈表中的某個(gè)結(jié)點(diǎn)，指針S指向一個(gè)要插入鏈表的新結(jié)點(diǎn)，現(xiàn)要把s所指結(jié)點(diǎn)插入p所指結(jié)點(diǎn)之后，某學(xué)生采用以下語句：ｐ->neｘｔ==s；s->ｎext==p－>next;這樣做對(duì)的嗎?若對(duì)的則回答對(duì)的,若不對(duì)的則說明應(yīng)如何改寫。２.（1)畫出對(duì)長度為10的有序表進(jìn)行折半查找的鑒定樹(以序號(hào)1，2,……１０表達(dá)樹結(jié)點(diǎn))。(2)對(duì)上述序列進(jìn)行折半查找，求等概率條件下，成功查找的平均查找長度。3.（１)運(yùn)用篩選法，把序列{３７,77，６2,９7,11,２7，52,47}建成堆(小根堆)。畫出相應(yīng)的完全二叉樹。(２)寫出對(duì)上述堆所相應(yīng)的二叉樹進(jìn)行前序遍歷得到的序列。四、程序填空題(每空2分，共1６分）1.以下函數(shù)為直接選擇排序算法，對(duì)ａ[口，a［幻,…ａ［ｎ]中的記錄進(jìn)行直接選擇排序,完畢程序中的空格。2.以下程序是中序遍歷二叉樹的遞歸算法的程序，完畢程序中空格部分(樹結(jié)構(gòu)中左、右指針域分別為left和right,數(shù)據(jù)域ｄata為字符型,ＢT指向根結(jié)點(diǎn)。?參考答案一、單項(xiàng)選擇題(每小題2分,共30分）BＡDBACDDDDＣＤBBA二、填空題(每題２分，共24分）1.樹形2．ｓ－＞ｎｅｘt＝＝=ｐ－＞ｎｅｘｔ;３.hs===hｓ一>ｎｅxｔ;4.ｆ＝==f一>nｅxｔ;5.４26.行號(hào)列號(hào)7.138.圖狀9.樹形1０．a(chǎn)bdｅｆCｇ11.尾頭1２.假上溢三、綜合應(yīng)用題(每小題10分,共30分)四、程序填空題(每空２分，共16分)1.(l)ｎ-l（２)n(3)k==j(4)a[i]==ａ[k]（5)ａ[ｋ]==ｔemp2．(1)Ｉnorｄer(BT->lｅｆt）(２）printf(＂%C＂,BＴ->data)(3)Iｎｏrdｅｒ（B1－"-＞right)一、單項(xiàng)選擇題（每小題2分,共30分)1．?dāng)?shù)據(jù)元素是數(shù)據(jù)的3基本單位,它( )。A.只能有一個(gè)數(shù)據(jù)項(xiàng)組成?? ???? B.至少有二個(gè)數(shù)據(jù)項(xiàng)組成C．可以是一個(gè)數(shù)據(jù)項(xiàng)也可以由若干個(gè)數(shù)據(jù)項(xiàng)組成? ?D.至少有一個(gè)數(shù)據(jù)項(xiàng)為指針類型2.絨性表的順序結(jié)構(gòu)中，( ?)。Ａ邏輯上相鄰的元素在物理位置上不一定相鄰 ??Ｂ.數(shù)據(jù)元素是不能隨機(jī)訪問的C．邏輯上相鄰的元素在物理位置上也相鄰? Ｄ.進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高3.以下表中可以隨機(jī)訪問的是(??)。Ａ.單向鏈表? ? ? B．雙向鏈表Ｃ．單向循環(huán)鏈表 ??? ?? D．順序表4.設(shè)順序存儲(chǔ)的錢性表長度為ｎ，對(duì)于刪除操作,設(shè)刪除位置是等概率的,則刪除一個(gè)元素平均移動(dòng)元素的次數(shù)為（? )。A．(ｎ+1)/2 ? ???? Ｂ.nＣ.2ｎ ??? ?? ??Ｄ．n-i5.設(shè)top是一個(gè)鏈棧的棧頂指針，棧中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域ｄata和指針域nｅxt組成,設(shè)用x接受樓頂元素,則出棧操作為( ?)。Ａ．x=ｔop-＞dａｔa;top=ｔoｐ->ｎext； ? ? ?Ｂ．ｔop＝ｔop－＞nｅｘt；x=top->ｄatａ；C.ｘ=top－＞ｎext；ｔop=ｔｏp->datａ;?? ?D．top->neｘt=top；x=ｔｏp-＞datａ；6．以于說法對(duì)的的是( )。A．隊(duì)列是后進(jìn)先出 ?? ? ? Ｂ．棧的特點(diǎn)是后進(jìn)后出C.棧的刪除和插入操作都只能在棧頂進(jìn)行??? D.隊(duì)列的刪除和捶入操作都只能在隊(duì)頭進(jìn)行７.串函數(shù)StｒCmｐ("b"，"cd")的值為(? )。A.1????? ??? ?B．０C.＂bcｄ"??? D.-18.設(shè)有一個(gè)12階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式將其下三角部分以行序?yàn)橹鞔鎯?chǔ)如一維數(shù)組b中〈矩陣Ａ的第一個(gè)元素為al，l，數(shù)組b的下標(biāo)從1開始)，則矩陣A中第４行的元素在數(shù)組b中的下標(biāo)i一定有( )。９.已知一個(gè)圖的邊數(shù)為ｍ．則該圖的所有頂點(diǎn)的度數(shù)之和為( ?)。A．２m? ???? ? B.mC．2m+1?? ?? ? D.m／21０.以下說法不對(duì)的的是(? )。A．連通圖G一定存在生成樹B.連通圈G的生成樹中一定包含G的所有頂點(diǎn)C.連通圖Ｇ的生成制中不一定包含G的所有邊D.連通圖G的生成樹可以是不連同的１1．散列查找的原理是(? )。A.在待查記錄的關(guān)鍵字值與該記錄的存儲(chǔ)位置之間建立擬定的相應(yīng)關(guān)系Ｂ.按待查記錄的關(guān)鍵字有序的順序方式存儲(chǔ)C.按關(guān)鍵字值的比較進(jìn)行查找D.基于二分查找的方法1２．排序過程中,每一趟從無序子表中將一個(gè)待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到所有排好序?yàn)橹?，該排序算法是?）。A.直接插入排序?? ??? ??B.快速排序fＣ.冒泡排序 ?? ? ?? D.選擇排序13.采用順序查找法對(duì)長度為n的線性表進(jìn)行查找〈不采用表尾設(shè)監(jiān)視哨的方法)，最壞的情況下要進(jìn)行(?)次元素間的比較。A.n+2 ????? ? ???B.nC．n－l ? ? ? ??D.ｎ／21４.如圖若從頂點(diǎn)a出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷,則也許得到的頂點(diǎn)序列為（? )。A.aｃｅbdfgh ? ? ? ?B.ａebｃghdfC.aeｄfｂｃｇh?? ? ?? ?D．a(chǎn)beｃdfgh１5．一棵哈夫曼樹總共有23個(gè)結(jié)點(diǎn),該樹共有( ?）個(gè)葉結(jié)點(diǎn)(終端結(jié)點(diǎn)〉。A.10? ? ? ? ?? B．13C．１1????? ? ? Ｄ．121３63ｉ二、填空題{每小黯2分,共24分｝１.通常數(shù)據(jù)的邏輯結(jié)構(gòu)涉及___＿_(dá)_＿＿_(dá)___、___＿＿_(dá)＿_(dá)___、________＿_(dá)_、＿_(dá)＿＿_(dá)____＿_(dá)_四種類型。2.設(shè)有一個(gè)單向鏈表,結(jié)點(diǎn)的指針域?yàn)閚ext,頭指針為ｈeａd,ｐ指向尾結(jié)點(diǎn),為了使該單向鏈表改為單向循環(huán)鏈表,可用語句_＿＿＿_(dá)__＿＿_(dá)___________＿＿_(dá)_＿_(dá)___＿_(dá)＿＿_(dá)____。3.設(shè)有一個(gè)單向循環(huán)鏈表,頭指針為hｅad，鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext，p指向尾結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若要?jiǎng)h除尾結(jié)點(diǎn)，得到一個(gè)新的單向循環(huán)鏈表，可執(zhí)行操作__＿_(dá)＿_(dá)_＿_(dá)__＿_(dá)_＿_(dá)＿_(dá)___＿_(dá)_____。４.在一個(gè)鏈隊(duì)中，f和ｒ分別為隊(duì)頭和隊(duì)尾指針,隊(duì)結(jié)點(diǎn)的指針域?yàn)閚eｘt,則插入一個(gè)s所指結(jié)點(diǎn)的操作為_＿_(dá)＿_(dá)_＿_(dá)＿_(dá)__