11.  In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is 
a.  log 2 n 
b.  n/2 
c.  log 2 n – 1 
d.  n 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).n

12.  Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest? 
a.  union only 
b.  intersection, membership 
c.  membership, cardinality 
d.  union, intersection 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).union, intersection

13.  Consider the function f defined below.
struct item { int data; struct item * next; }; int f(struct item *p) { return ( (p == NULL)  (p>next == NULL)  (( P>data <= p>next>data) && f(p>next)) ); } For a given linked list p, the function f returns 1 if and only if 
a.  the list is empty or has exactly one element 
b.  the elements in the list are sorted in nondecreasing order of data value 
c.  the elements in the list are sorted in nonincreasing order of data value 
d.  not all elements in the list have the same data value 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).the elements in the list are sorted in nondecreasing order of data value

14.  What are the time complexities of finding 8th element from beginning and 8th element from end in a singly linked list? Let n be the number of nodes in linked list, you may assume that n > 8. 
a.  O(1) and O(n) 
b.  O(1) and O(1) 
c.  O(n) and O(1) 
d.  O(n) and O(n) 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).O(1) and O(n)

15.  Is it possible to create a doubly linked list using only one pointer with every node. 
a.  Not Possible 
b.  Yes, possible by storing XOR of addresses of previous and next nodes 
c.  Yes, possible by storing XOR of current node and next node 
d.  Yes, possible by storing XOR of current node and previous node 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).Yes, possible by storing XOR of addresses of previous and next nodes

16.  Given pointer to a node X in a singly linked list. Only one pointer is given, pointer to head node is not given, can we delete the node X from given linked list? 
a.  Possible if X is not last node. Use following two steps (a) Copy the data of next of X to X. (b) Delete next of X 
b.  Possible if size of linked list is even 
c.  Possible if size of linked list is odd 
d.  Possible if X is not first node. Use following two steps (a) Copy the data of next of X to X. (b) Delete next of X 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).Possible if X is not last node. Use following two steps (a) Copy the data of next of X to X. (b) Delete next of X

17.  You are given pointers to first and last nodes of a singly linked list, which of the following operations are dependent on the length of the linked list? 
a.  Delete the first element 
b.  Insert a new element as a first element 
c.  Delete the last element of the list 
d.  Add a new element at the end of the list 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).Delete the last element of the list

18.  Consider the following function to traverse a linked list.
void traverse(struct Node *head) { while (head>next != NULL) { printf("%d ", head>data); head = head>next; } } Which of the following is FALSE about above function? 
a.  The function may crash when the linked list is empty 
b.  The function doesn't print the last node when the linked list is not empty 
c.  The function is implemented incorrectly because it changes head 
d.  None of the above 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).The function is implemented incorrectly because it changes head

19.  Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worstcase 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) 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).O(1)

20.  N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decreasekey operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations on the list in this order: Θ(N) delete, O(log N) insert, O(log N) find, and Θ(N) decreasekey What is the time complexity of all these operations put together 
a.  O(Log^2N) 
b.  O(N) 
c.  O(N^2) 
d.  Θ(N^2 Log N) 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).O(N^2)
