数据结构与算法分析 复习试卷A2.doc

课程名称： 任课教师： 学号： 姓名：
注：字迹务必清晰，书写工整。 本题共NUMPAGES7页，本页为第页
教务处试题编号：
注：字迹务必清晰，书写工整。 本题共NUMPAGES7页，本页为第页
出题: 编辑: 系所审核: 学院审核: 教务处试题编号：
四川大学期末考试试题（闭卷）
（2009~2010学年第1学期）
课程号：311036030课程名称：数据结构与算法分析（A卷） 任课教师： 孙界平，张卫华
适用专业年级：软件工程2008级 学号： 姓名：
考试须知
四川大学学生参加由学校组织或由学校承办的各级各类考试，必须严格执行《四川大学考试工作管理办法》和《四川大学考场规则》。有考试违纪作弊行为的，一律按照《四川大学学生考试违纪作弊处罚条例》进行处理。
四川大学各级各类考试的监考人员，必须严格执行《四川大学考试工作管理办法》、《四川大学考场规则》和《四川大学监考人员职责》。有违反学校有关规定的，严格按照《四川大学教学事故认定及处理办法》进行处理。题号一(40%)二(8%)三(42%)四(10%)卷面成绩得分阅卷时间注意事项：1.请务必将本人所在学院、姓名、学号、任课教师姓名等信息准确填写在试题纸和添卷纸上；
2.请将答案全部填写在本试题纸上；
3.考试结束，请将试题纸、添卷纸和草稿纸一并交给监考老师。

评阅教师
得分

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

2.IfRisabinaryrelationoversetS,thenRistransitiveif
a)aRaforallainS.
b)wheneveraRb,thenbRa,foralla,binS.
c)wheneveraRbandbRa,thena=b,foralla,binS.
*d)wheneveraRbandaRc,thenaRc,foralla,b,cinS.

3.Whenperformingasymptoticanalysis,wecanignoreconstantsandlowordertermsbecause:
*a)Wearemeasuringthegrowthrateastheinputsizegetslarge.
b)Weareonlyinterestedinsmallinputsizes.
c)Wearestudyingtheworstcasebehavior.
d)Weonlyneedanapproximation.

4.Foralistoflengthn,thelinked-listimplementation'sprevfunctionrequiresworst-casetime:
a)O(1).
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.Alloperationsonastackcanbeimplementedinconstanttimeexcept:
a)Push
b)Pop
c)Theimplementor'schoiceofpushorpop(theycannotbothbeimplementedinconstanttime).
*d)Noneoftheabove.

7.TheFullBinaryTreeTheoremstatesthat:
*a)Thenumberofleavesinanon-emptyfullbinarytreeisonemorethanthenumberofinternalnodes.
b)Thenumberofleavesinanon-emptyfullbinarytreeisonelessthanthenumberofinternalnodes.
c)Thenumberof