申論題 - 阿摩線上測驗

申論題資訊

試卷：112年 - 112 普通考試_統計、資訊處理：資料處理概要#115737
科目：資料處理
年份：112年
排序：0

題組內容

二、有一筆資料為12，10，7，23，13，6，15，17，46，3。

申論題內容

(一)請依序建置最小堆積（Min heap）樹（由上而下Top Down建置）。（10分）

詳解 (共 2 筆)

詳解提供者：默默

#include <stdio.h>
int arr[100] = {12, 10, 7, 23, 13, 6, 15, 17, 46, 3};
void kk(int a[], int size) {
// 完整的冒泡排序, 由小到大排序。
for (int j = 0; j < size - 1; j++) {
for (int i = 0; i < size - 1 - j; i++) {
if (a[i + 1] < a[i]) {
int temp = a[i + 1];
a[i + 1] = a[i];
a[i] = temp;
}
}
}
// 印出前10個元素
for (int i = 0; i < size; i++) {
printf("\n%d\n", a[i]);
}
}
int main() {

// 呼叫 kk 函數來排序並印出前10個元素
kk(arr, 10);
return 0;}

#include <stdio.h>

int arr[100] = {12, 10, 7, 23, 13, 6, 15, 17, 46, 3};
void kk(int a[], int size) {
// 完整的冒泡排序, 由小到大排序。
for (int j = 0; j < size - 1; j++) {
for (int i = 0; i < size - 1 - j; i++) {
if (a[i + 1] < a[i]) {
int temp = a[i+1];
a[i+1] = a[i];
a[i] = temp;
}
}
}
// 印出前10個元素
for (int i = 0; i < 10; i++) {
printf("\n%d\n", a[i]);
}
}
int main() {

// 呼叫 kk 函數來排序並印出前10個元素
kk(arr, 10);
return 0;
}

tree: 3 ->root node

6 7

10 12 13 15

17 23 46

詳解提供者：hchungw

要依序建置一個最小堆積（Min Heap）樹（Top Down建置），我們可以按照以下步驟操作，逐一將元素插入到堆積中，並確保每次插入後，堆的性質（父節點的值小於其子節點的值）得以維持。這個過程又被稱作上浮（percolate up）。

給定的數據序列為：12, 10, 7, 23, 13, 6, 15, 17, 46, 3。

下面展示了按照資料序列逐一插入過程中，最小堆積樹的變化：

插入12：
12
12
插入10：
10
,
12
10,12
插入7：
7
,
12
,
10
7,12,10
插入23：
7
,
12
,
10
,
23
7,12,10,23
插入13：
7
,
12
,
10
,
23
,
13
7,12,10,23,13
插入6：
6
,
12
,
7
,
23
,
13
,
10
6,12,7,23,13,10
插入15：
6
,
12
,
7
,
23
,
13
,
10
,
15
6,12,7,23,13,10,15
插入17：
6
,
12
,
7
,
17
,
13
,
10
,
15
,
23
6,12,7,17,13,10,15,23
插入46：
6
,
12
,
7
,
17
,
13
,
10
,
15
,
23
,
46
6,12,7,17,13,10,15,23,46
插入3：
3
,
12
,
6
,
17
,
13
,
10
,
15
,
23
,
46
,
7
3,12,6,17,13,10,15,23,46,7
每一步插入操作之後，都確保了堆的性質，即每個節點都小於其子節點。最終的結果是形成了一個最小堆積樹。

這個堆可以視為一個完全二叉樹，其存儲結構通常是一個陣列，根據上述過程，最終形成的最小堆積樹的陣列表示如下：
3
,
12
,
6
,
17
,
13
,
10
,
15
,
23
,
46
,
7
3,12,6,17,13,10,15,23,46,7

這表示根節點是最小的元素，每個父節點的值都小於或等於其子節點的值，滿足最小堆的性質。