Category: Data Structure Objective Questions

Data Structure Multiple Choice Questions on “Queue using Linked List”.

1. In linked list implementation of queue, if only front pointer is maintained, which of the following operation take worst case linear time?
a) Insertion
b) Deletion
c) To empty a queue
d) Both Insertion and To empty a queue
Answer: d
Clarification: Since front pointer is used for deletion, so worst time for the other two cases.

2. In linked list implementation of a queue, where does a new element be inserted?
a) At the head of link list
b) At the centre position in the link list
c) At the tail of the link list
d) At any position in the linked list
Answer: c
Clarification: Since queue follows FIFO so new element inserted at last.

3. In linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will change during an insertion into a NONEMPTY queue?
a) Only front pointer
b) Only rear pointer
c) Both front and rear pointer
d) No pointer will be changed
Answer: b
Clarification: Since queue follows FIFO so new element inserted at last.

4. In linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will change during an insertion into EMPTY queue?
a) Only front pointer
b) Only rear pointer
c) Both front and rear pointer
d) No pointer will be changed
Answer: c
Clarification: Since its the starting of queue, so both values are changed.

5. In case of insertion into a linked queue, a node borrowed from the __________ list is inserted in the queue.
a) AVAIL
b) FRONT
c) REAR
d) NULL
Answer: a
Clarification: All the nodes are collected in AVAIL list.

6. In linked list implementation of a queue, from where is the item deleted?
a) At the head of link list
b) At the centre position in the link list
c) At the tail of the link list
d) Node before the tail
Answer: a
Clarification: Since queue follows FIFO so new element deleted from first.

7. In linked list implementation of a queue, the important condition for a queue to be empty is?
a) FRONT is null
b) REAR is null
c) LINK is empty
d) FRONT==REAR-1
Answer: a
Clarification: Because front represents the deleted nodes.

8. The essential condition which is checked before insertion in a linked queue is?
a) Underflow
b) Overflow
c) Front value
d) Rear value
Answer: b
Clarification: To check whether there is space in the queue or not.

9. The essential condition which is checked before deletion in a linked queue is?
a) Underflow
b) Overflow
c) Front value
d) Rear value
Answer: a
Clarification: To check whether there is element in the list or not.

10. Which of the following is true about linked list implementation of queue?
a) In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end
b) In push operation, if new nodes are inserted at the beginning, then in pop operation, nodes must be removed from the beginning
c) In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from end
d) In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from beginning
Answer: a
Clarification: It can be done by both the methods.

Data Structure Multiple Choice Questions on “Bit Array”.

1. What is a bit array?
a) Data structure for representing arrays of records
b) Data structure that compactly stores bits
c) An array in which most of the elements have the same value
d) Array in which elements are not present in continuous locations
Answer: b
Clarification: It compactly stores bits and exploits bit-level parallelism.

2. Which of the following bitwise operations will you use to set a particular bit to 1?
a) OR
b) AND
c) XOR
d) NOR
Answer: a
Clarification: 1 OR 1 = 1, 0 OR 1 = 1, any bit OR’ed with 1 gives 1.

3. Which of the following bitwise operations will you use to set a particular bit to 0?
a) OR
b) AND
c) XOR
d) NAND
Answer: b
Clarification: 1 AND 0 = 0, 0 AND 0 = 0, any bit AND with 0 gives 0.

4. Which of the following bitwise operations will you use to toggle a particular bit?
a) OR
b) AND
c) XOR
d) NOT
Answer: c
Clarification: 1 XOR 1 = 0, 0 XOR 1 = 1, note that NOT inverts all the bits, while XOR toggles only a specified bit.

5. Which of the following is not an advantage of bit array?
a) Exploit bit level parallelism
b) Maximal use of data cache
c) Can be stored and manipulated in the register set for long periods of time
d) Accessing Individual Elements is easy
Answer: d
Clarification: Individual Elements are difficult to access and can’t be accessed in some programming languages. If random access is more common than sequential access, they have to be compressed to byte/word array. Exploit Bit parallelism, Maximal use of data cache and storage and manipulation for longer time in register set are all advantages of bit array.

6. Which of the following is not a disadvantage of bit array?
a) Without compression, they might become sparse
b) Accessing individual bits is expensive
c) Compressing bit array to byte/word array, the machine also has to support byte/word addressing
d) Storing and Manipulating in the register set for long periods of time
Answer: d
Clarification: Bit arrays allow small arrays of bits to be stored and manipulated in the register set for long periods of time with no memory accesses because of their ability to exploit bit-level parallelism, limit memory access, and maximally use the data cache, they often outperform many other data structures on practical data sets. This is an advantage of bit array. The rest are all disadvantages of bit array.

