計概16-03堆積－公職試題

【選擇題】

【D】01.下圖為何種資料結構？

          10

        /      \

      36       27

     /  \      /  \

   70   52  52   81

  /  \

72   98 (A)完滿二元樹(Full Binary Tree) (B)AVL樹(AVL Tree) (C)紅黑樹(Red-Black Tree) (D)最小堆積(MinHeap)。[109身心四等]

最小堆積：完全二元樹所有父節點的值恆小於等於子節點的值。

 

【B】02.用堆積排序法(Heap Sort)排序時，要先用BuildMaxHeap()將資料所存放的矩陣調整成Max Heap，再進行排序。現有矩陣：30 41 59 26 53 58 98，經BuildMaxHeap()後，得到結果為何(以矩陣儲存資料的方式排列)？ (A)59 53 58 26 41 30 98 (B)98 53 59 26 41 58 30 (C)58 53 30 26 41 59 98 (D)53 41 30 26 58 59 98。[111身心五等]

30    /      \   41      59  /   \    /   \ 26  53  58  98

59    /      \   41      30  /   \    /   \ 26  53  58  98

59    /      \   53      98  /   \    /   \ 26  41  58  30

98    /      \   53      59  /   \    /   \ 26  41  58  30

BuildMaxHeap()結果：98 53 59 26 41 58 30

 

【C】03.堆積(Heap)經常使用陣列來儲存。將70插入下圖所示陣列代表的最大堆積後，70所在位置的索引值為何？ (A)11 (B)5 (C)2 (D)1。[112地方四等電子]

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
	88	60	27	43	38	25	4	35	6	7

 

【A】04.下列關於堆積(Heap)的敘述何者錯誤？ (A)堆積必須是一個完美二元樹(perfect or full binary tree) (B)在最大堆積(max heap)中，每一個節點的值都不小於兒子們的值 (C)堆積是一個可利用陣列來實作的樹狀資料結構 (D)堆積可用於排序，利用堆積完成排序的演算法稱作堆積排序(heap sort)。[112國安五等]

堆積只需要是一個二元樹(binary tree)，其中每個節點都有一個值，且每個父節點的值都大於或等於其子節點的值。