1. Which of the following descriptions are TRUE about Linked List? why? (A) The

Question

1. Which of the following descriptions are TRUE about Linked List? why?

(A) The Big-O complexity to insert a node into a singly linked list is always O(1). (B) The Big-O complexity to delete a node from a doubly linked list is always O(1). (C) If there are both head and tail pointers in doubly linked list, then the insertion and deletion operation is always O(1) at the beginning and end of the list. (D) If a stack is implemented using a singly linked list, then it is more efficient to use the head pointer as the top of the stack. (E) If a queue is implemented using a singly linked list (with tail pointer), then it is more efficient to use the tail pointer as the front of the queue and the head pointer as the rear of the queue than vice versa. (F) Given only a pointer pointing to one of the nodes to be deleted, it is more efficient to delete that node in a doubly linked list than in a singly linked list. (G) Merging two sorted linked lists, each with N nodes, is O( N ).

2. Problem #5: Which of the following are TRUE about Binary Search Trees (BST) with no special attention paid to balancing, and Balanced BSTs? and why?

(A) Search operations are always O(log N ) in Binary Search Tree. (B) The search operation in Binary Search Tree is O(log N ) in the worst case. (C) The insertion operation in Binary Search Tree is O( log N ) in the worst case. (D) The output from in-order traversal on Binary Search Tree is always sorted. (E) After inserting N keys and deleting a random number of P keys ( P < N) in a Binary Search Tree, the resulting Binary Search Tree is always perfectly balanced. (F) Balanced Search Trees never ensure that all insertion, deletion, and search operations are O( log N ).

3.  Given the following insert() operations into an empty Binary Search Tree with no attention paid to balancing. Insert(2), Insert(0), Insert(1), Insert(3), Insert(5), Insert(7), Insert(9). Which of the following are true? and why?

(A) The numbers that the pre-order traversal visited are in this order: 2 0 1 3 5 7 9 (B) The numbers that the in-order traversal visited are in this order: 0 1 2 3 5 7 9 (C) The numbers that the post-order traversal visited are in this order: 1 0 9 5 7 3 2 (D) After Delete(5), the numbers that the post-order traversal visited are in this order: 1 0 9 7 3 2. (E) After Delete(5), the numbers that the level-order traversal visited are in this order: 2 0 3 1 7 9

4.  Which of the following sorting algorithms is the fastest when applying it to sort this sequence of numbers: {5, 17, 50, 55, 65, 70, 80, 90, 100}? why?

(A) Quick Sort (B) Merge Sort (C) Selection Sort (D) Insertion Sort (E) Heap Sort

Explanation / Answer

1.
A, B, C, D, E, F

2.
A, B, C, D, F

3.
B, D, E

4.
D) Insertion sort -> since it takes less swaps, when the array is sorted or only few items to exchange.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.