散列表H∏0.12],散列函数与再散列函数为 Ho( key )=key mod 13: Hi=(Hi-1+ rEv(key+1)mod 11+ 1) mod 13; 插入关键码序列为{2,8,31,20,19,18,53,27} H(2)=2,比较次数为1Ho(8)=8,比较次数为1 H0(31)=5,比较次数为1H(20)=7,比较次数为1 H(19)=6,比较次数为1 H(18)=5,沖突,H=9,比较次数为2 H(53)=1,比较次数为1 H(27)=1,冲突,H=7,冲突,H=0,比较次数为3 插入8个关键码后的散列表 2□ 四、综合算法题 (1)数据表定义 【解答】 const int DefaulISize= 100; template <class Type> class datalist ∥.据表的前视声明 template <class Type> class Element t ∥数据表元素类的定义 private Type key; ∥关键码 field otherdata ∥其它数据成员 p Type getKey(i return key;) ∥取当前结点的关键码 void setKey( const Type x){key=x;}/将当前结点的关键码修改为x template <class Type> class datalist i 用顺序表来存储待排序的元素,这些元素的类型是Type public: datalist( int MaxS== DefaulISize): MaxSize( Maxse ) Current Size(0) f Vector=new Element <Type>[MaxS=); 1 rivate Element<Type>*vector; ∥存储待排序元素的向量 int Max size currentSize ∥最大元素个数与当前元素个数 (2)计数排序的算法 【解答1】 template <class Type> void countsort( datalist<Type>& initList, datalisT<Type>& resuItlist )& i,j, c; Type refer for (i=0; i< initList. CurrentSize; i++)i refer: = initList Vector[]. getKey (i for(j=0; j< initList Current Size; j++)5 散列表 HT[0..12]，散列函数与再散列函数为 H0( key ) = key mod 13； Hi = ( Hi-1 + REV ( key + 1 ) mod 11 + 1 ) mod 13; 插入关键码序列为 { 2, 8, 31, 20, 19, 18, 53, 27 } H0( 2 ) = 2, 比较次数为 1 H0( 8 ) = 8, 比较次数为 1 H0( 31 ) = 5, 比较次数为 1 H0( 20 ) = 7, 比较次数为 1 H0( 19 ) = 6, 比较次数为 1 H0( 18 ) = 5, 冲突，H1 = 9，比较次数为 2 H0( 53 ) = 1，比较次数为 1 H0( 27 ) = 1，冲突，H1 = 7，冲突，H2 = 0，比较次数为 3 插入 8 个关键码后的散列表 0 1 2 3 4 5 6 7 8 9 10 11 12 27 53 2 31 19 20 8 18 四、综合算法题 (1) 数据表定义 【解答】 const int DefaultSize = 100; template <class Type> class datalist //数据表的前视声明 template <class Type> class Element { //数据表元素类的定义 private: Type key; //关键码 field otherdata; //其它数据成员 public: Type getKey ( ) { return key; } //取当前结点的关键码 void setKey ( const Type x ) { key = x; } //将当前结点的关键码修改为 x } template <class Type> class datalist { //用顺序表来存储待排序的元素，这些元素的类型是 Type public: datalist ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) { Vector = new Element <Type> [MaxSz]; } private: Element <Type> * Vector; //存储待排序元素的向量 int MaxSize, CurrentSize; //最大元素个数与当前元素个数 } (2) 计数排序的算法 【解答 1】 template <class Type> void countsort ( datalist<Type> & initList, datalist<Type> & resultList ) { int i, j, c; Type refer; for ( i = 0; i < initList.CurrentSize; i++ ) { c = 0; refer := initList.Vector[i].getKey ( ); for ( j = 0; j < initList.CurrentSize; j++ )