最新数据结构(C语言版)第三版__清华大学出版社_习题参考答案

只要有信心，努力，一切可以改变。附录 习题参考答案

习题1参考答案

1.1.选择题

(1). A. (2). A. (3). A. (4). B.

C. (5). A. (6). A. (7). C. (8). A. (9). B. (10.) A.

1.2.填空题

(1). 数据 关系

(2). 逻辑结构 物理结构

(3). 线性数据结构 树型结构 图结构

(4). 顺序存储 链式存储 索引存储 散列表（Hash）存储

(5). 变量的取值范围 操作的类别

(6). 数据元素间的逻辑关系 数据元素存储方式或者数据元素的物理关系

(7). 关系 网状结构 树结构

(8). 空间复杂度和时间复杂度

(9). 空间 时间

(10). Ο(n)

1.3 名词解释如下：

数据：数据是信息的载体

是计算机程序加工和处理的对象

包括数值数据和非数值数据

数据项：数据项指不可分割的、具有独立意义的最小数据单位

数据项有时也称为字段或域

数据元素：数据元素是数据的基本单位

在计算机程序中通常作为一个整体进行考虑和处理

一个数据元素可由若干个数据项组成

数据逻辑结构：数据的逻辑结构就是指数据元素间的关系

数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系

数据类型：是指变量的取值范围和所能够进行的操作的总和

算法：是对特定问题求解步骤的一种描述

是指令的有限序列

1.4 语句的时间复杂度为：

(1) Ο(n2)

(2) Ο(n2)

(3) Ο(n2)

(4) Ο(n-1)

(5) Ο(n3)

1.5 参考程序：

main()

{

int X

Y

Z；

scanf("%d

%d

%d"

&X

&Y

Z)；

if (X>=Y)

if(X>=Z)

if (Y>=Z)

{ printf("%d

%d

%d"

X

Y

Z);}

else

{ printf("%d

%d

%d"

X

Z

Y);}

else

{ printf("%d

%d

%d"

Z

X

Y);}

else

if(Z>=X)

if (Y>=Z)

{ printf("%d

%d

%d"

Y

Z

X);}

else

{ printf("%d

%d

%d"

Z

Y

X);}

else

{ printf("%d

%d

%d"

Y

X

Z);}

}

1.6 参考程序：

main()

{

int i

n;

float x

a[]

p;

printf("nn=");scanf("%f"

&n);

printf("nx=");scanf("%f"

&x);

for(i=0;i<=n;i++)

scanf("%f "

&a[i]);

p=a[0];

for(i=1;i<=n;i++)

{ p=p+a[i]*x;

x=x*x;}

printf("%f"

p)'

}

习题2参考答案

2.1选择题

(1). C. (2). B. (3). B. (4). B. 5. D. 6. B. 7. B. 8. A. 9. A. 10. D.

2.2.填空题

(1). 有限序列

(2). 顺序存储和链式存储

(3). Ｏ(n) O(n)

(4). n-i+1 n-i

(5). 链式

(6). 数据 指针

(7). 前驱 后继

(8). Ο(1) Ο(n)

(9). s->next=p->next; p->next=s ;

(10). s->next

2.3. 解题思路：将顺序表A中的元素输入数组a

若数组a中元素个数为n

将下标为0

1

2

...

（n-1）/2的元素依次与下标为n

n-1

...

（n-1）/2的元素交换

输出数组a的元素

参考程序如下：

main()

{

int i

n;

float t

a[];

printf("nn=");scanf("%f"

&n);

for(i=0;i<=n-1;i++)

scanf("%f "

&a[i]);

for(i=0;i<=(n-1)/2;i++)

{ t=a[i]; a[i] =a[n-1-i]; a[n-1-i]=t;}

for(i=0;i<=n-1;i++)

printf("%f"

a[i]);

}

2.4 算法与程序：

main()

