数据结构之编写冒泡排序算法

错误！未找到引用源。

void BubbleSortDec ( DataType a[], int n ) {

for ( i=0; i

for( j=0; j if ( not change ) break; // 没有交换则完成排序 } }

错误！未找到引用源。

分析：计算语句频度是计算时间复杂度的基础。可以用观察和归纳进行简单的计算。 1) 问题规模n 执行次数 1 1 2 2+1 3 3+2+1 ... ... n n+...+2+1=n(n+1)/2 结论：语句频度为n(n+1)/2。 2) 问题规模n 执行次数 1 1 2 2 3 2 4 3 ... ...

k

2 k+1 结论：语句频度为?logn??1。

错误！未找到引用源。 void Reverse ( SqList& L ) {

for ( i=0; i

错误！未找到引用源。

思路1：先查找适合插入的位置i

向后移动元素（从后向前处理） 插入元素，表长加1

思路2：从后向前查找插入位置，同时向后移动大于x的元素 插入元素，表长加1 注意：表满时不能插入。 // 顺序表结构

①

用边界值验证法说明对于偶数个元素的表会有何种情况。

const int MAXSIZE = 1024; typedef struct {

DataType elem[MAXSIZE]; int length; } SqList;

// 向非递减有序的顺序表L中插入元素x，仍保持非递减有序 // 插入成功返回true，否则返回false

bool OrderListInsert ( SqList &L, DataType x ) {

if ( L.length==MAXSIZE ) return false; // 表满，插入失败 // 将大于x的元素后移

for ( i=L.length-1; i>=0 && L.elem[i]>x; i--) L.elem[i+1] = L.elem[i];

// 插入x (因为最后执行i--，故应在i+1处) L.elem[i+1] = x; L.length++; return true; }

错误！未找到引用源。

void Remove ( SqList &L, DataType x ) {

i = 0; // 剩余元素个数，同时是下一个元素的插入位置 for ( j=0; j

L.length = i; // 剩余元素个数 }

本算法的时间复杂度为O(n)；若改用反复调用查找和删除算法，时间复杂度会达到O(n2)。

错误！未找到引用源。

思路：设已经唯一化的序列是(a0, … , ai-1)，剩余序列是(aj,…, an)。所要做的就是在已经唯一化的序列L.elem[0..i-1]中查找L.elem[j]，如果未找到则复制到L.elem[i]处。如此重复直到剩余序列为空。 void Unique ( SqList &L ) {

if ( L.length<=1 ) return; // 空表或只有一个元素的表已经唯一化了 i = 1; // 开始L.elem[0..0]是唯一化序列 for ( j=1; j

// 在L.elem[0..i-1]中查找L.elem[j] for ( k=0; k

if ( L.elem[k]==L.elem[j] ) break; if ( k==i ) { // L.elem[j]未出现过，复制到L.elem[i]处 if ( j!=i ) L.elem[i] = L.elem[j]; i++; } }

L.length = i; // 表长为i }

以上算法的时间复杂度为O(n2)。当然，可以反复将重复元素删除达到唯一化，时间复杂度仍是O(n2)，但是与以上算法相比要移动更多元素。

错误！未找到引用源。

分析：由于该表是有序的，相等的元素必然靠在一起，不必从头开始查找，所以算法的时间复杂度可以降低。

思路：类似习题错误！未找到引用源。，但是查找部分只要与L.elem[i-1]比较就可以了。 void Unique ( SqList &L ) {

i = 0; // 开始的唯一化序列为空(○?对比习题错误！未找到引用源。思考为什么不用i=1开始①) for ( j=1; j

if ( L.elem[j]!=L.elem[i-1] ) { // Note：写成L.elem[j]!=L.elem[j-1]亦可 if ( j!=i ) L.elem[i] = L.elem[j]; i++; }

L.length = i; // 表长 }

错误！未找到引用源。

思路：从链上依次取下结点，按照逆序建表的方法(参见2.错误！未找到引用源。错误！未找到引用源。错误！未找到引用源。节)重新建表。 void Reverse ( LinkList &L ) {

p = L->next; // 原链表 L->next = NULL; // 新表(空表) while ( p ) {

// 从原链表中取下结点s s = p;

p = p->next;

// 插入L新表表头 s->next = L->next; L->next = s; } }

错误！未找到引用源。

void InsertionSort ( LinkList &L ) {

h = L->next; // 原链表 L->next = NULL; // 新空表 while ( h ) {

// 从原链表中取下结点s s = h; h = h->next;

①

原因是这里不能确定表是否为空，而习题2.4则用开始的if语句排除了空表的情况。事实上，习题2.4也可以仿照此

处修改，请读者自己完成。

// 在新表中查找插入位置 p = L;

while ( p->next && p->next->data<=s->data ) p = p->next; // 在p之后插入s s->next = p->next; p->next = s; } }

错误！未找到引用源。

void SelectionSort ( LinkList &L ) {

p = L;

while ( p->next ) {

// 选择最小(从p->next至表尾) q = p; // 最小元素的前驱q s = p;

while ( s->next ) {

if ( s->next->data < q->next->data ) q = s; s = s->next; }

m = q->next; // 找到最小m // 最小元素m插入有序序列末尾(p之后) if ( q!=p ) {

q->next = m->next; // 解下最小m m->next = p->next; // 插入p之后 p->next = m; }

p = p->next; // L->next至p为有序序列 } }

错误！未找到引用源。

// 将非递减有序的单链表lb合并入la，保持非递减有序 // 结果la中含有两个链表中所有元素，lb为空表 void Merge ( LinkList &la, LinkList &lb ) {

p = la, q = lb;

while ( p->next and q->next ) { // 跳过la中较小的元素

while ( p->next and (p->next->data <= q->next->data) ) p = p->next;

// 把lb中较小的元素插入la中

while ( p->next and q->next and (q->next->data < p->next->data) ) { s = q->next;

q->next = s->next; s->next = p->next; p->next = s;

p = s; } }

if ( lb->next ) { // 表lb剩余部分插入la末尾 p->next = lb->next; lb->next = NULL; } }

错误！未找到引用源。

分析：什么是不可能的出栈序列？如果后入栈的数(如4)先出栈，则此前入栈元素(如1,2,3)在栈中的顺序就确定了，它们的出栈顺序一定是逆序(如3,2,1)，否则就是不可能的出栈序列(如2,1,3)。 不可能的出栈序列有：4123，4132，4213，4231，4312，3412，3142，3124。其中后3种都含312这一不可能序列。

错误！未找到引用源。

[fa][r][][][]?[fa][b][r][][]?[fa][b][c][r][]?[][fb][c][r][]?[][][fc][r][]? [][][][f r][] 队列空 ? ... ?[f][r][][fd][e]?[f][g][r][fd][e] 队列满。

错误！未找到引用源。

思路：先将队列中的元素入栈，然后从栈中取出重新入队列。 void Reverse ( SqQueue &Q ) {

InitStack ( S );

while ( ! QueueEmpty(Q) ) {

DeQueue ( Q, x ); Push ( S, x ); }

while ( ! StackEmpty(S) ) {

Pop ( S, x ); EnQueue ( Q, x ); } }

错误！未找到引用源。 思路：对子串长度归纳。

子串的长度是0，1，2，...，n，对应子串的个数分别是1(空串)，n，n-1，...，1，总起来就是1+n+(n-1)+...+2+1=1+n(n+1)/2。

错误！未找到引用源。

分析：分别从结点个数和分支个数考虑。

设叶子个数为n0，结点总数：n = n0+n1+n2+...+nk，分支数目：n-1 = n1+2 n2+...+k nk，于是得到叶子个数

n0?1??(i?1)ni

i?1k

错误！未找到引用源。

分析：完全二叉树中度为1的结点至多有一个。

完全二叉树中的结点数n+(n-1) ≤ N ≤ n + (n-1) + 1，即2n-1 ≤ N ≤ 2n，二叉树的高度是 ?log(2n?1)??1?h??log(2n)??1

于是，(1) 当n=2k时，h??log n??1，当没有度为1的结点时；h??log n??2，当有1个度为1的结点时。(2) 其他情况下，h??log n??2。

错误！未找到引用源。

void PrintBinaryTree ( BinTree bt, int indent ) {

if ( ! bt ) return;

for ( i=0; idata );

PrintBinaryTree ( bt->lchild, indent+1 ); PrintBinaryTree ( bt->rchild, indent+1 ); }

错误！未找到引用源。

void PrintBinaryTree ( BinTree bt, int level ) {

if ( ! bt ) return;

PrintBinaryTree ( bt->rchild, level+1 ); // 旋转后先打印右子树 for ( i=0; idata );

PrintBinaryTree ( bt->lchild, level+1 ); }

错误！未找到引用源。

分析：按层遍历完全二叉树，当遇到第一个空指针之后应该全都是空指针。 bool IsComplete ( BinTree bt ) {

// 按层遍历至第一个空指针 InitQueue ( Q ); EnQueue ( Q, bt );

while ( ! QueueEmpty(Q) ) { DeQueue ( Q, p ); if ( p ) {

EnQueue ( Q, p->lchild ); EnQueue ( Q, p->rchild ); } else

break; // 遇到第一个空指针时停止遍历 }

// 检查队列中剩余元素是否全部是空指针 while ( ! QueueEmpty(Q) ) { DeQueue ( Q, p );

if ( ! p ) return false; // 不是完全二叉树 }

return true; // 完全二叉树 }

错误！未找到引用源。

分析：进行后序遍历时，栈中保存的是当前结点的所有祖先。所以，后序遍历二叉树，遇到该结点

时，取出栈中的内容即是所有祖先。 // 求二叉树bt中结点xptr的所有祖先

vector Ancestors ( BinTree bt, BinTree xptr ) {

stack s; stack tag; p = bt;

while ( p || ! s.empty() ) { if ( p ) {

s.push ( p ); tag.push ( 1 ); p = p->lchild; } else {

p = s.pop(); f = tag.pop(); if ( f==1 ) {

s.push ( p ); tag.push ( 2 ); p = p->rchild; } else {

if ( p==xptr ) {

v = s; // 当前栈的内容就是xptr的所有祖先 return v; }

p = NULL; } }

} // while

return vector(); // return a null vector }

注：这里为描述方便借助了C++中的某些描述方式。

错误！未找到引用源。

思路：用后序遍历求出两者的所有祖先，依次比较。 // 求二叉树bt中两个结点q和r的最近的共同祖先

BinTree LastAncestor ( BinTree bt, BinTree q, BinTree r ) {

stack sq, sr;

stack s; stack tag; // 求q和r的所有祖先 p = bt;

while ( p || ! s.empty() ) { if ( p ) {

s.push ( p ); tag.push ( 1 ); p = p->lchild; } else {

p = s.pop(); f = tag.pop(); if ( f==1 ) {

s.push ( p ); tag.push ( 2 ); p = p->rchild; } else {

if ( p==q ) sq = s; // q的所有祖先 if ( p==r ) sr = s; // s的所有祖先

p = NULL; } } }

// 先跳过不同层的祖先，然后依次比较同一层的祖先

if ( sq.size()>sr.size() ) while ( sq.size()>sr.size() ) sq.pop(); else while ( sr.size()>sq.size() ) sr.pop(); // 求q和r的最近的共同祖先

while ( !sq.empty() and (sq.top()!=sr.top()) ) { //寻找共同祖先 sq.pop(); sr.pop(); }

if ( !sq.empty() ) return sq.top(); else

return NULL; }

错误！未找到引用源。

分析：当左孩子的优先级低于根时需要加括号，根的优先级大于右孩子时也需要加括号。 void PrintExpression ( BinTree bt ) {

if ( bt==NULL ) return ;

if ( bt->lchild==NULL and bt->rchild==NULL ) print ( bt->data ); // 叶子结点直接打印 else {

// 左子树

brackets = bt->lchild and is_operator(bt->lchild->data)

and comp_operator(bt->lchild->data, bt->data)<0; // 左孩子优先级低于根 if ( brackets ) print (“(“); PrintExpression ( bt->lchild ); if ( brackets ) print (“)”); // 根结点

print ( bt->data ); // 右子树

brackets = bt->rchild and is_operator(bt->lchild->data)

and comp_operator(bt->data, bt->rchild->data)>0; // 根的优先级大于右孩子 if ( brackets ) print (“(“); PrintExpression ( bt->rchild ); if ( brackets ) print (“)“); } }

注：is_operator(c)判断c是否是运算符；comp_operator(a,b)比较两个运算符的优先级。 bool is_operator(char c) { // 判断c是否是运算符 return c=='+' || c=='-' || c=='*' || c=='/'; }

int comp_operator(char opl, char opr) { // 比较两个运算符的优先级 return (opl=='*' || opl=='/' || opr=='+' || opr=='-') ? +1 : -1; }

错误！未找到引用源。

分析：树中的叶子没有孩子，即firstchild为空。 // 求树t中叶子结点的个数 int LeafCount ( CSTree t ) {

if ( t==NULL ) return 0; // 空树 if ( t->firstchild==NULL ) // 没有孩子 return 1 + LeafCount(t->nextsibling); else

return LeafCount(t->firstchild) + LeafCount(t->nextsibling); }

错误！未找到引用源。

分析：度最大的结点的度数。 int Degree ( CSTree t ) {

if ( t==NULL ) return 0; else

return max( Degree(t->firstchild), 1+Degree(t->nextsibling)); }

错误！未找到引用源。 int Depth ( CSTree t ) {

if ( t==NULL ) return 0; else {

depchild = Depth(t->firstchild); // 孩子的深度 depsibling = Depth(t->nextsibling); // 兄弟的深度 return max(depchild+1, depsibling); // 取较大者 } }

错误！未找到引用源。

分析：划分先序序列a=(D,(L),(R))和后序序列b=((L),D,(R))，然后对子序列(L)和(R)递归。 // 根据先序序列a[si..ti]和中序序列b[sj..tj]构造二叉树

BinTree CreateBinaryTree ( T a[], int si, int ti, T b[], int sj, int tj ) {

if ( n<=0 ) return 0; // 空树 // 建立根结点

p = new BinNode(a[si]); // 以a[si]为数据域建立新结点 // 根据根结点划分中序序列为b[sj..k-1]和b[k+1..tj] k = sj;

while ( b[k]!=a[si] ) k++; // 在b[]中搜索根结点a[si] // 建立左右子树

p->lchild = CreateBinaryTree ( a, si+1, si+k-sj, b, sj, k-1 ); // 建立左子树 p->rchild = CreateBinaryTree ( a, si+k-sj+1, b, k+1, tj); // 建立右子树 return p; }

错误！未找到引用源。

分析：根据先根和后根序列可以唯一确定一棵树。先根序列中的第一个是树的根，后根序列中最后一个是根，然后根据先根序列和后根序列，将其余序列划分成若干不相交的子序列，就是根的子树，对每一个子树，重复前面的步骤，最终就可以得到整个树。

先根GFKDAIEBCHJ ?根为G，第一棵子树的根为F，又后根DIAEKFCJHBG，所以第一棵子树为(DIAEKF)，同样第二棵子树为(CJHB)，依此类推，可得该树。

G F K D A I E C B H J 错误！未找到引用源。 分析：根据森林和二叉树的对应关系，可知森林的先序序列和中序序列。划分出每一棵树，正好得到每棵树的先序和后序序列，最终得到整个森林。

A B C E D F G I J H K L 错误！未找到引用源。 分析：由于每个字符出现的频率不同，使用固定长度的编码往往比哈夫曼编码使得整个通信量增多。这里先建立哈夫曼树，得出哈夫曼编码，然后计算通信所需的字节数。每字节含8位。

使用固定长度的编码所需字节数为(20+6+34+11+9+7+8+5)*3/8=37.5字节。一种可能的哈夫曼编码是：A:00, B:1100, C:10, D:010, E:011, F:1110, G:1111, H:1101，通信的总字节数是[(20+34)*2+(11+9)*3+(6+5+7+8)*4]/8=34字节。

错误！未找到引用源。

分析：哈夫曼树总是取两个最小的子树合并成一棵二叉树，共需n-1步完成算法，共增加n-1个结点，故总结点个数为n+(n-1)=2n-1。

错误！未找到引用源。

分析：如果n条弧恰好使n个顶点构成环的话，这是构成强连通图所需弧最少的情况。类似无向图的情况，n-1个顶点最多有(n-1)(n-2)条弧，再增加n-1条指向另外一点顶点的弧(或者相反方向的弧)，此时该图恰好不能构成强连通图，若再增加一条弧则必定强连通。 因此，n个顶点的有向图最少需要n条弧就可以构成强连通图；当弧的数目超过(n-1)(n-2)+(n-1) =

2

(n-1)时，必定构成强连通图。

错误！未找到引用源。 A E D B C (a) A B C E D (b)

1 0 0 0 0 1 1 0 1 0 1) A B C D E /\\ 3 0 4 0 /\\ 3 2 /\\ /\\ 4 3 /\\ /\\

0 1 /\\ 0 1 0 0 1 0 0 0 0 0 A 0 B 0 C 0 D 1 E 1 0 A 1 B 2 C /\\ 3 D 4 E 1 2 0 0 2) 2 /\\ 3 /\\ 2 /\\ 3 /\\ 0 A 1 B 2 C 3 D 4 E /\\ 3 0 /\\ 0 1 3) 4 /\\ 1 4 /\\ 3 /\\ 0 2 /\\ 1 2 1 3 /\\ 4)

0 A 1 B 2 C 3 D 4 E /\\ 0 4 0 1 0 2 1 2 1 3 /\\ 1 4 2 3 /\\ 2 4 /\\ 3 4 /\\ 5)

错误！未找到引用源。

分析：画出搜索树，写出结果。

(a) 深度优先搜索：ABCDE，广度优先搜索：ABCDE； (b) 深度优先搜索：ABCDE，广度优先搜索：ABCED。

错误！未找到引用源。 0 A 3 2 /\\ 1 B 2 C 3 D 4 E /\\ 0 /\\ 0 4 1 /\\ 1 2 /\\ 分析：这里用邻接表给出了图的存储结构，同时确定了邻接点的先后关系。仍然采用搜索树分析。 深度优先遍历结果：ADEBC。

错误！未找到引用源。 参考错误！未找到引用源。。

错误！未找到引用源。 参考错误！未找到引用源。。

错误！未找到引用源。 参考课本P173。

错误！未找到引用源。 3 B 1 3 5 A 1 C 2 3 4 F V-U D 2 3 E 普里姆算法： U U到V-U中各顶点的最小代价 最小代B C D E F 价边 {A} {B,C,D,E,F} AB/3 AC/1 AD/2 ∞ ∞ AC/1 {A,C} {B,D,E,F} AB/3 AD/2 CE/5 CF/4 AD/2 {A,C,D} {B,E,F} AB/3 CE/5 DF/2 DF/2 {A,C,D,F} {B,E} AB/3 FE/3 AB/3 {A,C,D,F,B} {E} BE/1 BE/1 {A,C,D,F,B,E} {} 克鲁斯卡尔算法：

依次选择代价最小的边：AC, BE, AD, DF，然后，可以选择AB或BC或EF即可。 最小生成树的总代价是9。

错误！未找到引用源。 A B C D E F G 分析：可能的拓扑有序序列有多种，A之后可能是B或D，逐渐类推可得到所有可能的拓扑序列：ADBCGFE, ABDCGFE, ABCDGFE, ABCGDFE, ABCGFDE, ABCGFED，共6种。

错误！未找到引用源。

1 3 2 5 7 2 2 2 3 9 5 1 3 8 2 3 事件 v1 v2 v3 最早发生时间ve 0 2 5 最晚发生时间vl 0 7 5 活动 a(1,2) a(1,3) a(1,4) 4 1 5 6 最早开始时间e 0 0 0 最晚开始时间l 5 0 2

v4 3 5 a(2,5) 2 7 v5 8 8 a(3,5) 5 5 v6 5 6 a(3,6) 5 6 v7 11 11 a(4,6) 3 5 v8 11 11 a(5,7) 8 8 v9 13 13 a(5,8) 8 9 a(6,8) 5 6 a(7,8) 11 11 a(7,9) 11 11 a(8,9) 11 11 整个工程完工需要13天，关键路径有1?3?5?7?8?9和1?3?5?7?9。

错误！未找到引用源。

8 A B 6 4 2 3 F C 3 2 6 5 E D 1 终点 B C D E F 最短路径 8 AB 从A到各顶点的最短路径 8 AB 6 ADEB 6 ADEB 7 ADFC ADFC ∞ 2 AD 8 ADC 8 ADC 7 ADF 3 ADE 4 ADF 7 ADEB ADFC ∞ 6 AF 4 3 AD ADE 2 4 ADF 6 错误！未找到引用源。 3 A 5 D 2 1 2 B 4 C 0 3 BA ∞ 2 AC ∞ ∞ 2 CD 0 3 BA ∞ 2 AC ∞ ∞ 0 3 BA ∞ 2 AC ∞ ∞ 2 CD 0 4 CB ∞ 0 ∞ 2 A(0)

0 5 0 4 CB 5 BAC ∞ 5 DA 1 DB 0 0 BAC ∞ 4 0 2 CB CD 5 1 7 0 DA DB DAC A(1) 0 7 CBA 0 4 DBA 1 DB 6 DBAC 0

4 ACD A(2) 6 4 5 2 ACB AC ACD 3 0 5 7 BA BAC BACD 7 4 0 2 CBA CB CD 4 DBA 1 DB 6 DBAC 0 ACDB AC 3 0 5 BA BAC 6 3 0 CDBA CDB 4 1 6 DBA DB DBAC 7 BACD 2 CD 0

A(3) A(4)

错误！未找到引用源。

分析：等概率情况下查找成功时ASL = (n+1)/2 = 5.5；若查找失败的概率为0.2，则ASL = 0.8×(10+1)/2 + 0.2×11 = 6.6。

技巧：可以用归纳法。查找第1个元素比较10个关键字，查找第2个元素比较9个关键字，……，查找第10个元素比较1个关键字，总共比较10+9+…+1=55个关键字，ASL=55/10=5.5。 提示：以上分析都是按照课本上的算法，如果遇到其他具体算法还需要具体分析。①

错误！未找到引用源。

分析：画出判定树进行分析、计算。 8 4 2 6 12 10 14 1 3 5 7 9 11 13 15 技巧：不断计算区间的中点下标(即两端下标之和除以2)作为根结点，最终画出判定树。

ASL = (1×1+2×2+4×3+8×4)/15 = 49/15。查找第3个元素需要比较4个关键字，即第8、4、2和第3个。

错误！未找到引用源。

分析：比较8个关键字才能找到的元素位于判定树的第8层。对长度为1023的有序表折半查找的判定树有10层，第1至8层应该是满二叉树，所以恰好比较8次才找到的有27 = 128个，至多比较8次就能找到的是位于判定树第1至8层所有结点，共28-1 = 255个。

错误！未找到引用源。

①

按照课本上的算法，查找从后往前进行，所以查找第1个元素要比较10个关键字。查找失败时，由于和“哨兵”记

录多比较了1次，所以需要比较11个关键字。

分析：相当于索引顺序表的查找，当采用顺序查找时为使平均查找长度最小，应该划分成sqrt(n) = 100块。具体分析参见“错误！未找到引用源。错误！未找到引用源。”。

错误！未找到引用源。

思路：根据中序遍历序列是否升序来判断。 非递归算法：

bool IsBinarySortTree ( BinTree bt ) {

InitStack(S);

p = bt; pre = 0; // pre保持为p的中序前驱 while ( p or ! StackEmpty(S) ) { if ( p ) {

Push(S, p); p = p->lchild; } else {

p = Pop(S);

if ( pre and (p->data <= pre->data) ) return false; // 不是二叉排序树 pre = p; // 记下前驱结点 p = p->rchild; } }

return true; // 二叉排序树 }

递归算法：

bool IsBinarySortTree ( BinTree bt ) {

pre = NULL;

return IsBST ( bt, pre ); // 调用递归算法 }

// 判断二叉树bt是否是二叉排序树，pre是bt的前驱结点 bool IsBST (BinTree bt, BinTree &pre ) {

if ( bt==0 ) return true; // 空树是二叉排序树 else {

if ( not IsBST(bt->lchild, pre) ) return false; // 左子树

if ( pre and (bt->data <= pre->data) ) return false; // 根结点 pre = bt; // 保持前驱结点

if ( not IsBST(bt->rchild, pre ) ) return false; // 右子树 return true; } }

错误！未找到引用源。

13 24 37 90 13 24 37 90 53 13 24 20 37 90 53 40

错误！未找到引用源。 13 24 RR 37 13 24 40 24 37 13 37 53 RL 90 24 13 37 53 90

24 13 37 40 53 RL 24 90 13 37 53 40 90 13 20 24 37 53 40 LR 20 90 13 37 53 24 40 90

错误！未找到引用源。

思路：实际上就是对二叉排序树的查找。具体算法参见“错误！未找到引用源。”二叉排序树的查找算法(递归和非递归算法)。

错误！未找到引用源。 结果：20，5，6。 分析：最坏情况下，二叉排序树的深度为n(结点个数)，最小深度等于完全二叉树的深度?logn??1。 平衡二叉排序树的最大深度和结点数的关系为Nh=Nh-1+Nh-2+1，N0=0，N1=1。

错误！未找到引用源。 结果：2，4，3。

分析：非空B-树中的根结点最少可以有2棵子树，其他非终端结点至少含有?m/2?=3棵子树。结点最多有m=5棵子树，m-1=4个关键字。

错误！未找到引用源。

思路：依次插入关键字建立哈希表。详细步骤参见“错误！未找到引用源。错误！未找到引用源。”。

0 1 2 3 4 5 6 7 8 9 10 11 12 141 12 681 191 201 852 91 231 1) ASL = (1+2+1+1+1+2+1+1)/8 =5/4=1.25

0 1 2 3 4 5 6 7 8 9 10 11 12 202 141 681 853 191 12 91 231 2) ASL = (2+1+1+3+1+2+1+1)/8 =3/2=1.5 3)

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

14 68 /\\ 1 /\\ 19 /\\ 20 9 /\\ 23 /\\ 85 /\\ ASL = (1+2+1+1+1+2+1+1)/8 =5/4=1.25

错误！未找到引用源。

1) 直接插入排序

(24), 86, 48, 56, 72, 36 (24, 86), 48, 56, 72, 36 (24, 48, 86), 56, 72, 36 (24, 48, 56, 86), 72, 36 (24, 48, 56, 72, 86), 36 (24, 36, 48, 56, 72, 86) 2) 希尔排序

24, 86, 48, 56, 72, 36 dk=3 24, 72, 36, 56, 86, 48 dk=2 24, 48, 36, 56, 86, 72 dk=1 24, 36, 48, 56, 72, 86 3) 起泡排序

24, 86, 48, 56, 72, 36 24, 48, 56, 72, 36,(86) 24, 48, 56, 36,(72, 86) 24, 48, 36,(56, 72, 86) 24, 36,(48, 56, 72, 86) 24,(36, 48, 56, 72, 86) 4) 快速排序

{24, 86, 48, 56, 72, 36}

{}24{86, 48, 56, 72, 36} {36, 48, 56, 72}86{} {}36{48, 56, 72} {}48{56, 72} {}56{72} (24, 36, 48, 56, 72, 86)

5) 简单选择排序

24, 86, 48, 56, 72, 36 (24), 86, 48, 56, 72, 36 (24, 36), 48, 56, 72, 86 (24, 36, 48), 56, 72, 86 (24, 36, 48, 56), 72, 86 (24, 36, 48, 56, 72), 86 6) 堆排序

24, 86, 48, 56, 72, 36

(86, 72, 48, 56, 24, 36) (建立堆) (72, 56, 48, 36, 24), 86 (56, 36, 48, 24), 72, 86 (48, 36, 24), 56, 72, 86 (36, 24), 48, 56, 72, 86 (24), 36, 48, 56, 72, 86 7) 归并排序

(24),(86),(48),(56),(72),(36) (24, 86), (48, 56), (36, 72) (24, 48, 56, 86), (36, 72) (24, 36, 48, 56, 72, 86) 8) 链式基数排序

(24, 86, 48, 56, 72, 36) 分配：

[0][1][2][3][4][5][6][7][8][9] 72 24 86 48 56 36

收集：72, 24, 86, 56, 36, 48 分配：

[0][1][2][3][4][5][6][7][8][9] 24 36 48 56 72 86 收集：(24, 36, 48, 56, 72, 86)

错误！未找到引用源。 分析：含有n个记录的序列排序可能的初始状态有n!个，所以描述n个记录排序过程的判定树必有n!个叶子，二叉树的高度h≥log2(n!)+1。该判定树上必定存在长度为log2(n!)的路径。所以借助比较的排序方法在最坏情况下的所需要比较次数至少为log2(n!)。时间复杂度为O(log2(n!)) = O(nlogn)。

本文来源：https://www.bwwdw.com/article/v7x6.html