00.Introduction1/1單選題(1分)Whichofthefollowingisthekeyproblemthiscourseputanemphasison?(以下哪個話題是我們這門計算幾何課程中，重點關注的話題？)Thecontinuityofcurvesandsurfaces(曲線和曲面的連續(xù)性問題)Thedivisionofgeometricproblemsinalgorithmdesignandanalysis(算法中關于幾何問題的分支)Digitalimageprocessingandrecognition(數(shù)字圖像的處理與識別)答案：B1/1單選題(1分)WhichofthefollowingispreferedwhenencounteringanewComputationalGeometricproblem?(當同學們面對一個新的計算幾何問題時，我們提倡的第一步是？)Goingthroughmaterials(查閱資料)Sharpobservation(敏銳的觀察)Rigorousconsideration(縝密的思考)Doingexperiments(做實驗驗證)答案：B01.ConvexHull1/3單選題(1分)Intheimagebelow,whichofthenailsshouldbeboundtightlybytherubberbandifweextendtherubberbandtoincludeallthenailsandthenwelooseit?在下面的圖中，用橡皮筋包含所有的釘子再松手，將會形成的一段一段的橡皮筋的邊界。請問這個邊界所緊緊勒住的釘子是哪些？1,2,3,4,5,61,2,7,8,5,31,2,7,6,5,31,2,8,5,3,4答案：B2/3單選題(1分)You'regivenpaintwithcolorofA=(10%,30%)andthepaintwiththecolorofB=(30%,70%).Whichofthefollowingcolorscanwegetbyblendingthesetwokindsofpain?現(xiàn)在有一種顏色A=(10%,30%)，一種顏色B=(30%,70%)，請問下面哪種顏色是可以被上述兩種顏色給勾兌出來的？(40%,70%)(60%,20%)(40%,90%)(25%,60%)答案：D3/3單選題(1分)Nowwehave3kindsofpaint,whichareU=(10%,10%)，V=(60%,10%)，W=(10%,30%).Whichofthefollowingcolorscan'tbegeneratedbymixingthese3kindsofpaint?現(xiàn)在有三種顏色U=(10%,10%)，V=(60%,10%)，W=(10%,30%)，你能夠快速地知道下面哪個顏色是不可能由這三種顏色勾兌出來的么？(60%,30%)(20%,20%)(40%,12%)(15%,20%)答案：A1/1單選題(1分)Whichoptiondoesn'tincludeanynon-extremeedgeforthepointssetbelow?對于下圖表示的點集來說，哪個選項包含的全部都是極邊？(1,3),(1,9),(1,2),(5,10)(3,5),(5,10),(9,10),(1,9)(1,9),(9,5),(3,10),(3,5)(3,5),(1,9),(9,4),(5,10)答案：B1/4單選題(1分)IfweuseIncrementalConstructionforgeneratingconvexhull,whatistheprogressofthevaryingcountoftheconvexhullforpointsbelow?對于下圖表示的點集來說，如果我們采用增量式策略構(gòu)造凸包，并按照標號依次將新的點加入，那么凸包上的點的個數(shù)變化過程是？1->2->3->3->4->5->51->2->2->3->4->5->61->2->3->4->4->5->61->2->3->3->4->5->6答案：D2/4單選題(1分)AfterintroducingIn-Convex-PolygonTest,let'sthinkabouttheIn-PolygonTestforgeneralpolygons.Generalpolygonscanbeconcaveorconvex,sometimeswithholes.Wehaveaspecificpointinageneralpolygon.Anotherrandompointexistingoutsidethepolygoncanbeconnectedwithitusingarandomcurve.Thenyou'llfindthat在討論了凸多邊形的In-Convex-PolygonTest方法之后，讓我們來思考一下一般多邊形的In-PolygonTest問題。與凸多邊形不同，一般多邊形可能是凹的，甚至可能是帶有孔洞的。對于一般多邊形內(nèi)部區(qū)域中的一點，我們在外部隨機找一點并隨意地用一根曲線連接它們，你會發(fā)現(xiàn)Thecurvepassesthroughtheboundaryofthepolygononce(曲線經(jīng)過多邊形邊界1次)Thecurvepassesthroughtheboundaryofthepolygonforoddtimes(曲線經(jīng)過多邊形邊界奇數(shù)次)Thecurvepassesthroughtheboundaryofthepolygonforseveraltimeswithnorules(曲線經(jīng)過多邊形邊界次數(shù)沒有規(guī)律)Thecurvepassesthroughtheboundaryofthepolygonforeventimes(曲線經(jīng)過多邊形邊界偶數(shù)次)答案：B3/4單選題(1分)Okaynow.Let'sthinkaboutthespecialcasebasedonthelastproblem.Forarandomgeneralpolygon,howdoyouknowwhetherthepointisinsidethepolygon?WhatisthemethodforIn-PolygonTest?好的，在上一題的基礎之上，我們將條件從一般的情況反推到特殊的情況。對于任意的一般多邊形，判斷某一點是不是在這個多邊形內(nèi)部，也就是In-PolygonTest的辦法是？Drawarayfromthepointandcheckiftherayintersectswiththeboundaryofthepolygontwice(從該點射出一條射線，如果射線與多邊形邊界交點為2個，則為內(nèi)部)Drawarayfromthepointandcheckiftherayintersectswiththeboundaryofthepolygonforeventimes(從該點射出一條射線，如果射線與多邊形邊界交點個數(shù)為偶數(shù)，則為內(nèi)部)Drawarayfromthepointandcheckiftherayintersectswiththeboundaryofthepolygonforoddtimes(從該點射出一條射線，如果射線與多邊形邊界交點個數(shù)為奇數(shù)，則為內(nèi)部)Drawasegmentpassingthroughthepointandcheckifthesegmentintersectswiththeboundaryofthepolygonforoddtimes(經(jīng)過該點畫一條線段，如果直線與多邊形邊界交點個數(shù)為奇數(shù)，則為內(nèi)部)答案：C4/4單選題(1分)Twosupportlinesdividetheconvexhullintotwoparts,standts.Fromtheimagebelowwecanknowthat凸包外部的一點x引出的兩條支撐線xt，xs將凸包邊界分成st和ts兩部分，通過觀察我們可以知道Anysegmentconnectingxwitharandompointontswillnotintersectwithanyotherboundaryoftheconvexhull(ts上的任意一點與x相連都不會與凸包其他邊界相交)Anysegmentconnectingxwitharandompointonstwillnotintersectwithanyotherboundaryoftheconvexhull(st上的任意一點與x相連都不會與凸包其他邊界相交)Anypointontsisinvisibletox(ts上的任意一點都對于x不可見)Anypointonstisvisibletox(st上的任意一點都對于x可見)答案：A1/4單選題(1分)WhichofthefollowingiswrongaboutInsertionSortandSelectionSort?下面關于插入排序和選擇排序的一些說法，錯誤的是SelectionSortmakesexchangesinunsortedsubsequence(選擇排序每次主要在unsorted序列中做交換)InsertionSortcanguaranteethemaximumvalueoftheunsortedsubsequencelessthaneveryelementinthesortedsubsequence(插入排序中unsorted序列的最大值不會超過sorted序列)TwokindsofsortingalgorithmsruninO(n^2)(兩種排序算法的期望時間復雜度都是O(n^2))Twokindsofsortingalgorithmsreducethelengthoftheunsortedsubsequenceinordertosortthearray(兩種排序算法都是通過逐步減少unsorted序列的長度來實現(xiàn)排序)答案：B2/4單選題(1分)Astheimagebelowshows,theveryfirststepofJarvisMarchalgorithmisfindinganextremepointasthestartpoint.Ifweprojectallthepointsontheplanetoalineandmakea2Dto1Dmapping,wewillfindthat如下圖所述，JarvisMarch算法的第一步，是確定一個開始的極點。如果我們將平面上的點都投影到一條直線上，做一個二維到一維的映射的話，我們會發(fā)現(xiàn)Allextremepointswillbeprojectedtoonepointontheline(極點總是被投影到直線上的一個點)Allextremepointswillbeprojectedtoeithermaximalorminimalpointontheline(極點總是被投影到直線上的最大值或者最小值)Themaximalorminimalpointonthelineismappedwiththeextremepoints(直線上的最大值或最小值總是對應著極點)Themaximalorminimalpointonthelineismappedwiththenon-extremepoints(直線上的最大值或最小值總是對應著非極點)答案：C3/4單選題(1分)Inthelastepisode,wetalkedaboutsortingusingthecomparatorofTo-LeftTest.Forpointsintheimagebelow,what'sthecorrectorder?(Sortthesepointsbycounter-clockawiseincreasinganglewithrespecttoredpoint)上一節(jié)中所講的利用To-Left測試來作為一個比較器進行排序的方法，我們通常稱為極角排序。對于如下的點來說，極角排序的結(jié)果是？（以紅色點作為極角排序的中心，從1號點開始逆時針進行排序）1,2,4,7,5,6,31,2,7,4,5,6,31,5,4,7,2,6,31,2,4,7,5,3,6答案：A4/4單選題(1分)InordertodeepenyourknowledgeofOutput-sensitiveAlgorithms,let'sreadasnippetofsimplecode.Thisisapieceofpseudocodeaboutimplementingdivisionusingsubtraction.Thetimecomplexityofthealgorithmis為了讓你對輸出敏感算法有更深的認識，我們來看這樣一個簡單的算法。這是一個利用減法實現(xiàn)除法的算法，如下圖偽代碼所示。該算法的時間復雜度是O(N)O(D)O(R)O(Q)答案：D1/3單選題(1分)IfA≤NBforalgorithmsAandB,whichofthefollowingiscorrect?當有兩個算法A和B，其中A≤NB的時候，下列哪個說法是正確的？InputofAcanbeconvertedtoinputofBinlineartime(算法A的輸入可以在線性時間內(nèi)轉(zhuǎn)換為算法B的輸入)InputofAcanbeconvertedtooutputofBinlineartime(算法A的輸入可以在線性時間內(nèi)轉(zhuǎn)換為算法B的輸出)OutputofAcanbeconvertedtoinputofBinlineartime(算法A的輸出可以在線性時間內(nèi)轉(zhuǎn)換為算法B的輸入)OutputofAcanbeconvertedtooutputofBinlineartime(算法A的輸出可以在線性時間內(nèi)轉(zhuǎn)換為算法B的輸出)答案：A2/3單選題(1分)Whichofthefollowingiswrongaccordingtothelastepisode?上面提到的曹沖稱象作為歸約思想的類比，下列哪個說法是錯誤的？CaoChonggettheweightoftheelephantusingtheweightoftherocksbasedonreduction(利用歸約思想，曹沖利用石頭的重量去估算出大象的重量)theweightofelephant≤NTheweightofrocks(大象的重量≤N石頭的重量)ReductionrelationshipheremeanstheboatandthewaterusedinCaoChong'smethod(這里的歸約關系是指曹沖稱象時的船和水)Iftwoobjectswiththesameweighthasdifferentmarks,thenreductionrelationshipherebreaks(如果兩個物體重量相同但吃水的刻度不同，則歸約關系就被破壞了)答案：B3/3單選題(1分)Afterlearningthereductionrelationshipbetween2d-CHandSorting,whichofthefollowingiswrong?學習了排序與二維凸包算法的歸約關系以后，下列哪個說法是錯誤的？Anyarraytobesortedcanbemappedtothepointssetonthe2d-planeinlineartime(任何一個待排序的數(shù)組，都可以線性時間映射為二維平面上的點集)Anyconvexhullonthe2d-planecanbemappedtoasortedarrayinlineartime(任何一個二維平面上的凸包，都可以線性時間映射為一個有序數(shù)組)Wecansolvea2d-CHproblemforsolvingasortingproblem(為了解決排序問題，我們可以先解決一個二維凸包問題)If2d-CHalgorithmscanbeO(n)intime,SortingalgorithmcanbeO(n)intime,too(如果二維凸包算法有O(n)的時間復雜度，那么排序算法也可以通過歸約達到O(n)的時間復雜度)答案：B1/2單選題(1分)StackisanimportantdatastructureinGrahamScan.IfthereisanemptystackSandthepushingorderofthestackisA,B,C,D,E,whichofthefollowingpoppingorderisillegal?在GrahamScan算法當中，棧是作為一個很重要的數(shù)據(jù)結(jié)構(gòu)存在的?，F(xiàn)在假設有一個空棧S，元素入棧的順序是A、B、C、D、E，那么下面哪個出棧順序是不可能存在的？B、A、D、C、ED、A、E、B、CC、B、A、E、DC、B、D、A、E答案：B2/2單選題(1分)InGrahamScan,thealgorithmendswithanemptystackT.WhystackSwon'tbecomeemptybeforestackTbecomeempty?在GrahamScan算法當中，算法結(jié)束是以T棧為空作為標志的，那么為什么S棧不會先于T棧變空呢？AllelementsofstackTgointothestackS(T棧中的元素都進入了S棧)ThesizeofstackSisalwayslargerthanthesizeofstackT(S棧中元素個數(shù)總是多于T棧)ThereareonlypushingtowoardsstackSwithnopoppingfromstackS(S棧中元素只會進不會出)TwoextremepointsstayatthebottomofstackSandit'simpossibletopopthemaccordingtoTo-Lefttest(S棧底部的兩點是極邊上的點，不可能因為To-Left測試而出棧)答案：D1/1單選題(1分)IfwedoGrahamScantothefigurebelow,what'sthepoppingorderofstackS?對下圖做GrahamScan掃描，S棧的出棧順序是？4，5，3，74，3，5，74，3，7，53，4，5，7答案：A1/2單選題(1分)Astheimagebelowshows,whywon'tthepoint2bebacktracked?如下圖所示，當發(fā)生backtrack的時候，為什么最多也不會越過2號點？Becausethealgorithmmakesadeterminationbeforebacktrackingthepoint2(因為算法在backtrack到2號點之前加了判斷)Becausethepoint2isanextremepoint(因為2號點是極點)Becausethepointsbeforethepoint2can'tbepopped(因為2號點前面的點也不會被pop出去)Becausethepoint3stillstandsinfrontofthepoint2(因為2號點前面還有3號點)答案：B2/2單選題(1分)Ifwedon'tapplypresorting,whatistheresultoftheGrahamScanforthisChinesecharacterfrombottomtotop?如果不做Presorting的話，下面這個字從下到上順序進行GrahamScan，最后會產(chǎn)生的結(jié)果是？Becauseeverycaseisanright-turn,eachpointwillbeontheconvexhull(由于每個點都是右拐的情況，所以所有的點都在凸包上)NopointswillstayinstackT(沒有點在T棧上)Acorrectconvexhullwillbeconstructed(會得到一個正確的凸包)NopointswillstayinstackS(沒有點在S棧上)答案：B1/3單選題(1分)Forasimplepolyhedron,itssizeofverticesis10anditssizeoffacesis5.Howmanyedgesdoesitown?對于一個簡單多面體來說，如果其頂點個數(shù)為10，面數(shù)為5，那么它包含多少條棱呢？13142324答案：A2/3單選題(1分)HowmanystepswillthescanningtakeifdoingGrahamScantonpoints?(Nodegenerationsituation)對n個點進行GrahamScan，其中scan的過程中最多會迭代多少步？（不考慮退化情況）2n-62n-52n-72n-8答案：B3/3單選題(1分)Ifwehaveasetofpointswhicharealreadysortedaccordingtoxcoordinates,sowhat'sthetimecomplexityofthealgorithmofUpper/LowerHull?前面介紹的Upper/LowerHull算法，如果輸入的平面上的點已經(jīng)是x方向上有序的話，那么該算法執(zhí)行的時間復雜度是？O(1)O(n2)O(n)O(nlgn)答案：C1/4單選題(1分)WhatiswrongabouttheanalogybetweenconvexhullusingDACandmergesort?關于利用分治思想構(gòu)建凸包算法和歸并排序算法的類比，錯誤的是Theresultingconvexhullisinanalogywiththesortedarray(最終的凸包結(jié)果類比于排好序的數(shù)組)Thedivisionofthepointsetisinanalogywiththedivisionofthearray(將平面上的點集進行劃分類比于對數(shù)組進行劃分)Combiningtwosubconvexhullstoonesubconvexhullisinanalogywithmergingtwosortedsubsequenceintoonesortedsubsequence(將兩個子凸包合并為一個子凸包類比于兩個排好序的子序列歸并為一個排好序的子序列)Thesizeoftheextremepointsonconvexhullisinanalogywiththesizeofsortedarray(凸包上極點的個數(shù)類比于數(shù)組的大小)答案：D2/4單選題(1分)Whichofthefollowingpolygonsisnotstar-shapedpolygon?下列哪個多邊形不是星形多邊形？答案：C3/4單選題(1分)Ifwetrytocombinethesetwoconvexhulls(convexhull1-5andconvexhull6-0)together,what'sthepointsoftheresultingstar-shapedpolygon?(Thepointswillstartwithpoint1andbelistedcounterclockawise)將上述兩個凸包（凸包1-5和凸包6-9）進行合并時，最后生成的星形多邊形上的頂點列表是？（從頂點1開始，逆時針排列）1,6,3,4,5,81,6,2,3,7,4,5,8,91,6,2,3,4,7,5,8,91,6,2,3,7,4,5,9,8答案：B4/4單選題(1分)Ifwecombinethesetwoconvexhulls(convexhull1-7,convexhull8-14)together,what'stheresultingstar-shapedpolygon?(Thepointswillstartwiththepoint1andbelistedclockawise)對于下圖所示的兩個凸包（凸包1-7，凸包8-14）進行歸并的時候，最后得到的星形多邊形的頂點列表是？（以1開始，順時針排列）1,2,8,9,10,11,12,4,5,6,71,2,8,9,10,3,11,12,13,14,4,5,6,71,2,8,9,10,3,11,12,4,5,6,71,2,9,10,3,11,4,5,6,7答案：C1/3單選題(1分)Whichofthefollowingchoicesiswrongaboutthefindingtheright-mostpointoftheleftconvexhull(withasizeofn)andtheleft-mostpointoftherightconvexhull(withasizeofm)?下列選項中對于尋找左凸包（規(guī)模為n）的最右側(cè)頂點和右凸包（規(guī)模為m）的最左側(cè)頂點這個操作來說，錯誤的是？TheoperationwilltakeO(m+n)timeifwedon'trecordanyinformation(如果不記錄任何信息的話，這個操作需要消耗O(m+n)時間)ItwilltakeO(1)timetocompletetheoperationifwerecordedtheleft-mostpointofeachsubconvexhull(只要每次記錄子凸包的最左頂點就可以在O(1)時間完成這個操作)Theleft-mostpointoftheleftconvexhullwillbecometheleft-mostpointofthecombinedconvexhull(左側(cè)子凸包的最左頂點將會成為合并后凸包的最左頂點)Theright-mostpointoftherightconvexhullwillbecometheright-mostpointofthecombinedconvexhull(右側(cè)子凸包的最右頂點將會成為合并后凸包的最右頂點)答案：B2/3單選題(1分)Astheimagebelowshows,theblackdashedlineconnecttheright-mostpointoftheleftconvexhullandtheleft-mostpointoftherightconvexhull;theorangelinerepresentstheuppercommontangent;theorangedahsedlinemeansthefirststepofZig-zagging.What'sthefollowingstepsofZig-zagging?如下圖所示，黑色虛線表示左凸包右頂點與右凸包左頂點的連線；橙色實線表示左右凸包的上切線；橙色虛線表示進行Zig-zag操作的第一步。請問接下來的步驟是？(2,5),(2,4),(1,4)(1,6),(1,5),(1,4)(2,5),(1,5),(1,4)(2,5),(3,5),(3,4),(2,4),(1,4)答案：A3/3單選題(1分)Whichofthefollowingpairsoftheconvexhullswillbewrongaboutsimplyconnectingtopmostpointsandbottommostpointsinordertocalculatethecommontangents?下列哪些凸包對計算公切線時，并不是每個凸包的上下兩個頂點互相相連？答案：C02.GeometricIntersection1/1單選題(1分)Whichofthefollowingisabout'count'ofgeometricintersectionproblems?下列哪個問題包含了幾何求交問題中的“計數(shù)”問題？Stopplayersfrompassingthroughwallsingamedevelopment(游戲開發(fā)中防止角色穿過墻壁)Construct3Dmodelswithbooleanoperationofsimplepolyhedrons(利用簡單幾何體進行布爾運算創(chuàng)建復雜三維模型)Getthenumberofintersectionsofsegmentsontheplane(判斷平面上線段的交點個數(shù))Raytracingmethodforphotorealisticrendering(光線追蹤算法進行真實感渲染)答案：C1/2單選題(1分)Thereisanarrayof1001elementswhichrangefrom1to1000.Onlyoneelementisrepeatedinthearraywhiletheothersexistonlyonceinthearray.Whichofthefollowingalgorithmsisthefastest?1-1000放在含有1001個元素的正整數(shù)數(shù)組中，只有唯一的一個元素值重復，其它均只出現(xiàn)一次。下列哪種算法查找這個重復元素最快？Enumeratealltheparisinthearray,findthepairwithsamevalues(枚舉1001個元素中所有的正整數(shù)對，找到值相同的那一對)XORallthenumbersinthearraytogether,thenXORnumberfrom1to1000(現(xiàn)將數(shù)組中所有數(shù)異或在一起，再與1-1000各異或一次)Sortthearrayandthenmakesequentialsearch(將數(shù)組進行排序，再線性搜索)Sortthearrayandthenmakebinarysearch(將數(shù)組進行排序，再二分搜索)答案：B2/2單選題(1分)Ifwedivide3,5,2,7,10,13intodifferentbucketsusingthemethodmentioned,what'stheresult?使用上述的Max-Gap分桶算法對下列數(shù)3,5,2,7,10,13進行分桶的話，結(jié)果是？(2,3),(5),(7),(10),(),(13)(2,3),(5),(7),(10),(13)(2),(3,5),(7),(10),(),(13)(2,3),(5),(),(7,10),(),(13)答案：A1/1單選題(1分)Ifweapplythealgorithmmetionedtofourintervalslike(1,3),(4,10),(5,6),(0,2),whichofthefollowingisthecorrectpatternsequence?以下4個區(qū)間(1,3),(4,10),(5,6),(0,2)運用上述算法進行相交檢測時，待檢測的模式序列是？LLLRRRLRLRLRLLRRLLRRLRLRLLRRLLRR答案：D1/1單選題(1分)What'swrongaboutthereductionbetweenEUandSID?下列關于EU問題和SID問題的歸約，錯誤的是？EU≦NSIDAccordingtoreduction,wecanfoundthelowerboundofSID(通過進行歸約，我們可以找到SID問題的下界)TheinputofSIDcanbeconvertedtotheinputofSIDinlineartime(SID問題的輸入可以在線性時間內(nèi)轉(zhuǎn)化為EU問題的輸入)TheoutputofSIDcanbeconvertedtotheoutputofEUinlineartime(SID問題的輸出可以在線性時間內(nèi)轉(zhuǎn)化為EU問題的輸出)答案：C1/2多選題(2分)Whichofthefollowingcanimplementpriorityqueue?(Multiplechoice)下列哪些數(shù)據(jù)結(jié)構(gòu)通常作為優(yōu)先隊列的實現(xiàn)？（多項選擇）Hashtable(哈希表)BinaryHeap(二叉堆)FibonacciHeap(Fibonacci堆)Stack(棧)答案：BC2/2單選題(1分)Thereareseveralsegmentsontheplane.Nowweputasweeplineontheplanerandomly.IfwemarkthesetofsegmentsstayinglefttothesweeplineasL,thesetofsegmentsstayingrighttothesweeplineasRandthesetofsegmentscrossedbysweeplineasM.Whichofthefollowingconclusionsiswrong?平面上若干條線段，隨機放置一條掃描線。我們設完全在掃描線左側(cè)的線段集為L；完全在掃描線右端的線段集為R；被掃描線穿過的線段集為M。那么下面哪個結(jié)論是錯誤的？SegmentsinLcan'tintersectwithsegmentsinR(L集合中的線段不可能與R集合中的線段相交)SegmentsinLcanprobablyintersectwithsegmentsinR(L集合中的線段可能與R集合中的線段相交)SegmentsinLcanprobablyintersectwithsegmentsinM(L集合中的線段可能與M集合中的線段相交)SegmentsinRcanprobablyintersectwithsegmentsinM(R集合中的線段可能與M集合中的線段相交)答案：B1/2單選題(1分)Astheimagebelowshows,what'sthecorrectorderofeventsineventqueuebeforeswipelinestart?如下圖所示，在掃描線開始掃描之前，事件隊列當中的事件排列是？1,4,5,7,3,2,10,8,9,61,4,5,3,2,7,10,8,9,61,4,5,7,3,2,10,9,8,61,5,4,7,3,2,10,8,9,6答案：A2/2單選題(1分)Astheimagebelowshows,what'sthecorrectorderofeventsineventqueueifthesweeplinehasalreadysweepedtothepositionindicatedbytheorangedashedline?如下圖所示，掃描線已經(jīng)行進至當前橙色虛線表示的位置，那么此時此刻，事件隊列當中的事件是如何排列的？D,5,3,2,10,8,9,6A,5,3,2,10,8,9,6D,7,3,2,10,8,9,6A,7,3,2,10,8,9,6答案：D1/1多選題(2分)WhichofthefollowingpatternsofthesegmentswillhaveO(n2)intersectionpoints?下列哪些線段排列模式的交點個數(shù)是O(n2)量級的？答案：AD1/2單選題(1分)Astheimagebelowshows,whichofthefollowingpairsofmonotonechainsiscorrectifwedividetheconvexpolygonhorizontally?如下圖所示，將該凸多邊形水平方向上分解為兩條單調(diào)鏈，下列哪種分法是正確的？(1,2,3,4,5),(1,8,7,6,5)(1,2,3,4),(1,8,7,6,5,4)(1,2,3,4,5,6),(1,8,7,6)(1,2,3,4),(1,8,7,6)答案：A2/2單選題(1分)Astheimagebelowshows,ePandeQaremedianedgesfortwomonotonechains.Whichpartcanbeexcludedwhenapplyingdecreaseandconquermethod?如下圖所示，eP和eQ分別是兩條單調(diào)鏈的medianedge。當使用上述算法進行減而治之的時候，哪一段是可以被去掉的？1234答案：D1/1單選題(1分)Astheimagebelowshows,what'sthecorrectsequenceofedgechasing?(Itstartswithaand1,theblueedgegoesfirst)如下圖所示，對這兩個凸多邊形實施邊追趕算法，每次移動到的邊的次序是？（從a和1開始順時針移動，藍色先行）2,b,c,d,3,e,1,a2,b,c,3,d,e,1,a2,b,3,c,d,e,1,a2,b,c,3,d,1,e,a答案：B1/1單選題(1分)Whysweeplinestructurecanbestoredinfixed-lengtharraywhenweuseittoconstructtheintersectionbetweenconvexpolygons?為什么說，使用掃描線方法對兩個凸多邊形求交時，掃描線狀態(tài)結(jié)構(gòu)只要用固定長度的數(shù)組來表示就可以了？Becauseanyconvexpolygonwillhavenomorethan4intersectionpointswiththesweepline.(因為任意凸多邊形與掃描線最多交于4個交點上)Becauseanypolygonwillhavenomorethan2intersectionpointswiththesweepline.(因為任意多邊形與掃描線最多交于2個交點上)Becauseanyconvexpolygonwillhavenomorethan2intersectionpointswiththesweepline.(因為任意凸多邊形與掃描線最多交于2個交點上)Becauseanyconvexpolygonwillhavenomorethan1intersectionpointswiththesweepline.(因為任意凸多邊形與掃描線最多交于1個交點上)答案：C1/1單選題(1分)WhatiswrongaboutthereductionbetweenHICandSorting?下列關于HIC問題和Sorting問題的歸約，不正確的是？TheinputofHICcanbeconvertedtotheinputofSortinginlineartime(HIC問題的輸入可以在線性時間內(nèi)轉(zhuǎn)化為Sorting問題的輸入)TheoutputofHICcanbeconvertedtotheoutputofSortinginlineartime(HIC問題的輸出可以在線性時間內(nèi)轉(zhuǎn)化為Sorting問題的輸出)Sorting≦NHICAccordingtoreduction,wecangetthelowerboundsofHIC(利用歸約，我們可以確定HIC問題的下界)答案：A03.Triangulation1/1多選題(2分)Whatstatementsarerightaboutinteriordiagonal?內(nèi)對角線具有的屬性是？（多項選擇）Connectedgesofthepolygon(連接多邊形的邊)Connectverticesofthepolygon(連接多邊形的頂點)Doesnotcrossedgesofthepolygon(不穿過多邊形的邊)Crossedgesofthepolygon(穿過多邊形的邊)答案：BC1/2單選題(1分)Astheimagebelowshows,whichyellowareaisthecorrectvisibilitypolygonforguardX?如下圖所示，下列哪種黃色區(qū)域是正確的哨兵X的可視范圍。答案：A2/2單選題(1分)Ifthereexistsapolyhedronwithcameraslocatedineachvertex,someinnerareaofthepolyhedronstillcan'tbeviewed.Itmeansthat我們說三維空間中的一個多面體，如果多面體每個頂點放置一個攝像頭，仍然無法覆蓋所有內(nèi)部區(qū)域，其實是說？Therearefewverticesofthepolygon(意味著這個多面體的頂點數(shù)很少)Therearealotofverticesofthepolygon(意味著這個多面體的頂點數(shù)很多)Thereisapointinsidethepolyhedronwhichconnecteachvertexcrossingthefacesofthepolyhedron(意味著多面體內(nèi)存在一個點，與所有頂點連線皆穿過多邊形的面)Thereisapointinsidethepolyhedronwhichconnectsomevertexcrossingthefacesofthepolyhedron(意味著多面體內(nèi)存在一個點，并存在與之相連會穿過多邊形的面的頂點)答案：C1/1單選題(1分)Forartgalleryproblemofn-gonwithoutholes,whichstatementisright?關于不帶孔洞的n邊多邊形的畫廊問題來說，下列哪個論述是正確的？n/3guardsareinsufficient(n/3個哨兵可能是不夠的)n/3guardsarealwayssufficient(n/3個哨兵總是足夠的)Atmostn/3guardsareneeded(至多需要n/3個哨兵)Atleastn/3guardsareneeded(至少需要n/3個哨兵)答案：B1/2單選題(1分)Let'sreivewPigeon-HolePrincipal.Wecanassumethatthereareabout150,000hairsonaperson'shead.Therearemorethan1,000,000peopleinBeijing.Thusthereareatleasttwopersonswiththesamecountofhairs.我們來復習一下鴿巢原理。我們首先假定常人的頭發(fā)數(shù)在15萬左右，而北京的人口大于100萬，那么北京至少有兩個人的頭發(fā)一樣多。Correct(正確)Wrong(錯誤)答案：A2/2單選題(1分)Astheimagesbelowshow,whichdualgraphofthetriangulationiscorrect?如下圖所示，對于這樣的多邊形三角剖分，哪個對偶圖才是正確的？答案：A1/1單選題(1分)Whichiswrongaboutorthogonalpolyonswithnedges?下列哪個關于n邊正交多邊形的論述是錯誤的？Orthogonalpolygonsarepolygonswithverticalorhorizontaledges(正交多邊形是指邊要么水平要么垂直的多邊形)Orthogonalpolygon'sanglesummustbetimesof90°(正交多邊形的內(nèi)角和一定是90°的倍數(shù))Orthogonalpolygonsarespecialpolygons(正交多邊形是一般多邊形的一種特例)n/5guardsfortheartgalleryproblemoforthogonalpolygonsarealwayssufficient(正交多邊形的畫廊問題n/5個哨兵總是足夠的)答案：D1/2單選題(1分)Whichisasimplepolygon?下列多邊形哪個是簡單多邊形？答案：C2/2單選題(1分)IfweapplyEar-Cuttingalgorithmtothesimplepolygonbelow,howmanycutsareallowedforthefirstcut?對于下面的簡單多邊形進行“割耳朵”算法的話，第一刀可以有多少種切法？5678答案：A1/2單選題(1分)Whenplanesweephasreachedthisplaceastheimagebelowshows,howmanypushandpopoperationshavebeendone?對下面的多邊形進行掃描時，請問棧中完成了多少次push操作？多少次pop操作？5,36,46,35,4答案：C2/2單選題(1分)Whichofthepolygonsisnotmonotonepolygon?下列哪個多邊形并不是單調(diào)多邊形？答案：B1/2單選題(1分)Whichofthefollowingisnotthecorrectwayofdecomposesimplepolygonintomonotonepolygons?下列哪種不是正確地將簡單多邊形剖分成單調(diào)多邊形的做法？答案：C2/2單選題(1分)Beforeyouenterthenextunit,pleasereviewthealgorithm.Whatisthetimecomplexityformonotonedecomposition?在進入下一小節(jié)的算法分析部分前，請你回憶一下整個算法。對多邊形進行單調(diào)多邊形分解所消耗的時間是O(n)O(nlogn)O(logn)O(n2)答案：B1/2單選題(1分)Ifwetetrahedralizearegulartriangularprism,howmanywaysoftetrahedralizationarelegal?(Eachvertexisdifferent)對一個正三菱柱進行四面體剖分，有多少種剖分方案？（考慮每個頂點都是不同的）5678答案：B2/2多選題(2分)Whichofthefollowingarecorrect?(Multiplechoices)以下哪些選項是正確的？（多項選擇）Apolyhedroncanbetetrahedralizedinmultipleways,buteachwayhasthesamenumberoftetrahedrons(同一個多面體可能有多種四面體剖分方法，但是每個方法剖分出的四面體數(shù)量相等)NotallpolyhedronscanbetetrahedralizedwithoutSteinerpoints(不是所有多面體都可以不引入Steinerpoints進行四面體剖分)Apolyhedroncanbetetrahedralizedintodiferentnumberoftetrahedrons(同一個多面體可能剖分出不同數(shù)量的四面體)WiththehelpofSteinerpoints,somepolyhedronscan'tstillbetetrahedralized(即使引入Steinerpoints，有的多面體仍然不能進行四面體剖分)答案：BC04.VoronoiDiagram1/1單選題(1分)Whichstatementiscorrectaccordingtotheexampleofgrasslandfire?剛剛提到的點火的這個例子中，下列哪個論述是正確的？Theresultwillbenotaffectedifweigniteatdifferentsitesatdifferenttime(不同時點火不會影響最后結(jié)果)Theresultingboundariescanbeformedatthesametime(點火最后的邊界可以在一個時間點全部生成)Theresultingboundariesareformedasacircle(點火最后生成的邊界是一個圓形)Theresultingboundarybetweentwositeshasthesamedistancetoeachofthem(點火最后生成的邊界到兩個起火點的距離相等)答案：D1/2單選題(1分)Foranyconvexpolgyon,youcancutitintotwopiecesandremoveoneforanytimes.Theresultingpolygonisstillconvex給定任意的一個凸多邊形，你可以對它切任意刀，每次切完選擇其中的一部分。最后的這個剩余的多邊形始終是凸的。Correct(正確)Wrong(錯誤)答案：A2/2單選題(1分)Intheimagebelow,whatissite,cell,VoronoivertexaandVoronoiedge?在下圖中的例子里，site，cell，Voronoivertex和Voronoiedge分別指的是？1324123414231243答案：A1/2單選題(1分)Ifwemakeadiskcenteredatonespecificpointinacellwhichcrossthesiteexactly,whymustthediskbeempty?為什么處于某個cell中的某個點為圓心，做一個剛好穿過這個cell對應的site的圓一定是空的？Ifthediskcontainsothersites,thenthepointwillnotbelongtothiscell(如果這個圓中還包含其他site，那么它將不屬于這個cell)Becausetheradiusofthediskissmall(因為這個圓的半徑很小)Becausethesiteisfarawayfromothersites(因為site與site之間很稀疏)Becausethediskmustexistinthecell(因為這個圓一定在這個cell內(nèi)部)答案：A2/2單選題(1分)Whatisthenumberofverticeswithadegreeof4inaVoronoiDiagram?Voronoi圖中度為4的頂點的數(shù)量等于Thenumberofsites/3(site的數(shù)量除以3)Thenumberofsites/4(site的數(shù)量除以4)Thenumberofcircleswhichcross4concylicsites(四個site共圓的圓數(shù)量)Thenumberofemptycircleswhichcross4concylicsites(四個site共圓的空圓數(shù)量)答案：D1/1單選題(1分)IfweconverttheVoronoidiagrambelowtotheplanargraph,howmanyfaces,edgesandnodesarethere?下列這個Voronoi圖如果轉(zhuǎn)換成平面圖的話，有多少個面，多少個邊，多少個節(jié)點？585584587486答案：A1/1多選題(2分)Whichofthefollowingareplanargraphs?(Multiple