Priority Queue

Uncategorized

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Priority Queue”.

1. Which of the following is not an application of priority queue?
A) Huffman codes
B) Interrupt handling in operating system
C) Undo operation in text editors
D) Bayesian spam filter

Answer: C
Explanation: A stack is used to perform the undo process.

2. What is the time complexity to insert a node based on key in a priority queue?
A) O(nlogn)
B) O(logn)
C) O(n)
D) O(n2)

Answer: C
Explanation: In the worst-case scenario, you could have to go through the entire list.

3. What is not a disadvantage of priority scheduling in operating systems?
A) A low priority process might have to wait indefinitely for the CPU
B) If the system crashes, the low priority systems may be lost permanently
C) Interrupt handling
D) Indefinite blocking

Answer: D
Explanation: The CPU can hold off on processing the lower priority process until the higher priority process is finished. Interrupt management is beneficial since interrupts should be given higher priority than current activities in order to be serviced and achieve the desired results.

4. What is the time complexity to insert a node based on position in a priority queue?
A) O(nlogn)
B) O(logn)
C) O(n)
D) O(n2)

Answer: C
Explanation: In the worst-case scenario, you could have to go through the entire list.

5. Which of the following is not an advantage of a priority queue?
A) Easy to implement
B) Processes with different priority can be efficiently handled
C) Applications with differing requirements
D) Easy to delete elements in any case

Answer: D
Explanation: In the worst-case scenario, the entire queue must be searched for the highest-priority element. This is going to take a little longer than normal. As a result, removing components isn’t a good idea.

6. What is the functionality of the following piece of code?

public Object delete_key() 
{
	if(count == 0)
	{
		System.out.println("Q is empty");
		System.exit(0);
	}
	else
	{
		Node cur = head.getNext();
		Node dup = cur.getNext();
		Object e = cur.getEle();
		head.setNext(dup);
		count--;
		return e;
	}
}

A) Delete the second element in the list
B) Return but not delete the second element in the list
C) Delete the first element in the list
D) Return but not delete the first element in the list

Answer: C
Explanation: A pointer is created to point to the first element in the list, and another is created to point to the second element. Pointer manipulations are performed until the first element is no longer pointed to by the other pointer, and its value is returned.

7. Select the appropriate code that inserts elements into the list based on the given key value.
(head and trail are dummy nodes to mark the end and beginning of the list, they do not contain any priority or element)
A)

public void insert_key(int key,Object item) 
{
	if(key<0)
	{
		Systerm.our.println("invalid");
		System.exit(0);
	}
	else
	{
		Node temp = new Node(key,item,null);
		if(count == 0)
		{
			head.setNext(temp);
			temp.setNext(trail);
		}
		else
		{
			Node dup = head.getNext();
			Node cur = head;
			while((key>dup.getKey()) && (dup!=trail))
			{
				dup = dup.getNext();
				cur = cur.getNext();
			}
			cur.setNext(temp);
			temp.setNext(dup);
		}
		count++;
	}
}

B)advertisement

public void insert_key(int key,Object item) 
{
	if(key<0)
	{
		Systerm.our.println("invalid");
		System.exit(0);
	}
	else
	{
		Node temp = new Node(key,item,null);
		if(count == 0)
		{
			head.setNext(temp);
			temp.setNext(trail);
		}
		else
		{
			Node dup = head.getNext();
			Node cur = dup;
			while((key>dup.getKey()) && (dup!=trail))
			{
				dup = dup.getNext();
				cur = cur.getNext();
			}
			cur.setNext(temp);
			temp.setNext(dup);
		}
		count++;
	}
}

C)

public void insert_key(int key,Object item) 
{
	if(key<0)
	{
		Systerm.our.println("invalid");
		System.exit(0);
	}
	else
	{
		Node temp = new Node(key,item,null);
		if(count == 0)
		{
			head.setNext(temp);
			temp.setNext(trail);
		}
		else
		{
			Node dup = head.getNext();
			Node cur = head;
			while((key>dup.getKey()) && (dup!=trail))
			{
				dup = dup.getNext();
				cur = cur.getNext();
			}
			cur.setNext(dup);
			temp.setNext(cur);
		}
		count++;
	}
}

D)

public void insert_key(int key,Object item) 
{
	if(key<0)
	{
		Systerm.our.println("invalid");
		System.exit(0);
	}
	else
	{
		Node temp = new Node(key,item,null);
		if(count == 0)
		{
			head.setNext(temp);
			temp.setNext(trail);
		}
		else
		{
			Node dup = head.getNext();
			Node cur = head;
			while((key>dup.getKey()) && (dup!=trail))
			{
				dup = cur
				cur = cur.getNext();
			}
			cur.setNext(dup);
			temp.setNext(cur);
		}
		count++;
	}
}

Answer: A
Explanation: ‘dup’ and ‘cur’ are two temporary pointers, with ‘cur’ trailing behind ‘dup’. Traverse the list until the given key is greater than a lesser-keyed part, then place the new node ‘temp’ in that location.

8. With what data structure can a priority queue be implemented?
A) Array
B) List
C) Heap
D) Tree

Answer: D
Explanation: An array, a list, a binary search tree, or a heap may be used to enforce a priority queue, with the heap being the most effective.

A priority queue is an abstract data form in computer science that is similar to a standard queue or stack data structure, except each element has a “priority” associated with it. A high-priority element is served before a low-priority element in a priority queue. When two elements with the same priority are served in some implementations, they are served in the order in which they were enqueued, while in other implementations, the ordering of elements with the same priority is unclear. Priority queues are often introduced with heaps, but they are conceptually different.

Leave a Reply

Your email address will not be published. Required fields are marked *