数据结构陈惠南主编第二版习题答案1 9章 全.docx

数据结构陈惠南主编第二版习题答案1 9章 全.docx

《数据结构陈惠南主编第二版习题答案1 9章 全.docx》由会员分享，可在线阅读，更多相关《数据结构陈惠南主编第二版习题答案1 9章 全.docx（32页珍藏版）》请在冰点文库上搜索。

数据结构陈惠南主编第二版习题答案19章全

第一章绪论

1．（第18页，第（5）题）

确定下列各程序段的程序步，确定划线语句的执行次数，计算它们的渐近时间复杂度。

（1）i=1;k=0;

do{

k=k+10*i;i++;

}while（i<=n-1）

划线语句的执行次数为n-1。

（2）i=1;x=0;

do{

x++;i=2*i;

}while（i

划线语句的执行次数为?

logn?

。

2（3）for（inti=1;i<=n;i++）

for（intj=1;j<=i;j++）

for（intk=1;k<=j;k++）

x++;

划线语句的执行次数为n（n+1）（n+2）/6。

（4）x=n;y=0;

while（x>=（y+1）*（y+1））y++;

划线语句的执行次数为?

?

n?

。

第二章线性表

1．第37页习题

（2）.2

在类LinearList中增加一个成员函数，将顺序表逆置，实现该函数并分析算法的时间复杂度。

不利用类SeqList提供的操作直接实现。

template

voidSeqList:

:

Invert（）

{

Te;

for（inti=1;i<=length/2;i++）{

e=elements[i-1];

elements[i-1]=elements[length-i];

elements[length-i]=e;

}

}

2．第37页习题（5）

在类SingleList中增加一个成员函数，将单链表逆置运算，直接实现该函数并分析其时间复杂度。

template

voidSingleList:

:

invert（）

{

Node*p=first,*q;

first=NULL;

while（p）{

q=p->link;p->link=first;

first=p;p=q;

}

}

中增加一个成SingleList题）单链表中结点按元素值递增链接，在类（第3．37页，第7。

（a?

b）员函数，直接实现删除结点值在a至b之间的结点template

）页，习题（7voidSingleList:

:

DeleteAb（Ta,Tb）//第37{

ode*p=first,*q=first;N

while（p&&p->data

if（p->data<=a）{

q=p;p=p->link;

}

elseif（q==first）{

q=p->link;

deletep;

p=first=q;

}

else{

q->link=p->link;

deletep;

p=q->link;

}

}

}

在不增加新结点的情况下，中增加一个成员函数，在类CircularList第4.（第37页，8题）直接实现两个链表合并为一个链表的算法，并分析其时间复杂度。

template

voidMerge（CircularList&a,

CircularList&b）

{

Node*p=b.first;

while（p->link!

=b.first）p=p->link;

p->link=a.first->link;

a.first->link=b.first->link;

b.first->link=b.first;

b.length=0;

}

template

voidMerge1（CircularList&a,

CircularList&b）

{

Node*p=b.first->link;

b.first->data=b.first->link->data;

b.first->link=a.first->link;

a.first->link=p->link;

p->link=p;

b.first=p;

}

第三章栈与队列

1．第50页习题

（1）

设A、B、C、D、E五个元素依次进栈（进栈后可立即出栈），问能否得到下列序列。

若能得到，则给出相应的push和pop序列；若不能，则说明理由。

1）A,B,C,D,E2）A,C,E,B,D

3）C,A,B,D,E4）E,D,C,B,A

答：

2）和3）不能。

对2）中的E，B，D而言，E最先出栈，则表明，此时B和D均在栈中，由于，B先于D进栈，所以应有D先出栈。

同理3）。

2.第50页习题（9）

利用栈可以检查表达式中括号是否配对，试编写算法实现之。

boolmatch（chara[],intn）

{

inttop=-1;

for（inti=0;i

if（a[i]=='（'）top++;

elseif（a[i]=='）'）

if（top>-1）top--;

elsereturntrue;

if（top>-1）returntrue;

returnfalse;

}

