Category: Data Structure Objective Questions

Data Structure Multiple Choice Questions on “Directed Acyclic Graph”.

1. Every Directed Acyclic Graph has at least one sink vertex.
a) True
b) False
Answer: a
Clarification: A sink vertex is a vertex which has an outgoing degree of zero.

2. Which of the following is not a topological sorting of the given graph?

a) A B C D E F
b) A B F E D C
c) A B E C F D
d) A B C D F E
Answer: d
Clarification: Topological sorting is a linear arrangement of vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. In A B C D F E, F comes before E in ordering.

3. With V(greater than 1) vertices, how many edges at most can a Directed Acyclic Graph possess?
a) (V*(V-1))/2
b) (V*(V+1))/2
c) (V+1)C2
d) (V-1)C2
Answer: a
Clarification: The first edge would have an outgoing degree of atmost V-1, the next edge would have V-2 and so on, hence V-1 + V-2…. +1 equals (V*(V-1))/2.

4. The topological sorting of any DAG can be done in ________ time.
a) cubic
b) quadratic
c) linear
d) logarithmic
Answer: c
Clarification: Topological sorting can be done in O(V+E), here V and E represents number of vertices and number of edges respectively.

5. If there are more than 1 topological sorting of a DAG is possible, which of the following is true.
a) Many Hamiltonian paths are possible
b) No Hamiltonian path is possible
c) Exactly 1 Hamiltonian path is possible
d) Given information is insufficient to comment anything
Answer: b
Clarification: For a Hamiltonian path to exist all the vertices must be connected with a path, had that happened there would have been a unique topological sort.

6. What sequence would the BFS traversal of the given graph yield?

a) A F D B C E
b) C B A F E D
c) A B D C E F
d) E F D C B A
Answer: c
Clarification: In BFS nodes gets explored and then the neighbors of the current node gets explored, before moving on to the next levels.

7. What would be the output of the following C++ program if the given input is

0 0 0 1 1
0 0 0 0 1
0 0 0 1 0
1 0 1 0 0
1 1 0 0 0
 
#include 
using namespace std;
bool visited[5];
int G[5][5];
 
void fun(int i)
{
	cout<<i<<" ";
	visited[i]=true;
	for(int j=0;j<5;j++)
		if(!visited[j]&&G[i][j]==1)
			fun(j);
}
 
int main()
{   
	for(int i=0;i<5;i++)
		for(int j=0;j<5;j++)
			cin>>G[i][j];
 
	for(int i=0;i<5;i++)
		visited[i]=0;
 
	fun(0);
		return 0;
}

a) 0 2 3 1 4
b) 0 3 2 4 1
c) 0 2 3 4 1
d) 0 3 2 1 4
Answer: b
Clarification: Given Input is the adjacency matrix of a graph G, whereas the function ‘fun’ prints the DFS traversal.

8. Which of the given statement is true?
a) All the Cyclic Directed Graphs have topological sortings
b) All the Acyclic Directed Graphs have topological sortings
c) All Directed Graphs have topological sortings
d) All the cyclic directed graphs hace non topological sortings
Answer: d
Clarification: Cyclic Directed Graphs cannot be sorted topologically.

9. For any two different vertices u and v of an Acyclic Directed Graph if v is reachable from u, u is also reachable from v?
a) True
b) False
Answer: b
Clarification: If such vertices exists it means that the graph contains a cycle which contradicts the first part of the statement.

10. What is the value of the sum of the minimum in-degree and maximum out-degree of an Directed Acyclic Graph?
a) Depends on a Graph
b) Will always be zero
c) Will always be greater than zero
d) May be zero or greater than zero
Answer: b
Clarification: Every Directed Acyclic Graph has a source and a sink vertex.

Data Structure Multiple Choice Questions on “Array and Array Operations”.

1. Which of these best describes an array?
a) A data structure that shows a hierarchical behavior
b) Container of objects of similar types
c) Arrays are immutable once initialised
d) Array is not a data structure
Answer: b
Clarification: Array contains elements only of the same type.

2. How do you initialize an array in C?
a) int arr[3] = (1,2,3);
b) int arr(3) = {1,2,3};
c) int arr[3] = {1,2,3};
d) int arr(3) = (1,2,3);
Answer: c
Clarification: This is the syntax to initialize an array in C.

