《数据结构与算法》课后习题答案

数据结构

2.3 课后习题解答

2.3.2 判断题

1．线性表的逻辑顺序与存储顺序总是一致的。（×） 2．顺序存储的线性表可以按序号随机存取。（√）

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。（×）

4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（√）

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（×）

6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√） 7．线性表的链式存储结构优于顺序存储结构。（×）

8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。（√）

9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√） 10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（×）

11．静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。（×）

12．线性表的特点是每个元素都有一个前驱和一个后继。（×）

2.3.3 算法设计题

1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。 【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标端开始一边比较，一边移位）然后插入x ，最后修改表示表长的变量。 int insert (datatype A[],int *elenum,datatype x) /*设elenum为表的最大下标*/ {if (*elenum==arrsize-1) return 0; /*表已满，无法插入*/ else {i=*elenum;

while (i>=0 && A[i]>x) /*边找位置边移动*/

{A[i+1]=A[i]; i--; }

A[i+1]=x; /*找到的位置是插入位的下一位*/ (*elenum)++;

return 1; /*插入成功*/ } }

时间复杂度为O(n)。

数据结构

2．已知一顺序表A，其元素值非递减有序排列，编写一个算法删除顺序表中多余的值相同的元素。

【提示】对顺序表A，从第一个元素开始，查找其后与之值相同的所有元素，将它们删除；再对第二个元素做同样处理，依此类推。 void delete(Seqlist *A) {i=0;

while(i<A->last) /*将第i个元素以后与其值相同的元素删除

*/

{k=i+1; while(k<=A->last&&A->data[i]==A->data[k]) k++; /*使k指向第一个与A[i]不同的元素*/ n=k-i-1; /*n表示要删除元素的个数*/ for(j=k;j<=A->last;j++) A->data[j-n]=A->data[j]; /*删除多余元素*/ A->last= A->last -n; i++; }

}

3．写一个算法，从一个给定的顺序表A中删除值在x~y(x<=y)之间的所有元素，要求以较高的效率来实现。

【提示】对顺序表A，从前向后依次判断当前元素A->data[i]是否介于x和y之间，若是，并不立即删除，而是用n记录删除时应前移元素的位移量；若不是，则将A->data[i]向前移动n位。n用来记录当前已删除元素的个数。 void delete(Seqlist *A,int x,int y) {i=0; n=0;

while (i<A->last) {if (A->data[i]>=x && A->data[i]<=y) n++; /*若A->data[i] 介于x和y之间，n自增*/ else A->data[i-n]=A->data[i]; /*否则向前移动A->data[i]*/ i++; }

A->last-=n; }

4．线性表中有n个元素，每个元素是一个字符，现存于向量R[n]中，试写一算法，使R中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间，元素移动次数最小。

【提示】对线性表进行两次扫描，第一次将所有的字母放在前面，第二次将所有的数字放在字母之后，其它字符之前。 int fch(char c) /*判断c是否字母*/ {if(c>='a'&&c<='z'||c>='A'&&c<='Z') return (1); else return (0); }

int fnum(char c) /*判断c是否数字*/ {if(c>='0'&&c<='9') return (1);

数据结构

else return (0); }

void process(char R[n]) {low=0; high=n-1;

while(low<high) /*将字母放在前面*/

{while(low<high&&fch(R[low])) low++;

while(low<high&&!fch(R[high])) high--; if(low<high) {k=R[low];

R[low]=R[high]; R[high]=k; }

}

low=low+1; high=n-1;

while(low<high) /*将数字放在字母后面，其它字符前面*/ {while(low<high&&fnum(R[low])) low++; while(low<high&&!fnum(R[high])) high--; if(low<high)

{k=R[low];

R[low]=R[high]; R[high]=k; }

}

}

5．线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m个元素和后n个元素进行整体互换。即将线性表：

（a1, a2, … , am, b1, b2, … , bn）改变为： （b1, b2, … , bn , a1, a2, … , am）。

【提示】比较m和n的大小，若m<n，则将表中元素依次前移m次；否则,将表中元素依次后移n次。

void process(Seqlist *L,int m,int n)

