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

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

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

2Whichofthefollowingisnotagoodprooftechnique.
a)proofbycontradiction.
*b)proofbyexample.
c)proofbymathematicalinduction.

3.Whenwewishtodescribetheupperboundforaproblemweuse:
*a)Theupperboundofthebestalgorithmweknow.
b)Thelowerboundofthebestalgorithmweknow.
c)Wecan'ttalkabouttheupperboundofaproblembecausetherecanalwaysbeanarbitrarilyslowalgorithm.

4.Thebestcaseforanalgorithmrefersto:
a)Thesmallestpossibleinputsize.
*b)Thespecificinputinstanceofagivensizethatgivesthelowestcost.
c)Thelargestpossibleinputsizethatmeetstherequiredgrowthrate.
d)Thespecificinputinstanceofagivensizethatgivesthegreatestcost.

5.Inthelinked-listimplementationpresentedinthebook,aheadernodeisused:
*a)Tosimplifyspecialcases.
b)Becausetheinsertanddeleteroutineswon'tworkcorrectlywithoutit.
c)Becausetherewouldbenootherwaytomakethecurrentpointerindicatethefirstelementonthelist.

6.Recursionisgenerallyimplementedusing
a)Asortedlist.
*b)Astack.
c)Aqueue.

7.Therelationshipbetweenafullandacompletebinarytreeis:
a)Everycompletebinarytreeisfull.
b)Everyfullbinarytreeiscompl