3. How do you instantiate an array in Java?
a) int arr[] = new int(3);
b) int arr[];
c) int arr[] = new int[3];
d) int arr() = new int(3);
Answer: c
Clarification: Note that int arr[]; is declaration whereas int arr[] = new int[3]; is to instantiate an array.

4. Which of the following is the correct way to declare a multidimensional array in Java?
a) int[] arr;
b) int arr[[]];
c) int[][]arr;
d) int[[]] arr;
Answer: c
Clarification: The syntax to declare multidimensional array in java is either int[][] arr; or int arr[][];

5. What is the output of the following Java code?

public class array
{
	public static void main(String args[])
	{
		int []arr = {1,2,3,4,5};
		System.out.println(arr[2]);
		System.out.println(arr[4]);
	}
}

a) 3 and 5
b) 5 and 3
c) 2 and 4
d) 4 and 2
Answer: a
Clarification: Array indexing starts from 0.

6. What is the output of the following Java code?

public class array
{
	public static void main(String args[])
	{
		int []arr = {1,2,3,4,5};
		System.out.println(arr[5]);
	}
}

a) 4
b) 5
c) ArrayIndexOutOfBoundsException
d) InavlidInputException
Answer: c
Clarification: Trying to access an element beyond the limits of an array gives ArrayIndexOutOfBoundsException.

7. When does the ArrayIndexOutOfBoundsException occur?
a) Compile-time
b) Run-time
c) Not an error
d) Not an exception at all
Answer: b
Clarification: ArrayIndexOutOfBoundsException is a run-time exception and the compilation is error-free.

8. Which of the following concepts make extensive use of arrays?
a) Binary trees
b) Scheduling of processes
c) Caching
d) Spatial locality
Answer: d
Clarification: Whenever a particular memory location is referred to, it is likely that the locations nearby are also referred, arrays are stored as contiguous blocks in memory, so if you want to access array elements, spatial locality makes it to access quickly.

9. What are the advantages of arrays?
a) Objects of mixed data types can be stored
b) Elements in an array cannot be sorted
c) Index of first element of an array is 1
d) Easier to store elements of same data type
Answer: d
Clarification: Arrays store elements of the same data type and present in continuous memory locations.

10. What are the disadvantages of arrays?
a) Data structure like queue or stack cannot be implemented
b) There are chances of wastage of memory space if elements inserted in an array are lesser than the allocated size
c) Index value of an array can be negative
d) Elements are sequentially accessed
Answer: b
Clarification: Arrays are of fixed size. If we insert elements less than the allocated size, unoccupied positions can’t be used again. Wastage will occur in memory.

11. Assuming int is of 4bytes, what is the size of int arr[15];?
a) 15
b) 19
c) 11
d) 60
Answer: d
Clarification: Since there are 15 int elements and each int is of 4bytes, we get 15*4 = 60bytes.

12. In general, the index of the first element in an array is __________
a) 0
b) -1
c) 2
d) 1
Answer: a
Clarification: In general, Array Indexing starts from 0. Thus, the index of the first element in an array is 0.

13. Elements in an array are accessed _____________
a) randomly
b) sequentially
c) exponentially
d) logarithmically
Answer: a
Clarification: Elements in an array are accessed randomly. In Linked lists, elements are accessed sequentially.

Data Structure Multiple Choice Questions on “Double Ended Queue (Dequeue)”.

1. What is a dequeue?
a) A queue with insert/delete defined for both front and rear ends of the queue
b) A queue implemented with a doubly linked list
c) A queue implemented with both singly and doubly linked lists
d) A queue with insert/delete defined for front side of the queue
Answer: a
Clarification: A dequeue or a double ended queue is a queue with insert/delete defined for both front and rear ends of the queue.

2. Select the function which performs insertion at the front end of the dequeue?
a)

public void function(Object item)
{
	Node temp = new Node(item,null);
	if(isEmpty())
	{
		temp.setNext(trail);
		head.setNext(temp);
	}
	else
	{
		Node cur = head.getNext();
		temp.setNext(cur);
		head.setNext(temp);
	}
	size++;
}

b)

