聽說今天的期中上機題連結慘掉了 所以把檔案放上來XD 課程名稱︰資料結構與演算法 課程性質︰資工系大一必修 課程教師︰張智星 開課學院：電機資訊學院 開課系所︰資工系 考試日期（年月日）︰2016/04/24 考試時限（分鐘）：筆試80min/上機80min 以下只有上機考部分，沒有範例測試檔，考試時間80min，必須使用git上傳並加tag 試題 : Be you start, you should be aware of the following requirements: Check out Github submission guidelines. Your program should take the input from the standard input and send the output to the standard output. Problem 1:(30%) Output all possible outcomes after using a stack: Problem definition: Print all possible outputs after passing distinct numbers 1, 2, 3, ..., n theough a stack and deleting in all possible ways. Specs: You can assume n is less than or equal to 12. Input format: The first line is an integer indicating the number n. Output format: Each line is a possible output list after using the stack. Hints: Consider the first number being popped out at position 1, 2, ..., and n, respectively. It is easier to use recursive implementation. Problem 2:(30%) Traverse a binary tree Problem definition: Print a binary tree's preorder, inorder, and postorder traversals. Specs: The input tree is represented as a vector, just like the way described in the textbook. The number of tree nodes is less than 100. Input format: The first line is a list of integers indicating the vector representation of the binary tree. Each used node is indicated by a positive integer. Each unused node is indicated by -1. (So the first number is always -1.) Output format: Line 1 is preorder traversal. Line 2 is inorder traversal. Line 3 is postorder traversal. Hint: It is easier to use recursive implementation. Problem 3:(40%) Restore a full binary tree from preorder and postorder Problem definition: Each node in a full binary tree has 0 or two children. It is easy to prove that we can uniquely determine a full binary tree from its preorder and postorder traversals. Write a program to output a full binary tree from its preorder and postorder traversals. Specs: The number of tree nodes is less than 20. You are not allowed to used linked lists/structures for the tree. Instead, you should use vector representation for the tree, as described in our slides/textbook. You are welcome to use available code over the internet, such as this one. http://goo.gl/J0VtHO However, since you are not allowed to use linked lists/structures for this problem, it would be easier to write your own program. Input format: Line 1 is the preorder traversal of the full binary tree Line 2 is the postorder traversal of the full binary tree Each node has a key of positive integer. Output format: Vector representation of the full binary tree, with -1 indicating unused positions. (So the first number is always -1.) Hint: It is easier to use recursive implementation. (Total Score = 100) --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.172 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1461498043.A.EAC.html

※ 發信站: 批踢踢實業坊(ptt.cc) ※ 轉錄者: jason1218 (140.112.16.172), 04/24/2016 19:42:16 ※ 編輯: jason1218 (140.112.16.172), 04/24/2016 19:43:13