南京理工大學紫金學院《數據結構》試題（卷）-高清數位重置版

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