计130121第四次作业

数据结构与算法

上机作业

第四次作业

一、选择题

1、具有n(n>1)个结点的完全二叉树中，结点i(2i>n)的左孩子结点是 D 。

A. 2i

B. 2i+1

C. 2i-1

D. 不存在

2、将一颗有100个结点的完全二叉树从上到下、从左到右一次对结点进行编号，根结点的编号为1，则编号为45的结点的右孩子的编号为 D 。

A. 46 A. O(n)

B. 47

C. 90

D. 91 D. O(logn2)

3、在结点数为n的堆中插入一个结点时，复杂度为 C 。

B. O(n2)

C. O(log2n)

4、两个二叉树是等价的，则它们满足 D 。

A. 它们都为空

B. 它们的左右子树都具有相同的结构

D. A、B和C

D. n+1

C. 它们对应的结点包含相同的信息 A. n

B. 「log2n

5、包含n个元素的堆的高度为 C 。（符号「a表示取不小a最小整数）

C. 「log2(n+1)

6、以下说法错误的是 B 。

A. 存在这样的二叉树，对其采用任何次序的遍历其结点访问序列均相同 B. 二叉树是树的特殊情形

C. 由树转换成二叉树，其根结点的右子树总是空的

D. 在二叉树中只有一棵子树的情形下，也要指出是左子树还是右子树

7、设F是一个森林，B是由F变换得到的二叉树。若F中有n个非终端结点，则B中没有右孩子的结点有 C 个。

A. n-1 A. 先根序列

B. n

C. n+1

D. n+2 C. 后根序列

D. 层次序列

8、将一棵树T转换为二叉树B，则T的后根序列是B的 B 。

B. 中根序列

9、设树T的度为4，其中度为1, 2, 3, 4的结点个数分别为4, 2, 1, 1，则T中的叶结点的个数为 D 。

A. 5

B. 6

C. 7

D. 8

10、设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1, M2, M3。与森林F对应的二叉树根结点的右子树上的结点个数为 D 。

A. M1-1

B. M1+M2

C. M2

D. M2+M3

11、若以二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是 C 。

二、填空题

1、如果一颗完全二叉树的任意一个非终结结点的元素都 不小于 其左儿子结点和右儿

A. 二叉排序树 B. 哈夫曼树 A. 32

B. 33

C. 34

C. 堆

D. 15

D. 线索二叉树

12、用5个权值{3, 2, 4, 5, 1}构造的哈夫曼树的带权路径长度是 B 。

子结点(如果有的话)的元素，则称此完全二叉树为最大堆。

2、堆是一种特殊形式的 完全 二叉树，对于最大堆而言，其根结点的元素的值应该是所有结点元素中 最大 的。

3、二叉树的复制是指按照一棵已知的二叉树复制一个副本，使两者 等价 。复制二叉树最长用的方法是 后根遍历递归算法 。

4、在定义堆时，通常采用 结构体 方式定义相应的二叉树，这样可以很容易实现其相关操作。

5、在构建选择树时，根据孩子结点的获胜者确定他们双亲结点所得到的选择树称为 胜者树 。根据孩子结点的失败者确定他们双亲结点所得到的选择树称为 败者树 。 6、树的表示方法包括 数组 、 邻接表 和 左右链 。

7、表达式(a+b*(c-d))-e/f的波兰式(前缀式)是 -+a*b-cd/ef ，逆波兰式(后缀式)是 abcd-*+ef/- 。

8、设F是由T1、T2、T3三棵树组成的森林，与F对应的二叉树为B。已知T1, T2, T3的结点数分别为n1, n2和n3，则二叉树B的左子树中有 n1-1 个结点，二叉树B的右子树中有 n2+n3 个结点。

9、设二叉树的中根序列为ABCDEFG，后根序列为BDCAFGE。则该二叉树的先根序列为 EACBDGF 。该二叉树对应的森林中包含 2 棵树。

10、先根次序遍历森林等同于按 先根 遍历对应的二叉树，后根次序遍历森林等同与按 中根 遍历对应的二叉树。

11、一棵哈夫曼树有19个结点，则其叶子结点的个数为 10 。

12、设有数据WG={7, 19, 2, 6, 32, 3, 21, 10}叶节点权重集合，则所构建哈夫曼树的高是 5 ，带权路径长度WPL为 169 。

13、设有一份电文中共使用6个字符a, b, c, d, e, f，其中出现频率依次为2，3，4，7，8，14，则字符c的哈夫曼编码是 001 ，电文编码的总长度为 80 。

15、在有n个结点的哈夫曼树中，叶子结点总数为 (n+1)/2 ，非叶结点的总数为 (n-1)/2 。

三、假设现在有如下的元素：7、16、49、82、5、31、6、2、44。画出将每一个元素插入堆中以后的最大堆。 要求：

利用基本操作Insert的基本原理，先用第一个元素7构成一个二叉树，然后将第二个元素16插入该二叉树中，再将第三个元素49插入堆中，……，直到最后一个元素插入为止。上述过程要求画图完成。

