Campus and Interview Preparation with Data Structure
Important topic of Data Structure :-
(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
If this article is helpful to you then please like share and comments.. Thank you...
 |
| 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)
(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;
}
}
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.
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.
(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
some pointer is
(a) 0 (1)
(b) 0 (log n)
(c) 0 (n)
(d) 0 (n 1og n)
(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
called
(a) Linked list
(b) node list
(c) Primitive list
(d) None of these
(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
(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)
(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
(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)
(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
(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.comIf this article is helpful to you then please like share and comments.. Thank you...
Comments
Post a Comment