如有错误,敬请谅解!

此文章仅为本人学习笔记,仅供参考,如有冒犯,请联系作者删除!!

目录

第一章习题答案

第二章习题答案

第三章习题答案

第五章习题答案

第六章习题答案

第七章习题答案

第八章查找

第九章排序


第一章习题答案

2××√

3、(1)包含改变量定义的最小范围(2)数据抽象、信息隐蔽

3)数据对象、对象间的关系、一组处理数据的操作

4)指针类型

5)集合结构、线性结构、树形结构、图状结构

6)顺序存储、非顺序存储

7)一对一、一对多、多对多

8)一系列的操作

9)有限性、输入、可行性

4、(1A2C3D

5、语句频度为1+1+2+1+2+3++1+2+3++n

第二章习题答案

1、(1)一半,插入、删除的位置

2)顺序和链式,显示,隐式

3)一定,不一定

4)头指针,头结点的指针域,其前驱的指针域

2、(1A2AEA

BHLIEA

CFM

DLJAGJAG

3D4D5C6AC

3、头指针:指向整个链表首地址的指针,标示着整个单链表的开始。

头结点:为了操作方便,可以在单链表的第一个结点之前附设一个结点,该结点的数据域可以存储一些关于线性表长度的附加信息,也可以什么都不存。

首元素结点:线性表中的第一个结点成为首元素结点。

4、算法如下:

int Linser(SeqList *L,int X)

{ int i=0,k;

if(L->last>=MAXSIZE-1)

{ printf(表已满无法插入)

return(0);

}

while(ilast&&L->elem[i]<X)

i++;

for(k=L->last;k>=I;k–)

L->elem[k+1]=L->elem[k];

L->elem[i]=X;

L->last++;

return(1);

}

5、算法如下:

#define OK 1

#define ERROR 0

Int LDel(Seqlist *L,int i,int k)

{ int j;

if(i(L->last+2))

{ printf(输入的ik值不合法);

return ERROR;

}

if((i+k)==(L->last+2))

{ L->last=i-2;

ruturn OK;

}

else

{for(j=i+k-1;jlast;j++)

elem[j-k]=elem[j];

L->last=L->last-k;

return OK;

}

}

8、算法如下:

#define OK 1

#define ERROR 0

Int Delet(LInkList L,int mink,int maxk)

{ Node *p,*q;

p=L;

while(p->next!=NULL)

p=p->next;

if(minknext->data>=mink)||(p->data<=maxk))

{ printf(参数不合法);

return ERROR;

}

else

{ p=L;

while(p->next-data<=mink)

p=p->next;

while(q->data<maxk)

{ p->next=q->next;

free(q);

q=p->next;

}

return OK;

}

}

9、算法如下:

int Dele(Node *S)

{ Node *p;

P=s->next;

If(p= =s)

{printf(只有一个结点,不删除)

return 0;

}

else

{if((p->next= =s)

{s->next=s;

free(p);

return 1;

}

Else

{ while(p->next->next!=s)

P=p->next;

P->next=s;

Free(p);

return 1;

}

}

}

第三章习题答案

2、(1

3、栈有顺序栈和链栈两种存储结构。

在顺序栈中,栈顶指针top=-1时,栈为空;栈顶指针top=Stacksize-1时,栈为满。

在带头结点链栈中,栈顶指针top- next=NULL,则代表栈空;只要系统有可用空间,链栈就不会出现溢出,既没有栈满。

5

#include

#include “stdio.h”

void main( )

{

char ch,temp;

SeqStack s;

InitStack(&s);

scanf(“%c”,&ch);

while(ch!=’@’&&ch!=’&’)

{

Push(&s,ch);

scanf(“%c”,&ch);

}

while(ch!=’@’&&!IsEmpty(&s))

{

Pop(&s,&temp);

scanf(“%c”,&ch);

if(ch!=temp)

break;

}

if(!IsEmpty(&s))

printf(“no!\n”);

else

{

scanf(“%c”,&ch);

if(ch==’@’) printf(“yes!\n”);

else printf(“no!\n”);

}

}

12、(1)功能:将栈中元素倒置。

2)功能:删除栈中的e元素。

3)功能:将队列中的元素倒置。

第五章习题答案

1、(1)数组A共占用48*6=288个字节;

2)数组A的最后一个元素的地址为1282

