南京理工大學(xué)紫金學(xué)院《數(shù)據(jù)結(jié)構(gòu)》試題（卷）-高清數(shù)位重置版

...wd......wd......wd...一、選擇題1.樹最適合用來表示〔〕。A.有序數(shù)據(jù)B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)2.一個堆是一棵〔〕二叉樹。A.普通B.排序C.滿D.完全3.設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m，假設(shè)用二叉鏈表作為存儲構(gòu)造，則該哈夫曼樹中共有〔〕個空指針域。A.2m-1B.2mC.2m+1D.4m4.線性構(gòu)造的順序存儲構(gòu)造是一種〔〕的存儲構(gòu)造。A.隨機(jī)存取B.順序存取C.索引存取D.散列存取5.一下是平衡二叉樹的是〔〕。A.B.C.D.6.對圖進(jìn)展廣度優(yōu)先遍歷時，通常采用〔〕來實(shí)現(xiàn)算法。A.棧B.隊(duì)列C.樹D.圖7.有一個有序表為{8，15，20，22，32，41，45，62，75，77，82，85，97}，當(dāng)二分查找值為22的數(shù)據(jù)時要進(jìn)展〔〕次對比。A.2B.3C.4D.58.設(shè)單鏈表中結(jié)點(diǎn)的構(gòu)造為(data,next)。指針n所指結(jié)點(diǎn)不是尾結(jié)點(diǎn)，假設(shè)在指針p所指結(jié)點(diǎn)之后插入結(jié)點(diǎn)s，則應(yīng)執(zhí)行以下哪一個操作A.s->next=p;p->next=s; B.s->next=p->next;p->next=s;C.s->next=p->next;p=s; D.p->next=s;s->next=p;9.由權(quán)值分別為11.8.6.2.5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為〔〕。A.24B.71C.48D.5310.無向圖G=(V,E)，其中V={a，b，c，d，e，f}，E={(a,b),(a,c),(a,e),(b,e),(c,f),(f,d),(e,d)}。對該圖進(jìn)展深度優(yōu)先遍歷，下面不能得到的序列是〔〕。A.acfdeb B.aebdfc C.aedfcb D.abecdf11.設(shè)有廣義表D(a,b,D)，其長度為〔〕，深度為〔〕。A.∞ B.3 C.2 D.512.線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用〔〕存儲方式最節(jié)省運(yùn)算時間。A.單鏈表B.僅有頭指針的單循環(huán)鏈表C.雙鏈表D.僅有頭指針的單循環(huán)鏈表13.在有n個結(jié)點(diǎn)的二叉鏈表中，值為非空的鏈域的個數(shù)為〔〕。A.n-1 B.2n-1 C.n+1 D.2n+114.稀疏矩陣一般的壓縮存儲方法有兩種，即〔〕。A.二維數(shù)組和三維數(shù)組B.三元組與散列C.三元組與十字鏈表D.散列和十字鏈表15.以下不是堆的序列是〔〕。A.100,85,98,77,80,60,82,40,20,10,66B.100,98,85,82,80,77,66,60,40,20,10C.10,20,40,60,66,77,80,82,85,98,100D.100,85,40,77,80,60,66,98,82,10,2016.一個棧的入棧序列是a,b,c,d,e，則棧的不可能輸出序列是〔〕A.edcba B.decba C.dcead D.abcde二、填空題1.下面程序段的時間復(fù)雜度是____________。 i=1; While(i<=n) i=i*5;2.在一個單鏈表中，要刪除某一個結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的________結(jié)點(diǎn)。3.在一個長度為n的順序表中，在第1個元素(1<=i<=n+1)之前插入一個新元素時須向后移動____________個元素。4.有一個10階對稱矩陣A，采用壓縮存儲方式〔以行為主存儲，且LOC(A[0][0])=1，則A[8][5]的地址是______。5.設(shè)在一棵二叉樹中，度為0的結(jié)點(diǎn)個數(shù)為8，度為2的結(jié)點(diǎn)個數(shù)為______。6.設(shè)二叉樹結(jié)點(diǎn)的先根序列為ABEDCFGH，中根序列為EDBAFCHG，則二叉樹中葉子結(jié)點(diǎn)是____________。7.求最小生成樹算法有Prim算法和Kruskal算法兩種，________算法適合稠密圖，________算法適合稀疏圖。8.數(shù)據(jù)表中有10000個元素，如果僅要求求出其中最大的10個元素，則采用____________是算法最節(jié)省時間。9.循環(huán)隊(duì)列中隊(duì)滿條件為：_____________________________。三、綜合題1.畫出廣義表LS=((),(e),(a,(b,c,d)))的頭尾鏈表存儲構(gòu)造。2.一棵二叉樹的先序序列與中序序列分別為：ABCDEFGHI和BCAEDGHFI〔1〕給出該二叉樹的后序遍歷序列?！?〕畫出該二叉樹的帶頭結(jié)點(diǎn)的中序線索二叉樹。〔3〕將該二叉樹轉(zhuǎn)換成森林。3.設(shè)有無向圖G，要求使用Prim算法構(gòu)造以頂點(diǎn)C為起點(diǎn)的最小生成樹，同時，寫出構(gòu)造最小生成樹的每一步過程〔無需注明權(quán)值〕。DDCAB155566423EF6第3題圖V5V4V1V0V2V3第4題圖67489103204.根據(jù)以以以下圖所示的AOE網(wǎng)，請答復(fù)以下問題：〔1〕求這個工程最早可能在什么時間完畢；〔2〕求每個活動的最早開場時間和最遲開場時間；〔3〕確定哪些活動是關(guān)鍵活動?；顒?lt;v0,v1><v0,v2><v1,v3><v2,v3><v2,v5><v3,v4><v3,v5><v4,v5>最早發(fā)生時間最遲發(fā)生時間5.輸入一個正整數(shù)序列{23,32,16,14,42,71,57,28,55,19,12,50}，〔1〕構(gòu)造一棵二叉排序樹〔只需最后結(jié)果圖〕。〔2〕畫出構(gòu)造的一棵平衡二叉樹〔只需最后結(jié)果圖〕。〔3〕HASH表表長為12，HASH函數(shù)為H(key)=key%11，試用線性探測再散列解決沖突的方法構(gòu)造哈希表。012345678910116.設(shè)待排序的關(guān)鍵字序列為{27,46,5,18,16,51,32,26},分別使用以下排序方法進(jìn)展排序，寫出題目所給定趟數(shù)的結(jié)果。〔1〕第三趟直接插入排序的結(jié)果?！?〕第一趟希爾排序的結(jié)果〔增量為3〕?！?〕第二趟歸并排序?！?〕第一趟快速排序。四、算法設(shè)計(jì)題有一個帶