Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
Stefan exam
| Question | Answer |
|---|---|
| Preorder = | Node ---> Left --->Right |
| Inorder = | Left ---> Node ---> RIght |
| Postorder = | Left --->RIght ---> Node |
| Stacks follow - | LIFO |
| Queues follow - | FIFO |
| A complete (perfect) binary tree with D internal nodes has exactly _________ leaves. | D + 1 |
| The time complexity to turn an array of size B into a max-heap using the bottom up method is Θ(______) - | Θ(__B___) filtering nodes downward. Because the vast majority of nodes are near the bottom and only move down a short distance, the total work scales perfectly linearly: |
| The space complexity to remove 1 item in a FIFO queue of size T implemented using linked lists is Θ(_____) | Θ(__1___) |
| The time complexity of one push() operation in a stack of size X implemented using an array is Θ(_____) | Θ(__1___) |
| is Heapsort adapative? Stable? | NO. NO. |
| The time complexity to insert k new items in a heap of size N is Θ(_________). Assume k < N/5. | Θ(__klgN___) Each insertion takes \(\log N\) time, and you repeat it a tiny, independent number of times. |
| Give the height of a balanced binary search tree with W nodes. If possible give Θ(____), if not give O(____). | |
| A Full tree ( strict binary tree) has how many children? | 0 or 2. NEVER 1 |
| An incomplete / general tree has how many children? | 0 - 2. its random |
| An incomplete / general tree with D internal nodes has exactly _________ leaves. | D / 2 leaves |
| The time complexity to turn an array of size B into a max-heap using the Top down method is Θ(______) - | Θ(_BlgB__) |
| The time complexity to insert k new items in a heap of size N is Θ(_________). Assume k = N | Θ(__N___) \(\Theta(N)\) If you are adding a massive amount of items at once, it is much faster to dump them all into the array and run the Bottom-Up |
| Give the height of a Full Binary Tree with W nodes in the worst case | Θ(W) |
| Give the minimum possible height of any binary tree with W nodes | Θ(lgW) |
| Give the height of an incomplete / arbitrary / general binary tree with W nodes | Θ(W) |
| Parent formula for binary heap = | index / 2 |
| Left Child formula for binary heap = | index * 2 |
| Right child formula for binary heap = | index * 2 + 1 |
| Removing in max heap = | removing max value |
| Removing in min heap = | removing min value |
Created by:
Alynna