緒論1、單選題Whichofthefollowingisthekeyproblemthiscourseputanemphasison?(以下哪個話題是我們這門計算幾何課程中，重點(diǎn)關(guān)注的話題？)A、Thecontinuityofcurvesandsurfaces(曲線和曲面的連續(xù)性問題)B、Thedivisionofgeometricproblemsinalgorithmdesignandanalysis(算法中關(guān)于幾何問題的分支)C、Digitalimageprocessingandrecognition(數(shù)字圖像的處理與識別)B1、

單選題

WhichofthefollowingispreferedwhenencounteringanewComputationalGeometricproblem?(當(dāng)同學(xué)們面對一個新的計算幾何問題時，我們提倡的第一步是？)A、Goingthroughmaterials(查閱資料)B、Sharpobservation(敏銳的觀察)C、Rigorousconsideration(縝密的思考)D、Doingexperiments(做實(shí)驗(yàn)驗(yàn)證)B第一章A1、

單選題Intheimagebelow,whichofthenailsshouldbeboundtightlybytherubberbandifweextendtherubberbandtoincludeallthenailsandthenwelooseit?在下面的圖中，用橡皮筋包含所有的釘子再松手，將會形成的一段一段的橡皮筋的邊界。請問這個邊界所緊緊勒住的釘子是哪些？A1,2,3,4,5,6B1,2,7,8,5,3C1,2,7,6,5,3D1,2,8,5,3,4B2、單選題You'regivenpaintwithcolorofA=(10%,30%)andthepaintwiththecolorofB=(30%,70%).Whichofthefollowingcolorscanwegetbyblendingthesetwokindsofpain?現(xiàn)在有一種顏色A=(10%,30%)，一種顏色B=(30%,70%)，請問下面哪種顏色是可以被上述兩種顏色給勾兌出來的？A(40%,70%)B(60%,20%)C(40%,90%)D(25%,60%)D3、單選題

Nowwehave3kindsofpaint,whichareU=(10%,10%)，V=(60%,10%)，W=(10%,30%).Whichofthefollowingcolorscan'tbegeneratedbymixingthese3kindsofpaint?現(xiàn)在有三種顏色U=(10%,10%)，V=(60%,10%)，W=(10%,30%)，你能夠快速地知道下面哪個顏色是不可能由這三種顏色勾兌出來的么？A(60%,30%)B(20%,20%)C(40%,12%)D(15%,20%)AB1、C1、

單選題Whichoptiondoesn'tincludeanynon-extremeedgeforthepointssetbelow?對于下圖表示的點(diǎn)集來說，哪個選項包含的全部都是極邊？A(1,3),(1,9),(1,2),(5,10)B(3,5),(5,10),(9,10),(1,9)C(1,9),(9,5),(3,10),(3,5)D(3,5),(1,9),(9,4),(5,10)BD1、

單選題IfweuseIncrementalConstructionforgeneratingconvexhull,whatistheprogressofthevaryingcountoftheconvexhullforpointsbelow?對于下圖表示的點(diǎn)集來說，如果我們采用增量式策略構(gòu)造凸包，并按照標(biāo)號依次將新的點(diǎn)加入，那么凸包上的點(diǎn)的個數(shù)變化過程是？A1->2->3->3->4->5->5B1->2->2->3->4->5->6C1->2->3->4->4->5->6D1->2->3->3->4->5->6D2、

單選題

AfterintroducingIn-Convex-PolygonTest,let'sthinkabouttheIn-PolygonTestforgeneralpolygons.Generalpolygonscanbeconcaveorconvex,sometimeswithholes.Wehaveaspecificpointinageneralpolygon.Anotherrandompointexistingoutsidethepolygoncanbeconnectedwithitusingarandomcurve.Thenyou'llfindthat在討論了凸多邊形的In-Convex-PolygonTest方法之后，讓我們來思考一下一般多邊形的In-PolygonTest問題。與凸多邊形不同，一般多邊形可能是凹的，甚至可能是帶有孔洞的。對于一般多邊形內(nèi)部區(qū)域中的一點(diǎn)，我們在外部隨機(jī)找一點(diǎn)并隨意地用一根曲線連接它們，你會發(fā)現(xiàn)A、Thecurvepassesthroughtheboundaryofthepolygononce(曲線經(jīng)過多邊形邊界1次)B、Thecurvepassesthroughtheboundaryofthepolygonforoddtimes(曲線經(jīng)過多邊形邊界奇數(shù)次)C、Thecurvepassesthroughtheboundaryofthepolygonforseveraltimeswithnorules(曲線經(jīng)過多邊形邊界次數(shù)沒有規(guī)律)D、Thecurvepassesthroughtheboundaryofthepolygonforeventimes(曲線經(jīng)過多邊形邊界偶數(shù)次)B3、

單選題Okaynow.Let'sthinkaboutthespecialcasebasedonthelastproblem.Forarandomgeneralpolygon,howdoyouknowwhetherthepointisinsidethepolygon?WhatisthemethodforIn-PolygonTest?好的，在上一題的基礎(chǔ)之上，我們將條件從一般的情況反推到特殊的情況。對于任意的一般多邊形，判斷某一點(diǎn)是不是在這個多邊形內(nèi)部，也就是In-PolygonTest的辦法是？A、Drawarayfromthepointandcheckiftherayintersectswiththeboundaryofthepolygontwice(從該點(diǎn)射出一條射線，如果射線與多邊形邊界交點(diǎn)為2個，則為內(nèi)部)B、Drawarayfromthepointandcheckiftherayintersectswiththeboundaryofthepolygonforeventimes(從該點(diǎn)射出一條射線，如果射線與多邊形邊界交點(diǎn)個數(shù)為偶數(shù)，則為內(nèi)部)C、Drawarayfromthepointandcheckiftherayintersectswiththeboundaryofthepolygonforoddtimes(從該點(diǎn)射出一條射線，如果射線與多邊形邊界交點(diǎn)個數(shù)為奇數(shù)，則為內(nèi)部)D、Drawasegmentpassingthroughthepointandcheckifthesegmentintersectswiththeboundaryofthepolygonforoddtimes(經(jīng)過該點(diǎn)畫一條線段，如果直線與多邊形邊界交點(diǎn)個數(shù)為奇數(shù)，則為內(nèi)部)C4、

