2021年10月自考數(shù)據(jù)結(jié)構(gòu)(02331)試題及答案解析

1、2021年10月高等教育自學(xué)考試全國(guó)統(tǒng)一命題考試數(shù)據(jù)結(jié)構(gòu)試卷(課程代碼02331)本試卷共8頁(yè)?？偡种?00分。考試時(shí)間150分鐘?？忌痤}須知：1.本卷所有試題必須在答題卡上作答。答在試卷上無(wú)效，試卷空白處和反面均可作草稿紙2 第一局部為選擇題。必須對(duì)應(yīng)試卷上的題號(hào)使用2B鉛筆將“答題卡的相應(yīng)代碼涂黑。3第二局部為非選擇題。必須注明大、小題號(hào)，使用0. 5毫米黑色字跡簽字筆作答。4合理安排答題空間超出答題區(qū)域無(wú)效。第一局部選擇題一、單項(xiàng)選擇題(本大題共15小題，每題2分，共30分)在每題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其選出并將“答題卡 的相應(yīng)代碼涂黑。未涂、錯(cuò)涂或多涂均無(wú)分

2、。1 以下選項(xiàng)中，不屬于線性結(jié)構(gòu)的是A .網(wǎng) B .棧 C .隊(duì)列 D .線性表2長(zhǎng)度為n的順序表，刪除位置i上的元素(0 < i wn 1)，需要移動(dòng)的元素個(gè)數(shù)為A . ni B . n i I C . i D . i+13 .棧采用不同的存儲(chǔ)方式時(shí)，以下關(guān)于出棧過程的表達(dá)中，正確的選項(xiàng)是A .順序棧需要判定?？?，鏈棧也需要判定B .順序棧需要判定?？眨湕２恍枰卸– .順序棧不需要判定?？?，而鏈棧需要判定D .順序棧不需要判定棧空，鏈棧也不需要判定4. 假設(shè)一個(gè)棧以數(shù)組 V0 . . n-1存儲(chǔ)，初始棧頂指針 top為n,那么x入棧的正確操作是A . top=top+1 ; Vt

3、op=x B . Vtop=x ; top=top+1C . top=top 一 1; Vmp=x D . Vtop=x ; top=top l5. 在二維數(shù)組a910中：每個(gè)數(shù)組元素占用3個(gè)存儲(chǔ)空間，從首地址SA開始按行優(yōu)先連續(xù)存放，那么元素 a85的起始地址是A . SA+141 B . SA+144 C . SA+222 D . SA+2556. 廣義表 A=(x, (y) , (a) , A)的深度是A . 2 B . 3 C . 4 D. g7. 一棵左子樹為空的二叉樹在前序線索化后，其空指針域個(gè)數(shù)為A . 0B. 1 C . 2 D.不確定&以下關(guān)于哈夫曼樹的表達(dá)中，錯(cuò)誤的

4、選項(xiàng)是A .用n個(gè)結(jié)點(diǎn)構(gòu)造的哈夫曼樹是唯一的B .哈夫曼樹中只有度為 0或度為2的結(jié)點(diǎn)C .樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)可能是兄弟結(jié)點(diǎn)D .同一結(jié)點(diǎn)集構(gòu)造的二叉樹中，哈夫曼樹的WPL最小9 . 6個(gè)頂點(diǎn)的強(qiáng)連通圖中，含有的邊數(shù)至少是A . 4 B . 5 C . 6 D . 710 .對(duì)題l0圖進(jìn)行深度優(yōu)先搜索遍歷，以下選項(xiàng)中，正確的遍歷序列是A. V3 V4 Y, Vj v2v5 v；力 v4D. v5 巧 ¥a F v3題10圖11.以下選項(xiàng)中，能構(gòu)戒題10圖中一條路徑的是A, VL 巧 V* V, V3B % va Vj v3 Y#c 勺旳 »1 vi v<12有向圖

5、采用鄰接矩陣存儲(chǔ)，某一行中非零元素的個(gè)數(shù)等于A .對(duì)應(yīng)頂點(diǎn)v的度B .對(duì)應(yīng)頂點(diǎn)v的出度C .對(duì)應(yīng)頂點(diǎn)v的入度D .依附于對(duì)應(yīng)頂點(diǎn) v的邊數(shù)13以下選項(xiàng)中，符合堆定義的是A .102 ,24,55,60,89,93B .24 ,89,55,60,93,102C .102 ,93,55,60,89,24D .102 ,60。89,93,55,2414.關(guān)鍵字序列為66 , 82, 25, 51, 98, 108，利用快速排序方法，以第一個(gè)元素為 基準(zhǔn)得到的一趟排序結(jié)果為A.25 ,51,66,82, 98, 108B.25 ,51,66,98, 82, 108C.51 ,25,66,108, 98

