02142數(shù)據(jù)結(jié)構(gòu)導(dǎo)論201710月份真題和答案解析

2016年10月高等教育自學(xué)考試全國(guó)統(tǒng)一命題考試數(shù)據(jù)結(jié)構(gòu)與論試卷（課程代碼02142）本試卷共4頁(yè)，滿分100分，考試時(shí)間150分鐘?？忌痤}注意事項(xiàng)：本卷所有試題必須在答題卡上作答。答在試卷上無(wú)效,第一部分為選擇題。必須對(duì)應(yīng)試卷上的題號(hào)使用第二部分為非選擇題。必須注明大、小題號(hào)，使用合理安排答題空間。超出答題區(qū)域無(wú)效。試卷空白處和背面均可作草稿紙。2B鉛筆將“答題卡”的相應(yīng)代碼涂黑。0.5本卷所有試題必須在答題卡上作答。答在試卷上無(wú)效,第一部分為選擇題。必須對(duì)應(yīng)試卷上的題號(hào)使用第二部分為非選擇題。必須注明大、小題號(hào)，使用合理安排答題空間。超出答題區(qū)域無(wú)效。試卷空白處和背面均可作草稿紙。2B鉛筆將“答題卡”的相應(yīng)代碼涂黑。0.5毫米黑色字跡簽字筆作答。第一部分選擇題（共30分）一、單項(xiàng)選擇題（本大題共10小題，每小題2分，共30分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其選出并將“答題卡”的相應(yīng)代碼涂黑。錯(cuò)涂、多涂或未涂均無(wú)分。.已知問(wèn)題規(guī)模為n,則下列程序片段的時(shí)間復(fù)雜度是Ci=1J=0fwhiie(i+j<<=n>(i((i>j)j++telsei++i)A*OS)B.OClogan)QO(n>D.O(2n).若用計(jì)算機(jī)來(lái)模擬銀行客戶排隊(duì)等待辦理業(yè)務(wù)的情形，則所應(yīng)該采用的數(shù)據(jù)結(jié)構(gòu)是A.棧B.隊(duì)列C.樹D.圖.若線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，則適用的查找方法為A.隨機(jī)查找B.散列查找C.二分查找D.順序查找.已知指針P和q分別指向某單鏈表中第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)，假設(shè)指針s指向另一個(gè)單鏈表中某個(gè)結(jié)點(diǎn),則在S所指結(jié)點(diǎn)之后插入上述單鏈表應(yīng)執(zhí)行的語(yǔ)句為.sfnext=P;qfnext=sfnext;.sfnext2q;尸next2sfnext;d.sfnext=P;qfnext=sfnext;.sfnext2q;尸next2sfnext;d依次入棧，則不能得到的出棧序列是C.p-next=sfnext;s-next=q;D.棧的運(yùn)算特點(diǎn)是先進(jìn)后出，元素a、b、c、A.abedBA.abedB.dcbaCcabdD.bcda.在實(shí)現(xiàn)隊(duì)列的鏈表結(jié)構(gòu)中，其時(shí)間復(fù)雜度最優(yōu)的是A.僅設(shè)置頭指針的單循環(huán)鏈表BC.僅設(shè)置頭指針的雙向鏈表.在實(shí)現(xiàn)隊(duì)列的鏈表結(jié)構(gòu)中，其時(shí)間復(fù)雜度最優(yōu)的是A.僅設(shè)置頭指針的單循環(huán)鏈表BC.僅設(shè)置頭指針的雙向鏈表D.僅設(shè)置尾指針的單循環(huán)鏈表.僅設(shè)置尾指針的雙向鏈表.任意一棵二叉樹的前序和后序遍歷的結(jié)果序列中，各葉子結(jié)點(diǎn)之間的相對(duì)次序關(guān)系是A.不一定相同B.都相同C.都不相同D.若某棵樹的存儲(chǔ)結(jié)構(gòu)采用雙親表示法，如題8圖所示，則該樹的高度是.互為逆序A.2B.3A.2B.3C.無(wú)向圖的鄰接矩陣一一定是A.對(duì)稱矩陣B.對(duì)角矩陣C.根據(jù)連通圖的深度優(yōu)先搜索的基本思想，如題.4D,5.稀疏矩陣D.三角矩陣10圖所示的連通圖的一個(gè)深度優(yōu)先搜索的結(jié)果序列是題10圖A.123456B,123465C.126345D,16254311.用順序查找方法對(duì)含有n個(gè)數(shù)據(jù)元素的順序表按從后向前查找次序進(jìn)行查找，現(xiàn)假設(shè)查找其中每個(gè)數(shù)據(jù)元素的概率不相等，那么A.該順序表按查找概率由低到高的順序來(lái)存儲(chǔ)數(shù)據(jù)元素，其ASL最小B.該順序表按查找概率由高到低的順序來(lái)存儲(chǔ)數(shù)據(jù)元素，其ASL最小ASL的大小與數(shù)據(jù)元素在該順序表中的位置次序無(wú)關(guān)ASL的大小與查找每個(gè)數(shù)據(jù)元素的概率無(wú)關(guān).已知散列表的存儲(chǔ)空間為T[0,…，16],散列函數(shù)為H(k)----kmod17,用二次探測(cè)法解決沖突。散列表中已插入下列關(guān)鍵字：TE53--39、T[6]一57和T[73—7,則下一個(gè)關(guān)鍵字值23在該散列表中插入的位置是A.T[23B.T[4]C.T[8]D.T[10].對(duì)關(guān)鍵字序列｛eSC,tab,ah,con,brk,del｝進(jìn)行排序時(shí)，若關(guān)鍵字序列的變化情況如下；①esc,tab,ah,con,brk,del②ah,tab,eSCcon,brk,del③alt,brk,esc,con,tab,del④alt,brk,con,esc,tab,delah,brk,con,del,tab,esc⑥ah,brk,con,del,esc,tab。則所用的排序方法是A.a1biB.antA.a1biB.ant>baD./＜耕第二部分非選A.直接插入排序B.直接選擇排序C.堆排序D.冒泡排序14.滿足最小堆定義的是A.{21,25,55,23,51,63}B.{21,51,55,63,25,23}C.{21,63,55,25,51,23}D.{21,51,23,63,55,25}15.設(shè)有兩個(gè)長(zhǎng)度分別為mn的降序有序序列{asa2,…，am）、{b1，b2,…，bn),米用一路歸并方法將它們合并成長(zhǎng)度為m+12的降序有序序列，則歸并過(guò)程中元素比較次數(shù)最少的條件一定是BCCCCCCCCCCCC擇題（共70分）二、填空題（本大題共13小題，每小題2分，共26分）.從宏觀上看，數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)反映了數(shù)據(jù)組織的三個(gè)層次。.在表長(zhǎng)為n的順序表中插入或刪除一個(gè)元素，則需移動(dòng)元素的具體個(gè)數(shù)與表長(zhǎng)和元素位置有關(guān)。.非空的單循環(huán)鏈表的頭指針為head,尾指針為rear,則rear一〉next=head。.設(shè)以數(shù)組Q[m]存放循環(huán)隊(duì)列的元素，變量rear和queuelen分別表示循環(huán)隊(duì)列中隊(duì)尾元素的下標(biāo)位置和元素的個(gè)數(shù)。則計(jì)算該隊(duì)列中隊(duì)頭元素下標(biāo)位置的公式是_（rear-queuelen+m）%m。.二維數(shù)組A[8][9]按行優(yōu)先順序存儲(chǔ)，若數(shù)組元素A[2][3]的存儲(chǔ)地址為l087,A[4][7]的存儲(chǔ)地址為ll53,則每個(gè)數(shù)組元素占用的存儲(chǔ)單元的個(gè)數(shù)是―3。.設(shè)一個(gè)完全二叉樹共含有196個(gè)結(jié)點(diǎn)，則該完全二叉樹中含有葉結(jié)點(diǎn)的個(gè)數(shù)是—98。.假設(shè)高度為h二叉樹中只有度為2和度為0這兩種類型的結(jié)點(diǎn)，則該類二叉樹中結(jié)點(diǎn)個(gè)數(shù)至多為2h-1、至少為_(kāi)_3。.若以數(shù)據(jù)集｛34,5,12,23,8,18｝為葉結(jié)點(diǎn)的權(quán)值構(gòu)造一棵哈夫曼（HUffman）樹，那么該Huffman樹的帶權(quán)路徑長(zhǎng)度WPL_238.設(shè)有散列函數(shù)H（k）和鍵值k'ZCkj了匕3若=則這種現(xiàn)象稱為“沖突”，且稱鍵值匕和k2互為同義詞。.一個(gè)圖的最小生成樹是滿足一定條件的生成樹，即一個(gè)圖的最小生成樹是指該圖的所有生成樹中權(quán)值之和最小的生成樹。.對(duì)長(zhǎng)度為n的有序順序表進(jìn)行二分查找，則查找表中的任意一個(gè)元素時(shí)，無(wú)論查找成功與失敗，最多與表中—longN_+1個(gè)元素進(jìn)行比較。.排序方法中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素按序進(jìn)行比較，將其插入已排序序列的正確位置上的方法稱為直接插入排序。.一般情況下，時(shí)闖復(fù)雜度是O（nl0g2n）且其空間復(fù)雜度最優(yōu)的排序方法是一堆排序—。三、應(yīng)用題（本大題共5小題，每小題6分，共30分）.借助于隊(duì)列能夠?qū)⒑衝個(gè)數(shù)據(jù)元素的棧逆置，比如棧S中的元素為｛a,b,C｝逆置后變成｛C,b,a｝。試簡(jiǎn)述你的解決方案。.為便于表示二叉樹的某些基本運(yùn)算，則深度為k.的二叉樹的順序存儲(chǔ)結(jié)構(gòu)中的數(shù)組的大小為多少？畫出如題30圖所示的二叉樹的順序存儲(chǔ)結(jié)構(gòu)示意圖，并說(shuō)明對(duì)一般形態(tài)的二叉樹不太適合使用順序存儲(chǔ)結(jié)構(gòu)來(lái)表示的原因。題30圖.先序遍歷、中序遍歷一個(gè)森林分別等同于先序、中序遍歷該森林所對(duì)應(yīng)的二叉樹?，F(xiàn)已知一個(gè)森林的先序序列和中序序列分別為ABCDEFIGJK口BDCAIFJGHE試畫出該森林。.設(shè)有一組關(guān)鍵字值序列｛e,b,d,f,a,g,C｝現(xiàn)要求：（1）根據(jù)二叉排序樹的創(chuàng)建方法構(gòu)造出相應(yīng)的二叉排序^^關(guān)鍵字值的大小按字母表順序計(jì)）；（2）計(jì)算等概率情況下在該二叉排序樹上查找成功的平均查找長(zhǎng)度ASL.若采用二路歸并排序方法對(duì)關(guān)鍵字序列｛25,9,78,6,65,15,58,18,45,20｝進(jìn)行升序排序，寫出其每趟排序結(jié)束后的關(guān)鍵字序列。四、算法設(shè)計(jì)題（本大題共2小題，每小題7分，共l4分）.某電商有關(guān)手機(jī)的庫(kù)存信息，按其價(jià)格從低到高存儲(chǔ)在一個(gè)帶有頭結(jié)點(diǎn)的單循環(huán)鏈表中，鏈表中的結(jié)點(diǎn)由品牌型號(hào)（nametype）、價(jià)格（price）、數(shù)量（quantity）和指針（next）四個(gè)域組成?，F(xiàn)新到in臺(tái)、價(jià)格為c、品牌型號(hào)為x的新款手機(jī)需入庫(kù)，寫出相應(yīng)的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)該要求的算法。?19typedefstructnode{^20char*nametypej江1intprice；^22intquantity;structnode*neKt;s24}Node,*LinkedList;2526voida<*d(LinkedLi5thead,charint%floatc){27Nodenew-(Node?}malloc(sizeof(Node));28new->rrametype-xj29new->price=c;30new->quantity=mj31new->nex?t■MULL;32Nodeq=head;34Nodep-head->next;while(p!=headp->price<c){q=p->next;p=p->next;new->nex7t=p;39q->next=newj40return;41142}35.寫出向存儲(chǔ)結(jié)構(gòu)為鄰接矩陣的無(wú)向圖G中插入一條邊(x,y)的算法。算法的頭函數(shù)為:voidAddEdgetoGraph(Graph*G,VertexTypeX,VertexTypey>,無(wú)向圖G的存儲(chǔ)結(jié)構(gòu)為：ItdefineMaxVertexnumtypedefcharVertexType；typedefintEdge7'ype；xypedefstructgraph{int口，H〃圖的實(shí)際頂點(diǎn)數(shù)和邊數(shù)EdgeTypeedge[MaxVertcx]CMaxVertcx]；〃鄰接矩陣VertexTypevertexfMaxVertex]；〃頂點(diǎn)表}Graph；??????■■■....^..■奧鴛膏篇;雷前；,?，2C16年1。月高等教盲同學(xué)猾試全國(guó)”「俞胭號(hào)貳