單選題Twosupportlinesdividetheconvexhullintotwoparts,standts.Fromtheimagebelowwecanknowthat凸包外部的一點(diǎn)x引出的兩條支撐線xt，xs將凸包邊界分成st和ts兩部分，通過觀察我們可以知道A、Anysegmentconnectingxwitharandompointontswillnotintersectwithanyotherboundaryoftheconvexhull(ts上的任意一點(diǎn)與x相連都不會與凸包其他邊界相交)B、Anysegmentconnectingxwitharandompointonstwillnotintersectwithanyotherboundaryoftheconvexhull(st上的任意一點(diǎn)與x相連都不會與凸包其他邊界相交)C、Anypointontsisinvisibletox(ts上的任意一點(diǎn)都對于x不可見)D、Anypointonstisvisibletox(st上的任意一點(diǎn)都對于x可見)AE1、

單選題

WhichofthefollowingiswrongaboutInsertionSortandSelectionSort?下面關(guān)于插入排序和選擇排序的一些說法，錯誤的是A、SelectionSortmakesexchangesinunsortedsubsequence(選擇排序每次主要在unsorted序列中做交換)B、InsertionSortcanguaranteethemaximumvalueoftheunsortedsubsequencelessthaneveryelementinthesortedsubsequence(插入排序中unsorted序列的最大值不會超過sorted序列)C、TwokindsofsortingalgorithmsruninO(n^2)(兩種排序算法的期望時間復(fù)雜度都是O(n^2))D、Twokindsofsortingalgorithmsreducethelengthoftheunsortedsubsequenceinordertosortthearray(兩種排序算法都是通過逐步減少unsorted序列的長度來實(shí)現(xiàn)排序)B2、

單選題

Astheimagebelowshows,theveryfirststepofJarvisMarchalgorithmisfindinganextremepointasthestartpoint.Ifweprojectallthepointsontheplanetoalineandmakea2Dto1Dmapping,wewillfindthat如下圖所述，JarvisMarch算法的第一步，是確定一個開始的極點(diǎn)。如果我們將平面上的點(diǎn)都投影到一條直線上，做一個二維到一維的映射的話，我們會發(fā)現(xiàn)A、Allextremepointswillbeprojectedtoonepointontheline(極點(diǎn)總是被投影到直線上的一個點(diǎn))B、Allextremepointswillbeprojectedtoeithermaximalorminimalpointontheline(極點(diǎn)總是被投影到直線上的最大值或者最小值)C、Themaximalorminimalpointonthelineismappedwiththeextremepoints(直線上的最大值或最小值總是對應(yīng)著極點(diǎn))D、Themaximalorminimalpointonthelineismappedwiththenon-extremepoints(直線上的最大值或最小值總是對應(yīng)著非極點(diǎn))C3、

單選題

Inthelastepisode,wetalkedaboutsortingusingthecomparatorofTo-LeftTest.Forpointsintheimagebelow,what'sthecorrectorder?(Sortthesepointsbycounter-clockawiseincreasinganglewithrespecttoredpoint)上一節(jié)中所講的利用To-Left測試來作為一個比較器進(jìn)行排序的方法，我們通常稱為極角排序。對于如下的點(diǎn)來說，極角排序的結(jié)果是？（以紅色點(diǎn)作為極角排序的中心，從1號點(diǎn)開始逆時針進(jìn)行排序）A1,2,4,7,5,6,3B1,2,7,4,5,6,3C1,5,4,7,2,6,3D1,2,4,7,5,3,6A4、

單選題InordertodeepenyourknowledgeofOutput-sensitiveAlgorithms,let'sreadasnippetofsimplecode.Thisisapieceofpseudocodeaboutimplementingdivisionusingsubtraction.Thetimecomplexityofthealgorithmis為了讓你對輸出敏感算法有更深的認(rèn)識，我們來看這樣一個簡單的算法。這是一個利用減法實(shí)現(xiàn)除法的算法，如下圖偽代碼所示。該算法的時間復(fù)雜度是A、O(N)B、O(D)C、O(R)D、O(Q)DF1、

單選題

IfA≤N

BforalgorithmsAandB,whichofthefollowingiscorrect?當(dāng)有兩個算法A和B，其中A≤N

B的時候，下列哪個說法是正確的？A、InputofAcanbeconvertedtoinputofBinlineartime(算法A的輸入可以在線性時間內(nèi)轉(zhuǎn)換為算法B的輸入)B、InputofAcanbeconvertedtooutputofBinlineartime(算法A的輸入可以在線性時間內(nèi)轉(zhuǎn)換為算法B的輸出)C、OutputofAcanbeconvertedtoinputofBinlineartime(算法A的輸出可以在線性時間內(nèi)轉(zhuǎn)換為算法B的輸入)D、OutputofAcanbeconvertedtooutputofBinlineartime(算法A的輸出可以在線性時間內(nèi)轉(zhuǎn)換為算法B的輸出)A2、

單選題