public void function(Object item)
{
	Node temp = new Node(item,null);
	if(isEmpty())
	{
		temp.setNext(trail);
		head.setNext(trail);
	}
	else
	{
		Node cur = head.getNext();
		temp.setNext(cur);
		head.setNext(temp);
	}
	size++;
}

c)

public void function(Object item)
{
	Node temp = new Node(item,null);
	if(isEmpty())
	{
		Node cur = head.getNext();
		temp.setNext(cur);
		head.setNext(temp);
	}
	else
	{
		temp.setNext(trail);
		head.setNext(temp);
	}
	size++;
}

d)

public void function(Object item)
{
	Node temp = new Node(item,null);
	if(isEmpty())
	{
		Node cur = head.getNext();
		temp.setNext(cur);
		cur.setNext(temp);
	}
	else
	{
		head.setNext(trail);
		trail.setNext(temp);
	}
	size++;
}

View Answer

Answer: a
Clarification: Create a new node, if the current list is empty, the ‘head’ points to this node and this new node points to ‘trail’. Otherwise, ‘head’ points to the new node and this in turn points to the current first element(head.getNext()).

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

public void function(Object item)
{
	Node temp=new Node(item,trail);
	if(isEmpty())
	{
		head.setNext(temp);
		temp.setNext(trail);
	}
	else
	{
		Node cur=head.getNext();
		while(cur.getNext()!=trail)
		{
			cur=cur.getNext();
		}
		cur.setNext(temp);
	}
	size++;
}

a) Insert at the front end of the dequeue
b) Insert at the rear end of the dequeue
c) Fetch the element at the rear end of the dequeue
d) Fetch the element at the front end of the dequeue
Answer: b
Clarification: If the list is empty, this new node will point to ‘trail’ and will be pointed at by ‘head’. Otherwise, traverse till the end of the list and insert the new node there.

4. What are the applications of dequeue?
a) A-Steal job scheduling algorithm
b) Can be used as both stack and queue
c) To find the maximum of all sub arrays of size k
d) To avoid collision in hash tables
Answer: d
Clarification: All of the mentioned can be implemented with a dequeue.

5. Which of the following can be used to delete an element from the front end of the queue?
a)

public Object deleteFront() throws emptyDEQException
{
	if(isEmpty())
		throw new emptyDEQException("Empty");
	else
	{
		Node temp = head.getNext();
		Node cur = temp;
		Object e = temp.getEle();
		head.setNext(cur);
		size--;
		return e;
	}
}

b)

public Object deleteFront() throws emptyDEQException
{
	if(isEmpty())
		throw new emptyDEQException("Empty");
	else
	{
		Node temp = head.getNext();
		Node cur = temp.getNext();
		Object e = temp.getEle();
		head.setNext(cur);
		size--;
		return e;
	}
}

c)

public Object deleteFront() throws emptyDEQException
{
	if(isEmpty())
		throw new emptyDEQException("Empty");
	else
	{
		Node temp = head.getNext();
		Node cur = temp.getNext();
		Object e = temp.getEle();
		head.setNext(temp);
		size--;
		return e;
	}
}

d)

public Object deleteFront() throws emptyDEQException
{
	if(isEmpty())
		throw new emptyDEQException("Empty");
	else
	{
		Node temp = head.getNext();
		Node cur = temp.getNext();
		Object e = temp.getEle();
		temp.setNext(cur);
		size--;
		return e;
	}
}

View Answer

Answer: b
Clarification: Have two pointers, one(temp) pointing to the first element and the other(cur) pointing to the second element. Make the ‘head’ point to the second element, this removes all reference for ‘temp’.

 
 
6. Which of the following can be used to delete an element from the rear end of the queue?
a)

public Object deleteRear() throws emptyDEQException
{
	if(isEmpty())
		throw new emptyDEQException("Empty");
	else
	{
		Node temp = head.getNext();
		Node cur = temp;
		while(temp.getNext() != trail)
		{
			temp = temp.getNext();
			cur = cur.getNext();
		}
		Object e = temp.getEle();
		cur.setNext(trail);
		size--;
		return e;
	}
}

b)

