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

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

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

2.ForsetP,thenotation|P|indicates
*a)ThenumberofelementsinP.
b)TheinverseofP.
c)ThepowersetofP.
d)Noneoftheabove.

3.Pickthegrowthratethatcorrespondstothemostefficientalgorithmwhenn=4.
a)5n
b)20logn
c)2n^2
*d)2^n

4.Whentheupperandlowerboundsforanalgorithmarethesame,weuse:
a)big-Ohnotation.
b)big-Omeganotation.
*c)Thetanotation.
d)asymptoticanalysis.
e)Averagecaseanalysis.
f)Worstcaseanalysis.

5.Ascomparedtothelinkedlistimplementationforlists,thearray-basedlistimplementationrequires:
a)Morespace
b)Lessspace
*c)Moreorlessspacedependingonhowmanyelementsareinthelist.

6.Whencomparingthedoublyandsinglylinkedlistimplementations,wefindthatthedoublylinkedlistimplementation
*a)Savestimeonsomeoperationsattheexpenseofadditionalspace.
b)Savesneithertimenorspace,butiseasiertoimplement.
c)Savesneithertimenorspace,andisalsohardertoimplement.
7.ThecorrecttraversaltouseonaBSTtovisitthenodesinsortedorderis:
a)Preordertraversal.
*b)Inordertraversal.
c)Postordertraversal.

8.Wheneverynodeofafullbinarytreestoresa4-bytedatafield,two4-bytechildpointers,anda4-byteparentpointer,theoverheadfractionisapproximately:
a)onequarter.
b)one