Whichofthefollowingiswrongaccordingtothelastepisode?上面提到的曹沖稱象作為歸約思想的類比，下列哪個說法是錯誤的？A、CaoChonggettheweightoftheelephantusingtheweightoftherocksbasedonreduction(利用歸約思想，曹沖利用石頭的重量去估算出大象的重量)B、theweightofelephant≤NTheweightofrocks(大象的重量≤N石頭的重量)C、ReductionrelationshipheremeanstheboatandthewaterusedinCaoChong'smethod(這里的歸約關(guān)系是指曹沖稱象時的船和水)D、Iftwoobjectswiththesameweighthasdifferentmarks,thenreductionrelationshipherebreaks(如果兩個物體重量相同但吃水的刻度不同，則歸約關(guān)系就被破壞了)B3、

單選題Afterlearningthereductionrelationshipbetween2d-CHandSorting,whichofthefollowingiswrong?學(xué)習(xí)了排序與二維凸包算法的歸約關(guān)系以后，下列哪個說法是錯誤的？A、Anyarraytobesortedcanbemappedtothepointssetonthe2d-planeinlineartime(任何一個待排序的數(shù)組，都可以線性時間映射為二維平面上的點(diǎn)集)B、Anyconvexhullonthe2d-planecanbemappedtoasortedarrayinlineartime(任何一個二維平面上的凸包，都可以線性時間映射為一個有序數(shù)組)C、Wecansolvea2d-CHproblemforsolvingasortingproblem(為了解決排序問題，我們可以先解決一個二維凸包問題)D、If2d-CHalgorithmscanbeO(n)intime,SortingalgorithmcanbeO(n)intime,too(如果二維凸包算法有O(n)的時間復(fù)雜度，那么排序算法也可以通過歸約達(dá)到O(n)的時間復(fù)雜度)BG1、

單選題StackisanimportantdatastructureinGrahamScan.IfthereisanemptystackSandthepushingorderofthestackisA,B,C,D,E,whichofthefollowingpoppingorderisillegal?在GrahamScan算法當(dāng)中，棧是作為一個很重要的數(shù)據(jù)結(jié)構(gòu)存在的?，F(xiàn)在假設(shè)有一個空棧S，元素入棧的順序是A、B、C、D、E，那么下面哪個出棧順序是不可能存在的？A、B、A、D、C、EB、D、A、E、B、CC、C、B、A、E、DD、C、B、D、A、EB2、

單選題

InGrahamScan,thealgorithmendswithanemptystackT.WhystackSwon'tbecomeemptybeforestackTbecomeempty?在GrahamScan算法當(dāng)中，算法結(jié)束是以T棧為空作為標(biāo)志的，那么為什么S棧不會先于T棧變空呢？A、AllelementsofstackTgointothestackS(T棧中的元素都進(jìn)入了S棧)B、ThesizeofstackSisalwayslargerthanthesizeofstackT(S棧中元素個數(shù)總是多于T棧)C、ThereareonlypushingtowoardsstackSwithnopoppingfromstackS(S棧中元素只會進(jìn)不會出)D、TwoextremepointsstayatthebottomofstackSandit'simpossibletopopthemaccordingtoTo-Lefttest(S棧底部的兩點(diǎn)是極邊上的點(diǎn)，不可能因?yàn)門o-Left測試而出棧)DH1、

單選題IfwedoGrahamScantothefigurebelow,what'sthepoppingorderofstackS?對下圖做GrahamScan掃描，S棧的出棧順序是？A4，5，3，7B4，3，5，7C4，3，7，5D3，4，5，7AI1、

單選題Astheimagebelowshows,whywon'tthepoint2bebacktracked?如下圖所示，當(dāng)發(fā)生backtrack的時候，為什么最多也不會越過2號點(diǎn)？A、Becausethealgorithmmakesadeterminationbeforebacktrackingthepoint2(因?yàn)樗惴ㄔ赽acktrack到2號點(diǎn)之前加了判斷)B、Becausethepoint2isanextremepoint(因?yàn)?號點(diǎn)是極點(diǎn))C、Becausethepointsbeforethepoint2can'tbepopped(因?yàn)?號點(diǎn)前面的點(diǎn)也不會被pop出去)D、Becausethepoint3stillstandsinfrontofthepoint2(因?yàn)?號點(diǎn)前面還有3號點(diǎn))B2、單選題

Ifwedon'tapplypresorting,whatistheresultoftheGrahamScanforthisChinesecharacterfrombottomtotop?如果不做Presorting的話，下面這個字從下到上順序進(jìn)行GrahamScan，最后會產(chǎn)生的結(jié)果是？A、Becauseeverycaseisanright-turn,eachpointwillbeontheconvexhull(由于每個點(diǎn)都是右拐的情況，所以所有的點(diǎn)都在凸包上)B、NopointswillstayinstackT(沒有點(diǎn)在T棧上)C、Acorrectconvexhullwillbeconstructed(會得到一個正確的凸包)D、NopointswillstayinstackS(沒有點(diǎn)在S棧上)BJ1、

單選題Forasimplepolyhedron,itssizeofverticesis10anditssizeoffacesis5.Howmanyedgesdoesitown?對于一個簡單多面體來說，如果其頂點(diǎn)個數(shù)為10，面數(shù)為5，那么它包含多少條棱呢？A13B14C23D24A2、單選題

HowmanystepswillthescanningtakeifdoingGrahamScantonpoints?(Nodegenerationsituation)對n個點(diǎn)進(jìn)行GrahamScan，其中scan的過程中最多會迭代多少步？（不考慮退化情況）A2n-6B2n-5C2n-7D2n-8B3、

單選題

