Use C++ ,language if necessary.
SHORT ANSWER SECTION - Provide in depth answers in your own words.
1. Compare and Contrast Dynamic vs Static memory and where in RAM memory each type of structure is placed. Describe Virtual Memory.
2. Compare and contract Linked List data structure to Array data structure.
3. (a) Briefly describe Abstract Data Types (ADT) or Abstract Data structures in general.
3. (b) Describe the purpose of implementing a Queue, Stack, or Hashmap on an Array or Linked List. Describe why one would implement a Queue, Stack, or Hashmap.
4. Why is look-up faster for a Binary Tree then Linked List?
5. Why is it difficult to perform a binary search on a linked list?
6. Describe the process of analyzing the Big O Notation for a Stack or Queue.
7. Memory Allocation Analysis: Describe your process for calculating memory required for the following examples. Give an estimate in MB/GB of the amount of memory required.
(a) Array of Doubles that contains 100,000 elements.
(b) Linked List of chars contains 1,000,000 nodes.
Big O SECTION List appropriate Worst Case Big O Notation under the different algorithms or data structure operations. Choose from right column and place under left column. Right column can be used more than once or not all.
|
A. Empty() check method on Stack of 1000 elements with array as underlying data structure
|
O(1)
|
|
B. Traversing a Linked List from the Last Node to the Head Node
|
O(n)
|
|
C. Look Up of Node in a 100,000 element Binary Search Tree
|
O(n^2)
|
|
D. Traversing every node in Queue with array as underlying data structure
|
O(log n)
|
|
E. Accessing key in 1,000,000 element Hash Map
|
O(n log n)
|