public Object deleteRear() throws emptyDEQException
{
	if(isEmpty())
		throw new emptyDEQException("Empty");
	else
	{
		Node temp = head.getNext();
		Node cur = head;
		while(temp != trail)
		{
			temp = temp.getNext();
			cur = cur.getNext();
		}
		Object e = temp.getEle();
		cur.setNext(trail);
		size--;
		return e;
	}
}

c)

public Object deleteRear() throws emptyDEQException
{
	if(isEmpty())
	throw new emptyDEQException("Empty");
	else
	{
		Node temp = head.getNext();
		Node cur = head;
		while(temp.getNext()!=trail)
		{
			temp = temp.getNext();
			cur = cur.getNext();
		}
		Object e = temp.getEle();
		cur.setNext(trail);
		size--;
		return e;
	}
}

d)

public Object deleteRear() throws emptyDEQException
{
	if(isEmpty())
	throw new emptyDEQException("Empty");
	else
	{
		Node temp = head.getNext();
		Node cur = head;
		while(temp.getNext()!=trail)
		{
			temp = temp.getNext();
			cur = cur.getNext();
		}
		Object e = temp.getEle();
		temp.setNext(trail);
		size--;
		return e;
	}
}

View Answer

Answer: c
Clarification: Traverse till the end of the list with a pointer ‘temp’ and another ‘cur’ which is trailing behind temp, make ‘cur’ point to trail, this removes all reference for ‘temp’.

 
 
7. What is the time complexity of deleting from the rear end of the dequeue implemented with a singly linked list?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n²)
View Answer

Answer: c
Clarification: Since a singly linked list is used, first you have to traverse till the end, so the complexity is O(n).

8. After performing these set of operations, what does the final list look contain?

InsertFront(10);
InsertFront(20);
InsertRear(30);
DeleteFront();
InsertRear(40);
InsertRear(10);
DeleteRear();
InsertRear(15);
display();

a) 10 30 10 15
b) 20 30 40 15
c) 20 30 40 10
d) 10 30 40 15
Answer: d
Clarification: A careful tracing of the given operation yields the result.
10
20 10
20 10 30
10 30
10 30 40
10 30 40 10
10 30 40
10 30 40 15

Data Structure Multiple Choice Questions on “Parallel Array”.

1. What are parallel arrays?
a) Arrays of the same size
b) Arrays allocated one after the other
c) Arrays of the same number of elements
d) Arrays allocated dynamically
Answer: c
Clarification: Different arrays can be of different data types but should contain same number of elements. Elements at corresponding index belong to a record.

2. Which of the following can be called a parallel array implementation?
a)

   firstName  = ['Joe','Bob','Frank','Hans']
   lastName   = ['Smith','Seger','Sinatra','Schultze']
   heightInCM = [169,158,201,199]
 
   for i in xrange(len(firstName)):
       print "Name:",firstName[i], lastName[i]
       print "Height in CM:,",heightInCM[i]

b)

   firstName  = ['Joe','Bob','Frank','Hans']
   lastName   = ['Smith','Seger']
   heightInCM = [169,158]
 
   for i in xrange(len(firstName)):
       print "Name:",firstName[i], lastName[i]
       print "Height in CM:,",heightInCM[i]

c)

   firstName  = ['Joe','Bob']
   lastName   = ['Smith','Seger','Sinatra','Schultze']
   heightInCM = [169,158]
 
   for i in xrange(len(firstName)):
       print "Name:",firstName[i], lastName[i]
       print "Height in CM:,",heightInCM[i]

d)

   firstName  = ['Joe','Bob']
   lastName   = ['Smith','Seger' ,'Schultze']
   heightInCM = [169,158]
 
   for i in xrange(len(firstName)):
       print "Name:",firstName[i], lastName[i]
       print "Height in CM:,",heightInCM[i]

View Answer

Answer: a
Clarification: All the arrays must have equal length, that is, contain same number of elements.

3. Which of the following is a disadvantage of parallel array over the traditional arrays?
a) When a language does not support records, parallel arrays can be used
b) Increased locality of reference
c) Ideal cache behaviour
d) Insertion and Deletion becomes tedious
Answer: d
Clarification: Insertion and deletion of elements require to move every element from their initial positions. This will become tedious. For Record collection, locality of reference and Ideal Cache behaviour we can use parallel arrays.