3.第50页习题（10）

声明并实现链式队列类LinkedQueue。

template

classLinkedStack:

publicStack

{

public:

LinkedStack（）;

~LinkedStack（）;

virtualboolIsEmpty（）const;

virtualboolIsFull（）const;

virtualboolGetTop（T&x）;

virtualboolPush（constTx）;

virtualboolPop（）;

virtualvoidSetNull（）;

private:

Node*top;

};

template

LinkedStack:

:

LinkedStack（）

{

top=NULL;

}

template

LinkedStack:

:

~LinkedStack（）

{

Node*q;

while（top）{

q=top->link;

deletetop;

top=q;

}

}

template

boolLinkedStack:

:

IsEmpty（）const

{

return!

top;

}

template

boolLinkedStack:

:

IsFull（）const

{

returnfalse;

}

template

boolLinkedStack:

:

GetTop（T&x）

{

if（IsEmpty（））{

cout<

returnfalse;

}

x=top->data;

returntrue;

}

template

boolLinkedStack:

:

Push（constTx）

{

Node*q=newNode;

q->data=x;

q->link=top;

top=q;

returntrue;

}

template

boolLinkedStack:

:

Pop（）

{

Node*q=top;

if（IsEmpty（））{

cout<

returnfalse;

}

top=top->link;

deleteq;

returntrue;

}

template

voidLinkedStack:

:

SetNull（）

{

Node*q;

while（top）{

q=top->link;

deletetop;

top=q;

}

}

第四章数组与字符串

1.给出三维数组元素A[i][j][k]的存储地址loc（A[i][j][k]）。

答：

设有三维数组声明为A[n][n][n]，每个元素占k个存储单元，则312loc（A[i][j][k]）=loc（A[0][0][0]）+k*（i*n*n+j*n+k）3232．（第68页，第5题）给出下列稀疏矩阵的

顺序三元组的行优先和列优先表示。

．

答：

题）页，第6683．（第的值。

和k[]对题图4-5的稀疏矩阵执行矩阵转置时数组num[]答：

）题

（2）154．（第69页，第中增加一个成员函数，实现统计该串中出现的字符、字符个数和每个String在顺序串类字符出现的次数。

voidString:

:

count（charch[],int&n,intnum[]）

{

n=0;

for（inti=0;i

intj=0;

while（j

=ch[j]）j++;

if（j==n）{

ch[j]=str[i];

num[j]=1;

n++;

}

elsenum[j]++;

}

}

递归第五章

1．设计一个递归算法，实现对一个有序表的顺序搜索。

template

intSeqList:

:

Search4（constT&x）const

{

elements[length]=1000;

returnSch4（x,0）;

}

template

intSeqList:

:

Sch4（constT&x,inti）const

{

if（x

elseif（x==elements[i]）return++i;

elsereturnSch4（x,i+1）;

}

补充题：

（2）求顺序搜索有序表失败时的平均搜索长度。

设有序表为（a,a,…,a），通常可以假定待查n21元素位于a之前，a与a之间，a与a之间,…,a与a之间以及a之后的共n+1个位置处的n312n-11n2概率是相等的。

答：

树第六章

2）题1．第107页，第（C，可分别组成多少不同的无序树、有序树和二叉树？

A，B和对于三个结点9棵

（1）无序树：

答：

12棵

（2）有序树：

棵3）二叉树：

30（次方i－1

（1）k的、2取整）/ki＋k－2

（2）（1m＋1）k＋（3）（i－0不等于1）%k（（4）i－）题页，第（42．第107设对一棵二叉树进行中序遍历和后序遍历的结果分别为：

BDCEAFHG1）中序遍历（DECBHGFA）后序遍历（2画出该二叉树。

答：

小题661073.第页，第（）题的第设计算法，交换一棵二叉树中每个结点的左、右子树。

template

voidBTree:

:

Exch（BTNode*p）

