Campus and Interview Preparation with Data Structure

Important topic of  Data Structure    :-

• Stack

• Queue

• Linked List

• Sorting

• Heap

• Tree

• AVL Tree

• Hashing

• C language questions

• C ++ Language

campus/interview preparation

Objective type questions or multiple choice questions (MCQ) are often asked in various exams, including job recruitment tests. It also helps in understanding language constructs, syntax and fundamental rules.click the link given in above list to go to that topic.

Linked List in Data Structure

1. Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best known algorithm to delete the node x from the list?

(a) O(n)
(b) O(log2 n)
(c) O(logn)
(d) O(1)

Answer

(a)

To delete an intermediate node, the next pointer of Q should be copied to previous node’s next pointer. For this to happen, previous node address should be known. So a traversal of linked list should be done which has time complexity of O (n).

2. The following C function takes a singly-linked list of integers as a parameter and rearranges the elements of the list. The list is represented as pointer to a structure. The function is called with the list containing the integers 1, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents of the list after the function completes execution?

struct node {int value; struct node *next;);
void rearrange (struct node *list) {
struct node *p, *q;
int temp;
if (!list || !list -> next) return;
p = list; q = list -> next;
while (q) {
temp = p -> value;
p -> value = q -> value;
q -> value = temp;
p = q -> next;
q = p ? p -> next : 0;
}
}

(a) 1, 2, 3, 4, 5, 6, 7
(b) 2, 1, 4, 3, 6, 5, 7
(c) 1, 3, 2, 5, 4, 7, 6
(d) 2, 3, 4, 5, 6, 7, 1

Answer

(b)

Initially p points to first node and q points to second node. Now value of both the nodes get interchanged by code of swapping using third variable. After swapping
p = q -> next
q points to third node now.
q = p -> next
and q points to fourth node.
In this data of two nodes get interchanged and now it points to next two nodes.

3. In a circular linked list

(a) Components are all linked together in some sequential manner.
(b) There is no beginning and no end.
(c) Components are arranged hierarchically.
(d) Forward and backward traversal within the list is permitted.

Answer

(b)

In a circular linked list, the last node contains the address of first node, looping in itself. So there is no end and no beginning.

4. In a linked list with n nodes, the time taken to insert an element after an element pointed by
some pointer is

(a) 0 (1)
(b) 0 (log n)
(c) 0 (n)
(d) 0 (n 1og n)

Answer

(a)

If the element after which node needs to be inserted is pointed by some pointer, then traversal of complete list is not required. Thus insertion in that case is O (1) .

5. 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) None of these

Answer

(a)

6. Which of the following operations is performed more efficiently by doubly linked list than by singly linked list?

(a) Deleting a node whose location is given
(b) Searching of an unsorted list for a given item
(c) Inverting the list after the node with given location
(d) Traversing a list to process each node

Answer

(a)

For deleting the node in singly linked list, a traversal is needed till previous node of the node to be deleted which is not required in case of doubly linked list.

7. The time required to delete a node x from a doubly linked list having n nodes is

(a) O (n)
(b) O (log n)
(c) O (1)
(d) O (n log n)

Answer

(c)

To delete a node x (a pointer) , no traversal is required. Thus o (1) is required.

8. Time required finding any element of the linked list is.

(a) O (n2)
(b) O (1)
(c) O (n)
(d) None of these

Answer

(c)

O (n)Traversal of linked list of all n items is required to search element in the worst case. Thus O (n) is the time complexity.

9. Pointer is pointing to the first element of the Node then time required to insert Element to second position is

(a) O(n2)
(b) O (sqrt(n))
(c) O(n)
(d) O(1)

Answer

(d)

Since insertion is O (1) and no traversal is required to reach the second node. Thus it is done in O (1).

10. A variant of linked list in which last node of the list points to the first node of the list is?

(a) Singly linked list
(b) Doubly linked list
(c) Circular linked list
(d) Multiply linked list

Answer

(c)

This is the definition of Circular linked list.

source-www.mysirg.com

If this article is helpful to you then please like share and comments.. Thank you...