Ifwehaveasetofpointswhicharealreadysortedaccordingtoxcoordinates,sowhat'sthetimecomplexityofthealgorithmofUpper/LowerHull?前面介紹的Upper/LowerHull算法，如果輸入的平面上的點(diǎn)已經(jīng)是x方向上有序的話，那么該算法執(zhí)行的時間復(fù)雜度是？AO(1)BO(n2)CO(n)DO(nlgn)CK1、單選題WhatiswrongabouttheanalogybetweenconvexhullusingDACandmergesort?關(guān)于利用分治思想構(gòu)建凸包算法和歸并排序算法的類比，錯誤的是A、Theresultingconvexhullisinanalogywiththesortedarray(最終的凸包結(jié)果類比于排好序的數(shù)組)B、Thedivisionofthepointsetisinanalogywiththedivisionofthearray(將平面上的點(diǎn)集進(jìn)行劃分類比于對數(shù)組進(jìn)行劃分)C、Combiningtwosubconvexhullstoonesubconvexhullisinanalogywithmergingtwosortedsubsequenceintoonesortedsubsequence(將兩個子凸包合并為一個子凸包類比于兩個排好序的子序列歸并為一個排好序的子序列)D、Thesizeoftheextremepointsonconvexhullisinanalogywiththesizeofsortedarray(凸包上極點(diǎn)的個數(shù)類比于數(shù)組的大小)D2、

單選題Whichofthefollowingpolygonsisnotstar-shapedpolygon?下列哪個多邊形不是星形多邊形？C3、

單選題

Ifwetrytocombinethesetwoconvexhulls(convexhull1-5andconvexhull6-0)together,what'sthepointsoftheresultingstar-shapedpolygon?(Thepointswillstartwithpoint1andbelistedcounterclockawise)將上述兩個凸包（凸包1-5和凸包6-9）進(jìn)行合并時，最后生成的星形多邊形上的頂點(diǎn)列表是？（從頂點(diǎn)1開始，逆時針排列）A1,6,3,4,5,8B1,6,2,3,7,4,5,8,9C1,6,2,3,4,7,5,8,9D1,6,2,3,7,4,5,9,8B4、單選題Ifwecombinethesetwoconvexhulls(convexhull1-7,convexhull8-14)together,what'stheresultingstar-shapedpolygon?(Thepointswillstartwiththepoint1andbelistedclockawise)對于下圖所示的兩個凸包（凸包1-7，凸包8-14）進(jìn)行歸并的時候，最后得到的星形多邊形的頂點(diǎn)列表是？（以1開始，順時針排列）A1,2,8,9,10,11,12,4,5,6,7B1,2,8,9,10,3,11,12,13,14,4,5,6,7C1,2,8,9,10,3,11,12,4,5,6,7D1,2,9,10,3,11,4,5,6,7CL1、

單選題

Whichofthefollowingchoicesiswrongaboutthefindingtheright-mostpointoftheleftconvexhull(withasizeofn)andtheleft-mostpointoftherightconvexhull(withasizeofm)?下列選項中對于尋找左凸包（規(guī)模為n）的最右側(cè)頂點(diǎn)和右凸包（規(guī)模為m）的最左側(cè)頂點(diǎn)這個操作來說，錯誤的是？A、TheoperationwilltakeO(m+n)timeifwedon'trecordanyinformation(如果不記錄任何信息的話，這個操作需要消耗O(m+n)時間)B、ItwilltakeO(1)timetocompletetheoperationifwerecordedtheleft-mostpointofeachsubconvexhull(只要每次記錄子凸包的最左頂點(diǎn)就可以在O(1)時間完成這個操作)C、Theleft-mostpointoftheleftconvexhullwillbecometheleft-mostpointofthecombinedconvexhull(左側(cè)子凸包的最左頂點(diǎn)將會成為合并后凸包的最左頂點(diǎn))D、Theright-mostpointoftherightconvexhullwillbecometheright-mostpointofthecombinedconvexhull(右側(cè)子凸包的最右頂點(diǎn)將會成為合并后凸包的最右頂點(diǎn))B2、

單選題Astheimagebelowshows,theblackdashedlineconnecttheright-mostpointoftheleftconvexhullandtheleft-mostpointoftherightconvexhull;theorangelinerepresentstheuppercommontangent;theorangedahsedlinemeansthefirststepofZig-zagging.What'sthefollowingstepsofZig-zagging?如下圖所示，黑色虛線表示左凸包右頂點(diǎn)與右凸包左頂點(diǎn)的連線；橙色實(shí)線表示左右凸包的上切線；橙色虛線表示進(jìn)行Zig-zag操作的第一步。請問接下來的步驟是？A(2,5),(2,4),(1,4)B(1,6),(1,5),(1,4)C(2,5),(1,5),(1,4)D(2,5),(3,5),(3,4),(2,4),(1,4)A3、單選題

Whichofthefollowingpairsoftheconvexhullswillbewrongaboutsimplyconnectingtopmostpointsandbottommostpointsinordertocalculatethecommontangents?下列哪些凸包對計算公切線時，并不是每個凸包的上下兩個頂點(diǎn)互相相連？C圓第二章1、

單選題

Whichofthefollowingisabout'count'ofgeometricintersectionproblems?下列哪個問題包含了幾何求交問題中的“計數(shù)”問題？A、Stopplayersfrompassingthroughwallsingamedevelopment(游戲開發(fā)中防止角色穿過墻壁)B、Construct3Dmodelswithbooleanoperationofsimplepolyhedrons(利用簡單幾何體進(jìn)行布爾運(yùn)算創(chuàng)建復(fù)雜三維模型)C、Getthenumberofintersectionsofsegmentsontheplane(判斷平面上線段的交點(diǎn)個數(shù))D、Raytracingmethodforphotorealisticrendering(光線追蹤算法進(jìn)行真實(shí)感渲染)CA1、