{

if（p）{

BTNode*q=p->lchild;

p->lchild=p->rchild;

p->rchild=q;

Exch（p->lchild）;

Exch（p->rchild）;

}

}

4.第107页，第10题

将图题6-24中的树转换成二叉树，并将图6-23中的二叉树转换成森林。

11题5.第107页，第6-24中的树的先序遍历和后序遍历的结果。

给出对图K

，H，，C，M，B，LGD答：

先序：

A，，E，F，J，A，，BL，K，C，G，F，E，DM，H，，后序：

J12题1076.第页，第分别以下列数据为输入，构造最小堆。

80，60，70，20，30，4050，

（1）10，1020，40，30，5070

（2）80，，60，，40，30，50，，，，，（3）8010702060）（1

（2）

3）（题107页，第137.第求结果优先权队列分别以上题的数据为输入，从空的优先权队列开始，依此插入这些元素，

的状态。

（2）小题11088.第页，第14题第（）、，对字符集合进行哈夫曼编码，S={A,B,C,D,E,F}，W={2,3,5,7,9,12}W为各字符的频率。

设

1）画出哈夫曼树（

（2）计算带权路径长度

第七章集合与搜索树

1．第137页，第（5）,

建立37，45，91，25，14，76，56，65为输入时的二叉搜索树，再从该树上依此删除76，45，则树形分别如何？

）137页，第（62．第试写一个判定任意给定的二叉树是否二叉搜索树算法。

;boolfail=false;?

intk=-template

voidBTree:

:

IsBiTree（BTNode*p,int&k,bool&fail）

{

if（p&&!

fail）{

IsBiTree（p->lchild,k,fail）;

if（kelement）k=p->element;

elsefail=true;

IsBiTree（p->rchild,k,fail）;

}

}

8）页，第（．第1373AVL搜索树。

以下列序列为输入，从空树开始构造X，Y，C，

（1）A，Z，B2）A,V,L,T,R,E,I,S,O,K

（

）12．第137页，第（4时，树中元素个数最少为多少？

B-树的高度为2阶5:

5

答）题137．第页，第（135a,g,f,b,k,d,h,m,j,e,s,i,r,x,建立从空树开始，以关键字序列：

;

树B-阶

（1）4．

（2）5阶B-树。

树4阶B-

（1）

阶B-树

（2）5

14）题6．第137页，第（a,e,f,h。

4阶B-树上依次删除从上题的

第八章散列与跳表

页，第（3）题1．第154h（key）=key%11。

采用线性探查法解决冲突，试用关键字值序设散列表ht[11]，散列函数，55建立散列表。

453525，，80，，60，，5070列：

6页，第（）题1542．第C++给出用拉链方法解决冲突的散列表搜索操作的函数实现。

template

boolLinkedHashTable:

:

Search（constK&k,E&e）const

{

inti=k%M,j;

HNode*p=ht[i];//元素结点类型Hnode

while（p）{

if（p->element==k）returntrue;

p=p->nextsynonym;

}

returnfalse;

}

3．第154页，第（3）题

设散列表ht[11]，散列函数h（key）=key%11。

采用二次探查法解决冲突，试用关键字值

序列：

70，25，80，35，60，45，50，55建立散列表。

）题154页，第（44．第（key）=key%9+1h（key）=key%11，h对上题的例子，若采用双散列法，试以散列函数21建立散列表。

图第九章

1）题1881．第页，第（对下面的有向图求

（1）每个顶点的入度和出度；

（2）强连通分量（3）邻接矩阵

2）题第188页，第（．2，5〉〉，〈4，〉〉，〈4，0，〈4，1，〉〈，〉〈，〉当以边〈1，0，〈13〉，2，1，〈24〉，3，2，〈346个顶点没有边的图开始，通过依此插入这些边，建立邻接表结构。

5〈，0〉的次序从只有画出该邻接表。

4188页，第（）题3．第已知有向图的邻接表，试写出计算各顶点的入度的算法。

template

voidLinkedGraph:

:

Degree（）