{if(m<=n)

for(i=1;i<=m;i++) {x=L->data[0];

for(k=1;k<=L->last;k++) L->data[k-1]=L->data[k]; L->data[L->last]=x; } else for(i=1;i<=n;i++) {x=L->data[L->last]; for(k=L->last-1;k>=0;k- -) L->data[k+1]=L->data[k];

数据结构

L->data[0]=x; }

} 6．已知带头结点的单链表L中的结点是按整数值递增排列的，试写一算法，将值为x 的结点插入到表L中，使得L仍然递增有序，并且分析算法的时间复杂度。 LinkList insert(LinkList L, int x) {p=L; while(p->next && x>p->next->data) p=p->next; /*寻找插入位置*/ s=(LNode *)malloc(sizeof(LNode)); /*申请结点空间*/ s->data=x; /*填装结点*/ s->next=p->next; p->next=s; /*将结点插入到链表中*/ return(L);

}

7．假设有两个已排序（递增）的单链表A和B，编写算法将它们合并成一个链表C而不改变其排序性。

LinkList Combine(LinkList A, LinkList B)

{C=A; rc=C;

pa=A->next; /*pa指向表A的第一个结点*/ pb=B->next; /*pb指向表B的第一个结点*/ free(B); /*释放B的头结点*/

while (pa && pb) /*将pa、pb所指向结点中，值较小的一个插入到链表C的表尾*/ if(pa->data<pb->data)

{rc->next=pa; rc=pa;

pa=pa->next; } else

{rc->next=pb; rc=pb;

pb=pb->next; }

if(pa) rc->next=pa; else rc->next=pb; /*将链表A或B中剩余的部分链接到链表C的表尾*/ return(C);

}

8．假设长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某一结点的指针，编写算法删除该结点的前驱结点。

【提示】利用循环单链表的特点，通过s指针可循环找到其前驱结点p及p的前驱结点q，然后可删除结点*p。 viod delepre(LNode *s) {LNode *p, *q;

数据结构

p=s;

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

p=p->next; }

q->next=s; free(p); }

9．已知两个单链表A和B分别表示两个集合，其元素递增排列，编写算法求出A和B的交集C，要求C同样以元素递增的单链表形式存储。

【提示】交集指的是两个单链表的元素值相同的结点的集合，为了操作方便，先让单链表C带有一个头结点，最后将其删除掉。算法中指针p用来指向A中的当前结点，指针q用来指向B中的当前结点，将其值进行比较，两者相等时，属于交集中的一个元素，两者不等时，将其较小者跳过，继续后面的比较。 LinkList Intersect(LinkList A, LinkList B)

{LNode *q, *p, *r, *s; LinkList C;

C= (LNode *)malloc(sizeof(LNode)); C->next=NULL; r=C; p=A; q=B;

while (p && q )

if (p->data<q->data) p=p->next; else if (p->data==q->data)

{s=(LNode *)malloc(sizeof(LNode)); s->data=p->data; r->next=s; r=s; p=p->next; q=q->next; }

else q=q->next;

r->next=NULL; C=C->next; return C; }

10．设有一个双向链表，每个结点中除有prior、data和next域外，还有一个访问频度freq域，在链表被起用之前，该域的值初始化为零。每当在链表进行一次Locata(L,x)运算后，令值为x的结点中的freq域增1，并调整表中结点的次序，使其按访问频度的非递增序列排列，以便使频繁访问的结点总是靠近表头。试写一个满足上述要求的Locata(L,x)算法。 【提示】在定位操作的同时，需要调整链表中结点的次序：每次进行定位操作后，要查看所查找结点的freq域，将其同前面结点的freq域进行比较，同时进行结点次序的调整。 typedef struct dnode

数据结构

{datatype data; int freq;

struct DLnode *prior,*next; }DLnode,*DLinkList;

DlinkList Locate(DLinkList L, datatype x) {p=L->next;

while(p&&p->data!=x) p=p->next; if(!p) return(NULL);

p->freq++;

while(p->prior!=L&&p->prior->freq<p->freq) {k=p->prior->data;

p->prior->data=p->data; p->data=k;

k=p->prior->freq;

p->prior->freq=p->freq; p->freq=k; p=p->prior;

} return(p);

}

/*查找值为x的结点，使p指向它*/ /*若查找失败，返回空指针*/ /*修改p的freq域*/ /*调整结点的次序*/

/*返回找到的结点的地址*/

3.3 课后习题解答 ##

3.3.1 选择题

1．向一个栈顶指针为Top的链栈中插入一个p所指结点时，其操作步骤为（C）。 A．Top->next=p; B．p->next=Top->next;Top->next=p; C．p->next=Top;Top=p; D．p->next=Top;Top=Top->next;

2．对于栈操作数据的原则是（B）。

A．先进先出 B．后进先出 C．后进后出 D．不分顺序

3．若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是（D）。

A．i B．n-i C． n-i+1 D．不确定 4．表达式a*(b－c)＋d的后缀表达式是（B）。

