Dharma Placement Paper - Data Structure Questions And Answers

Dharma Previous Years Solved Sample Placement Papers

1. A linear collection of data elements where the linear node is given by means of pointer is called?
   (a) Linked list
   (b) Node list
   (c) Primitive list
   (d) Unordered list
   Answer: (a)
   Explanation: In a linked list, each node contains data and the address of the next node. These nodes are linked using pointers.

2. Consider an implementation of an unsorted singly linked list with a head pointer only. Given the representation, which of the following operations can be implemented in O(1) time?
   i) Insertion at the front of the linked list
   ii) Insertion at the end of the linked list
   iii) Deletion of the front node of the linked list
   iv) Deletion of the last node of the linked list
   (a) I and II
   (b) I and III
   (c) I, II, and III
   (d) I, II, and IV
   Answer: (b)
   Explanation: Insertion and deletion at the front of the linked list can be done in O(1) time because the head pointer is known. Operations at the end require traversal, resulting in O(n) time.

3. In a linked list, each node contains a minimum of two fields. One field is the data field to store the data. The second field is?
   (a) Pointer to character
   (b) Pointer to integer
   (c) Pointer to node
   (d) Node
   Answer: (c)
   Explanation: Each node contains data and a pointer (reference) to the next node in the list.

4. What would be the asymptotic time complexity to add a node at the end of a singly linked list, if the pointer is initially pointing to the head of the list?
   (a) O(1)
   (b) O(n)
   (c) θ(n)
   (d) θ(1)
   Answer: (c)
   Explanation: To add a node at the end, we must traverse the list from the head to the last node. This traversal takes θ(n) time.

5. What would be the asymptotic time complexity to insert an element at the front of the linked list (head is known)?
   (a) O(1)
   (b) O(n)
   (c) O(n²)
   (d) O(n³)
   Answer: (a)
   Explanation: Adding a node at the front involves creating a new node and updating the head pointer. This takes constant time, O(1).

6. What would be the asymptotic time complexity to find an element in the linked list?
   (a) O(1)
   (b) O(n)
   (c) O(n²)
   (d) O(n⁴)
   Answer: (b)
   Explanation: In the worst case, the desired element is at the end of the list, requiring traversal of all nodes. This results in O(n) time complexity.

7. What would be the asymptotic time complexity to insert an element at the second position in the linked list?
   (a) O(1)
   (b) O(n)
   (c) O(n²)
   (d) O(n³)
   Answer: (a)
   Explanation: Adding a node at the second position requires updating the pointer of the new node and the first node. This process is done in O(1) time.

8. The concatenation of two lists can be performed in O(1) time. Which of the following variations of the linked list can be used?
   (a) Singly linked list
   (b) Doubly linked list
   (c) Circular doubly linked list
   (d) Array implementation of list
   Answer: (c)
   Explanation: A circular doubly linked list allows concatenation in O(1) time by breaking and reconnecting links at the ends of the two lists.

9. Consider the following definition in C programming language:
   struct node {
int data;
struct node *next;
};
typedef struct node NODE;
NODE *ptr;
   Which of the following C code is used to create a new node?
   (a) ptr = (NODE*)malloc(sizeof(NODE));
   (b) ptr = (NODE*)malloc(NODE);
   (c) ptr = (NODE*)malloc(sizeof(NODE*));
   (d) ptr = (NODE)malloc(sizeof(NODE));
   Answer: (a)
   Explanation: The correct way to allocate memory for a new node in C is to use malloc(sizeof(NODE)).