Advantages of Linked list:

1. Linked lists are dynamic. Their size can be altered during runtime.
2. Memory-efficient.
3. Insertion and Deletion is easier.

1. Consumes more space as additional space is required to store pointer address.

1. Creation
2. Insertion
3. Deletion
4. Travevrsing

Solved Example: 9968-01

Which type of linked list stores the address of the header node in the next field of the last node ? (NIELIT Scientist B- 2020)

A. Singly linked list

B. Circular linked list

C. Doubly linked list

D. Hashed list

Correct Answer: B

Solved Example: 9968-02

What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order? (GATE CS 2020)

A. $\theta (n)$

B. $\theta (n \log n)$

C. $\theta (n^2)$

D. $\theta (1)$

Correct Answer: C

Solved Example: 9968-03

In a doubly linked list, the number of pointers affected for an insertion operation will be: (ISRO Scientist CS 2017)

A. 4

B. 0

C. 1

D. Depends upon the nodes of the doubly linked list

Correct Answer: D

A tree is a non-empty set, one element of which is designed the root of the tree while the remaining elelments are partitioned into non-empty sets each of which is a sub-tree of the root.

1. Leaf Node:
2. Path:
3. Siblings
4. Ancestors and Descendent
5. Subtree
6. Level

Solved Example: 9971-01

Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is: (GATE CS 2015)

A. $\Omega(\log n)$

B. $(n)$

C. $(n \log n)$

D. $(n^2)$

Correct Answer: A

Advantages of Arrays:

1. Convenient to declare
2. Syntax is easy to code and remember
3. Accessing by index number is faster.

1. Size of an array is fixed and has to be speified at the compile time. Overallocation is often practiced to be on the safer side. This is not memory efficient.
2. Insertion of new items is complicated at specific location, as it disrupts entire array.

Solved Example: 9970-01

Consider a 2-dimensional array x with 10 rows and 4 columns, with each element storing a value equivalent to the product of row number and column number. The array is stored in row-major format. If the first element x[0][0] occupies the memory location with address 1000 and each element occupies only one memory location, which all locations (in decimal) will be holding a value of 10? (ISRO Scientist CS 2020)

A. 1018, 1019

B. 1022, 1041

C. 1017, 1036

D. 1000, 1399

Correct Answer: C

Solved Example: 9970-02

An algorithm performs $(\log N)^{\dfrac{1}{2}}$ find operations, N inserts operations, $(\log N)^{\dfrac{1}{2}}$ delete operations, and $(\log N)^{\dfrac{1}{2}}$ decrease - key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease - key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations? (GATE CS 2015)

A. Unsorted array

B. Min-heap

C. Sorted array

D. Sorted doubly linked list

Correct Answer: A