Campus and Interview Preparation with Data Structure
Important topic of Data Structure :-
- Heap
- Tree
- AVL Tree
- Hashing
 |
| campus/interview preparation |
Objective type questions or multiple choice questions (MCQ) are often asked in various exams, including job recruitment tests. It also helps in understanding language constructs, syntax and fundamental rules.click the link given in above list to go to that topic.
It is not a max heap as 12 and 7 are greater than 6.
But since (c) follows both the property at each node. This is a heap.
Here in all 3 swaps are required
1) 100 needs to be swapped with 15.
2) 100 needs to swapped with 50
3) 100 needs to be swapped with 89.
This will create a max heap satisfying all the properties of it.
Now 35 is inserted to it at the bottom.
Now restoring it up to again regain the max heap property,two swaps are required
a) Since 15 is smaller than 35, these both needs to be swapped.
b) 30 is less than 15, so again 35 and 15 needs to be swapped.
Heap in Data Structure
1.
Which of the following sequences of array elements forms a heap?
Which of the following sequences of array elements forms a heap?
(a) {23, 17, 14, 6, 13, 10, 1, 12, 7, 5}
(b) {23, 17, 14, 6, 13, 10, 1, 5, 7, 12}
(c) {23, 17, 14, 7, 13, 10, 1, 5, 6, 12}
(d) {23, 17, 14, 7, 13, 10, 1, 12, 5, 7}
(b) {23, 17, 14, 6, 13, 10, 1, 5, 7, 12}
(c) {23, 17, 14, 7, 13, 10, 1, 5, 6, 12}
(d) {23, 17, 14, 7, 13, 10, 1, 12, 5, 7}
Answer
(c)
Heap has
the following two properties:-
1) All the levels are filled in the order i.e. all the levels have maximum number of nodes except possibly the last level. In the last level all the nodes occur to the left.
2) Heap order property –If it is max heap, then data in root node must be greater than its successors. In case of min heap, then data in root node must be less than its predecessors.
1) All the levels are filled in the order i.e. all the levels have maximum number of nodes except possibly the last level. In the last level all the nodes occur to the left.
2) Heap order property –If it is max heap, then data in root node must be greater than its successors. In case of min heap, then data in root node must be less than its predecessors.
It is not a max heap as 12 and 7 are greater than 6.
But since (c) follows both the property at each node. This is a heap.
2.
A complete binary min-heap is made by including each integer in [1, 1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is ________
A complete binary min-heap is made by including each integer in [1, 1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is ________
(a) 2
(b) 3
(c) 8
(d) 9
(b) 3
(c) 8
(d) 9
Answer
(c) 8
1 can be
the top node only as it is the smallest node and min heap needs to be formed.2
can become child node of 1,3 can again become child node of 2 and so on. All
the other nodes after 9 can be filled in the manner that satisfies structural
property of heap ( Complete binary tree). So maximum depth could be 8.
3.
Consider the following array of elements. 〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉. The minimum number of interchanges needed to convert it into a max-heap is
Consider the following array of elements. 〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉. The minimum number of interchanges needed to convert it into a max-heap is
(a) 4
(b) 5
(c) 2
(d) 3
(b) 5
(c) 2
(d) 3
Answer
(d) 3
Here in all 3 swaps are required
1) 100 needs to be swapped with 15.
2) 100 needs to swapped with 50
3) 100 needs to be swapped with 89.
This will create a max heap satisfying all the properties of it.
4.
Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4. Now consider that a value 35 is inserted into this heap. After insertion, the new heap is
Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4. Now consider that a value 35 is inserted into this heap. After insertion, the new heap is
(a) 40, 30, 20, 10, 15, 16, 17, 8, 4, 35
(b) 40, 35, 20, 10, 30, 16, 17, 8, 4, 15
(c) 40, 30, 20, 10, 35, 16, 17, 8, 4, 15
(d) 40, 35, 20, 10, 15, 16, 17, 8, 4, 30
(b) 40, 35, 20, 10, 30, 16, 17, 8, 4, 15
(c) 40, 30, 20, 10, 35, 16, 17, 8, 4, 15
(d) 40, 35, 20, 10, 15, 16, 17, 8, 4, 30
Answer
(b)
Now 35 is inserted to it at the bottom.
Now restoring it up to again regain the max heap property,two swaps are required
a) Since 15 is smaller than 35, these both needs to be swapped.
b) 30 is less than 15, so again 35 and 15 needs to be swapped.
5.
Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i <= n), the index of the parent is
Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i <= n), the index of the parent is
(a) i – 1
(b) floor(i/2)
(c) ceiling(i/2)
(d) (i+1)/2
(b) floor(i/2)
(c) ceiling(i/2)
(d) (i+1)/2
Answer
(b)
If i is
the index of child, then floor(i/2) is the index of the parent.In short, if
index starts from 1 and parent is at I,then its child if present are at 2i and
2i+1 node.
6.
In a max heap, element with the greatest key is always in the ______________ node
In a max heap, element with the greatest key is always in the ______________ node
(a) leaf
(b) root
(c) first node of left sub tree
(d) first node of right sub tree
(b) root
(c) first node of left sub tree
(d) first node of right sub tree
Answer
(b)
Heap
satisifies structure property and heap order property.Heap property says that
parent element should be greater than any of its children. By this logic, we
can infer that greates element should be at root.
7.
What is the most appropriate data structure to implement a priority queue?
What is the most appropriate data structure to implement a priority queue?
(a) Heap
(b) circular array
(c) Linked list
(d) Binary tree
(b) circular array
(c) Linked list
(d) Binary tree
Answer
(a) Heap
Heap is
used to implement priority queue because both insertion or deletion can be done
in O(logn) time which is better compared to other data structures.
8.
A complete binary tree with the property that key value in any node is greater than or equal to the key values in both its children is called as.
A complete binary tree with the property that key value in any node is greater than or equal to the key values in both its children is called as.
(a) Binary
search tree
(b) Threaded binary tree
(c) Heap
(d) AVL tree
(b) Threaded binary tree
(c) Heap
(d) AVL tree
Answer
(c) Heap
This is
the heap order property.
9.
What is the time complexity of Build Heap operation.
What is the time complexity of Build Heap operation.
(a) O(nLogn)
(b) O(n^2)
(c) O(Logn)
(d) O(n)
(b) O(n^2)
(c) O(Logn)
(d) O(n)
Answer
(d) O(n)
Heap can
be built in O(n) time using Bottom up approach.
10.
In a binary max heap containing n numbers, the smallest element can be found in time (GATE CS 2006)
In a binary max heap containing n numbers, the smallest element can be found in time (GATE CS 2006)
(a) O(n)
(b) O(logn)
(c) O(loglogn)
(d) O(1)
(b) O(logn)
(c) O(loglogn)
(d) O(1)
Answer
(a)
In the
max heap, smallest number can be a leaf node only.Thats why we will have to
check all the leaf nodes. Leaf nodes will always be of O(n).
Hence answer is A).
Hence answer is A).
If this article is helpful to you so please like share and comments..Thank you..
Comments
Post a Comment