數(shù)據(jù)結(jié)構(gòu)萼論試題答案及評(píng)分參考（課程代礴0.2142）一維嚷讖提艱：本大題共15，4滿小噩?2機(jī)澳時(shí)分■LC工E：!.I）4.A5,C乩總7,B3.C9,AL值6■■n.aizdbhi.dm1&散據(jù)項(xiàng)1^.head根上212Hli24.同艾利空i.」阻1&散據(jù)項(xiàng)1^.head根上212Hli24.同艾利空i.」阻"+i溫堆排殍此汲元素所她的位堂9.（丁匕注「一qite'.ifQta/：5rv.21^82居25.權(quán)德之癇最小27.直接橘人排序三、應(yīng)甫題（本大遨共S小趟，每小題6分，共卻分）弱.先拼找中元.器傕次出校并人狄列,瓜分）然感使該隊(duì)列元素俵次出趴列靜進(jìn)入段.，（3分）a.■■■,"4-一、'.產(chǎn)C、.-11：■■.?■■,■■,",30,數(shù)組的大小為介一L（2分＞聯(lián)壽存儲(chǔ)綺椅示意圖=［石］可在J*|黑2分）原網(wǎng):會(huì)特成存鑄空間的浪費(fèi)現(xiàn)壕；.（2分-■31.先根據(jù)蛤定的兩個(gè)序列梅選出相應(yīng)?的二叉將.然后?再將其轉(zhuǎn)成森林:迄i!J構(gòu)造出的二叉推FF樹翎等性四.等替士<--CA52X2十&X3fIX必內(nèi)片謔"&數(shù)據(jù)結(jié)構(gòu)導(dǎo)淪流圈等黑及評(píng)分參考第1頁(yè)￡娃2頁(yè)>?理時(shí)，..,.?..?,.11...?：....，o.."".??.；.,.?,?.!?：*,???--..二^....-.：......：*..：?.?*.?\：:「、：11一二，/.：.哪…趟一?貉36m燈口.距那哪…趟一?貉36m燈口.距那7?盼俗吸引：.蒲二感[&￥257S3DS汾3&5猶2。權(quán).:???????￡―：：,..^-,.第三?。?川.”821船鼾凰if2G.⑸弟西趟工6，15IS絹裾.落都國(guó)￡?：'?.旗.算法設(shè)計(jì)麴（不大題為r小遨t瞪小篆7分，共Y分:

,....??<1分:(1和<2/.對(duì)存砥結(jié)梅為：：?：,X；.."yperkf^trui：t'門分》f?分）◎分）門分）

。分31mciymeiypc；fjdntprice：mlquantifyjstructnode>nxntr：；Nade,*LinkedLJ5ti實(shí)我算法為：?......；］；：.;.,..；.二：一?.，：.：：?...?.,???一：曜謠二'：.?：：voidUnk^dLsstheadTchar米x；si門；，f2%lB「：：/二黎囁鼻潭{nevp,???,?(No<ie±)oc(齒ztiof(Norte));xk：w->Ti2imetypenew—；>pncw-CH'ittw>quantHy,:;?tTi->ncxt=NuIl1日=聯(lián)期中=卜出血—>口。匕〃版或指鐘q指向。所招結(jié)點(diǎn)的前騾?.?.....while：5！"'head&S7-p^>price<c>-'q-q>nfAt；p-p—>next^>^'....4"new—>■next~p；q->nextnew；returni)32.voiclA4dEd作：：nGr罡ph(Gtaphh：G+V