Shiang 發問時間: 社會與文化語言 · 1 0 年前

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

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.

29. Compare the difference between Single Linked Lists and Doubly Linked Lists, and state the advantages and disadvantages respectively.

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.

1 個解答

評分
  • Ted
    Lv 4
    1 0 年前
    最佳解答

    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.

    Single linked list每個節點只有一個指標欄指向下個節點

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

    Doubly linked list每個節點則有兩個指標欄指向下個和前一個節點

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

    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

    參考資料: 大腦 & 資料結構 & 演算法 & 資料庫
    • 登入以對解答發表意見
還有問題?馬上發問,尋求解答。