数据结构与算法分析 复习试卷a2

《数据结构与算法分析 复习试卷a2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程名称：任课教师：学号：姓名：四川大学期末考试试题（闭卷）（2009~2010学年第1学期）课程号：311036030课程名称：数据结构与算法分析（A卷）任课教师：孙界平，张卫华适用专业年级：软件工程2008级学号：姓名：考试须知四川大学学生参加由学校组织或由学校承办的各级各类考试，必须严格执行《四川大学考试工作管理办法》和《四川大学考场规则》。有考试违纪作弊行为的，一律按照《四川大学学生考试违纪作弊处罚条例》进行处理。四川大学各级各类考试的监考人员，必须严格执行《四川大学考试工作管理办法》、

2、《四川大学考场规则》和《四川大学监考人员职责》。有违反学校有关规定的，严格按照《四川大学教学事故认定及处理办法》进行处理。题号一(40%)二(8%)三(42%)四(10%)卷面成绩得分阅卷时间注意事项：1.请务必将本人所在学院、姓名、学号、任课教师姓名等信息准确填写在试题纸和添卷纸上；2.请将答案全部填写在本试题纸上；3.考试结束，请将试题纸、添卷纸和草稿纸一并交给监考老师。eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee评阅教师得分一、单项选择题（

3、本大题共20小题，每小题2分，共40分）提示：在每小题列出的备选项中只有一个是符合题目要求的，请将其代码写到答题纸上。错选、多选或未选均无分。1.Asolutionisefficientifa)itsolvesaproblemwithintherequireresourceconstraints.b)itsolvesaproblemwithinhumanreactiontime.c)itsolvesaproblemfasterthanotherknownsolutions.d)aandb.*e)

4、aandc.f)bandc.2.IfRisabinaryrelationoversetS,thenRistransitiveifa)aRaforallainS.b)wheneveraRb,thenbRa,foralla,binS.c)wheneveraRbandbRa,thena=b,foralla,binS.*d)wheneveraRbandaRc,thenaRc,foralla,b,cinS.3.Whenperformingasymptoticanalysis,wecanignorecons

5、tantsandlowordertermsbecause:*a)Wearemeasuringthegrowthrateastheinputsizegetslarge.b)Weareonlyinterestedinsmallinputsizes.c)Wearestudyingtheworstcasebehavior.d)Weonlyneedanapproximation.4.Foralistoflengthn,thelinked-listimplementation'sprevfunctionre

6、quiresworst-casetime:a)O(1).注：字迹务必清晰，书写工整。本题共7页，本页为第7页教务处试题编号：课程名称：任课教师：学号：姓名：b)O(logn).*c)O(n).d)O(n^2).5.Findingtheelementinanarray-basedlistwithagivenkeyvaluerequiresworstcasetime:a)O(1).b)O(logn).*c)O(n).d)O(n^2).6.Alloperationsonastackcanbeimple

7、mentedinconstanttimeexcept:a)Pushb)Popc)Theimplementor'schoiceofpushorpop(theycannotbothbeimplementedinconstanttime).*d)Noneoftheabove.7.TheFullBinaryTreeTheoremstatesthat:*a)Thenumberofleavesinanon-emptyfullbinarytreeisonemorethanthenumberofinternal

8、nodes.b)Thenumberofleavesinanon-emptyfullbinarytreeisonelessthanthenumberofinternalnodes.c)Thenumberofleavesinanon-emptyfullbinarytreeisonehalfofthenumberofinternalnodes.d)Thenumberofinternalnodesinanon-emptyfullbinarytreeisonehalfofthenumberofleaves