[試題] 104下 張智星 資料結構與演算法 期中考
課程名稱︰資料結構與演算法
課程性質︰資工系大一必修
課程教師︰張智星
開課學院：電機資訊學院
開課系所︰資工系
考試日期（年月日）︰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://www.ptt.cc/bbs/NTU-Exam/M.1461498043.A.EAC.html
※ jason1218:轉錄至看板 b04902xxx 04/24 19:42
推
04/24 20:18, , 1F
04/24 20:18, 1F
推
05/02 18:23, , 2F
05/02 18:23, 2F
推
04/18 16:45, , 3F
04/18 16:45, 3F