严蔚敏++数据结构习题集答案(9)

NOV NOV NOV 加APR 加MAR OCT OCT OCT 右单旋 FEB FEB FEB SEP JUL JUL SEP SEP -2 DEC JUL AUG AUG APR AUG DEC APR DEC MAR APR

NOV NOV 加MAY OCT OCT FEB FEB 左单旋 SEP JUL +2 MAR SEP AUG AUG JUL MAY APR DEC MAR APR DEC

MAY

NOV -2 MAR

加JUN OCT FEB FEB NOV 左右双旋 AUG MAR AUG SEP MAY OCT JUL SEP APR JUL MAY APR DEC DEC JUN

JUN MAR 加JAN NOV FEB AUG JUL MAY OCT

APR DEC JAN JUN SEP

8-9 将关键码1, 2, 3, ?, 2k-1依次插入到一棵初始为空的AVL树中。试证明结果树是完全平衡的。 【解答】

所谓“完全平衡”是指所有叶结点处于树的同一层次上，并在该层是满的。此题可用数学归纳法证明。

当k = 1时，21-1 = 1，AVL树只有一个结点，它既是根又是叶并处在第0层，根据二叉树性质，应具有20 = 1个结点。因此，满足完全平衡的要求。 设k = n时，插入关键码1, 2, 3, ?, 2n-1到AVL树中，恰好每一层(层次号码i = 0, 1, ?, n-1)有2i个结点，根据二叉树性质，每一层达到最多结点个数，满足完全平衡要求。则当k = n+1时，插入关键码为1, 2, 3, ?, 2n-1, 2n, ?, 2n+1-1，总共增加了从2n到2n+1-1的2n+1-1-2n +1 = 2n个关键码，使得AVL树在新增的第n层具有2n个结点，达到该层最多结点个数，因

此，满足完全平衡要求。

8-10设散列表为HT[13], 散列函数为 H (key) = key 。用闭散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。采用线性探查法寻找下一个空位, 画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。 (2) 采用双散列法寻找下一个空位, 再散列函数为 RH (key) = (7*key) % 10 + 1, 寻找下一个空位的公式为 Hi = (Hi-1 + RH (key)) % 13, H1 = H (key)。画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。 【解答】 使用散列函数 H(key) = key mod 13，有 H(12) = 12, H(23) = 10, H(45) = 6, H(57) = 5, H(20) = 7, H(03) = 3, H(78) = 0, H(31) = 5, H(15) = 2, H(36) = 10. (1) 利用线性探查法造表：

0 1 2 3 4 5 6 7 8 9 10 11 12 78

15 03 57 45 20 31 23 36 12 (1) (1) (1) 搜索成功的平均搜索长度为

(1) (1) (1) (4)

(1) (2) (1)

114 ASLsucc = 10(1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) = 10 搜索不成功的平均搜索长度为

361ASLunsucc = 13(2 + 1 + 3 + 2 + 1 + 5 + 4 + 3 + 2 + 1 + 5 + 4 + 3) = 13

(2) 利用双散列法造表： Hi = (Hi-1 + RH (key)) % 13, H1 = H (key) 0 1 2 3 4 5 6 7 78 15 03 57 45 20 (1) (1) (1) 搜索成功的平均搜索长度为

8 31 9 36 10 11 23 12 12 (1)

(1) (1) (1) (3) (5) (1)

116ASLsucc = 10(1 + 1 + 1 + 1 + 1 + 1 + 3 + 5 + 1 + 1) = 10

静态数据表类定义

#include const int DefaultSize = 100;

template class dataList

template class Element { friend class dataList ; private: Type key;

//排序码 //其它数据成员

field otherdata;

//数据表元素类的定义

//数据表的前视声明

public:

Type getKey ( ) { return key; }

//取当前结点的排序码 //将当前结点的排序码修改为x //结点x的值赋给this

void setKey ( const Type x ) { key = x; }

Element& operator = ( Element& x )

{ key = x->key; otherdata = x->otherdata; }

int operator == ( Type& x ) { return key == x->key; } //判this与x相等 int operator <= ( Type& x ) { return key <= x->key; } //判this小于或等于x int operator > ( Type& x ) { return key > x->key; } int operator < ( Type& x ) { return key > x->key; }

template class dataList {

//用顺序表来存储待排序的元素，这些元素的类型是Type private:

Element * Vector; int MaxSize, CurrentSize; public:

datalist ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) { Vector = new Element [MaxSize]; } int length ( ) { return CurrentSize; }

Element& operator [ ] ( int i ) { return Vector[i]; } void swap ( Element & x, Element & y ) //交换x, y }

{ Element temp = x; x = y; y = temp; }

//排序

void Sort ( );

//构造函数

//存储待排序元素的向量 //最大元素个数与当前元素个数 //用于快速排序的一次划分算法

}

//判this大于x //判this小于x

int Partition ( const int low, const int high )

静态链表类定义

template class staticlinkList;

template class Element { friend class staticlinkList; private: Type key; int link; public:

Type getKey ( ) { return key; } int getLink ( ) { return link; } }

template class staticlinkList { private:

//静态链表的类定义

//取当前结点的排序码 //将当前结点的排序码修改为x //取当前结点的链接指针 //将当前结点的链接指针置为ptr

void setKey ( const Type x ) { key = x; } void setLink ( const int ptr ) { link = ptr; }

//排序码，其它信息略 //结点的链接指针

//静态链表元素类的定义 //静态链表类的前视声明

Element *Vector; int MaxSize, CurrentSize; public:

//存储待排序元素的向量

//向量中最大元素个数和当前元素个数

dstaticlinkList ( int Maxsz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) { Vector = new Element [Maxsz]; }

}

9-1 什么是内排序? 什么是外排序? 什么排序方法是稳定的? 什么排序方法是不稳定的? 【解答】内排序是排序过程中参与排序的数据全部在内存中所做的排序，排序过程中无需进行内外存数据传送，决定排序方法时间性能的 …… 此处隐藏：4033字，全部文档内容请下载后查看。喜欢就下载吧 ……