Data Structures and Algorithms - B.Tech 3rd Semester Exam., 2019 (New Course)

Which of the following points is/are true about linked list data structure when it is compared with array?

1. Arrays have better cache locality that can make them better in terms of performance.
2. It is easy to insert and delete elements in linked list.
3. The size of array has to be pre-decided, linked lists can change their size any time.
4. All of the above

What is the functionality of the following code?
\( public\ void\ function(Node\ node)\ \{ \)
\( \quad if(size==0)\ head=node; \)
\( \quad else\ \{ \)
\( \quad \quad Node\ temp,\ cur; \)
\( \quad \quad for(cur=head; (temp=cur.getNext())! \) \(=null; cur=temp); \)
\( \quad \quad cur.setNext(node); \)
\( \quad \} \)
\( \quad size++; \)
\( \} \)

1. Inserting a node at the beginning of the list
2. Deleting a node at the beginning of the list
3. Inserting a node at the end of the list
4. Deleting a node at the end of the list

What is the space complexity for deleting a linked list?

1. \( O(1) \)
2. \( O(n) \)
3. Either \( O(1) \) or \( O(n) \)
4. \( O(\log n) \)

The situation when in a linked list START=NULL is

1. underflow
2. overflow
3. housefull
4. saturated

What would be the asymptotic time complexity to add a node at the end of singly linked list, if the pointer is initially pointing to the head of the list?

1. \( O(1) \)
2. \( O(n) \)
3. \( \Theta(n) \)
4. \( \Theta(1) \)

What kind of linked list is best to answer question like "What is the item at position n"?

1. Singly linked list
2. Doubly linked list
3. Circular linked list
4. Array implementation of linked list

A variation of linked list is circular linked list, in which the last node in the list points to first node of the list. One problem with this type of list is

1. it wastes memory space since the pointer head already points to the first node and thus the list node does not need to point to the first node
2. it is not possible to add a node at the end of the list
3. it is difficult to traverse the list as the pointer of the last node is now not NULL
4. All of the above

Each node in a linked list must contain at least

1. three fields
2. two fields
3. four fields
4. five fields

A linear list in which the last node points to the first node is

1. singly linked list
2. circular linked list
3. doubly linked list
4. None of the above

In a linked list, insertion can be done at

1. beginning
2. end
3. middle
4. All of the above

What is a Hash Table, and what is the average case and worst-case time for each of its operations? How can we use this structure to find all anagrams in a dictionary?

Describe insertion in max heap tree with example from the following list of numbers: 33, 42, 67, 23, 44, 49, 74

Sort the given values using quicksort and write time complexity of algorithm: 65, 70, 75, 80, 85, 60, 55, 50, 45

Insert the following sequence of elements into an AVL tree, starting with an empty tree: 10, 20, 15, 25, 30, 16, 18, 19

Delete 30 in the AVL tree that you got.

Write algorithm for quicksort and mention time and space complexity in each case.

Define collision in hashing. What are the different methodologies to resolve collision? Explain briefly.

Construct binary search tree and write pre- and post-order traversals of this tree: 8, 3, 1, 10, 6, 14, 4, 7, 13, 22, 5

Write algorithm to count leaf node in binary tree and check whether tree is balanced or not.

Write a recursive and iterative version of insertion sort algorithm and mention time complexity.

BFS

DFS

Binary search tree

Balance factor