單選題Thereisanarrayof1001elementswhichrangefrom1to1000.Onlyoneelementisrepeatedinthearraywhiletheothersexistonlyonceinthearray.Whichofthefollowingalgorithmsisthefastest?1-1000放在含有1001個元素的正整數(shù)數(shù)組中，只有唯一的一個元素值重復(fù)，其它均只出現(xiàn)一次。下列哪種算法查找這個重復(fù)元素最快？A、Enumeratealltheparisinthearray,findthepairwithsamevalues(枚舉1001個元素中所有的正整數(shù)對，找到值相同的那一對)B、XORallthenumbersinthearraytogether,thenXORnumberfrom1to1000(現(xiàn)將數(shù)組中所有數(shù)異或在一起，再與1-1000各異或一次)C、Sortthearrayandthenmakesequentialsearch(將數(shù)組進(jìn)行排序，再線性搜索)D、Sortthearrayandthenmakebinarysearch(將數(shù)組進(jìn)行排序，再二分搜索)B2、單選題Ifwedivide3,5,2,7,10,13intodifferentbucketsusingthemethodmentioned,what'stheresult?使用上述的Max-Gap分桶算法對下列數(shù)3,5,2,7,10,13進(jìn)行分桶的話，結(jié)果是？A(2,3),(5),(7),(10),(),(13)B(2,3),(5),(7),(10),(13)C(2),(3,5),(7),(10),(),(13)D(2,3),(5),(),(7,10),(),(13)AB1、

單選題

Ifweapplythealgorithmmetionedtofourintervalslike(1,3),(4,10),(5,6),(0,2),whichofthefollowingisthecorrectpatternsequence?以下4個區(qū)間(1,3),(4,10),(5,6),(0,2)運(yùn)用上述算法進(jìn)行相交檢測時，待檢測的模式序列是？A、LLLRRRLRB、LRLRLLRRC、LLRRLRLRD、LLRRLLRRDC1、

單選題What'swrongaboutthereductionbetweenEUandSID?下列關(guān)于EU問題和SID問題的歸約，錯誤的是？A、EU≦NSIDB、Accordingtoreduction,wecanfoundthelowerboundofSID(通過進(jìn)行歸約，我們可以找到SID問題的下界)C、TheinputofSIDcanbeconvertedtotheinputofSIDinlineartime(SID問題的輸入可以在線性時間內(nèi)轉(zhuǎn)化為EU問題的輸入)D、TheoutputofSIDcanbeconvertedtotheoutputofEUinlineartime(SID問題的輸出可以在線性時間內(nèi)轉(zhuǎn)化為EU問題的輸出)CD1、

多選題Whichofthefollowingcanimplementpriorityqueue?(Multiplechoice)下列哪些數(shù)據(jù)結(jié)構(gòu)通常作為優(yōu)先隊列的實(shí)現(xiàn)？（多項選擇）A、Hashtable(哈希表)B、BinaryHeap(二叉堆)C、FibonacciHeap(Fibonacci堆)D、Stack(棧)BC2、

單選題

Thereareseveralsegmentsontheplane.Nowweputasweeplineontheplanerandomly.IfwemarkthesetofsegmentsstayinglefttothesweeplineasL,thesetofsegmentsstayingrighttothesweeplineasRandthesetofsegmentscrossedbysweeplineasM.Whichofthefollowingconclusionsiswrong?平面上若干條線段，隨機(jī)放置一條掃描線。我們設(shè)完全在掃描線左側(cè)的線段集為L；完全在掃描線右端的線段集為R；被掃描線穿過的線段集為M。那么下面哪個結(jié)論是錯誤的？A、SegmentsinLcan'tintersectwithsegmentsinR(L集合中的線段不可能與R集合中的線段相交)B、SegmentsinLcanprobablyintersectwithsegmentsinR(L集合中的線段可能與R集合中的線段相交)C、SegmentsinLcanprobablyintersectwithsegmentsinM(L集合中的線段可能與M集合中的線段相交)D、SegmentsinRcanprobablyintersectwithsegmentsinM(R集合中的線段可能與M集合中的線段相交)BE1、單選題Astheimagebelowshows,what'sthecorrectorderofeventsineventqueuebeforeswipelinestart?如下圖所示，在掃描線開始掃描之前，事件隊列當(dāng)中的事件排列是？A1,4,5,7,3,2,10,8,9,6B1,4,5,3,2,7,10,8,9,6C1,4,5,7,3,2,10,9,8,6D1,5,4,7,3,2,10,8,9,6A2、

單選題Astheimagebelowshows,what'sthecorrectorderofeventsineventqueueifthesweeplinehasalreadysweepedtothepositionindicatedbytheorangedashedline?如下圖所示，掃描線已經(jīng)行進(jìn)至當(dāng)前橙色虛線表示的位置，那么此時此刻，事件隊列當(dāng)中的事件是如何排列的？A、D,5,3,2,10,8,9,6B、A,5,3,2,10,8,9,6C、D,7,3,2,10,8,9,6D、A,7,3,2,10,8,9,6DF1、多選題

WhichofthefollowingpatternsofthesegmentswillhaveO(n2)intersectionpoints?下列哪些線段排列模式的交點(diǎn)個數(shù)是O(n2)量級的？ADG1、

單選題

Astheimagebelowshows,whichofthefollowingpairsofmonotonechainsiscorrectifwedividetheconvexpolygonhorizontally?如下圖所示，將該凸多邊形水平方向上分解為兩條單調(diào)鏈，下列哪種分法是正確的？A(1,2,3,4,5),(1,8,7,6,5)B(1,2,3,4),(1,8,7,6,5,4)C(1,2,3,4,5,6),(1,8,7,6)D(1,2,3,4),(1,8,7,6)A2、

單選題Astheimagebelowshows,eP

andeQ

