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

二路插入排序是将待排关键字序列r[n]中关键字分二路分别按序插入到辅助向量d[n]前半部和后半部(注:向量d可视为循环表)其原则为先将r[l]赋给d[]再从r[] 记录开始分二路插入编写实现二路插入排序算法【北京工业大学 八 (分)】

． 叙述基数排序算法并对下列整数序列图示其基数排序的全过程()【南京航空航天大学 一 】

．输入N个只含一位数字的整数试用基数排序的方法对这N个数排序【中国人民大学 三(分)】

．设记录R[i]的关键字为R[i]KEY(<=i<=k)树结点T[i](<=i<=K)指向败者记录T[]为全胜记录下标写一算法产生对应上述R[i](<=i<= k)的败者树要求除R[k]和T[k]以外只用O()辅助空间【东南大学 九 (分)】

．设有顺序放置的n个桶每个桶中装有一粒砾石每粒砾石的颜色是红白蓝之一要求重新安排这些砾石使得所有红色砾石在前所有白色砾石居中所有蓝色砾石居后重新安排时对每粒砾石的颜色只能看一次并且只允许交换操作来调整砾石的位置【上海大学 二 (分)】

数据结构DEAP的定义如下DEAP是一棵完全二叉树它或者是一棵空树或者满足下列特性

()树根不包含元素．()其左子树是一小堆(MINHEAP)其右子树是一大堆(MAXHEAP)

()若右子树非空设ｉ是左子树的任一结点ｊ是右子树中与ｉ相应的结点．若这样的ｊ结点不存在则取ｊ为右子树中与ｉ的父结点相应的结点;结点ｉ的关键字总是小于或等于结点ｊ的关键字值

一个DEAP的例子如图所示

与结点相对应的结点为与结点对应的结点为

给出在该DEAP中插入结点后的结果

写出在DEAP中插入新结点的算法

用C或PASCAL语言编写实现上述算法的程序(分)【浙江大学 (分)】

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