3)按行存储时locA36=1000+[3-1*8+6-1]*6=1126

4)按列存储时locA36=1000+[6-1*6+3-1]*6=1192

9、(1)(ab)(2)((cd))(3)(b)(4b5)(d

10D

第六章习题答案

1、三个结点的树的形态有两个;三个结点的二叉树的不同形态有5个。

3、证明:分支数=n1+2n2++knk 1

n= n0+n1++nk 2

n=分支数+1 3

将(1)(2)代入(3)得

n0= n2+2n3+3n4++k-1nk+1

4、

注:C结点作为D的右孩子(画图的时候忘记了,不好意思)

5n0=50n2=n0-1=49,所以至少有99个结点。

6、(1)前序和后序相同:只有一个结点的二叉树

2)中序和后序相同:只有左子树的二叉树

3)前序和中序相同:只有右子树的二叉树

参考:

试找出满足下列条件的二叉树:

(1)先序序列与后序序列相同;

(2)中序序列与后序序列相同;

(3)先序序列与中序序列相同;

(4)中序序列与层次遍历序列相同。

解:

(1)若先序序列与后序序列相同,则或为空树,或为只有根结点的二叉树。

(2)若中序序列与后序序列相同,则或为空树,或为任一结点至多只有左子树的二叉树。

(3)若先序序列与中序序列相同,则或为空树,或为任一结点至多只有右子树的二叉树。

(4)若中序序列与层次遍历序列相同,则或为空树,或为任一结点至多只有右子树的二叉树。

7、证明:n个结点的K叉树共有nk个链域,分支数为n-1(即非空域)。

空域=nk-n-1=nk-n+1

8、对应的树如下:

9、(答案不唯一)

哈夫曼树如下图所示:

哈夫曼编码如下:

频率 编码

0.07 0010

0.19 10

0.02 00000

0.06 0001

0.32 01

0.03 00001

0.21 11

0.10 0011

11、对应的二叉树如下:

12、求下标分别为ij的两个桔点的最近公共祖先结点的值。

typedef int ElemType;

void Ancestor(ElemType A[],int n,int i,int j)

{while(i!=j)

if(i>j) i=i/2;

else j=j/2;

printf(“所查结点的最近公共祖先的下标是%d,值是%d”,i,A[i]);

}

15、编写递归算法,对于二叉树中每一个元素值为X的结点,删去以它为根的子树,并释放相应的空间。

void Del_Sub(BiTree T)

{ if(T->lchild) Del_Sub(T->lchild);

if(T->rchild) Del_Sub(T->rchild);

free(T);

}

void Del_Sub_x(BiTree T,int x)

{ if(T->data==x) Del_Sub(T);

else

{if(T->lchild) Del_Sub_x(T->lchild,x);

if(T->rchild) Del_Sub_x(T->rchild,x);

}

}

22

int Width(BiTree bt)

{if (bt==NULL) return (0);

else

{BiTree p,Q[50];

int front=1,rear=1,last=1;

int temp=0, maxw=0;

Q[rear]=bt;

while(front<=last)

{p=Q[front++]; temp++;

if (p->lchild!=NULL) Q[++rear]=p->lchild;

if (p->rchild!=NULL) Q[++rear]=p->rchild;

{last=rear;

if(temp>maxw) maxw=temp;

temp=0;}

}

return (maxw);

}

void Print_CSTree(CSTree T,int i)//按凹入表形式打印输出树的元素,i表示结点所在层次,初次调用时i=0 {

for(j=1;j<=i;j++) printf(" "); //留出i个空格以表现出层次 printf(“%c\n”,T->data); //打印元素,换行 for(p=T->firstchild;p;p=p->nextsib) Print_CSTree(p,i+1); //打印子树 }//Print_CSTree

}

第七章习题答案

1、(1)顶点1的入度为3,出度为0

顶点2的入度为2,出度为2

顶点3的入度为1,出度为2

顶点4的入度为1,出度为3

顶点5的入度为2,出度为1

顶点6的入度为2,出度为3

2)邻接矩阵如下:

0 0 0 0 0 0

1 0 0 1 0 0

0 1 0 0 0 1

0 0 1 0 1 1

1 0 0 0 0 0

1 1 0 0 1 0

3)邻接表

4)逆邻接表

2、答案不唯一

2)深度优先遍历该图所得顶点序列为:123456

