考試

104年中鋼 資訊工程 - 考試

Hamiltion avatarHamiltion · 2019-03-26

Table of Contents

104年 中鋼 資訊工程考題，複選題之中，

( ABCDE ) 36.若給予三個節點 A, B, C，哪些是正確的?
(A) 可構成30顆不同的binarytree
(B) 可構成 12 顆不同的 ordered tree
(C) 可構成 9 顆不同的 unordered tree(又稱為 oriented tree)
(D) 可構成 3 顆不同的 free tree(即 connected acyclic graph)
(E) 若三個節點的前序追蹤、中序追蹤或後序追蹤為:ABC，可構成 5 顆不同的
binary tree

請問選項A到D要怎麼解？是否有高手可以提點，
我只知道選項E的公式，謝謝。

--
考試

All Comments

Carol avatarCarol2019-03-27
https://imgur.com/a/ISreRxt
Bethany avatarBethany2019-04-01
有錯還請指正~
Edwina avatarEdwina2019-04-05
上面網址內共有1文字說明+3張圖A,B,D的圖示哦~
Donna avatarDonna2019-04-09
突然發現如果答案D也正確的話，定義我要再查一下QQ
Zanna avatarZanna2019-04-11
https://goo.gl/PnXXmN
Steve avatarSteve2019-04-16
上面網頁內有詳解，與解答都一樣了~
Faithe avatarFaithe2019-04-19
先不填ABC值，用三空值節點先建樹結構，而二元樹子節
點有分左右，一般樹沒分。所以三層結構下，二元樹有
先走左(右)再走右(左) 當四種，而一般樹只有每層各一
節點 這一種。
Candice avatarCandice2019-04-22
而兩層結構就都是一種，樹根帶兩子節點。畫完結構再
來分別填ABC進去，二元樹共五種結構，每種各3!填法。
Steve avatarSteve2019-04-27
一般樹結構共兩種，且可分有序樹跟無序樹，差別是同
父節點的兄弟節點間有次序差別。三層結構的下因為每節
點頂多一子節點，所以無序有序都一樣，3!=6種填法。
而兩層節構下，樹根有兩子節點，有序無序就有差，有
序有3!種填法。無序只有誰當樹根的差別，3種。所以綜
合，有序樹有3!+3!棵，無序樹3!+3棵。
Sandy avatarSandy2019-04-28
free tree就當連通非循環圖，沒有誰當樹根的概念，三
頂點用兩個邊變連通非循環，兩點degree是1，一點degre
e是2，就看degree是2的頂點要擺誰，3種放法。
Isabella avatarIsabella2019-05-02
謝謝兩位高手解惑