計算機概論、大意(資訊科學概論,電腦常識,電子計算機概論)題庫下載題庫

Huffman編碼是用貪心演算法來實現的

實現huffman最好的資料結構時優先順序佇列（可以通過最小堆來實現）。整個演算法的時間複雜度可以達到nlg(n)，這裡為了簡單，沒有實現最小堆，而使用的是stl中的set，通過實現正確的比較函式物件，每次可以取得優先順序（字元出現頻度最低）最大的值。但是這裡的時間複雜度卻提高了，因為操作set的選擇時，時間複雜度時lgn,但是隨著選擇的，選擇“未被訪問的最高優先順序的兩個元素（flag=0）”的探測次數也為增大，平均探測次數是n/2，因此最後實現huffman的時間複雜度將是n^2lg(n)。當然也可以通過記錄每次選擇元素時其在set中的位置（偏移量），下次選擇時直接通過這個偏移量找到合適位置，探測的時間複雜度將會是1，最後實現huffman的時間複雜度也可以達到nlog(n)。

貪心演算法是一種求解問題的方法，通常適用於需要在眾多可能的解決方案中尋找最佳解決方案的問題。貪心演算法的基本思想是，在每一個階段選擇當前看起來最好的選擇，而不考慮後續步驟的影響。儘管貪心演算法不能保證一定能找到問題的最佳解，但在某些情況下，貪心演算法可以得到很好的解決方案。

選項 (A) 和 (B) 為正確敘述。Prim 和 Kruskal 演算法都是用來尋找最小生成樹的貪心演算法，它們通過在每一個階段選擇當前看起來最好的邊來構建最小生成樹。

霍夫曼碼是一種讓不同的字符對應到不同的編碼的方式，通常用於數據壓縮。Huffman 演算法是一種貪心演算法，它通過將出現頻率較高的字符編碼為較短的二進制位，從而實現數據壓縮。因此，選項 (C) 為錯誤敘述。