A．abcd*-+ B．abc-*d+ C．abc*-d+ D．+-*abcd

5．采用顺序存储的两个栈共享空间S[1..m]，top[i]代表第i个栈( i=1,2)的栈顶，栈1的底在S[1]，栈2的底在S[m]，则栈满的条件是（B）。

A．top[2]-top[1]|=0 B．top[1]+1=top[2] C．top[1]+top[2]=m D．top[1]=top[2]

6．一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（C）。 A． edcba B． decba C．dceab D． abcde

7．在一个链队列中，若f,r分别为队首、队尾指针，则插入s所指结点的操作为（B）。 A．f->next=r;f=s; B．r->next=s;r=s; C．s->next=r;r=s; D．s->next=f;f=s;

8．用不带头结点的单链表存储队列时，在进行删除运算时（D）。

数据结构

A．仅修改头指针 B．仅修改尾指针

C．头、尾指针都要修改 D．头、尾指针可能都要修改

9．递归过程或函数调用时，处理参数及返回地址，要用一种称为（C）的数据结构。 A．队列 B．静态链表 C．栈 D．顺序表 10．栈和队都是（C）。

A．顺序存储的线性结构 B．链式存储的非线性结构 C．限制存取点的线性结构 D．限制存取点的非线性结构

3.3.2 判断题

1．栈和队列的存储，既可以采用顺序存储结构，又可以采用链式存储结构。（√） 2．任何一个递归过程都可以转换成非递归过程。（√）

3．若输入序列为1,2,3,4,5,6，则通过一个栈可以输出序列3,2,5,6,4,1。（√） 4．通常使用队列来处理函数的调用。（×）

5．循环队列通常用指针来实现队列的头尾相接。（×）

3.3.3 简答题

1．循环队列的优点是什么？如何判别它的空和满？ 循环队列的优点是能够克服“假溢满”现象。 设有循环队列sq，队满的判别条件为：

（sq->rear+1）%maxsize==sq->front;或sq->num==maxsize。 队空的判别条件为： sq->rear==sq->front。

2．栈和队列数据结构各有什么特点，什么情况下用到栈，什么情况下用到队列？ 栈和队列都是操作受限的线性表，栈的运算规则是“后进先出”，队列的运算规则是“先进先出”。栈的应用如数制转换、递归算法的实现等，队列的应用如树的层次遍历等。

3．什么是递归？递归程序有什么优缺点？

一个函数在结束本函数之前，直接或间接调用函数自身，称为递归。例如，函数f在执行中，又调用函数f自身，这称为直接递归；若函数f在执行中，调用函数g，而g在执行中，又调用函数f，这称为间接递归。在实际应用中，多为直接递归，也常简称为递归。

递归程序的优点是程序结构简单、清晰，易证明其正确性。缺点是执行中占内存空间较多，运行效率低。

4．设有编号为1,2,3,4的四辆车，顺序进入一个栈式结构的站台，试写出这四辆车开出车站的所有可能的顺序（每辆车可能入站，可能不入站，时间也可能不等）。

1234,1243,1324,1342,1432,213,2143,2314,2341,2431,3214,3241,3421,4321

4.3 课后习题解答###

4.3.1 选择题

1．下面关于串的叙述错误的是（C）。 A．串是字符的有限序列

B．串既可以采用顺序存储，也可以采用链式存储 C．空串是由空格构成的串

D．模式匹配是串的一种重要运算 2．串的长度是指（B）。

A．串中所含不同字母的个数 B．串中所含字符的个数

数据结构

C．串中所含不同字符的个数 D．串中所含非空格字符的个数 3．已知串S=‘aaab’,其Next数组值为（A）。

A．0123 B．1123 C．1231 D．1211

4．二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要（D）个字节；M的第8列和第5行共占（A）个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的（C）元素的起始地址一致。

（1）A．90 B．180 C．240 D．540 （2）A．108 B．114 C．54 D．60

（3）A．M[8][5] B．M[3][10] C．M[5][8] D．M[0][9]

5．数组A中，每个元素的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（C），若该数组按行存放，元素A[8][5]的起始地址是（D），若该数组按列存放，元素A[8][5]的起始地址是（B）。

（1）A．80 B．100 C．240 D．270 （2）A．SA+141 B．SA+144 C．SA+222 D．SA+225 （3）A．SA+141 B．SA+180 C．SA+117 D．SA+225 6．稀疏矩阵采用压缩存储，一般有（C）两种方法。 A．二维数组和三维数组 B．三元组和散列 C．三元组表和十字链表 D．散列和十字链表

