刑事警察人員 97 年計算機數學考古題

假設input alphabet 是包含0 與1 的所有可能字串的集合，請用regular expression 表 示下列集合： 所有由0 與1 構成的字串且0 出現的次數正好為兩次。（5 分） 所有由0 與1 構成的字串且0 出現的次數必須為奇數次。（5 分）

運用邏輯推論法則中的矛盾證法，證明下列推論，並說明每一步驟理由。（10 分）           s q r p r q p      V s V

假設Sn 是所有n 位的二元序列中沒有出現010 的個數。列出Sn 的遞迴關係及初始 條件。（15 分）

在某間電腦公司的上班員工中，有80%為男性及20%為女性。已知在男性員工中會 寫Java 程式者是女生會寫Java 程式者的x 倍。若從公司內所有會寫Java 程式的員 工中隨機抽取一位，該名程式設計人員為男性的機率為50%。另女性會寫Java 程式 者在女生中所佔比例是20%。試求男生中會寫Java 程式者在男生中所佔的比例是多 少？（15 分）

付15 元投擲一個公平的骰子一次，如果出現點數為x，則可以獲得x2 元。試求獲利 的平均數與變異數。（10 分）

下列遞迴關係是Quicksort 的平均計算時間： 1 1 T( ) T( 1) T( ) 1 n p n p n p n n               其中n 代表輸入值的個數。假設當n≦2 時T(n)=1，請證明T(n)=O(n log n)。 （15 分）

某一電腦零售商根據過去銷售的情形分析得知，桌上型電腦佔了20%，筆記型電腦 佔了45%，小螢幕電腦佔了35%。廠商為了存貨管理問題，想了解各型電腦現今銷 售情形是否仍維持不變？分析最近200 筆銷售紀錄發現：桌上型電腦賣了48 台， 筆記型電腦賣了76 台及小螢幕電腦賣了76 台。請在5%的「顯著水準」下，檢定 現今銷售情形是否仍維持不變。（10 分） 附註：χ2 5%,1=3.841，χ2 5%,2=5.991，χ2 5%,3=7.815，χ2 5%,4=9.488

某電腦公司徵聘工程師，依應徵者報名先後順序從1 到N 編號，但N 是多少並未 對外公布。主考官隨機抽樣7 位應徵者，其編號為：50, 42, 64, 24, 12, 34, 76。試依 下列方法估算N 值： 樣本平均數。（5 分） 中位數。（5 分） 全距。（5 分）