《数据结构与算法》课后习题答案教学教材.pdf

《《数据结构与算法》课后习题答案教学教材.pdf》由会员分享，可在线阅读，更多相关《《数据结构与算法》课后习题答案教学教材.pdf（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 数据结构与算法课后习题答案精品文档2.3课后习题解答2.3.2判断题1 .线性表的逻辑顺序与存储顺序总是一致的。（X）2.顺序存储的线性表可以按序号随机存取。（J）3.顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。（X）4.线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（J）5.在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（X）6.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（J）7.线性表的链式存储结构优于顺序存储结构。（义）8.在线性表的顺序存储结

2、构中，插入和删除时移动元素的个数与该元素的位置有关。（J）9.线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（V）10.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（X）11.静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i 个元素的时间与i 无关。（X）12.线性表的特点是每个元素都有一个前驱和一个后继。（X）2.3.3算法设计题1.设线性表存放在向量Aarrsize的前elenum个分量中，且递增有序。试写一算法，将 x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。【提示】直接

3、用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标端开始一边比较，一边移位）然后插入x,最后修改表示表长的变量。int insert（datatype A,int*elenum,datatype x）/*设 elenum为表的最大下标*/if(*elenum=arrsize-l)return 0;法插入*/else i=*elenum;whil

4、e(i=0&Aix)移动*/Ai+l=Ai;i；/*表已满，无/*边找位置边收集于网络，如有侵权请联系管理员删除精品文档Ai+l=x;/*找到的位置是插入位的下一位*/(*elenum)+；return 1;/*插入成功*/时间复杂度为0(n)。2.已知一顺序表A,其元素值非递减有序排列，编写一个算法删除顺序表中多余的值相同的元素。【提示】对顺序表A,从第一个元素开始，查找其后与之值相同的所有元素，将它们删除；再对第二个元素做同样处理，依此类推。void delete(Seqlist*A)i=0;while(ilast)/*将 第 i 个元素以后与其值相同的元素删除k=i+l;while(kl

5、ast&A-datai=A-datak)k+;/*使 k 指 向第个与Ai不同的元素*/n=k-i-l;for(j=k;jlast;j+)A-dataj-n=A-dataj;A-last=A-last-n;i+；/*n 表示要删除元素的个数*/*删除多余元素*/3.写一个算法，从一个给定的顺序表A 中删除值在xy(xdatai是否介于x 和 y 之间，若是，并不立即删除，而是用n记录删除时应前移元素的位移量；若不是，则将A-data用向前移动n位。n用来记录当前已删除元素的个数。void delete(Seqlist*A,int x,int y)i=0;n=0;while(ilast)if(A

6、-datai=x&A-datafidatai介于 x 和 y 之间，n 自增*/else A-datai-n=A-datai;i+；/*否则向前移动A-datai*/A-last-=n;收集于网络，如有侵权请联系管理员删除精品文档4.线性表中有n 个元素，每个元素是一个字符，现存于向量Rn中，试写一算法，使 R 中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间，元素移动次数最小。【提示】对线性表进行两次扫描，第一次将所有的字母放在前面，第二次将所有的数字放在字母之后，其它字符之前。int fch(char c)/*判断c是 否 字 母*/if(c=,a,&c=,A,&c

7、=0&c=9)return(1);else return(0);)void process(char Rn)low=0;high=n-1;while(lowhigh)/*将 字 母 放 在 前 面*/while(loww+;while(lowhigh&!fch(Rhigh)high;if(lowhigh)k=Rlow;Rlow=Rhigh;Rhigh=k;)low=low+l;high=n-l;while(lowhigh)/*将 数 字 放 在 字 母 后 面，其 它 字 符 前 面*/while(lowhigh&fnum(Rlow)low+;while(lowhigh&!fnum(Rhigh

8、)high;if(lowhigh)k=Rlow;Rlow=Rhighl;Rhigh=k;5.线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m 个元素和后n 个元素进行整体互换。即将线性表：(ai,a2,.,am,bi,bs,.,bn)改变为：(b i,b 2,，b n,a i,a 2,，a m)【提示】比较m 和 n 的大小，若 m n,则将表中元素依次前移m 次；否则，将表中元素依次后移n次。收集于网络，如有侵权请联系管理员删除精品文档void process(Seqlist*L,int m,int n)if(m=n)fbr(i=l;idata0;for(k=1;kla

9、st;k+)L-datak-l=L-datafk;L-dataL-last=x;else for(i=l;idataL-last;for(k=L-last-l;k=0;k-)L-datak+l=L-datak;L-dataO=x;6.已知带头结点的单链表L 中的结点是按整数值递增排列的，试写一算法，将值为x的结点插入到表L 中，使得L 仍然递增有序，并且分析算法的时间复杂度。LinkList insert(LinkList L,int x)P=L；while(p-next&xp-next-data)p=p-next;s=(LNode*)malloc(sizeof(LNode);s-data=x

10、;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;pb=B-next;free(B);while(pa&pb)if(pa-datadata)rc-next=pa;rc=pa;pa=pa-next;/*寻找插入位置*/*申请结点空间*/*填装结点*/编写算法将它们合并成一/*pa指向表A的第一个结点*/*pb指向表B的第一一个结点*/*释放B的头结点*/*将pa、pb所

11、指向结点中，值较小的一个插入到链表C的表尾*/elserc-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;

12、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,*

13、p,*r,*s;LinkList C;C=(LNode*)malloc(sizeof(LNode);C-next=NULL;r=C;P=A;q=B;while(p&q)if(p-datadata)p=p-next;else if(p-data=q-data)s=(LNode*)malloc(sizeof(LNode);s-data=p-data;r-next=s;s;p=p-next;q=q-next;收集于网络，如有侵权请联系管理员删除精品文档else q=q-next;r-next=NULL;C=C-next;return C;)1 0.设有一个双向链表，每个结点中除有prior、data

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

15、next;DLnode,*DLinkList;DlinkList Locate(DLinkList L,datatype x)p=Lnext;while(p&p-data!=x)p=p-next;它*/if(!p)return(NULL);*/p-freq+；/*查找值为X的结点，使p指向/*若查找失败，返回空指针/*修改p的freq域while(p-prior!=L&p-prior-freqfreq)/*调整结点的次序*/k=pprior-data;p-prior-data=p-data;p-data=k;k=p-prior-freq;p-prior-freq=p-freq;p-freq=k

16、;p=p-prior;)retum(p);/*返回找到的结点的地址*/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,其输出序列为pi,p2,p3,，PN,若 PN是 n,则

17、pi是（D）oA.i B.n-i C.n-i+1 D.不确定4.表达式a*（bc）+d 的后缀表达式是（B）。A.abcd*-+B.abc-*d+C.abc*-d+D.+-*abcd5.采 用 顺 序 存 储 的 两 个 栈 共 享 空 间 topi代表第i 个栈（i=l,2）的栈顶，栈 1的底在S l,栈 2 的底在Sm,则栈满的条件是（B）oA.top2-topl|=0 B.topl+l=top2C.topl+topf2=m D.topl=top26.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（C）。A.edcba B.decba C.dceab D.abcde7.在一

18、个链队列中，若 f,r分别为队首、队尾指针，则插入s所指结点的操作为（B）oA.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

19、.栈和队列的存储，既可以采用顺序存储结构，又可以采用链式存储结构。（J）2.任何一个递归过程都可以转换成非递归过程。（J）3.若输入序列为123,4,5,6,则通过一个栈可以输出序列325,6,4,1。（V）4.通常使用队列来处理函数的调用。（X）5.循环队列通常用指针来实现队列的头尾相接。（X）3.3.3简答题1.循环队列的优点是什么？如何判别它的空和满？循环队列的优点是能够克服“假溢满”现象。设有循环队列s q,队满的判别条件为：（sq-rear+l）%maxsize=sq-front;或 sq-num=maxsize o队空的判别条件为：sq-rear=sq-fronto收集于网络，如有

20、侵权请联系管理员删除精品文档2.栈和队列数据结构各有什么特点，什么情况下用到栈，什么情况下用到队列？栈和队列都是操作受限的线性表，栈的运算规则 是“后进先出”，队列的运算规则是“先进先出”。栈的应用如数制转换、递归算法的实现等，队列的应用如树的层次遍历等。3.什么是递归？递归程序有什么优缺点？一个函数在结束本函数之前，直接或间接调用函数自身，称为递归。例如，函数f 在执行中，又调用函数f 自身，这称为直接递归；若函数f 在执行中，调用函数g,而 g在执行中，又调用函数f,这称为间接递归。在实际应用中，多为直接递归，也常简称为递归。递归程序的优点是程序结构简单、清晰，易证明其正确性。缺点是执行中

21、占内存空间较多，运行效率低。4.设有编号为1,2,3,4的四辆车，顺序进入一个栈式结构的站台，试写出这四辆车开出车站的所有可能的顺序（每辆车可能入站，可能不入站，时间也可能不等）。1234,1243,1324,1342,1432,213,2143,2314,2341,2431,3214,3241,3421,43214.3课后习题解答#4.3.1 选择题1.下面关于串的叙述错误的是（C）。A.串是字符的有限序列B.串既可以采用顺序存储，也可以采用链式存储C.空串是由空格构成的串D.模式匹配是串的一种重要运算2.串的长度是指（B）。A.串中所含不同字母的个数 B.串中所含字符的个数C.串中所含不同

22、字符的个数 D.串中所含非空格字符的个数3.已知串S=a a a b,其 Next数组值为（D）。A.0123 B.1123 C.1231 D.12114.二维数组M 的成员是6 个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从0 到 8,列下标j 的范围从1到 1 0,则存放M 至少需要（D）个字节；M 的第8 列和第5 行共占（A）个字节；若M 按行优先方式存储，元素 M的起始地址与当M 按列优先方式存储时的（C）元素的起始地址一致。（1）A.90 B.180 C.240 D.540（2）A.108 B.114 C.54 D.60（3）A.M85 B.M310 C.D.M095

23、.数组A 中，每个元素的存储占3个单元，行下标i 从 1到 8,列下标j从 1至 U 10,从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（C）,若该数组按行存放，元素A85的起始地址是（C）,若该数组按列存放，元素A85的起始地址是（C）。（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+2256.稀疏矩阵采用压缩存储，一般有(C)两种方法。A.二维数组和三维数组 B.三元组和散列C.

24、三元组表和十字链表 D.散列和十字链表4.3.2判断题1.串相等是指两个串的长度相等。(X)2.KMP算法的特点是在模式匹配时指示主串的指针不会变小。(J)3.稀疏矩阵压缩存储后，必会失去随机存取功能。(J)4.数组是线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。(义)5.若采用三元组存储稀疏矩阵，把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。(X)6.若一个广义表的表头为空表，则此广义表亦为空表。(X)7.所谓取广义表的表尾就是返回广义表中最后一个元素。(X)4.3.3简答题1.KMP算法较朴素的模式匹配算法有哪些改进？KMP算法主要优点是主串指针不回溯。

25、当主串很大不能一次读入内存且经常发生部分匹配时，KMP算法的优点更为突出。2.设字符串 S=aabaabaabaac,P=aabaac。(1)给出S和 P 的next值和nextval值；(2)若 S 作主串，P 作模式串，试给出利用KMP算法的匹配过程。【解答】(1)S 的 next 与 nextval 值分另U 为 012123456789 和 002002002009,p 的next 与 nextval 值分别为 012123 和 002003。(2)利用BF算法的匹配过程：利用KMP算法的匹配过程：第一趟匹配：aabaabaabaac 第一趟匹配：aabaabaabaacaabaac(

26、i=6,j=6)aabaac(i=6,j=6)第二趟匹配：aabaabaabaac 第二趟匹配：aabaabaabaacaa(i=3,j=2)(aa)baac第三趟匹配：aabaabaabaac 第三趟匹配：aabaabaabaaca(i=3,j=l)(成功)(aa)baac第四趟匹配：aabaabaabaacaabaac(i=9,j=6)第五趟匹配：aabaabaabaacaa(i=6,j=2)第六趟匹配：aabaabaabaaca(i=6,j=l)第七趟匹配：aabaabaabaac(成功)aabaac(i=13,j=7)3.假设按行优先存储整数数组A9358时，第一个元素的字节地址是10

27、0,每个整数占4 个字节。问下列元素的存储地址是什么？(1)aoooo(2)ami(3)a3i25(4)as247【解答】(1)LOC(aoooo)=100收集于网络，如有侵权请联系管理员删除精品文档(2)LOC(aini)=100+(3*5*8*l+5*8*l+8*l+l)*4=776(3)LOC(a3i25)=100+(3*5*8*3+5*8*l+8*2+5)*4=1784(4)LOC(a8247)=100+(3*5*8*8+5*8*2+8*4+7)*4=48164.假设一个准对角矩阵：r a n a i2 、a2i a22a33 a34a43 a44aij32m-1,2m-1 32m-L

28、2mI a2m,2m-1 32m,2m j按以下方式存储于一维数组B4m中(m 为一个整数)：0 1 2 3 4 5 6.k.4m-1 4ma na 12321322333334343aij 32 m-1.2ma2m,2m-132m,2m写出下标转换函数k=f(i,j)。【解答】由题目可知，每一行有两个非0 元素。当i 为奇数时，第 i 行的元素为：ai.i ai.(i+i)此时k=2*(i-l)+j-i=i+j-2当i 为偶数时,第 i 行的元素为:ai,(i-i),au，此时k=2*(i-l)+j-I+l=i+j-l综上所述，k=i+j-i%2-lo5.设有nxn的带宽为3 的带状矩阵A,

29、将其3 条对角线上的元素存于数组B3n中,使得元素Buv=aij,试推导出从(i,j)到(u,v)的下标变换公式。【解答】u=j-i+lv=j-l6.现有如下的稀疏矩阵A(如图所示)，要求画出以下各种表示方法。(1)三元组表表示法(2)十字链表法。000220-150133000000-60000000091000000028000J【解答】(1)三元组表表示法:i j v收集于网络，如有侵权请联系管理员删除精品文档11 4 2 221 6 -1 532 2 1 342 3 353 4-665 1 9 176 3 2 8(2)十字链表法:0 1 2 3 4 57.画出下列广义表的头尾表示存储结

30、构示意图。(1)A=(a,b,c),d,(a,b,c)(2)B=(a,(b,(c,d),e),f)(1)精品文档5.3课后习题解答5.3.1 选择题1 .下列说法正确的是（C）。A.二叉树中任何一个结点的度都为2B.二叉树的度为2C.一棵二叉树的度可小于2D.任何一棵二叉树中至少有一个结点的度为22.以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中（n0）,空链域的个数为（C）。A.2n-l B.n-1 C.n+1 D.2n+l3.线索化二叉树中，某结点*p 没有孩子的充要条件是（B）。A.p-lchild=NULL B.p-ltag=l 且 p-rtag=lC.p-ltag=O D

31、.p-lchild=NULL 且 p-ltag=l4.如果结点A 有 3 个兄弟，而且B 是 A 的双亲，则 B 的度是（B）。A.3 B.4 C.5 D.15.某二叉树T 有n 个结点，设按某种顺序对T 中的每个结点进行编号，编号值为1,2,.-n o 且有如下性质:T 中任意结点v,其编号等于左子树上的最小编号减 1 ,而 v 的右子树的结点中，其最小编号等于v左子树上结点的最大编号加1 ,这是按（B）编号的。A.中序遍历序列B.先序遍历序列C.后序遍历序列D.层次顺序6.设 F 是一个森林，B 是由F 转换得到的二叉树，F 中有n 个非终端结点,B 中右指针域为空的结点有（C）个。A.n

32、-1 B.n C.n+1 D.n+27.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（B）。A.500 B.501 C.490 D.4958.设森林F 中有三棵树，第一，第二，第三棵树的结点个数分别为N1,N2和 N3。与森林F 对应的二叉树根结点的右子树上的结点个数是（D）。A.N1 B.N1+N2 C.N2 D.N2+N39.任何一棵二叉树的叶结点在先序、中序、后序遍历序列中的相对次序（A）。A.不发生改变B.发生改变 C.不 能 确 定 D.以上都不对10.若一棵二叉树的后序遍历序列为dabec,中序遍历序列为debac,则先序遍历序列为（D）。A.cbed B.decab C

33、.deabc D.cedba11.若一棵二叉树的先序遍历序列为abdgcefh,中序遍历的序列为dgbaechf,则后序遍历的结果为（D）。A.gcefha B.gdbecfha C.bdgaechf D.gdbehfca收集于网络，如有侵权请联系管理员删除精品文档12.一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（AB）。A.所有的结点均无左孩子 B.所有的结点均无右孩子C.只有一个叶子结点 D.是一棵满二叉树13.引入线索二叉树的目的是（A）。A.加快查找结点的前驱或后继的速度B.为了能在二叉树中方便的进行插入与删除C.为了能方便的找到双亲D.使二叉树的遍历结果唯

34、一1 4.设高度为h 的二叉树上只有度为0 和度为2 的结点，则此类二叉树中所包含的结点数至少为（B）。A.2*h B.2*h-l C.2*h+l D.h+115.一个具有567个结点的二叉树的高h 为（D）。A.9 B.10 C.9 至 566 之间 D.10 至 567 之间16.给一个整数集合3,5,6,7,9 ,与该整数集合对应的哈夫曼树是(B)A5.3.2判断题1.二叉树是树的特殊形式。（J）2.由树转换成二叉树，其根结点的右子树总是空的。（J）3.先根遍历一棵树和先序遍历与该树对应的二叉树，其结果不同。（X）4.先根遍历森林和先序遍历与该森林对应的二叉树，其结果不同。（X）5.完全

35、二叉树中，若一个结点没有左孩子，则它必是叶子。（J）6.对于有N 个结点的二叉树，其高度为Llog2N+l。（X）7.若一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的先序遍历序列中的最后一个结点。（J）8.若一个结点是某二叉树子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。（V）9.不使用递归也可实现二叉树的先序、中序和后序遍历。（J）10.先序遍历二叉树的序列中，任何结点的子树的所有结点不一定跟在该结点之后。（义）11.先序和中序遍历用线索树方式存储的二叉树，不必使用栈。（X）12.在后序线索二叉树中，在任何情况下都能够很方便地找到任意结

36、点的后继。（义）13.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。（收集于网络，如有侵权请联系管理员删除精品文档1 4 .在哈夫曼编码中，出现频率相同的字符编码长度也一定相同。（义）1 5 .用一维数组存放二叉树时，总是以先序遍历存储结点。（X）1 6 .由先序序列和后序序列能唯一确定一棵二叉树。（X）1 7 .由先序序列和中序序列能唯一确定一棵二叉树。（J）1 8 .对一棵二叉树进行层次遍历时，应借助于一个栈。（X）1 9 .完全二叉树可采用顺序存储结构实现存储，非完全二叉树则不能。（X）2 0 .满二叉树一定是完全二叉树，反之未必。（J）5.3.3 简答题1 .一棵度为2

37、 的树与一棵二叉树有何区别？树与二叉树之间有何区别？【解答】二叉树是有序树，度为2 的树是无序树，二叉树的度不一定是2。二叉树是有序树，每个结点最多有两棵子树，树是无序树，且每个结点可以有多棵子树。2 .对于图1 所示二叉树，试给出：（1）它的顺序存储结构示意图；（2）它的二叉链表存储结构示意图；（3）它的三叉链表存储结构示意图。【解答】（1）顺序存储结构示意图：|A|B|C|D|E|F 下 1A1AlG|A|A|H|（2）二叉链表存储结构示意图：（3）三叉链表存储结构示意图：3.对于图2 所示的树，试给出:(1)(2)(3)【解答】双亲数组表示法示意图；孩子链表表示法示意图；孩子兄弟链表表示

38、法示意图。（1）双亲数组表示法示意图:（2）孩子:表表示嚏咫思图:0A-11B02C03D24E25F16G17H58I29J4精品文档(3)孩子兄弟链表表示法示意图:B Bl-(J4.画出图3所示的森林经转换后所对应的二叉树一，并指出森林中满足什么条件的结点在二叉树中是叶子。在二叉树中某结点所对应的森林中结点为叶子结点的条件是该结点在森林中既没有孩子也没有右兄弟结点。5.将题5 图所示的二叉树转换成相应的森林。收集于网络，如有侵权请联系管理员删除精品文档（题5图）【解答】森林：6 .证明：在结点数多于1的哈夫曼树中不存在度为1的结点。证明：由哈夫曼树的构造过程可知，哈夫曼树的每一分支结点都是

39、由两棵子树合并产生的新结点，其度必为2,所以哈夫曼树中不存在度为1的结点。7.证明：若哈夫曼树中有n个叶结点，则树中共有2 n l个结点。证明：n 个叶结点，需经n-1次合并形成哈夫曼树，而每次合并产生一个分支结点，所以树中共有2n-l个结点。8 .证明：由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树。证明：给定二叉树结点的前序序列和对称序（中序）序列，可以唯一确定该二叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左 边（设 1个元素）表示左子树，若左边无元素，则说明左子树为空；右 边（设 r 个元素）是右子树，若为空，则右子树为空。根据前序遍历中“根一左子树

40、一右子树”的顺序，则由从第二元素开始的1个结点序列和中序序列根左边的1个结点序列构造左子树，由前序序列最后1 个元素序列与中序序列根右边的r 个元素序列构造右子树。9 .已知一棵度为m的树中有m个度为1的结点，血个度为2的结点，n m个度为m的结点，问该树中共有多少个叶子结点？有多少个非终端结点？解：设树中共有n 个结点，no个叶结点，那么n=n o+n i+.+n m （1）树中除根结点外，每个结点对应着一个分支，而度为k的结点发出k个分支，所以：n=n i+2*n 2+.+m*nm+l （2）由（1）、（2）可知 n o=n 2+2*n 3+3*r u+（m-l）*n m+l1 0 .在具

41、有n （n l）个结点的树中，深度最小的那棵树其深度是多少？它共有多少叶子和非叶子结点？深度最大的那棵树其深度是多少？它共有多少叶子和非叶子结点？2;n-1;1;n;1,n-11 1 .设高度为h的二叉树上只有度为0和度为2的结点，问该二叉树的结点数可能达到的最大值和最小值。最大值:2h-l；最小值：2h-l1 2 .求表达式：a+b*（cd）e/f的波兰式（前缀式）和逆波兰式（后缀式）。波兰式：-+a*b-c d/e f 逆波兰式：a b c d-*+e f/-1 3 .画出和下列已知序列对应的树T：树的先根次序访问序列为：G FK DAI EBCH J；收集于网络，如有侵权请联系管理员删除

42、精品文档树的后根访问次序为：DI AEK FCJ H BG o【解答】对应的二叉树和树分别如下左、右图所示:1 4 .画出和下列已知序列对应的森林F：森林的先根次序访问序列为：ABCDEFG H I J K L；森林的后根访问次序为：CBEFDG AJ I K L H o1 5 .画出和下列已知序列对应的树T：二叉树的层次访问序列为：ABCDEFG H I J；二叉树的中序访问次序为：DBG EH J ACI Fo【解答】按层次遍历，第一个结点（若树不空）为根，该结点在中序序列中把序列分成左右两部分一左子树和右子树。若左子树不空，层次序列中第二个结点左子树的根；若左子树为空，则层次序列中第二个

43、结点右子树的根。对右子树也作类似的分析。层次序列的特点是：从左到右每个结点或是当前情况下子树的根或是叶子。1 6.假设用于通信的电文由字符集 4 1?lchild)+count(root-rchild)+l);)2.请设计一个算法，要求该算法把二叉树的叶结点按从左至右的顺序链成一个单链表。二叉树按Ichikl-rchild方式存储，链接时用叶结点的rchild域存放链指针。【提示】这是一个非常典型的基于二叉树遍历算法，通过遍历找到各个叶子结点，因为不论前序遍历、中序遍历和后序遍历，访问叶子结点的相对顺序都是相同的，即都是从左至右。而题目要求是将二叉树中的叶子结点按从左至右顺序建立一个单链表，因

44、此，可以采用三种遍历中的任意一种方法遍历。这里使用中序递归遍历。设置前驱结点指针p re,初始为空。第一个叶子结点由指针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(p re=NULL)head=

45、T;pre=T;/*处理第一个叶子结点*/else pre-rchild=T;收集于网络，如有侵权请联系管理员删除精品文档pre=T;/*将叶子结点链入链表*/InOrder(T-rchild);/*中序遍历右子树木/pre-rchild=NULL;/*设置链表尾结点*/return(head);)3.给定一棵用二叉链表表示的二叉树，其根指针为ro o t,试写出求二叉树的深度的算法。【提示】采取递归算法。int Height(BiTree root)int hl,hr;if(root=NULL)return(O);else hl=Height(root-lchild);hr=Height(r

46、oot-rchild);if(hlhr)return(hl+1);else return(hr+l);)4.给定一棵用二叉链表表示的二叉树，其根指针为ro o t,试求二叉树各结点的层数。【提示】采用先序递归遍历算法实现。*1二叉树结点的层次数 当结点为根结点void fun(BiTree root,int n)if(t=NULL)return;else printf(%d”,n);fun(root-lchild,n+l);fun(root-rchild,n+l);)5.给定一棵用二叉链表表示的二叉树，其根指针为ro o t,试写出将二叉树中所有结点的左、右子树相互交换的算法。【提示】设 ro

47、ot为一棵用二叉链表存储的二叉树，则交换各结点的左右子树的运算可基于后序遍历实现：交换左子树上各结点的左右子树；交换左子树上各结点的左右子树；再交换根结点的左右子树。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 个结点的完全二叉树采用顺序结构存储，试设计非递归算法对其进行先序遍历。【提示】二叉树的顺序存储

48、是按完全二叉树的顺序存储格式按层次存储的，双亲结点与子女结点的下标间有确定的关系。对顺序存储结构的二叉树进行先序遍历，与二叉链表存放二叉树的遍历策略类似。但是在顺序存储结构下，判二叉树结点为空的条件为：结点下标大于n,或结点值为0（一般二叉树中的“虚结点”）ovoid PreOrder(datatype datan+l)/*o号单元未用*/int stackn;int top;if(nl)return;t=l；top=0;while(t0)while(t=n&datat!=0)Visite(datat);stackftop=t;top+;t=t*2;if(topdata=x)/*若当前结点值为

49、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

50、 ,char post ,int il,int ir,int pl,int pr,BiTree t)/*数组in和数组post中存放着二叉树的中序遍历序列和后序遍历序列，il和 ir表示中序遍历序列的左右端*/*点，pl和 pr表示后序遍历序列的左右端点，t 表示二叉树的根*/t=(BiTNode*)malloc(sizeof(BiTNode);t-data=postpr;m=il;while(inm!=post pr)m+;if(m=il)t-lchild=NULL;else InPost(in,post,il,m-1 ,pl,pl+m-1 -il,t-lchild);if(m=ir)t-r