4.3.2 判断题

1．串相等是指两个串的长度相等。（×）

2．KMP算法的特点是在模式匹配时指示主串的指针不会变小。（√） 3．稀疏矩阵压缩存储后，必会失去随机存取功能。（√）

4．数组是线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（×）

5．若采用三元组存储稀疏矩阵，把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。（×）

6．若一个广义表的表头为空表，则此广义表亦为空表。（×） 7．所谓取广义表的表尾就是返回广义表中最后一个元素。（×）

4.3.3 简答题

1．KMP算法较朴素的模式匹配算法有哪些改进?

KMP算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP算法的优点更为突出。

2．设字符串S=‘aabaabaabaac'，P=‘aabaac'。 （1）给出S和P的next值和nextval值；

（2）若S作主串，P作模式串，试给出利用KMP算法的匹配过程。 【解答】

（1）S的next与nextval值分别为012123456789和002002002009，p的next与nextval值分别为012123和002003。

（2）利用BF算法的匹配过程： 利用KMP算法的匹配过程：

第一趟匹配：aabaabaabaac 第一趟匹配：aabaabaabaac

aabaac(i=6,j=6) aabaac(i=6,j=6)

数据结构

第二趟匹配：aabaabaabaac 第二趟匹配：aabaabaabaac aa(i=3,j=2) (aa)baac

第三趟匹配：aabaabaabaac 第三趟匹配：aabaabaabaac a(i=3,j=1) (成功) (aa)baac 第四趟匹配：aabaabaabaac aabaac(i=9,j=6) 第五趟匹配：aabaabaabaac aa(i=6,j=2) 第六趟匹配：aabaabaabaac a(i=6,j=1) 第七趟匹配：aabaabaabaac

(成功) aabaac(i=13,j=7)

3．假设按行优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址是100，每个整数占４个字节。问下列元素的存储地址是什么？

(1) a0000 (2)a1111 (3)a3125 (4)a8247

【解答】(1) LOC( a0000)= 100

(2) LOC( a1111)=100+(3*5*8*1+5*8*1+8*1+1)*4=776 (3) LOC( a3125)=100+(3*5*8*3+5*8*1+8*2+5) *4=1784 (4) LOC( a8247)= 100+(3*5*8*8+5*8*2+8*4+7) *4=4816 4．假设一个准对角矩阵：

a11 a12

a21 a22

a33 a34

a43 a44

….

aij

a2m-1,2m-1 a2m-1,2m

a2m,2m-1 a2m,2m

按以下方式存储于一维数组B[4m]中（m为一个整数）：

写出下标转换函数k=f(i,j)。 【解答】

由题目可知，每一行有两个非0元素。

当i为奇数时，第i行的元素为：ai,i、ai,(i+1)，此时k=2*(i-1)+j-i=i+j-2 当i为偶数时，第i行的元素为：ai,(i-1)、ai,i，此时k=2*(i-1)+j-I+1=i+j-1 综上所述，k=i+j-i%2-1。

5．设有n×n的带宽为3的带状矩阵A，将其3条对角线上的元素存于数组B[3][n]中，使得元素B[u][v]=aij，试推导出从（i,j）到 (u,v)的下标变换公式。 【解答】

u=j-i+1 v=j-1

数据结构

6．现有如下的稀疏矩阵A（如图所示），要求画出以下各种表示方法。 （1）三元组表表示法 （2）十字链表法。

【解答】

0 0 0 22 0 -15 0 13 3 0 0 0 0 0 0 -6 0 0 0 0 0

0 0 0 91 0 0 0 0 0 0 0 28 0 0 0

（1）三元组表表示法:

（2）十字链表法：

0 1 2

3 4 5

数据结构

7．画出下列广义表的头尾表示存储结构示意图。 （1）A=((a,b,c),d,(a,b,c)) （2）B=(a,(b,(c,d),e),f) （1）

（2）

5.3 课后习题解答

5.3.1 选择题

1．下列说法正确的是（C）。

A．二叉树中任何一个结点的度都为2 B．二叉树的度为2

C．一棵二叉树的度可小于2

D．任何一棵二叉树中至少有一个结点的度为2

2．以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中（n>0），空链域的个数为（C）。

A．2n-1 B．n-1 C．n+1 D．2n+1

3．线索化二叉树中，某结点*p没有孩子的充要条件是（B）。 A．p->lchild=NULL B．p->ltag=1且p->rtag=1