7. Which of the following is/are not applications of bit arrays?
a) Used by the Linux kernel
b) For the allocation of memory pages
c) Bloom filter
d) Implementation of Vectors and Matrices
Answer: d
Clarification: Normal Arrays are used to implement vectors and matrices. Bit arrays have no prominent role. Remaining all are applications of Bit Arrays.

8. Which class in Java can be used to represent bit array?
a) BitSet
b) BitVector
c) BitArray
d) BitStream
Answer: a
Clarification: The BitSet class creates a special type of array that can hold bit values.

9. Which of the following bitwise operator will you use to invert all the bits in a bit array?
a) OR
b) NOT
c) XOR
d) NAND
Answer: b
Clarification: NOT operation is used to invert all the bits stored in a bit array.
Eg: NOT (10110010) = 01001101.

10. Run-Length encoding is used to compress data in bit arrays.
a) True
b) False
Answer: a
Clarification: A bit array stores the combinations of bit 0 and bit 1. Each bit in the bit array is independent. Run Length encoding is a data compression technique in which data are stored as single value and number of times that value repeated in the data. This compression reduces the space complexity in arrays. Bit arrays without compression require more space. Thus, we will use Run-Length encoding in most of the cases to compress data in bit arrays.

11. What does Hamming weight/population count mean in Bit arrays?
a) Finding the number of 1 bit in a bit array
b) Finding the number of 0 bit in a bit array
c) Finding the sum of bits in a bit array
d) Finding the average number of 1’s and 0’s in bit arrays
Answer: a
Clarification: Hamming/ population count involves finding the number of 1’s in the bit array. Population count is used in data compression.

12. Bit fields and Bit arrays are same.
a) True
b) False
Answer: b
Clarification: Bit field contains the number of adjacent computer locations used to store the sequence of bits to address a bit or groups of bits. Bit array is an array that stores combinations of bit 0 and bit 1. Thus, bit fields and Bit arrays are different.

13. Which one of the following operations returns the first occurrence of bit 1 in bit arrays?
a) Find First Zero
b) Find First One
c) Counting lead Zeroes
d) Counting lead One
Answer: b
Clarification: Find First One operation returns the first occurrence of bit 1 in the bit array. Find First Zero operation returns the first occurrence of bit 0 in the bit array. If the most significant bit in bit array is 1, then count lead zeroes operation returns the number of zeroes present before the most significant bit. If the most significant bit in bit array is 0, then the count lead one returns the number of ones present before the most significant bit.

Data Structure Multiple Choice Questions on “Binary Trees using Linked Lists”.

1. Advantages of linked list representation of binary trees over arrays?
a) dynamic size
b) ease of insertion/deletion
c) ease in randomly accessing a node
d) both dynamic size and ease in insertion/deletion
Answer: d
Clarification: It has both dynamic size and ease in insertion and deletion as advantages.

2. Disadvantages of linked list representation of binary trees over arrays?
a) Randomly accessing is not possible
b) Extra memory for a pointer is needed with every element in the list
c) Difficulty in deletion
d) Random access is not possible and extra memory with every element
Answer: d
Clarification: Random access is not possible with linked lists.

3. Which of the following traversing algorithm is not used to traverse in a tree?
a) Post order
b) Pre order
c) Post order
d) Randomized
Answer: d
Clarification: Generally, all nodes in a tree are visited by using preorder, inorder and postorder traversing algorithms.

4. Level order traversal of a tree is formed with the help of
a) breadth first search
b) depth first search
c) dijkstra’s algorithm
d) prims algorithm
Answer: a
Clarification: Level order is similar to bfs.

5. Identify the reason which doesn’t play a key role to use threaded binary trees?
a) The storage required by stack and queue is more
b) The pointers in most of nodes of a binary tree are NULL
c) It is Difficult to find a successor node
d) They occupy less size
Answer: d
Clarification: Threaded binary trees are introduced to make the Inorder traversal faster without using any stack or recursion. Stack and Queue require more space and pointers in the majority of binary trees are null and difficulties are raised while finding successor nodes. Size constraints are not taken on threaded binary trees, but they occupy less space than a stack/queue.

