WorksheetsTechnical MCQs
Total questions: 35
Worksheet time: 26mins
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is
O(n)
O(logn)
O(log*n)
O(1)
Let A be a square matrix of size n x n. Consider the following program. What is the expected output?
C = 100
for i = 1 to n do
for j = 1 to n do
{
Temp = A[i][j] + C
A[i][j] = A[j][i]
A[j][i] = Temp - C
}
for i = 1 to n do
for j = 1 to n do
Output(A[i][j]);
The matrix A itself
Transpose of matrix A
Adding 100 to the upper diagonal elements and subtracting 100 from diagonal elements of A
None of the above
Consider an array consisting of -ve and +ve numbers. What would be the worst time comparisons an algorithm can take in order to segregate the numbers having same sign altogether i.e all +ve on one side and then all -ve on the other ?
N-1
N
N+1
(N*(N-1))/2
Consider the following function that takes reference to head of a Doubly Linked List as parameter. Assume that a node of doubly linked list has previous pointer as prev and next pointer as next.
void fun(struct node **head_ref)
{
struct node *temp = NULL;
struct node *current = *head_ref;
while (current != NULL)
{
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}
if(temp != NULL )
*head_ref = temp->prev;
}
Assume that reference of head of following doubly linked list is passed to above function 1 2 3 4 5 6. What should be the modified linked list after the function call?
2 <--> 1 <--> 4 <--> 3 <--> 6 <-->5
5 <--> 4 <--> 3 <--> 2 <--> 1 <-->6
6 <--> 5 <--> 4 <--> 3 <--> 2 <--> 1
6 <--> 5 <--> 4 <--> 3 <--> 1 <--> 2
Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?
Insertion Sort
Quick Sort
Heap Sort
Merge Sort
What is the output of following function for start pointing to first node of following linked list? 1->2->3->4->5->6
void fun(struct node* start)
{
if(start == NULL)
return;
printf("%d ", start->data);
if(start->next != NULL )
fun(start->next->next);
printf("%d ", start->data);
}
1 4 6 6 4 1
1 3 5 1 3 5
1 2 3 5
1 3 5 5 3 1
In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is
log 2 n
n/2
log 2 n – 1
n
Consider the following pseudocode that uses a stack
declare a stack of characters
while ( there are more characters in the word to read )
{
read a character
push the character on the stack
}
while ( the stack is not empty )
{
pop a character off the stack
write the character to the screen
}
What is output for input "codelab"?
codelabcodelab
baledoc
codelab
baledocbaledoc
The following postfix expression with single digit operands is evaluated using a stack:
8 2 3 ^ / 2 3 * + 5 1 * -
Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:
6, 1
5, 7
3, 2
1, 5
To evaluate an expression without any embedded function calls:
One stack is enough
Two stacks are needed
As many stacks as the height of the expression tree are needed
A Turing machine is needed in the general case
How many stacks are needed to implement a queue. Consider the situation where no other data structure like arrays, linked list is available to you.
1
2
3
4
The maximum number of binary trees that can be formed with three unlabeled nodes is:
1
5
4
3
The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:
n/2
(n-1)/3
(n-1)/2
(2n+1)/3
The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:
2^h -1
2^(h-1) – 1
2^(h+1) -1
2*(h+1)
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?
7 5 1 0 3 2 4 6 8 9
0 1 2 3 4 5 6 7 8 9
0 2 4 3 1 6 5 9 8 7
9 8 6 4 2 3 0 1 5 7
The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?
2
3
4
6
Which of the following traversals is sufficient to construct BST from given traversals 1) Inorder 2) Preorder 3) Postorder
Any one of the given three traversals is sufficient
Either 2 or 3 is sufficient
2 and 3
1 and 3
The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?
10, 20, 15, 23, 25, 35, 42, 39, 30
15, 10, 25, 23, 20, 42, 35, 39, 30
15, 20, 10, 23, 25, 42, 35, 39, 30
15, 10, 23, 25, 20, 35, 42, 39, 30
Given an undirected graph G with V vertices and E edges, the sum of the degrees of all vertices is
E
2E
V
2V
How many undirected graphs (not necessarily connected) can be constructed out of a given set V = {v1, v2, ... vn} of n vertices?
n(n-1)/2
2n
n!
2n(n-1)/2
A shared variable x, initialized to zero, is operated on by four concurrent processes W, X, Y, Z as follows. Each of the processes W and X reads x from memory, increments by one, stores it to memory, and then terminates. Each of the processes Y and Z reads x from memory, decrements by two, stores it to memory, and then terminates. Each process before reading x invokes the P operation (i.e., wait) on a counting semaphore S and invokes the V operation (i.e., signal) on the semaphore S after storing x to memory. Semaphore S is initialized to two. What is the maximum possible value of x after all processes complete execution?
-2
-1
1
2
A process executes the code
fork();
fork();
fork();
The total number of child processes created is
3
4
7
8
Consider three CPU-intensive processes, which require 10, 20 and 30 time units and arrive at times 0, 2 and 6, respectively. How many context switches are needed if the operating system implements a shortest remaining time first scheduling algorithm? Do not count the context switches at time zero and at the end.
1
2
3
4
Which of the following process scheduling algorithm may lead to starvation
FIFO
Round Robin
Shortest Job Next
None of the above
If the quantum time of round robin algorithm is very large, then it is equivalent to:
First in first out
Shortest Job Next
Priority scheduling
None of the above
Consider the 3 processes, P1, P2 and P3 shown in the table.
Process Arrival time Time Units Required
P1 0 5
P2 1 7
P3 3 4
The completion order of the 3 processes under the policies FCFS and RR2 (round robin scheduling with CPU quantum of 2 time units) are
FCFS: P1, P2, P3
RR2: P1, P2, P3
FCFS: P1, P3, P2
RR2: P1, P3, P2
FCFS: P1, P2, P3
RR2: P1, P3, P2
FCFS: P1, P3, P2
RR2: P1, P2, P3
Consider the following table of arrival time and burst time for three processes P0, P1 and P2.
Process Arrival time Burst Time
P0 0 ms 9 ms
P1 1 ms 4 ms
P2 2 ms 9 ms
The pre-emptive shortest job first scheduling algorithm is used. Scheduling is carried out only at arrival or completion of processes. What is the average waiting time for the three processes?
5.0 ms
4.33 ms
6.33 ms
7.33 ms
Which of the following statements are true?
I. Shortest remaining time first scheduling may cause starvation
II. Preemptive scheduling may cause starvation
III. Round robin is better than FCFS in terms of response time
I only
I and III only
II and III only
I, II and III
In the process state transition diagram for a uniprocessor system, assume that there are always some processes in the ready state: Now consider the following statements: I. If a process makes a transition D, it would result in
another process making transition A immediately.
II. A process P2 in blocked state can make transition E
while another process P1 is in running state.
III. The OS uses preemptive scheduling.
IV. The OS uses non-preemptive scheduling.
Which of the above statements are TRUE?
I and II
I and III
II and III
II and IV
Which of the following page replacement algorithms suffers from Beladyâs anomaly?
FIFO
LRU
Optimal Page Replacement
Both LRU and FIFO
Page fault occurs when
When a requested page is in memory
When a requested page is not in memory
When a page is corrupted
When an exception is thrown
An operating system uses the Bankerâs algorithm for deadlock avoidance when managing the allocation of three resource types X, Y, and Z to three processes P0, P1, and P2. The table given presents the current system state. Here, the Allocation matrix shows the current number of resources of each type allocated to each process and the Max matrix shows the maximum number of resources of each type required by each process during its execution. There are 3 units of type X, 2 units of type Y and 2 units of type Z still available. The system is currently in a safe state. Consider the following independent requests for additional resources in the current state:
REQ1: P0 requests 0 units of X,
0 units of Y and 2 units of Z
REQ2: P1 requests 2 units of X,
0 units of Y and 0 units of Z
Which one of the following is TRUE?
Only REQ1 can be permitted.
Only REQ2 can be permitted.
Both REQ1 and REQ2 can be permitted.
Neither REQ1 nor REQ2 can be permitted
A system contains three programs and each requires three tape units for its operation. The minimum number of tape units which the system must have such that deadlocks never arise is _________.
6
7
8
9
Which of the following is major part of time taken when accessing data on the disk?
Settle time
Rotational latency
Seek time
Waiting time
Put the following disk scheduling policies results in minimum amount of head movement.
FCFS
Circular SCAN
Elevator/SCAN
LOOK
