课程名称︰ 资料结构与程式设计 课程性质︰ 选修 课程教师︰ 郑振牟 开课学院： 电机资讯学院 开课系所︰ 电机工程学系 考试日期（年月日）︰ 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