数据结构考研分类复习真题 第十章 排序[50]

．解答问题

()(分)设某文件中待排序记录的排序码为试画图表示出树形选择排序(增序)过程的前三步

()(分) 试说明树形选择排序的基本思想

()(分) 树形选择排序与直接选择排序相比较优缺点是什么？

()(分) 堆排序是如何改进树形排序方法的？优点是什么？【山东大学 五(分)】 【山东工业大学 五 (分)】

若有N个元素已构成一个小根堆 那么如果增加一个元素为Kn+请用文字简要说明你如何在logn 的时间内将其重新调整为一个堆?【中科院计算所 三 (分)】

．填空并回答相关问题

()下面是将任意序列调整为最大堆(MAX HEAP)的算法请将空白部分填上

将任意序列调整为最大堆通过不断调用adjust函数即FOR(i=n/;i >;i )adjust(listin);其中list为待调整序列所在数组(从下标开始)n为序列元素个数adjust函数为

void adjust(int list[]int rootint n)

/*将以root为下标的对应元素作为待调整堆的根待调整元素放在list数组中最大元素下标为n*/

{int childrootkey;

rootkey=list[root];

child=*root;

while(child<=n)

{if((child<n)&&(list[child]<list[child+]))

()_______;

if(rootkey>list[child])

break;

else{List[()_______]=list[child];

child*=;

}

}

list[child/]=rootkey;

}

()．判断下列序列能否构成最大堆();若不能按上述算法将其调整为堆调整后的结果为( )【浙江大学 七 (分)】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []