下载文档原格式
第三次作业第三章栈和队列一、选择题1. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ D ）。
A. i-j-1B. i-jC. j-i+1D. 不确定的2. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ AD ）。
A. |top[2]-top[1]|=0B. top[1]+1=top[2]C. top[1]+top[2]=mD.top[1]=top[2]3. 栈在（ D ）中应用。
A. 递归调用B. 子程序调用C. 表达式求值D. A，Ｂ，Ｃ4. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（ D ），其中^为乘幂。
A. 3,2,4,1,1；(*^(+*-B. 3,2,8；(*^-C. 3,2,4,2,2；(*^(-D. 3,2,8；(*^(-5. 用链接方式存储的队列，在进行删除运算时（ D ）。
A. 仅修改头指针B. 仅修改尾指针C. 头、尾指针都要修改D. 头、尾指针可能都要修改6. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ A ）。
A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m7. 栈和队列的共同点是（ C ）。
A. 都是先进先出B. 都是先进后出C. 只允许在端点处插入和删除元素D. 没有共同点8. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( C )。
A． 6 B. 4 C. 3 D. 2二、判断题1.消除递归不一定需要使用栈，此说法（√）2. 栈是实现过程和函数等子程序所必需的结构。
第三章习题1.按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：⑴如进站的车厢序列为123，则可能得到的出站车厢序列是什么？⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。
（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。
2.设队列中有A、B、C、D、E这5个元素，其中队首元素为A。
如果对这个队列重复执行下列4步操作：（1）输出队首元素；（2）把队首元素值插入到队尾；（3）删除队首元素；（4）再次删除队首元素。
直到队列成为空队列为止，得到输出序列：（1）A、C、E、C、C （2） A、C、E（3） A、C、E、C、C、C （4） A、C、E、C3.给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？4.按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ5.试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1& 序列2’模式的字符序列。
其中序列1和序列2中都不含字符’&’，且序列2是序列1的逆序列。
例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。
6.假设表达式由单字母变量和双目四则运算算符构成。
试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。
7.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。
8.要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。
9.简述以下算法的功能（其中栈和队列的元素类型均为int）：（1）void proc_1(Stack S){ int i, n, A[255];n=0;while(!EmptyStack(S)){n++; Pop(&S, &A[n]);}for(i=1; i<=n; i++)Push(&S, A[i]);}（2）void proc_2(Stack S, int e) { Stack T; int d;InitStack(&T);while(!EmptyStack(S)){ Pop(&S, &d);if (d!=e) Push( &T, d);}while(!EmptyStack(T)){ Pop(&T, &d);Push( &S, d);}}（3）void proc_3(Queue *Q){ Stack S; int d;InitStack(&S);while(!EmptyQueue(*Q)){DeleteQueue(Q, &d);Push( &S, d);}while(!EmptyStack(S)){ Pop(&S, &d);EnterQueue(Q，d)}}实习题1．回文判断。
第三章习题1.按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：⑴如进站的车厢序列为123，则可能得到的出站车厢序列是什么？⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。
（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。
2.设队列中有A、B、C、D、E这5个元素，其中队首元素为A。
如果对这个队列重复执行下列4步操作：（1）输出队首元素；（2）把队首元素值插入到队尾；（3）删除队首元素；（4）再次删除队首元素。
直到队列成为空队列为止，得到输出序列：（1）A、C、E、C、C （2） A、C、E（3） A、C、E、C、C、C （4） A、C、E、C3.给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？4.按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ5.试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1& 序列2’模式的字符序列。
其中序列1和序列2中都不含字符’&’，且序列2是序列1的逆序列。
例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。
6.假设表达式由单字母变量和双目四则运算算符构成。
试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。
7.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。
8.要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。
9.简述以下算法的功能（其中栈和队列的元素类型均为int）：（1）void proc_1(Stack S){ int i, n, A[255];n=0;while(!EmptyStack(S)){n++; Pop(&S, &A[n]);}for(i=1; i<=n; i++)Push(&S, A[i]);}（2）void proc_2(Stack S, int e){ Stack T; int d;InitStack(&T);while(!EmptyStack(S)){ Pop(&S, &d);if (d!=e) Push( &T, d);}while(!EmptyStack(T)){ Pop(&T, &d);Push( &S, d);}}（3）void proc_3(Queue *Q){ Stack S; int d;InitStack(&S);while(!EmptyQueue(*Q)){DeleteQueue(Q, &d);Push( &S, d);}while(!EmptyStack(S)){ Pop(&S, &d);EnterQueue(Q，d)}}实习题1．回文判断。
数据结构第三章的习题答案数据结构第三章的习题答案在学习数据结构的过程中，习题是巩固知识和提高能力的重要方式。
第三章的习题主要涉及线性表、栈和队列的实现和操作。
本文将对这些习题进行解答，并给出详细的步骤和思路。
1. 第一题要求实现一个线性表的插入操作。
线性表是一种常用的数据结构，它的特点是元素之间存在一对一的关系。
要实现插入操作，首先需要定义线性表的数据结构，可以使用数组或链表来实现。
然后，根据插入位置，将插入位置之后的元素依次后移，为要插入的元素腾出空间。
最后，将要插入的元素放入插入位置。
2. 第二题要求实现一个栈的压栈和出栈操作。
栈是一种后进先出（LIFO）的数据结构，可以使用数组或链表来实现。
压栈操作就是将元素放入栈顶，出栈操作就是将栈顶元素取出并删除。
要实现这两个操作，可以使用一个指针来指示栈顶位置，每次压栈时将指针加一，出栈时将指针减一。
需要注意的是，栈满时不能再进行压栈操作，栈空时不能进行出栈操作。
3. 第三题要求实现一个队列的入队和出队操作。
队列是一种先进先出（FIFO）的数据结构，同样可以使用数组或链表来实现。
入队操作就是将元素放入队尾，出队操作就是将队头元素取出并删除。
与栈不同的是，队列需要维护队头和队尾两个指针。
每次入队时将元素放入队尾，并将队尾指针后移一位；出队时将队头元素取出，并将队头指针后移一位。
需要注意的是，队列满时不能再进行入队操作，队列空时不能进行出队操作。
4. 第四题要求实现一个栈的括号匹配算法。
括号匹配是一种常见的应用场景，例如编程语言中的括号匹配。
要实现这个算法，可以使用栈来辅助。
遍历字符串中的每个字符，如果是左括号，则将其压入栈中；如果是右括号，则将栈顶元素取出并判断是否与右括号匹配。
如果匹配，则继续遍历下一个字符；如果不匹配，则说明括号不匹配，返回错误。
最后，如果栈为空，则说明括号匹配成功；如果栈不为空，则说明括号不匹配，返回错误。
5. 第五题要求使用栈实现一个逆波兰表达式的计算器。
第3章作业答案一、填空1. 向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。
2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。
不允许插入和删除运算的一端称为栈底。
3. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
4.在具有n个单元的循环队列中，队满时共有n-1 个元素。
设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。
在进栈或进队操作时，按a1、a2、a3、a4次序每次进入一个元素。
假设栈或队的初始状态都是空。
现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A ，第二次出栈得到的元素是 B 是；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C ，第二次出队得到的元素是 D 。
经操作后，最后在栈中或队中的元素还有E个。
供选择的答案：A～D：①a1 ②a2 ③a3 ④a4E：①1 ②2 ③3 ④0答：ABCDE＝2, 4, 1, 2, 2栈是一种线性表，它的特点是 A 。
设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。
往栈中推入（PUSH）一个新元素时，变量T的值 B ；从栈中弹出（POP）一个元素时，变量T的值 C 。
设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D ，变量T的值是 E 。
供选择的答案：A：①先进先出②后进先出③进优于出④出优于进⑤随机进出B，C：①加1 ②减1 ③不变④清0 ⑤加2 ⑥减2D：①a,b ②b,c ③c,a ④b,a ⑤c,b ⑥a,cE：①n+1 ②n+2 ③n ④n-1 ⑤n-2答案：ABCDE=2, 2, 1, 6, 4在做进栈运算时，应先判别栈是否 A ；在做退栈运算时，应先判别栈是否 B 。
... 数据结构与算法上机作业第三章树一、选择题1、在一棵树中，如果结点 A 有3 个兄弟， B 是A 的双亲，则 B 的度为 DA. 1B. 2C. 3D. 42、深度为h 的完全二叉树至少有 D 个结点，至多有 B 个结点A. 2 hB. 2h-1C. 2h+1D. 2h-12^(h-1) -1 +1=2^(h-1)前（n-1）层满，第h 层只有一结点3、具有n 个结点的满二叉树有 C 个叶结点。
A. n/2B. (n-1)/2C. (n+1)/2D. n/2+1因为二叉树中，有这样一个性质，如果其终端结点数（也就是叶子节点）的个数为n1，度为 2 的结点数为n2，则n1=n2+1;假设叶子节点有x 个，则度为 2 的个数为x-1：所以：2x-1 = n; 所以x = (n+1)/2 ( 满二叉树)所以叶子节点个数为：(n+1)/2非终端结点为：(n+1)/2-14、一棵具有25 个叶结点的完全二叉树最多有 B 个结点。
A. 48B. 49C. 50D. 515、已知二叉树的先根遍历序列是ABCDEF ，中根遍历序列是CBAEDF ，则后根遍历序列是A 。
A. CBEFDAB. FEDCBAC. CBEDFAD. 不定6、具有10 个叶结点的二叉树中有 B 个度为 2 的结点。
A. 8B. 9C. 10D. 117、一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足 C 。
A. 所有非叶结点均无左孩子B. 所有非叶结点均无右孩子C. 只有一个叶子结点D. A 和B 同时成立8、在线索二叉树中，t 所指结点没有左子树的充要条件是B。
A. t->left=NULLB. t->ltag=TRUEC. t->ltag=TRUE 且t->left=NULLD. 以上都不对9、n 个结点的线索二叉树上含有的线索数为C。
A. 2nB. n-1C. n+1D. nn-1 表示结点的左右子树，其余n-1 指针为空线索取代原来的空链10、二叉树按照某种顺序线索化后，任一结点都有指向其前驱和后继的线索，这种说法 B 。
数据结构第三章习题本文共分为三部分，分别针对数据结构第三章中的不同习题进行解答。
第一部分，解答关于树和二叉树的习题。
1.对于给定的有“n(n>0)”个结点的树，边数应为“n-1”条。
解析：树是一种无环连通无向图，因此任意n个结点的树有n-1条边。
2.往2（2≤n≤64）叉树的每个结点上添加一个数据元素，设计一个数据结构，实现迅速求该2叉树中所有结点的数据元素之和。
解析：可以使用先序遍历算法来完成，先序遍历树的根节点，然后递归遍历左子树和右子树，将每个结点的数据元素加和。
3.设计一个算法，判定给定的二叉树是否是完全二叉树。
解析：可以使用层次遍历算法来判定。
如果一棵树是完全二叉树，那么层次遍历结果中，如果一些结点有右孩子，那么该结点之后的所有结点都必须有孩子；如果一些结点没有右孩子，则该结点之后的所有结点都不能有孩子。
4.设有一棵完全二叉树，编写算法，生成一棵采用二叉链表存储结构的二叉树。
解析：可以使用层次遍历算法来构建树。
从根节点开始，依次按层次遍历的顺序遍历所有结点，依次将结点和它的孩子结点用链表链接起来。
第二部分，解答关于图的习题。
1.利用邻接表存储图，写出一个算法，判断两个节点之间是否存在路径。
解析：可以使用深度优先算法或广度优先算法来判断两个节点之间是否存在路径。
首先从起始节点开始，遍历其邻接节点，递归或使用队列来保存需要遍历的节点，直到遍历到目标节点或遍历完所有的节点。
2.利用邻接表存储图，写出一个算法，求图的连通分量个数。
解析：可以使用深度优先算法或广度优先算法来求图的连通分量个数。
首先从起始节点开始，遍历其邻接节点，标记遍历过的节点，直到遍历完所有的节点。
每次从一个未标记的节点开始进行遍历，当所有的节点都被遍历过后，即可得到图的连通分量个数。
3.利用邻接表存储图，写出一个算法，判断给定的图是否为无向图。
解析：可以遍历所有的边，对于每一条边(u,v)，如果(u,v)存在，则判断(v,u)是否存在，如果都存在，则图为无向图，否则为有向图。
第三章习题解答1.分别写出对链栈的入栈和出栈操作的算法。
链栈的结点类型定义如下：Typedef struct stacknode {SElemtype data;struct stacknode *next;}stacknode, *linkstack;入栈操作：Status push( linkstack &S, SElemtype e){ p=(linkstack)malloc(sizeof(stacknode));If (!p) return ERROR;p->data=e;p->next=S;S=p;return OK;}出栈操作：Status pop(linkstack &S, SElemtype &e){ if (!S) return ERROR;p=s;s=p->next;free(p);return OK;}P24/3.15假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。
试编写实现这个双向栈tws的三个操作：初始化inistack(tws),入栈push(tws,i,x)和出栈pop(tws,i)的算法，其中i为0或1，用以分别指示设在数组两端的两个栈，并讨论按过程（正/误状态变量可设为变参）或函数设计这些操作算法各有什么优缺点。
双栈的结构类型定义如下：typedef struct{Elemtype *base[2];Elemtype *top[2];}BDStacktype; //双向栈类型栈的初始化操作：status Init_Stack(BDStacktype &tws,int m)//初始化一个大小为m的双向栈tws{ tws.base[0]=(Elemtype*)malloc(m*sizeof(Elemtype));tws.base[1]=tws.base[0]+m-1;tws.top[0]=tws.base[0];tws.top[1]=tws.base[1];return OK;}入栈操作：Status push(BDStacktype &tws,int i,Elemtype x) // x入栈,i=0表示低端栈,i=1表示高端栈{ if (tws.top[0]>tws.top[1]) return OVERFLOW;//注意此时的栈满条件if (i==0) *tws.top[0]++=x;elseif (i==1) *tws.top[1]--=x;else return ERROR;return OK;}出栈操作：Status pop(BDStacktype &tws, int i, Elemtype &x) // x出栈,i=0表示低端栈,i=1表示高端栈{ if (i==0){ if (tws.top[0]==tws.base[0]) return OVERFLOW;x=*--tws.top[0];}else if (i==1){ if (tws.top[1]==tws.base[1]) return OVERFLOW;x=*++tws.top[1];}else return ERROR;return OK;}P24/3.18试写一个判别表达式中开、闭括号是否配对出现的算法。
数据结构第1～3章作业参考答案【1.4】【解法一】⑴抽象数据类型复数：ADT Complex{数据对象：D={ci|ci∈R, i=1,2, 其中R为实数集}数据关系：R={<c1,c2>| ci∈D, i=1,2, 其中c1为复数实部, c2为复数虚部}基本操作：InitComplex (&C,v1,v2)操作结果：构造一个复数C，元素c1, c2分别被赋以参数v1, v2的值。
DestroyComplex(&C)初始条件：复数C已存在。
操作结果：销毁复数C。
GetReal(C, &e)初始条件：复数C已存在。
操作结果：用e返回复数C实部的值。
Get Imaginary(C, &e)初始条件：复数C已存在。
操作结果：用e返回复数C虚部的值。
SetReal(&C, e)初始条件：复数C已存在。
操作结果：用e更新复数C实部的值。
Set Imaginary(&C, e)初始条件：复数C已存在。
操作结果：用e更新复数C虚部的值。
AdditionComplex (&C, C1, C2)初始条件：复数C1，C2已存在。
操作结果：复数C1与复数C2相加，用复数C返回其和。
SubstractComplex(&C, C1, C2)初始条件：复数C1，C2已存在。
操作结果：复数C1减去复数C2，用复数C返回其差。
MultipleComplex(&C, C1, C2 )初始条件：复数C1，C2已存在。
操作结果：复数C1与复数C2相乘，用复数C返回其积。
DividedComplex(&C, C1, C2)初始条件：复数C1，C2已存在，且C2≠0。
操作结果：复数C1除以复数C2，用复数C返回其商。
ModulusComplex(C, &e)初始条件：复数C已存在。
操作结果：求复数C的模，用e返回。
ConjugateComplex(&C, C1)初始条件：复数C1已存在。
数据结构与算法上机作业第三章树一、选择题1、在一棵树中，如果结点A有3个兄弟，B是A的双亲，则B的度为DA. 1B. 2C. 3D. 42、深度为h的完全二叉树至少有D个结点，至多有 B 个结点A. 2hB. 2h-1C. 2h+1D. 2h-12^(h-1) -1 +1=2^(h-1)前（n-1）层满，第h层只有一结点3、具有n个结点的满二叉树有C个叶结点。
A. n/2B. (n-1)/2C. (n+1)/2D. n/2+1因为二叉树中，有这样一个性质，如果其终端结点数（也就是叶子节点）的个数为n1，度为2的结点数为n2，则n1=n2+1;假设叶子节点有x个，则度为2的个数为x-1：所以：2x-1 = n; 所以x = (n+1)/2 (满二叉树)所以叶子节点个数为：(n+1)/2非终端结点为：(n+1)/2-14、一棵具有25个叶结点的完全二叉树最多有B个结点。
A. 48B. 49C. 50D. 515、已知二叉树的先根遍历序列是ABCDEF，中根遍历序列是CBAEDF，则后根遍历序列是A 。
A. CBEFDAB. FEDCBAC. CBEDFAD. 不定6、具有10个叶结点的二叉树中有B个度为2的结点。
A. 8B. 9C. 10D. 117、一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足C 。
A. 所有非叶结点均无左孩子B. 所有非叶结点均无右孩子C. 只有一个叶子结点D. A和B同时成立8、在线索二叉树中，t所指结点没有左子树的充要条件是B。
A. t->left=NULLB. t->ltag=TRUEC. t->ltag=TRUE且t->left=NULLD. 以上都不对9、n个结点的线索二叉树上含有的线索数为C。
A. 2nB. n-1C. n+1D. nn-1表示结点的左右子树，其余n-1指针为空线索取代原来的空链10、二叉树按照某种顺序线索化后，任一结点都有指向其前驱和后继的线索，这种说法B 。
A. 正确B. 错误C. 不确定D. 都有可能11、具有n(n>1)个结点的完全二叉树中，结点i(2i>n)的左孩子结点是D。
A. 2iB. 2i+1C. 2i-1D. 不存在12、具有64个结点的完全二叉树的深度为 C 。
A. 5B. 6C.7D. 813、将一颗有100个结点的完全二叉树从上到下、从左到右一次对结点进行编号，根结点的编号为1，则编号为45的结点的右孩子的编号为C。
A. 46B. 47C. 90D. 912i举个简单的例子就可以看出来，比如7个节点时（也就是三层时），编号为1的左子树编号是2，编号2的左子树是4，编号3的左子树编号为6。
以此就可以看出来。
左结点是2i,右结点才是2i+114、在结点数为n的堆中插入一个结点时，复杂度为C。
A. O(n)B. O(n2)C. O(log2n)D. O(log n2)15、两个二叉树是等价的，则它们满足D。
A. 它们都为空B. 它们的左右子树都具有相同的结构C. 它们对应的结点包含相同的信息D. A、B和C16、包含n个元素的堆的高度为 C 。
（符号「a表示取不小a最小整数）A. nB. 「log2nC. 「log2(n+1)D. n+117、以下说法错误的是B。
A. 存在这样的二叉树，对其采用任何次序的遍历其结点访问序列均相同B. 二叉树是树的特殊情形C. 由树转换成二叉树，其根结点的右子树总是空的D. 在二叉树中只有一棵子树的情形下，也要指出是左子树还是右子树18、设F是一个森林，B是由F变换得到的二叉树。
若F中有n个非终端结点，则B中没有右孩子的结点有C个。
A. n-1B. nC. n+1D. n+219、将一棵树T转换为二叉树B，则T的后根序列是B的B。
A. 先根序列B. 中根序列C. 后根序列D. 层次序列20、将一棵树转换为二叉树后，这颗二叉树的形态是 A 。
A. 唯一的，根结点没有左孩子B. 唯一的，根结点没有右孩子C. 有多种，根结点都没有左孩子D. 有多种，根结点都没有右孩子树转换成二叉树，根节点是没有右孩子的，这由转换规则应该不难理解，且转换规则是唯一的，所以转换成的二叉树是唯一的21、设树T的度为4，其中度为1, 2, 3, 4的结点个数分别为4, 2, 1, 1，则T中的叶结点的个数为 D 。
A. 5B. 6C. 7D. 822、设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1, M2, M3。
与森林F对应的二叉树根结点的右子树上的结点个数为D。
A. M1-1B. M1+M2C. M2D. M2+M323、若以二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是C。
A. 二叉排序树B. 哈夫曼树C. 堆D. 线索二叉树24、用5个权值{3, 2, 4, 5, 1}构造的哈夫曼树的带权路径长度是 B 。
A. 32B. 33C. 34D. 15二、填空题1、一棵二叉树有67个结点，结点的度是0和2。
问这棵二叉树中度为2的结点有33个。
2、含A, B, C三个结点的不同形态的二叉树有5棵。
3、含有4个度为2的结点和5个叶子结点的完全二叉树，有1或0个度为1的结点。
4、具有100个结点的完全二叉树的叶子结点数为50。
5、在用左右链表示的具有n个结点的二叉树中，共有2n 个指针域，其中n-1 个指针域用于指向其左右孩子，剩下的n+1 个指针域是空的。
6、如果一颗完全二叉树的任意一个非终结结点的元素都不小于其左儿子结点和右儿子结点(如果有的话)的元素，则称此完全二叉树为最大堆。
7、堆是一种特殊形式的完全二叉树，对于最大堆而言，其根结点的元素的值应该是所有结点元素中最大的。
8、二叉树的复制是指按照一棵已知的二叉树复制一个副本，使两者等价。
复制二叉树最长用的方法是后根遍历递归算法。
9、在定义堆时，通常采用结构体方式定义相应的二叉树，这样可以很容易实现其相关操作。
10、在构建选择树时，根据孩子结点的获胜者确定他们双亲结点所得到的选择树称为胜者树。
根据孩子结点的失败者确定他们双亲结点所得到的选择树称为败者树。
11、树的表示方法包括数组、邻接表和左右链。
12、表达式(a+b*(c-d))-e/f的波兰式(前缀式)是-+a*b-cd/ef ，逆波兰式(后缀式)是abcd-*+ef/- 。
13、设F是由T1、T2、T3三棵树组成的森林，与F对应的二叉树为B。
已知T1, T2, T3的结点数分别为n1, n2和n3，则二叉树B的左子树中有n1-1个结点，二叉树B 的右子树中有n2+n3个结点。
14、设二叉树的中根序列为ABCDEFG，后根序列为BDCAFGE。
则该二叉树的先根序列为EACBDGF 。
该二叉树对应的森林中包含2棵树。
15、先根次序遍历森林等同于按先根遍历对应的二叉树，后根次序遍历森林等同与按中根遍历对应的二叉树。
16、一棵哈夫曼树有19个结点，则其叶子结点的个数为10。
17、设有数据WG={7, 19, 2, 6, 32, 3, 21, 10}叶节点权重集合，则所构建哈夫曼树的高是5 ，带权路径长度WPL为169 。
18、设有一份电文中共使用6个字符a, b, c, d, e, f，其中出现频率依次为2，3，4，7，8，19，则字符c的哈夫曼编码是001，电文编码的总长度为80 。
20、在有n个结点的哈夫曼树中，叶子结点总数为(n+1)/2，非叶结点的总数为(n-1)/2。
三、试分别画出具有4个结点的二叉树的所有不同形态。
四、已知一棵二叉树的中根序列和后根序列分别是BDCEAHFG和DECBHGFA，请画出此二叉树。
五、已知非空二叉树T，写一个算法，求度为2的结点的个数。
要求：1、定义二叉树的抽象数据类型和型BTREE，并定义基本操作。
2、编写函数count2(BTREE T)，返回度为2的节点的个数。
3、在主函数中，构建一个二叉树，并验证所编写的算法。
六、用递归方法写一个算法，求二叉树的叶子结点数int leafnum(BTREE T)。
要求：1、定义二叉树的抽象数据类型和型BTREE，并定义基本操作。
2、编写函数leafnum(BTREE T)，返回树T的叶子节点的个数。
在主函数中，构建一个二叉树，并验证所编写的算法。
七、画出下图所表示的二叉树的中序线索二叉树和先序线索二叉树。
八、已知二叉树的先根序列是AEFBGCDHIKJ，中根序列是EFAGBCHKIJD，画出此二叉树，并画出后序线索二叉树。
九、在中序线索二叉树中插入一个结点Q作为树中某个结点P的左孩子，试给出相应的算法。
要求：1、定义中序线索二叉树的型THTREE以及基本操作。
2、定义函数void LInsert(THTREE P, THTREE Q); 实现题目要求的操作。
在主函数中，利用操作RInsert和LInsert构造一个线索二叉树，并中序输出二叉树的结点的元素，验证结果。
#include<iostream>#include<iomanip>#include<cmath>#include<cstdlib>#include<string>using namespace std;typedef int elementtype;struct node{//节点的型node* lchild;node* rchild;bool ltag;bool rtag;elementtype element;};typedef node* head;//指向树根roottypedef node* tree;//指向线索树的根节点void makeNull(head& h)//将线索二叉树置空{h->lchild=h;h->ltag=false;h->rchild=h;h->rtag=true;}head pointTotree(head& h,tree& t)//令head指向tree,注意head指向的并不是根节点，tree指向根节点{h->lchild=t;h->rchild=h;h->ltag=true;h->rtag=true;return h;}//中根遍历的下一个节点node* inNext(node* p){node* q=p->rchild;if(p->rtag==true)//如果有右子树，找出右子树的最左节点while(q->ltag==true)q=q->lchild;return q;}//中根遍历的上一个节点node* inPre(node* p){node *q= p->lchild;if(p->ltag==true)//如果P的左子树存在，则其前驱结点为左子树的最右结点while(q->rtag==true)q=q->rchild;return q;//左子树的最右结点}//中序遍历void thInOrder(head h){node* temp;temp=h;do{temp=inNext(temp);if(temp!=h)cout<<temp->element<<" ";}while(temp!=h);}//插入右孩子void rInsert(node* s,node* r){node* w;r->rchild=s->rchild;r->rtag=s->rtag;r->lchild=s;r->ltag=false;//新插入的节点木有左子树，所以lchild指向的是父节点s->rchild=r;s->rtag=true;//原节点的右孩子为新插入的节点if(r->rtag==true){//这里是神马意思呢∑q|?Д?|p，就是如果被插节点s有右子树，//找出被插节点s的的next位置，即右子树中的最左节点，令其lchild指向新添加的节点r//因为插入前该最左节点的lchild指向的是原来节点sw=inNext(r);w->lchild=r;}}//插入左孩子void lInsert(node* s,node* l){node* w;l->lchild=s->lchild;l->ltag=s->ltag;l->rchild=s;l->rtag=false;s->lchild=l;s->ltag=true;if(l->ltag==true){//与插入右孩子方法相似，只需把左右方向对调即可w=inPre(l);w->rchild=l;}}int main(){head h=new node;node* root=new node;node* lc=new node;node* rc=new node;node* c=new node;root->element=1;lc->element=2;rc->element=3;c->element=4;h->rchild=root;h->lchild=h;h->ltag=true;h->rtag=true;root->lchild=h;root->rchild=h;root->ltag=false;root->rtag=false;//构造线索树213lInsert(root,lc);rInsert(root,rc);thInOrder(h);cout<<endl;//root左边插入ClInsert(root,c);thInOrder(h);return 0;}十、假设现在有如下的元素：7、16、49、82、5、31、6、2、44。
