PAGEPAGE12008～2009學(xué)年第二學(xué)期《GIS算法基礎(chǔ)》試卷A答案填空題（每空1分，共20分）1.正確性確定性清晰性2.算法的時間復(fù)雜度算法的空間復(fù)雜度3.邊界內(nèi)部外部4.右側(cè)左側(cè)P0、P1、P2三點(diǎn)共線5.按屬性信息的要求來查詢定位空間位置根據(jù)對象的空間位置查詢有關(guān)的屬性信息6.解析變換法數(shù)值變化法數(shù)值解析變換法7.8.右手螺旋凸凹二、單項(xiàng)選擇題（每題2分，共20分）1.B2.D3.B4.A5.A6.C7.C8.B9.A10.D三、判斷對錯題（正確的打“√”，錯誤的打“×”）（每題2分，共20分）1.√2.×3.√4.√5.√6.×7.×8.×9.√10.×四、簡答題（每題5分，共20分）1.請說明線性結(jié)構(gòu)和樹型結(jié)構(gòu)的異同點(diǎn)。線性結(jié)構(gòu)中第一個數(shù)據(jù)元素(無前驅(qū))；最后一個數(shù)據(jù)元素(無后繼)；其它數(shù)據(jù)元素(一個前驅(qū)、一個后繼)。樹型結(jié)構(gòu)中根結(jié)點(diǎn)(無前驅(qū))；多個葉子結(jié)點(diǎn)(無后繼)；其它數(shù)據(jù)元素(一個前驅(qū)、多個后繼)。2.柵格數(shù)據(jù)的壓縮分為無損壓縮技術(shù)和有損壓縮技術(shù)，請說明什么是無損壓縮技術(shù)，什么是有損壓縮技術(shù)。（1）無損壓縮技術(shù)是指壓縮過程中沒有任何信息損失，通過解碼操作可以完全恢復(fù)原來的信息；（2）有損壓縮技術(shù)是指為了提高壓縮效率，最大限度地壓縮數(shù)據(jù)，在壓縮過程中損失一部分相對不太重要的信息，解碼時這部分難以恢復(fù)。3.請說明鏈?zhǔn)骄幋a的優(yōu)點(diǎn)和缺點(diǎn)。優(yōu)點(diǎn)：鏈?zhǔn)竭叴a可以有效地壓縮柵格數(shù)據(jù)，而且對于估算面積、長度、轉(zhuǎn)折方向的凹凸度等運(yùn)算十分方便，比較適合于存儲圖形數(shù)據(jù)。缺點(diǎn)：對邊界進(jìn)行合并和插入等修改編輯工作比較困難，對局部的修改將改變整體結(jié)構(gòu)，效率較低，而且由于鏈碼以每個區(qū)域?yàn)閱挝淮鎯吔?，相鄰區(qū)域的邊界將被重復(fù)存儲而產(chǎn)生冗余。4.請寫出數(shù)據(jù)挖掘的步驟。答：（1）數(shù)據(jù)清理（消除噪音或不一致數(shù)據(jù)，補(bǔ)缺）；（2）數(shù)據(jù)集成（多種數(shù)據(jù)源可以組合在一起）；（3）數(shù)據(jù)選擇（從數(shù)據(jù)庫中提取相關(guān)的數(shù)據(jù)）；（4）數(shù)據(jù)變換（變換成適合挖掘的形式）；（5）數(shù)據(jù)挖掘（使用智能方法提取數(shù)據(jù)模式）；（6）模式評估（識別提供知識的真正有趣模式）；（7）知識表示（可視化和知識表示技術(shù)）。五、分析題（10分）請把下圖按照前序遍歷、中序遍歷和后序遍歷的方法寫出結(jié)果。前序遍歷：-+a*b-cd/ef中序遍歷：a+b*c-d-e/f后序遍歷：abcd-*+ef/-六．計(jì)算題（10分）1.某縣要在其所轄的8個鄉(xiāng)鎮(zhèn)之一修建一個消防站，為8個鄉(xiāng)鎮(zhèn)服務(wù)，要求消防站至最遠(yuǎn)鄉(xiāng)鎮(zhèn)的距離達(dá)到最小。假設(shè)該8個鄉(xiāng)鎮(zhèn)之間的交通網(wǎng)絡(luò)被抽象為下圖所示的無向賦權(quán)連通圖，權(quán)值為鄉(xiāng)鎮(zhèn)之間的距離。下面求解消防站應(yīng)設(shè)在哪個鄉(xiāng)鎮(zhèn)，即哪個頂點(diǎn)？解：首先，用Dijkstra算法計(jì)算出每一個頂點(diǎn)vi至其它各頂點(diǎn)v的最短路徑長度dij(i,j=1,2,…,6)，寫出距離矩陣：其次，求距離矩陣中每行的最大值，即各個頂點(diǎn)的最大服務(wù)距離，得 e(v1)=14,e(v2)=15,e(v3)=20,e(v4)=12,e(v5)=15,e(v6)=17,e(v7)=12,e(