2. 计算机
  3. 阅读以下说明和流程图，从供选择的答案中选出应填入流程图(n)处的字句写在对应栏内。 [说明] 以下是某图像二元树存储与还原算法的主要思想描述。 设一幅2n×2n的二值图像，以：“1”表示黑像素点，以“0”表示白像素点。图像二元树结构表示

阅读以下说明和流程图，从供选择的答案中选出应填入流程图(n)处的字句写在对应栏内。 [说明] 以下是某图像二元树存储与还原算法的主要思想描述。 设一幅2n×2n的二值图像，以：“1”表示黑像素点，以“0”表示白像素点。图像二元树结构表示

admin2009-02-15  55
问题 阅读以下说明和流程图，从供选择的答案中选出应填入流程图(n)处的字句写在对应栏内。
    [说明]
   以下是某图像二元树存储与还原算法的主要思想描述。
   设一幅2n×2n的二值图像，以：“1”表示黑像素点，以“0”表示白像素点。图像二元树结构表示依赖于图像的二元分割，即交替在X轴方向和Y轴方向上分割。先进行水平分割，分成两个2n-1×2n图像子块，然后进行垂直分割，分成4个2n-1×2n-1的正方形块，如此分割，直到子块只含同一像素点为止。如图8-8为一“E”字的二值图像，对其进行二元分割，相应的二元树如图8-9所示。根据图像二元树的0叶结点和1叶结点的数目，删除多者，保留少者。如“E”字图像的二元树0叶结点较多，裁剪后如图8-10所示。
   
裁剪后图像二元树有4类结点，分别用二进制编码如下：
   ◆  左右儿子都有的结点，编码为11；
   ◆  仅有左儿子的结点，编码为10；
   ◆  仅有右儿子的结点，编码为01；
   ◆  叶结点，编码为00。
   存储时，先存储剩余叶结点的类型编码，二进制码00表示0叶结点，11表示1叶结点。再按层次顺序，自左至右存储裁剪后图像二元树各结点的编码。
   图像二元树的存储算法用C语言描述所定义的数据结构及函数如下：
   struct Node{                                /*图像二元树结点*/
   street Node*Left；
   street Node*Righ t；
       char  Pixel；
     }
   struct Node Queue[MaxLen]；              /*队列*/
     InitQueue()                            /*初始化队列Queue的函数；  */
     EmptyQueue  ()                        /*判断队列Queue是否为空的数，若空返回1，否则返回0；  */
     AddQueue(Item)                        /*将Item加到队列Queue的数；  */
     GetQueue()                            /*取队列Queue第一个元素的函数；  */
     PutCode(Code)                         /*写2位二进制码Code到文件的函数*/
   还原算法是存储算法的逆过程，将文件中的二进制码序列转换成图像二元树。还原算法的数据结构与函数与存储算法的相同，还原算法新增了一个函数GetCode  ()。
   GetCode()                               /*从文件中读2位二进制码的函数*/
   [C程序]
   存储算法
   void Backup  (char CutPixel，st ruct Node ImageTree)’/*Cu tP ixel=0表示裁剪0叶结点*/
     {  InitQueue()；
        AddQueue ( ImageTree )  ;
        PutCode  ( 1-CutPixel )  ;
      While ( !EmptyQueue ( )  )
      {  TreeNode= GetQueue ( )  ;
   if  (TreeNode→Left＝＝NULL)
    {  PutCode (0)  ;
    continue:
    }
    Tl= TreeNode→Left;
    Tr= TreeNode→R igh t;
   if ( Tl→Left= = NULL && Tl→Pixel= = CutPixel )
       L=0;
    else
    {
         (1);
       AddQueue  ( Tl )  ;
    }
     if ( Tr→Left= = NULL && Tr→Pixel= = CutPixel )
        R=0;
     else
   {
       (2)  
     AddQueue  (T)  ;
    }
       (3)  
  }
    }
     还原算法
     void Restore  ( struct Node  *TreeRoot )
     {  TreeRoot=  ( strut Node*)malloc  ( sizeof (struct Node)
    InitQueue ( );
    AddQueue  ( TreeRoot )  ;
    CutPixel= 1- GetCode ( )  ;
    while  ( ! EmptyQueue ( )  )
      {  TrecNode= GetQueue ( Queue )  ;
         NodeCode= GetCode ( )  ;
         switch  ( NodeCode )
          {
            case 0:
                          TreeNode→Left = NULL ;
                          TreeNode→Right= NULL
                          TreePixel=(4);
                   break;
            case 1:
                      Tr=  (  structNode*  )malloc   sizeof (  structNode)
                      TreeNode→Righ t= Tr;
                     AddQueue  (Tr)  ;
                      TI=  ( struct Node*  ) malloc    sizeof ( struct Node )
                      Tl→Lefi- NULL;
                      Tl→Right NULL;
                      Tl→Pixel= CutPixel;
                      break;
            case 2:
                    T1=  (  structNode* )malloc    sizeof (struct Node)
                    TreeNode→Lef t= Tl;
                     (5);
                   Tr=  ( structNode* ) malloc  ( sizeof ( street Node )
                   Tr→Left=-NULL ;
                   Tr→Right= NULL ,,
                   Tr→Pixel= CutPixel;
                break;
            case 3:
                    T1= (  struct Node*  ) malloc (  sizeof ( struct Node )
                    TreeNode→Righ t= Tl;
                    AddQueue  ( T1 )  ;
                    Tr=  (  struct Node*  )malloc  (sizeof ( struct Node
                    TreeNode→Righ t=Tr;
                    AddQueue (Tr)  ;
                    break;
                }
            }
   }
选项
答案(1)L=1 (2) R=1 (3) PutCode(L*2+R) (4) 1-CutPixel (5)AddQueue(T1)
解析 本题涉及了某图像二元树存储与还原算法。考生需要用一定时间去分析算法的思想。算法中主要应用了二元树存储结构。(1)根据算法思想，二元树左边没有节点[if (T1→Left==NULL&&T1→Pixel== CutPixel)]，判断为假，那么(1)处应为L=1。同理可判断(2)处应为R=1。(3)根据算法设计思想，“if (TreeNode→Leff==NULL)”判断为假时，应该写二进制码L*2+R到文件。故答案为PutCode(L*2+R)。 (4)还原算法，当获取的存储码NodeCode=GetCode()为0时，根据存储算法只有L=0，R=0时GetCbde()才为0，再根据存储算法中的“PutCode(1-CutPixel)”，可知TreePixel=1-CutPixel。(5)NodeCode==2的情况时，对于存储算法，应该是L=1，R=0，这样L*2+R=2才成立。那么(5)处应该为AddQueue(T1)。
转载请注明原文地址:https://kaotiyun.com/show/UMDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

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