Data Structure Questions and Answers – Priority Queue

«
»

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

1. With what data structure can a priority queue be implemented?
a) Array
b) List
c) Heap
d) Tree
View Answer

Answer: d
Explanation: Priority queue can be implemented using an array, a list, a binary search tree or a heap, although the most efficient one being the heap.
advertisement

2. 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
View Answer

Answer: c
Explanation: Undo operation is achieved using a stack.

3. 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++;
	}
}
View Answer
Answer: a
Explanation: Have two temporary pointers ‘dup’ and ‘cur’ with ‘cur’ trailing behind ‘dup’. Traverse through the list until the given key is greater than some element with a lesser key, insert the new node ‘temp’ in that position.
 
 

4. 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)
View Answer

Answer: c
Explanation: In the worst case, you might have to traverse the entire list.
advertisement

5. 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
View Answer

Answer: c
Explanation: A pointer is made to point at the first element in the list and one more to point to the second element, pointer manipulations are done such that the first element is no longer being pointed by any other pointer, its value is returned.

6. 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
View Answer

Answer: c
Explanation: The lower priority process should wait until the CPU completes the processing higher priority process. Interrupt handling is an advantage as interrupts should be given more priority than tasks at hand so that interrupt can be serviced to produce desired results.
advertisement

7. Which of the following is not an advantage of 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
View Answer

Answer: d
Explanation: In worst case, the entire queue has to be searched for the element having highest priority. This will take more time than usual. So deletion of elements is not an advantage.

8. 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)
View Answer

Answer: c
Explanation: In the worst case, you might have to traverse the entire list.

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn