



下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
(15Points)A.Canyougiveanexampleofaheapwithsevendistinctelementssuchthatapre-ordertraversaloftheheapyieldstheelementsinsortedorder?Ifnotwhy?
Answer:
1
2 5
3 467
B.Canyougiveanexampleofaheapwithsevendistinctelementssuchthatanin-ordertraversaloftheheapyieldstheelementsinsortedorder?Ifnotwhy?
Answer:
No.Inain-ordertraversalofatreerootedatnodev,theresultisv.leftChildren(maybeasub-tree),v,v.rightChildren(maybeasub-tree).Ifthetreeisaheap,becauseofHeap-OrderProperty,thereexistsomekey(s)inv.leftChildrengreaterthanthekeyofv,andthesituationisthesamewithv.rightChildren,sotheresultcannotbeinsortedorder.
C.Canyougiveanexampleofaheapwithsevendistinctelementssuchthatapost-ordertraversaloftheheapyieldstheelementsinsortedorder?Ifnotwhy?
Answer:
1
5 2
7 643
(15Points)ConsiderannbynmatrixMwhoseelementsare0’sand1’ssuchthatinanyrow,allthe1’scomebeforeany0’sinthatrow.AssumingAisalreadyinmemory,describeanalgorithmrunninginO(n)timeforfindingtherowofMthatcontainthemostof1’s.
Answer:
AlgorithmfindMaxRow()
i<-0
j<-0
maxCount<-0
maxRow<-0
whilei<n
whileM[i][j]=1
j<-j+1
if(j=n)
returni
ifj>maxCount
maxCount<-j
maxRow<-i
i<-i+1
returnmaxRow
(15Points)ConsiderthesamematrixMinquestion2.DescribeanalgorithmrunninginO(nlogn)forcountingthenumberof1’sinM.
Answer:
Algorithmcount()
i<-0
j<-0
s<-0
whilei<n
whileM[i][j]=1
j<-j+1
whileM[i][j-1]=0
j<-j-1
s<-s+j
returns
Notquite.Youshoulduseabinarysearchoneachrowtofindthelocationoftherightmost1.
(15Points)Wearegiventwon-elementsortedsequencesAandBthatshouldnotbeviewedassets(thatis,AandBmaycontainduplicateelements).DescribeanO(n)methodforcomputingasequencerepresentingthesetAUB(withnoduplicateelements).
Answer:
Assumethattheyaresortedinnon-decreasingorder.
Algorithmunion(A,B,S)
Input:sequenceAandBsortedinnon-decreasingorder,andenemptysequenceS
Output:S,AUB
S.insertLast(min{A.first().element(),B.first().element()})
while(not(A.isEmpty()orB.isEmpty()))
ifA.first().element()<=B.first().element()
ifS.last().element()=A.first().element()
A.remove(A.first())
else
S.insertLast(A.remove(A.first()))
else
ifS.last().element()=B.first().element()
B.remove(B.first())
else
S.insertLast(B.remove(B.first()))
while(notA.isEmpty())
ifS.last().element()=A.first().element()
A.remove(A.first())
else
S.insertLast(A.remove(A.first()))
while(notB.isEmpty())
ifS.last().element()=B.first().element()
B.remove(B.first())
else
S.insertLast(B.remove(B.first()))
(10Points)YouarebeinginterviewedtobehiredasacashierinaDollarStore.TheManagerasksyoutodevelopanefficientgreedyalgorithmformakingchangeforaspecifiedvalueundera$1usingaminimumnumberofcoinsofquarters,dimes,nickels,andpennies.Describeyouralgorithm.Youwillnotbehiredifyouralgorithmisnotgreedy!
Answer:
Algorithm
Input:x,theamountofmoneyintermsofcent
Output:Q,D,N,P------numberofeachunity
Q,D,N,P<-0
while(x>=25)
Q<-Q+1
x<-x-25
while(x>=10)
D<-D+1
x<-x-10
while(x>=5)
N<-N+1
x<-x-5
while(x>=1)
P<-P+1
x<-x-1
(15Points)Giventhestoryinquestion5,ifthedenominationswerenot$0.25,$0.10,$.05,and$0.01(butsomeotherdenominations),doyouthinkyourgreedyalgorithmstillworks?JustifyyouranswerwithsolidargumentsorexamplestobequalifiedforajobatUSTreasury.
Answer:
Yes,Ithinkso.
IftherearedenominationsofD0,D1,...,Dn,andthatD0<D1<...<Dn,D0mustbeafactorofx,namelyxmodD0=0.
SupposeweexpresstheamountofmoneyxinonlyD0,thentotalnumberisCount(D0)+Count(D1)+...+Count(Dn)=x/D0+0+...+0.
IfwetransfertheexpressionfromD0to(D0andDk)(k>0),thetotalnumberwilldecreasetox/Dk+y(y=(xmodDk)/D0).So,thefirstpartx/DkisdecreasingwithDkincreasing,whilethesecondpartyisasub-problemoftheoriginalproblemandwecansolveitwiththesameprinciple.
No,thisisincorrect.Imagineyouhadcoinswithdenominations1c,9c,10candhadtomakechangefor18c,thenthegreedyalgorithmwouldmakechangewitha10cand81ccoins,whilethebestsolutionis29ccoins.
(15Points)Designadivide-and-conqueralgorithmforfindingtheminimumandmaximumelementsofnnumbersusingnomorethan3n/2comparisons.
Answer:
pickarandomelementTargetrandomlyfromtheset
dividetheremainingelementsintotwosets
G:elementsthatgreaterthanTarget
S:elementsthatsmallerthanTarget
(throwawayelementsthatequaltoTarget)
ifGisNULL
Targetisthemaximumelement
ifSisNULL
Targetistheminimumelement
ifGisnotNULL
recursivelydo
pickarandomelementTargetfromtheremainingelements
throwawayelementsthatsmallerthanorequaltoTarget
isSisnotNULL
recursivelydo
pickarandomelementTargetfromtheremainingelements
throwawayelementsthatgreaterthanorequaltoTarget
Fromthesolutions,
Dividethesetofnnumbersn/2groupsoftwoele
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 智慧教育平台下的教学模式创新
- 智慧城市大数据管理与隐私保护的未来趋势
- 教育资源优化配置在中医教学中的实践研究
- 全球化背景下的教育创新课程设计
- 营养膳食培训课件
- 智慧教育中的数字资源均衡分配方案
- 教育大数据库的构建与个性化学习方案设计实践
- 中国南方航空接送机理论培训
- 抖音商户达人合作流程标准化制度
- 抖音商户编导短视频传播潜力评估制度
- 门诊就诊高峰期应急预案7篇,门诊患者高峰期应急预案
- 2023年江苏南京江北新区第二批招考聘用编制内教师100人笔试题库含答案解析
- 保修管理控制程序
- 《“将军饮马”问题》说课稿
- 2023年邵阳市大祥区体育教师招聘笔试题库及答案
- GB/T 9117-2010带颈承插焊钢制管法兰
- GB/T 12513-2006镶玻璃构件耐火试验方法
- 食品营养与健康-18中国居民平衡膳食宝塔
- 胰岛素注射篇课件
- 浅谈今天怎样当好校长课件
- 人教版七年级上下册英语单词表-含音标
评论
0/150
提交评论