C．p->ltag=0 D．p->lchild=NULL 且p->ltag=1 4．如果结点A有3个兄弟,而且B是A的双亲,则B的度是（B）。 A．3 B．4 C．5 D．1 5．某二叉树T有n个结点,设按某种顺序对T中的每个结点进行编号，编号值为1,2,...n。且有如下性质:T中任意结点v,其编号等于左子树上的最小编号减１,而v的右子树的结点中,其最小编号等于v左子树上结点的最大编号加１，这是按（B）编号的。

A． 中序遍历序列 B． 先序遍历序列 C． 后序遍历序列 D． 层次顺序

6．设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点,B中右指针域为空的结点有（C）个。

A．n-1 B． n C． n+1 D．n+2

数据结构

7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（C）。 A． 500 B． 501 C．490 D．495

8．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为N1，N2和N3。与森林F对应的二叉树根结点的右子树上的结点个数是（D）。

A．N1 B．N1+N2 C．N2 D．N2+N3

9．任何一棵二叉树的叶结点在先序、中序、后序遍历序列中的相对次序（A）。 A．不发生改变 B． 发生改变 C． 不能确定 D． 以上都不对

10．若一棵二叉树的后序遍历序列为dabec，中序遍历序列为debac，则先序遍历序列

为（D）。

A．cbed B．decab C．deabc D．cedba

11．若一棵二叉树的先序遍历序列为abdgcefh，中序遍历的序列为dgbaechf，则后序遍历的结果为（D）。

A． gcefha B． gdbecfha C． bdgaechf D． gdbehfca

12．一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（B）。

A．所有的结点均无左孩子 B．所有的结点均无右孩子 C．只有一个叶子结点 D．是一棵满二叉树 13．引入线索二叉树的目的是（A）。 A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 14．设高度为h的二叉树上只有度为０和度为２的结点，则此类二叉树中所包含的结点数至少为（B）。

A．2*h B． 2*h-1 C． 2*h+1 D．h+1 15．一个具有567个结点的二叉树的高h为（D）。

A．9 B．10 C．9至566之间 D．10至567之间 16．给一个整数集合{3，5，6，7，9}，与该整数集合对应的哈夫曼树是（B）。 A．

5.3.2 判断题

1．二叉树是树的特殊形式。（√）

2．由树转换成二叉树，其根结点的右子树总是空的。（√）

3．先根遍历一棵树和先序遍历与该树对应的二叉树，其结果不同。（×） 4．先根遍历森林和先序遍历与该森林对应的二叉树，其结果不同。（×） 5．完全二叉树中，若一个结点没有左孩子，则它必是叶子。（√） 6．对于有N个结点的二叉树，其高度为 log2N ＋1。（×）

7．若一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的

数据结构

先序遍历序列中的最后一个结点。（√）

8．若一个结点是某二叉树子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。（√）

9．不使用递归也可实现二叉树的先序、中序和后序遍历。（√） 10．先序遍历二叉树的序列中，任何结点的子树的所有结点不一定跟在该结点之后。（×） 11．先序和中序遍历用线索树方式存储的二叉树，不必使用栈。（×）

12．在后序线索二叉树中，在任何情况下都能够很方便地找到任意结点的后继。（×） 13．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。（√） 14．在哈夫曼编码中，出现频率相同的字符编码长度也一定相同。（×） 15．用一维数组存放二叉树时，总是以先序遍历存储结点。（×） 16．由先序序列和后序序列能唯一确定一棵二叉树。（×） 17．由先序序列和中序序列能唯一确定一棵二叉树。（√） 18．对一棵二叉树进行层次遍历时，应借助于一个栈。（×）

19．完全二叉树可采用顺序存储结构实现存储，非完全二叉树则不能。（×） 20．满二叉树一定是完全二叉树，反之未必。（√）

5.3.3 简答题

1．一棵度为2的树与一棵二叉树有何区别？树与二叉树之间有何区别？ 【解答】

①二叉树是有序树，度为2的树是无序树，二叉树的度不一定是2。

②二叉树是有序树，每个结点最多有两棵子树，树是无序树，且每个结点可以有多棵子树。 2．对于图1所示二叉树，试给出： （1）它的顺序存储结构示意图； （2）它的二叉链表存储结构示意图； （3）它的三叉链表存储结构示意图。

【解答】

（

(图 1)

（2）二叉链表存储结构示意图： （3）三叉链表存储结构示意图：

3．对于图2所示的树，试给出：

（1）双亲数组表示法示意图；

（2）孩子链表表示法示意图；

（3）孩子兄弟链表表示法示意图。

【解答】

（1）双亲数组表示法示意图： （2）孩子链表表示法示意图： (图 2)

数据结构

