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

1、.课后习题解答判断题线性表的逻辑顺序与存储顺序总是一致的。顺序存储的线性表可以按序号随机存取。一半的元素需要移动。 因此属于同一数据对象。 在线性表的顺序存储构造中，逻辑上相邻的两个元素在物理位置上并不一定相邻。在线性表的链式存储构造中，逻辑上相邻的元素在物理位置上不一定相邻。线性表的链式存储构造优于顺序存储构造。在线性表的顺序存储构造中，插入和删除时移动元素的个数与该元素的位置有关。线性表的链式存储构造是用一组任意的存储单元来存储线性表中数据元素的。在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随i个元i无关。线性表的特点是每个元素都有一个前驱和一个后继。算法设计题设线

2、性表存放在向量Aarrsize 的前elenum个分量中，且递增有序。试写一算法将x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。相邻，不一定将向量和表示线性表长度的变量封装成一个构造体，因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，假设有，那么根据原线性表中元的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，也可以从高低标端开x ，最后修改表示表长的变量。intinsert(datatypeA,int*elenum,datatypex)/*elenumif(*elenum=arrsize-1)return0;/*表已满，无法

3、插入else i=*elenum;为表的最大下标*/*/while (i=0 & 边找位置边移动*/Ai+1=Ai;i-;Ai+1=x;(*elenum)+; return 1;/* 插入成功 */时间复杂度为 O(n) 。/* 找到的位置是插入位的下一位*/元素。【提示】 对顺序表 A ，从第一个元素开场，查找其后与之值一样的所有元素，将它们删除； 再对第二个元素做同样处理，依此类推。void delete(Seqlist*A)i=0;while(ilast)*/k=i+1;/* 将第 i 个元素以后与其值一样的元素删除while(klast&A-datai=A-datak)/*kAi*/k

4、+;n=k-i-1;for(j=k;jlast;j+)A-dataj-n=A-dataj; A-last= A-last-n;i+;A以较高的效率来实现。/*n 表示要删除元素的个数 */* 删除多余元素 */xy(xdataixynA-datai向前移n n 用来记录当前已删除元素的个数。void delete(Seqlist *A,int x,int y)i=0; n=0;while (ilast)if(A-datai=x&A-dataidatai介于 x和 y之间， n自增 */elseA-datai-n=A-datai; /* i+;A-last-=n;A-datai*/线性表中有n

5、个元素，每个元素是一个字符，现存于向量Rn中，试写一算法，使R 中的字符按字母字符、 数字字符和其它字符的顺序排列。 要求利用原来的存储空间， 元素移动次数最小。【提示】 对线性表进展两次扫描， 第一次将所有的字母放在前面， 第二次将所有的数字放在字母之后，其它字符之前。int fch(char c)if(c=a&c=A&c=0&c=9)return (1);/* 判断 c 是否字母 */* 判断 c 是否数字 */elsereturn (0);void process(charRn)low=0; high=n-1;while(lowhigh)while(lowhigh&fch(Rlow)lo

6、w+; while(lowhigh&!fch(Rhigh)if(lowhigh)k=Rlow;Rlow=Rhigh; Rhigh=k;/* 将字母放在前面 */*将数字放在字母后面，其它字符前面*/low=low+1; high=n-1; while(lowhigh)while(lowhigh&fnum(Rlow) low+; while(lowhigh&!fnum(Rhigh)if(lowhigh)k=Rlow;Rlow=Rhigh;Rhigh=k;线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m元素和后 n 个元素进展整体互换。即将线性表：a, ,改变为：1,a2m,

7、b1,b2nb1,b2,nb,a1 ,a2, ma。mn的大小，假设 mn移后移 n 次。void process(Seqlist *L,int m,int n)if(m=n) for(i=1;idata0;for(k=1;klast;k+)L-datak-1=L-datak; L-dataL-last=x;m 次；否那么 ,将表中元素依次else for(i=1;idataL-last; for(k=L-last-1;k=0;k- L-datak+1=L-datak;L-data0=x;带头结点的单链表L中的结点是按整数值递增排列的，试写一算法， 将值为 x的结点插入到表L 中，使得 L 仍

8、然递增有序，并且分析算法的时间复杂度。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;s-next=p-next; p-next=s; return(L);ABC 不改变其排序性。LinkList Combine(LinkList A, LinkList B)C=A;rc=C;pa=A-next; /*pa 指向表 A 的第一个结点 */

9、pb=B-next; /*pb 指向表 B 的第一个结点*/free(B); /* 释放 B 的头结点 */while (pa & pb) /* 将 pa 、pb 所指向结点中，值较小的一个插入到链表 C 的表尾 */if(pa-datadata)rc-next=pa; rc=pa;pa=pa-next;elserc-next=pb; rc=pb;pb=pb-next;if(pa)rc-next=pa;elserc-next=pb;/*A B C */return(C);假设长度大于1 的循环单链表中，既无头结点也无头指针，p 为指向该链表中某结点的指针，编写算法删除该结点的前驱结点。s 指针

10、可循环找到其前驱结点p p 的前驱结点q， 然后可删除结点* p。viod delepre(LNodeLNode* p, *q;p=s;while (p-next!=s)q=p;p=p-next;q-next=s; free(p);两个单链表A和B分别表示两个集合，其元素递增排列，编写算法求出A和BCC 同样以元素递增的单链表形式存储。【提示】 交集指的是两个单链表的元素值一样的结点的集合，为了操作方便，先让单链表 Cp A q 用来B 时，将其较小者跳过，继续后面的比拟。LinkListIntersect(LinkListA,LinkListB)LNode*q,*p,*r,*LinkList

11、 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;r=s;p=p-next; q=q-next;elseq=q-next; r-next=NULL;C=C-next; returnC;设有一个双向链表，每个结点中除有prior 、data和next 域外，还有一个访问频度freq Lo

12、cata(L,x) x freq 1Locata(L,x) 算法。【提示】在定位操作的同时，需要调整链表中结点的次序：每次进展定位操作后，要查看所查找结点的freq域，将其同前面结点的freq域进展比拟，同时进展结点次序的调整。typedef struct dnodedatatype data; int freq;struct DLnode*prior,*next;DLnode,*DLinkList;DlinkListLocate(DLinkListL,datatypex)p=L-next;while(p&p-data!=x) p=p-next; if(!p) return(NULL);p-f

13、req+;while(p-prior!=L&p-prior-freqfreq)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 */* 调整结点的次序 */* 返回找到的结点的地址*/课后习题解答#选择题ATop-next=p;CTop 的链栈中插入一个p 所指结点时，其操作步骤为Dp-next=Top;Top=Top-next;C。对于栈

14、操作数据的原那么是B。A先进先出B后进先出C后进后出D不分顺序piD。1,2,3,，,n其输出序列为p1,p2,p3，pN,假设pN是n，A iBn-i+1D不确定表达式 a*(b c)d 的后缀表达式是 B。A BCabc*-d+D+-*abcd采用顺序存储的两个栈共享空间S1.m ，topi代表第i个栈(i=1,2) 的栈顶，栈1底在S1 ，栈2 的底在 Sm ，那么栈满的条件是B。A top2-top1|=0 Ctop1+top2=m 6一个栈的入栈序列是B Dtop1=top2a,b,c,d,e ，那么栈的不可能的输出序列是C。A edcbaBdecbaCdceabD abcde在一个

15、链队列中， Af-next=r;f=s; Cs-next=r;r=s;f,r 分别为队首、队尾指针，那么插入s 所指结点的操作为B。B r-next=s;r=s; D s-next=f;f=s;用不带头结点的单链表存储队列时，在进展删除运算时D。A 仅修改头指针 B 仅修改尾指针C头、尾指针都要修改 D 头、尾指针可能都要修改C的数据构造。A队列B 静态链C。 A顺序存储的线性构C限制存取点的线性判断题C栈D顺序表B 链式存储的非线性构造D 限制存取点的非线性构造栈和队列的存储，既可以采用顺序存储构造，又可以采用链式存储构造。任何一个递归过程都可以转换成非递归过程。3假设输入序列为1,2,3,

16、4,5,6 ，那么通过一个栈可以输出序列 3,2,5,6,4,1 。通常使用队列来处理函数的调用。循环队列通常用指针来实现队列的头尾相接。简答题循环队列的优点是能够克制“假溢满现象。设有循环队列 sq ，队满的判别条件为：（sq-rear+1 %maxsize=sq-front;或sq-num=maxsize队空的判别条件为：sq-rear=sq-front。栈和队列数据构造各有什么特点，什么情况下用到栈，什么情况下用到队列？栈和队列都是操作受限的线性表， 栈的运算规那么是 “后进先出 ，队列的运算规那么是“先进先出。栈的应用如数制转换、递归算法的实现等，队列的应用如树的层次遍历等。什么是递归

17、？递归程序有什么优缺点？一个函数在完毕本函数之前，直接或间接调用函数自身，称为递归。例如，函数 f 在执行中，又调用函数f自身，这称为直接递归；假设函数f在执行中，调用函数g，而g 在执中，又调用函数这称为间接递归。在实际应用中，多为直接递归，也常简称为递归。递归程序的优点是程序构造简单、清晰，易证明其正确性。缺点是执行中占内存空间较多，运行效率低。设有编号为1,2,3,4的四辆车，顺序进入一个栈式构造的站台，试写出这四辆车开车站的所有可能的顺序每辆车可能入站，可能不入站，时间也可能不等。1234,1243,1324,1342,1432,213,2143,2314,2341,2431,3214

18、,3241,3421,4321#选择题下面关于串的表达错误的选项是C。 A串是字符的有限序列 BC空串是由空格构成的串 D2串的长度是指B。A 串中所含不同字母的个数 B串中所含字符的个数CD3S=aaab ,Next A。A 0123B 1123C 1231 D 1211二维数组M的成员是6 个字符每个字符占一个存储单元组成的串，行下标X围从0 到8，列下标j的X围从1 到10，那么存放M至少需要D个字节；M的第第5 行共占A个字节；假设M按行优先方式存储，元M85的起始地址与当M先方式存储时的C元素的起始地址一致。1A 90B180C 240D 5402A 108B114C 54D603A

19、 M09i8列和按列优数组 A中，每个元素的存储占3个单元，行下标i从1到8，列下标j从1到10， 从首地址SA开场连续存放在存储器内，存放该数组至少需要的单元个数是C，假设该数组 按行存放，元素A85的起始地址是D，假设该数组按列存放，元素A85的起始地址B 。1A80B100C240D2702ASA+141BSA+144CSA+222DSA+2253ASA+141BSA+180CSA+117DSA+225稀疏矩阵采用压缩存储，一般有CA 二维数组和三维数组 B三元组和散列CD散列和十字链表判断题串相等是指两个串的长度相等。KMP算法的特点是在模式匹配时指示主串的指针不会变小。稀疏矩阵压缩存

20、储后，必会失去随机存取功能。数组是线性构造的一种推广，因此与线性表一样，可以对它进展插入，删除等操作。该矩阵的转置运算。 假设一个广义表的表头为空表，那么此广义表亦为空表。所谓取广义表的表尾就是返回广义表中最后一个元素。简答题KMP算法较朴素的模式匹配算法有哪些改良?KMP 算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生局部匹配时， KMP 算法的优点更为突出。设字符串S=aabaabaabaac，P=aabaac 。1S P next nextval 值；2S P KMP 算法的匹配过程。【解答】（1S的next与nextval值分别为012123456789和00200

21、2002021，p的next 与nextval值分别为012123和002003。利用 KMPaabaac(i=6,j=6)2BF 第一趟匹配：aabaabaabaacaabaac(i=6,j=6)第一趟匹配：匹配过程：算aabaabaabaac法的第二趟匹配：aa(i=3,j=2)(aa)baacaabaabaabaac第二趟匹配：aabaabaabaac第三趟匹配：aabaabaabaac第三趟匹配： a(i=3,j=1)(aa)baac第四趟匹配： aabaabaabaacaabaac(i=9,j=6)第五趟匹配： aabaabaabaacaa(i=6,j=2)第六趟匹配：aabaaba

22、abaaca(i=6,j=1)第七趟匹配： aabaabaabaac( 成功)aabaac(i=13,j=7)假设按行优先存储整数数组 时，第一个元素的字节地址是 100数占个字节。问以下元素的存储地址是什么？(1)a0000(2)a1111(3)a3125(4)a8247【解答】(1)LOC(a0000 )=100(2) LOC( a 1111 )=100+(3*5*8*1+5*8*1+8*1+1)*4=776(3)LOC(a 3125)=100+(3*5*8*3+5*8*1+8*2+5)*4=1784 (4)LOC(a 8247)=100+(3*5*8*8+5*8*2+8*4+7)a11a

23、12a21 a22a33a34a43a44.aija2m-1,2m-1 a2m-1,2ma2m,2m-1 a2m,2m按以下方式存储于一维数组B4m 中 m 为一个整数：4m-14m012356k2m-1,2ma2m,2m-1a2m,2ma 11a aa22aaa43aij写出下标转换函数 k=f(i,j) 。【解答】由题目可知，每一行有两个非 0 元素。当 i 为奇数时，第 i 行的元素为： a i,i、 a i,(i+1)，此时 k=2*(i-1)+j-i=i+j-2i i a i,(i-1)a k=2*(i-1)+j-I+1=i+j-1 k=i+j-i%2-1 。nn 3 A3 B3n中

24、，使得元Buv=a i,j(u,v) 的下标变换公式。【解答】u=j-i+1 v=j-1.A如下图，要求画出以下各种表示方法。（1三元组表表示法（2十字链表法。000220-150133000000-60000000091000000028000【解答】1三元组表表示法:ijv11422216-15322134233534-665191763282十字链表法：01234502213231142216-1534-6235191456328.画出以下广义表的头尾表示存储构造示意图。（1A=(a,b,c),d,(a,b,c)（2B=(a,(b,(c,d),e),f)（1111 1111 d（20a1

25、b1c1110a 1110f0 b110 c0 c0d课后习题解答选择题以下说法正确的选项是C。A 二叉树中任何一个结点的度都为 22一棵二叉树的度可小于 2 D任何一棵二叉树中至少有一个结点的度为2的个数为 C。n 个结点的二叉链表中2n0 ，空链域A2n-1Bn-1Cn+1D 2n+1Ap-lchild=NULL Cp-ltag=0*p没有孩子的充要条件是BBp-ltag=1且p-rtag=1p-lchild=NULL p-ltag=1A3 ,BA,BB。A3B4C5D1某二叉树T有n 个结点,设按某种顺序对T 中的每个结点进展编号，编号值为1,2,.n 且有如下性质:T 中任意结点v,其

26、编号等于左子树上的最小编号减,而v的右子树的结点中,其最小编号等于 v 左子树上结点的最大编号加，这是按B 编号的。A 中序遍历序列 B 先序遍历序列 C后序遍历序列 D层次顺序设F 是一个森林，B是由F转换得到的二叉树域为空的结点有C个。F中有n 个非终端结点,B中右指针An-1nn+D1Cn+2.一棵完全二叉树上500B5011001 C490D495C。设森林F 中有三棵树，第一，第二，第三棵树的结点个数分别为N1，N2和N3。与森林 F 对应的二叉树根结点的右子树上的结点个数是BN1+N2CN2D。任何一棵二叉树的叶结点在先序、中序、后序遍历序列中的相对次序A。A 不发生改变 B发生改

27、变假设一棵二叉树的后序遍历序以上都不对debac ，那么先序遍历序为为D。dabec，中序遍历序列为列AcbedBdecabCdeabcD11假设一棵二叉树的先序遍历序列为abdgcefh ，中序遍历的序列为历的结果为 D 。AgcefhaBgdbecfhaCbdgaechfDdgbaechf ，那么后序遍12一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，那么该二叉树一定满足B 。A 所有的结点均无左孩子 B 所有的结点均无右孩子C只有一个叶子结点 D 是一棵满二叉树13 引入线索二叉树的目的是A。A加快查找结点的前驱或后继的速度 B为了能在二叉树中方便的进展插入与删除C为了能方便的找到

28、双亲 D使二叉树的遍历结果唯一设高度为 h那么此类二叉树中所包含的结B。A 2*hB 2*h-1C 2*h+1D h+1一个具有567 个结点的二叉树的高h 为D。A9B10C9 566 D10 567 之间给一个整数集合3，5，6，7，9，与该整数集合对应的哈夫曼树是B。ABCD939579676676733557935判断题二叉树是树的特殊形式。由树转换成二叉树，其根结点的右子树总是空的。先根遍历一棵树和先序遍历与该树对应的二叉树，其结果不同。.先根遍历森林和先序遍历与该森林对应的二叉树，其结果不同。完全二叉树中，假设一个结点没有左孩子，那么它必是叶子。对于有 Nlog 2N1。假设一个结

29、点是某二叉树子树的中序遍历序列中的最后一个结点，那么它必是该子树的.先序遍历序列中的最后一个结点。树的后序遍历序列中的第一个结点。 不使用递归也可实现二叉树的先序、中序和后序遍历。先序遍历二叉树的序列中，任何结点的子树的所有结点不一定跟在该结点之后。先序和中序遍历用线索树方式存储的二叉树，不必使用栈。在后序线索二叉树中，在任何情况下都能够很方便地找到任意结点的后继。哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。在哈夫曼编码中，出现频率一样的字符编码长度也一定一样。用一维数组存放二叉树时，总是以先序遍历存储结点。对一棵二叉树进展层次遍历时，应借助于一个栈。完全二叉树可采用顺序存储

30、构造实现存储，非完全二叉树那么不能。满二叉树一定是完全二叉树，反之未必。简答题2 的树与一棵二叉树有何区别？树与二叉树之间有何区别？【解答】2 2个结点最多有两棵子树， 树是无序树， 且每个结点可以有多棵子树。A对于图 1 所示二叉树，试给出：1它的顺序存储构造示意图；BC2它的二叉链表存储构造示意图；3它的三叉链表存储构造示意图。【解答】DEF1顺序存储构造示意图：ABCDEFGH(1)HG2二叉链表存储构造示意图：3三叉链表存储构造示意图：AABC DEFGHBC D E F2 所示的树，试给出：G H （1双亲数组表示法示意图；GFEDI（2孩子链表表示法示意图；HJ 图2)（3 孩子兄

31、弟链表表示法示意图。【解答】（1双亲数组表示法示意图：2孩子链表表示法示意图：ABC.2648 100A0A-10A1B01B2C02C3D23D4E24E5F15F6G16G7H57H8I28I9J49J10K410K11M311M12N812N5311973孩子兄弟链表表示法示意图：ABCGFEDH JK12I3 在二叉树中是叶子。A FJBCDGEHI(图 3).【解答】ABF ECGJDHI.在二叉树中某结点所对应的森林中结点为叶子结点的条件是该结点在森林中既没有孩子也没有右兄弟结点。将题 5 图所示的二叉树转换成相应的森林。ABCDEFGH【解答】 森林：(题 5 图)CAFBEHD

32、G1 1 的结点。证明：由哈夫曼树的构造过程可知，哈夫曼树的每一分支结点都是由两棵子树合并产生的新结点，其度必为 2，所以哈夫曼树中不存在度为 1 的结点。n 个叶结点，需经2n-1 个结点。n 个叶结点，那么树中共有 2n 1 个结点。n-1 次合并形成哈夫曼树，而每次合并产生一个分支结点，所证明：由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树。证明：给定二叉树结点的前序序列和对称序中序序列，可以唯一确定该二叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两局部，左边设l个元r 个元素是右子树，假设素表示左子树，假设左边无元素，那么说明左子树为空；右边设空，那么右子树

33、为空。根据前序遍历中“根 左子树右子树的顺序，那么由从第二元素开场的l 个结点序列和中序序列根左边的l个结点序列构造左子树，由前序序列最后r 个元素序列与中序序列根右边的一棵度为r 个元素序列构造右子树。m 的树中有 n1 个度为 1 的结点，n2 个度为2 的结点，nm 个度m n n0 个叶结点，那么n=n 0+n1+ +nm(1)树中除根结点外，每个结点对应着一个分支，而度为n=n 1+2*n 2+m*n m+1由(1)(2)n0= n2+2*n 3+3*n 4+(m -1)*n m+1k 的结点发出 k 个分支，所以：在具有 nn1个结点的树中，深度最小的那棵树其深度是多少？它共有多少

34、2; n-1; 1; n; 1, n-1设高度为h 的二叉树上只有度的最大值和最小值。2h-12h-1和度为 2 .求表达式a *ab*(c d)e/f 的波兰式前缀式和逆波兰式后缀式。d/ef逆波兰式： abcd*ef/-画出和以下序列对应的树T ：GFKDAIEBCHJ；树的后根访问次序为：DIAEKFCJHBG。【解答】 对应的二叉树和树分别如下左、右图所示：GGFFBBKKCHCDDAEJAHIJIE画出和以下序列对应的森林F： ABCDEFGHIJKL森林的后根访问次序为：CBEFDGAJIKLH。AHDEGIKLJ画出和以下序列对应的树T ： ABCDEFGHIJ ； DBGEHJ

35、ACIF 。【解答】ABCDEFGHIJ按层次遍历，第一个结点 假设树不空为根，该结点在中序序列中把序列分成左右两局部左子树和右子树。假设左子树不空，层次序列中第二个结点左子树的根；假设左子树为空，右每个结点或是当前情况下子树的根或是叶子。a,b,c,d,e,f,g 中的字母构成。它们在电文中出现的0.31,0.16,0.10,0.08,0.11,0.20,0.04,1为这 7 个字母设计哈夫曼编码。.27 总长压缩多少？1哈夫曼树：1.001a：100.410.59b：1100101c：0100.200.210.310.28d：11100101e：01100g：111127 0.100.11

36、0.160.1200.800.403 位二进制数。等长编码的平均长度：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%算法设计题root ，试写出求二叉树结点的数目的算法。【提示】 采用递归算法实现。二叉树结点的数目0 当二叉树为空左子树结点数目右子树结点数目1 当二叉树非空int count(BiTree root)if (root=NULL) retu

37、rn (0);elsereturn (count(root-lchild)+count(root-rchild)+1);请设计一个算法，要求该算法把二叉树的叶结点按从左至右的顺序链成一个单链表。二叉树按lchild-rchild方式存储，时用叶结点的【提示】 这是一个非常典型的基于二叉树遍历算法，rchild 域存放链指针。通过遍历找到各个叶子结点，因为不管前序遍历、中序遍历和后序遍历，访问叶子结点的相对顺序都是一样的，即都是从左至右。而题目要求是将二叉树中的叶子结点按从左至右顺序建立一个单链表， 遍历中的任意一种方法遍历。这里使用中序递归遍历。设置前驱结点指针第一个叶子结点由指针head指向

38、，遍历到叶子结点时，就将它前驱因此，可以采用三种pre ，初始为空。 rchild 指针指向它，最后叶子结点的 rchild 为空。LinkList head,pre=NULL; LinkListInOrder(BiTree/* 全局变量 */*中序遍历二叉树T，将叶子结点从左到右链成一个单链表，表头指针为head*/if(T)InOrder(T-lchild);/*中序遍历左子树*/if(T-lchild=NULL&当前是叶子结点*/if (pre=NULL)head=T;pre=T;/*处理第一个叶子结点*/else pre-rchild=T;.pre=T;InOrder(T-rchild

39、);/* 将叶子结点链入链表 */* 中序遍历右子树 */pre-rchild=NULL return(head);/*/给定一棵用二叉链表表示的二叉树，其根指针为root，试写出求二叉树的深度的算法。【提示】 采取递归算法。intHeight(BiTreeinthl,hr;root)if (root=NULL) return(0); elsehl=Height(root-lchild);hr=Height(root-rchild); if (hlhr) return (hl+1); else return(hr+1);【提示】 采用先序递归遍历算法实现。root ，试求二叉树各结点的层数。二

40、叉树结点的层次数1其双亲结点的层次数当结点为根结点当结点非根结点voidfun(BiTreeroot, intn)if(t=NULL)return; elseprintf( %dfun(root-lchild,n+1); fun(root-rchild,n+1);给定一棵用二叉链表表示的二叉树，其根指针为 root 右子树相互交换的算法。【提示】设root为一棵用二叉链表存储的二叉树，那么交换各结点的左右子树的运算可基于后序遍历实现： 交换左子树上各结点的左右子树； 交换左子树上各结点的左右子树； 再交换根结点的左右子树。voidExchange(BiTreeroot)BiTNode*p;(r

41、oot)Exchange(root-lchild); Exchange(root-rchild); p=root-lchild;root-lchild=root-rchild;root-rchild=p;.n 序遍历。【提示】 二叉树的顺序存储是按完全二叉树的顺序存储格式按层次存储的，双亲结点与子女结点的下标间有确定的关系。对顺序存储构造的二叉树进展先序遍历，与二叉链表存放二n0一般二叉树中的“虚结点。voidPreOrder(datatypedatan+1)intstackn; int top; if(n1)return; t=1;top=0;while (t0)while(t=n&data

42、t!=0) Visite(datat); stacktop=t;top+; t=t*2; if (topdata=x)while(!Empty_Stack(S)Pop(S,q);printf(q-data);/*假设当前结点值为x，依次输出栈中元素的值*/return;/* 假设当前结点值不是x*/elsePush_Stack(S,p);p=p-lchild;if(!Empty_Stack(S) p=r-rchild;else return;/* 当栈非空，栈顶元素出栈，进入右子树*/一棵二叉树的后序遍历序列和中序遍历序列，写出可以确定这棵二叉树的算法。【提示】 根据后序遍历和中序遍历的特点，

43、采用递归算法实现。voidInPost(charin,charpost,intil,intir,intpl,intpr,BiTreet)/* in post 中存放着二叉树的中序遍历序列和后序遍历序列，ilir 表示中序遍历序列的左右端*/* 点， pl 和 pr 表示后序遍历序列的左右端点， t 表示二叉树的根 */t=(BiTNode *)malloc(sizeof(BiTNode); t-data=postpr;m=il;while (inm!=post pr ) m+;if (m= il)t-lchild=NULL;elseInPost(in,post,il,m-1,pl,pl+m-1

44、-il,t-lchild); if(m=ir)t-rchild=NULL;elseInPost(in,post,m+1,ir,pr-ir+m,pr-1,t-rchild);编写算法判断一棵二叉链表表示的二叉树是否是完全二叉树。【提示】 根据完全二叉树的定义可知，对完全二叉树按照从上到下，从左到右的次序遍历应后继一定无孩子。 因此， 可采用按层次遍历二叉树的方法依次对每个结点进展判断。这里增加一个标志以表示所有已扫描过的结点均有左、右孩子，将局部判断结果存入 CM 中， CM表示整个二叉树是否是完全二叉树，B 为 1 表示到目前为止所有结点均有左右孩子。int CompleteBT(BiTree

45、T)Init_Queue(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;if(rchild!=NULL) CM=0;else CM=B;In_Queue(Q,p-lchild);if(p-rchild=NULL)B=0; elseIn_Queue(Q,p-rchild);/* 初始化队列 Q*/*当队列不为空时执行循环*/*B=0表示缺少左、右孩子*/*CM=0 表示不是完全二叉树*/*/*/return(CM);n A1.n中，试据此建立一棵用二叉

46、链表表示的二叉树。BiTreeCreate(dataypeA,inti)/*n 个结点的完全二叉树存于一维数组 A 中，据此建立以二叉链表表示的完全二叉树,初始调用时 ,i=1*/BiTree T;if(idata=Ai;if (2*in)T-lchild=NULL;else T-lchild=Create(A,2*i); if (2*i+1n) T-rchild=NULL;else T-rchild=Create(A,2*i+1);return (T);s t相似，即要么它们都为空或都只有一个结点，要么它们的左右子树都相似。【提示 】两棵空二叉树或仅有根结点的二叉树相似； 对非空二叉树， 可

47、判左右子树是否相似，采用递归算法。int Similar(BiTree s, BiTree t)&q=NULL)return(1);if(!s&t|s&!t)return(0);else return(Similar(s-lchild,t-lchild) & Similar(s-rchild,t-rchild)写出用逆转链方法对二叉树进展先序遍历的算法。【提示 】用逆转链的方法遍历二叉树，不需要附加的栈空间，而是在遍历过程中沿结点的右子树下降时，临时改变结点lchild或者rchild的值，使之指向双亲，从而为以后的上升提供路径，上升时再将结点的 lchild 或者 rchild 恢复。typ

48、edefstructtnodedatatype data;int tag;/*tag 0，进入左子树时置struct tnode *lchild, *rchild;Bnode, *Btree;voidPreOrder(Btreebt)Bnode*r,*p,指向当前结点，rpif(bt=NULL)return; p=bt; r= NULL: while( p)Visit(p); if(p-lchild)1，从左子树回来时，再恢复为q 指向要访问的下一结点*/* 访问 p 所指结点 */* 下降进入左子树 */p-tag=1;q=p-lchild;q=p-lchild=r;r=p;p=q;0*/*

49、 下降进入右子树 */elseif(p-rchild)q=p-rchild;r=p; p=q;else /* */whle(r&t-tag=0) | (r&t-tag=1&r-rchild=NULL)if(r&t-tag=0)q=r-rchild; r-rchild=p;p=r;r=q;/*从右子树回来 */elser-tag=0; q=r-lchild;r-lchild=p;p=r;r=q;/*从左子树回来 */if (r=NULL)return;elser-tag=0; q=r-rchild;r-rchild= r-lchild; r-lchild=p; p=q;/*从左子树回来，准备进入

50、右子树*/对以孩子兄弟链表表示的树编写计算树的深度的算法。【提示 】采用递归算法实现。树的深度0 假设树为空Max第一棵子树的深度1，兄弟子树的深度假设树非空int high(CSTreeT)if(T=NULL)return(0);/*假设树为空，返回0*/elseh1=high(t-lchild);/* *h1T的第一棵子树的深度*/h2=high(t-nextsibling);/*h2为t的兄弟子树的深度*/return(max(h1+1,h2);对以孩子链表表示的树编写计算树的深度的算法。【提示】采用递归算法实现。1 假设根结点没有子树树的深度max( 所有子树的深度 ) 1 假设根结点

51、有子树#define MAXNODE high(SNode tMAXNODE,intj)if(tj.firstchild=NULL)return(1);/*假设根结点没有子树*/else p=ti.firstchild;max=high(t,p-data); p=p-nextchild; while(p) h=high(t,p-data); if(hmax) max=h;.p=p-nextchild;return(max+1);对以双亲链表表示的树编写计算树的深度的算法。【提示 】从每一个结点开场，从下向上搜索至根结点，记录结点的层次数， 其中的最大值就是树的深度。int high(PNode

52、 t,intn)maxh=0;for (i=0 ;imaxh)maxh=h;return(maxh) ;选择题n 条边的无向图的邻接表的存储中，边结点的个数有。AnBCD n*nn条边的无向图的邻接多重表的存储中，边结点的个数有A。AnBCD n*nA BCAOV 网DAOE 网最短路径的生成算法可用C。A B克鲁斯卡尔算法C迪杰斯特拉算D 哈夫曼算法一个无向图的邻接表如以下图所示：序号vertexfirstedgev1v2v3130231v4011从顶点 v0 出发进展深度优先搜索，经历的结点顺序为B。.Av0,v3,v2,v1Bv0,v1,v2,v3Cv0,v2,v1,v3Dv0, v1,

53、 v3, v22V0D。Av0,v3,v2,v1Bv0,v1,v2,v3Cv0,v2,v1,v3Dv0, v1, v3, v2设有向图n 个顶点和e 条边，进展拓扑排序时，总的计算时间为D。AO(nlog O(enO(elogD O (n+e)n e A。Kruskal 算法生成最小生成树，其时间复A O(elogO(enO(elogD O(nlog 2n)关键路径是事件结点网络中A 。A从源点到汇点的最长路径B从源点到汇点的最短路径C最长的回路D最短的回9下面关于求关键路径的说法不正确的选项是。A求关键路径是以拓扑排序为根底的 B一个事件的最早开场时间与以该事件为尾的弧的活动最早开场时间一样

54、 C时间的差D关键活动一定位于关键路径上1010 B 条边才能确保其是连通图。A8B9C10D11判断题求最小生成树的Prim算法在边较少、结点较多时效率较高用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。AOV-有回路的图不能进展拓扑排序。故只存储邻接矩阵的下(或上 )三角局部即可。任何无向图都存在生成树。假设一个有向图的邻接矩阵对角线以下元素均连通分量是无向图中的极小连通子图。那么该图的拓扑有序序列必定存在。强连通分量是有向图中的极大强连通子图用邻接矩阵 A表示图，判定任意两个结点和vj之间是否有长度为m 的路径相连，那么只要

55、检查Am的第i行第j列的元素是否为0 即可。缩短关键路径上活动的工期一定能够缩短整个工程的工期。AOE网中一定只有一条关键路径。简答题对于如图1 所示的有向图，试给出：1每个顶点的入度和出度；2邻接矩阵；3邻接表；1.（4逆邻接表；（5 强连通分量。【解答】（112122231，3、顶43，0523612。（2邻接矩阵：0001000100101000000111000000110100010010302345011223344556013 144逆邻接表：011412452313402445255625强连通分量：514623G 2 所示，试给出：1该图的邻接矩阵；2该图的邻接表；3该图的多

56、重邻接表；v2v5v1v4v74从出发的“深度优先遍历序列；5从出发的“广度优先遍历序列。v3v62.【解答】1该图的邻接矩阵：01100001010000100100001101100001001000100100001102该图的邻接表：0v1121v2022v3023v432454v5365v6366v7453该图的多重邻接表：v1v2 v30102v4v531 32343 5v6v764 654从v1 出发的“深度优先遍历序列：v1v2v4v3v5v7v65v1 v1v2v3v4v5v6v7用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否有关？【解答】n(n0)n2

57、个数与图的边数无关。设有向图G 如图3 所示，试画出列。G 的十字链表构造，并写出图 G 的两个拓扑序v2v5v1v3v6图 3.【解答】1G 的十字链表构造：0 v101021 v214152 v325v4v5435 v653542G 的两个拓扑序列： v1v2v3v6v5v4; 5如图 4 AOE 网：（1（2v1 v3 v2v6v5v4（3找出该 AOE 网中的关键路径，并答复完成该工程需要的最短时间。a 1=3Ba Ea 5=9a 9=5Aa3a4=7 CDaa 6=10aFHa 10 =3a 11 =2G图 41ve(A)=0ve(B)= ve(A)+3=3ve(C)= ve(A)+

58、5=5ve(D)=max(ve(B)+6, ve(C)+7)=12ve(E)= ve(D)+9=21ve(G)=ve(D)+8=20ve(F)= max(ve(D)+10, ve(G)+6)=26ve(H)= max(ve(E)+E, ve(G)+2, ve(F)+3)=29vl(H)=29vl(E)= vl(H)vl(F)= vl(H) 3=26vl(G)= min(vl(H)2, vl(F)6)=20vl(D)= min(vl(E)9, vl(F) 10, vl(G) 8)=12.vl(B)= vl(D)6=6vl(B)= vl(D)6=6vl(C)=vl(D) 7=5vl(A)=min(

59、vl(B)3,vl(C)5)= 02e(a1)=0e(a 7)=12e(a 2 )=0e(a 8 )=20e(a 3)=3e(a 9)=21e(a4)=5e(a5)=12e(a10)=26e(a11)=20e(a6)=12l(a1)=3 (a7)=12l(a2)=0 l(a8)=20l(a3)=6 l(a9)=24l(a4)=5 l(a10 )=26l(a5)=15 l(a11 )=27l(a6)=16间：29ADFa10=3a4=7a8=6a2=5a7=8CG课后习题解答(P152)选择题静态查找表与动态查找表的根本区别在于A 它们的逻辑构造不一样 B 施加在其上的操作不一样C所包含的数据元

60、素类型不一样 D 存储实现不一样在表长为 nA nB 1Cn+1Dn-1A。顺序查找适用于存储构造为CA 哈希存储 B压缩存储CD索引存储用顺序查找法对具有n个结点的线性表查找一个结点的时间复杂度为CAO(logn2)BO(nlogn)CO(n)D适用于折半查找的表的存储方式及元素排列要求为D。A方式存储，元素无序B方式存储，元素有序C顺序方式存储，元素无序D顺序方式存储，元素有有一个长度为12 的有序表，按折半查找法对该表进展查找，在表内各元素等概率况下查找成功所需的平均比拟次数为B。A35/12B37/12C39/1243/1271 391232416275778295，100 上进展折半