听说今天的期中上机题连结惨掉了 所以把档案放上来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/cn.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