6、, 82D.51 ,25,66,82, 98, 10815.以下選項(xiàng)中,其平均查找性能與基于二叉排序樹的查找相當(dāng)?shù)氖茿 .二分查找B .順序查找C .分塊查找 D .索引順序查找第二局部非選擇題二、填空題(本大題共10小題，每題2分，共20分) 請(qǐng)?jiān)诖痤}卡上作答。16線性表(a1, a2，an)中，除外，每個(gè)元素都有唯一的直接前趨。17. 指針P指向單鏈表中某個(gè)結(jié)點(diǎn)，在P所指結(jié)點(diǎn)后插入指針s所指的結(jié)點(diǎn)，正確的操作序歹y是。18. 設(shè)Push,、Pop分別表示人棧和出棧操作，x=10, y=20, z=30。依次進(jìn)行以下操作：Push(y) 、Push(z)、Push(z)、X=Pop()、Y=

7、Pop() , x,y 的值分別是 。19. 廣義表 L=(a , (b, e, (e , f, g, h) , head(L)=。20. 設(shè)樹T的度為3,其中度為1、2和3的結(jié)點(diǎn)個(gè)數(shù)分別為 3、2和1,那么T中葉子結(jié)點(diǎn)的 個(gè)數(shù)為。21 .由一棵二叉樹的后序遍歷序列和 遍歷序列可以唯一確定該二叉樹。22. 在有n個(gè)頂點(diǎn)的無(wú)向圖中，任一頂點(diǎn)的度不大于 。23. 借助于一個(gè)棧來(lái)實(shí)現(xiàn)的圖的遍歷算法是 。24. 假設(shè)有向圖中存在拓?fù)渑判蛐蛄校敲丛搱D一定不存在 。25. 關(guān)鍵字序列為66 , 82, 25, 51, 98, 108，趟二路歸并排序的結(jié)果為三、簡(jiǎn)答題(本大題共4小題，每題5分。共20分)

8、請(qǐng)?jiān)诖痤}卡上作答。26n階對(duì)稱矩陣A的元素為a,j (0 < i , j <n 一 1)，采用“按行優(yōu)先將下三角局部 的元素(含主對(duì)角線)保存在一維數(shù)組sa中，且約定元素ao,o保存在sa0 中,元素ai,j ( <i , j w n-1)保存在sak中，請(qǐng)給出由下標(biāo)i , j計(jì)算下標(biāo)k的計(jì)算公式。27. 己知二又樹T如題27圖所示。題27圖請(qǐng)問答以下問題：(1) 畫出該二叉樹對(duì)應(yīng)的森林。(2) 寫出對(duì)森林進(jìn)行前序遍歷的遍歷序列i28. 題28圖所示為一棵含 2個(gè)關(guān)鍵字的3階B樹T?，F(xiàn)將關(guān)鍵字序列40 , 60, 70, 20, 10 依次插入到T中，畫出每插入一個(gè)關(guān)鍵字后得

9、到的樹型。30 50；I R Fgg&J 二 I 一-題2塔圖29. 給定無(wú)向帶權(quán)連通圖G如題29圖所示，從頂點(diǎn)V0開始，使用普里姆(Prim)算法，求G的最小生成樹 T。請(qǐng)答復(fù)以下問題。(1) 畫出最小生成樹T。(2) 計(jì)算T中各邊權(quán)值之和。5分，共20分)四、算法閱讀題(本大題共4小題，每題 請(qǐng)?jiān)诖痤}卡上作答。30. 請(qǐng)寫出以下程序段的輸出結(jié)果。define ListSize 100int data ListSize ； int length； SeqUst；void £30 (SeqList * list)I intijk;for( i = 0 ； i <- li

10、st «> length -* 2 ； i + ) j-i + l；while( j <- list -> length - 1) if( list -> datai = List -> datafj) for( k = j < list -> length - 1 ； k 豐十) list -> data k = list -> dataF k + 1 ；list -> length ；ielseJ+；void main() SeqList li<= | 0,3t7,3,3,3,4,03,7| ,10 jint i

11、；f30(&list)；printf(tT Jen = % dn" list* length)； for( i =0 ；! < list length ； i + ) printf( % d, n , list. data訂)；printf (11 nrt ) j運(yùn)行結(jié)果*31. 己知存儲(chǔ)稀疏矩陣三元組表的類型定義如下：#define MAX LOOtypedef struct Int ij;非零元索的行號(hào)、列號(hào)(下標(biāo)欣v；非零元累值| TriTupleNode ；typed巳f(wàn) struct ITriTupleNode MAX; "存舖三元組的數(shù)組:nt/矩

12、陣的行數(shù)、列數(shù)和非零元素個(gè)數(shù)iTSMatri稀疏矩陣類型碉數(shù)創(chuàng)的功能是將厲斯表云的矩陣轉(zhuǎn)豎后保存柱"斗fihE空白處填麹適當(dāng)內(nèi)容. 使其完成揩足功int Bl(T5Matrixfi,T5Matri* b) "返回值訂 表示岀錯(cuò)山表示正輪I /兒和 b分別是薙陣M.T的三元組表戸為郴竦矩陣M的轉(zhuǎn)世int p,q,cohb i>m = a. n ； h is ti = jn； b > I = a, t;if(b->t<0)return【；皿|q = 0;(off rol = 0 ； cvln+n； 4-*-cnl)fpHiO； p<()t +p)i

