Sample Paper for Mid-Terms (Course Code: CSE-228)
Unit 1:
1. Which notation is used to describe the worst-case time complexity of an algorithm?
a) Omega notation
b) Theta notation
c) Big O notation
d) None of the above
Correct answer: c) Big O notation
2. What does complexity analysis help us understand about an algorithm?
a) The running time of the algorithm
b) The space requirements of the algorithm
c) The trade-off between time and space
d) All of the above
Correct answer: d) All of the above
3. What does the term "asymptotic" mean in the context of complexity analysis?
a) The exact running time of an algorithm
b) The worst-case running time of an algorithm
c) An approximation of the running time
d) The running time as the input size approaches infinity
Correct answer: d) The running time as the input size approaches infinity
4. What is the time complexity of the following code snippet?
int i = 1;
while (i < n) {
i = i * 2;
}
a) O(1)
b) O(log n)
c) O(n)
d) O(n^2)
Correct answer: b) O(log n)
5. What is the time complexity of the following code snippet?
for (int i = 0; i < n; i++) {
for (int j = 1; j < n; j = j * 2) {
// Some constant-time operations
}
}
a) O(n)
b) O(n log n)
c) O(log n)
d) O(n^2)
Correct answer: b) O(n log n)
6. What is the time complexity of the following code snippet?
for (int i = 0; i < n; i++) {
for (int j = i; j > 0; j = j / 2) {
// Some constant-time operations
}
}
a) O(1)
b) O(log n)
c) O(n)
d) O(n^2)
Correct answer: b) O(log n)
7. What is the time complexity of the following code snippet?
for (int i = 0; i < n; i++) {
for (int j = n; j > 0; j = j / 2) {
// Some constant-time operations
}
}
a) O(1)
b) O(log n)
c) O(n)
d) O(n^2)
Correct answer: b) O(log n)
8. Which of the following statements about stacks is true?
a) Stacks are dynamic data structures that can resize automatically.
b) Stacks can only store elements of the same data type.
c) Stacks are primarily used for searching and sorting operations.
d) Stacks can be implemented using arrays or linked lists.
Correct answer: d) Stacks can be implemented using arrays or linked lists.
9. How can a stack be used to reverse the order of elements in an array efficiently?
a) By pushing all elements of the array onto the stack and then popping them back
into a new array.
b) By popping all elements of the array and pushing them onto a new stack.
c) By swapping the first and last elements of the array repeatedly using a stack.
d) By inserting each element of the array at the bottom of the stack.
10. Which of the following statements about stack overflow is true?
a) Stack overflow occurs when the stack runs out of memory space.
b) Stack overflow is a technique used to insert new elements into a stack.
c) Stack overflow is an error that occurs when the stack becomes empty.
d) Stack overflow is the process of removing elements from a stack.
Correct answer: a) Stack overflow occurs when the stack runs out of memory
space.
11. In a stack, which element is always accessible?
a) Top element
b) Bottom element
c) Middle element
d) All elements
Correct answer: a) Top element
12. What is typically counted during runtime analysis?
a) The number of arithmetic and other operations required for the program
execution.
b) The amount of memory (megabytes) needed for the program to run.
c) The duration in seconds needed for the program to run.
d) The sum of seconds and megabytes required for the program to run.
e) The product of seconds and megabytes needed for the program to run.
Correct answer: a) The number of arithmetic and other operations required for the
program execution.
13. Which of the following options represents the correct big-O notation for the sum of
consecutive numbers from 1 to n?
a) O(log n)
b) O(n)
c) O(n log n)
d) O(n²)
Correct answer: b) O(n²)
14. What is the worst-case time complexity of the given loop?
while (n > 0)
{
n = n/10; // Integer division is used
}
a) O(1)
b) O(log n)
c) O(n)
d) O(n²)
Correct answer: b) O(log n)
15. Which stack operation can potentially cause stack underflow?
a) is_empty
b) pop
c) push
d) Two or more of the above operations
Correct answer: b) pop
16. Which of the following applications could utilize a stack?
a) A program to balance parentheses.
b) Managing local variables during runtime.
c) Syntax analyzer for a compiler.
d) All of the above.
Correct answer: d) All of the above.
17. In the linked list implementation of the stack class, where does the push operation place
a new entry in the linked list?
a) At the head
b) At the tail
c) After all other entries that are greater than the new entry.
d) After all other entries that are smaller than the new entry.
Correct answer: a) At the head
18. In the array-based implementation of the stack class (with a fixed-sized array), which
operations have a worst-case behavior requiring linear time?
a) is_empty
b) peek
c) pop
d) push
e) None of these operations require linear time.
Correct answer: c) pop
19. You are tasked with performing a queue operation using a stack. Assuming the stack
has a size of 'n' and contains 'm' variables, what is the time complexity of performing the
deQueue operation using only stack operations (push and pop)?
a) O(m)
b) O(n)
c) O(m*n)
d) The provided data is insufficient.
Correct answer: a) O(m)
20. If for an algorithm time complexity is given by O((3⁄2)n) then complexity will be
a) constant
b) quardratic
c) exponential
d) none of the mentioned
Correct answer: c) exponential
21. The Worst case occur in linear search algorithm when
a) Item is somewhere in the middle of the array
b) Item is not in the array at all
c) Item is the last element in the array
d) Item is the last element in the array or is not there at all
Correct answer: d) Item is the last element in the array or is not there at all
Unit 2:
1. If the elements “A”, “B”, “C” and “D” are placed in a queue and are deleted one at a time,
in what order will they be removed?
a) ABCD
b) DCBA
c) DCAB
d) ABDC
Correct answer: a) ABCD
2. A normal queue, if implemented using an array of size MAX_SIZE, gets full when?
a) Rear = MAX_SIZE – 1
b) Front = (rear + 1)mod MAX_SIZE
c) Front = rear + 1
d) Rear = front
Correct answer: a) Rear = MAX_SIZE – 1
3. In a circular queue, how do you increment the rear end of the queue?
a) rear++
b) (rear+1) % CAPACITY
c) (rear % CAPACITY)+1
d) rear- -
Correct answer: b) (rear+1) % CAPACITY
4. What is the time complexity of enqueue operation?
a) O(logn)
b) O(nlogn)
c) O(n)
d) O(1)
Correct answer: d) O(1)
5. What is the output of the following Java code?
public class CircularQueue
{
protected static final int CAPACITY = 100;
protected int size,front,rear;
protected Object q[];
int count = 0;
public CircularQueue()
{
this(CAPACITY);
}
public CircularQueue (int n)
{
size = n;
front = 0;
rear = 0;
q = new Object[size];
}
public void enqueue(Object item)
{
if(count == size)
{
System.out.println("Queue overflow");
return;
}
else
{
q[rear] = item;
rear = (rear+1)%size;
count++;
}
}
public Object dequeue()
{
if(count == 0)
{
System.out.println("Queue underflow");
return 0;
}
else
{
Object ele = q[front];
q[front] = null;
front = (front+1)%size;
count--;
return ele;
}
}
public Object frontElement()
{
if(count == 0)
return -999;
else
{
Object high;
high = q[front];
return high;
}
}
public Object rearElement()
{
if(count == 0)
return -999;
else
{
Object low;
rear = (rear-1)%size;
low = q[rear];
rear = (rear+1)%size;
return low;
}
}
}
public class CircularQueueDemo
{
public static void main(String args[])
{
Object var;
CircularQueue myQ = new CircularQueue();
myQ.enqueue(10);
myQ.enqueue(3);
var = myQ.rearElement();
myQ.dequeue();
myQ.enqueue(6);
var = mQ.frontElement();
System.out.println(var+" "+var);
}
}
a) 3 3
b) 3 6
c) 6 6
d) 10 6
Correct answer: a) 3 3
6. What happens to the front and rear of a queue when elements are added or removed?
a) The front always points to the first element, and the rear always points to the last
element.
b) The front and rear are always equal.
c) The front and rear change positions after each ENQUEUE operation.
d) The front and rear move as elements are added or removed.
Correct answer: d) The front and rear move as elements are added or removed.
7. Given an array [10, 20, 30, 40, 50], perform the following operations on a queue using this
array: ENQUEUE(60), DEQUEUE, and ENQUEUE(70). What will be the resulting queue?
a) [30, 40, 50, 60, 70]
b) [20, 30, 40, 50, 60]
c) [10, 20, 30, 40, 50, 60, 70]
d) [70, 60, 50, 40, 30, 20, 10]
Correct answer: a) [30, 40, 50, 60, 70]
8. Which operation adds an element to the rear of a queue?
a) push()
b) enqueue()
c) addFirst()
d) insert()
Correct answer: b) enqueue()
9. When does a queue underflow occur?
a) When trying to add an element to a full queue
b) When trying to remove an element from an empty queue
c) When the queue has a circular structure
d) When the queue has a priority order
Correct answer: b) When trying to remove an element from an empty queue
10. What is the primary drawback of using an array-based queue?
a) Limited capacity
b) Slow insertion operation
c) High memory usage
d) Inefficient removal of elements
Correct answer: a) Limited capacity
11. Given a singly-linked linked list with 30 nodes, which insertion and deletion approach can
be applied to use it as a queue?
a) Insertion at HEAD, Deletion at HEAD
b) Insertion at TAIL, Deletion at TAIL
c) Insertion at HEAD, Deletion at TAIL
d) Insertion from the middle and deletion from the middle of the list
Correct answer: c) Insertion at HEAD, Deletion at TAIL
12. What is the basic difference between a stack and a queue?
a) Queue allows insertion and deletion on the same ends of the list, while stack
allows insertion and deletion on different ends.
b) Queue allows insertion from one end and deletion from any of the ends, while
stack allows deletion from one end and insertion from any end.
c) Queue allows insertion and deletion on different ends of the list, while stack
allows insertion and deletion on the same end.
d) None of the above.
Correct answer: c) Queue allows insertion and deletion on different ends of the
list, while stack allows insertion and deletion on the same end.
13. In a singly linked list that maintains a HEAD and a TAIL, what is the time complexity for
performing the DEQUEUE operation at the TAIL in a queue of size "n" implemented with this
linked list?
a) O(log n)
b) O(n)
c) O(1)
d) O(n^2)
Correct answer: b) O(n)
Unit 3:
1. What is the primary difference between a Hashtable and a HashMap in Java?
a) Hashtable allows null keys and values, whereas HashMap does not.
b) Hashtable is synchronized, while HashMap is not.
c) Hashtable allows duplicate keys, whereas HashMap does not.
d) Hashtable allows for faster key lookups compared to HashMap.
Correct Answer: b) Hashtable is synchronized, while HashMap is not.
2. In a HashMap, if two different keys have the same hash code and are stored in the same
bucket, what data structure is used to handle collisions?
a) Linked List
b) Array
c) Binary Search Tree
d) Stack
Correct Answer: a) Linked List
3. What happens when you attempt to insert a duplicate key into a HashMap?
a) The new value overwrites the old value associated with the same key.
b) The HashMap throws an exception.
c) Both values are stored, and you can retrieve them using different methods.
d) The old value is deleted, and the new value is inserted.
Correct Answer: a) The new value overwrites the old value associated with the
same key.
4. What is the time complexity of retrieving a value by its key from a HashMap (average
case)?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
Correct Answer: a) O(1)
5. Which of the following methods in the HashMap class is used to check if a key is present
in the map?
a) containsKey()
b) containsValue()
c) keySet()
d) getValue()
Correct Answer: a) containsKey()
6. What happens to the load factor of a HashMap when you add more elements to it?
a) The load factor decreases.
b) The load factor increases.
c) The load factor remains constant.
d) The load factor becomes irrelevant.
Correct Answer: b) The load factor increases.
7. In Java, which class should you use for a synchronized version of a HashMap?
a) ConcurrentHashMap
b) SynchronizedHashMap
c) SyncHashMap
d) SafeHashMap
Correct Answer: a) ConcurrentHashMap
8. What is the primary drawback of using a Hashtable over a HashMap?
a) Hashtable does not allow null values.
b) Hashtable is slower due to synchronization.
c) Hashtable uses more memory.
d) Hashtable has a smaller initial capacity.
Correct Answer: b) Hashtable is slower due to synchronization.
9. When is it advisable to use a ConcurrentHashMap instead of a synchronized Hashtable?
a) When you need higher insertion performance.
b) When you need to ensure thread safety without synchronization overhead.
c) When you have a small number of threads accessing the map.
d) When you need to allow null keys and values.
Correct Answer: a) When you need higher insertion performance.
10. Which method is used to remove a key-value pair from a HashMap by specifying the
key?
a) removeValue()
b) delete()
c) remove()
d) discard()
Correct Answer: c) remove()
11. What is the default initial capacity of a HashMap in Java?
a) 10
b) 16
c) 32
d) 64
Correct Answer: b) 16
12. What is the significance of the "capacity" and "load factor" parameters when creating a
HashMap?
a) Capacity determines the maximum number of elements the map can hold.
b) Load factor determines when the map will be resized.
c) Capacity is the initial number of buckets, and load factor is the maximum allowed
fill ratio.
d) Capacity is the number of elements, and load factor is the number of buckets.
Correct Answer: c) Capacity is the initial number of buckets, and load factor is
the maximum allowed fill ratio.
13. In a HashMap, what happens when two keys have the same hash code and are stored
in the same bucket?
a) The older key-value pair is replaced by the newer one.
b) Both key-value pairs are stored in the same bucket.
c) A collision exception is thrown.
d) The HashMap automatically resizes to accommodate both key-value pairs.
Correct Answer: b) Both key-value pairs are stored in the same bucket.
14. Which Java interface is commonly used to iterate over the keys of a HashMap?
a) Iterable
b) Enumeration
c) Set
d) Map.Entry
Correct Answer: c) Set
15. What is the time complexity of removing a key-value pair from a HashMap?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
Correct Answer: a) O(1)
