数据结构习题集.doc

《数据结构习题集.doc》由会员分享，可在线阅读，更多相关《数据结构习题集.doc（142页珍藏版）》请在三一办公上搜索。

1、数据结构习题集第一章 绪论16 试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值。 17 已知k阶裴波那契序列的定义为f0=0， f1=0， ， fk-2=0，fk-1=1；fn=fn-1 + fn-2 + + fn-k， n=k，k+1， 试编写求k阶裴波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。 18 假设有A，B，C，D，E五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中每一行的形式为编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。项目名称性 别校 名成 绩得 分 19 试编写算法，计算i！2i的

2、值并存入数组a 0.arrsize-1的第i-1个分量中（I=1，2，n）。假设计算机中允许的最大值为maxint，则当narrsize或对某个k（1kn）使k！2kmaxint时，应按出错处理。注意选择你认为较好的出错处理方法。20 试编写算法求一元多项式的值Pn（x）=aixi的值Pn（x0），并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为ai（I=0，1，n），x0和n，输出为Pn（x0）。第二章 线性表 本章算法设计题涉及的顺序表和线性链表的类型定义如下：#define LIST_INIT_SIZE 100#define LIST

3、INCREMENT 10typedef structElemttpe *elem; / 存储空间地址int length; /当前长度int listsize; /当前分配的存储容SqList; /顺序表类型typedef struct LnodeElemType data;Struct Lnode *next；Lnode,*LinkList; /线性链表类型2.10 指出以下算法中的错误和低效（即费时）之处，并将它改写为一个既正确又高效的算法。Status DeleteK(SqList&a,int i,int k) /本过程从顺序结构的线性表a中删除第i个元素起的k个元素if (i1ka .

4、length)return INFEASIBLE; /参数不合法else for(count=1;count=i+1;j-) a.elemj-1=a.elemj;a. length-;return OK;/DeleteK 2。11 设顺序表va中的数据元素递增有序.试写一算法，将x插入到顺序表的 适当位置上，以保持该表的有序性。 2。12 设A=（a1,am）和B=（b1,bn）均为顺序表,A/和B/分别为A和B中除去最大共同前缀后的子表（例如，A=（x，y，y，z，x，z），B=（x，y，y，z，y，x，x，z），则两者中最大的共同前缀为（x，y，y，z），在两表中除去最大共同前缀后的子表分

5、别为A/=（x，z）和B/=（y，x，x，z）。若A/=B/=空表，则A =B；若A/=空表，而B/空表，或者两者均不为空表，且A/的首元小于B/的首元，则A B；否则A B。试写一个比较A，B大小的算法（请注意：在算法中，不要破坏表A和B，并且，也不一定先求得A/和B才进行比较）。 2。13 试写一算法在带头结点得单链表结构上实现线性表操作LOCATE(L,X). 2。14 试写一算法在带头结点得单链表结构上实现线性表操作LENGTH(L). 2。15 已知指针ha和hb分别指向两个单链表得有结点，并且已知两个链表得长度分别为m和n。试写一算法将这两个链表连接在一起（即令其中一个表的首元结点