{

int*d=newint[n];inti;

ENode*p;

for（i=0;i

for（i=0;i

p=a[i];

while（p）{

d[p->adjvex]++;

p=p->nextarc;

}

}

for（i=0;i

}

）题页，第（．4第18862为起始顶点的深度优先搜索和广度优先搜索。

分别所建立的邻接表上进行以顶点在题2画出遍历所得到的深度优先搜索和广度优先搜索的生成森林（或生成树）。

）题188第页，第（85．

.分别设计算法，在邻接矩阵上实现有向图的深度优先搜索template

voidMGraph:

:

DFS（intv,boolvisited[]）

{

visited[v]=true;

cout<<<

for（intj=0;j

if（a[v][j]&&!

visited[j]）

DFS（j,visited）;

}

）题10第188页，第（6．。

9-3所示的工序组成。

若各工序以流水方式进行（即串行进行）设某项工程由图题

网络；AOV

（1）画出给工程的

（2）给出该工程的全部合理的工程流程。

7．第188页，第（11）题

设有边集合：

〈0，1〉，〈1，2〉，〈4，1〉，〈4，5〉，〈5，3〉，〈2，3〉

（1）求此图的所有可能的拓扑序列；

（2）若以此顺序通过加入边的方式建立邻接表，则在该邻接表上执行拓扑排序算法（TopoSort），则得到的拓扑序列是其中哪一种？

13）题8.第188页，第（的无向图的最小代价生成树。

使用普里姆算法以1为源点，画出图题9-5

）题页，第（9.第18816d9-6的有向图中以顶点A为源点的单源最短路径。

写出一维数组用迪杰斯特拉算法求图题在执行该算法的过程中各步的状态。

和path

源终最短路路径长

3AB（A,B）

4C（A,B,C）

4（A,D）D

4E（A,B,E）

G__

d[D]d[E]d[G]Sd[A]

d[B]d[C]

path[C]path[E]path[A]path[D]path[G]path[B]

∞4,AA5,A0,-13,A∞,-1,-1

4,B0,-1B3,A4,A∞,-14,B

4,B0,-14,A,-13,AC4,B∞4,B4,A∞0,-1,-14,BD3,A

4,B

∞,-1

4,B

3,A

4,A

E

0,-1

10.第188页，第（17）题

用弗洛伊德算法求图题9-6的有向图的所有顶点之间的最短路径。

写出二维数组d和path在

执行该算法的过程中各步的状态。

path

d

-1A-1AA-1∞54∞30

-1B-1-1B-1∞1∞10∞

-1C-1-1-1-1∞2∞∞0∞

-1-1-1-1-1D3∞∞0∞∞-1∞-1∞∞∞2-10E-1-1

-1

-1∞∞G∞-13-1

2G0

（1）初始状态

dA

pathA

-1A-1AA-13054

-10-11-1-11BB

-1C-1-10-1-12

-1-1-13-1D-10

-1-1-1-102E-1

-1

G-1-1-1G0

32∞∞∞

pathB

dB

34044∞BAB-1-1A

-11∞∞B-11B-1∞0-1

-1-10∞∞-12-1∞∞-1C

-14B∞40-1B3∞-1D

-10∞∞∞-1-1∞2-1-1E

-1

0∞-1∞3G∞2-1-1G

pathC

dC

BAB-1A-14∞4034

-1C-1-1BB∞011∞3

-1∞-1∞0C2-1-1-1∞∞-134∞∞4-1-1D0BB

-1E0-12∞∞-1-1∞-1∞

-1

G2∞-1-103G-1∞∞

pathD

dD

BA-1AB-143044∞-1-1-1BBC∞3∞011

-1-1BDC-1∞6025∞-1BB-1D-1∞044∞3

-1∞∞B052-1D-1E6

-1

∞0237B6D

-1GG

pathEpathGdEdG

∞-1AB

AB444-103

-1-1-1BCB10∞31∞-1C-1D-1B∞5206∞-1DB-1B-1∞3∞404

-1-1DE-1B∞265