CSD201 Questions plus Answers 2024
2. 2. Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?
a. Merge Sort
b. Insertion Sort
c. Quick Sort
d. Heap Sort: a
3. 3. What is the output of following function for start pointing to first no...
1. 1. What does the following function do for a given Linked List with first node as head?
void fun1(node head)
{ if(head == NULL)
return; fun1(head.next);
System.out.write(head.data);
}
a. Prints all nodes of linked list in reverse order
b. Prints all nodes of linked lists
c. Prints alternate nodes of Linked List
d. Prints alternate nodes in reverse order: a
2. 2. Which of the following sorting algorithms can be used to sort a random linked list with minimum time
complexity?
a. Merge Sort
b. Insertion Sort
c. Quick Sort
d. Heap Sort: a
3. 3. What is the output of following function for start pointing to first node of following linked list? 1->2->3-
>4->5->6
if(start.next != NULL )
fun(start.next.next);
System.out.write(star.data);
}
a. 1 3 5 5 3 1
b. 1 4 6 6 4 1
c. 1 3 5 1 3 5
d. 1 2 3 5: a
4. 4. In the worst case, the number of comparisons needed to search a singly linked list of length n for a given
element is
a. n
b. n/2
, CSD201 Questions plus Answers 2024
c. log¬2n -1
d. log¬2n: a
5. 5. Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations
among union, intersection, membership, cardi- nality will be the slowest?
a. union, intersection
b. membership, cardinality
c. intersection, membership
d. union only: a
6. 6. 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): a
7. 7. 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:
a
8. 8. 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 last element of the list
b. Delete the first element
c. Insert a new element as a first element
d. Add a new element at the end of the list: a
9. 9. 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(1)
b. O(n)
c. O(logn)
d. O(log2n): b
, CSD201 Questions plus Answers 2024
10. 10. The concatenation of two lists is to be performed in O(1) time. Which of the following implementations
of a list should be used?
a. circular doubly linked list
b. array implementation of lists
c. doubly linked list
d. singly linked list: a
11. 11. Consider the following statements:
i. First-in-first out types of computations are efficiently supported by STACKS.
ii. Implementing LISTS on linked lists is more efficient than implementing LISTS on
an array for almost all the basic LIST operations.
iii. Implementing QUEUES on a circular array is more efficient than imple- menting QUEUES on a linear
array with two indices.
iv. Last-in-first-out type of computations are efficiently supported by QUEUES.
a. (ii) and (iii) are true
b. (i) and (ii) are true
c. (iii) and (iv) are true
d. (ii) and (iv) are true: a
12. 12. Following is C like pseudo code of a function that takes a number as an argument, and uses a stack S
to do processing
void fun(int n)
{
Stack S; // Say it creates an empty stack S while (n > 0)
{
// This line pushes the value of n%2 to stack S push(&S, n%2);
n = n/2;
}
// Run while Stack S is not empty while (!
isEmpty(&S))
printf("%d ", pop(&S)); // pop an element from S and print it
}
a. Prints binary representation of n
, CSD201 Questions plus Answers 2024
b. Prints the value of Logn
c. Prints the value of Logn in reverse order
d. Prints binary representation of n in reverse order: a
13. 13. Which one of the following is an application of Stack Data Structure?
a. Arithmetic expression evaluation
b. Organization charts
c. File systems
d. Programming environments: a
14. 14. To evaluate an expression without any embedded function calls:
a. One stack is enough
b. As many stacks as the height of the expression tree are needed
c. Two stacks are needed
d. A Turing machine is needed in the general case: a
15. 15. The result evaluating the postfix expression 10 5 + 60 6 / * 8 - is a. 142
b. 284
c. 213
d. 71: a
16. 16. Suppose a stack is to be implemented with a linked list instead of an array. What would be the
effect on the time complexity of the push and
pop operations of the stack implemented using linked list (Assuming stack is implemented efficiently)?
a. O(1) for insertion and O(1) for deletion
b. O(1) for insertion and O(n) for deletion
c. O(n) for insertion and O(1) for deletion
d. O(n) for insertion and O(n) for deletion: a
17. 17. The best data structure to check whether an arithmetic expression has balanced parenthesis is a
a. Stack
b. Tree
c. Queue
d. List: a
18. 18. The seven elements A, B, C, D, E, F and G are
pushed onto a stack in reverse order, i.e., starting from G. The stack is popped five times and each element is
inserted into a queue.Two elements are deleted from the queue and pushed back onto the stack.Now, is
element presented at top of the stack.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller Certifiedacademics. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $10.79. You're not tied to anything after your purchase.