边的序列为:(12)(23)(34)(45)(56

3)广度优先遍历该图所得顶点序列为:156324

边的序列为:(15)(16)(13)(12)(54

3、(1)每个事件的最早发生时间:ve(0)=0,ve(1)=5,ve(2)=6, ve(3)=12, ve(4)=15, ve(5)=16,

ve(6)=16, ve(7)=19, ve(8)=21, ve(9)=23

每个事件的最晚发生时间: vl(9)=23, vl(8)=21, vl(7)=19, vl(6)=19, vl(5)=16, vl(4)=15,

vl(3)=12, vl(2)=6, vl(1)=9, vl(0)=0

2)每个活动的最早开始时间:e(0,1)=0, e(0,2)=0, e(1,3)=5, e(2,3)=6, e(2,4)=6, e(3,4)=12, e(3,5)=12,

e(4,5)=15, e(3,6)=12, e(5,8)=16, e(4,7)=15, e(7,8)=19, e(6,9)=16, e(8,9)=21

每个活动的最迟开始时间:

l(0,1)=4, l(0,2)=0, l(1,3)=9, l(2,3)=6, l(2,4)=12, l(3,4)=12, l(3,5)=12, l(4,5)=15, l(3,6)=15, l(5,8)=16, l(4,7)=15,

l(7,8)=19, l(6,9)=19, l(8,9)=21

3)关键路径如下图所示:

4、顶点1到其余顶点的最短路经为:

1-3最短路经为13;长度为15

1-2最短路经为132;长度为19

1-5最短路经为135;长度为25

1-4最短路经为1324;长度为29

  1. 6最短路经为13246;长度为44

5.

6.

13A(7)B(3)C(2)D(11)E(8)

第八章查找

1、画出对长度为10的有序表进行折半查找的判定树,并求其等概率时查找成功的平均查找长度。

解:ASL=(1+2*2+4*3+3*4)/10=2.9

5、解:(1)插入完成后的二叉排序树如下:

ASL=(1+2*2+3*3+3*4+2*5+1*6)/12=3.5

ASL=(1+2*2+3*4+4*5)=37/12

12、解:哈希表构造如下:

0

1

2

3

4

5

6

7

8

9

10

22

41

30

01

53

46

13

67

H(22)=(22*3)%11=0

H(41)=(41*3)%11=2

H(53)=(53*3)%11=5

H(46)=(46*3)%11=6

H(30)=(30*3)%11=2 (41)冲突

H1(30)=(2+1)%11=3

H(13)=(13*3)%11=6 46冲突

H1(13)=(6+1)%11=7

H(01)=(01*3)%11=3 30冲突

H1(01)=(3+1)%11=4

H(67)=(67*3)%11=3 30冲突

H1(67)=(3+1)%11=4 01冲突

H2(67)=(3+2)%11=5 53冲突

H3(67)=(3+3)%11=6 46冲突

H4(67)=(3+4)%11=7 13冲突

H5(67)=(3+5)%11=8

ASLsucc=(1*4+2*3+6)/8=2

ASLunsucc=(2+8+7+6+5+4+3+2)/8=37/8

第九章排序

1、以关键字序列(503087512061908170897275653426)为例,手工执行以下排序算法,写出每一趟派结束时的关键字状态。

1)直接插入排序(2)希尔排序(增量序列为531

3)快速排序 4)堆排序(5)归并排序

解:

2)增量为5的排序结果:170087275061426503897512653908

增量为3的排序结果:061087275170426503897512653908

增量为1的排序结果:061087170275426503512653897908

3)一次划分后:{426 087 275 061 170}503{897 908 653 512}

分别进行:{170 087 275 061}426 503 {512 653} 897 {908}

{061 087}170{275}426 503 512 {653} 897 908

061 087 170 275 426 503 512 653 897 908

7、已知一组关键字:(4027281215507),要求采用快速排序法从小到大排序。请写出每趟排序后的划分结果。

解:初始状态:40 27 28 12 15 50 7

一次划分:{7 27 28 12 15} 40 {50}

依次划分:7 {27 28 12 15} 40 50

7 {15 12} 27 {28} 40 50

7 12 15 27 28 40 50

16、(1A3 B1 C4 D2 E7 (2)C (3)C

17、对,错,对

如有错误,请联系作者删除

并恳请同行朋友予以斧正,万分感谢!