4. Which of the following is an advantage of parallel arrays?
a) Poor locality of reference for non-sequential access
b) Very little direct language support
c) Expensive to shrink or grow
d) Increased Locality of Reference
Answer: d
Clarification: Elements in the parallel array are accessed sequentially as one arrays holds the keys whereas other holds the values. This sequential access generally improves Locality of Reference. It is an advantage.

5. What is a sorted array?
a) Arrays sorted in numerical order
b) Arrays sorted in alphabetical order
c) Elements of the array are placed at equally spaced addresses in the memory
d) All of the mentioned
Answer: d
Clarification: The array can be sorted in any way, numerical, alphabetical or any other way but the elements are placed at equally spaced addresses.

6. To search for an element in a sorted array, which searching technique can be used?
a) Linear Search
b) Jump Search
c) Binary Search
d) Fibonacci Search
Answer: c
Clarification: Since the array is sorted, binary search is preferred as its time complexity is O(logn).

7. Which of the following is not an application of sorted array?
a) Commercial computing
b) Priority Scheduling
c) Discrete Mathematics
d) Hash Tables
Answer: d
Clarification: Sorted arrays have widespread applications as all commercial computing involves large data which is very useful if it is sorted. It makes best use of locality of reference and data cache. Linked lists are used in Hash Tables not arrays.

8. What is the worst case time complexity of inserting an element into the sorted array?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n²)
Answer: c
Clarification: In the worst case, an element must added to the front of the array, which means that rest of the elements have to be shifted, hence the worst case time complexity becomes O(n).

Data Structure Multiple Choice Questions on “Threaded Binary Tree”.

1. What is a threaded binary tree traversal?
a) a binary tree traversal using stacks
b) a binary tree traversal using queues
c) a binary tree traversal using stacks and queues
d) a binary tree traversal without using stacks and queues
Answer: d
Clarification: This type of tree traversal will not use stack or queue.

2. What are the disadvantages of normal binary tree traversals?
a) there are many pointers which are null and thus useless
b) there is no traversal which is efficient
c) complexity in implementing
d) improper traversals
Answer: a
Clarification: As there are majority of pointers with null value going wasted we use threaded binary trees.

3. In general, the node content in a threaded binary tree is ________
a) leftchild_pointer, left_tag, data, right_tag, rightchild_pointer
b) leftchild_pointer, left_tag
c) leftchild_pointer, left_tag, right_tag, rightchild_pointer
d) leftchild_pointer, left_tag, data
Answer: a
Clarification: It contains additional 2 pointers over normal binary tree node structure.

4. What are null nodes filled with in a threaded binary tree?
a) inorder predecessor for left node and inorder successor for right node information
b) right node with inorder predecessor and left node with inorder successor information
c) they remain null
d) some other values randomly
Answer: a
Clarification: If preorder or postorder is used then the respective predecessor and successor info is stored.

5. Which of the following tree traversals work if the null left pointer pointing to the predecessor and null right pointer pointing to the successor in a binary tree?
a) inorder, postorder, preorder traversals
b) inorder
c) postorder
d) preorder
Answer: a
Clarification: In threaded binary trees, the null left pointer points to the predecessor and the right null pointer point to the successor. In threaded binary trees, we can use in-order, preorder and postorder traversals to visit every node in the tree.

6. What are double and single threaded trees?
a) when both left, right nodes are having null pointers and only right node is null pointer respectively
b) having 2 and 1 node
c) using single and double linked lists
d) using heaps and priority queues
Answer: a
Clarification: They are properties of double and single threaded binary trees respectively.

7. What is wrong with below code for inorder traversal of inorder threaded binary tree:

   inordertraversal(threadedtreenode root):
   threadedtreenode q = inorderpredecessor(root)
   while(q!=root):
   q=inorderpredecessor(q)
   print q.data

a) inordersuccessor instead of inorderpredecessor must be done
b) code is correct
c) it is code for post order
d) it is code for pre order
Answer: a
Clarification: Property of inorder threaded binary tree is left node with inorder predecessor and right node with inorder successor information are stored.

8. What is inefficient with the below threaded binary tree picture?

a) it has dangling pointers
b) nothing inefficient
c) incorrect threaded tree
d) space is being used more
Answer: a
Clarification: The nodes extreme left and right are pointing to nothing which could be also used efficiently.