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

數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)二一、單項選擇題１．從n個數(shù)中選取最大元素（）。A．基本操作是數(shù)據(jù)元素間的互換B.算法的時間復(fù)雜度是Ｏ(n）Ｃ．算法的時間復(fù)雜度是Ｏ(n2)D．需要進(jìn)行(n+1)次數(shù)據(jù)元素間的比較2．線性表采用鏈?zhǔn)酱鎯r，其地址（）。A.一定是不連續(xù)的B.必須是連續(xù)的C.部分地址必須是連續(xù)的D.可以連續(xù)也可以不連續(xù)３.設(shè)hｅad為非空的單向循環(huán)鏈表頭指針，p指向鏈表的尾結(jié)點，則滿足邏輯表達(dá)式()的值為真。Ａ．p->next＝NUＬLB．ｐ－>neｘt==heａdC．p->next＝heａdD.p==NＵLL4.帶頭結(jié)點的單向鏈表的頭指針為ｈｅａd,該鏈表為空的鑒定條件是（）的值為真。A．head=＝NULＬＢ.ｈead－＞next==headC.heａd==hｅaｄ->nexｔD.hｅａd－>nｅxt==NULL５.設(shè)順序存儲的線性表長度為n,要刪除第i個元素，按課本的算法,當(dāng)ｉ=（)時,移動元素的次數(shù)為3A.3B.n／２C．n-３Ｄ6．設(shè)順序存儲的線性表長度為n,對于插入操作，設(shè)插入位置是等概率的，則插入一個元素平均移動元素的次數(shù)為()。A．nB．n/2C．ｎ-1Ｄ．ｎ－7.一個棧的進(jìn)棧序列是a，ｂ，c，ｄ，則棧的不也許的出棧序列是（）。A.dcｂaB.bcａｄC.ｃbaｄD.aｄbｃ8.一個棧的進(jìn)棧序列是5，6,7，8，則棧的不也許的出棧序列是（)(進(jìn)出棧操作可以交替進(jìn)行)Ａ.7,6,８，５B.5,8，６，7C．7，６,5,8D.８，７,６，59.設(shè)有一個帶頭結(jié)點的鏈隊列，隊列中每個結(jié)點由一個數(shù)據(jù)域daｔa和指針域next組成,ｆｒoｎt和reaｒ分別為鏈隊列的頭指針和尾指針,要執(zhí)行出隊操作,用ｘ保存出隊元素的值,p為指向結(jié)點類型的指針,可執(zhí)行如下操作:p=fｒont->next;x=p-＞daｔa;然后指行（）。Ａ．front=p->next;Ｂ．front-＞ｎext=p;C.froｎt=p;D.fｒont－>next＝p->ｎeｘｔ;１0.棧和隊列的相同點是(）。A.都是后進(jìn)先出B．都是后進(jìn)后出Ｃ.邏輯結(jié)構(gòu)與線性表不同D.邏輯結(jié)構(gòu)與線性表相同，都是操作規(guī)則受到限制的線性表11.在C語言中，存儲字符串“ＡＢCD”需要占用(）字節(jié)。A.4Ｂ．2C．5Ｄ1２.在C語言中,運用數(shù)組a存放字符串“Helｌｏ”,以下語句中對的的是（)。A.ｃｈara［10]＝“Hｅlｌｏ”;Ｂ.chａrａ［1０];a=“Hello”;C．chara［１0］=‘Hello’;D．ｃhara[1０］＝｛‘Ｈ’,’e’,’l’,’l’,’o’};13.設(shè)有一個10階的對稱矩陣Ａ,采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中。(矩陣A的第一個元素為a１,1,數(shù)組ｂ的下標(biāo)從1開始),則矩陣元素a5,3相應(yīng)一維數(shù)組ｂ的數(shù)組元素是（)。Ａ.b[18］B．b[8］C．b[13]D.ｂ[10]14.設(shè)有一個1５階的對稱矩陣A,采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組ｂ中。(矩陣A的第一個元素為a1,１，數(shù)組b的下標(biāo)從1開始）,則數(shù)組元素b[１3］相應(yīng)A的矩陣元素是（)。A.a5,3Ｂ．a(chǎn)６,4C.ａ7,2D15.深度為5的完全二叉樹共有20個結(jié)點,則第5層上有(）個結(jié)點(根所在結(jié)點為第一層)。A.3B．8Ｃ１6．一棵完全二叉樹共有３0個結(jié)點,則該樹一共有（）層(根結(jié)點所在層為第一層)。A．6Ｂ．4Ｃ.3D17．已知一個圖的所有頂點的度數(shù)之和為m,且m是以下4中情況之一,則m只也許是(）。A．9B.7C．１5D18．以下說法對的的是（）。A.連通圖Ｇ的生成樹中不一定包含Ｇ的所有頂點B.連通圖Ｇ的生成樹中一定要包含Ｇ的所有邊C.連通圖Ｇ一定存在生成樹D.連通圖G的生成樹一定是唯一的19.線性表只要以（)方式存儲就能進(jìn)行折半查找。A.鏈接B.順序C．關(guān)鍵字有序的順序D．二叉樹2０．對二叉排序樹進(jìn)行（)遍歷,遍歷所得到的序列是有序序列。A.按層次B.前序C.中序D．后序２1．對n個元素進(jìn)行冒泡排序若某趟冒泡中只進(jìn)行了（）次元素間的互換，則表白序列已經(jīng)排好序。A.1B.２Ｃ.0Ｄ22.以下排序算法中，在一趟排序過程中，除了其它相關(guān)操作外,只進(jìn)行一次元素間的互換的算法是（)。A.冒泡B.直接選擇Ｃ.直接插入D．折半插入2３.在對一組元素（64，48，106,33，25，82，70，５５,93)進(jìn)行直接插入排序時，當(dāng)進(jìn)行到要把第7個元素70插入到已經(jīng)排好序的子表時,為找到插入位置，需進(jìn)行（)次元素間的比較(指由小到大排序）。Ａ.6B．２C.3D24.對長度為n的線性表進(jìn)行順序查找，在等概率情況下，平均查找長度為（)。A.ｎＢ．(ｎ+1）/２C．2nD．n-１SHAＰE\*MERGEFＯRＭAT25.如圖,若從頂點a出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷，則也許得到的頂點序列為(）。abecdfgabecdfgＢ.acｆedgｂC．ａbecｄgfD．ａbecｆdg２6．如圖若從頂點ａ出發(fā)按深度優(yōu)先搜索法進(jìn)行遍歷，則也許得到的頂點序列為（）。ababecdfgＢ．ａｅｄｃbｇfＣ．a(chǎn)ｃfebｄgD．ａｅｃｂdｇf27.一棵哈夫曼樹有１0個非葉子結(jié)點（非終端結(jié)點),該樹總共有()個結(jié)點。A．２１Ｂ.２0C．228．一棵哈夫曼樹有12個葉子結(jié)點（終端結(jié)點)，該樹總共有()個結(jié)點。A．21B．２2Ｃ.2３Ｄ29.隊列的插入操作在（）進(jìn)行。A．隊頭B．隊尾C．隊頭或隊尾D.在任意指定位置３０．隊列的刪除操作在（）進(jìn)行。A.隊尾B．隊頭C．隊頭或隊尾D.在任意指定位置二、填空題１．通?？梢园涯吵鞘兄懈鞴徽军c間的線路圖抽象成_＿＿_(dá)＿_(dá)__結(jié)構(gòu)。２.結(jié)構(gòu)中的元素之間存在多對多的關(guān)系稱為＿_(dá)__＿＿_(dá)_結(jié)構(gòu)。3.要在一個單向鏈表中刪除p所指向的結(jié)點，已知q指向ｐ所指結(jié)點的直接前驅(qū)結(jié)點,若鏈表中結(jié)點的指針域為nｅxt，則可執(zhí)行____＿_(dá)＿＿。4．設(shè)有一個單向循環(huán)鏈表，結(jié)點的指針域為neｘｔ，頭指針為head,指針p指向表中某結(jié)點,若邏輯表達(dá)式＿＿_(dá)_＿_(dá)__的結(jié)果為真，則p所指結(jié)點為尾結(jié)點。5.設(shè)有一個鏈棧,棧頂指針為ｈs，現(xiàn)有一個ｓ所指向的結(jié)點要入棧,則可執(zhí)行操作＿_(dá)______和hｓ=s;6．設(shè)有一個鏈棧,棧頂指針為hs,現(xiàn)有一個s所指向的結(jié)點要入棧,則可執(zhí)行操作s->ｎext＝ｈs;_____＿_(dá)_。7.在一個不帶頭結(jié)點的非空鏈隊中,f和r分別為隊頭和隊尾指針，隊結(jié)點的數(shù)據(jù)域為ｄaｔａ，指針域為next，若要進(jìn)行出隊操作，并用變量x存放出隊元素的數(shù)據(jù)值，則相關(guān)操作為___＿_(dá)__＿;__＿_(dá)_＿_(dá)_。8.在一個鏈隊中，f和r分別為隊頭和隊尾指針，隊結(jié)點的指針域為next，s指向一個要入隊的結(jié)點,則入隊操作為_＿_(dá)_＿＿_(dá)_;___＿_(dá)_＿_(dá);9．順序存儲字符串“ＡBCD”需要占用__＿＿_(dá)＿_(dá)_個字節(jié)。1０．循環(huán)隊列的最大存儲空間為MaxSize=6,采用少用一個元素空間以有效地判斷棧空或棧滿,若隊頭指針ｆｒont=４，當(dāng)隊尾指針reaｒ=___＿_(dá)___時隊滿,隊列中共有_＿＿_(dá)____個元素。11．一棵二叉樹葉結(jié)點(終端結(jié)點)數(shù)為5，單分支結(jié)點數(shù)為2，該樹共有__＿_(dá)__個結(jié)點12.程序段char*s=”ａＢcD”;n=０;wｈile（＊s!=’\0’{ｉf(*s>=’ａ’&＆*s<＝’ｚ’)n++；s＋＋;}執(zhí)行后ｎ＝_____＿_(dá)＿１3．設(shè)一棵完全二叉樹,其最高層上最右邊的葉結(jié)點的編號為奇數(shù),該葉節(jié)點的雙親結(jié)點的編號為10,該完全二叉樹一共有＿＿＿_(dá)＿_(dá)__個結(jié)點。14．一棵二叉樹中順序編號為5的結(jié)點(樹中各結(jié)點的編號與等深度的完全二叉中相應(yīng)位置上結(jié)點的編號相同），若它存在左孩子，則左孩子的編號為＿_(dá)_＿＿＿_(dá)_。15.結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為__＿_(dá)____結(jié)構(gòu)。16．根據(jù)搜索方法的不同，圖的遍歷有_____＿_(dá)_兩種方法。17.結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系稱為＿_(dá)____＿_(dá)結(jié)構(gòu)。18．結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為___＿_(dá)＿_(dá)＿結(jié)構(gòu)。1９.如圖所示的二叉樹，其后序遍歷序列為。eefgibachd20．一棵有n個葉結(jié)點的二叉樹,其每一個非葉結(jié)點的度數(shù)都為2，則該樹共有_____＿_(dá)個結(jié)點。21．圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是_____＿的。(回答對的或不對的)22.串的兩種最基本的存儲方式分別是___＿_(dá)_＿和＿_(dá)__＿_(dá)__。23.按某關(guān)鍵字對記錄序列排序，若關(guān)鍵字的記錄在排序前和排序后仍保持它們的前后關(guān)系,則排序算法是穩(wěn)定的,否則是不穩(wěn)定的。２4.按某關(guān)鍵字對記錄序列排序，若關(guān)鍵字的記錄在排序前和排序后仍保持它們的前后關(guān)系,則排序算法是穩(wěn)定的,否則是不穩(wěn)定的。三、綜合題1．(1)一組記錄的關(guān)鍵字序列為{45，40，65,43，35,95}寫出運用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一趟劃分的結(jié)果(規(guī)定給出一趟劃分中每次掃描和互換的結(jié)果)(2)同樣對序列｛45，4０，65，43,３５,9５}運用直接插入排序，寫出逐次插入過程（從第一個元素一直到第六個元素）。2.設(shè)有一個不帶頭結(jié)點的單向鏈表,頭指針為head，結(jié)點類型為NODE，每個結(jié)點包含一個數(shù)據(jù)域ｄata和一個指針域next，該鏈表有兩個結(jié)點，p指向第二個結(jié)點（尾結(jié)點),按以下規(guī)定寫出相應(yīng)語句（不規(guī)定完整程序,(1)、（2）、（3)、（4）是一個連續(xù)的過程)。（１）新開辟一個結(jié)點,使指針s指向該結(jié)點,結(jié)點的數(shù)據(jù)成員datａ賦值為１（2)把該結(jié)點插入鏈表的尾部，釋放指針ｓ的指向(3）刪除鏈表的第一個結(jié)點(4）已知p1指向另一個新結(jié)點,把它插入到ｐ所指結(jié)點和尾結(jié)點之間３．(１）運用篩選過程把序列{4２,8２,67,１0２，1６,32，５7,52}建成堆(小根堆),畫出相應(yīng)的完全二叉樹(不規(guī)定中間過程）（2)寫出對上述堆相應(yīng)的完全二叉樹進(jìn)行中序遍歷得到的序列4．（1)設(shè)有序列{10,12，15，19,22，25，10０,130，１5０,２00}畫出對上述序列進(jìn)行折半查找的鑒定樹（以序列中的元素作為樹的結(jié)點)(2）為了成功查找到１00需要進(jìn)行多少次元素間的比較？為了查找9，通過多少次元素間的比較可知道查找失敗?５.(1）設(shè)有一個整數(shù)序列｛50,3８,16,82，１10，13,６４},依次取出序列中的數(shù)，構(gòu)造一棵二叉排序樹(2)運用上述二叉排序樹，為了查找１10，經(jīng)多少次元素間的比較能成功查到，為了查找１5,經(jīng)多少次元素間的比較可知道查找失?。?(１）設(shè)有查找表｛5,１４,2,6,18,７,4,16,3}，依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹。（2）說明如何由序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果，對上述二叉排序給出中序遍歷的結(jié)果。四、程序填空題１．以下函數(shù)為鏈棧的進(jìn)棧操作，x是要進(jìn)棧的結(jié)點的數(shù)據(jù)域,top為棧頂指針sｔructnode｛EleｍTypｅｄata;strucｔｎodｅ*ｎeｘt;｝;structnｏｄe*ｔop;vｏidＰuｓh(ＥlｅmTypex){structｎode*ｐ；ｐ=（sｔruｃtnｏｄe*)malｌoc（＿_(dá)_(１)_____);p－>ｄａt(yī)ａ=x;__＿(２)___＿_(dá);_____（３)_＿_(dá)；}2．設(shè)線性表為(6，1０,16，4）,以下程序用說明結(jié)構(gòu)變量的方法建立單向鏈表，并輸出鏈表中各結(jié)點中的數(shù)據(jù)。#definｅNULL0ｖoｉdmain()｛NＯDEa,b，ｃ，d,*hｅａｄ,*p;ａ．ｄata=６;b．data=10;c.dａt(yī)ａ=1６；d.ｄata＝4；/*d是尾結(jié)點*/hｅad=（1);a.nｅxt=&b;b.ｎext=&c;ｃ.next＝&d;(2）;／*以上結(jié)束建表過程*/p=ｈeａd;/＊p為工作指針,準(zhǔn)備輸出鏈表＊/do｛printｆ(“%d\ｎ”,（3））;(4);｝while(（5））;｝3．以下函數(shù)在head為頭指針的具有頭結(jié)點的單向鏈表中刪除第i個結(jié)點,stｒuctnode｛iｎtdata；strucｔnｏde＊next;};typeｄｅfｓｔrucｔnｏdeNOＤＥintｄｅｌete(NODＥ*heａd，ｉｎti)｛NＯDE＊p,*q;inｔj；q=head;j＝0;while((q！=NULL)&＆(＿＿_(dá)(1）＿＿＿_(dá)_)){_＿_(dá)（2)＿＿_(dá)__;j++；}iｆ（q=＝NＵＬL)retｕrn(0);ｐ=__＿（3)__＿_(dá)＿;___(4）__＿＿＿=p－>next;freｅ（＿＿_(dá)(5)_＿_(dá)__);ｒeturn(1);}4.以下程序是中序遍歷二叉樹的遞歸算法的程序，完畢程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和rigｈt，數(shù)據(jù)域datａ為字符型,BT指向根結(jié)點）。ｖｏｉdInｏrder(strｕctBＴｒｅeＮode＊BT）{if（ＢT!=NUＬL){(1）;(2）;(3);}｝答案一、單項選擇題（每小題2分,共30分）１．B２．D3．Ｂ４．Ｄ5．C6．Ｂ7.D8．B9.D１0．D11．C12．Ａ１3．C14．A15.C16.D1７．D1８.C19.C20．C21.C22.B23．C２4．B25．Ｃ26．A２７.Ａ28．C2９.B30.B二、填空題（每題2分，共２４分)1．圖狀2．圖狀3．ｑ-＞neｘｔ＝p－>nｅxt；４．p->next==hｅaｄ;5．s－>nｅxt=hｓ；6.hs=s;７.x=ｆ->data;f＝f-＞nｅxt；8.ｒ->nｅxt＝s;ｒ＝s;９．51０．3;５11.1112.213．21１４.1015、樹形16、深度優(yōu)先；廣度優(yōu)先17．線性18.圖狀（網(wǎng)狀）1９．gｄbeiｈfｃa２0．２n-１21．對的22.順序存儲