单项选择(1996年中国科学技术大学)

如果只考虑有序树的情形,那么具有7个结点的不同形态的树共有【】

A、132

B、154

C、429

D、127

答案解析

A

【解析】

具有n个结点 的不同形态的树的数目tn和具有n-1个结点互不相似的二叉树的数目相同。

具有n个结点互不相似的二叉树的数目为1/n+1Cn 2n

讨论

树是结点的集合,它的根结点数目是【 】

某二又树的先序遍历序列为 ABCDFGE,中序遍历序列为 BAFDGCE。以下关于该二又树的叙述中,正确的是【 】。

对于一般的树结构,可以采用孩子-兄弟表示法,即每个结点设置两个指针域,一个指针(左指针)指示当前结点的第一个孩子结点,另一个指针(右指针)指示当前结点的下一个兄弟结点。某树的孩子-兄弟表示如下图所示。以下关于结点 D 与 E 的关系的叙述中,正确的是【 】。

对下图所示的二叉树进行中序遍历(左子树、根结点、右子树)的结果是【 】。

已知一棵度为m的树中有N1个度为1的结点,N2个度为2的结点,...,Nm个度为m的结点。试问该树中有多少个叶子结点?

对于正整数n ,输出其和等于n且满足以下限制条件的所有正整数的和式,组成和式的数字自左至右构成一个非递增的序列。如 n = 4 ,程序输出为:4 = 44 = 3 + 14 = 2 + 24 = 2 + 1 + 1 4 = 1 + 1 + 1 + 1test 是实现该功能的 C 程序段,请将未完成的部分补足,使之完整。test 函数为一递归函数,参数 n 为被分解和式的数, k 为当前的分解深度。算法思想是对 n 的所有合理的和式分解,将分解出的数(称为和数)存于二数组 a[]中。当其中一个分解己不再需要进一步进行时,即找到一个解,将存于 a[] 中的一个完整和式的和数输出。当还需要进一部分解时,以要进一部分解的数及分解深度为参数,递归调用 test 函数。#define MAXN 100 int a[MAXN]; test(int n,int k){     int i,j;     for (j=__________;j>=1;j--){         a[k]=j;          if (__________){             printf ( "%d = %d" , a[0],a[l]);             for (i = 2 ; i < = k ; i + + )                 printf ( " + % d " , a[i]);             printf ( "  n " );         }else test(__________,k + l );     } }

栈的输入序列为1,2,3,...,n,输出序列为a1,a2,a3,...,an,若ai=n(1≤i≤n),则有 ak>ak+1>an。

若需在O(log2n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是【 】。

在一个有n个顶点的无向网中,有O(n1.5*log2n)条边,则应该选用【 】算法来求这个网的最小生成树,从而使计算时间较少。

在叶子数目和权值相同的所有二叉树中,最优二叉树一定是完全二叉树,该说法【 】。

有n个数顺序(依次)进栈,则出栈顺序有Cn种。Cn=×

啥夫曼树是带权路径长度最短的树,路径上权值较大的结点离根较近。

什么是啥夫曼(Huffman)树?

线索二叉树是一种【 】结构。

二叉树在线索化后,仍不能有效求解的问题是【 】。

二叉树中,具有两个子女的结点的中序后继结点最多只能有一个子女。

阅读以下说明和C函数,填补代码中的空缺(1)~(6)。二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数 GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组 counter[], counter[i]存放第i层上的结点数,并按照层次顺序来遍历二又树中的结点,在此过程中可获得每个结点的层次值,最后从counter[]中取出最大的元素就是树的宽度。按照层次顺序遍历二叉树的实现方法是借助一个队列,按访问结点的先后顺序来记录结点,离根结点越近的结点越先进入队列,具体处理过程为:先令根结点及其层次号(为1)进入初始为空的队列,然后在队列非空的情况下,取出队头所指示的结点及其层次号,然后将该结点的左子树根结点及层次号入队列(若左子树存在),其次将该结点的右子树根结点及层次号入队列(若右子树存在),然后再取队头,重复该过程直至完成遍历。设二叉树采用二叉链表存储,结点类型定义如下:typedef struct BTNode{ TElemType data; struct BTNode *left, *right;}BTNode, *BiTree;队列元素的类型定义如下:typedef struct{ BTNode *ptr; int LevelNumber;}QElemType;Get Width()函数中用到的函数原型如下所述,队列的类型名为 QUEUE:InitQueue(QUEUE *Q):初始化一个空队列,成功时返回值为1,否则返回值0isEmpty(QUEUE Q):判断队列是否为空,是空则为1,否则为0EnQueue( QUEUE*Q, QElemType a):将元素a加入队列,成功返回值为1,否则返回值0DeQueue(QUEUE *Q, QElemType *):删除队头元素,并通过参数带回其值,成功则返回值1,否则返回值0GetHeight (BiTree root):返回值为二叉树的高度(即层次数,空二叉树的高度为0)int Getwidth(BiTree root){ QUEUE Q; QElemType a, b; int width,height= GetHeight(root); int i, *counter =(int *)calloc(height+1, sizeof (int)); if(__(1)__) return -1;/*申请空间失败*/ if(! root) return 0;/*空树的宽度为0*/ if(__(2)__) return -1;/*初始化队列失败时返回*/ a.ptr= root; a.LevelNumber=1; if(! EnQueue(&Q,a)) return -1;/*元素入队列操作失败时返回*/ while (! isEmpty(Q)){ if(__(3)__)return -1;/*出队列操作失败时返回*/ counter[b. LevelNumber]++;/*对层号为b. LevelNumber的结点计数*/ if(b.ptr->left){/*若左子树存在,则左子树根结点及其层次号入队*/ a.ptr= b.ptr->left; a.LevelNumber=__(4)__; if(!EnQueue(&Q,a)) return -1; } if(b.ptr-> right){/*若右子树存在,则右子树根结点及其层次号入队*/ a.ptr= b.ptr->right; a. LevelNumber=__(5)__; if(! EnQueue(&Q,a)) return -1; } } width= counter[1]; for(i=1; i< height +1; 1++)/*求 counter[]中的最大值*/ if(__(6)__)width= counter [i]; free(counter); return width;}

与算术表达式3-(2+7)/4对应的二又树为【 】。

对二叉树中的结点如下编号:树根结点编号为1,根的左孩子结点编号为2、右孩子结点编号为3,以此类推,对于编号为i的结点,其左孩子编号为2i、右孩子编号为2i+1。例如,下图所示二又树中有6个结点,结点a、b、c、d、e、f的编号分别为1、2、3、5、7、11。那么,当结点数为n(n>0)的【 】时,其最后一个结点编号为2n-1。

某二叉树的先序遍历(根、左、右)序列为 EFHIGJK、中序遍历(左、根、右)序列为HFIEJKG,则该二叉树根结点的左孩子结点和右孩子结点分别是【 】