2023年數(shù)據(jù)結(jié)構(gòu)與算法期末試卷B

2023—2023學年第二學期閩江學院期末試卷考試課程:《數(shù)據(jù)結(jié)構(gòu)與算法》試卷類別：Ａ卷□B卷t考試形式:閉卷t開卷□合用專業(yè)年級：1３級金融服務(wù)、１3級軟件服務(wù)裝訂線裝訂線題號一二三總分得分一、單項選擇題60%(請將答案填入答題卡相應(yīng)位置,30題,每題2分，共60分)得分1、計算機算法必須具有輸入、輸出和(）等5個特性。A.可行性、可移植性和可擴充性B.可行性、擬定性和有窮性C.擬定性、有窮性和穩(wěn)定性D．易讀性、穩(wěn)定性和安全性2、設(shè)語句ｘ++的時間是單位時間，則以下語句的時間復(fù)雜度為（）。foｒ(i=1；i<=n;ｉ++)?x+＋;A．O(1）B．O(n2)C.O(n)D.O(n3)3、以下哪種邏輯結(jié)構(gòu)關(guān)系最松散（) A．集合Ｂ.線性Ｃ．樹Ｄ．圖４、以下哪種線性表的存儲地址一定是連續(xù)的()A．有序表B.順序表C.單鏈表Ｄ．雙鏈表5、帶頭指針的循環(huán)鏈表在表尾插入，時間復(fù)雜性()Ａ.O(1）B.O(n）C.O(n2)D.O(n3)6、設(shè)結(jié)點結(jié)構(gòu)為（dａt(yī)a,next）,L是帶頭結(jié)點和尾指針的單循環(huán)鏈表,L->ｌaｓt是表尾結(jié)點指針。若想刪除鏈表的首元結(jié)點，則應(yīng)執(zhí)行下列（)操作？A.s=L-＞lａsｔ；L-＞laｓｔ＝L－＞lａst->nｅxt;fｒee（s)；B.Ｌ->laｓt=Ｌ->last->neｘｔ;frｅｅ(L->lａsｔ);C.L->lasｔ=L-＞last-＞next－>ｎexｔ;fｒｅe(L->last);Ｄ．s＝L->last-＞neｘt->nｅxｔ;Ｌ->laｓt->nｅxt-＞ｎｅxt=s-＞next;fｒｅｅ(s);7、帶頭結(jié)點的單鏈表L為空的鑒定條件是（）A.L->nｅxｔ=＝NＵＬＬ；B.L!=NULL;C．Ｌ->nｅxt==L;Ｄ.Ｌ==NULＬ;8、設(shè)結(jié)點結(jié)構(gòu)為(prior,dａt(yī)a,neｘt),Ｌ是不帶頭結(jié)點循環(huán)雙鏈表,L是表頭結(jié)點指針。若想刪除循環(huán)雙鏈表中ｐ結(jié)點的后繼結(jié)點(假設(shè)存在)，則應(yīng)執(zhí)行下列（）操作?A．p-＞ｎext=ｐ->nｅxｔ->neｘt；B．p->nexｔ=p->nｅxt-＞next;p->next->ｐｒiｏr＝p；C．ｐ->ｎext=p->next->nｅxｔ;p->next-＞nexｔ->prｉｏｒ=p;D．p－＞nｅxt->prｉor=ｐ;p->neｘｔ＝p->next->next;9、若在線性表中經(jīng)常涉及插入刪除操作，則采用以下哪種表進行元素存儲比較好(）？A．有序表Ｂ.順序表C．鏈表D．棧1０、在一個長度為n的順序表中插入第i個元素(１＜=i<＝n+1）時，需向前移動（)個元素。Ａ.n－iB．ｎ-ｉ+１C．n-ｉ－1D．i1１、假定對元素序列(7,3,５,9,1，12)進行堆排序，并且采用小根堆,則由初始數(shù)據(jù)構(gòu)成的初始堆為（)。Ａ.1，3,5，７,９,１2B．1,３,5,9，7,1２Ｃ．1，5,3,７,９,12D.1,5,3,９,12,712、假定一個初始堆為(1,5,3,9,１2,7，1５,10)，則進行第一趟堆排序后得到的結(jié)果為（)。A．3,5,7,9，１2,10,15,1B.3,５,９，7,1２,10,15，1C.3，7,５，9,12,10,1５,1Ｄ.3,５，7,１２，9,10，1５,11３、在平均情況下速度最快的排序方法為()Ａ．直接選擇排序Ｂ.歸并排序C.基數(shù)排序D．快速排序1４、若一個元素序列基本有序,則選用()方法較快。A．直接插入排序B．簡樸選擇排序C．歸并排序D.快速排序1５、對1000個元素進行排序,規(guī)定既快又省空間,則以下（)算法比較好。A.直接插入排序Ｂ.堆排序C.歸并排序D.快速排序16、設(shè)元素的進棧順序為1,2,3,那么以下哪種是不也許的出棧序列。A．１２3B．132C.３1２Ｄ.312１7、棧的插入和刪除操作在(）進行。A.棧頂B．棧底C．中間D．任意位置18、隊列中元素的進出原則為()。A.先進先出Ｂ．后進先出C．大數(shù)先出Ｄ．小數(shù)先出1９、對二叉排序樹進行以下哪種遍歷會得到一個有序序列。Ａ.先序遍歷Ｂ.中序遍歷Ｃ．后序遍歷D.層序遍歷2０、由權(quán)值分別為３,８，６,2，5的葉子結(jié)點生成一棵哈夫曼樹,它的帶權(quán)途徑長度為（）。A.24???B.4８ C.72 ? Ｄ.２1、在一棵度為3的樹中，度為3的結(jié)點數(shù)為3個,度為2的結(jié)點數(shù)為２個,度為1的結(jié)點數(shù)為3個，則度為0的結(jié)點數(shù)為(）個。Ａ.8 ? Ｂ.９?? Ｃ．6 D．722、在一棵二叉樹上第3層的結(jié)點數(shù)最多為（)。A.2? ?B.4? ?C.6 Ｄ．823、用順序存儲的方法將完全二叉樹中的所有結(jié)點逐層存放在數(shù)組中R[1．.n］,結(jié)點R[ｉ]若有右孩子，其右孩子的編號為結(jié)點()。A.R[2i＋1] B.R[2ｉ］??Ｃ．R［i/2]? D.R[2i-1]24、已知圖中某條途徑上有k個頂點,則該途徑長度為()。A．k-1B．kC．k+1D.2k25、以下(）算法用于在有向網(wǎng)中求單源最短途徑。A．普里姆算法B．克魯斯卡爾算法C．迪杰斯特拉算法Ｄ.弗洛伊德算法２6、在一張有向圖中，若一個頂點的入度為k1，出度為k２，則相應(yīng)鄰接表中該標點單鏈表中的結(jié)點數(shù)為()。A．k1Ｂ.k２C．k1＋k2D．２(k1+k２)27、設(shè)有7個結(jié)點的無向圖，該圖至少應(yīng)用(）條邊能保證是一個連通圖。A．5Ｂ．6C．7D．828、1０個頂點組成的無向完全圖中，有()條弧。Ａ．45B.90C．100Ｄ.20029、對于順序存儲的有序表(5，１２,20，26,３７,42,46,５0,６4），若采用折半查找，則查找元素12的比較次數(shù)為（）。A.2 ?B.3 C.4??D.53０、假定對線性表(38,25，７4,52，４8)進行哈希存儲,采用H(k)=k%7作為哈希函數(shù)，采用開放定址法解決沖突，則在建立哈希表的過程中,將會碰到(）次存儲沖突。A．4? B．5 C.6 ?D.７二、程序完型填空題10％（請將答案填入答題卡相應(yīng)位置，1題5空,每空2分，共10分)得分已知圖的鄰接表定義如下:constMAX＿ＶERTEX＿NUＭ=20;ｔyｐｅｄeｆsｔrｕctArcNoｄｅ{?inｔadｊｖex；?ｓｔructArcＮode*ｎｅxtarc; ｉntinfｏ；／／ＩｎｆoTypｅ*iｎfｏ;}ArｃＮｏdｅ;//邊結(jié)點typedefｃharVeｒtexTｙpe;ｔｙpedefｓtructVNode{?ＶeｒteｘTypeｄaｔa； ArcNｏde*fｉrstａｒｃ；}VNode,AdｊＬist[ＭＡＸ_ＶERＴEX_NＵM];//頂點數(shù)組中的頂點結(jié)點ｔyｐeｄefstrucｔ{?AdｊＬｉstvertｉceｓ; intｖｅxnum,aｒcｎｕm;}ALGraｐh;//圖請將下列有向圖的創(chuàng)建算法補充完整：ｖｏidＣｒeateＵＤG(AＬGｒａph*Ｇ){／/假設(shè)所需變量皆已經(jīng)定義 scanf("%d,%d",＆(G->vexnum),&(G-＞aｒcnum));／/輸入圖的頂點數(shù)與弧數(shù)?/／構(gòu)造頂點數(shù)組?foｒ(i=０;i<Ｇ－>ｖeｘｎum;ｉ＋＋) {? geｔchar();/／吸取輸入的回車符??scanｆ("%c＂,＿＿_（1)＿＿_)；/／輸入圖的頂點信息??___(2)___; }//構(gòu)造邊結(jié)點?for(k=0；k<G->aｒｃnum；k+＋)?{ ｇetchar(）;//吸取回車符? ｓcaｎf("%c,％c＂,＆v1,&ｖ2);//輸入弧的兩個端點??ｉ=LocateVex(G,ｖ1);/／起點的編號??j=LoｃatｅＶex（G,v2);//終點的編號 ｐi=___(3)＿_＿； pi-＞ａdｊveｘ=__＿(4)__＿; pｉ-＞nｅxtａrc=___（5)___;? G-＞vｅrtices[i］.ｆirstaｒc=pi; }}(１)A．&(Ｇ->ｖertices[ｊ]．ｄata)Ｂ.＆(G－＞vertices[i］.datａ)C．&(Ｇ－＞vertiｃes［j］.adｊｖｅx)Ｄ.&(Ｇ->vertｉcｅs[i].adjvｅx)（2）Ａ.G-＞vexｎum++B.此處不需要添加代碼Ｃ.G-＞dａｔａ[i].firstarｃ=NULLD.Ｇ->vertｉcｅs［i].fｉrsｔarc=ＮUＬＬ(３）Ａ.ｎewＮoｄeＢ.nｅwVＮodeＣ.ｎewArcNodeＤ．newALGrａph(4)Ａ．iＢ.jC.ｖ1D.v２（5)Ａ．Ｇ-＞vｅrtｉｃeｓ［ｉ］．fiｒｓtaｒcB.Ｇ－＞vｅｒｔiceｓ[ｊ].firstarｃＣ.G－＞vｅrticｅs[i].nexｔarcD．G->vｅｒtｉces[ｊ].nｅxtarｃ三、填空題30%(請將答案填入答題卡相應(yīng)位置，除第3題第一空為4分外，其余都為2分，共30分）得分１、已知記錄(４６，7４,５3，14,26，３8,8６,65，27,３4）,請給出歸并排序的第一趟排序結(jié)果(以第一個元素作為基準）：___＿__2、從一棵二叉排序樹中查找一個元素時,若元素的值大于根結(jié)點的值,則繼續(xù)向＿_____查找。3、假設(shè)一棵二叉樹的后序序列為ＤCEＧBFHKJIA,中序序列為DCBGEAHFＩJK,請畫出該二叉樹______(４分),并寫出該二叉樹的先序遍歷序列______。4、已知二叉樹的二叉鏈表表達法定義如下:ｔypｅdefcharＴElｅmＴype；typｅdｅfstructBiTnode{TEｌemＴypedata;structBiTnｏdｅ*lchｉlｄ，*rchilｄ；}BiTNｏｄe，*BiTrｅe;請將下列二叉樹的查找算法補充完整:intLocaｔｅElem（BiTreeT，TElｅmTypee)//e為要查找的元素{?intfｌｏｏr;//用于記錄層數(shù)?if（T)/／若樹不空 {ｉf(___(1）＿__)//若在根處找到? ?return1;? fｌoｏｒ=Locａt(yī)eElem(_＿＿(2)___）;//在左子樹查找 ?iｆ(fｌｏｏr>0)//若在左子樹中找到? ?retuｒn__＿(3）___;??ｆloor=LocａｔeEleｍ(___(4)___);? if(floor>0) ?retｕrn___(５)___； } rｅtuｒn0;／/若樹為空，則直接返回0,說明找不到}5、已知圖的鄰接表定義如第二題所示，下列程序段為圖的深度優(yōu)先搜索算法，請將算法中缺失的語句補充完整：voidDFS（ALＧrａphG，iｎtv)//從編