《数据结构与算法设计》树-*题-精选文档

发布于:2021-06-18 19:07:58

树的练*题 1. 具有n个顶点的二叉树,共有多少边? n-1 2、若一个具有N个顶点,K条边的无向图是一个森林 (N>K),那么该森林有多少棵树? N-K 3、已知一棵度为m的树中有N1个度为1的节点,N2个 度为2的节点,…, Nm个度为m的节点。问该树有 多少叶子节点? N0 = N2+ 2N3+ ……+ (m-1)Nm+1 4、层数为k的二叉树中,最大和最小节点数各为多少 ? 2k-1, k 5、有n个节点的二叉树中,有m个叶子节点,问非叶 子节点中度为2和度为1的节点各有多少? n2 = m-1; n1=n-2m +1 1 B C B 2 1. 假定一棵树的广义表示为(A(B(C,D(E,F,G), H(I,J))),则树中所含的结点数为 (10)个,树的 深度为( 4)个,树的度为 (3 )。 2、在哈夫曼编码中,若编码长度只允许小于等于4, 则除了已对两个字符编码为0和10外,还可以最多对 4 ( ) 个字符编码. 3、一颗二叉树的前序遍历序列为aebdc,后序遍历序 列为bcdea,根节点的孩子节点 A.只有e B. e和b A C. e和c D. 不确定 3 ? 试问利用树的先根次序遍历结果和 后根次序遍历结果能否唯一确定一 棵树? 1、树的先根次序遍历的结果与其对应二叉树的前序遍 历结果相同 2、树的后根次序遍历结果与其对应二叉树的中序遍历 结果相同; 3、对于二叉树而言,先序遍历和中序遍历可以确定一 个二叉树, 因此,树的先根次序遍历结果和后根次序遍历结果能 唯一确定一棵树 4 ? 用二叉链表作为二叉树的存储表示,统计二叉树中 叶结点的个数,请完成下列递归程序 。 typedef struct BiTNode { // 结点结构 TElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree; int leaf (BiTNode * ptr ) { if ( ptr == NULL ) return 0; else if ( ptr->lChild == NULL && ptr->rChild == NULL ) return 1; else return leaf ( ptr->lChild )+ leaf ( ptr->rChild ) ; } 5 ? 二叉树的双序遍历(Double-order traversal)是指:对 于二叉树的每一个结点来说,先访问这个结点,再 按双序遍历它的左子树,然后再一次访问这个结点, 接下来按双序遍历它的右子树。试写出执行这种双 序遍历的算法。 void Double_order ( BiTNode *current ) { if ( current != NULL ) { printf(“%f,”, current->data); Double_order ( current->rChild ) ; printf(“%f,”, current->data); Double_order ( current->rChild ); } } 6 ? 已知一棵具有n个结点的完全二叉树被顺序存储于一 维数组的A[1]~A[n]元素中,试找出编号为i的结点 的双亲和所有孩子。假设每一个元素用一个整数表 示。完成下列程序 7 void Request(int A[], int n, int i) { //从数组A中打印出编号为i的结点的双亲和孩子 i>n if( ) exit(1); printf(current element:%f”, A[i]); int j=i/2; //下标为j的结点是下标为i结点的双亲 j>0 if( ) printf(“parent:%f”,A[j]); else prinf(“No parent!); if( 2*i<n ){ printf(left child:%f”,A[2*i]); printf(right child:%f“,A[2*i+1]; } 2*i==n ){ else if( printf(left child:%f,A[2*i]); printf(no right child!; } else printf(no children!“); } 8 ? 已知二叉树 – 先序序列为:ABCDEF – 中序序列为:CBAEDF ? 请画出该二叉树。 A B C E D F 9 A D 10 ? 已知二叉树 – 中序序列为:ABCEFGHD – 后序序列为:ABFHGEDC ? 请画出该二叉树。 – 中序:LDR A – 后序:LRD A B C E F G H D A B F H G E D C C B E D G F H 11 ? 将下列森林转化为二叉树,然后对森林进行先序和 后序遍历 1 2 3 4 5 6 7 8 9 10 12 13 11 14 15 12 ? 将下列树进行中序线索化 A B C G E D F C G B E A D F 中序:CBAGEDF 13 ? 试分别找出满足以下条件的所有二叉树 – 二叉树的前序序列与中序序列相同 – 二叉树的中序序列与后序序列相同 – 二叉树的前序序列与后序序列相同 ? 如果一棵Huffman树有n0个叶子节点,那么该树有 多少节点? ? 已知如下序列:8、5、3、2、7、23、9、11、2、35, 请构造一棵Huffman树。 2n0-1 14 ? 请指出下列函数的功能 //先序遍历方式,递归 void swap(BiTNode *b){ BiTNode *t; if(b== NULL) return; t = b->lchild; b->lchild = b->rchild; b->rchild =t; swap(b->lchild ); swap(b->rchild

相关推荐

最新更新

猜你喜欢