2015年秋西南大學(xué)網(wǎng)教-(0012)《數(shù)據(jù)結(jié)構(gòu)》大作業(yè)A-標(biāo)準(zhǔn)答案

西南大學(xué)網(wǎng)絡(luò)與繼續(xù)教育學(xué)院課程考試試題卷類別：網(wǎng)教專業(yè)：軟件工程2015年12月A卷課程名稱【編號】：數(shù)據(jù)結(jié)構(gòu)【0012】大作業(yè)滿分：100分一、大作業(yè)題目1、選擇題1）在算法分析中，主要分析的是（）A.正確性和簡單性B.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性C.空間復(fù)雜度和時(shí)間復(fù)雜度D.可用性和正確性2）在一個(gè)單鏈表中，如果刪除P結(jié)點(diǎn)所指向的后續(xù)結(jié)點(diǎn)，以下語句正確的是（）A.P=P->nextB.=p->next->nextC.p-next=p->next->nextD.p=p-next,p-next=p->next->next3）串與普通的線性表相比較，它的特殊性體現(xiàn)在（）。A.順序的存儲結(jié)構(gòu)B.鏈?zhǔn)酱鎯Y(jié)構(gòu)C.數(shù)據(jù)元素任意員D.數(shù)據(jù)元素是一個(gè)字符4）廣義表G=(a,b(c,d,(e,f)),g)的長度是（）。A.3B.4C.7D.85）廣義表運(yùn)算式HEAD(TAIL((a,b,c),(x,y,z)))的結(jié)果是：A.(x,y,z)B.(a,b,c)C.xD.a6）某二叉樹的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹中結(jié)點(diǎn)數(shù)目為（）。A.3B.2C.4D.57）表達(dá)式a*(b+c)-d的后綴表達(dá)式是（）。A.abcd+-B.abc+*d-C.abc*+d-D.-+*abcd8）按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有（）種。A.6B.4C.3D.59）由權(quán)值為3，6，7，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）。A.51B.23C.53D.7410）下面（）可以判斷出一個(gè)有向圖中是否有環(huán)（回路）。A.廣度優(yōu)先遍歷B.拓?fù)渑判駽.求最短路徑D.求關(guān)鍵路徑2、填空題1）帶有頭結(jié)點(diǎn)的雙向循環(huán)列表L為空的條件。2）棧的插入和刪除操作在3）稀疏矩陣的壓縮方式有完成。。和4）已知二維數(shù)組A[m][n]采用行序?yàn)橹鞣绞酱鎯?，每個(gè)元素占k個(gè)存儲單元，并且第一個(gè)元素的存儲地址是LOC(A[0][0])，則A[i][j]的地址是_______。5）用順序存儲的方法，將完全二叉樹中所有結(jié)點(diǎn)按層逐個(gè)從左到右的順序存放在一維數(shù)組R[1..N]中，若結(jié)點(diǎn)R[i]有右孩子，則其右孩子是6）采用鄰接表存儲的圖，其深度優(yōu)先遍歷類似于二叉樹的7）當(dāng)利用大小為N的數(shù)組存儲循環(huán)隊(duì)列時(shí)，該隊(duì)列的最大長度是。。。8）設(shè)哈希表長m=14,哈希函數(shù)H(key)=keyMOD11。表中已有4個(gè)結(jié)點(diǎn)：addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7其余地址為空，如用二次探測再散列處理沖突，則關(guān)鍵字為49的地址為。9）數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R），其中D是10）一個(gè)算法的效率分為效率和效率。3、應(yīng)用題的有限集合，R是D上的有限集合。1）編寫算法,將一個(gè)頭指針為head不帶頭結(jié)點(diǎn)的單鏈表改造為一個(gè)單向循環(huán)鏈表，并分析算法的時(shí)間復(fù)雜度。2）已知二叉樹的先序遍歷序列為ABCDEFGH，中序遍歷序列為CBEDFAGH，畫出二叉樹。然后寫出該二叉樹的后序遍歷序列。3）試用權(quán)集合{12,4,5,6,1,2}構(gòu)造哈夫曼樹，并計(jì)算哈夫曼樹的帶權(quán)路徑長度。4）已知圖G如下所示，根據(jù)Prim算法，構(gòu)造最小生成樹。（要求給出生成過程）5）設(shè)哈希表HT表長m為13，哈希函數(shù)為H(k)=kMODm，給定的關(guān)鍵值序列為{19,14,23,10,68,20,84,27,55,11}。試求出用線性探測法解決沖突時(shí)所構(gòu)造的哈希表，并求出在等概率的情況下查找成功的平均查找長度ASL。二、大作業(yè)要求大作業(yè)共需要完成22道題：第1大題必做，滿分30分；第2大題必做，滿分30分；第3大題選作2題，滿分40分。答卷提交要求：考試題提前公布，學(xué)生下載試題和答題卷后，在答題卷上答題。完成后需網(wǎng)上提交答卷。答卷于11月20日－－12月6日通過點(diǎn)擊頁面左側(cè)導(dǎo)航欄內(nèi)“我的考試”－“課程論文/大作業(yè)”提交。1、選擇題1)C2)C3)D4)A5)C6)C7)B8)D9)A10)A2、填空題1)l==l->next2)棧頂3)三元組順序表十字鏈表。4)LOC(A[0][0])+(n*i+j)*k5)R[2i+1]6)先序遍歷7)n-18)99)數(shù)據(jù)元素關(guān)系10)時(shí)間效率空間效率3、應(yīng)用題2）已知二叉樹的先序遍歷序列為ABCDEFGH，中序遍歷序列為CBEDFAGH，畫出