13、f( (2)eoDlb -> 血ta町 i b(J)tb->dateq.j =(4) ;b -> JaUi. q = A - datu； p 叫IIreturn 0；I,32. 二叉樹的二叉鏈表類型定義如下：typwirlflf atnict node |rhrtr rtatfl；SiTurt tier已 梓(child h + rchild| BinTNoJe -tvpcdef BinITVode * BinTree ；函數(shù)CnpyBin的功能是完成二叉樹敢的復(fù)制.程序如下：BiuTree CopyBin(BinTree Bt)函數(shù)返回值為描向復(fù)制后的二叉樹報(bào)的指針i Bi

14、nTiee p ；(11 ；else ip = (BinTNodc * )malloc(3izeof( BinTNodc)；p ->data = Bidata；p -> Lchild = _ ( 2)；p *> rchild -(3)；Ireftim p；為完成指定功能，請(qǐng)?jiān)诳瞻滋幪顚戇m當(dāng)容，使其功能完整。33函數(shù)f33的參數(shù)t指向題33圖所示的二叉排序樹的根，閱讀程序，答復(fù)以下問題。題刃圖type def intlet struct ntid KeyType key * node 染 ichild + irhiM ；35TMc, *BSTree；BSTree /33(BST

15、itc tTKeyType K)BSTme p；wiiile(t!=NULL)I if(t -> kry = K)I printf嚴(yán)査找J®功3return t；IP - hif (i key >K) L = 1 -> khild；七 1st i = t -> ichijd jIprint廣背找不成功;1 = ( BSTrpe) naJluc(sizeof( RSTKtxk )；t->HiildsNULL； t->ichid=NlJLL;if (p -> key>K) p ">Ichild t； i h陽(yáng) p ->

16、 rchild = t； return NULLj(1) 假設(shè)連續(xù)3次調(diào)用函數(shù)f33，參數(shù)K的值依次取10、25、10,寫出每次調(diào)用后函數(shù)的輸 出結(jié)果；(2) 說明函數(shù)f33的功能。五、算法設(shè)計(jì)題(本大題共I小題。共10分) 請(qǐng)?jiān)诖痤}卡上作答。34.順序表 SeqList定義如下：typedef structKeyType key ;In foType otheri nf0;RecType :typedef RecType SeqListMAXSIZE+1 ;編寫函數(shù)，用冒泡排序法將n個(gè)元素的待排序列R按關(guān)鍵字降序排序。函數(shù)原型為：int f34(SeqList R , int n)。2021

17、年10月高等教育自學(xué)考試全國(guó)統(tǒng)一命電考試數(shù)據(jù)結(jié)構(gòu)試題答案及評(píng)分參考課程代碼02331，-單項(xiàng)選捧題集太軀其訂小晅，每小麺2令，共10I A?33- A«+ C5. D0 D7. C5, K氏 C10. BI】.B憶H!3 C14. D15. A門超館科包過QQ16581612It空SE姦大JS共15理.密小題2分* *20 m16.別17, g®iext=iKAnexr nexW;13, 30,30】蟲A抄52L申序21H-123-闌蠟書黑犢索誰(shuí)圧24.冋聘(st 環(huán)25*悄 S2.25.5L9S. IDS2解笞甌 外大國(guó)共沖小礫 創(chuàng)囲5乩 技拔分26.設(shè)無(wú)累j 2宴訂&#

18、163;釘、在數(shù)俎sa申的存福住廈為k.假設(shè)i >= ja碣林m啟矩陣申.iS 1 - <i41y24j t假設(shè)i < j.剰秫在上壬角疑陣屮，SWk-jO+iy2+l*貯+盯,.班、二+丿當(dāng)總J估分'斗進(jìn)1鮎留神蠟屣結(jié)梅楚贖幷進(jìn)履評(píng)金命鷺鵡1頁(yè)曲3柬27. Uj対應(yīng)的需林如卜糾師示.C7J狐禪的帀序網(wǎng)陌序列為.BDEGCFH2*. <1>得到前厳小生辰拚T如不脯示=3拎邊載擔(dān)之和mto.世*算遷閱強(qiáng)題甘傾箕4小粧.野小越丨廿'共如分3d.輸出黯黑：ImvM< 1 紗Of 3,7,4,毎玫1分共4對(duì)救細(xì)魴切試趣番奠忑評(píng)少參粵翹？罰【冥3蟲3LM©分idainfp.(15>> iclatiip! j“分?aUAHUnj.i<r#>扭 ；L> rsTum NULLifc liC2) CopyBin(DbMchi1d)d分?C3) Copy氐疏 B卜Arched)心分、33. CD査找不龍功門分賣找成功“分査視威功c分d功償*在一養(yǎng)并療擁上査找冶定的關(guān)磁孑一假設(shè)査找戍功.柬尿示“晝