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

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