1. A binary tree has ten nodes. The inorder and preorder traversals of the binary tree are shown as follows.
 Inorder: FKCGJBDEAI
 Preorder: GFCKDJBIEA
Draw the tree.

VI. Writing 20% Around the world, schools are currently adopting Content and Language Integrated Learning (CLIL) or English as a Medium of Instruction (EMI) to convey academic content in English. Please compare the two approaches (10%) and do you agree or disagree with the implementation of either approach in secondary education in Taiwan in order to develop our country into a bilingual nation (10%)? Give reasons for your answer and include any relevant examples from your own knowledge or experience. Write an essay of at least 300 words.

1. Test-making (1): Please rewrite the following passage into a cloze test of about 150 words with five questions for graders, and provide the answer to the questions.       Scientists from universities in the US and UK, who jointly analyzed data collated on a range of species, say they are "astounded" by the figure. They point out that it is about 50% higher than previous estimates. The wildlife trade - in the likes of horns, ivory and exotic pets - is the number one cause of animal extinction, tied only with land development. "The sheer diversity of species being traded is astounding - the risk that will grow is very worrying," said Prof David Edwards of the University of Sheffield, a co-researcher on the study.      The study, published in Science, identified hotspots for traded birds, mammals, amphibians and reptiles in regions within the Andes mountain range and Amazon rainforest, sub-Saharan Africa, South East Asia and Australia. The research also identified another 3,000 or so species that look set to be traded in the future, based on their similarities with animals currently bought and sold - for example if they have bright plumage or exotic horns. "If one species is traded, the chances are its evolutionary cousins are also traded," said Dr. Brett Scheffers of the University of Florida. "Once we discovered that pattern, we could develop a new model that would predict which species are likely to be traded in the future, even if they are not traded now." The scientists stress the need for proactive rather than reactive strategies, including a "watch list" of susceptible species, better detection of illegal imports, fighting corruption and engaging local people in conservation. Prof Edwards said: "Withouturgent focus on how to stem both the supply and demand for wild-caught species, there is a real danger that we will lose many traded species."      Individuals can help by not taking any illegal animal products offered to them abroad, he said, and bychecking any exotic pets they buy have not been captured illegally from the wild.

2. Test-making (2): Please write three reading comprehension questions based on the reading passage below for graders and the answers provided.       The rich, multi-ethnic and multi-dimensional culture of Nepal is based on centuries-old traditions and social customs. Its diversities range of mountain communities and social strata are expressed in music, dance, folklore,language, and religion.       Nepal has two main religions, Hinduism and Buddhism, although many Nepalese practice a uniquecombination of both mixed with a degree of animism. The traditions of both go back over two millennia to the birth of the Buddha in Lumbini and the ancient Hindu rituals still strong today. Also treasured is the tradition of excellence in arts and crafts.       Visitors will need to observe native customs when visiting temples, such as respectful, conservative dress,removing shoes before entry and asking permission to enter a Hindu temple. Nepalis are friendly, although displays of affection in public are not appreciated. Superstitions rule and it brings bad luck to praise a baby’s appearance or walk on spilled rice. Red chilies hang everywhere, driving away evil spirits and bus drivers always say a prayer before departing.       The family is very important in Nepalese life, and is traditionally close-knit and loyal. Women are generally subservient to men and although highly honored as mothers, they have less access to education and political power. In rural areas, women work longer and harder than men, as they are expected to combine their household and child-raising chores with farming and taking care of the livestock.       An artistic and intellectual revival took place in the 1950s, sparking a flowering of literature and art focused on national pride and religious values. Nowadays, the traditional culture of Nepal is fostered in radio programs featuring folk music and, in rural areas, devotional music and songs, a strong part of village life.

IV. Essay Question  With the implementation of the new 108 curriculum, what kind of role do you think the teachers should take on? (250 – 300 words)

a. Determine the entropy of the data set. (4 points)

b. Determine the average entropy of the resulting subsets obtained by splitting on attribute A. (4 points)

c. How much information gain is obtained if attribute A is selected for the root node of the decision tree? (2 points) Note: Please use the values: log23 = 1.6 and log25 = 2.3. Hint: Entropy = is distribution for event i

3. To transmit text across a network, an English character is usually encoded in 8 bits in which bits 0~6 are the ASCII code and bit 7 is used for parity checking. Suppose a string of 5 characters, infni, is to be transmitted and odd-parity checking is adopted. Let the ASCII code of i be 1101001, the ASCII code of n be 1101110, and the ASCII code of f be 1100110. What is the sequence of 40 bits encoded for the 5-character string? Please show the sequence in hexadecimal (base 16) form.

4. Suppose we have an array A containing 9 integers: 240, 119, 682, 341, 225, 556, 122, 661, 245, i.e. A = [240, 119, 682, 341, 225, 556, 122, 661, 245] with the first index being 0. Please convert the array A into a maxheap and show the content of A after conversion. Note that the conversion should be done in-place.

（一）丟擲第一次後雙方身上可能各有幾枚代幣？【4 分；未寫出推論過程者不予計分】