2. 从业资格
  3. 阅读以下说明和C函数，填补代码中的空缺（1）～（6），将解答填入答题纸的对应栏内

阅读以下说明和C函数，填补代码中的空缺（1）～（6），将解答填入答题纸的对应栏内

题库2022-08-02  46
问题 阅读以下说明和C函数，填补代码中的空缺（1）～（6），将解答填入答题纸的对应栏内。【说明】    二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组counter[]，counter存放第i层上的结点数，并按照层次顺序来遍历二叉树中的结点，在此过程中可获得每个结点的层次值，最后从counter[]中取出最大的元素就是树的宽度。    按照层次顺序遍历二叉树的实现方法是借助一个队列，按访问结点的先后顺序来记录结点，离根结点越近的结点越先进入队列，具体处理过程为：先令根结点及其层次号（为1）进入初始为空的队列，然后在队列非空的情况下，取出队头所指示的结点及其层次号，然后将该结点的左予树根结点及层次号入队列（若左子树存在），其次将该结点的右子树根结点及层次号入队列（若右子树存在），然后再取队头，重复该过程直至完成遍历。    设二叉树采用二叉链表存储，结点类型定义如下：    typedef struct BTNode {            TElemType data;            struct BTNode *left, *right;    } BTNode, *BiTree;   队列元素的类型定义如下：    typedef struct {            BTNode *ptr;            int LevelNumber;    } QElemType;   GetWidth()函数中用到的函数原型如下所述，队列的类型名为QUEUE：【C函数】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.LeveINumber=  （5） ;                if  ( !EnQueue (&Q,  a))  return -1;            }        }    width=counter [1] ;    for (i=1;  i＜ height  +1;  i++)    /* 求counter[]中的最大值 */            if  ( （6） ) width=counter;       free(counter);    return width;}
选项
答案
解析 （1）!counter  或0==counter  或NULL==counter  或等价表示
（2）!InitQueue(&Q)  或0==InitQueue(&Q)   或等价表示
（3）!DeQueue(&Q,&b) 或0==DeQueue(＆Q,&b)  或等价表示
（4）b.LeveINumber+1    或等价表示
（5）b.LeveINumber+1    或等价表示
（6）counter>width   或等价表示


本题考查数据结构实现和C语言基本应用。
    考生需要认真阅读题目中的说明，以确定代码部分的处理逻辑，从而完成代码。
    根据注释，空（1）处应填入“!counter”或其等价形式。
    由于初始化队列的函数原型为“InitQueue(QUEUE *Q)”且返回值为0表示操作失败，因此调用该函数时实参应取地址，即空（2）处应填入“!InitQueue(&Q)”或其等价形式。
    空（3）处需进行出队列操作，同时通过参数得到队头元素，根据说明，该空应填入“!DeQueue(&Q,&b)”或其等价形式。
    出队操作后，得到的队头元素用b表示，根据队列元素的类型定义，其对应结点在二叉树中的层次号表示为b.LevelNumber，显然，其孩子结点的层次号应加1，因此空（4）和（5）处应填入“b.LevelNumber+1”。
    从代码中可知变量width的作用是表示最大的层次编号，并通过顺序地扫描数组counter中的每一个元素来确定width的值，显然，空（6）处应填入“counter>width”或其等价形式。
转载请注明原文地址:https://tihaiku.com/congyezige/2427261.html
本试题收录于： 初级程序员题库软件水平考试初中高级分类

初级程序员

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)