Computer Science MCQS

Computer Science MCQ with detailed explanations for students & freshers preparing for entrance exams, various tests, interviews, competitive exams like GATE exam, interview, competitive examination and entrance exam.

Which of the following application makes use of a circular linked list?

A. a) Recursive function calls
B. b) Undo operation in a text editor
C. c) Implement Hash Tables
D. d) Allocating CPU to resources
Correct answer is: D. d) Allocating CPU to resources
ircular linked lists are particularly well-suited for scenarios where a cyclical or repetitive pattern is involved. In the context of CPU allocation, this is precisely the case.

Round-robin scheduling: This is a common algorithm used to allocate CPU time to multiple processes.

Circular nature: A circular linked list forms a loop, perfectly representing the cyclic nature of round-robin scheduling.

Efficient iteration: The circular structure allows for easy traversal from one process to the next without the need for special end-of-list checks.

By maintaining a circular linked list of processes, the operating system can efficiently cycle through them, granting each process a time slice of CPU time in turn. Once the last process is served, the list wraps back to the beginning, ensuring fairness and equal opportunity for all processes.

Would you li

Which data structure is based on the Last In First Out (LIFO) principle?

A. a) Tree
B. b) Linked List
C. c) Stack
D. d) Queue
Correct answer is: C. c) Stack
Explanation:

LIFO means the last element added to the stack is the first one to be removed.

Imagine a stack of plates. The last plate you put on the stack is the first one you take off.

This behavior is essential in many applications, such as function calls, expression evaluation, and backtracking algorithms.

Key operations of a stack:

Push: Adds an element to the top of the stack.

Pop: Removes the top element from the stack.

Peek: Returns the top element without removing it.

isEmpty: Checks if the stack is empty.

Which of the following points is/are not true about Linked List data structure when it is compared with an array?

A. a) Random access is not allowed in a typical implementation of Linked Lists
B. b) Access of elements in linked list takes less time than compared to arrays
C. c) Arrays have better cache locality that can make them better in terms of performance
D. d) It is easy to insert and delete elements in Linked List
Correct answer is: B. b) Access of elements in linked list takes less time than compared to arrays
Access of elements in linked list takes less time than compared to arrays is not true.

Explanation:

Arrays provide random access to elements. This means you can directly access any element by its index in constant time (O(1)).

Linked lists provide sequential access to elements. To access a specific element, you need to traverse the list from the beginning, one node at a time. This takes linear time (O(n)), where n is the number of elements in the list.

Therefore, accessing elements in a linked list is generally slower than in an array.

The other options are true:

a) Random access is not allowed in a typical implementation of Linked Lists: This is correct.

c) Arrays have better cache locality that can make them better in terms of performance: This is true due to the way arrays store elements contiguously in memory.

d) It is easy to insert and delete elements in Linked List: This is generally true, especially when compared to arrays, where shifting elements might be required.

The prefix form of A-B/ (C * D ^ E) is?

