文档介绍：四川大学期末考试试题（闭卷）
（2009-2010学年第2学期）
课程号：311036030课程名称：数据结构与算法（D卷）任课教师：孙界平杨秋辉张卫华
适用专业年级：软件工程2009级学号：姓名：
考试须知
四川大学学生参加由学rticularorder.
Whatstructureisusedbytopologicalsort()
ADG
GAD
DAG
AGD
评阅教师得分：一、判断题(本大题共5小题，每小题2分，共10分)提示：正确打T,错误打F,:将其结果填写在答题纸上。
Thespace/timetradeoffprinciplesaysthatonecanoftenachieveareductionintimeifoneiswillingtosacrificespaceorviceversa.()
Theupperboundforanalgorithmisthesameastheworstcaseforthatalgorithm.()
Array-basedlistsaregenerallymorespaceefficientthanlistedlistswhentheuserknowsinadvanceapproximatelyhowlargethelistwillbecome.()
Thenumberofemptysubtreesinanon-emptybinarytreeisonemorethanthenumberof
nodesinthetree.()
Forgraphrepresentation,adjacencymatrixismorespaceefficientthanadjacencylistbecausetheformerrequiresnooverheadforpointers.()
|…评］阅弟师*「得？分二三、名词解释题(本大题共3小题，每小题5分，共15分)。提示：解释每小题所；给名词的含义，若解释正确则给分，若解释错误则无分，若解释不准确或不全面，则酌情扣
分。
topologicalsort
simplepath
loadfactor
，评阅教师j得分！四、应用题(本大题共4小题，每小题5分，共20分)。提示：请给出准确答案，|j!如果有中间步骤，答案错误的情况下有步骤分。
BuildaMAXheapof
40,55,49,73,12,27,98,81,64,36
BuildaHuffmantreeof
A
B
C
D
E
F
G
H
I
J
2
3
7
11
15
19
23
31
43
86
AVLtreeofinputsequence
16,3,7,11,9,26,18,14,15
Usemathematicalinductiontoprovethatthenumberofleavesinanon-emptyfullK-arytreeis(K-1)n+1,wherenisthenumberofinternalnodes.
五、编程题（本大题共2小题，共25分）。提示：每小题给出了一个程序设计要求，请按照要求写出源程序代码，如果源程序代码中出现语法错误或逻辑错误，则酌情扣分。
Writearecur