課程名稱︰資料結構與演算法
課程性質︰資工系大一必修
課程教師︰張智星
開課學院：電機資訊學院
開課系所︰資工系
考試日期（年月日）︰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)