数据结构课后习题部分参考答案

第一章

一、选择题

1．C 2．C 3．A 4．D 5．B 二、判断题

1．╳ 2．╳ 3．╳ 4．╳ 5．∨ 三、简答题

1． 常见逻辑结构：

集合结构，数据元素之间的关系仅仅是属于同一个集合。

线性结构，除第一个元素只有一个直接后继、最后一个元素只有一个直接前驱，其余元素有且只有唯一一个直接前驱、有且只有唯一一个直接后继，数据元素之间存在一对一的关系。

树形结构，树中只有唯一一个根元素，除根元素之外，其余元素只有一个直接前驱，但可以有多个直接后继元素，数据元素之间存在一对多的关系。

图形结构，元素之间关系任意，数据元素之间存在多对多的关系。

常用的存储结构： 顺序存储，把逻辑上相邻的元素存储在物理位置相邻的存储单元中，由此得到的存储表示称为顺序存储结构。通常用数组实现。 链式存储，对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附加的指针字段来表示，由此得到的存储表示称为链式存储结构。通常用指针来实现。

除上述两种方法外，有时为了查找方便还采用索引存储方法和散列存储方法。

索引存储：在存储结点信息的同时，还建立附加的索引表来标识结点的地址。 散列存储：根据元素的关键码确定元素存储位置的存储方式。 2． 算法与程序的区别：

程序不一定满足有穷性(如操作系统)；

程序中的指令必须是机器可执行的，算法中的指令则无此限制；

算法代表了对问题的解，程序则是算法在计算机上的特定的实现(一个算法若用程序设计语言来描述，它才是一个程序);

数据结构+算法=程序。

3．例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录就是一个结点，对于整个表来说，只有一个开始结点和一个终端结点，其他的结点则各有一个也只有一个直接前趋和直接后继。这几个关系就确定了这个表的逻辑结构——线形结构。

那么我们怎样把这个表中的数据存储到里呢? 用高级语言如何表示各结点之间的关系呢? 是用一片连续的内存单元来存放这些记录（顺序存储）还是随机存放各结点数据再用指针进行链接（链式存储）呢? 这就是存储结构的问题，我们都是从高级语言的层次来讨论这个问题的。

最后，我们有了这个表，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。 4．例如栈和队列，两个数据结构的逻辑结构和存储方式完全相同，只是对于运算（如插入、删除）的定义不同，两个结构具有显著不同的特性。 5．语句频度

（1）n-1 （2）1 （3）n(n+1)/2 （4）n/2-1 （5）100

6．时间复杂度

（1）O(log3n) （2）O(n2) （3）O(n2) 7．算法思想：

P (x，n)=(…((anx+an-1)x+an-2)x+…+a1)x+a0 语句： y=0 ;