{

int i

n;

float t

a[];

printf("nn=");scanf("%f"

&n);

for(i=0;i

scanf("%f "

&a[i]);

for(i=1;i

if(a[i]>a[0]

{ t=a[i]; a[i] =a[0]; a[0]=t;}

printf("%f"

a[0]);

for(i=2;i

if(a[i]>a[1]

{ t=a[i]; a[i] =a[1]; a[1]=t;}

printf("%f"

a[0]);

}

2.5 算法与程序：

main()

{

int i

j

k

n;

float x

t

a[];

printf("nx=");scanf("%f"

&x);

printf("nn=");scanf("%f"

&n);

for(i=0;i

scanf("%f "

&a[i]); // 输入线性表中的元素

for (i=0; i

k=i;

for (j=i+1; j

if (k<>j) {t=a[i];a[i]=a[k];a[k]=t;}

}

for(i=0;i

if(a[i]>x) break;

for(k=n-1;k>=i;i--) // 移动线性表中元素

然后插入元素x

a[k+1]=a[k];

a[i]=x;

for(i=0;i<=n;i++) // 依次输出线性表中的元素

printf("%f"

a[i]);

}

2.6 算法思路：依次扫描A和B的元素

比较A、B当前的元素的值

将较小值的元素赋给C

如此直到一个线性表扫描完毕

最后将未扫描完顺序表中的余下部分赋给C即可

C的容量要能够容纳A、B两个线性表相加的长度

有序表的合并算法：

void merge (SeqList A

SeqList B

SeqList *C)

{ int i

j

k；

i=0；j=0；k=0；

while ( i<= && j<= )

if ([i]<=[j])

C->data[k++]=[i++]；

else

C->data[k++]=[j++]；

while (i<= )

C->data[k++]= [i++]；

while (j<= )

C->data[k++]=[j++]；

C->last=k-1；

}

2.7 算法思路：依次将A中的元素和B的元素比较

将值相等的元素赋给C

如此直到线性表扫描完毕

线性表C就是所求递增有序线性表

算法：

void merge (SeqList A

SeqList B

SeqList *C)

{ int i

j

k；

i=0；j=0；k=0；

while ( i<=)

while（j<= )

if ([i]=[j])

C->data[k++]=[i++]；

C->last=k-1；

}

习题3参考答案

3.1.选择题

(1). D (2). C (3). D (4). C (5). B (6). C (7). C (8). C (9). B (10).AB

(11). D (12). B (13). D (14). C (15). C (16). D(17). D (18). C (19). C (20). C

3.2.填空题

（1） FILO

FIFO

（2） -1

3 4 X * + 2 Y * 3 / -

（3）

stack.s[]=x

（4） p>llink->rlink=p->rlink

p->rlink->llink=p->rlink

（5） (R-F+M)%M

（6） top1+1=top2

（7） F==R

（8） front==rear

（9） front==(rear+1)%n

（10） N-1

3.3 答：一般线性表使用数组来表示的

线性表一般有插入、删除、读取等对于任意元素的操作

而栈只是一种特殊的线性表

栈只能在线性表的一端插入（称为入栈

push）或者读取栈顶元素或者称为"弹出、出栈"(pop)

3.4 答：相同点：栈和队列都是特殊的线性表

只在端点处进行插入

删除操作

不同点：栈只在一端（栈顶）进行插入

删除操作；队列在一端（top）删除

一端(rear)插入

3.5 答：可能序列有14种：ABCD; ACBD; ACDB; ABDC; ADCB; BACD; BADC; BCAD; BCDA; BDCA;

CBAD; CBDA; CDBA; DCBA

3.6 答：不能得到4

3

5

6

1

2

最先出栈的是4

则按321的方式出

不可能得到1在2前的序列

可以得到1

3

5

4

2

6

按如下方式进行push(1)

pop()

push(2)

push(3)

pop()

push(4)

push(5)

pop()

pop()

pop()

push(6)

pop()

3.7 答：stack

3.8 非递归:

int vonvert (int no

int a[]) //将十进制数转换为2进制存放在a[]

并返回位数

{

int r;

SeStack s

*p;

P=&s;

Init_stack(p);

while(no)

{

push(p

no%2);

no/=10;

}

r=0;

while(!empty_stack(p))

{

pop(p

a+r);

r++;

}

return r;

}

递归算法:

void convert(int no)

{

if(no/2>0)

{

Convert(no/2);

Printf("%d"

no%2);

}

else

printf("%d"

no);

}

3.9 参考程序：

void view(SeStack s)

{

SeStack *p; //假设栈元素为字符型

char c;

p=&s;

while(!empty_stack(p))

{

c=pop(p);

printf("%c"

c);

}

printf("n");

}

3.10 答：char

3.11 参考程序：

void out(linkqueue q)

{

int e;

while( != )

{

dequeue(q

e);

print(e); //打印

}

}

习题4参考答案

4.1 选择题：

(1). A (2). D (3). C (4). C (5). B (6). B (7). D (8). A (9). B (10). D

4.2 填空题：

（1） 串长相等且对应位置字符相等

（2） 不含任何元素的串

0

（3） 所含字符均是空格

所含空格数

（4） 10

（5） "hello boy"

（6） 13

（7） 1066

（8） 模式匹配

（9） 串中所含不同字符的个数

（10） 36

4.3 StrLength (s)=14

StrLength (t)=4

SubStr( s

8

7)=" STUDENT"

SubStr(t

2

1)="O"

StrIndex(s

"A")=3

StrIndex (s

t)=0

StrRep(s

"STUDENT"

q)=" I AM A WORKER"

4.4 StrRep(s

"Y"

"+");StrRep(s

"+*"

"*Y");

4.5 空串：不含任何字符；空格串：所含字符都是空格

串变量和串常量:串常量在程序的执行过程中只能引用不能改变；串变量的值在程序执行过程中是可以改变和重新赋值的

主串与子串：子串是主串的一个子集

串变量的名字与串变量的值:串变量的名字表示串值的标识符

4.6

int EQUAl(S

T)

{

char *p

*q;

p=&S;

q=&T;

while(*p&&*q)

{

if(*p!=*q)

return *p-*q;

p++;

q++;

}

return *p-*q;

}

4.7

(1)6*8*6=288

(2)1000+47*6=1282

(3)1000+(8+4)*8=1096

(4)1000+(6*7+4)*8=1368

4.8

习题5参考答案

5.1 选择

（1）C（2）B（3）C（4）B（5）C（6）D（7）C（8）C（9）B（10）C

（11）B（12）C（13）C（14）C（15）C（16）B

5.2 填空

（1）1

（2）1036；1040

（3）2i

（4） 1 ； n ; n-1 ; 2

（5）2k-1；2k-1

（6）ACDBGJKIHFE

（7）p!=NULL

（8）Huffman树

（9）其第一个孩子; 下一个兄弟

（10）先序遍历；中序遍历

5.3

叶子结点:C、F、G、L、I、M、K；

非终端结点：A、B、D、E、J；

各结点的度：

结点： A B C D E F G L I J K M

度： 4 3 0 1 2 0 0 0 0 1 0 0

树深：4

5.4

无序树形态如下：

二叉树形态如下：

5.5

二叉链表如下:

三叉链表如下:

5.6

先序遍历序列:ABDEHICFJG

中序遍历序列:DBHEIAFJCG

后序遍历序列:DHIEBJFGCA

5.7

(1) 先序序列和中序序列相同：空树或缺左子树的单支树；

(2) 后序序列和中序序列相同：空树或缺右子树的单支树；

(3) 先序序列和后序序列相同：空树或只有根结点的二叉树

5.8

这棵二叉树为:

5.9

先根遍历序列:ABFGLCDIEJMK

后根遍历序列:FGLBCIDMJKEA

层次遍历序列:ABCDEFGLIJKM

5.10

证明：设树中结点总数为n

叶子结点数为n0

则

n=n0 + n1 + ...... + nm （1）

再设树中分支数目为B

则

B=n1 + 2n2 + 3n3 + ...... + m nm （2）

因为除根结点外

每个结点均对应一个进入它的分支

所以有

n= B + 1 （3）

将（1）和（2）代入（3）

得

n0 + n1 + ...... + nm = n1 + 2n2 + 3n3 + ...... + m nm + 1

从而可得叶子结点数为：

n0 = n2 + 2n3 + ...... + (m-1)nm + 1

5.11

由5.10结论得

n0 = (k-1)nk + 1

又由 n=n0 + nk

得nk= n-n0

代入上式

得

n0 = (k-1)（n-n0）+ 1

叶子结点数为：n0 = n (k-1) / k

5.12

int NodeCount(BiTree T)

{ //计算结点总数

if(T)

if (T-> lchild==NULL )&&( T --> rchild==NULL )

return 1;

else

return NodeCount(T-> lchild ) +Node ( T --> rchild )+1;

else

return 0;

}

5.13

void ExchangeLR(Bitree bt){

/* 将bt所指二叉树中所有结点的左、右子树相互交换 */

if (bt && (bt->lchild || bt->rchild)) {

bt->lchild<->bt->rchild;

Exchange-lr(bt->lchild);

Exchange-lr(bt->rchild);

}

}/* ExchangeLR */

5.14

int IsFullBitree(Bitree T)

{/* 是则返回1

否则返回0

*/

Init_Queue(Q); /* 初始化队列*/

flag=0;

In_Queue(Q

T); /* 根指针入队列

按层次遍历*/

while(!Empty_Queue (Q))

{

Out_Queue(Q

p);

if(!p) flag=1; /* 若本次出队列的是空指针时

则修改flag值为1

若以后出队列的指针存在非空

则可断定不是完全二叉树 */

else if (flag) return 0; /*断定不是完全二叉树 */

else

{

In_Queue(Q

p->lchild);

In_Queue(Q

p->rchild); /* 不管孩子是否为空

都入队列

*/

}

}/* while */

return 1; /* 只有从某个孩子指针开始

之后所有孩子指针都为空

才可断定为完全二叉树*/

}/* IsFullBitree */

5.15

转换的二叉树为：

5.16

对应的森林分别为：

5.17

typedef char elemtype;

typedef struct

{ elemtype data;

int parent;

} NodeType;

(1) 求树中结点双亲的算法:

int Parent(NodeType t[ ]

elemtype x){

/* x不存在时返回-2

否则返回x双亲的下标(根的双亲为-1 */

for(i=0;i

if(x==t[i].data) return t[i].parent;

return -2;

}/*Parent*/

(2) 求树中结点孩子的算法:

void Children(NodeType t[ ]

elemtype x){

for(i=0;i

if(x==t[i].data)

break;/*找到x

退出循环*/

}/*for*/

if(i>=MAXNODE) printf("x不存在n");

else {

flag=0;

for(j=0;j

if(i==t[j].parent)

{ printf("x的孩子:%cn"

t[j].data);

flag=1;

}

if(flag==0) printf("x无孩子n");

}

}/*Children*/

5.18

typedef char elemtype;

typedef struct ChildNode

{ int childcode;

struct ChildNode *nextchild;

}

typedef struct

{ elemtype data;

struct ChildNode *firstchild;

} NodeType;

(1) 求树中结点双亲的算法:

int ParentCL(NodeType t[ ]

elemtype x){

/* x不存在时返回-2

否则返回x双亲的下标 */

for(i=0;i

if(x==t[i].data) {

loc=i;/*记下x的下标*/

break;

}

if(i>=MAXNODE) return -2; /* x不存在 */

/*搜索x的双亲*/

for(i=0;i

for(p=t[i].firstchild;p!=NULL;p=p->nextchild)

if(loc==p->childcode)

return i; /*返回x结点的双亲下标*/

}/* ParentL */

(2) 求树中结点孩子的算法:

void ChildrenCL(NodeType t[ ]

elemtype x){

for(i=0;i

if(x==t[i].data) /*依次打印x的孩子*/

{

flag=0; /* x存在 */

for(p=t[i].firstchild;p;p=p->nextchild)

{ printf("x的孩子:%cn"

t[p-> childcode].data);

flag=1;

}

if(flag==0) printf("x无孩子n");

return;

}/*if*/

printf("x不存在n");

return;

}/* ChildrenL */

5.19

typedef char elemtype;

typedef struct TreeNode

{ elemtype data;

struct TreeNode *firstchild;

struct TreeNode *nextsibling;

} NodeType;

void ChildrenCSL(NodeType *t

elemtype x){ /* 层次遍历方法 */

Init_Queue(Q); /* 初始化队列 */

In_Queue(Q

t);

count=0;

while(!Empty_Queue (Q)){

Out_Queue(Q

p);

if(p->data==x)

{ /*输出x的孩子*/

p=p->firstchild;

if(!p) printf("无孩子n");

else

{ printf("x的第%i个孩子:%cn"

++count

p->data);/*输出第一个孩子*/

p=p->nextsibling; /*沿右分支*/

while(p){

printf("x的第%i个孩子:%cn"

++count

p->data);

p=p-> nextsibling;

}

}

return;

}

if(p-> firstchild) In_Queue(Q

p-> firstchild);

if(p-> nextsibling) In_Queue(Q

p-> nextsibling);

}

}/* ChildrenCSL */

5.20

(1) 哈夫曼树为:

(2) 在上述哈夫曼树的每个左分支上标以1

右分支上标以0

并设这7个字母分别为A、B、C、D、E、F和H

如下图所示：

则它们的哈夫曼树为分别为:

A：1100

B：1101

C：10

D：011

E：00

F：010

H：111

习题6参考答案

6.1 选择题

（1）C （2）A （3）B（4）C（5）B______条边

（6）B（7）A（8）A（9）B（10）A

（11）A（12）A（13）B（14）A（15）B（16）A（17）C

6.2 填空

（1） 4

（2） 1对多 ; 多对多

（3） n-1 ; n

（4） 0_

（5） 有向图

（6） 1

（7） 一半

（8） 一半

（9）___第i个链表中边表结点数___

（10）___第i个链表中边表结点数___

（11）深度优先遍历；广度优先遍历

（12）O（n2）

（13）___无回路

6.3

（1）邻接矩阵:

（2）邻接链表：

（3）每个顶点的度：

顶点 度

V1 3

V2 3

V3 2

V4 3

V5 3

6.4

（1）邻接链表：

（2）逆邻接链表：

（3）顶点 入度 出度

V1 3 0

V2 2 2

V3 1 2

V4 1 3

V5 2 1

V6 2 3

6.5

（1）深度优先查找遍历序列：V1 V2 V3 V4 V5; V1 V3 V5 V4 V2; V1 V4 V3 V5 V2

（1）广度优先查找遍历序列：V1 V2 V3 V4 V5; V1 V3 V2 V4 V5; V1 V4 V3 V2 V5

6.6

有两个连通分量：

6.7

顶点

（1）

（2）

（3）

（4）

（5）

Low Close

Cost Vex

Low Close

Cost Vex

Low Close

Cost Vex

Low Close

Cost Vex

Low Close

Cost Vex

V1

0 0

0 0

0 0

0 0

0 0

V2

1 0

0 0

0 0

0 0

0 0

V3

1 0

1 0

0 0

0 0

0 0

V4

3 0

2 1

2 1

0 1

0 1

V5

∞ 0

5 1

3 2

2 3

0 3

U

{v1}

{v1

v2}

{v1

v2

v3}

{v1

v2

v3

v4}

{v1

v2

v3

v4

v5}

T

{}

{ (v1

v2) }

{(v1

v2)

(v1

v3) }

{(v1

v2)

(v1

v3)

(v2

v4) }

{(v1

v2)

(v1

v3)

(v2

v4)

(v4

v5) }

最小生成树的示意图如下：

6.8

拓扑排序结果： V3--> V1 --> V4 --> V5 --> V2 --> V6

6.9

（1）建立无向图邻接矩阵算法：

提示：参见算法6.1

因为无向图的邻接矩阵是对称的

所以有

for (k=0; ke; k++) /*输入e条边

建立无向图邻接矩阵*/

{ scanf("n%d

%d"

&i

&j);

G ->edges[i][j]= G ->edges[j][i]=1;

}

(2)建立无向网邻接矩阵算法:

提示：参见算法6.1

初始化邻接矩阵：

#define INFINITY 32768 /* 表示极大值*/

for(i=0;in;i++)

for(j=0;jn;j++) G->edges[i][j]= INFINITY;

输入边的信息：

不仅要输入边邻接的两个顶点序号

还要输入边上的权值

for (k=0; ke; k++) /*输入e条边

建立无向网邻接矩阵*/

{ scanf("n%d

%d

%d"

&i

&j

&cost); /*设权值为int型*/

G ->edges[i][j]= G ->edges[j][i]=cost;/*对称矩阵*/

}

(3)建立有向图邻接矩阵算法:

提示：参见算法6.1

6.10

(1)建立无向图邻接链表算法：

typedef VertexType char;

int Create_NgAdjList(ALGraph *G)

{ /* 输入无向图的顶点数、边数、顶点信息和边的信息建立邻接表 */

scanf("%d"

&n); if(n<0) return -1; /* 顶点数不能为负 */

G->n=n;

scanf("%d"

&e); if(e<0) return =1; /*边数不能为负 */

G->e=e;

for(m=0;m< G->n ;m++)

G-> adjlist [m].firstedge=NULL; /*置每个单链表为空表*/

for(m=0;m< G->n;m++)

G->adjlist[m].vertex=getchar(); /*输入各顶点的符号*/

for(m=1;m<= G->e; m++)

{

scanf("n%d

%d"

&i

&j); /* 输入一对邻接顶点序号*/

if((i<0 || j<0) return -1;

p=(EdgeNode*)malloc(sizeof(EdgeNode));/*在第i+1个链表中插入一个边表结点*/

p->adjvex=j;p->next= G-> adjlist [i].firstedge;

G-> adjlist [i].firstedge=p;

p=(EdgeNode*)malloc(sizeof(EdgeNode));/*在第j+1个链表中插入一个边表结点*/

p->adjvex=i;p->next= G-> adjlist [j].firstedge;

G-> adjlist [j].firstedge=p;

} /* for*/

return 0; /*成功*/

}//Create_NgAdjList

(2)建立有向图逆邻接链表算法：

typedef VertexType char;

int Create_AdjList(ALGraph *G)

{ /* 输入有向图的顶点数、边数、顶点信息和边的信息建立逆邻接链表 */

scanf("%d"

&n); if(n<0) return -1; /* 顶点数不能为负 */

G->n=n;

scanf("%d"

&e); if(e<0) return =1; /*弧数不能为负 */

G->e=e;

for(m=0;m< G->n; m++)

G-> adjlist [m].firstedge=NULL; /*置每个单链表为空表*/

for(m=0;m< G->n;m++)

G->adjlist[m].vertex=getchar(); /*输入各顶点的符号*/

for(m=1;m<= G->e ; m++)

{

scanf("n%d

%d"

&t

&h); /* 输入弧尾和弧头序号*/

if((t<0 || h<0) return -1;

p=(EdgeNode*)malloc(sizeof(EdgeNode));/*在第h+1个链表中插入一个边表结点*/

p->adjvex=t;p->next= G-> adjlist [h].firstedge;

G-> adjlist [h].firstedge=p;

} /* for*/

return 0; /*成功*/

}//Create_AdjList

6.11

void Create_AdjM(ALGraph *G1

MGraph *G2)

{ /*通过无向图的邻接链表G1生成无向图的邻接矩阵G2*/

G2->n=G1->n; G2->e=G1->e;

for(i=0;in;i++) /* 置G2每个元素为0 */

for(j=0;jn;j++) G2->edges[i][j]= 0;

for(m=0;m< G1->n;m++)

G2->vexs[m]=G1->adjlist[m].vertex; /*复制顶点信息*/

num=（G1->n/2==0?G1->n/2:G1->n/2+1）; /*只要搜索前n/2个单链表即可*/

for(m=0;m< num;m++)

{ p=G1->adjlist[m].firstedge;

while(p)

{ /* 无向图的存储具有对称性*/

G2->edges[m][ p->adjvex ]= G2->edges[p->adjvex ] [m] =1;

p==p->next;

}

}/* for */

}/*Create_AdjM */

6.12

void Create_AdjL(ALGraph *G1

MGraph *G2)

{ /*通过无向图的邻接矩阵G1

生成无向图的邻接链表G2*/

G2->n=G1->n; G2->e=G1->e;

for(i=0;in;i++) /* 建立每个单链表 */

{ G2->vexs[i]=G1->adjlist[i].vertex;

G2->adjlist[i].firstedge=NULL；

for(j=i; jn; j++) /*对称矩阵

只要搜索主对角以上的元素即可*/

{ if(G1->edges[i][j]== 1)

{ p=(EdgeNode*)malloc(sizeof(EdgeNode));/*在第i+1个链表中插入一个边表结点*/

p->adjvex=j;p->next= G-> adjlist [i].firstedge;

G-> adjlist [i].firstedge=p;

p=(EdgeNode*)malloc(sizeof(EdgeNode));/*在第j+1个链表中插入一个边表结点*/

p->adjvex=i;p->next= G-> adjlist [j].firstedge;

G-> adjlist [j].firstedge=p;

}/*if*/

}/* for*/

}/* for*/

}/* Create_AdjL */

6.13

(1) 邻接矩阵中1的个数的一半;

(2) 若位于[i-1

j-1]或[j-1

i-1]位置的元素值等于1

则有边相连

否则没有

(3) 顶点i的度等于第i-1行中或第i-1列中1的个数

6.14

(1) 邻接链表中边表结点的个数的一半;

(2) 若第i-1（或j-1）个单链表中存在adjvex域值等于j-1（或i-1）的边表结点

则有边相连

否则没有

(3) 顶点i的度等于第i-1个单链表中边表结点的个数

6.15

提示：参见算法6.2 和6.3

习 题 7参考答案

7.1 选择题

（1）C (2)C (3) C (4)B (5) A (6)A (7) D (8)B (9)D (10) B

(11)B (12)A (13)C (14)C (15)A (16)D (17)C (18)B

C (19)B (20)A

7.2 填空题

（1） O(n)

O(log2n)

（2） 1

2

4

8

5

log2(n+1)-1

（3） 小于

大于

（4） 增序序列

（5）

m-1

（6） 70; 34

20

55

（7） n/m

（8） 开放地址法

链地址法

（9） 产生冲突的可能性就越大

产生冲突的可能性就越小

（10） 关键码直接

（11） ②

①

⑦

（12） 16

16

8

21

（13） 直接定址法

数字分析法

平方取中法

折叠法

除留余数法

随机数法

（14） 开放地址法

再哈希法

链地址法

建立一个公共溢出区

（15） 装满程度

（16） 索引

快

（17） 哈希函数

装填因子

（18） 一个结点

（19） 中序

（20） 等于

7.3 一棵二叉排序树(又称二叉查找树)或者是一棵空树

或者是一棵同时满足下列条件的二叉树：

(1)若它的左子树不空

则左子树上所有结点的键值均小于它根结点键值

(2)若它的右子树不空

则右子树上所有结点的键值均大于它根结点键值

(3)它的左、右子树也分别为二叉排序树

7.4 对地址单元d=H(K)

如发生冲突

以d为中心在左右两边交替进行探测

按照二次探测法

键值K的散列地址序列为：

do=H(K)

d1=(d0+12)mod m

d2=(d0-12)mod m

d3=(d0+22)mod m

d4=(d0-12)mod m

......

7.5 衡量算法的标准有很多

时间复杂度只是其中之一

尽管有些算法时间性能很好

但是其他方面可能就存在着不足

比如散列查找的时间性能很优越

但是需要关注如何合理地构造散列函数问题

而且总存在着冲突等现象

为了解决冲突

还得采用其他方法

二分查找也是有代价的

因为事先必须对整个查找区间进行排序

而排序也是费时的

所以常应用于频繁查找的场合

对于顺序查找

尽管效率不高

但却比较简单

常用于查找范围较小或偶而进行查找的情况

7.6此法要求设立多个散列函数Hi

i=1

...

k

当给定值K与闭散列表中的某个键值是相对于某个散列函数Hi的同义词因而发生冲突时

继续计算该给定值K在下一个散列函数Hi+1下的散列地址

直到不再产生冲突为止

7.7散列表由两个一维数组组成

一个称为基本表

另一个称为溢出表

插入首先在基本表上进行；假如发生冲突

则将同义词存人溢出表

7.8 结点个数为n时

高度最小的树的高度为1

有两层

它有n-1个叶结点

1个分支结点；高度最大的树的高度为n-l

有n层

它有1个叶结点

n-1个分支结点

7.9 设顺序查找以h为表头指针的有序链表

若查找成功则返回结点指针p

查找失败则返回null值

pointer sqesrearch(pointer h

int x

pointerp)

{

p=null；

while(h)

if(x>h->key)

h=h->link；

else

{

if(x==h->key)

p=h；

return(p)；

}

}

虽然链表中的结点是按从小到大的顺序排列的

但是其存储结构为单链表

查找结点时只能从头指针开始逐步进行搜索

故不能用折半(二分)查找

7.10 分析：对二叉排序树来讲

其中根遍历序列为一个递增有序序列

因此

对给定的二叉树进行中根遍历

如果始终能保证前一个值比后一个值小

则说明该二叉树是二叉排序树

int bsbtr (bitreptr T) ／*predt记录当前结点前趋值

初值为-∞*／

{ if (T==NULL) return(1)；

else

{b1=bsbtr(T->lchild)； ／*判断左子树*／

if (!b1|| (predt>=T->data)) return(0)；*当前结点和前趋比较*／

predt=T->data； ／*修改当前结点的前趋值*／

return(bsbtr(T->rchild))； ／*判断右子树并返回最终结果*／

}

}

7.11 (1)使用线性探查再散列法来构造散列表如表下所示

散列表

───────────────────────────────

地址 0 1 2 3 4 5 6 7 8 9 10

───────────────────────────────

数据 33 1 13 12 34 38 27 22

───────────────────────────────

（2）使用链地址法来构造散列表

如下图

(3)装填因子a=8／11

使用线性探查再散列法查找成功所需的平均查找次数为

Snl=0．5(1+1／(1-a))=0．5*(1+1／(1-8／11))=7／3

使用线性探查再散列法查找不成功所需的平均查找次数为：

Unl=0．5(1+1／(1-a)2)=0．5*(1+1／(1-8／11)2)=65／9

使用链地址法查找成功所需的平均查找次数为：

Snc=l+a／2=1+8／22=15／11

使用链地址法查找不成功所需的平均查找次数为： '

Unl=a+e-a=8／1l+e-8／11

7.12 分析：在等查区间的上、下界处设两个指针

由此计算出中间元素的序号

当中间元素大于给定值X时

接下来到其低端区间去查找；当中间元素小于给定值X时

接下来到其高端区间去查找；当中间元素等于给定值X时

表示查找成功

输出其序号

Int binlist(sqtable A

int s

t

keytype X) ／*t、s分别为查找区间的上、下界*／

{ if(s

else

{ mid=(S+t)／2；

switCh(mid)

{case x<[： return(binlist(A

s

mid-l

X))；

／*在低端区间上递归*／

case x==[mid].key： return(mid)；

case x>[mid].key： return(a

mid+l

t

X))；

／*在高端区间上递归*／

}

}

}

+查找成功*／／

7.13

int sqsearch0 (sqtable A

keytype X) /*数组有元素n个*／

{ i=l；[n+1].key=X； ／t设置哨兵*／

while ([n+1].key!=X) i++；

return (i% (n／1))； ／*找不到返回0

找到返回其下标*／

}

查找成功平均查找长度为：(1+2+3+...+n)／n：(1+n)／2

查找不成功平均查找长度为：n+1

7.14

散列函数：H(key)=100+(key个位数+key十位数) mod l0；

形成的散列表：

100 101 102 103 104 105 106 107 108 109

98 75 63 46 49 79 61 53 17

查找成功时的平均长度为：(1+2+1+1+5+1+1+5+5+3)/10=2.5次

由于长度为10的哈希表已满

因此在插人第11个记录时所需作的比较次数的期望值为10

查找不成功时的平均长度为10

习 题 8参考答案

8．1 选择题

（1）B (2)A (3)D (4)C (5)B (6)A (7)B (8)C (9)A (10)C

(11)D (12)C (13) C （14）D （15）C (16)B (17) D （18）C （19）B （20）D

8.2填空题

（1） 快速

归并

（2） O（log2n）

O(nlog2n)

（3） 归并

（4） 向上

根结点

（5） 19

18

16

20

30

22

（6）

（7）49

13

27

50

76

38

65

97

（8）8

8

（9）插入

选择（每次选择最大的）

（10）快速

归并

(11)O(1)

O(nlog2n)

(12)稳定

(13)3

(14)(15

20

50

40)

(15)O(log2n)

(16)O(n2)

(17)冒泡排序

快速排序

(18)完全二叉树

n/2

(19)稳定

不稳定

(20)2

4

(20

40

15)

8.3. 假定给定含有n个记录的文件(r1

f2

...

rn)

其相应的关键字为(k1

k2

...

kn)

则排序就是确定文件的一个序列rr

r2

...

rn

使得k1'≤k2'≤...≤kn'

从而使得文件中n个记录按其对应关键字有序排列

如果整个排序过程在内存中进行

则排序叫内部排序

假设在待排序的文件中存在两个或两个以上的记录具有相同的关键字

若采用某种排序方法后

使得这些具有相同关键字的记录在排序前后相对次序依然保持不变

则认为该排序方法是稳定的

否则就认为排序方法是不稳定的

8.4．稳定的有：直接插入排序、二分法插入排序、起泡排序、归并排序和直接选择排序

8.5．初始记录序列按关键字有序或基本有序时

比较次数为最多

8.6．设5个元素分别用a

b

c

d

e表示

取a与b、c与d进行比较

若a>b

c>d(也可能是a

c

此时情况类似)

显然此时进行了两次比较

取b与d再比较

若b>d则a>b>d

若b

则有c>d>b

此时已进行了3次比较

要使排序比较最多7次

可把另外两个元素按折半检索排序插入到上面所得的有序序列中

此时共需要4次比较

从而可得算法

共只需7次比较

8.7．题目中所说的几种排序方法中

其排序速度都很快

但快速排序、归并排序、基数排序和Shell排序都是在排序结束后才能确定数据元素的全部序列

而排序过程中无法知道部分连续位置上的最终元素

而堆排序则是每次输出一个堆顶元素(即最大或最少值的元素)

然后对堆进行再调整

保证堆顶元素总是当前剩下元素的最大或最小的

从而可知

欲在一个大量数据的文件中

如含有15000个元素的记录文件中选取前10个最大的元素

可采用堆排序进行

8.8．二分法排序

8.9．

void insertsort(seqlist r)  ；

{ ／／对顺序表中记录R[0一N-1)按递增序进行插入排序&NBSP；

int i

j；  ；

for(i=n-2；i>=0; i--) ／／在有序区中依次插入r[n-2]．．r[0]  ；

if(r[i].key>r[i+1].key) ／／若不是这样则r[i]原位不动 ；

{  ；

r[n]=r[i]；j=i+l； ／／r[n]是哨兵 ；

do{ ／／从左向右在有序区中查找插入位置 ；

r[j-1]= r[j]； ／／将关键字小于r[i]．key的记录向右移 ；

j++；  ；

}whle(r[j].key r[j-1]=r[n]； ／／将引i)插入到正确位置上 ；

}／／endif ；

}／／insertsort．  ；

8.10．

建立初始堆：[937 694 863 265 438 751 742129075 3011]&NBSP；

&NBSP；

第一次排序重建堆：[863 694 751 765 438 301 742 129 075]937

8.11．在排序过程中

每次比较会有两种情况出现

若整个排序过程至少需作t次比较

则显然会有2^t个情况

由于n个结点总共有n!种不同的排列

因而必须有n!种不同的比较路径

于是： 2t≥n!

即t≥log2n!

因为log2nl=nlog2n-n／ln2+log2n／2+O(1)

故有log2n!≈nlog2n

从而t≧nlog2n得证

8.12．依据堆定义可知：

序列(1)、(2)、(4)是堆

(3)不是堆

从而可对其调整使之为如下的大根堆(100

95

80

60

40

95

82

10

20)

8.13．第一趟：[265 301] [129 751] [863 937] [694 742] [076 438]&NBSP；

&NBSP；

第二趟：[129 265 301 751] [694 742 863 937] [076 438]&NBSP；

&NBSP；

第三趟：[129 265 301 694 742 751 863 937] [076 438]&NBSP；

&NBSP；

第四趟：[076 129 265 301 438 694 742 751 863 937]&NBSP；

8.14．

(1)归并排序：

(18

29) (25

47) (12

58) (10

51)

(18

25

29

47) (10

12

51

58)

(10

12

18

25

29

47

51

58)

(2)快速排序：

(10

18

25

12

29

58

51

47)

(10

18

25

12

29

47

51

58)

(10

12

18

25

29

47

51

58)

(3)堆排序：

初始堆(大顶堆)：(58

47

51

29

18

12

25

10)

第一次调整：(51

47

25

29

18

12

10)(58)

第二次调整：(47

29

25

10

18

12)(51

58)

第三次调整：(29

18

25

10

12)(47

51

58)

第四次调整：(25

18

12

10)(29

47

51

58)

第五次调整：(18

10

12)(25

29

47

51

58)

第六次调整：(12

10) (18

25

29

47

51

58)

第七次调整：(10

12

18

25

29

47

51

58)

8.15．

(1)直接插入排序

序号 1 2 3 4 5 6 7 8 9 10 11 12

关键字 83 40 63 13 84 35 96 57 39 79 61 15

1=2 40 83 [63 13 84 35 96 57 39 79 61 15]

1=3 40 63 83 [13 84 35 96 57 39 79 61 15]

1=4 13 40 63 83 [84 3 5 96 57 39 79 61 15]

I=5 13 40 63 83 84 [35 96 57 39 79 61 15]

I=6 13 35 40 63 83 84 [96 57 39 79 61 15]

1=7 13 35 40 63 83 84 96 [57 39 79 61 15]

1=8 13 35 40 57 63 83 84 96 [ 39 79 61 15]

1=9 13 35 39 40 57 63 83 84 96 [79 61 15]

I=10 13 35 39 40 57 63 79 83 84 96 [61 15]

I=11 13 35 39 40 57 61 63 79 83 84 96 [15]

1=12 13 15 35 39 40 57 61 63 79 83 84 96

(2)直接选择排序

序号 1 2 3 4 5 6 7 8 9 10 11 12

关键字 83 40 63 13 84 35 96 57 39 79 61 15

i=1 13 [ 40 63 83 84 35 96 57 39 79 61 15]

i=2 13 15 [63 83 84 35 96 57 39 79 61 40]

i=3 13 15 35 [83 84 63 96 57 39 79 61 40]

i=4 13 15 35 39 [84 63 96 57 83 79 61 40]

i=5 13 15 35 39 40 [63 96 57 83 79 61 84]

i=6 13 15 35 39 40 57 [96 63 83 79 61 84]

i=7 13 15 35 39 40 57 61 [63 83 79 96 84]

i=8 13 15 35 39 40 57 61 63 [83 79 96 84]

i=9 13 15 35 39 40 57 61 63 79 183 96 84]

i=10 13 15 35 39 40 57 61 63 79 83 [96 84]

i=11 13 15 35 39 40 57 61 63 79 83 84 [96]

(3)快速排序

关键字 83 40 63 13 84 35 96 57 39 79 61 15

第一趟排序后 [15 40 63 13 61 35 79 57 39] 83 [96 84]

第二趟排序后 [13] 15 [63 40 61 35 79 57 39] 83 84 [96]

第三趟排序后 13 15 [39 40 61 35 57] 63 [79] 83 84 96

第四趟排序后 13 15 [35] 39 [61 40 57] 63 79 83 84 96

第五趟排序后 13 15 35 39 [57 40] 61 63 79 83 84 96

第六趟排序后 13 15 35 39 40 [57] 61 63 79 83 84 96

第七趟排序后 13 15 35 39 40 57 61 63 79 83 84 96

(4)堆排序

关键字 83 40 63 13 84 35 96 57 39 79 61 15

排序成功的序列 96 84 83 79 63 61 57 40 39 35 15 13

(5)归并排序

关键字 83 40 63 13 84 35 96 57 39 79 61 15

第一趟排序后 [40 83] [13 63] [35

84] [57 96] [39 79] [15 61]

第二趟排序后 [13 40 63 83] [35 57 84 96] [15 39 61 79]

第三趟排序后 [13 35 40 57 63 83 84 96]] [15 39 61 79]

第四趟排序后 13 15 35 39 40 57 61 63 79 83 84 96