DATA STRUCTURES FINAL RUTGERS
EXAM QUESTIONS AND ANSWERS
Suppose that you have an unsorted array A of size n and a sorted array B of size m.
Note that n is much larger than m. Answer the questions below.
What is the fastest algorithm to find the common values in these two arrays? - Correct
Answers -for each value in A do a binary search on B
What is the running time (big O notation) to insert a new node in the front of a
Circular Linked List - Correct Answers -O(1)
To insert at the front requires creating a new node and updating the last pointer
to the new front. No list traversal is needed
Suppose that x is a Node in a CLL. What does the following code fragment do?
Node t = new Node();
t.item = "Apples";
t.next = x.next;
x.next = t; - Correct Answers -Inserts node t immediately after node x.
Assume n items will be inserted into a data structure:
• n is much greater than 0.
• The n items can be store into a computer's memory.
• The only operation that occurs in the data structure is insertion
which is the fastest data structure to store these n items? - Correct Answers -Array,
unsorted array or linked list
What is the running time (big O) for rehashing given the input size n? Give the
reasoning. - Correct Answers -O(n).
Each of the n keys will need to be remapped to the new table
What is the worst case running time (big O notation) to insert a new node in a
sorted Doubly Linked List? - Correct Answers -O(n)
Item to be inserted is greater than all other items in the list. Need to traverse the
entire list to insert item.
Insert a new node to the beginning of the list. best and worst - Correct Answers -O(1)
EXAM QUESTIONS AND ANSWERS
Suppose that you have an unsorted array A of size n and a sorted array B of size m.
Note that n is much larger than m. Answer the questions below.
What is the fastest algorithm to find the common values in these two arrays? - Correct
Answers -for each value in A do a binary search on B
What is the running time (big O notation) to insert a new node in the front of a
Circular Linked List - Correct Answers -O(1)
To insert at the front requires creating a new node and updating the last pointer
to the new front. No list traversal is needed
Suppose that x is a Node in a CLL. What does the following code fragment do?
Node t = new Node();
t.item = "Apples";
t.next = x.next;
x.next = t; - Correct Answers -Inserts node t immediately after node x.
Assume n items will be inserted into a data structure:
• n is much greater than 0.
• The n items can be store into a computer's memory.
• The only operation that occurs in the data structure is insertion
which is the fastest data structure to store these n items? - Correct Answers -Array,
unsorted array or linked list
What is the running time (big O) for rehashing given the input size n? Give the
reasoning. - Correct Answers -O(n).
Each of the n keys will need to be remapped to the new table
What is the worst case running time (big O notation) to insert a new node in a
sorted Doubly Linked List? - Correct Answers -O(n)
Item to be inserted is greater than all other items in the list. Need to traverse the
entire list to insert item.
Insert a new node to the beginning of the list. best and worst - Correct Answers -O(1)