for (i=n;i>=0;i--) y=y*x+ ai ; 函数： void p( ) {float x,y; int n,i,a;

scanf(\"%f\scanf(\"%d\y=0;

for (i=n;i>=0;i--) {scanf(\"%d\

y=y*x+a; }

printf(\"x=%4.2f,y=%6.4f\}

第二章

一、选择题

1．A 2．A 3．D 4．C 5．D 6．B 7．C 8．B 9．A 10．D 11．B 12．D 二、判断题

1．╳ 2．∨ 3．╳ 4．∨ 5．╳ 6．∨ 7．╳ 8．∨ 9．∨ 10．╳ 11．╳ 12．╳ 三、算法设计题 1．

第一种方法（从后往前比较）：

因已知顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向前寻找到第一个

小于或等于x的元素位置i后，插入该位置后面即可。

在寻找过程中，由于大于x的元素都应放在x之后，所以可边寻找，边后移元素，当找到第一个小于或等于x的元素位置i时，插入x的位置i+1也空出来了。 算法如下：

void InsertIncreaseList1(seqlist *L,datatype x) {int i;

if (L->elemnum==maxsize) printf(\"overflow\"); // L->elemnum 中存放当前顺序表中的元素个数 for (i=L->elemnum-1;i>=0 && L->data[i]>x;i--) L->data[i+1]=L->data[i]; //从后往前比较并移动元素 L->data[i+1]=x;

L->elemnum++; }

第二种方法（从前往后比较）：

void InsertIncreaseList2(seqlist *L,datatype x) {int i,j;

if (L->elemnum==maxsize) printf(\"overflow\"); i=0;

while((i<=L->elemnum-1)&&(L->data[i]elemnum-1;j>=i;j--) L->data[j+1]=L->data[j]; //腾位置 L->data[i]=x; //插入 L->elemnum++; }

2（思路同算法2-16）

6（同1类似，最好也做一下。1是顺序存储，6是链式存储。做完同1比较一下） 7（看算法2-17,尾插实现）

第三章 一、选择题

1．C 2．B 3．D 4．B 5．B 6．C 7．B 8．D 9．C 10．C 二、判断题

1．∨ 2．∨ 3．∨ 4．╳ 5．╳ 三、简答题

1循环队列的优点是：它可以克服顺序队列的\"假上溢\"现象，能够使存储队列的向量空间得到充分的利用。 判别循环队列的\"空\"或\"满\"通常有两种方法：

（1）另设一个变量num记录当前队列中的元素个数,当num==0时队空， num==maxsize时队满。 （2）少用一个存储单元(即少存一个元素), 队空条件为front == rear，队满条件为(rear + 1) % maxsize == front 。

2．栈的特点是先进后出，队列的特点是先进先出。 先进后出用栈；先进先出用队列。

3．一个直接调用自己或通过一系列调用间接调用自己的过程称为递归。

递归程序结构清晰，可读性强，而且容易用数学归纳法来证明程序的正确性。 递归程序运行效率低，不论是耗费的计算时间还是占用的存储空间都比非递归程序要多。 4．1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321（十四种可能） 四、算法设计题

1．思想：将一半字符入栈) 算法为：

//以下为顺序栈的存储结构定义

#define StackSize 100 //假定预分配的栈空间最多为100个元素

typedef char DataType;//假定栈元素的数据类型为字符 typedef struct{

DataType data[StackSize]; int top; }SeqStack;

int IsHuiwen( char *t)

{//判断t字符向量是否为回文，若是，返回1，否则返回0 SeqStack s; int i , len; char temp; InitStack( &s);

len=strlen(t); //求向量长度

for ( i=0; iif （len%2==1） i++；// 处理向量长度为奇数的情况 while( !EmptyStack( &s))

{// 每弹出一个字符与相应字符比较 temp=Pop (&s);

if( temp!=S[i]) return 0 ;// 不等则返回0 else i++; }

return 1 ; // 比较完毕均相等则返回 1 }

2．我们通常用一个有三个分量（存储元素的空间、front、rear）的结构体变量实现循环队列，此题即要求用一个数组和两个简单变量（而不是一个结构体变量）实现循环队列的入队和出队。

5．思想： 对表达式进行扫描，凡遇到'('就进栈，遇')'就退掉栈顶的'('，表达式被扫描完毕，栈应为空。 算法如下：

int PairBracket( char *SR)

{//检查表达式ST中括号是否配对 int i;

SeqStack S; //定义一个栈 InitStack (&s);

for (i=0; iif ( S[i]=='(' ) Push(&S, SR[i]); //遇'('时进栈 if ( S[i]==')' ) //遇')'

if (!StackEmpty(S))//栈不为空时，将栈顶元素出栈 Pop(&s);

else return 0;//不匹配，返回0 }

if EmptyStack(&s) return 1;// 匹配，返回1 else return 0;//不匹配，返回0

}

第五章 一、选择题

1． C 2． C 3. B 4． B 5．B 6． C 7． B 8． D 9． A 10．D 11．D 12．C 13．B 14．D 15．B 二、判断题

1． ╳ 2．∨ 3． ╳ 4．╳ 5． ∨ 6． ╳ 7．╳ 8． ╳ 9．∨ 10．╳ 11. ╳ 12. ∨ 13．╳ 14．╳ 15．╳ 16．╳ 17．∨ 18．╳ 19．╳ 20．∨ 三、简答题

1．一棵度为2的树与一棵二叉树的区别在于: 度为2的树有两个分支，没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右不能交换。

树与二叉树的区别：

（1）二叉树的一个结点至多有两个子树，树形则不然。

（2）树中的结点只有一个子树时，无须区分其是左子树还是右子树；而二叉树中的结点只有一个子树时，必需确定其是左子树还是右子树。

2．（1） 0 A 1 B 2 C 3 D 4 E 5 F 6 7 8 9 G 10 11 12 H （2）

A B C D G

EFH

（3）

A B C D EGFH

3． （1） 0 1 2 3 4 5 6 7 8 9 10 11 12

A B C G F E D I H J K M N -1 0 0 1 1 2 2 2 4 5 5 6 7 （2） 0 1 2 3 4 5 6 7 8 9 10 11 12 A B C G F E D I H J K M N Λ Λ Λ Λ Λ Λ 1 3 5 9 11 Λ 2 Λ 4 Λ 6 10 Λ 7 Λ 8 Λ 12 Λ （3）

A B C GHFJKEDMN

I4．

ABFJECGDHI

森林中既无孩子又无右兄弟的结点在二叉树中是叶结点。 5．

ACHFBEDG 6. 用反证法证明。假设结点数大于1的哈夫曼树存在节点A度为1，那么A的孩子lchild的权值和A相同...

(叙述叙述)=>此树的WPL并非最小... 那么此树就不是哈夫曼树...

=>假设错误...=>结点数大于1的哈夫曼树不存在度为1的结点 7.n0=n2+1,n=n0+n1+n2= n0+0+ n0-1=2n0-1

8. 用数学归纳法证明。结点数n=1时，成立；假定n<=m-1时成立，证明n=m时成立。 9. 解：设该树中的叶子数为n0个。该树中的总结点数为n个，则有： n=n0+n1+n2+…+nm (1)

又有除根结点外，树中其他结点都有双亲结点，且是唯一的(由树中的分支表示)，所以，有双亲的结点数为：

n-1=0*n0+1*n1+2*n2+…+m*nm (2) 联立(1)(2)方程组可得：

叶子数为：n0=1+0*n1+1*n2+2*n3+...+(m-1)*nm 非终端结点数：n-n0=n1+n2+…+nm 10．2，n-1,n,1,n-1

11. 2–1,2h – 1 13．

h

GFBCHK DAEJI

14．

ABDCEFJGIKHL 15．

ABCFDEGHIJ

16．解：

(1)哈夫曼编码

1.00 0 0.590 0.280 0.120 g0.04 1 d 0.08

1 0.410 a f0.200 c0.10 1 0.211 e0.111 1 b0.160.31 哈夫曼编码树

根据上图可得编码表： a:01 b:001 c:110 d:0001 e:111 f:10 g:0000

(2)用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为： 2*0.31+3*0.16+3*0.10+4*0.08+3*0.11+2*0.20+4*0.04=2.61 2.61/3=0.87=87%

其平均码长是等长码的87%。 所以平均压缩率为13%。 四、算法设计题 1.

第一种方法（使用全局变量）： int n=0;

void nodenum1(BiTree root) { if(root!=NULL) { n++;

nodenum1(root->lchild); nodenum1(root->rchild); } }

第二种方法（不用全局变量）： 求结点数的递归定义为： 若为空树，结点数为0

若只有根结点，则结点数为1；

否则，结点数为根结点的左子树结点数+右子树结点数+1 int nodenum2(BiTree root)

{ if(root==NULL) return 0;

else return (1+nodenum2(root->lchild)+nodenum2(root->rchild)); }

第六章 一、选择题

1．B 3. B 4. C 5.(1) B (2) D 7. B 10. B 二、判断题

1．╳ 2． ∨ 3．∨ 4．╳ 7．∨ 9. ╳ 11．╳ 12．∨ 三、简答题 1.

(1) 每个顶点入度和出度：

ID(v1)=2 OD(v1)=1 ID(v2)=2 OD(v2)=2 ID(v3)=1 OD(v3)=3 ID(v4)=3 OD(v4)=0

ID(v5)=2 OD(v5)=3 ID(v6)=1 OD(v6)=2

(2) 邻接矩阵：

0 0 0 1 0 0

1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0

1 1 0 1 0 0 0 1 0 0 1 0

(3) 邻接表： 1 2 3 4 5 6 2. (1)

∧ 4∧ 1 4 1 2 3∧ 5 2 5∧ 6∧ 4∧ 0 1 1 0 0 0 0

1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 0

2 1 1 2 4 4 3∧ 4∧ 4∧ 3 7∧ 7∧ 5 6∧ (2) V1 V2 V3 V4 V5 V6 V7 5 6∧

(4)v1,v2,v4,v3,v5,v7,v6 (5)v1,v2,v3,v4,v5,v6,v7 3.用邻接矩阵表示图时，矩阵元素的个数与顶点个数有关（矩阵元素的个数是顶点个数的平方），与边的条数无关（矩阵中非零元素的个数与边的条数有关）。 四、算法设计题

8． （1）

int PATHDFS(ALGraph *G，int i,int j){

//以邻接表为存储结构，判断vi和vj之间是否有路径，若有返回1，否则返回0 EdgeNode *p；

visited[i]=TRUE； //标记vi已访问

p=G->adjlist[i].firstedge； //取vi边表的头指针 while(p){//依次搜索vi的邻接点vk，这里k=p->adjvex if （!visited[p->adjvex])//若vk尚未被访问 if (p->adjvex==j) return 1;

else ruturn PATHDFS(g，p->adjvex,j);//则以Vk为出发点向纵深搜索 p=p->next； //找vi的下一邻接点 } return 0; }//PATHDFS

（2）

int BFS(ALGraph *G，int i,int j)

{//以邻接表为存储结构，判断vi和vj之间是否有路径，若有返回1，否则返回0 int i；

CirQueue Q； //须将队列定义中DataType改为int EdgeNode *p；

InitQueue(&Q)；//队列初始化 visited[i]=TRUE；

EnQueue(&Q，i)；//vi已访问，将其人队。（实际上是将其序号人队） while(!QueueEmpty(&Q)){//队非空则执行 i=DeQueue(&Q)； //相当于vi出队

p=G->adjlist[i].firstedge； //取vi的边表头指针 while(p){//依次搜索vi的邻接点vk(令p->adjvex=k) if(!visited[p->adjvex]) //若vk未访问过 if (p->adjvex==j) return 1; else{

visited[P->adjvex]=TRUE； EnQueue(&Q，p->adjvex)； }//访问过的vk人队 p=p->next；//找vi的下一邻接点 }//endwhile }//endwhile return 0; }//end of pathBFS

10．

void ShortestPath(ALGraph *G,int P[ ],int D[ ]) { int final[MaxVerNum],i,j,k,min;

EdgeNode *s;

final[0]=1; /* 初始时集合S中只有0号顶点 */ D[0]=0;

P[0]=-1; /* 0号顶点 无前驱顶点 ，用-1表示 */ for(i=1;in;i++) { final[i]=0; D[i]= INFINITY ;

P[i]=0; /* P[i]存放i号顶点的前驱顶点 */ }

s=G->adjlist[0].firstedge;

while (s!=NULL) { D[s->adjvex]=s->weight; s=s->next; } for(i=1;in; i++) /*重复G->n-1次*/ { min=INFINITY; for(k=0;kn;k++)

if(final[k]==0&&D[k]adjlist[j].firstedge; while (s!=NULL)

{if((final[s->adjvex]==0)&& (D[j]+ s->weight< D[s->adjvex]))

{ D[s->adjvex]= D[j]+ s->weight; P[s->adjvex]=j; }

s=s->next;}

}

}

第七章 一、选择题

1． B 2. C 3. C 4. C 5. D 6. B 7. C 8. D 9. D 10. D 11. C 12. D 13. B 二、判断题

1．╳ 2 .∨ 3. ╳ 4. ∨ 5. ╳ 6. ∨ 7. ∨ 8. ∨ 9. ╳ 10. ╳ 11.∨ 13.∨ 14. ∨ 15.╳ 16. ∨ 18.╳ 19.∨ 20. ∨ 三、简答题 1．答：

等概率情况下，查找成功的平均查找长度为：

ASL=(1+2*2+3*4+4*8+5*3)/18=3.556

查找失败时，最多的关键字比较次树不超过判定树的深度，此处为5。

２．解：

(1) ASLSUCC=(1+2 X2+3 X3+4X3+5X2+6)/12=3.5

(2) 排序为：Apr,Aug,Dec,Feb,Jan,July,June,Mar,May,Nov,Oct,Sep

折半查找ASLSUCC=(1+2 X2+3 X4+4X5)/12=37/12

６． （1） 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Apr Aug Dec Feb Jan Mar May June July Sep Oct Nov ASLSUCC=(1+2+1+1+1+1+2+4+5+2+5+6)/12=31/12 ASLUNSUCC=(1+2+3+4+5+1+2+3+4+5+6+7+8+9)/14=60/14

(2) ∧ Feb ∧ ∧ Nov ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ASLSUCC=(7x1+4x2+1x3)/12=18/12 ASLUNSUCC=12/14(按照平均查找长度的定义，“Ci”指的是：“关键字和给定值比较的个数”，则在用链地址处理冲突时，和“空指针”的比较不计在内。否则，ASLUNSUCC=（7x1+3x2+3x3+1x4)/14=26/14） Apr Aug ∧ Dec ∧ Jan Mar June May ∧ Oct ∧ July ∧ Sep ∧ 手工计算等概率情况下查找成功的平均查找长度规则如下： ASLsucc＝

其中Ci为置入每个元素时所需的比较次数

手工计算等概率情况下查找不成功的平均查找长度规则如下： ASLunsucc＝

其中Ci为函数取值为i时确定查找不成功时比较次数 四、算法设计题 1. 解:

typedef struct{ KeyType key；

InfoType otherinfo； //此类型依赖于应用 }NodeType；

typedef NodeType SeqList[n+1]； //n号单元用作哨兵 int SeqSearch(Seqlist R，KeyType K)

{ //在顺序表R[0..n-1]中顺序查找关键字为K的结点， //成功时返回找到的结点位置，失败时返回-1 int i；

R[n].key=K； //设置哨兵 i=0;

while(R[i].key!= k ) i++; /* 从表前往后找 */ if (i等概率情况下查找成功ASL=(1+2+3+…+n)/n 等概率情况下查找失败时的ASL=n+1

2.

int bs(datatype a[ ],int l,int h,int kx) {int m;

if (l>h) return(0); m=(l+h)/2;

if (a[m].key==kx) return(m);

if (a[m].keykx) return(bs(a,l,m-1,kx)); }

3.解：

void bins(seqlist *L，datatype x)

// seqlist为顺序表类型，datatype为元素类型,元素按关键字升序排列 {int low,high,mid,i;

low=0;high=L->last;mid=(low+high)/2; while(low<=high)

{if (x.keydata[mid].key) high=mid-1; else low=mid+1; mid=(low+high)/2; }

for(i= L->last;i>=low;i--) L->data[i+1]= L->data[i];

L->data[low]=x; L->last++; } 4.解：

void output(btree *t)

{ if (t!=NULL)

{ output (t->rchild);

printf(“%d”,t->data);

output (t->lchild) ; } } 9. 解：

由二叉排序树的定义可得：二叉排序树中左子树的所有结点的值都小于根结点的值，所有右子树中结点的值都大于根结点的值。那么只要对待判定的二叉树中的结点按层遍历并判断即可。在该算法中要用到队列保存已遍历的结点指针。

typedef BinTNode *DataType;//循环队列中元素为二叉树结点指针 int BinSortStree(BinTree T) { CirQueue Q; BinTNode *p;

if (!T) return 1;//空树为二叉排序树 InitQueue(&Q); EnQueue(&Q,T);

while(!QueueEmpty(&Q)) { p=DeQueue(&Q); if (p->lchild)

if (p->datalchild->data) return -1;//不是二叉排序树 else EnQueue(&Q,p->lchild); if (p->rchild)

if (p->data>p->rchild->data) return -1;//不是二叉排序树 else EnQueue(&Q,p->rchild); }

return 1;//是二叉排序树 }

第八章 一、选择题

1.A 2.C 3.C 4.D 5.D 6.C 7.B 8.C 9.D 10.C 二、判断题

1.╳ 2.╳ 3.╳ 4.╳ 5.╳ 6.∨ 7.╳ 8.∨ 9.∨ 10.╳ 三、简答题

1．

原序列：(Tim, Kay, Eva, Roy, Dot, Jon, Kim, Ann, Tom, Jim, Guy, Amy) （1） 直接插入排序

(Tim) Kay Eva Roy Dot Jon Kim Ann Tom Jim Guy Amy (Kay Tim) Eva Roy Dot Jon Kim Ann Tom Jim Guy Amy (Eva Kay Tim) Roy Dot Jon Kim Ann Tom Jim Guy Amy (Eva Kay Roy Tim) Dot Jon Kim Ann Tom Jim Guy Amy (Dot Eva Kay Roy Tim) Jon Kim Ann Tom Jim Guy Amy (Dot Eva Jon Kay Roy Tim) Kim Ann Tom Jim Guy Amy (Dot Eva Jon Kay Kim Roy Tim) Ann Tom Jim Guy Amy (Ann Dot Eva Jon Kay Kim Roy Tim) Tom Jim Guy Amy (Ann Dot Eva Jon Kay Kim Roy Tim Tom) Jim Guy Amy (Ann Dot Eva Jim Jon Kay Kim Roy Tim Tom) Guy Amy (Ann Dot Eva Guy Jim Jon Kay Kim Roy Tim Tom) Amy (Ann Amy Dot Eva Guy Jim Jon Kay Kim Roy Tim Tom) （2） 冒泡排序

Tim Kay Eva Roy Dot Jon Kim Ann Tom Jim Guy Amy Amy Tim Kay Eva Roy Dot Jon Kim Ann Tom Jim Guy Amy Ann Tim Kay Eva Roy Dot Jon Kim Guy Tom Jim Amy Ann Dot Tim Kay Eva Roy Guy Jon Kim Jim Tom Amy Ann Dot Eva Tim Kay Guy Roy Jim Jon Kim Tom Amy Ann Dot Eva Guy Tim Kay Jim Roy Jon Kim Tom Amy Ann Dot Eva Guy Jim Tim Kay Jon Roy Kim Tom Amy Ann Dot Eva Guy Jim Jon Tim Kay Kim Roy Tom Amy Ann Dot Eva Guy Jim Jon Kay Tim Kim Roy Tom Amy Ann Dot Eva Guy Jim Jon Kay Kim Tim Roy Tom Amy Ann Dot Eva Guy Jim Jon Kay Kim Roy Tim Tom （3）选择排序

Amy Kay Eva Roy Dot Jon Kim Ann Tom Jim Guy Tim Amy Ann Eva Roy Dot Jon Kim Kay Tom Jim Guy Tim Amy Ann Dot Roy Eva Jon Kim Kay Tom Jim Guy Tim Amy Ann Dot Eva Roy Jon Kim Kay Tom Jim Guy Tim Amy Ann Dot Eva Guy Jon Kim Kay Tom Jim Roy Tim Amy Ann Dot Eva Guy Jim Kim Kay Tom Jon Roy Tim Amy Ann Dot Eva Guy Jim Jon Kay Tom Kim Roy Tim Amy Ann Dot Eva Guy Jim Jon Kay Tom Kim Roy Tim Amy Ann Dot Eva Guy Jim Jon Kay Kim Tom Roy Tim Amy Ann Dot Eva Guy Jim Jon Kay Kim Roy Tom Tim Amy Ann Dot Eva Guy Jim Jon Kay Kim Roy Tim Tom （4） 快速排序

Tim Kay Eva Roy Dot Jon Kim Ann Tom Jim Guy Amy Amy Kay Eva Roy Dot Jon Kim Ann Guy Jim Tim Tom Amy Kay Eva Roy Dot Jon Kim Ann Guy Jim Tim Tom Amy Jim Eva Guy Dot Jon Ann Kay Kim Roy Tim Tom

Amy Ann Eva Guy Dot Jim Jon Kay Kim Roy Tim Tom Amy Ann Eva Guy Dot Jim Jon Kay Kim Roy Tim Tom Amy Ann Dot Eva Guy Jim Jon Kay Kim Roy Tim Tom （5）归并排序

Tim Kay Eva Roy Dot Jon Kim Ann Tom Jim Guy Amy

(Kay Tim)(Eva Roy)(Dot Jon)(Ann Kim)(Jim Tom)(Amy Guy) (Eva Kay Tim Roy) (Ann Dot Jon Kim) (Amy Guy Jim Tom) (Ann Dot Eva Jon Kay Kim Tim Roy) (Amy Guy Jim Tom) (Amy Ann Dot Eva Guy Jim Jon Kay Kim Roy Tim Tom) （6）基数排序

Tim Kay Eva Roy Dot Jon Kim Ann Tom Jim Guy Amy Eva Tim Kim Tom Jim Jon Ann Dot Kay Roy Guy Amy Kay Tim Kim Jim Amy Ann Tom Jon Dot Roy Guy Eva Amy Ann Dot Eva Guy Jim Jon Kay Kim Roy Tim Tom 2．

50，18，12，61，8，17，87，25

87，61，50，25，8，17，12，18（初始堆）

第一趟 18，61，50，25，8，17，12，87 第二趟 12，25，50，18，8，17，61，87 第三趟 12，25，17，18，8，50，61，87 第四趟 8，18，17，12，25，50，61，87 第五趟 8，12，17，18，25，50，61，87 第六趟 8，12，17，18，25，50，61，87 第七趟 8，12，17，18，25，50，61，87 3．基数排序 6．

（1）堆同一般二叉树一样既可采用顺序存储，也可采用链接存储。但因为堆是一棵完全二叉 树，所以适宜采用顺序存储，这样能够充分利用其存储空间。 （2）堆顶 （3）4n