A. a) -A/B*C^DE
B. b) -A/BC*^DE
C. c) -ABCD*^DE
D. d) -/*^ACBDE
Correct answer is: A. a) -A/B*C^DE
Understanding Prefix Notation

In prefix notation, the operator precedes its operands.

The order of evaluation is from right to left.

Breaking Down the Expression

Given the infix expression: A - B / (C * D ^ E)

To convert it to prefix, we need to follow these steps:

Handle Parentheses:

We start with the innermost parentheses: (C * D ^ E)

Converting this to prefix: * ^ CD E

Handle Division:

The expression becomes: A - B / (* ^ CD E)

Converting it to prefix: - A / B * ^ CD E

Final Prefix Expression:

The complete prefix expression is: -A / B * ^ CD E

Therefore, the correct prefix form of the given infix expression is -A / B * ^ CD E.

The data structure required for Breadth First Traversal on a graph is?

A. a) Array
B. b) Stack
C. c) Tree
D. d) Queue
Correct answer is: D. d) Queue
A queue is the essential data structure for Breadth-First Search (BFS) traversal on a graph.

Why a Queue?

FIFO (First In, First Out) principle: This is crucial for exploring nodes level by level. The first node added to the queue is the first one to be visited.  

Efficient enqueue and dequeue operations: The queue allows for quick insertion and removal of nodes, which is necessary for BFS.

How it works:

Enqueue the starting node: Add the initial node to the queue.

Dequeue a node: Remove the front node from the queue and visit it.

Enqueue neighbors: Add all unvisited neighbors of the dequeued node to the queue.  

Repeat steps 2 and 3: Continue until the queue is empty.

By using a queue, BFS ensures that all nodes at a given depth are visited before moving to the next level, resulting in a breadth-wise exploration of the graph.

Which of the following statement(s) about stack data structure is/are NOT correct?

A. a) Top of the Stack always contain the new node
B. b) Stack is the FIFO data structure
C. c) Null link is present in the last node at the bottom of the stack
D. d) Linked List are used for implementing Stacks
Correct answer is: B. b) Stack is the FIFO data structure
Stack is the FIFO data structure is the incorrect statement.

Explanation:

Stack follows the LIFO (Last In, First Out) principle. This means the last element added to the stack is the first one to be removed.

FIFO (First In, First Out) is the characteristic of a queue data structure, not a stack.

The other options are correct:

a) Top of the Stack always contains the new node: This is true, as new elements are added to the top of the stack.

c) Null link is present in the last node at the bottom of the stack: This is typically true in a linked list implementation of a stack, where the bottom node points to null to indicate the end of the stack.

d) Linked List are used for implementing Stacks: This is a common way to implement stacks.

What data structure would you mostly likely see in non recursive implementation of a recursive algorithm?

A. a) Stack
B. b) Linked List
C. c) Tree
D. d) Queue
Correct answer is: A. a) Stack
A stack is the data structure most likely seen in a non-recursive implementation of a recursive algorithm.

Why a Stack?

LIFO (Last In, First Out) property: This mirrors the behavior of recursive function calls, where the most recent function call is the first to finish.

Simulates function call stack: In recursion, the system implicitly uses a stack to keep track of function calls and their return addresses. A non-recursive implementation can explicitly use a stack to mimic this behavior.

How it works:

Push function arguments and local variables onto the stack: Before processing a recursive call, store relevant information on the stack.

Process the current iteration: Handle the current problem without making recursive calls.

Pop values from the stack for the next iteration: Retrieve stored information to simulate returning from a recursive call.

By using a stack, you can effectively transform a recursive algorithm into an iterative one, often improving performance and memory efficiency.

What is the value of the postfix expression 6 3 2 4 + – *?

A. a) 74
B. b) -18
C. c) 22
D. d) 40
Correct answer is: B. b) -18
Postfix notation evaluates expressions by processing operands first, followed by operators.

Given expression: 6 3 2 4 + - *

Scan the expression from left to right:

6, 3, 2, 4: These are operands, so we push them onto a stack.

+: We encounter an operator. Pop the top two elements from the stack (4 and 2), add them (4 + 2 = 6), and push the result (6) back onto the stack.

-: We encounter another operator. Pop the top two elements from the stack (6 and 3), subtract them (3 - 6 = -3), and push the result (-3) back onto the stack.

*: We encounter the last operator. Pop the top two elements from the stack (6 and -3), multiply them (6 * -3 = -18), and push the result (-18) back onto the stack.

Since we've reached the end of the expression, the final result is the only element left on the stack, which is -18.

Therefore, the value of the postfix expression 6 3 2 4 + - * is -18.

Which data structure is needed to convert infix notation to postfix notation?

A. a) Tree
B. b) Branch
C. c) Stack
D. d) Queue
Correct answer is: C. c) Stack
LIFO (Last In, First Out) property: This is crucial for handling operators and their precedence.

Efficient push and pop operations: The stack allows for quick insertion and removal of operators, which is necessary for the conversion process.

How it works:

Scan the infix expression from left to right:

If an operand is encountered, add it to the postfix expression.

If an operator is encountered:While the stack is not empty and the precedence of the top operator is greater than or equal to the precedence of the current operator, pop the top operator from the stack and add it to the postfix expression. Push the current operator onto the stack.

When the end of the expression is reached:

Pop all remaining operators from the stack and add them to the postfix expression.

By using a stack and following these steps, we can effectively convert infix expressions to their postfix equivalents.

Which of the following is not the application of stack?

A. a) Data Transfer between two asynchronous process
B. b) Compiler Syntax Analyzer
C. c) Tracking of local variables at run time
D. d) A parentheses balancing program
Correct answer is: A. a) Data Transfer between two asynchronous process
Stacks follow LIFO (Last In, First Out) principle: This means the last element added is the first one to be removed.

Data transfer between asynchronous processes requires a FIFO (First In, First Out) structure, where the first element added is the first one to be removed.

Queues are the ideal data structure for this purpose, as they adhere to the FIFO principle.

Other options:

b) Compiler Syntax Analyzer: Stacks are used extensively in compilers for parsing expressions and checking for syntax errors.

c) Tracking of local variables at run time: Function calls and their corresponding local variables are managed using stacks.

d) A parentheses balancing program: As we discussed earlier, stacks are essential for checking the balance of parentheses in an expression.

Therefore, while stacks are crucial for many applications, they are not suitable for data transfer between asynchronous processes.

Scroll to Top