（3）孩子兄弟链表表示法示意图：

4．画出图3所示的森林经转换后所对应的二叉树，并指出森林中满足什么条件的结点在二叉树中是叶子。

(图 3)【解答】

数据结构

在二叉树中某结点所对应的森林中结点为叶子结点的条件是该结点在森林中既没有孩子也没有右兄弟结点。

5．将题

(题5图)

【解答】森林：

6．证明：在结点数多于1的哈夫曼树中不存在度为1的结点。 证明：由哈夫曼树的构造过程可知，

哈夫曼树的每一分支结点都是由两棵子树合并产生的新结点，其度必为2，所以哈夫曼树中不存在度为1的结点。

7．证明：若哈夫曼树中有n个叶结点，则树中共有2n－1个结点。

证明：n个叶结点，需经n-1次合并形成哈夫曼树，而每次合并产生一个分支结点，所以树中共有2n-1个结点。

8．证明：由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树。

证明：给定二叉树结点的前序序列和对称序（中序）序列，可以唯一确定该二叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（设l个元素）表示左子树，若左边无元素，则说明左子树为空；右边（设r个元素）是右子树，若为空，则右子树为空。根据前序遍历中“根—左子树—右子树”的顺序，则由从第二元素开始的l个结点序列和中序序列根左边的l个结点序列构造左子树，由前序序列最后r个元素序列与中序序列根右边的r个元素序列构造右子树。

9．已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，……，nm个度为m的结点，问该树中共有多少个叶子结点？有多少个非终端结点？

解：设树中共有n个结点，n0个叶结点，那么

n=n0+n1+…+nm (1)

树中除根结点外，每个结点对应着一个分支，而度为k的结点发出k个分支，所以： n=n1+2*n2+…+m*nm+1 (2)

由(1)、(2)可知n0= n2+2*n3+3*n4+…+(m-1)*nm+1

10．在具有n（n>1）个结点的树中，深度最小的那棵树其深度是多少？它共有多少叶子和非叶子结点？深度最大的那棵树其深度是多少？它共有多少叶子和非叶子结点？

2; n-1; 1; n; 1, n-1 11．设高度为h的二叉树上只有度为0和度为2的结点，问该二叉树的结点数可能达到的最大值和最小值。

最大值：2h-1； 最小值：2h-1

数据结构

12．求表达式： a＋b*(c－d)－e/f的波兰式（前缀式）和逆波兰式（后缀式）。 波兰式： - + a * b – c d / e f 逆波兰式：a b c d - * + e f / - 13．画出和下列已知序列对应的树T：

树的先根次序访问序列为：GFKDAIEBCHJ； 树的后根访问次序为：DIAEKFCJHBG。

【解答】对应的二叉树和树分别如下左、右图所示：

14．画出和下列已知序列对应的森林F：

森林的先根次序访问序列为：ABCDEFGHIJKL； 森林的后根访问次序为：CBEFDGAJIKLH。

15．画出和下列已知序列对应的树T：

二叉树的层次访问序列为：ABCDEFGHIJ； 二叉树的中序访问次序为：DBGEHJACIF。

【解答】

按层次遍历，第一个结点（若树不空）为根，该结点在中序序列中把序列分成左右两部分—左子树和右子树。若左子树不空，层次序列中第二个结点左子树的根；若左子树为空，则层次序列中第二个结点右子树的根。对右子树也作类似的分析。层次序列的特点是：从左到右每个结点或是当前情况下子树的根或是叶子。

16．假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成。它们在电文中出现的频度分别为{0.31,0.16,0.10,0.08,0.11,0.20,0.04}, （1）为这7个字母设计哈夫曼编码。

数据结构

（2）对这7个字母进行等长编码，至少需要几位二进制数？哈夫曼编码比等长编码使电文总长压缩多少？

（1）哈夫曼树： a：10 b：110

c：010

d：1110

e：011

f：00

g：1111

（2）对这7个字母进行等长编码，至少需要3位二进制数。

等长编码的平均长度：0.31*3+0.16*3+0.10*3+0.08*3+0.11*3+0.20*3+0.04*3=3 哈夫曼编码：0.31*2+0.16*3+0.10*3+0.08*4+0.11*3+0.20*2+0.04*4=2.54 哈夫曼编码比等长编码使电文总长压缩了：1 - 2.54/3=15.33%

5.3.4 算法设计题

1．给定一棵用二叉链表表示的二叉树，其根指针为root，试写出求二叉树结点的数目的算法。

【提示】采用递归算法实现。

int count(BiTree root)

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