aremedianedgesfortwomonotonechains.Whichpartcanbeexcludedwhenapplyingdecreaseandconquermethod?如下圖所示，eP和eQ分別是兩條單調(diào)鏈的medianedge。當(dāng)使用上述算法進(jìn)行減而治之的時候，哪一段是可以被去掉的？A1B2C3D4DH1、

單選題

Astheimagebelowshows,what'sthecorrectsequenceofedgechasing?(Itstartswithaand1,theblueedgegoesfirst)如下圖所示，對這兩個凸多邊形實(shí)施邊追趕算法，每次移動到的邊的次序是？（從a和1開始順時針移動，藍(lán)色先行）A2,b,c,d,3,e,1,aB2,b,c,3,d,e,1,aC2,b,3,c,d,e,1,aD2,b,c,3,d,1,e,a

BI1、單選題Whysweeplinestructurecanbestoredinfixed-lengtharraywhenweuseittoconstructtheintersectionbetweenconvexpolygons?為什么說，使用掃描線方法對兩個凸多邊形求交時，掃描線狀態(tài)結(jié)構(gòu)只要用固定長度的數(shù)組來表示就可以了？A、Becauseanyconvexpolygonwillhavenomorethan4intersectionpointswiththesweepline.(因?yàn)槿我馔苟噙呅闻c掃描線最多交于4個交點(diǎn)上)B、Becauseanypolygonwillhavenomorethan2intersectionpointswiththesweepline.(因?yàn)槿我舛噙呅闻c掃描線最多交于2個交點(diǎn)上)C、Becauseanyconvexpolygonwillhavenomorethan2intersectionpointswiththesweepline.(因?yàn)槿我馔苟噙呅闻c掃描線最多交于2個交點(diǎn)上)D、Becauseanyconvexpolygonwillhavenomorethan1intersectionpointswiththesweepline.(因?yàn)槿我馔苟噙呅闻c掃描線最多交于1個交點(diǎn)上)CJ1、

單選題WhatiswrongaboutthereductionbetweenHICandSorting?下列關(guān)于HIC問題和Sorting問題的歸約，不正確的是？A、TheinputofHICcanbeconvertedtotheinputofSortinginlineartime(HIC問題的輸入可以在線性時間內(nèi)轉(zhuǎn)化為Sorting問題的輸入)B、TheoutputofHICcanbeconvertedtotheoutputofSortinginlineartime(HIC問題的輸出可以在線性時間內(nèi)轉(zhuǎn)化為Sorting問題的輸出)C、Sorting≦NHICD、Accordingtoreduction,wecangetthelowerboundsofHIC(利用歸約，我們可以確定HIC問題的下界)A第三章1、

多選題Whatstatementsarerightaboutinteriordiagonal?內(nèi)對角線具有的屬性是？（多項選擇）A、Connectedgesofthepolygon(連接多邊形的邊)B、Connectverticesofthepolygon(連接多邊形的頂點(diǎn))C、Doesnotcrossedgesofthepolygon(不穿過多邊形的邊)D、Crossedgesofthepolygon(穿過多邊形的邊)BCA1、單選題Astheimagebelowshows,whichyellowareaisthecorrectvisibilitypolygonforguardX?如下圖所示，下列哪種黃色區(qū)域是正確的哨兵X的可視范圍。A2、單選題Ifthereexistsapolyhedronwithcameraslocatedineachvertex,someinnerareaofthepolyhedronstillcan'tbeviewed.Itmeansthat我們說三維空間中的一個多面體，如果多面體每個頂點(diǎn)放置一個攝像頭，仍然無法覆蓋所有內(nèi)部區(qū)域，其實(shí)是說？A、Therearefewverticesofthepolygon(意味著這個多面體的頂點(diǎn)數(shù)很少)B、Therearealotofverticesofthepolygon(意味著這個多面體的頂點(diǎn)數(shù)很多)C、Thereisapointinsidethepolyhedronwhichconnecteachvertexcrossingthefacesofthepolyhedron(意味著多面體內(nèi)存在一個點(diǎn)，與所有頂點(diǎn)連線皆穿過多邊形的面)D、Thereisapointinsidethepolyhedronwhichconnectsomevertexcrossingthefacesofthepolyhedron(意味著多面體內(nèi)存在一個點(diǎn)，并存在與之相連會穿過多邊形的面的頂點(diǎn))CB1、

單選題Forartgalleryproblemofn-gonwithoutholes,whichstatementisright?關(guān)于不帶孔洞的n邊多邊形的畫廊問題來說，下列哪個論述是正確的？A、n/3guardsareinsufficient(n/3個哨兵可能是不夠的)B、n/3guardsarealwayssufficient(n/3個哨兵總是足夠的)C、Atmostn/3guardsareneeded(至多需要n/3個哨兵)D、Atleastn/3guardsareneeded(至少需要n/3個哨兵)BC1、

單選題Let'sreivewPigeon-HolePrincipal.Wecanassumethatthereareabout150,000hairsonaperson'shead.Therearemorethan1,000,000peopleinBeijing.Thusthereareatleasttwopersonswiththesamecountofhairs.我們來復(fù)習(xí)一下鴿巢原理。我們首先假定常人的頭發(fā)數(shù)在15萬左右，而北京的人口大于100萬，那么北京至少有兩個人的頭發(fā)一樣多。A、Correct(正確)B、Wrong(錯誤)A2、

單選題Astheimagesbelowshow,whichdualgraphofthetriangulationiscorrect?如下圖所示，對于這樣的多邊形三角剖分，哪個對偶圖才是正確的？AD1、