6. The following lines talks about deleting a node in a binary tree.(the tree property must not be violated after deletion)
i) from root search for the node to be deleted
ii)
iii) delete the node at
what must be statement ii) and fill up statement iii)
a) ii)-find random node,replace with node to be deleted. iii)- delete the node
b) ii)-find node to be deleted. iii)- delete the node at found location
c) ii)-find deepest node,replace with node to be deleted. iii)- delete a node
d) ii)-find deepest node,replace with node to be deleted. iii)- delete the deepest node
Answer: d
Clarification: We just replace a to be deleted node with last leaf node of a tree. this must not be done in case of BST or heaps.

7. What may be the psuedo code for finding the size of a tree?
a) find_size(root_node–>left_node) + 1 + find_size(root_node–>right_node)
b) find_size(root_node–>left_node) + find_size(root_node–>right_node)
c) find_size(root_node–>right_node) – 1
d) find_size(root_node–>left_node + 1
Answer: a
Clarification: Draw a tree and analyze the expression. we are always taking size of left subtree and right subtree and adding root value(1) to it and finally printing size.

8. What is missing in this logic of finding a path in the tree for a given sum (i.e checking whether there will be a path from roots to leaf nodes with given sum)?

checkSum(struct bin-treenode *root , int sum) :
  if(root==null)
    return sum as 0
  else :
     leftover_sum=sum-root_node-->value
     //missing

a) code for having recursive calls to either only left tree or right trees or to both subtrees depending on their existence
b) code for having recursive calls to either only left tree or right trees
c) code for having recursive calls to either only left tree
d) code for having recursive calls to either only right trees
Answer: a
Clarification: if(left subtree and right subtree) then move to both subtrees
else if only left subtree then move to left subtree carrying leftover_sum parameter
else if only right subtree then move to right subtree carrying leftover_sum parameter.

9. What must be the missing logic below so as to print mirror of a tree as below as an example?

if(rootnode):
  mirror(rootnode-->left)
  mirror(rootnode-->right)
 
  //missing
 
end

a) swapping of left and right nodes is missing
b) swapping of left with root nodes is missing
c) swapping of right with root nodes is missing
d) nothing is missing
Answer: a
Clarification: Mirror is another tree with left and right children of nodes are interchanged as shown in the figure.

10. What is the code below trying to print?

void print(tree *root,tree *node)
{
  if(root ==null) return 0
  if(root-->left==node || root-->right==node) || print(root->left,node)
  ||printf(root->right,node)
  {
     print(root->data)
  }
}

a) just printing all nodes
b) not a valid logic to do any task
c) printing ancestors of a node passed as argument
d) printing nodes from leaf node to a node passed as argument
Answer: c
Clarification: We are checking if left or right node is what the argument sent or else if not the case then move to left node or right node and print all nodes while searching for the argument node.

Data Structure Multiple Choice Questions on “Splay Tree”.

1. What are splay trees?
a) self adjusting binary search trees
b) self adjusting binary trees
c) a tree with strings
d) a tree with probability distributions
Answer: a
Clarification: Splay trees are height balanced, self adjusting BST’s.

2. Which of the following property of splay tree is correct?
a) it holds probability usage of the respective sub trees
b) any sequence of j operations starting from an empty tree with h nodes atmost, takes O(jlogh) time complexity
c) sequence of operations with h nodes can take O(logh) time complexity
d) splay trees are unstable trees
Answer: b
Clarification: This is a property of splay tree that ensures faster access. we push the most recently used nodes to top which leads to faster access to recently used values.

3. Why to prefer splay trees?
a) easier to program
b) space efficiency
c) easier to program and faster access to recently accessed items
d) quick searching
Answer: c
Clarification: Whenever you insert an element or remove or read an element that will be pushed or stored at the top which facilitates easier access or recently used stuff.

4. Is it true that splay trees have O(logn) amortized complexity ?
a) true
b) false
Answer: a
Clarification: We go with amortized time complexity when we feel that not all operations are worst and some can be efficiently done. in splay trees not all splay operations will lead to O(logn) worst case complexity.

5. What is a splay operation?
a) moving parent node to down of child
b) moving a node to root
c) moving root to leaf
d) removing leaf node
Answer: b
Clarification: Splay trees mainly work using splay operations. wheneve we insert, delete and search for a node we splay the respective nodes to root. we have zig-zag and zig-zig operations.

