数据结构与算法-等级考试试题(二级考试 2005年4月二叉树)

填空题（2005年4月二级考试）

某二叉树中度为2的结点有18个，则该二叉树中有__________个叶子结点。

答案解析

19

【解析】

二叉树具有如下性质：在任意一棵二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。

根据题意，度为2的结点为18个，那么，叶子结点就应当是19个。

讨论

数据结构与算法

有n个数顺序（依次）进栈，则出栈顺序有Cn种。Cn=×

设栈的输入序列是（1，2，3，4），则【】不可能是其出栈序列。

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

设栈的输入序列为1,2,3,...,n，输出序列为a1,a2,a3,...,an，若存在1≤k≤n使得 ak=n，则当k≤i≤n时，ai 为【】

没有提供指针类型的语言，无法构造链式结构，该说法【】

如果入栈序列为ABCD，不可能出现的出栈序列是【】

算术表达式(a+b)*(c-d/e)的后缀表达式为【】

假设有两个按元素值递增有序排列的线性表A和B，均以带头结点的单链表作为存储结构，编写算法将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（A表和B表）的结点空间存放表C。

试写出在双向链表da中的插入操作算法，算法中插入位置的获取可直接引入getnodep(da,i)，其中参数da为双向链表，i是要插入的数据，要求算法中含有双向链表da的结点结构描述。

已知结点指针p、q分别表示双向链表中任意两个相邻结点（即p->rlink=q且q->llink=p），请写出删除q所指结点的程序段。

二叉树

一棵二叉树按中序遍历时各结点被访问的次序和这棵二叉树按后序遍历时各结点被访问的次序能否唯一确定这棵二叉树的结构？为什么？若已知一棵二叉树按先序遍历时各结点被访问的次序和这棵二叉树按后序遍历时各结点被访问的次序，能否唯一确定这棵二叉树的结构？为什么？

如果一棵huffman树T有n0个叶子结点，那么，树T有多少个结点？要求给出求解过程。

对于二叉树T 的两个结点 n1 和 n2 ，我们应该选择树 T 结点的前序、中序和后序中哪两个序列来判断结点 n1 必定是结点 n2的祖先，并给出判断的方法。不需证明判断方法的正确性。

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

求具有最小带权路径长度的二叉树的算法称为__________算法。对于给出的一组权W={10，12，16，21，30}，通过该算法示出的二叉树的带权路径长度为__________。

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

阅读以下说明和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;}

最优二叉树(或哈夫曼树)是指权值为w1，w2，…，wn的n个叶结点的二叉树中带权路径长度最小的二叉树。【】是哈夫曼树(叶结点中的数字为其权值)。

与算术表达式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。

树和二叉树

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

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

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

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

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

在有 6 个字符组成的字符集 S 中，各个字符出现的频次分别为 3、4、5、6、8、10，为 S 构造的哈夫曼树的加权平均长度为【】

已知一棵二叉树的树形如图，若其后序遍历为 f、d、b、e、c、a，则其先序列为【】

由二叉树的前序和后序遍历序列【】唯一地确定这棵二叉树。

具有7个结点的互不相识的二叉树共有__________棵。

证明，由一棵二叉树的前序序列和中序序列可唯一地确定这棵二叉树。设一棵二叉树的前序序列为ABDGECFH，中序序列为DGBEAFHC，试画出该二叉树。