# 急!!!幾題研究所計概問題-請求計概高解答

23. Discuss the differences between transaction databases and data warehouse databases.

24. List and discuss the four transaction properties.

What is a transaction log, and what is its function?

28. What is a complete binary tree? Considering a complete binary tree with n levels, please compute the number of tree nodes.

30. Show that the following statements are correct.

(1) The maximum number of nodes on level i of a binary tree is 2i-1, i≧1.

(2) The maximum number of nodes in a binary tree of depth k is 2k-1, k≧1.

31. Use pseudo-codes to write out the inorder, preorder and postorder for Binary Tree, respectively.

32. It is assumed that we have the following key values in sequence: 30, 22, 18, 31, 25, 5, 10. Write out the max heap after each value is inserted into the heap.

33. Show that the number of edges in an n vertex complete graph is n (n-1) /2.

34. It is assumed that there are 5 vertices in a complete graph. Please show all of its spanning trees.

35. Please show that Kruskal’s algorithm generates a minimum cost spanning tree.

Rating
• Ted
Lv 4

23.

Transaction DataBase主要供連線使用者查詢資料用

Warehouse DataBase則是儲存資料，供Data mining等技術找出資料隱藏的關連性，以作為決策輔助

24. (1)

交易會將一組的資料從一個狀態改到另外一個狀態。要一個交易正確，必須要符合下列的特性 ACID (Atomicity，Consistency，Isolation，Durability)

Atomicity:要求包含在一個交易中所有的改變要不是全部完成，就是全部回復到交易前的狀態，好像沒發生過。

Consistency:要求系統的一致性，對於儲存的資料，運作的資料的定義是一致的。

Isolation:要求同時進行的多個交易彼此互不相干擾，同時使用到的資源也能由系統保證是循序(serial)地存取。

Durability:要求完成交易的資料要能在任何情況下都保存下來，不管是否系統當機或有其他的意外狀況發生。

(2)

transaction log紀錄所有DB上的操作以及登入登出，當DB出錯時或是要追查哪些人做過哪些操作時可使用

28. (1)

完整二元樹就是依照節點(node)的索引(index)依序填入鍵(key)值的二分支(2-way)樹

(2)

若節點數為X

|_ log(2為底)X _|(取下界)+1=n

所以 2^(n-1)<=x<=2^n-1

29.

優點:較節省空間 缺點:只能單向操作

優點:能雙向操作，效率較佳 缺點：較佔空間

30. (1) (題目打錯，應該是2^(i-1))

level1最多只有1=2^(1-1)個node，即根

level2最多有2=2^(2-1)個nodes

level3最多有4=2^(3-1)個nodes

leveli最多有2^(i-1)個noeds

(2) (題目打錯，應該是2^k-1)

此題為第28題第二小題的答案，

若節點數為X

|_ log(2為底)X _|+1=k

2^(k-1)<=x<=2^k-1

2^k-1是最大値

31.

preorder:

procedure PREORDER(T)

//T is a binary tree where each node has three fields LCHILD, DATA, RCHILD

if T≠0 then

[print(DATA(T))

call PREORDER(LCHILD(T))

call PREORDER(RCHILD(T))

]

end PREORDER

inorder:

procedure INORDER(T)

//T is a binary tree where each node has three fields LCHILD, DATA, RCHILD

if T≠0 then

[call INORDER(LCHILD(T))

print(DATA(T))

call INORDER(RCHILD(T))

]

end INORDER

postorder:

procedure POSTORDER(T)

//T is a binary tree where each node has three fields LCHILD, DATA, RCHILD

if T≠0 then

[call POSTORDER(LCHILD(T))

call POSTORDER(RCHILD(T))

print(DATA(T))

]

end POSTORDER

32.

-----31

----/---\

30------18

/---\ ----/-- \

25-22-5---10

33.

n個節點，每個節點有其他n-1個節點可連線，所有節點連完後，所有的邊(edge)

會重複連兩次，所以共有n(n-1)/2個邊

34.

這個實在太多了~~妳自己畫~~只要能連接所有的點~~沒有多餘的邊就是了

35.

MST-KRUSKAL(G,w)

A←NULL

for each vertex v屬於V[G]

do MAKE-SET(v)

sort the edges of E into nondecreasing order by weight w

for each edge(u,v)屬於E，taken in nondecreasing order by weight

do if FIND-SET(u)≠FIND-SET(v)

then A←A∪{(u,v)}

UNION(u,v)

return A

Source(s): 大腦 & 資料結構 & 演算法 & 資料庫