return (count(root->lchild)+count(root->rchild)+1);

} 2．请设计一个算法，要求该算法把二叉树的叶结点按从左至右的顺序链成一个单链表。二叉树按lchild-rchild方式存储，链接时用叶结点的rchild域存放链指针。

【提示】这是一个非常典型的基于二叉树遍历算法，通过遍历找到各个叶子结点，因为不论前序遍历、中序遍历和后序遍历，访问叶子结点的相对顺序都是相同的，即都是从左至右。而题目要求是将二叉树中的叶子结点按从左至右顺序建立一个单链表，因此，可以采用三种遍历中的任意一种方法遍历。这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。 LinkList head,pre=NULL; /*全局变量*/ LinkList InOrder(BiTree T)

/*中序遍历二叉树T，将叶子结点从左到右链成一个单链表，表头指针为head*/ { if(T) { InOrder(T->lchild);

if (T->lchild==NULL && T->rchild==NULL) if (pre==NULL) { head=T; pre=T; } else { pre->rchild=T;

/*中序遍历左子树*/ /*当前是叶子结点*/

二叉树结点的数目＝

当二叉树为空

左子树结点数目＋右子树结点数目＋1 当二叉树非空

/*处理第一个叶子结点*/

数据结构

pre=T; }

InOrder(T->rchild); pre->rchild=NULL; return(head); }

/*将叶子结点链入链表*/ /*中序遍历右子树*/ /*设置链表尾结点*/

3．给定一棵用二叉链表表示的二叉树，其根指针为root，试写出求二叉树的深度的算法。

【提示】采取递归算法。

int Height(BiTree root) { int hl,hr;

if (root==NULL) return(0); else { hl=Height(root->lchild);

hr=Height(root->rchild); if (hl>hr) return (hl+1); else return(hr+1); }

}

4．给定一棵用二叉链表表示的二叉树，其根指针为root，试求二叉树各结点的层数。 【提示】采用先序递归遍历算法实现。

二叉树结点的层次数＝

1

当结点为根结点 当结点非根结点

其双亲结点的层次数＋1

void fun (BiTree root, int n) { if (t==NULL) return;

else{ printf(―%d‖,n);

fun(root->lchild,n+1); fun(root->rchild,n+1);

}

}

5．给定一棵用二叉链表表示的二叉树，其根指针为root，试写出将二叉树中所有结点的左、右子树相互交换的算法。

【提示】设root 为一棵用二叉链表存储的二叉树，则交换各结点的左右子树的运算可基于后序遍历实现：交换左子树上各结点的左右子树；交换左子树上各结点的左右子树；再交换根结点的左右子树。

void Exchange(BiTree root) { BiTNode *p;

if (root)

{ Exchange(root->lchild);

Exchange(root->rchild); p=root->lchild;

root->lchild=root->rchild;

root->rchild=p; }

}

数据结构

6．一棵具有n个结点的完全二叉树采用顺序结构存储，试设计非递归算法对其进行先序遍历。 【提示】二叉树的顺序存储是按完全二叉树的顺序存储格式按层次存储的，双亲结点与子女结点的下标间有确定的关系。对顺序存储结构的二叉树进行先序遍历，与二叉链表存放二叉树的遍历策略类似。但是在顺序存储结构下，判二叉树结点为空的条件为：结点下标大于n，或结点值为0（一般二叉树中的“虚结点”）。 void PreOrder (datatype data[n+1]) /*0号单元未用*/ { int stack[n] ; int top; if(n<1) return; t=1; top=0;

while (t<=n||top>0)

{ while (t<=n&&data[t]!=0)

{ Visite(data[t]);

stack[top]=t; top++; t=t*2; }

if (top<=0) return;

else { top--; t=stack[top]; t=t*2+1; } }

z7．二叉树中查找值为x的结点，试设计打印值为x 的结点的所有祖先结点算法。 【提示】对二叉树进行先序非递归遍历，查找值为x的结点。进入子树时，将子树的根压栈；从子树返回时，将栈顶元素出栈。当找到值为x的结点时，栈中存放的就是其祖先结点，依次打印各结点的值。

void PrintNode (BiTree T, datatype x)

{ Init_Stack(S); /*初始化空栈*/ p=T;

while (p|| !Empty_Stack(S)) /*若p非空，或栈非空*/ { while (p)

{ if (p->data==x) /*若当前结点值为x，依次输出栈中元素的值*/

{ while (!Empty_Stack(S)) { Pop(S,q);

printf(q->data); } return;

}

else{ Push_Stack(S,p);} /*若当前结点值不是x，压栈*/

p=p->lchild; }

if(!Empty_Stack(S))

{ Pop_Stack(S,r); /*当栈非空，栈顶元素出栈，进入右子树*/

p=r->rchild; } else return;

}

数据结构

}

}

8．已知一棵二叉树的后序遍历序列和中序遍历序列，写出可以确定这棵二叉树的算法。

【提示】根据后序遍历和中序遍历的特点，采用递归算法实现。 void InPost (char in [ ] , char post [ ] , int il , int ir, int pl, int pr, BiTree t)

/*数组in和数组post中存放着二叉树的中序遍历序列和后序遍历序列，il和ir表示中序遍历序列的左右端*/

/*点， pl和 pr表示后序遍历序列的左右端点，t表示二叉树的根*/

{ t=(BiTNode *) malloc(sizeof(BiTNode)); }

9．编写算法判断一棵二叉链表表示的二叉树是否是完全二叉树。

【提示】根据完全二叉树的定义可知，对完全二叉树按照从上到下，从左到右的次序遍历应满足：①若某结点没有左孩子，则一定无右孩子；②若某结点缺（左或右）孩子，则其所有后继一定无孩子。因此，可采用按层次遍历二叉树的方法依次对每个结点进行判断。这里增加一个标志以表示所有已扫描过的结点均有左、右孩子，将局部判断结果存入CM中，CM表示整个二叉树是否是完全二叉树，B为1表示到目前为止所有结点均有左右孩子。 int CompleteBT(BiTree T) { Init_Queue(Q); /*初始化队列Q*/

B=1; CM=1;

if (T!=NULL) { In_Queue(Q,T);

while(!Empty_Queue(Q)) /*当队列不为空时执行循环*/ { p=Out_Queue(Q); if(p->lchild==NULL) { B=0; /*B=0表示缺少左、右孩子*/ if(rchild!=NULL) CM=0; /*CM=0表示不是完全二叉树*/

}

else {CM=B;

In_Queue(Q,p->lchild); /*左孩子入队列*/ if(p->rchild==NULL) B=0; else In_Queue(Q,p->rchild); /*右孩子入队列*/

}

}

return(CM);

}

t->data=post[pr]; m=il;

while (in[m]!=post [pr] ) m++; if (m== il) if (m==ir)

t->lchild=NULL ; t->rchild=NULL;

else InPost ( in, post,il,m-1,pl,pl+m-1-il, t->lchild);

else InPost (in,post,m+1,ir,pr-ir+m,pr-1,t->rchild);

数据结构

}

10．有n个结点的完全二叉树存放在一维数组A[1..n]中，试据此建立一棵用二叉链表表示的二叉树。

BiTree Create(dataype A[],int i)

/*n个结点的完全二叉树存于一维数组A中，据此建立以二叉链表表示的完全二叉树,初始调用时,i=1*/

{ BiTree T; if (i<=n)

{ T=(BiTree)malloc(sizeof(BiTNode));

T->data=A[i];

if (2*i>n) T->lchild=NULL; else T->lchild=Create(A,2*i); if (2*i+1>n) T->rchild=NULL;

else T->rchild=Create(A,2*i+1); }

return (T); }

11．编写算法判定两棵二叉树是否相似。所谓两棵二叉树s和t相似，即要么它们都为空或都只有一个结点，要么它们的左右子树都相似。 【提示】两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。

int Similar(BiTree s, BiTree t)

{ if(s==NULL && q==NULL) return (1);

else if(!s && t || s && !t) return (0);

else return(Similar(s->lchild,t->lchild) && Similar(s->rchild,t->rchild)) }

12．写出用逆转链方法对二叉树进行先序遍历的算法。

【提示】用逆转链的方法遍历二叉树，不需要附加的栈空间，而是在遍历过程中沿结点的左右子树下降时，临时改变结点lchild或者rchild的值，使之指向双亲，从而为以后的上升提供路径，上升时再将结点的lchild或者rchild恢复。

typedef struct tnode { datatype data;

int tag; /*tag的值初始为0，进入左子树时置1，从左子树回来时，再恢复为0*/ struct tnode *lchild, *rchild; } Bnode, *Btree;

void PreOrder(Btree bt)

{ Bnode *r, *p, *q; /*p指向当前结点，r指向p的双亲，q指向要访问的下一结点*/ if(bt==NULL) return; p=bt; r= NULL: while( p)

{ Visit(p); /*访问p所指结点*/ if(p->lchild) /*下降进入左子树*/ { p->tag=1; q=p->lchild; q=p->lchild=r; r=p; p=q; }

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