6、连在另一个表的最后一个之后），假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。 2。16 已知指针la和lb分别指向两个无头接点单链表中的首元接点，下列算法是从表la中删除自第I个偶，将元素起共len个元素后，将它们插入到表lb中第I个元素之前。试问此算法是否真确？若有错，则请改正之。Staus DeleteAndInsertSub (LinkedList la, LinkedList lb,int i,int j,int len)if(i0j0len0) return INFEASIBLE;P=la;k=l;While(knext;k

7、+;q=p;while (knext;k+;s=lb;k=1;while(knext;k+;s-next=p; q-next=s-next;return OK;/DeleteAndInsertSub217 试写一算法，在无头结点的动态单链表上实现线性表操作INSERT(L，i，b)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。218 同2.17题要求。试写一算法，实现线性表操作DELETE(L，i)。219 已知线性表中的元素以递增有序排列，并以单链表作存储结构。试写以高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素）同时释放被删结点空间，并分析你的

8、算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。 220 同2.19题条件，试写一高效的算法，删除表中相同的多值元素（使得操作后得线性表中得所有元素得值均不相同），同时释放被删结点空间，并分析你得算法得时间复杂度。2.21试写一算法，实现顺序表的就地拟置，即利用原表的存储空间将线性表（a1,a2,an）逆置为（an,an-1,a1）.2.22 试写一算法，对单链表实现就地逆置。2.23 设线性表A=（a1,a2,am）,B=(b1,b2,bn),试写一个按下列规则合并A,B为线性表C的算法，即使得 C=（a1,b1,am,bm,bm+1

9、,，bn） 当mn时 ;或者 C=（a1,b1,an,bn,an+1,，bm） 当mn时.线性表A,B和C均以单链表作存储结构，且C表利用表A和表B中的结点空间构成，注意：单链表的长度值m和n均未显示存储。2.24 假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表.2.25 假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的元素值各不相同），现要求另辟空间构成一个线性表C,其元素为A和B中元素的交集

10、，且C中的元素也依值递增有序排列，试对顺序表编写求C的算法。2.26 要求同2.25题，是对单链表编写求C的算法。2.27 对2.25题的条件作以下两点修改，对顺序表重新编写求得表C的算法。 假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同; 利用表A的空间存放表C.2.28 对2.25题的条件作以下两点修改, 对顺序表重新编写求得表C的算法.假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同; 利用原表(A表或B表)中的结点构造C,并释放A表中的无用结点。2.29 已知A,B和C为三个递增有序的线性表，现要求对A表作如下操作：

11、删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法时间复杂度（注意：题中没有特别指明同一表中的元素值各不相同）。2.30 要求同2.29题，试写对单链表的编写算法，请释放A表中的无用结点。2.31 假设某个单向链表的长度大于1，且表中既无结点也无头指针。已知s为指向链表中的某个节点的指针，试编写算法在链表中删除指针s所指接点的前驱结点。2.32 已知有一个单项循环链表，其每个结点中含三个域：pre,data,和next,其中data为数据域，next为指向后继结点的指针域，pre业为指针域，但它的值为空（NULL）.是编写算法将此单项循环链表改为双向循

12、环链表，即使pre成为指向前驱结点的指针域。2.33 已知有一个线性链表表示的线性表中含有三类字符的数据元素，（如字母字符，数据字符和其他字符），试编写算法将该线性表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。 在2.34至2.36题中，“异或指针双向链表”类型XorLinkedList和指针异或函数XorP定义为： Typedef struct XorNode char data ; struct NorNode LRPtr； XorNode,*XorPointer; Typedef struct /无头结点的异或指针双向链表 XorPointer Left, Righ

13、t; /分别指向链表的左端和右端 XorLinkedList； XorPointer XorP(XorPointer p, XorPointer q); /指针异或函数XorP返回指针p和q的异或（XOR）值2.34 假设在算法描述语言中引入指针的二元运算“异或”（用“”表示），若a和b为指针，则ab的运算结果仍为原指针类型，且 a(ab)=(aa)b=b (ab)b=a(bb)=a 则可利用一个指针域来实现双向链表L。链表中的每个结点只含两个域：data域和LRPtr域，其中LRPtr域存放该结点的左邻和右邻的结点指针(不存放在NULL)的异或。若设指针L.Left指向链表中的最左结点，L.

14、Right指向链表中的最右结点，则可实现从左向右或从右向左遍历此双向链表的操作。试写一算法，按任一方向依次输出链表中的各元素值。2.35 采用2.34题所述的存储结构，写出在第i个结点的算法。2.36 采用2.34题所述的存储结构，写出删除第i个结点的算法。2.37 设一带结点的双向循环链表表示的线性表L=(a1,a2,an).试写一个时间复杂度为O（n）的算法，将L改造为（a1,a3,an,a4,a2）。2.38 设有一个双向循环列表，每个结点中除了有pre,data,next三个域外，还增设了一个访问频度freq。在链表被启用之前，频度域freq的值均初始化为零，而每当用链表进行一次LOC

15、ATE(L,x)的操作后，被访问的结点（即元素值等于x的结点）中的频度域freq的值便增一，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合以上要求的LOCATE操作算法。 在2.39至2.40题中，稀疏多项式采用的顺序存储结构SqPoly定义为 typedef struct int coef; int exp PolyTerm; typedef struct PolyTerm *data; int last; SqPoly;2.39 已知多项式Pn(X)=c1xe1+c2xe2+cmxem,其中n=emem-1e10,

16、ci0(i=1,2,m),m1.试采用存储量同多项式项数m成正比的顺序存储结构，编写求Pn(x0)的算法（x0为给定值），并分析你的算法的时间复杂度。2.40 采用2.39题给定的条件和存储结构，编写求P(x)=Pn1(x)-Pn2(x)的算法，将结果多项式存放在新辟的空间中，并分析你的算法的时间复杂度。 在2.41至2.42题中，稀疏多项式采用的循环链表存储结构LinkedPoly定义为 typedef struct PolyNode PolyTerm data; Struct PolyNode *next; PolyNode,* PolyLink;Typedef PolyLink Link

17、edPoly;2.41 试以循环链表作稀疏多项式的存储结构，编写求其导函数的算法 ，要求利用原多项式中的结点空间存放其导函数(多项式)，同时释放所有的无用（被删）结点。2.42 试编写算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间构成这两个链表。第三章 栈和队列3.15 假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别为设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化inistack(tws)、入栈push(tws,i,x)和出栈pop(tws,i)的算法，其中i

18、为0或者1，用以分别指示设在数组两端的两个栈，并讨论按过程（正/误状态变量可设为参变）或函数设计这些操作算法各有什么优缺点。3.16 假设如题3.1所述火车调度站的入口处有n节硬席或软席车厢（分别以H和S表示）等待调度，试编写算法，输出对这n节车厢进行调度的操作（即入栈或出栈操作）序列，以使所有的软席车厢都被调整到硬席车厢之前。3.17 试写一个算法，识别依次读入的一个以为结束符的字符序列是否为形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是属该模式的字符序列，而13&3-1则不是。3.18 试写一个判别表达式中开、闭括号是否

19、配对出现的算法。3.19 假设一个算术表达式中可以包含三种括号：圆括号“（”和“）”、方括号“”和“”和花括号“”和“”，且这三种括号可按任意的次序嵌套使用（如：()）。编写判别给定表达式中所含括号是否正确配对出现的算法（已知表达式已存入数据元素为字符的顺序表中）。3.20 假设以二维数组g(1.m,1.n)表示一个图像区域，gi,j表示该区域中点（i,j）所具颜色，其值为从0到k的整数。试编写算法置换点(i0,j0)所在区域的颜色。约定和(i0,j0)同色的上下左右的邻结点为同色区域的点。3.21假设表达式为单字母变量和双目四则运算符构成。试写一算法，降一个通常书写形式且书写正确地表达式转换

20、为逆波兰式。3.22如题3.21的假设条件，试写一算法，对以逆波兰式表示的表达式求值。3.23如题3.21的假设条件，试写一算法，判断给定的非空后缀表达式是否为正确的逆波兰式（即后缀表达式）。如果是，则将它转化为波兰式（即前缀表达式）。3.24 试编写如下定义的 递归算法，并根据算法画出求g(5,2)时栈的变化过程。 3.25 试写出求递归函数 F（n）的递归算法，并消除递归：3.26 求解平方根 A的迭代函数定义如下：其中，P是A的近似平方根，e是结果允许误差。试写出相应的递归算法，并消除递归。3.27 以知Aackerman函数的定义如下：（1） 写出递归算法；（2） 写出非递归算法；（3

21、） 根据非递归算法，画出求akm（2，1）时栈的变化过程。3.28 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。3.29 如果希望循环队列的元素都能得到利用，则需设置一个标域tag，并以tag的值为0或1来区分，尾指针和头指针相同时的队列状态是“空”的还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（如当循环队列容量较小而队列中每个元素占的空间较多时，哪一种方法较好）。330 假设将循环队列定义为：以域变量rear和length分别指示循环队列

22、中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。331 假设称正读和反读都相同的字符序列为“回文”，例如，abba和abcba是回文，abcde和ababab则不是回文。试写一个算法判别读入的一个以为结束符的字符序列是否是“回文”。332 试利用循环队列编写求k阶斐波那契序列中前n+1项（f0,f1,fn）的算法，要求满足：fnmax而fn+1max，其中max为某个约定的常数。（注意：本题所用循环队列的容量仅为k，则在算法结束时，留在循环队列中的元素应是所求k阶斐波那契序列中的最后k项fn-k+1,fn）。 3

23、33 在顺序存储结构上实现输出受限的双端循环队列的入列和出列（只允许队头出列）算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。 334 假设在如教科书341节中图39所示的铁道转轨图的输入端有n节车厢：硬座、硬卧和软卧（分别以 P,H和S表示）等待调度，要求这三种车厢在输出端铁道上的排列次序为：硬座在前，软卧在中，硬卧在后。试利用输出受限的双端队列对这n节车厢进行调度，编写算法输出调度的操作序列：分别以字符E 和D表示对双端队列的头端进行入队列和出队列是操

24、作；以字符A表示对双端队列的尾端进行入队列的操作。 第四章 串在编写410至414题的算法时，请采用StringType数据类型：StringType 是串的一个抽象数据类型，它包含以下五种基本操作：Void StrAssign(StringType&t, StringType s)/将s的值赋给t。s的实际参量可以是串变量或者串常量（如：abcd）。Int StrCompare(StringType s,StringType t)/比较s 和t。若st，返回值0；若s=t ，返回值=0；若st，返回值0。Int StrLength(StringType s)/返回s中的元素个数，即该串的长度

25、。StringType Concat(StringType s,StringType t)/返回由s和t联接而成的新串。StringType SubString(StringType s,int start,int len)/当1startStrLength(s)且0lenStrLength(s)-start+1时，/返回s中第start个字符起长度为len的字串，否则返回空串。 410 编写对串求逆的递推算法。 411 编写算法，求得所有包含在串s中而不包含在串t中的字符（s中重复是字符只选一个）构成的新串r，以及r 中每个字符在s中第一次出现的位置。 412 编写一个实现串的置换操作Rep

26、lace(&S,T,V)的算法。 413 编写算法，从串s中删除所有和串t相同的字串。 414 利用串的基本操作以及栈和集合的基本操作，编写“由一个算法表达式的前缀式求后缀式”的递推算法（假设前缀式不含语法错误）。 在编写415至420题的算法时，请采用教科书421节中所定义的定长顺序存储表示，而不允许调用串的基本操作。 415 编写算法，实现串的基本操作StrAssign(&T,chars)。 416 编写算法，实现串的基本操作 StrCompare(S,T)。 417 编写算法，实现串的基本操作 Replace(&S,T,V)。 418 编写算法，求串s所含不同字符的总数和每种字符的个数。

27、 419 在串的定长顺序存储结构上直接实现411题要求的算法。 420 编写算法，从串s中删除所有和串t相同的字串。421 假设以结点大小为1（且附设头结点）的链表结构表示串。试编写实现下列六种串的基本操作StrAssign,StrCopy,StrCompare,StrLength,Concathe 和SubString的函数。 422 假设以块链结构表示串。试编写将串s插入到串t中某个字符之后的算法（若串t中不存在此字符，则将串s联接在串t的末尾）。423 假设以块链结构作串的存储结构。试编写判别给定串是否具有对称性的算法，并要求算法的时间复杂度为O(StrLength(S)。 在编写424

28、至426题的算法时，请采用教科书422节中所定义的堆分配存储表示。 424 试写一算法，在串的堆存储结构上实现串基本操作Concat(&T,s1,s2). 425 试写一算法，实现堆存储结构的串的置换操作Replace(&S,T,V)。 426 试写一算法，实现堆存储结构的串的插入操作StrInsert(&S,pos,T)。 427 当以教科书421节中定义的定长顺序结构表示串时，可如下所述改进定位函数的算法：先将模式串t中的第一个字符和最后一个字符与主串s中相应的字符比较，在两次比较都相等之后，再依次从t的第二个字符起逐个比较。这样做可以克服算法Index（算法45）在求模式串akb(ak表

29、示连续k 个字符a)在主串anb(kn)中的定位函数时产生的弊病。试编写上述改进算法，并比较这两种算法在作Index(anb,akb)运算时所需要进行的字符间的比较次数。假设以结点大小为（带头结点）的链表结构表示串，则在利用next函数值进行串匹配时，在每个结点中需设三个域：数据域chdata、指针域succ和指针域next。其中chdata域存放一个字符；succ域存放指向同一链表中后继结点的指针；next域在主串中存放指向同一链表中前驱结点的指针；在模式串中，存放指向当该结点的字符和主串中的字符不等时。模式串中下一个应进行比较的字符结点（即与该结点字符的next函数值相对应的字符结点）的指

30、针，若该结点字符的next函数值为零，则其next域的值应指向头结点。试按上述定义的结构改写求模式串的next函数值的算法。试按题定义的结构改写串匹配的改进算法（KMP算法）。假设以定长顺序存储结构表示串，试设计一个算法，求串s中出现是第一个最长重复子串及其位置，并分析你的算法的时间复杂度。假设以定长顺序存储结构表示串，试设计一个算法，求串s和串t的一个最长公共子串，并分析你的算法的时间复杂度。若要求第一个出现的最长公共子串（即它在串s和串td最左边的位置上出现）和所有的最长公共子串，讨论你的算法能否实现。 第五章数组与广义表试设计一个算法，将数组An中的元素A0至An+1循环右移k位，并要求

31、只要一个元素大小的附加存储，元素移动或交换次数为O(n). 519 若矩阵Am+n中的某个元素aij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵Am*n，试编写求出矩阵中所有马鞍点的算法，并分析你的算法在最坏情况下的时间复杂度。 520 类似于以一维数组表示一元多项式，以m维数组：（aj），0jin,i=1,2,m,表示m元多项式，数组元素表示多项式中的系数。例如，和二元多项式x2+3xy+4y2-x+2相应的二维数组为试编写一个算法将m维数组表示的m元多项式以常规表示的形式（按降幂顺序）输出。可将其中一项印成ckx1Ee1xmEem（

32、其中m,ck和ej(j=1,2,m)印出它们具体的值），当ck或ej(j=1,2,m)为1时，ck的值或”E”和ej的值可省略不印。 5.21 假设稀疏矩阵A和B均以三元组顺序表作为存储结构。试写出矩阵相加的算法，另设三元组C存放结果矩阵。 522 假设系数矩阵A和B均以三元组顺序表作为存储结构。试写出满足以下条件的矩阵相加的酸法；假设三元组顺序表A的空间足够大，将矩阵B加到矩阵A上，不增加A,B之外的附加空间，你的算法能否达到O(m,n)的时间复杂度？其中m和n分别为A,B矩阵中非零元的数目。 5.23 三元组顺序表的一种变型是，从三元组顺序表中去掉行下标域得到二元组顺序表，另设一个行起始向

33、量，其每个分量是二元组顺序表的一个下标值，指示该行中第一个非零元素在二元组顺序表中的起始位置。试编写一个算法 ，由矩阵元素的下标值i，j求矩阵元素。试讨论这种方法和三元组顺序表相比有什么优缺点。 524 三元组顺序表的另一种变型是，不存矩阵元素的行、列下标，而存非零元在矩阵中以行为主序时排列的顺序号，即在LOC(0,0)=1,l=1时按教科书5.2节中公式（5-2）计算出的值。试写一算法，由矩阵元素的下标值i，j求元素的值。 5.25 若将稀疏矩阵A的非零元素以行序为主序的顺序存于一维数组V中，并用二维数组B表示A中的相应元素是否为零元素（以0和1分别表示零元素和非零元素）。例如，可用V=(1

34、5,22,-6,9)和表示。试写一算法，实现在上述表示法中实现矩阵相加的运算。并分析你的算法的时间复杂度。 526 试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。 527 试按教科书5 .3.2节中定义的十字链表存储表示编写将稀疏矩阵B加到稀疏矩阵A上的算法。 528 采用教科书5.6节中给出的m元多项式的表示方法，写一个求m元多项式中第一变元的偏导数的算法。 529 采用教科书5.6节中给出的m元多项式的表示方法，写一个m元多项式相加的算法。 530 试按表头、表尾的分析方法重写求广义表的深度的递归算法。 531 试按教科书5.5节图5.10所示结点结构编写复制

35、广义表的递归算法。 532 试编写判别两个广义表是否相同的递归算法。 533 试编写递归算法，输出广义表中所有原子项及其所在层次。 5.34 试编写递归算法，逆转广义表中的数据元素。 例如：将广义表 （a,(b,c),(),(d),e),f)） 逆转为： （f,(e,(d)）,(),(c,b),a）. 5.35 假设广义表按如下形式的字符串表示。 （1，2，n ） n0 其中i或为单字母表示的原子，或为广义表；n=0时为只含空格字符的空表（ ）。 试按教科书5.5节图5.8所示链表结点结构编写，按照写入的一个广义字符串建立其存储结构的递归算法。 5.36 按教科书5.5节图5.8所示链表结点结

36、构编写按上题描述的格式输出广义表的递归算法。 5.37 试编写递归算法，删除广义表中所有值等于x的原子项。 5.38 试编写算法，依次从左到右输出广义表中第l层的原子项。 例如：广义表（a,(b,c)）,(d)中的a为第一层的原子项；b和d为第二层的原子项；c为第三层的原子项。第六章 树与二叉树 6.33 假定用两个一堆数组L1.n和R1.n作为有n个结点的二叉树的存储结构，Li和Ri分别指示结点i的左孩子和右孩子，0表示空。试写一个算法判别结点u是否为结点v的子孙。6.34 同6.33题的条件。先由L和R建立一维数组T1.n，使T中第i（i=1，2，n）个分量指示结点i的双亲，然后写判别结点

37、u是否为结点v的子孙的算法。 在以下6.36至6.38和6.41至6.53题中，均以二叉链表作为二叉树的存储结构。6.36 若已知两棵二叉树B1和B2皆为空，或者皆不空且B1的左、右子树和B2的左、右子树分别相似，则称二叉树B1和B2相似。试编写算法，判别给定两棵二叉树是否相似。 6.37 试利用栈的基本操作写出先序遍历的非递归形式的算法。6.38 同6.37题条件，写出后序遍历的非递归算法（提示：为分辨后序遍历时两次进栈的不同返回点，需在指针进栈时同时将一个标志进栈）。 6.39 假设在二叉链表的结点中增设两个域：双亲域（parent）以指示其双亲结点；标志域（mark取值0.2）以区分在遍

38、历过程中到达该结点时应继续向左或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。 6.40 若在二叉链表的结点中只增设一个双亲域以指示其双亲结点，则在遍历过程中能否不设栈？试以此存储结构编写不设栈进行中序遍历的递推形式的算法。 6.41 编写递归算法，在二叉树中求位于先序序列中第k个位置的结点的值。 6.42 编写递归算法，计算二叉树中叶子结点的数目。 6.43 编写递归算法，将二叉树中所有结点的左、右子树相互交换。6.44 编写递归算法：将二叉树中以元素值为x的结点为根的子树的深度。 6.45 编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释

39、放相应的空间。6.46 编写复制一棵二叉树的非递归算法。 6.47 编写按层次顺序（同一层自左至右）遍历二叉树的算法。 6.48 已知在二叉树中，* root为根结点，* p和* q为二叉树中两个结点，试编写求距离它们最近的共同祖先的算法。 6.49 编写算法判别给定二叉树是否为完全二叉树。 6.50 假设以三元组（F,C,L/R）的形式输入一棵二叉树的诸边（其中F表示双亲结点的标识，C表示孩子结点标识，L/R表示C为F的左孩子或右孩子），且在输入的三元组序列中，C是按层次顺序出现的。设结点的标识是字符类型。F=时C为根结点标识，若C也为，则表示输入结束。例如，6.15题所示二叉树的三元组序列

40、输入格式为：ALABLACRBDLCELCFRDGRFHL L试编写算法，由输入的三元组序列建立二叉链表。 6.51 编写一个算法，输出以二叉树表示的算法表达式，若该表达式中含有括号，则在输出时应添上。6.52 一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积。试写一算法，求二叉树的繁茂度。6.53 试编写算法，求给定二叉树上从根结点到叶子结点的一条其路径长度等于树是深度减一的路径（即列出从根结点到该叶子结点的结点序列），若这样的 路径存在多条，则输出路径终点（叶子终点）在“最左”的一条。 6.54 已知一棵完全二叉树存于顺序表sa中，sa.elem1.sa.last含结点值。试编写

41、算法由此顺序存储结构建立该二叉树的二叉链表。6.55 为二叉链表的结点增加DescNum域。试写一算法，求二叉树的每个结点的子孙数目并存入其DescNum域。并给出算法的时间复杂度。 6.56 试写一个算法，在先序后继线索二叉树中，查找给定结点 * p在先序序列中的后继（假设二叉树的根结点未知）。并讨论实现此算法对存储结构有何要求？6.57 试写一个算法，在后序后继线索二叉树中，查找给定结点 * p在后序序列中的后继（二叉树的根结点指针并未给出）。并讨论实现算法对存储结构有何要求？ 6.58 试写一个算法，在中序全线索二叉树的结点 * p之下，插入一棵以结点 * x为根、只有左子树的中序全线索

42、二叉树，使 * x为根的二叉树成为 * p的左子树。若 * p原来有左子树，则令它为 * x的右子树。完成插入之后的二叉树应保持全线索化特性。6.59 编写算法完成下列操作：无重复地输出以孩子兄弟链表存储的树T中所有的边。输出的形式为（k1，k2），（ki，kj），其中，ki和kj为树结点中的结点标识。 6.60 试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子的个数。6.61 试编写算法，求一棵以孩子-兄弟链表表示的树的度。 6.62 对以孩子-兄弟链表表示的树编写计算树的深度的算法。6.63 对以孩子链表表示的树编写计算树的深度的算法。6.64 对以双亲表表示的树编写计算树的深度的算法。

43、 6.65 已知一棵二叉树的前序序列和中序序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。 6.66 假设有n个结点的树T采用了双亲表示法，写出由此建立树的孩子-兄弟链表的算法。6.67 假设以二元组（F,C）的形式输入一棵树的诸边（其中F表示双亲结点的标识， C表示孩子结点标识），且在输入的二元组序列中，C是按层次顺序出现的。F=时C为根结点标识，若C也为，则表示输入结束。例如，如下所示树的输入序列为试编写算法，由输入的二元组序列建立树的孩子-兄弟链表。6.68 已知一棵树的由根至叶子结点按层次输入的结点序列及每个结点的度（每层中自左至右输入），试写出构造此树的孩子-兄弟链表的算法。 6.69 假设以二叉链表存储的二叉树中，每个结点所含数据元素均为单字母，试编写算法，按树状打印二叉树的算法。例如：左下二叉树印为右下形状。6.70 如果用大写字母标识二叉树结点，则一棵二叉树可以用符合下面语