6. Which of the following options is an application of splay trees?
a) cache Implementation
b) networks
c) send values
d) receive values
Answer: a
Clarification: Splay trees can be used for faster access to recently accessed items and hence used for cache implementations.

7. When we have red-black trees and AVL trees that can perform most of operations in logarithmic times, then what is the need for splay trees?
a) no there is no special usage
b) In real time it is estimated that 80% access is only to 20% data, hence most used ones must be easily available
c) redblack and avl are not upto mark
d) they are just another type of self balancing binary search trees
Answer: b
Clarification: May be the stats showing 80-20% may be not accurate, but in real time that is the widely spread scenario seen. If you are into this type of situation, you must choose implementing splay trees.

8. After the insertion operation, is the resultant tree a splay tee?

a) true
b) false
Answer: a
Clarification: There is a zig-zag and right operation(zig) which gives the right hand side tree. refer splay operations for insertion in splay tree.

9. What output does the below pseudo code produces?

    Tree_node function(Tree_node x)
    {
        Tree_node y = x.left;
        x.left = y.right;
        y.right = x;
        return y;
    }

a) right rotation of subtree
b) left rotation of subtree
c) zig-zag operation
d) zig-zig operation
Answer: a
Clarification: When a right rotation is done the parent of the rotating node becomes it’s right node and it’s child becomes it’s left child.

10. What is the disadvantage of using splay trees?
a) height of a splay tree can be linear when accessing elements in non decreasing order.
b) splay operations are difficult
c) no significant disadvantage
d) splay tree performs unnecessary splay when a node is only being read
Answer: a
Clarification: This will be the case after accessing all n elements in non-decreasing order. Since the height of a tree corresponds to the worst-case access time, this means that the actual cost of an operation can be high. However the amortized access cost of this worst case is logarithmic O(log n).

Data Structures & Algorithms Multiple Choice Questions on “Expression Tree”.

1. The leaves of an expression tree always contain?
a) operators
b) operands
c) null
d) expression

Answer: b
Clarification: The leaves of an expression tree always contain the result of a given expression (i.e.) operands.

2. A node can have a minimum of one child.
a) true
b) false

Answer: a
Clarification: It is possible for a node to have at least one child, as is the case with the unary minus operator.

3. What does the other nodes of an expression tree(except leaves) contain?
a) only operands
b) only operators
c) both operands and operators
d) expression

Answer: b
Clarification: The nodes other than leaves always contain only operators. There cannot be any operand in those nodes.

4. An expression tree is a kind of?
a) Binary search tree
b) Fibonacci tree
c) Binary tree
d) Treap

Answer: c
Clarification: The expression tree is a binary tree. It contains operands at leaf nodes and remaining nodes are filled with operators. The operands and the operators can be arranged in any order (ascending, descending).

5. The expression obtained by recursively producing a left expression, followed by an operator, followed by recursively producing a right expression is called?
a) prefix expression
b) infix expression
c) postfix expression
d) paranthesized expression

Answer: b
Clarification: It is an infix expression because the format of an infix expression is given by operand-operator-operand.

6. The average depth of a binary tree is given as?
a) O(N)
b) O(log N)
c) O(M log N)
d) O(√N)

Answer: d
Clarification: The average depth of a binary expression tree is mathematically found to be O(√N).

7. Only infix expression can be made into an expression tree.
a) true
b) false

Answer: b
Clarification: All infix, prefix and postfix expressions can be made into an expression tree using appropriate algorithms.

8. An expression tree is created using?
a) postfix expression
b) prefix expression
c) infix expression
d) paranthesized expression

Answer: a
Clarification: A postfix expression is converted into an expression tree by reading one symbol at a time and constructing a tree respectively.

9. ++a*bc*+defg is an?
a) postfix expression
b) infix expression
c) prefix expression
d) invalid expression

Answer: c
Clarification: It is a prefix expression obtained from a preorder traversal since it is of the form operator-operand-operand.

10. An expression tree’s nodes can be deleted by calling?
a) malloc
b) calloc
c) delete
d) free

Answer: d
Clarification: In Binary trees, nodes are created by calling malloc and they are deleted by calling free.

11. In an expression tree algorithm, what happens when an operand is encountered?
a) create one node pointing to a stack
b) pop the nodes from the stack
c) clear stack
d) merge all the nodes

Answer: a
Clarification: When an operand is encountered, create one node trees and push it on to the stack. When an operator is encountered, pop the pointers from last two trees from the stack.