Please visit, subscribe and share 10 Minutes Lectures in Computer Science
Showing posts with label Data Structures. Show all posts
Showing posts with label Data Structures. Show all posts

# Data structures and algorithms multiple choice questions with answers, important interview questions in data structures, data structures questions for entrance exams, frequently asked questions in data structures and algorithms, GATE questions in data structures with explained answers

## SET 10

1. Consider a perfect binary tree of height 5. Which of the following are the minimum and maximum number of nodes in the right sub-tree of the root?

a) 32

b) 31

c) 16

d) 9

2. Rank the following functions by increasing order of growth; (For example, the correct ordering of n2, n4, n, n3 is n, n2, n3, n4.)

 f1 = (n!)1/n f2 = ((n)n)1/2 f3 = log nn f4 = n log n

a) f1, f2, f3, f4

b) f1, f3, f4, f2

c) f1, f2, f4, f3

d) f2, f1, f3, f4

### 3. What is a collision in a hash table implementation of a symbol table? Choose the most appropriate one.

a) Two key-value pairs that have equal keys but different values.

b) Two key-value pairs that have different keys and hash to different indices.

c) Two key-value pairs that have different keys but hash to the same index.

d) Two key-value pairs that have equal keys but hash to different indices.

4. A linear-probing hash table of length 10 uses the hash function h(x) = x mod 10. After inserting six integer keys into an initially empty hash table, the array of keys is:

Which of the following insertion sequences resulting in the above hash table? Assume that the length of the hash table does not change during the insertions.

a) 46, 42, 34, 52, 23, 33

b) 34, 42, 23, 52, 33, 46

c) 46, 34, 42, 23, 52, 33

d) 42, 46, 33, 23, 34, 52

### 5. Which of the following algorithms is parsimonious?

a) Insertion sort

b) Selection sort

c) Heap sort

d) All of the above

*************************

# Data structures and algorithms multiple choice questions with answers, important interview questions in data structures, data structures questions for entrance exams, frequently asked questions in data structures and algorithms, GATE questions in data structures with explained answers

## SET 09

1. Which among the following comparison sorts are in-place sorts?

a) Bucket sort

b) Insertion sort

c) Selection sort

d) Parallel merge sort

Answer: (b) Insertion sort and (c) Selection sort

What is in-place sort?

### An in-place sort is one that sorts the input without requiring additional space.

A sort algorithm in which the sorted items occupy the same storage as the original ones. A sorting algorithm that uses a small constant amount of extra space in addition to the original input, usually overwrite the input space, is referred as in-place sorting. [Refer here for more, what is in-place sort].

Insertion Sort is typically done in-place, by iterating up the array, growing the sorted list behind it. At each array-position, it checks the value there against the largest value in the sorted list (which happens to be next to it, in the previous array-position checked). If larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted list, shifts all the larger values up to make a space, and inserts into that correct position. [Refer here for more, Wikipedia. ]

The selection sort algorithm finds the smallest (or largest, depending on sorting order) element in the unsorted sub-list, exchanges it with the leftmost unsorted element (putting it in sorted order), and moves the sub-list boundaries one element to the right without any additional space. [Refer here more more - Wikipedia, Selection sort]

### 2. A max heap can be converted into a min heap in ________.

a) Exponential time

c) Linear time

d) Logarithmic time

### Building a min heap on any array will take linear time. Hence, converting a max heap array into min heal will take the same time.

Min heap is a special binary tree where the value stored in the parent node is less than or equal to the children and max heap is a tree where the parent is larger than or equal to the children.

3. To delete a dynamically allocated tree, the most suitable traversal technique is ________.

a) Pre-order

b) Post-order

c) In-order

d) Level-order

### To delete a dynamically allocated tree, we can delete children first and then the parent.

We will traverse the tree by using post Order traversal because we have to delete all child nodes first before deleting root node. If we delete root node first then we cannot traverse child nodes of root without maintaining a separate data store.

*************************

# Data structures and algorithms multiple choice questions with answers, important interview questions in data structures, data structures questions for entrance exams, frequently asked questions in data structures and algorithms, GATE questions in data structures with explained answers

## SET 08

a) 20

b) 21

c) 63

d) 12

### Minimum number of nodes in an AVL tree can be recursively calculated as follows;

Min. number of nodes of height h, N(h) = N(h-1) + N(h-2) + 1

Here, 1 is added to include the root node.

N(0) = 1,

N(1) = 2,

N(2) = N(1) + N(0) + 1 = 2+1+1 = 4,

N(3) = N(2) + N(1) + 1 = 4 + 2 + 1 = 7,

N(4) = 12,

N(5) = 20.

AVL tree

An AVL tree is a binary search tree with a self-balancing condition stating that the difference between the height of the left and right subtrees cannot be no more than one.

An AVL tree has the following properties:

1. The sub-trees of every node differ in height by at most one.

2. Every sub-tree is an AVL tree.

a) 20

b) 3

c) 12

d) 5

### Minimum value in an AVL tree can be found at the left most node that has left pointer NULL. Such a node can be found at a height of 3 for an AVL tree of height 5.

3. Consider a perfect binary tree of height h. Which of the following options represents the minimum and maximum number of nodes in the right sub-tree of the root?

a) 2h, 2h

b) 2h-1, 2h-1

c) 2h-1, 2h-1

d) 2h-1, 2h-1

### A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level. In this tree each level contains the maximum number of nodes, ie., every level is completely full of nodes.

The number of nodes in a perfect binary tree = 2h+1-1

As per the question, we need to find the number of nodes in the right sub-tree alone. Also, the right sub-tree is at height less than that of original tree. Hence, the number of nodes = 2h-1.

### For a perfect binary tree, the minimum and maximum number of nodes will be 2h+1-1. Hence, for the right sub-tree alone, they are 2h-1.

*************************

## Featured Content

### Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

data recovery