單選題Whichiswrongaboutorthogonalpolyonswithnedges?下列哪個關(guān)于n邊正交多邊形的論述是錯誤的？A、Orthogonalpolygonsarepolygonswithverticalorhorizontaledges(正交多邊形是指邊要么水平要么垂直的多邊形)B、Orthogonalpolygon'sanglesummustbetimesof90°(正交多邊形的內(nèi)角和一定是90°的倍數(shù))C、Orthogonalpolygonsarespecialpolygons(正交多邊形是一般多邊形的一種特例)D、n/5guardsfortheartgalleryproblemoforthogonalpolygonsarealwayssufficient(正交多邊形的畫廊問題n/5個哨兵總是足夠的)DE1、

單選題Whichisasimplepolygon?下列多邊形哪個是簡單多邊形？C2、

單選題IfweapplyEar-Cuttingalgorithmtothesimplepolygonbelow,howmanycutsareallowedforthefirstcut?對于下面的簡單多邊形進(jìn)行“割耳朵”算法的話，第一刀可以有多少種切法？A5B6C7D8AF1、

單選題Whenplanesweephasreachedthisplaceastheimagebelowshows,howmanypushandpopoperationshavebeendone?對下面的多邊形進(jìn)行掃描時，請問棧中完成了多少次push操作？多少次pop操作？A5,3B6,4C6,3D5,4C2、

單選題

Whichofthepolygonsisnotmonotonepolygon?下列哪個多邊形并不是單調(diào)多邊形？BG1、單選題Whichofthefollowingisnotthecorrectwayofdecomposesimplepolygonintomonotonepolygons?下列哪種不是正確地將簡單多邊形剖分成單調(diào)多邊形的做法？C2、

單選題Beforeyouenterthenextunit,pleasereviewthealgorithm.Whatisthetimecomplexityformonotonedecomposition?在進(jìn)入下一小節(jié)的算法分析部分前，請你回憶一下整個算法。對多邊形進(jìn)行單調(diào)多邊形分解所消耗的時間是A、O(n)B、O(nlogn)C、O(logn)D、O(n2)BI1、

單選題

Ifwetetrahedralizearegulartriangularprism,howmanywaysoftetrahedralizationarelegal?(Eachvertexisdifferent)對一個正三菱柱進(jìn)行四面體剖分，有多少種剖分方案？（考慮每個頂點(diǎn)都是不同的）A5B6C7D8B2、

多選題Whichofthefollowingarecorrect?(Multiplechoices)以下哪些選項是正確的？（多項選擇）A、Apolyhedroncanbetetrahedralizedinmultipleways,buteachwayhasthesamenumberoftetrahedrons(同一個多面體可能有多種四面體剖分方法，但是每個方法剖分出的四面體數(shù)量相等)B、NotallpolyhedronscanbetetrahedralizedwithoutSteinerpoints(不是所有多面體都可以不引入Steinerpoints進(jìn)行四面體剖分)C、Apolyhedroncanbetetrahedralizedintodiferentnumberoftetrahedrons(同一個多面體可能剖分出不同數(shù)量的四面體)D、WiththehelpofSteinerpoints,somepolyhedronscan'tstillbetetrahedralized(即使引入Steinerpoints，有的多面體仍然不能進(jìn)行四面體剖分)BC第四章A1、單選題

Whichstatementiscorrectaccordingtotheexampleofgrasslandfire?剛剛提到的點(diǎn)火的這個例子中，下列哪個論述是正確的？A、Theresultwillbenotaffectedifweigniteatdifferentsitesatdifferenttime(不同時點(diǎn)火不會影響最后結(jié)果)B、Theresultingboundariescanbeformedatthesametime(點(diǎn)火最后的邊界可以在一個時間點(diǎn)全部生成)C、Theresultingboundariesareformedasacircle(點(diǎn)火最后生成的邊界是一個圓形)D、Theresultingboundarybetweentwositeshasthesamedistancetoeachofthem(點(diǎn)火最后生成的邊界到兩個起火點(diǎn)的距離相等)DB1、單選題

Foranyconvexpolgyon,youcancutitintotwopiecesandremoveoneforanytimes.Theresultingpolygonisstillconvex給定任意的一個凸多邊形，你可以對它切任意刀，每次切完選擇其中的一部分。最后的這個剩余的多邊形始終是凸的。A、Correct(正確)B、Wrong(錯誤)A2、

單選題

Intheimagebelow,whatissite,cell,VoronoivertexaandVoronoiedge?在下圖中的例子里，site，cell，Voronoivertex和Voronoiedge分別指的是？A1324B1234C1423D1243AC1、

單選題Ifwemakeadiskcenteredatonespecificpointinacellwhichcrossthesiteexactly,whymustthediskbeempty?為什么處于某個cell中的某個點(diǎn)為圓心，做一個剛好穿過這個cell對應(yīng)的site的圓一定是空的？A、Ifthediskcontainsothersites,thenthepointwillnotbelongtothiscell(如果這個圓中還包含其他site，那么它將不屬于這個cell)B、Becausetheradiusofthediskissmall(因?yàn)檫@個圓的半徑很小)C、Becausethesiteisfarawayfromothersites(因?yàn)閟ite與site之間很稀疏)D、Becausethediskmustexistinthecell(因?yàn)檫@個圓一定在這個cell內(nèi)部)A2、

單選題Whatisthenumberofverticeswithadegreeof4inaVoronoiDiagram?Voronoi圖中度為4的頂點(diǎn)的數(shù)量等于A、Thenumberofsites/3(site的數(shù)量除以3)B、Thenumberofsites/4(site的數(shù)量除以4)C、Thenumberofcircleswhichcross4concylicsites(四個site共圓的圓數(shù)量)D、Thenumberofemptycircleswhichcross4concylicsites(四個site共圓的空圓數(shù)量)DD1、單選題

IfweconverttheVoronoidiagrambelowtotheplanargraph,howmanyfaces,edgesandnodesarethere?下列這個Voronoi圖如果轉(zhuǎn)換成平面圖的話，有多少個面，多少個邊，多少個節(jié)點(diǎn)？A585B584C587D486AE1、

