[試題] 97上 鄭振牟 資料結構與程式設計 期末考

[llewxam (鋼琴中的大賦格)]

課程名稱︰      資料結構與程式設計
課程性質︰      選修
課程教師︰      鄭振牟
開課學院：      電機資訊學院
開課系所︰      電機工程學系
考試日期（年月日）︰    2009/01/14
考試時限（分鐘）：      100
是否需發放獎勵金：      是，謝謝
（如未明確表示，則不予發放）

試題 :


1. Show how to use stacks to convert the following infix expression to its

   prefix form: "!(A&&!((B<C)||(C>D))||(C<E)," assuming the standard C/C++

   operator precedence.


2. Write an algorithm to construct a binary tree given by its postorder and

   inorder traversal sequences. Is the tree uniquely determined by these two

   sequences? Prove or disprove by giving a counter example.


3. Given the list of numbers {12, 2, 16, 30, 8, 28, 4, 10, 20, 6, 18},

   construct an indexed binary search tree, explicitly labeling the lestSize

   and rank of each node as defined in class. Show how to delete the sixth

   smallest element from the constructed indexed binary search tree.


4. A source node of a directed graph is a node that does not have any incoming

   edges, whereas a sink node is a node that does not have any outgoing edges.

   Using Dijkstra's algorithm, compute the shortest paths from the source node

   of the graph given by its weighted adjacency matrix. What is the shortest

   path from that source to the sink node? Show the process of Dijstra by

   recording the d and p arrays as done in class.



                        [0 6 5 5 0 0 0]
                        [0 0 0 0 1 0 0]
                        [0 2 0 0 1 0 0]
                        [0 0 2 0 0 1 0]
                        [0 0 0 0 0 0 3]
                        [0 0 0 0 0 0 3]
                        [0 0 0 0 0 0 0]



5. Sort the list of numbers {12, 2, 16, 30, 8, 28, 4, 10, 20, 6, 18} in place

   using the Quick Sort algorithm by showing the process.


6. Prove that the binomial tree B_k has 2^k nodes, k >= 0.


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.243.6
→ ketsu1109   :已收入精華區