四、编写一个函数，在最大堆中查找任意元素，并分析其时间复杂度。 要求：

1、 定义最大堆的型HEAP及其基本操作。

2、 定义函数int Find(HEAP H, Elementtype e)，查找e是否为堆的元素，如果是，返回

该元素在堆中的位置，如果不是，返回0。（提示：利用最大堆的元素特点进行查找，可降低复杂度）

在主函数中首先构建一个二叉树，然后验证所构造的函数。 typedefstryct{ int key; datathpe data; }elementtype; Typedefstruct{

Elementtype elements[Maxsize]; int n; }HEAP;

Void MaxHeap(HEAP heap)//创建一个空堆 { heap.n=0;}

Bool HeapEmpty(HEAP heap)//判断堆是否为空 {

If(!(heap.n))return true; Else return false; }

Bool HeapFull(HEAP heap)//判断堆是否为满 {if(heap.n==Maxsize-1) return true; Else return false; }

Void Insert(HEAP&heap,elementtype element)//在堆heap中插入元素为element的结点 { Int I;

If(!HeapFull(heap)){ I=heap.n+1;

While((i!=1)&&(element.data>heap.elements[i/2].data)) {heap.elements[i]=heap.elements[i/2]; i/=2; } Heap.n++;

Heap.elements[i]=element; } }

Elementtype DeleteMax(HEAP&heap)//删除堆中最大元素 {int paraent=1,child=2; Elementtype element,tmp;

If(!HeapEmpty(heap)){ Element=heap.elements[1]; Tmp=heap.elements[heap.n-]; While(child<=heap.n) {

If((child=heap.elements[child].data)break; Heap.elements[paraent]=heap.elements[child]; Paraent=child; Child*=2;}

Heap.elements[paraent]=tmp; Return element;} }

Int Find(HEAP,datatype x) {int m=1;

While((m=x) m++; else return 0; else m++;} if(m<=H.n)return m; else return 0; } Int main(){ HEAP H;

Elementtype element; Int data[]={1,3,5,7,9,11,13}; H.n=0;

For(int i=0;i<7;i++) {element.key=i+1; Element.data=data[i]; Insert(H,element);

}for(int i;i<=H.n;i++)cout<

For(int i=1;i<=H.n;i++)cout<

Cout<,endl;

Cout<<”查找的元素：”; Int x; Cin>>x;

Cout<

五、给定叶子结点的权值集合{15, 3,14, 2, 6, 9, 16, 17}，构造相应的哈夫曼树，并计算其带权路径长度。

82 2 W=(2+3)*5+6*4+(9+14+15)*3+(16+17)*2=229 六、已知n=9和一组等价关系：

1≡5、6≡8、7≡2、9≡8、3≡7、4≡2、9≡3

试应用抽象数据类型MFSET设计一个算法，按输入的等价关系进行等价分类。

1{1}{2}{3}{4}{5}{6}{7}{8}{9} 21=5；{1,5}{2}{3}{4}{6}{7}{8}{9} 36=8；{1,5}{2}{3}{4}{6,8}{7}{9} 47=2；{1,5}{2,7}{3}{4}{6,8}{9} 59=8；{1,5}{2,7}{3}{4}{6,8,9} 63=7；{1,5}{2,3,7}{4}{6,8,9} 74=2；{1,5}{2,3,4,7}{6,8,9} 89=3；{1,5}{2,3,4,6,7,8,9}

七、画出下图所示的森林经转换后所对应的二叉树，并指出在二叉树中某结点为叶子结点

3 5 5 11 9 14 15 2029 16 17 49 33 时，所对应的森林中结点应满足的条件。

出森林F。

提示：先画出森林F所对应的二叉树B，然后再将B转换为森林。 C

九、画出表达式(A+B*C/D)*E+F*G所对应的树结构，并写出该表达式的波兰表示式和逆波兰表示式。 + + E F G 波兰表达式 ： +*+A*B/CDE*FG 逆波兰表达式 ：ABCD/*+E*FG*+ A * * * E F J B D G I K L A H I 八、已知森林F的先根序列为：ABCDEFGHIJKL，后根序列为：CBEFDGAJIKLH，试画

D H E C G J B F A B

C / D 1、 十、

2、 实现将一个四则混合运算转换成二叉树的函数：BTREE convert(char *express)，其

中参数express为四则混合运算表达式，返回值为生成的树。

3、 实现计算四则混合运算的值的函数：double computer(BTREE bt)，其中，参数bt为

四则运算所对应的树，返回值为计算结果。提示：先求树的的波兰表达式，然后利用栈结构计算表达式的值。

在主函数中进行测试，求2+3*（5+8）/4-5的值。 要求：

1、上述作业要求在单独完成；

2、完成后，于规定期限内提交到ftp服务器的相应目录中中，注意，在提交时将所编写的程序统一拷贝到一个Word文件中，文件名格式为“学号+姓名”。

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