97年 - 97 專技高考_資訊技師：離散數學與應用統計#37544

科目：技師◆離散數學與應用統計 | 年份：97年 | 選擇題數：0 | 申論題數：6

試卷資訊

所屬科目：技師◆離散數學與應用統計

選擇題 (0)

申論題 (6)

一、令 x₁, x₂,..., x_n為一整數數列。證明：對任一整數 k, 1 ≤ k ≤ n，存在兩個整數，i 和 j， i ≤ j，使得 k 可以整除 x_i＋x_i+1＋…＋x_j。（20 分）

二、樹（tree）是一個沒有迴圈（cycle）的連通圖（connected graph）。證明：在任一個點（vertex）數大於 1 的樹中，至少有兩點其度數（degree）等於 1。（20 分）

【已刪除】三、令 G＝（V, E）為一個無向圖（undirected graph）。ω ：E → Z 為權重（weight）函數，以下是計算最小權重擴張樹（minimum spanning tree）T 的演算法。（20 分）

在演算法中，E_T 表示 T 的邊（edge）。此演算法先令 E_T = 0，然後從最小權重的邊開始，一一設法加入 E_T 中，條件是不能產生迴圈（cycle）。因此這個演算法必須測試 T 加上 e_i，T＋e_i，會不會有迴圈，設計一個資料結構，使這個演算法可以在 O(m log n) 計算步驟內完成計算的工作，得到正確的答案。

⑴一婦人連生 5 個男孩，現又懷孕，這一胎仍為男孩的機率為何？

⑵一家庭有 6 個小孩，已看到 5 個男孩，沒看到的那一位仍為男孩的機率為何？

五、設 p 為學生曾經考試作弊的機率，為使學生更誠實的回答問題，教授設計兩個問題： ⑴（較敏感問題）你是否考試作弊過？⑵（較不敏感問題）你是否在六月出生？被測的學生可以自行擲一銅板，若出現正面（H）則回答⑴題，若出現反面（T）則回答⑵題，令 q 表示學生回答“是”的機率，假設學生誠實的依照這個方法回答問題，估計學生曾經考試作弊的機率 p。（20 分）