课程名称︰资料结构与算法
课程性质︰资工系大一必修
课程教师︰张智星
开课学院：电机资讯学院
开课系所︰资工系
考试日期（年月日）︰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)