[理工] 97成資管資結

[cksh8008 (ck)]

成98-101資結解答(其中一年份)換97年

覺得應該徵不到了

一起對答案，和討論哪邊有錯吧

http://tinyurl.com/bdadwln

1.
(a)3
(b)3
(c)4
(d)2

解釋就不寫了

2.

*畫-的部分表示為紅節點

(a)              (b)          (C)

   A              A           無法
  / \            / \
 B   C          B   C         因此樹高為5，而B點的高為2，
     -          -   -         因紅點不可連續，假設高為5那一路徑為紅黑紅黑配置
    / \          \   \        黑點會有 5/2 = 2個黑點
   D   E          D   E       而B點最多為 2/2 = 1個黑點
        \             /       紅黑樹定義 每條路徑黑點數需相同
         F           F        =>所以無法建立出
         -           -

3.不太懂，盡力寫看看，搞不好全錯

(a)

B只用來裝部分node => size為O(n)

(b)

O(n^2)

因為是用adjacent matrix來儲存 => O(n)

(c)

不能改善，因為還不能確定i點前已經確認過了

這樣會造成有些點沒有判斷到


4.

typedef struct *node
{
   int data;
   int X;
   int Y;
   struct node*L;
   struct node*R;
}node no[n*n/2];

int putdata(int a[][],X,Y)
{
   int count=0;
   for(i=0;i<X;i++)
   {
     for(j=0;j<Y;j++)
     {
        if(j==Y)//如果放到最下面時，無node可linked
        {
           no[count++]->data = a[j][i];//就放值就好
        }
        else
        {
           no[count]->data = a[j][i];
           no[count]->X=j;
           no[count]->Y=i;
           no[count]->L=no[j+1];
           no[count]->R=no[i+1];
           count++;
        }
     }
     Y--;
   }
   no[0]->X=X;
   no[0]->Y=Y;
}

5.

將BT node加一變數
int count=1;//沒read過就為1

void inorder(node*r)
{
   while(r!=NULL&&count&&r->count==1)//找不為NULL的node和沒read過的node
   {
      r->count=0;//read過變為0
      inorder(r->left);
      printf("%d",r->data);
      inorder(r->right);
   }
}

6.7.8

懶得寫


一起對答吧，來信討論也可以

剩幾天了，都加油吧

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 175.181.145.70