南京师范大学2004年春季学期.DOC

1南京师范大学 2004 年春季学期数据结构课程期末考试试卷2004 年 6 月 27 日， （时间）命题人：院系 学号 姓名 成绩一、填空。 （每题 2 分，共计 20 分）1算法的健壮性是指 。2对一个线性表分别进行遍历和逆置运算，其最好的时间复杂度分别为 和 。3n 个数入栈，所有可能的出栈序列共有 种。4下面程序段的时间复杂度为 （n1） 。sum=1;for(i=0; sum=x ) j-；while (i0;-i）HeapAdjust（a,i,n ）;for（i= ; i1;-i）t=a1;a1=ai;ai=t;（2）上面程序建成的堆是大顶堆还是小顶堆？（2 分）（3）对 n 个元素进行初始建堆的过程中，最多进行 次数据比较。 （2 分）（4）堆排序稳定吗？请举例说明。 （3 分）