2. 计算机
  3. 阅读以下说明和C函数，填补代码中的空缺(1)～(6)，将解答填入答题纸的对应栏内。 【说明】 二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组counter[]，cou

阅读以下说明和C函数，填补代码中的空缺(1)～(6)，将解答填入答题纸的对应栏内。 【说明】 二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组counter[]，cou

admin2016-05-11  59
问题 阅读以下说明和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 LevelNumbe r；
    )QElemType；
    GetWidth()函数中用到的函数原型如下所述，队列的类型名为QUEUE：

【C函数】
    int GetWidth(BiTree  root)
    {
    QUEUE  Q；
QElemType a，b；
    int width，height=GetHeight(root)；
    int i，*counter=(int*)calloc(height+l，sizeof(int)};
    if(  (1)  )    return一1；    ／*申请空间失败*／
    if(!root)    return 0；    ／*空树的宽度为0*／
    if(  (2)  )    return一1；    ／*初始化队列失败时返回*／
    a．ptr=root；    a．LeveiNumber=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；
    }
    i f(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；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．LevelNumber+1 或等价表示 (5)b．LevelNumber+1 或等价表示 (6)counter[i]＞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://www.kaotiyun.com/show/t9jZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

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