申論 1某系統A 使用雜湊表（hash table）儲存不同的正整數鍵值，亦即不允許重複鍵值，雜湊表有11 個儲存格，索引從0 開始，雜湊函數（hash function）為hA( k)k mod11，其用平方探查法（quadraticprobing）處理碰撞（collision）問題，探查序列為hA( k)(hA( k)i2)mod11(i0,1,2,...)，刪除資料時，i被刪除資料的位置標記為特殊符號DELETED。請回答下列問題：㈠給定一個空的雜湊表，依序插入下列鍵值22、1、13、24、35、46、7、18，請畫出所有鍵值插入完成後的雜湊表狀態，並列出插入鍵值46 時的完整探查過程。（10 分）㈡承上題，依序刪除鍵值24、13，畫出刪除後的雜湊表狀態。並說明為什麼刪除鍵值時需用DELETED 標記，而不能將該鍵值所在的儲存格恢復成「從未存放過鍵值」的空狀態。（5 分）㈢承上題，執行插入鍵值12，請列出插入時的探查過程、操作停止的理由，並寫出12 最後插入那一個儲存格。插入時，DELETED 標記視為可放入新鍵值的儲存格。請注意鍵值不能重覆。（5 分）㈣相較於系統A，考慮另一個採用平方探查法之系統，系統B 的表格大小為8，索引亦從0 開始，雜湊函數hB( k )及探查序列hB( k )分別定義為ihB( k)k mod8、hB( k)(hB( k)i2i2)mod8 (i0,1,2,...)。在非均i勻雜湊（non-uniform hashing）的情況下，也就是許多鍵值可能被分配到相同或少數幾個初始雜湊位置時，那一個系統的雜湊表儲存格利用率可能較高？並說明理由。（5 分）