多選題Whichofthefollowingareplanargraphs?(Multiplechoices)下列哪些圖是平面圖？（多項選擇）ABCDF1、

單選題

IntheDCELbelow,howdoweaccesspfrome?在下圖所示的DCEL中，從一條半邊e找到另一側(cè)的頂點(diǎn)p的辦法是？A、e->pred->oriB、e->pred->pred->pred->oriC、e->pred->pred->oriD、e->twin->succ->oriC2、

單選題

WhichstatementiscorrectforDCELbelow?下列關(guān)于這個DCEL結(jié)構(gòu)來說，哪個等式是正確的？A、e->pred->pred->twin=e->twin->succ->succB、e->pred->pred->twin=e->twin->succ->succ->twin->succC、e->twin->succ->ori=e->pred->oriD、e->twin->succ->succ->twin=e->pred->predB3、

單選題

FortheDCELbelow,whatisthemethodoftraversalfromftos?對于下面這個DCEL結(jié)構(gòu)來說，從一個面f到達(dá)另一個面s的遍歷辦法是？A、s=f->inc->twin->succ->succ->incB、s=f->inc->twin->succ->succ->twinC、s=f->inc->twin->succ->twin->incD、s=f->inc->twin->succ->succ->twin->incDG1、

單選題

Accordingtothereductionbetweensortingand2DVD,howcanweconverttheunsortedarraytotheinputofa2DVDproblem?Wesetanelementinarrayasx,theminimumelementisminandthemaximumoneismax.Howcanwemapthenumberstothepointsontheplane?在上述關(guān)于排序和二維Voronoi圖的歸約當(dāng)中，如何將一個待排序的數(shù)組轉(zhuǎn)化為為二維Voronoi圖的輸入呢？設(shè)數(shù)組中的某個元素為x，最小值為min，最大值為max。那么映射為二維平面上的點(diǎn)的方法可以是？A(x,x^2)B(cosθ,sinθ),θ=((x-min)/(max-min)*2π)C(cosθ,cosθ),θ=((x-min)/(max-min)*2π)D(x,1)BH1、單選題

Ifweapplyaffinetransformtothesquarebelow,whichisnotpossible?對于下圖中所示的正方形進(jìn)行的變換，哪一個不是仿射變換？DI1、

單選題Ifε=12,whatwillwegetafteraplyingliftingtransformtoanarrayof[3,5,2,1,4,6]?設(shè)ε=12，那么對于一個數(shù)組[3,5,2,1,4,6]來說，提升變換以后的點(diǎn)是？A、(3,1),(5,2),(2,3),(1,4),(4,5),(6,6)B、(3,2),(5,4),(1,8),(4,10),(6,12)C、(3,3),(5,5),(2,7),(1,9),(4,11),(6,13)D、(3,2),(5,4),(2,6),(1,8),(4,10),(6,12)D2、單選題Intheproofmentioned,what'stherelationshipamongthese3dashedline?在上述證明當(dāng)中，這三條虛線的長度關(guān)系是？A、ji<Ii<JiB、ji<Ji<IiC、Ji<ji<IiD、Ii<Ji<jiBJ1、單選題

Whyisthenaiveconstructionsoinefficient?為什么這種直觀的算法的時間復(fù)雜度如此之高呢？A、unnecessarycalculationwhenclippingthecell(對cell做裁剪的過程中有多余的計算)B、Thealgorithmisnotcorrect(這個算法是不正確的)C、Intersectiontakestoomuchtime(求交的算法太低效了)D、Constructionofintersectionbetweentheconvexhullandahalf-planetakeO(n3)time(構(gòu)造一個凸包和一個半平面的交需要O(n3)時間)AK1、

單選題IntheincrementalconstructionofVoronoidiagram,eachoftheedgesofthecellforanewsite(yellow)isdeterminedbyabisectorbetweenthenewsiteandanoldone.Supposethatthebisectorsaredeterminedinanorderasbelow.What'stheorderinwhichtheexistingedgesaretraversed?如下圖所示使用增量構(gòu)造法進(jìn)行Voronoi圖構(gòu)造，此時加入一個黃色頂點(diǎn)后，產(chǎn)生新的bisector。產(chǎn)生bisector的順序如下所示，那么Voronoi邊的遍歷順序是？A、acdefgijbB、acdfeghijbC、acdefghijbD、adefgijbCL1、

單選題

AboutthestrategyofDACforVoronoidiagram,whichofthefollowingiscorrect?關(guān)于Voronoi圖的分治算法思路，正確的是？A、hRcutthecellofr(hR裁切r對應(yīng)的cell)B、hRcutthecellofl(hR裁切l(wèi)對應(yīng)的cell)C、hLcutthecellofl(hL裁切l(wèi)對應(yīng)的cell)D、Thewhitepolylineinthefigureabovedenotedthebisectorbetweenlandr(圖中白色邊界為l和r的bisector)B2、

單選題

Whichofthefollowingcontoursmustbewrong?下列哪條輪廓線一定是錯誤的？C3、

單選題

Thereare100siteslefttothecontourand50sitesrighttothecontour.Whatcouldbethemaximumlengthofthecontour?一條contour左邊有100個site，右邊有50個site，那么contour的最大長度是？A50B5000C150D100CM1、

單選題

Whatdothenumbersintheimagebelowindicate?對于下圖來說，每個標(biāo)號所指示的區(qū)域分別是？A、frozenarea,unfrozenarea,unscannedhalf-planeB、unfrozenarea,frozenarea,unscannedhalf-planeC、frozenarea,unfrozenarea,scannedhalf-planeD、unfrozenarea,frozenarea,scannedhalf-planeA2、

單選題Anypointi