數(shù)據(jù)結(jié)構(gòu)期末試卷(武漢理工大學(xué))

1、一、選擇題(答案不唯一可多選，26分，每空2分)1下列各項(xiàng)中屬于邏輯結(jié)構(gòu)的有。A.哈希表B.有序表C.單鏈表D.順序表2.由3個(gè)結(jié)點(diǎn)組成的二叉樹(shù)的深度可能是。A.1B.2C.3D.43將一個(gè)a100100的三對(duì)角矩陣以行主序存入一維數(shù)組B298中，元素a6564在B數(shù)組中的位置k等于。A.198B.197C.196D.195一棵滿二叉樹(shù)同時(shí)又是一棵。A.完全二叉樹(shù)B.二叉排序樹(shù)C.正則二叉樹(shù)D.平衡二叉樹(shù)長(zhǎng)度為n的順序表，在任何位置上插入或刪除一個(gè)元素的概率相等，插入一個(gè)元素時(shí)平均移動(dòng)個(gè)元素,刪除一個(gè)元素時(shí)平均移動(dòng)個(gè)元素。A.(n+1)/2B.n/2C.(n-1)/2D.(n-2)/2用s表示

2、入棧操作，*表示出棧操作，棧的初態(tài)、終態(tài)均為空，入棧和出棧的操作序列可表示成僅為由s和*組成的序列。下面的序列中合法的操作序列有。A.s*ss*s*B.sss*s*C.s*s*ss*D.sss*s*s*是特殊的線性表。A.隊(duì)列B.哈希表C.棧D.判定表表長(zhǎng)為25的哈希表，用除留余數(shù)法公式H(key)=key%p或H(key)=keymodp，則p應(yīng)取為宜。A.23B.24C.25D.26任一個(gè)有向圖的拓?fù)湫蛄小.可能不存在B.有一個(gè)C.一定有多個(gè)D.有一個(gè)可多個(gè)在下列的排序方法中，方法可能出現(xiàn)這種情況：在最后一趟開(kāi)始之前，所有的元素都不在其最終應(yīng)在的正確位置上。A快速排序B.冒泡排序C.堆排

3、序D.插入排序若以4,5,6,7,8作為權(quán)值構(gòu)造Huffmen樹(shù)，則該樹(shù)的帶權(quán)路徑長(zhǎng)度為。A.67B.68C.69D.70設(shè)head(L)、tail()分別為取廣義表表頭和表尾的操作，則從廣義表L=(x,y,z),a,(u,v,w)中取出原子u的運(yùn)算為。A.head(tail(tail(head(L)B.tail(head(head(tail(L)C.head(tail(head(taill(L)D.head(head(tail(tail(L)二、填空題(共32分，每空2分)TOC o 1-5 h z13.在單鏈表中設(shè)置頭結(jié)點(diǎn)和作用是。線索二叉樹(shù)的左線索指向其，右線索指向其。樹(shù)在計(jì)算機(jī)內(nèi)的鏈?zhǔn)?/p>

4、存存儲(chǔ)表示方法有、和?，F(xiàn)象稱為沖突。17用(A,B)的形式表示邊，對(duì)圖1的無(wú)向圖，從項(xiàng)點(diǎn)A開(kāi)始求最小生成樹(shù)，用Prim算法產(chǎn)生的邊依次是，用Kruskal算法產(chǎn)生的邊依次是。個(gè)元素。20個(gè)元素。20直接插入排序、堆排序算法的時(shí)間復(fù)雜度分別是21樹(shù)根的層次是1，則深度為8的完全二叉樹(shù)至少有個(gè)結(jié)點(diǎn)，擁有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的最大層次數(shù)是。對(duì)n個(gè)記錄進(jìn)行2-路歸并排序，一共需要進(jìn)行趟歸并。三簡(jiǎn)答題(47分)(6分)有5個(gè)元素，其入棧次序?yàn)锳,B,C,D,E,在各種可能的出棧序列中，第一個(gè)出棧元素是C且第二個(gè)出棧元素是D的出棧序列有哪幾個(gè)？(12分)一棵樹(shù)的邊的集合為(I,M),(I,N),(E,

5、I),(B,E),(B,D),(C,B),(G,J),(G,K),(A,G),(A,F),(H,L),(A,H),(C,A)。(1)畫出這棵樹(shù)。哪個(gè)是根結(jié)點(diǎn)？哪些是葉子？樹(shù)的深度是多少？將此樹(shù)轉(zhuǎn)化為相應(yīng)的二叉樹(shù)。將轉(zhuǎn)化所得的二叉樹(shù)進(jìn)行后序穿線，建立后序線索樹(shù)。(7分)用十字鏈表存儲(chǔ)稀疏矩陣的非零元，畫出存放非零元的結(jié)點(diǎn)的結(jié)構(gòu)圖，并說(shuō)明結(jié)點(diǎn)中各個(gè)域中分別存放什么內(nèi)容？(12分)對(duì)n個(gè)結(jié)點(diǎn)的有向圖，采用鄰接矩陣和鄰接表表示時(shí)，如何判斷下列問(wèn)題(1)圖中有多少條邊？任意兩個(gè)頂點(diǎn)i和j是否有邊相連？任意一個(gè)頂點(diǎn)的度是多少？(10分)依次輸入序列(62,68,30,61,25,14,53,47,90,84)中的元素，生成一棵二叉排序樹(shù)。四.算法設(shè)計(jì)(45分，每小題15分)要求：用C語(yǔ)言、類C語(yǔ)言或類Pascal語(yǔ)言編寫算法；應(yīng)對(duì)算法中使用的數(shù)據(jù)類型給出必要的說(shuō)明和注釋。用帶頭結(jié)點(diǎn)的循環(huán)鏈表作為隊(duì)列的存儲(chǔ)表示，不設(shè)頭指針而只設(shè)一個(gè)尾指針rear指向隊(duì)尾結(jié)點(diǎn)。試寫了該鏈?zhǔn)疥?duì)列的出隊(duì)算法。