雨课堂在线学堂《计算几何》作业单元考核答案

00.Introduction1/1单选题(1分)Whichofthefollowingisthekeyproblemthiscourseputanemphasison?(以下哪个话题是我们这门计算几何课程中，重点关注的话题？)Thecontinuityofcurvesandsurfaces(曲线和曲面的连续性问题)Thedivisionofgeometricproblemsinalgorithmdesignandanalysis(算法中关于几何问题的分支)Digitalimageprocessingandrecognition(数字图像的处理与识别)答案：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?现在有一种颜色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?现在有三种颜色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?对于下图表示的点集来说，如果我们采用增量式策略构造凸包，并按照标号依次将新的点加入，那么凸包上的点的个数变化过程是？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问题。与凸多边形不同，一般多边形可能是凹的，甚至可能是带有孔洞的。对于一般多边形内部区域中的一点，我们在外部随机找一点并随意地用一根曲线连接它们，你会发现Thecurvepassesthroughtheboundaryofthepolygononce(曲线经过多边形边界1次)Thecurvepassesthroughtheboundaryofthepolygonforoddtimes(曲线经过多边形边界奇数次)Thecurvepassesthroughtheboundaryofthepolygonforseveraltimeswithnorules(曲线经过多边形边界次数没有规律)Thecurvepassesthroughtheboundaryofthepolygonforeventimes(曲线经过多边形边界偶数次)答案：B3/4单选题(1分)Okaynow.Let'sthinkaboutthespecialcasebasedonthelastproblem.Forarandomgeneralpolygon,howdoyouknowwhetherthepointisinsidethepolygon?WhatisthemethodforIn-PolygonTest?好的，在上一题的基础之上，我们将条件从一般的情况反推到特殊的情况。对于任意的一般多边形，判断某一点是不是在这个多边形内部，也就是In-PolygonTest的办法是？Drawarayfromthepointandcheckiftherayintersectswiththeboundaryofthepolygontwice(从该点射出一条射线，如果射线与多边形边界交点为2个，则为内部)Drawarayfromthepointandcheckiftherayintersectswiththeboundaryofthepolygonforeventimes(从该点射出一条射线，如果射线与多边形边界交点个数为偶数，则为内部)Drawarayfromthepointandcheckiftherayintersectswiththeboundaryofthepolygonforoddtimes(从该点射出一条射线，如果射线与多边形边界交点个数为奇数，则为内部)Drawasegmentpassingthroughthepointandcheckifthesegmentintersectswiththeboundaryofthepolygonforoddtimes(经过该点画一条线段，如果直线与多边形边界交点个数为奇数，则为内部)答案：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序列的长度来实现排序)答案：B2/4单选题(1分)Astheimagebelowshows,theveryfirststepofJarvisMarchalgorithmisfindinganextremepointasthestartpoint.Ifweprojectallthepointsontheplanetoalineandmakea2Dto1Dmapping,wewillfindthat如下图所述，JarvisMarch算法的第一步，是确定一个开始的极点。如果我们将平面上的点都投影到一条直线上，做一个二维到一维的映射的话，我们会发现Allextremepointswillbeprojectedtoonepointontheline(极点总是被投影到直线上的一个点)Allextremepointswillbeprojectedtoeithermaximalorminimalpointontheline(极点总是被投影到直线上的最大值或者最小值)Themaximalorminimalpointonthelineismappedwiththeextremepoints(直线上的最大值或最小值总是对应着极点)Themaximalorminimalpointonthelineismappedwiththenon-extremepoints(直线上的最大值或最小值总是对应着非极点)答案：C3/4单选题(1分)Inthelastepisode,wetalkedaboutsortingusingthecomparatorofTo-LeftTest.Forpointsintheimagebelow,what'sthecorrectorder?(Sortthesepointsbycounter-clockawiseincreasinganglewithrespecttoredpoint)上一节中所讲的利用To-Left测试来作为一个比较器进行排序的方法，我们通常称为极角排序。对于如下的点来说，极角排序的结果是？（以红色点作为极角排序的中心，从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为了让你对输出敏感算法有更深的认识，我们来看这样一个简单的算法。这是一个利用减法实现除法的算法，如下图伪代码所示。该算法的时间复杂度是O(N)O(D)O(R)O(Q)答案：D1/3单选题(1分)IfA≤NBforalgorithmsAandB,whichofthefollowingiscorrect?当有两个算法A和B，其中A≤NB的时候，下列哪个说法是正确的？InputofAcanbeconvertedtoinputofBinlineartime(算法A的输入可以在线性时间内转换为算法B的输入)InputofAcanbeconvertedtooutputofBinlineartime(算法A的输入可以在线性时间内转换为算法B的输出)OutputofAcanbeconvertedtoinputofBinlineartime(算法A的输出可以在线性时间内转换为算法B的输入)OutputofAcanbeconvertedtooutputofBinlineartime(算法A的输出可以在线性时间内转换为算法B的输出)答案：A2/3单选题(1分)Whichofthefollowingiswrongaccordingtothelastepisode?上面提到的曹冲称象作为归约思想的类比，下列哪个说法是错误的？CaoChonggettheweightoftheelephantusingtheweightoftherocksbasedonreduction(利用归约思想，曹冲利用石头的重量去估算出大象的重量)theweightofelephant≤NTheweightofrocks(大象的重量≤N石头的重量)ReductionrelationshipheremeanstheboatandthewaterusedinCaoChong'smethod(这里的归约关系是指曹冲称象时的船和水)Iftwoobjectswiththesameweighthasdifferentmarks,thenreductionrelationshipherebreaks(如果两个物体重量相同但吃水的刻度不同，则归约关系就被破坏了)答案：B3/3单选题(1分)Afterlearningthereductionrelationshipbetween2d-CHandSorting,whichofthefollowingiswrong?学习了排序与二维凸包算法的归约关系以后，下列哪个说法是错误的？Anyarraytobesortedcanbemappedtothepointssetonthe2d-planeinlineartime(任何一个待排序的数组，都可以线性时间映射为二维平面上的点集)Anyconvexhullonthe2d-planecanbemappedtoasortedarrayinlineartime(任何一个二维平面上的凸包，都可以线性时间映射为一个有序数组)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算法当中，栈是作为一个很重要的数据结构存在的。现在假设有一个空栈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算法当中，算法结束是以T栈为空作为标志的，那么为什么S栈不会先于T栈变空呢？AllelementsofstackTgointothestackS(T栈中的元素都进入了S栈)ThesizeofstackSisalwayslargerthanthesizeofstackT(S栈中元素个数总是多于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?如下图所示，当发生backtrack的时候，为什么最多也不会越过2号点？Becausethealgorithmmakesadeterminationbeforebacktrackingthepoint2(因为算法在backtrack到2号点之前加了判断)Becausethepoint2isanextremepoint(因为2号点是极点)Becausethepointsbeforethepoint2can'tbepopped(因为2号点前面的点也不会被pop出去)Becausethepoint3stillstandsinfrontofthepoint2(因为2号点前面还有3号点)答案：B2/2单选题(1分)Ifwedon'tapplypresorting,whatistheresultoftheGrahamScanforthisChinesecharacterfrombottomtotop?如果不做Presorting的话，下面这个字从下到上顺序进行GrahamScan，最后会产生的结果是？Becauseeverycaseisanright-turn,eachpointwillbeontheconvexhull(由于每个点都是右拐的情况，所以所有的点都在凸包上)NopointswillstayinstackT(没有点在T栈上)Acorrectconvexhullwillbeconstructed(会得到一个正确的凸包)NopointswillstayinstackS(没有点在S栈上)答案：B1/3单选题(1分)Forasimplepolyhedron,itssizeofverticesis10anditssizeoffacesis5.Howmanyedgesdoesitown?对于一个简单多面体来说，如果其顶点个数为10，面数为5，那么它包含多少条棱呢？13142324答案：A2/3单选题(1分)HowmanystepswillthescanningtakeifdoingGrahamScantonpoints?(Nodegenerationsituation)对n个点进行GrahamScan，其中scan的过程中最多会迭代多少步？（不考虑退化情况）2n-62n-52n-72n-8答案：B3/3单选题(1分)Ifwehaveasetofpointswhicharealreadysortedaccordingtoxcoordinates,sowhat'sthetimecomplexityofthealgorithmofUpper/LowerHull?前面介绍的Upper/LowerHull算法，如果输入的平面上的点已经是x方向上有序的话，那么该算法执行的时间复杂度是？O(1)O(n2)O(n)O(nlgn)答案：C1/4单选题(1分)WhatiswrongabouttheanalogybetweenconvexhullusingDACandmergesort?关于利用分治思想构建凸包算法和归并排序算法的类比，错误的是Theresultingconvexhullisinanalogywiththesortedarray(最终的凸包结果类比于排好序的数组)Thedivisionofthepointsetisinanalogywiththedivisionofthearray(将平面上的点集进行划分类比于对数组进行划分)Combiningtwosubconvexhullstoonesubconvexhullisinanalogywithmergingtwosortedsubsequenceintoonesortedsubsequence(将两个子凸包合并为一个子凸包类比于两个排好序的子序列归并为一个排好序的子序列)Thesizeoftheextremepointsonconvexhullisinanalogywiththesizeofsortedarray(凸包上极点的个数类比于数组的大小)答案：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)?下列选项中对于寻找左凸包（规模为n）的最右侧顶点和右凸包（规模为m）的最左侧顶点这个操作来说，错误的是？TheoperationwilltakeO(m+n)timeifwedon'trecordanyinformation(如果不记录任何信息的话，这个操作需要消耗O(m+n)时间)ItwilltakeO(1)timetocompletetheoperationifwerecordedtheleft-mostpointofeachsubconvexhull(只要每次记录子凸包的最左顶点就可以在O(1)时间完成这个操作)Theleft-mostpointoftheleftconvexhullwillbecometheleft-mostpointofthecombinedconvexhull(左侧子凸包的最左顶点将会成为合并后凸包的最左顶点)Theright-mostpointoftherightconvexhullwillbecometheright-mostpointofthecombinedconvexhull(右侧子凸包的最右顶点将会成为合并后凸包的最右顶点)答案：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?下列哪个问题包含了几何求交问题中的“计数”问题？Stopplayersfrompassingthroughwallsingamedevelopment(游戏开发中防止角色穿过墙壁)Construct3Dmodelswithbooleanoperationofsimplepolyhedrons(利用简单几何体进行布尔运算创建复杂三维模型)Getthenumberofintersectionsofsegmentsontheplane(判断平面上线段的交点个数)Raytracingmethodforphotorealisticrendering(光线追踪算法进行真实感渲染)答案：C1/2单选题(1分)Thereisanarrayof1001elementswhichrangefrom1to1000.Onlyoneelementisrepeatedinthearraywhiletheothersexistonlyonceinthearray.Whichofthefollowingalgorithmsisthefastest?1-1000放在含有1001个元素的正整数数组中，只有唯一的一个元素值重复，其它均只出现一次。下列哪种算法查找这个重复元素最快？Enumeratealltheparisinthearray,findthepairwithsamevalues(枚举1001个元素中所有的正整数对，找到值相同的那一对)XORallthenumbersinthearraytogether,thenXORnumberfrom1to1000(现将数组中所有数异或在一起，再与1-1000各异或一次)Sortthearrayandthenmakesequentialsearch(将数组进行排序，再线性搜索)Sortthearrayandthenmakebinarysearch(将数组进行排序，再二分搜索)答案：B2/2单选题(1分)Ifwedivide3,5,2,7,10,13intodifferentbucketsusingthemethodmentioned,what'stheresult?使用上述的Max-Gap分桶算法对下列数3,5,2,7,10,13进行分桶的话，结果是？(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个区间(1,3),(4,10),(5,6),(0,2)运用上述算法进行相交检测时，待检测的模式序列是？LLLRRRLRLRLRLLRRLLRRLRLRLLRRLLRR答案：D1/1单选题(1分)What'swrongaboutthereductionbetweenEUandSID?下列关于EU问题和SID问题的归约，错误的是？EU≦NSIDAccordingtoreduction,wecanfoundthelowerboundofSID(通过进行归约，我们可以找到SID问题的下界)TheinputofSIDcanbeconvertedtotheinputofSIDinlineartime(SID问题的输入可以在线性时间内转化为EU问题的输入)TheoutputofSIDcanbeconvertedtotheoutputofEUinlineartime(SID问题的输出可以在线性时间内转化为EU问题的输出)答案：C1/2多选题(2分)Whichofthefollowingcanimplementpriorityqueue?(Multiplechoice)下列哪些数据结构通常作为优先队列的实现？（多项选择）Hashtable(哈希表)BinaryHeap(二叉堆)FibonacciHeap(Fibonacci堆)Stack(栈)答案：BC2/2单选题(1分)Thereareseveralsegmentsontheplane.Nowweputasweeplineontheplanerandomly.IfwemarkthesetofsegmentsstayinglefttothesweeplineasL,thesetofsegmentsstayingrighttothesweeplineasRandthesetofsegmentscrossedbysweeplineasM.Whichofthefollowingconclusionsiswrong?平面上若干条线段，随机放置一条扫描线。我们设完全在扫描线左侧的线段集为L；完全在扫描线右端的线段集为R；被扫描线穿过的线段集为M。那么下面哪个结论是错误的？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?如下图所示，扫描线已经行进至当前橙色虚线表示的位置，那么此时此刻，事件队列当中的事件是如何排列的？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?下列哪些线段排列模式的交点个数是O(n2)量级的？答案：AD1/2单选题(1分)Astheimagebelowshows,whichofthefollowingpairsofmonotonechainsiscorrectifwedividetheconvexpolygonhorizontally?如下图所示，将该凸多边形水平方向上分解为两条单调链，下列哪种分法是正确的？(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分别是两条单调链的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?为什么说，使用扫描线方法对两个凸多边形求交时，扫描线状态结构只要用固定长度的数组来表示就可以了？Becauseanyconvexpolygonwillhavenomorethan4intersectionpointswiththesweepline.(因为任意凸多边形与扫描线最多交于4个交点上)Becauseanypolygonwillhavenomorethan2intersectionpointswiththesweepline.(因为任意多边形与扫描线最多交于2个交点上)Becauseanyconvexpolygonwillhavenomorethan2intersectionpointswiththesweepline.(因为任意凸多边形与扫描线最多交于2个交点上)Becauseanyconvexpolygonwillhavenomorethan1intersectionpointswiththesweepline.(因为任意凸多边形与扫描线最多交于1个交点上)答案：C1/1单选题(1分)WhatiswrongaboutthereductionbetweenHICandSorting?下列关于HIC问题和Sorting问题的归约，不正确的是？TheinputofHICcanbeconvertedtotheinputofSortinginlineartime(HIC问题的输入可以在线性时间内转化为Sorting问题的输入)TheoutputofHICcanbeconvertedtotheoutputofSortinginlineartime(HIC问题的输出可以在线性时间内转化为Sorting问题的输出)Sorting≦NHICAccordingtoreduction,wecangetthelowerboundsofHIC(利用归约，我们可以确定HIC问题的下界)答案：A03.Triangulation1/1多选题(2分)Whatstatementsarerightaboutinteriordiagonal?内对角线具有的属性是？（多项选择）Connectedgesofthepolygon(连接多边形的边)Connectverticesofthepolygon(连接多边形的顶点)Doesnotcrossedgesofthepolygon(不穿过多边形的边)Crossedgesofthepolygon(穿过多边形的边)答案：BC1/2单选题(1分)Astheimagebelowshows,whichyellowareaisthecorrectvisibilitypolygonforguardX?如下图所示，下列哪种黄色区域是正确的哨兵X的可视范围。答案：A2/2单选题(1分)Ifthereexistsapolyhedronwithcameraslocatedineachvertex,someinnerareaofthepolyhedronstillcan'tbeviewed.Itmeansthat我们说三维空间中的一个多面体，如果多面体每个顶点放置一个摄像头，仍然无法覆盖所有内部区域，其实是说？Therearefewverticesofthepolygon(意味着这个多面体的顶点数很少)Therearealotofverticesofthepolygon(意味着这个多面体的顶点数很多)Thereisapointinsidethepolyhedronwhichconnecteachvertexcrossingthefacesofthepolyhedron(意味着多面体内存在一个点，与所有顶点连线皆穿过多边形的面)Thereisapointinsidethepolyhedronwhichconnectsomevertexcrossingthefacesofthepolyhedron(意味着多面体内存在一个点，并存在与之相连会穿过多边形的面的顶点)答案：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.我们来复习一下鸽巢原理。我们首先假定常人的头发数在15万左右，而北京的人口大于100万，那么北京至少有两个人的头发一样多。Correct(正确)Wrong(错误)答案：A2/2单选题(1分)Astheimagesbelowshow,whichdualgraphofthetriangulationiscorrect?如下图所示，对于这样的多边形三角剖分，哪个对偶图才是正确的？答案：A1/1单选题(1分)Whichiswrongaboutorthogonalpolyonswithnedges?下列哪个关于n边正交多边形的论述是错误的？Orthogonalpolygonsarepolygonswithverticalorhorizontaledges(正交多边形是指边要么水平要么垂直的多边形)Orthogonalpolygon'sanglesummustbetimesof90°(正交多边形的内角和一定是90°的倍数)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?下列哪个多边形并不是单调多边形？答案：B1/2单选题(1分)Whichofthefollowingisnotthecorrectwayofdecomposesimplepolygonintomonotonepolygons?下列哪种不是正确地将简单多边形剖分成单调多边形的做法？答案：C2/2单选题(1分)Beforeyouenterthenextunit,pleasereviewthealgorithm.Whatisthetimecomplexityformonotonedecomposition?在进入下一小节的算法分析部分前，请你回忆一下整个算法。对多边形进行单调多边形分解所消耗的时间是O(n)O(nlogn)O(logn)O(n2)答案：B1/2单选题(1分)Ifwetetrahedralizearegulartriangularprism,howmanywaysoftetrahedralizationarelegal?(Eachvertexisdifferent)对一个正三菱柱进行四面体剖分，有多少种剖分方案？（考虑每个顶点都是不同的）5678答案：B2/2多选题(2分)Whichofthefollowingarecorrect?(Multiplechoices)以下哪些选项是正确的？（多项选择）Apolyhedroncanbetetrahedralizedinmultipleways,buteachwayhasthesamenumberoftetrahedrons(同一个多面体可能有多种四面体剖分方法，但是每个方法剖分出的四面体数量相等)NotallpolyhedronscanbetetrahedralizedwithoutSteinerpoints(不是所有多面体都可以不引入Steinerpoints进行四面体剖分)Apolyhedroncanbetetrahedralizedintodiferentnumberoftetrahedrons(同一个多面体可能剖分出不同数量的四面体)WiththehelpofSteinerpoints,somepolyhedronscan'tstillbetetrahedralized(即使引入Steinerpoints，有的多面体仍然不能进行四面体剖分)答案：BC04.VoronoiDiagram1/1单选题(1分)Whichstatementiscorrectaccordingtotheexampleofgrasslandfire?刚刚提到的点火的这个例子中，下列哪个论述是正确的？Theresultwillbenotaffectedifweigniteatdifferentsitesatdifferenttime(不同时点火不会影响最后结果)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内部)答案：A2/2单选题(1分)Whatisthenumberofverticeswithadegreeof4inaVoronoiDiagram?Voronoi图中度为4的顶点的数量等于Thenumberofsites/3(site的数量除以3)Thenumberofsites/4(site的数量除以4)Thenumberofcircleswhichcross4concylicsites(四个site共圆的圆数量)Thenumberofemptycircleswhichcross4concylicsites(四个site共圆的空圆数量)答案：D1/1单选题(1分)IfweconverttheVoronoidiagrambelowtotheplanargraph,howmanyfaces,edgesandnodesarethere?下列这个Voronoi图如果转换成平面图的话，有多少个面，多少个边，多少个节点？585584587486答案：A1/1多选题(2分)Whichofthefollowingareplanargraphs?(Multiple