软题库 移动APP 扫码下载APP 随时随地移动学习 培训课程
当前位置:信管网 >> 在线考试中心 >> 信息系统项目管理师题库 >> 试题查看
试卷名称 2014年下半年程序员考试下午真题试题(案例分析)
考试中心《2014年下半年程序员考试下午真题试题(案例分析)》在线考试
试卷年份2014年下半年
试题题型【分析简答题】
试题内容

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

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[i];
   
    free(counter);
    return width;
}


相关试题

推荐文章
合作网站内容