All questions of Programming & Data Structures for Computer Science Engineering (CSE) Exam
The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a Max Heap. The resultant Max Heap is.- a)
- b)
- c)
- d)
Correct answer is option 'A'. Can you explain this answer?
The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a Max Heap. The resultant Max Heap is.
a)
b)
c)
d)
|
Crack Gate answered |
32, 15, 20, 30, 12, 25, 16
After insertion of 32, 15 and 20
After insertion of 32, 15 and 20
After insertion of 30
Max Heap property is violated, so 30 is swapped with 15
After insertion of 12
After insertion of 25
Max Heap property is violated, so 25 is swapped with 20
After insertion of 16
How many distinct binary search trees can be created out of 4 distinct keys?- a)4
- b)14
- c)24
- d)42
Correct answer is option 'B'. Can you explain this answer?
How many distinct binary search trees can be created out of 4 distinct keys?
a)
4
b)
14
c)
24
d)
42
|
Rajeev Menon answered |
Number of Binary Search trees for n nodes is given by = (2n)! / n! * (n+1)!
Hence for 4 keys or nodes-
= 8! /4! * 5!
= 14
Hence, 14 distinct binary search trees are possible for 4 keys.
So, the Correct Answer is Option B
So, the Correct Answer is Option B
You can solve many such questions & mock tests by going through the course:
Predict output of following program
#include <stdio.h>
int fun(int n)
{
if (n == 4)
return n;
else return 2*fun(n+1);
}
int main()
{
printf("%d ", fun(2));
return 0;- a)4
- b)8
- c)16
- d)Runtime Error
Correct answer is option 'C'. Can you explain this answer?
Predict output of following program
#include <stdio.h>
int fun(int n)
{
if (n == 4)
return n;
else return 2*fun(n+1);
}
int main()
{
printf("%d ", fun(2));
return 0;
#include <stdio.h>
int fun(int n)
{
if (n == 4)
return n;
else return 2*fun(n+1);
}
int main()
{
printf("%d ", fun(2));
return 0;
a)
4
b)
8
c)
16
d)
Runtime Error
|
Gitanjali Mishra answered |
Explanation:
- The given program is a recursive function that calls itself until the base case is reached.
- The function `fun()` takes an integer `n` as a parameter and returns either `n` if `n` is equal to 4, or `2*fun(n+1)` if `n` is not equal to 4.
- In the `main()` function, `fun(2)` is called, which will recursively call `fun()` with increasing values until `n` reaches 4.
- When `n` reaches 4, the base case is met, and the function returns 4.
- Substituting the return values back into the recursive calls, we get:
`fun(2) = 2*fun(3) = 2*(2*fun(4)) = 2*(2*4) = 16`
- Therefore, the output of the program will be `16`.
So, the correct answer is:
c) 16
#include<stdio.h>
int f(int *a, int n)
{
if(n <= 0) return 0;
else if(*a % 2 == 0) return *a + f(a+1, n-1);
else return *a - f(a+1, n-1);
}
int main()
{
int a[] = {12, 7, 13, 4, 11, 6};
printf("%d", f(a, 6));
getchar();
return 0;
}- a)-9
- b)5
- c)15
- d)19
Correct answer is option 'C'. Can you explain this answer?
#include<stdio.h>
int f(int *a, int n)
{
if(n <= 0) return 0;
else if(*a % 2 == 0) return *a + f(a+1, n-1);
else return *a - f(a+1, n-1);
}
int main()
{
int a[] = {12, 7, 13, 4, 11, 6};
printf("%d", f(a, 6));
getchar();
return 0;
}
int f(int *a, int n)
{
if(n <= 0) return 0;
else if(*a % 2 == 0) return *a + f(a+1, n-1);
else return *a - f(a+1, n-1);
}
int main()
{
int a[] = {12, 7, 13, 4, 11, 6};
printf("%d", f(a, 6));
getchar();
return 0;
}
a)
-9
b)
5
c)
15
d)
19
|
Sanya Agarwal answered |
f() is a recursive function which adds f(a+1, n-1) to *a if *a is even. If *a is odd then f() subtracts f(a+1, n-1) from *a. See below recursion tree for execution of f(a, 6). .
f(add(12), 6) /*Since 12 is first element. a contains address of 12 */
|
|
12 + f(add(7), 5) /* Since 7 is the next element, a+1 contains address of 7 */
|
|
7 - f(add(13), 4)
|
|
13 - f(add(4), 3)
|
|
4 + f(add(11), 2)
|
|
11 - f(add(6), 1)
|
|
6 + 0
So, the final returned value is 12 + (7 – (13 – (4 + (11 – (6 + 0))))) = 15
f(add(12), 6) /*Since 12 is first element. a contains address of 12 */
|
|
12 + f(add(7), 5) /* Since 7 is the next element, a+1 contains address of 7 */
|
|
7 - f(add(13), 4)
|
|
13 - f(add(4), 3)
|
|
4 + f(add(11), 2)
|
|
11 - f(add(6), 1)
|
|
6 + 0
So, the final returned value is 12 + (7 – (13 – (4 + (11 – (6 + 0))))) = 15
How many distinct BSTs can be constructed with 3 distinct keys?- a)4
- b)5
- c)6
- d)9
Correct answer is option 'B'. Can you explain this answer?
How many distinct BSTs can be constructed with 3 distinct keys?
a)
4
b)
5
c)
6
d)
9
|
|
Sanya Agarwal answered |
For distinct BST we apply this formula
n = 3 here so C(6, 3) = 20 and 20/4 = 5
n = 3 here so C(6, 3) = 20 and 20/4 = 5
Consider the following recursive C function that takes two arguments
unsigned int foo(unsigned int n, unsigned int r) {
if (n > 0) return (n%r) + foo (n/r, r));
else return 0;
}
What is the return value of the function foo when it is called as foo(345, 10) ?
- a)345
- b)12
- c)5
- d)3
Correct answer is option 'B'. Can you explain this answer?
Consider the following recursive C function that takes two arguments
unsigned int foo(unsigned int n, unsigned int r) {
if (n > 0) return (n%r) + foo (n/r, r));
else return 0;
}
What is the return value of the function foo when it is called as foo(345, 10) ?
a)
345
b)
12
c)
5
d)
3
|
|
Sanya Agarwal answered |
Consider the following recursive C function. If get(6) function is being called in main() then how many times will the get() function be invoked before returning to the main()?
void get (int n)
{
if (n < 1) return;
get(n-1);
get(n-3);
printf("%d", n);
}- a)15
- b)25
- c)35
- d)45
Correct answer is option 'B'. Can you explain this answer?
Consider the following recursive C function. If get(6) function is being called in main() then how many times will the get() function be invoked before returning to the main()?
void get (int n)
{
if (n < 1) return;
get(n-1);
get(n-3);
printf("%d", n);
}
void get (int n)
{
if (n < 1) return;
get(n-1);
get(n-3);
printf("%d", n);
}
a)
15
b)
25
c)
35
d)
45
|
|
Sanya Agarwal answered |
get(6) [25 Calls]
/ \
[17 Calls] get(5) get(3) [7 Calls]
/ \
get(4) get(2)[5 Calls]
/ \
[7 Calls] get(3) get(1)[3 Calls]
/ \
get(2) get(0)
/ \
[3 Calls]get(1) get(-1)
/ \
get(0) get(-2)
We can verify the same by running below program. [sourcecode language="CPP"] # include int count = 0; void get (int n) { count++; if (n < 1) return; get(n-1); get(n-3); } int main() { get(6); printf("%d ", count); } [/sourcecode] Output: 25
/ \
[17 Calls] get(5) get(3) [7 Calls]
/ \
get(4) get(2)[5 Calls]
/ \
[7 Calls] get(3) get(1)[3 Calls]
/ \
get(2) get(0)
/ \
[3 Calls]get(1) get(-1)
/ \
get(0) get(-2)
We can verify the same by running below program. [sourcecode language="CPP"] # include int count = 0; void get (int n) { count++; if (n < 1) return; get(n-1); get(n-3); } int main() { get(6); printf("%d ", count); } [/sourcecode] Output: 25
Output of following program?
#include <stdio.h>
int fun(int n, int *f_p)
{
int t, f;
if (n <= 1)
{
*f_p = 1;
return 1;
}
t = fun(n- 1,f_p);
f = t+ * f_p;
*f_p = t;
return f;
}
int main()
{
int x = 15;
printf (" %d n", fun(5, &x));
return 0;
}- a)6
- b)8
- c)14
- d)15
Correct answer is option 'B'. Can you explain this answer?
Output of following program?
#include <stdio.h>
int fun(int n, int *f_p)
{
int t, f;
if (n <= 1)
{
*f_p = 1;
return 1;
}
t = fun(n- 1,f_p);
f = t+ * f_p;
*f_p = t;
return f;
}
int main()
{
int x = 15;
printf (" %d n", fun(5, &x));
return 0;
}
#include <stdio.h>
int fun(int n, int *f_p)
{
int t, f;
if (n <= 1)
{
*f_p = 1;
return 1;
}
t = fun(n- 1,f_p);
f = t+ * f_p;
*f_p = t;
return f;
}
int main()
{
int x = 15;
printf (" %d n", fun(5, &x));
return 0;
}
a)
6
b)
8
c)
14
d)
15
|
Ravi Singh answered |
Let x is stored at location 2468 i.e. &x = 2468
(dots are use just to ensure alignment)
x = 15
fun(5, 2468)
...{t = fun(4, 2468)
.......{t = fun(3, 2468)
...........{t = fun(2,2468)
...............{t = fun(1, 2468)
...................{// x=1
........................return 1}
................t = 1
................f = 2 //1+1 //since *f_p is x
................x = t = 1
................return 2}
...........t = 2
...........f = 2+1
...........x = t = 2
...........return 3}
........t = 3
........f = 3+2
........x = t = 3
........return 5}
....t = 5
....f = 5+3
....x = t = 5
....return 8}
x = 15
fun(5, 2468)
...{t = fun(4, 2468)
.......{t = fun(3, 2468)
...........{t = fun(2,2468)
...............{t = fun(1, 2468)
...................{// x=1
........................return 1}
................t = 1
................f = 2 //1+1 //since *f_p is x
................x = t = 1
................return 2}
...........t = 2
...........f = 2+1
...........x = t = 2
...........return 3}
........t = 3
........f = 3+2
........x = t = 3
........return 5}
....t = 5
....f = 5+3
....x = t = 5
....return 8}
which implies fun (5,2468) is 8.
Which of the following traversal outputs the data in sorted order in a BST?- a)Preorder
- b)Inorder
- c)Postorder
- d)Level order
Correct answer is option 'B'. Can you explain this answer?
Which of the following traversal outputs the data in sorted order in a BST?
a)
Preorder
b)
Inorder
c)
Postorder
d)
Level order
|
Abhay Bhadouriya answered |
Inorder traversal of a BST outputs data in sorted order. Read here for details.
How many stacks are needed to implement a queue. Consider the situation where no other data structure like arrays, linked list is available to you.- a)1
- b)2
- c)3
- d)4
Correct answer is option 'B'. Can you explain this answer?
How many stacks are needed to implement a queue. Consider the situation where no other data structure like arrays, linked list is available to you.
a)
1
b)
2
c)
3
d)
4
|
|
Crack Gate answered |
- A queue operates on a First In, First Out (FIFO) principle, while a stack works on a Last In, First Out (LIFO) principle.
- By using two stacks, we can simulate the FIFO behavior of a queue.
thus option B is correct
A hash table can store a maximum of 10 records. Currently there are records in locations 1, 3, 4, 7, 8, 9, 10. The probability of a new record going into location 2, with a has function resolving collisions by linear probing is- a)0.6
- b)0.1
- c)0.2
- d)0.5
Correct answer is option 'A'. Can you explain this answer?
A hash table can store a maximum of 10 records. Currently there are records in locations 1, 3, 4, 7, 8, 9, 10. The probability of a new record going into location 2, with a has function resolving collisions by linear probing is
a)
0.6
b)
0.1
c)
0.2
d)
0.5
|
Maulik Pillai answered |
If the new record hashes onto one of the six locations 7, 8, 9, 10, 1 or 2, the location 2 will receive the new record. The probability is 6/10 (as 10 is the total possible number of locations).
Consider the following C function:int f(int n){static int i = 1;if(n >= 5) return n;n = n+i; i++;return f(n);}The value returned by f(1) is- a)5
- b)6
- c)7
- d)8
Correct answer is option 'C'. Can you explain this answer?
Consider the following C function:
int f(int n)
{
static int i = 1;
if(n >= 5) return n;
n = n+i;
i++;
return f(n);
}
The value returned by f(1) is
a)
5
b)
6
c)
7
d)
8
|
|
Akshita Khanna answered |
answer is 7.as,
f(1):n=2,i=2
f(2):n=4,i=3
f(4):n=7,i=4
f(7):print(n)===>>> 7<ans>
f(1):n=2,i=2
f(2):n=4,i=3
f(4):n=7,i=4
f(7):print(n)===>>> 7<ans>
A stack A has 4 entries as following sequence a,b,c,d and stack B is empty. An entry popped out of stack A can be printed or pushed to stack B. An entry popped out of stack B can only be printed.
Then the number of possible permutations that the entries can be printed will be ?
- a)24
- b)12
- c)21
- d)14
Correct answer is option 'D'. Can you explain this answer?
A stack A has 4 entries as following sequence a,b,c,d and stack B is empty. An entry popped out of stack A can be printed or pushed to stack B. An entry popped out of stack B can only be printed.
Then the number of possible permutations that the entries can be printed will be ?
a)
24
b)
12
c)
21
d)
14
|
Prateek Khanna answered |
permutations which start with D:
to print D first , all a,b,c must be pushed on to stack before popping D and the only arrangement possible = D C B A
permutations start with C:
you need to push a and b from stack A to stack B , now print C
content of stack B= b a (from top to bottom)
content of stack A = d
permutations possible = 3!/2! = 3 = they are c d b a, c b d a, c b a d --> 3 permutations here
permutations starting with b :
to print b first, a will be pushed onto stack B
content of stack B= a
content of stack A= c d
you can bring these out in (3! -1) as (d a c) is not possible--> 5 possible
permutations starting with a:
fix ab
a b _ _
in this a b c d or a b dc
fix ac
a c _ _
a c b d or a c d b
fix ad
a d _ _
a d c b
total 5
total = 1+3+5+5= 14
to print D first , all a,b,c must be pushed on to stack before popping D and the only arrangement possible = D C B A
permutations start with C:
you need to push a and b from stack A to stack B , now print C
content of stack B= b a (from top to bottom)
content of stack A = d
permutations possible = 3!/2! = 3 = they are c d b a, c b d a, c b a d --> 3 permutations here
permutations starting with b :
to print b first, a will be pushed onto stack B
content of stack B= a
content of stack A= c d
you can bring these out in (3! -1) as (d a c) is not possible--> 5 possible
permutations starting with a:
fix ab
a b _ _
in this a b c d or a b dc
fix ac
a c _ _
a c b d or a c d b
fix ad
a d _ _
a d c b
total 5
total = 1+3+5+5= 14
Which of the following data structure to convert an Infix expression into equivalent Prefix/Postfix notation?- a)Array
- b)Hashing
- c)Stack
- d)Queue
Correct answer is option 'C'. Can you explain this answer?
Which of the following data structure to convert an Infix expression into equivalent Prefix/Postfix notation?
a)
Array
b)
Hashing
c)
Stack
d)
Queue
|
|
Sudhir Patel answered |
Conversion of infix to postfix is,
Infix: ((a+b)*(c-d))
Infix: ((a+b)*(c-d))
The postfix expression is ab+cd-*
Hence the correct answer is Stack.
What all is true about Stack data structure? (More than one option is correct)- a)Last IN First OUT
- b)Minimum 2 queues are required to implement a stack
- c)First IN First OUT
- d)Does not have a fixed size.
Correct answer is option 'A,B,D'. Can you explain this answer?
What all is true about Stack data structure? (More than one option is correct)
a)
Last IN First OUT
b)
Minimum 2 queues are required to implement a stack
c)
First IN First OUT
d)
Does not have a fixed size.
|
Ananya Kumari answered |
What all is true about stack data structure? ( more than one option is correct)
last in first out ,
maximum 2 queues are required to implement a stack
does not have a fixed size
Correct is ABD is right ans
last in first out ,
maximum 2 queues are required to implement a stack
does not have a fixed size
Correct is ABD is right ans
What does the following function print for n = 25?void fun(int n){if (n == 0)return;printf("%d", n%2);fun(n/2);- a)11001
- b)10011
- c)11111
- d)00000
Correct answer is option 'B'. Can you explain this answer?
What does the following function print for n = 25?
void fun(int n)
{
if (n == 0)
return;
printf("%d", n%2);
fun(n/2);
a)
11001
b)
10011
c)
11111
d)
00000
|
|
Ravi Singh answered |
The function mainly prints binary representation in reverse order.
Which of the following statements is false?- a)A tree with n nodes has (n - 1) edges.
- b)A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results.
- c)A complete binary tree with n internal nodes has (n + 1) leaves.
- d)The maximum number of nodes in a binary tree of height h is (2h+1 - 1).
Correct answer is option 'B'. Can you explain this answer?
Which of the following statements is false?
a)
A tree with n nodes has (n - 1) edges.
b)
A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results.
c)
A complete binary tree with n internal nodes has (n + 1) leaves.
d)
The maximum number of nodes in a binary tree of height h is (2h+1 - 1).
|
|
Sanya Agarwal answered |
A labelled rooted binary tree can not be constructed uniquely when inorder traversal is given along with post-order or pre-order traversal.
The result evaluating the postfix expression 10 5 + 60 6/* 8 - is- a)284
- b)213
- c)142
- d)71
Correct answer is option 'C'. Can you explain this answer?
The result evaluating the postfix expression 10 5 + 60 6/* 8 - is
a)
284
b)
213
c)
142
d)
71
|
Baishali Reddy answered |
10 5 + 60 6 / * 8 -
Result is 142.
Result is 142.
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;
Correct answer is option 'C'. Can you explain this answer?
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;
|
|
Sudhir Patel answered |
The syntax to declare multidimensional array in java is either int[][] arr; or int arr[][];
Which of the following concepts make extensive use of arrays?- a)Binary trees
- b)Scheduling of processes
- c)Caching
- d)Spatial locality
Correct answer is option 'D'. Can you explain this answer?
Which of the following concepts make extensive use of arrays?
a)
Binary trees
b)
Scheduling of processes
c)
Caching
d)
Spatial locality
|
Arka Shah answered |
Explanation:
Arrays are a fundamental data structure in computer science that allow for efficient storage and retrieval of data. They are used extensively in various concepts and algorithms. Out of the given options, the concept that makes the most extensive use of arrays is "Spatial locality".
Spatial Locality:
Spatial locality is a concept in computer architecture that refers to the tendency of a program to access data that is close to the previously accessed data. It is based on the observation that programs often access data in a sequential or localized manner.
Arrays and Spatial Locality:
Arrays are particularly well-suited for exploiting spatial locality because they store elements of the same type in contiguous memory locations. When an array is accessed sequentially, the CPU can efficiently retrieve the next element from the cache, taking advantage of spatial locality. This results in faster and more efficient memory access.
Benefits of Using Arrays:
Arrays offer several benefits when it comes to spatial locality:
1. Cache Efficiency: Arrays allow for effective utilization of cache memory. As the elements of an array are stored sequentially in memory, accessing consecutive array elements benefits from cache locality.
2. Reduced Memory Latency: Spatial locality reduces memory latency by minimizing the number of cache misses. When accessing elements sequentially, the CPU can fetch them from the cache without having to access main memory, which is significantly slower.
3. Vectorization and Parallelism: Accessing elements of an array sequentially enables vectorization and parallelism. Modern processors often have SIMD (Single Instruction Multiple Data) instructions, which can process multiple data elements in parallel. Sequential access allows these instructions to operate efficiently on array elements.
4. Optimized Hardware Access: Array-based access patterns are well-suited for hardware prefetching, branch prediction, and other hardware optimizations. These optimizations further enhance the performance of accessing array elements.
In conclusion, spatial locality heavily relies on efficient memory access patterns, and arrays provide a natural way to exploit this concept. They offer cache efficiency, reduced memory latency, support for vectorization and parallelism, and optimized hardware access. Therefore, arrays make extensive use of spatial locality.
Arrays are a fundamental data structure in computer science that allow for efficient storage and retrieval of data. They are used extensively in various concepts and algorithms. Out of the given options, the concept that makes the most extensive use of arrays is "Spatial locality".
Spatial Locality:
Spatial locality is a concept in computer architecture that refers to the tendency of a program to access data that is close to the previously accessed data. It is based on the observation that programs often access data in a sequential or localized manner.
Arrays and Spatial Locality:
Arrays are particularly well-suited for exploiting spatial locality because they store elements of the same type in contiguous memory locations. When an array is accessed sequentially, the CPU can efficiently retrieve the next element from the cache, taking advantage of spatial locality. This results in faster and more efficient memory access.
Benefits of Using Arrays:
Arrays offer several benefits when it comes to spatial locality:
1. Cache Efficiency: Arrays allow for effective utilization of cache memory. As the elements of an array are stored sequentially in memory, accessing consecutive array elements benefits from cache locality.
2. Reduced Memory Latency: Spatial locality reduces memory latency by minimizing the number of cache misses. When accessing elements sequentially, the CPU can fetch them from the cache without having to access main memory, which is significantly slower.
3. Vectorization and Parallelism: Accessing elements of an array sequentially enables vectorization and parallelism. Modern processors often have SIMD (Single Instruction Multiple Data) instructions, which can process multiple data elements in parallel. Sequential access allows these instructions to operate efficiently on array elements.
4. Optimized Hardware Access: Array-based access patterns are well-suited for hardware prefetching, branch prediction, and other hardware optimizations. These optimizations further enhance the performance of accessing array elements.
In conclusion, spatial locality heavily relies on efficient memory access patterns, and arrays provide a natural way to exploit this concept. They offer cache efficiency, reduced memory latency, support for vectorization and parallelism, and optimized hardware access. Therefore, arrays make extensive use of spatial locality.
Consider the C function given below.
int f(int j)
{
static int i = 50;
int k;
if (i == j)
{
printf(“something”);
k = f(i);
return 0;
}
else return 0;
}Which one of the following is TRUE?- a)The function returns 0 for all values of j
- b)The function prints the string something for all values of j.
- c)The function returns 0 when j = 50.
- d)The function will exhaust the runtime stack or run into an infinite loop when j = 50
Correct answer is option 'D'. Can you explain this answer?
Consider the C function given below.
int f(int j)
{
static int i = 50;
int k;
if (i == j)
{
printf(“something”);
k = f(i);
return 0;
}
else return 0;
}
int f(int j)
{
static int i = 50;
int k;
if (i == j)
{
printf(“something”);
k = f(i);
return 0;
}
else return 0;
}
Which one of the following is TRUE?
a)
The function returns 0 for all values of j
b)
The function prints the string something for all values of j.
c)
The function returns 0 when j = 50.
d)
The function will exhaust the runtime stack or run into an infinite loop when j = 50
|
|
Sanya Agarwal answered |
When j is 50, the function would call itself again and again as neither i nor j is changed inside the recursion.
An operator delete(i) for a binary heap data structure is to be designed to delete the item in the i-th node. Assume that the heap is implemented in an array and i refers to the i-th index of the array. If the heap tree has depth d (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal of the element?- a)O(1)
- b)O(d) but not O(1)
- c)O(2d) but not O(d)
- d)O(d2d) but not O(2d)
Correct answer is option 'B'. Can you explain this answer?
An operator delete(i) for a binary heap data structure is to be designed to delete the item in the i-th node. Assume that the heap is implemented in an array and i refers to the i-th index of the array. If the heap tree has depth d (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal of the element?
a)
O(1)
b)
O(d) but not O(1)
c)
O(2d) but not O(d)
d)
O(d2d) but not O(2d)
|
Palak Khanna answered |
For this question, we have to slightly tweak the delete_min() operation of the heap data structure to implement the delete(i) operation. The idea is to empty the spot in the array at the index i (the position at which element is to be deleted) and replace it with the last leaf in the heap (remember heap is implemented as complete binary tree so you know the location of the last leaf), decrement the heap size and now starting from the current position i (position that held the item we deleted), shift it up in case newly replaced item is greater than the parent of old item (considering max-heap). If it’s not greater than the parent, then percolate it down by comparing with the child’s value. The newly added item can percolate up/down a maximum of d times which is the depth of the heap data structure. Thus we can say that complexity of delete(i) would be O(d) but not O(1).
C preprocessors can have compiler specific features.- a)True
- b)False
- c)Depends on the standard
- d)Depends on the platform
Correct answer is option 'A'. Can you explain this answer?
C preprocessors can have compiler specific features.
a)
True
b)
False
c)
Depends on the standard
d)
Depends on the platform
|
Prasad Chakraborty answered |
Explanation:
The C preprocessor is a text substitution tool that is used to modify the source code before it gets compiled. It is a part of the compiler system and is executed before the actual compilation process. The preprocessor performs a set of operations like macro expansion, conditional compilation, and file inclusion, among others.
The preprocessor is not a part of the C language standard, but it is a part of the compiler system. Hence, the preprocessor features may vary from one compiler to another. Some compilers may offer additional features that are not available in other compilers.
Compiler Specific Features:
Compiler-specific features are those features that are not a part of the C standard but are provided by the compiler to enhance the functionality of the preprocessor. These features may include:
1. Pragma Directives: Some compilers provide additional preprocessor directives that are used to control the compiler behavior. These directives are called pragma directives.
2. Inline Functions: Some compilers provide inline functions that are used to improve the performance of the program by avoiding the overhead of function calls.
3. __attribute__ Specifier: Some compilers provide the __attribute__ specifier that is used to specify the attributes of a variable, function, or type.
4. __typeof__ Operator: Some compilers provide the __typeof__ operator that is used to determine the type of an expression at compile time.
Conclusion:
Therefore, it can be concluded that C preprocessors can have compiler-specific features, as different compilers may provide additional features that are not available in other compilers. These features can be used to enhance the functionality of the preprocessor and improve the performance of the program.
The C preprocessor is a text substitution tool that is used to modify the source code before it gets compiled. It is a part of the compiler system and is executed before the actual compilation process. The preprocessor performs a set of operations like macro expansion, conditional compilation, and file inclusion, among others.
The preprocessor is not a part of the C language standard, but it is a part of the compiler system. Hence, the preprocessor features may vary from one compiler to another. Some compilers may offer additional features that are not available in other compilers.
Compiler Specific Features:
Compiler-specific features are those features that are not a part of the C standard but are provided by the compiler to enhance the functionality of the preprocessor. These features may include:
1. Pragma Directives: Some compilers provide additional preprocessor directives that are used to control the compiler behavior. These directives are called pragma directives.
2. Inline Functions: Some compilers provide inline functions that are used to improve the performance of the program by avoiding the overhead of function calls.
3. __attribute__ Specifier: Some compilers provide the __attribute__ specifier that is used to specify the attributes of a variable, function, or type.
4. __typeof__ Operator: Some compilers provide the __typeof__ operator that is used to determine the type of an expression at compile time.
Conclusion:
Therefore, it can be concluded that C preprocessors can have compiler-specific features, as different compilers may provide additional features that are not available in other compilers. These features can be used to enhance the functionality of the preprocessor and improve the performance of the program.
Consider the following Binary Search Tree
Q. If we randomly search one of the keys present in above BST, what would be the expected number of comparisons?- a)2.75
- b)2.25
- c)2.57
- d)3.25
Correct answer is option 'C'. Can you explain this answer?
Consider the following Binary Search Tree
Q. If we randomly search one of the keys present in above BST, what would be the expected number of comparisons?
a)
2.75
b)
2.25
c)
2.57
d)
3.25
|
Milan Chavan answered |
Expected number of comparisons = (1*1 + 2*2 + 3*3 + 4*1)/7 = 18/7 = 2.57
Which of the following traversals is sufficient to construct BST from given traversals 1) Inorder 2) Preorder 3) Postorder- a)Any one of the given three traversals is sufficient
- b)Either 2 or 3 is sufficient
- c)2 and 3
- d)1 and 3
Correct answer is option 'B'. Can you explain this answer?
Which of the following traversals is sufficient to construct BST from given traversals 1) Inorder 2) Preorder 3) Postorder
a)
Any one of the given three traversals is sufficient
b)
Either 2 or 3 is sufficient
c)
2 and 3
d)
1 and 3
|
|
Preethi Iyer answered |
When we know either preorder or postorder traversal, we can construct the BST. Note that we can always sort the given traversal and get the inorder traversal. Inorder traversal of BST is always sorted.
Given two Balanced binary search trees, B1 having n elements and B2 having m elements, what is the time complexity of the best known algorithm to merge these trees to form another balanced binary tree containing m+n elements ?- a)O(m+n)
- b)O(mlogn)
- c)O(nlogm)
- d)O(m2 + n2)
Correct answer is option 'A'. Can you explain this answer?
Given two Balanced binary search trees, B1 having n elements and B2 having m elements, what is the time complexity of the best known algorithm to merge these trees to form another balanced binary tree containing m+n elements ?
a)
O(m+n)
b)
O(mlogn)
c)
O(nlogm)
d)
O(m2 + n2)
|
Garima Bose answered |
The correct answer is option 'A' - O(mn). Let's understand why.
To merge two balanced binary search trees, we need to follow a specific algorithm that ensures the resulting tree is still balanced.
Here is a step-by-step explanation of the algorithm:
1. Convert B1 and B2 to sorted arrays using an inorder traversal. This step takes O(n) and O(m) time, respectively.
2. Merge the two sorted arrays into a single sorted array using the merge algorithm from Merge Sort. This step takes O(n+m) time.
3. Construct a balanced binary search tree from the merged sorted array. This step takes O(n+m) time.
4. The final balanced binary search tree contains n+m elements.
Now, let's analyze the time complexity of the algorithm:
- Converting B1 and B2 to sorted arrays takes O(n) and O(m) time, respectively.
- Merging the two sorted arrays takes O(n+m) time.
- Constructing a balanced binary search tree from the merged sorted array also takes O(n+m) time.
Therefore, the total time complexity of the algorithm is:
O(n) + O(m) + O(n+m) + O(n+m) = O(n+m) + O(n+m) = 2O(n+m) = O(n+m)
Since n and m are the number of elements in B1 and B2 respectively, the time complexity of the algorithm can be written as O(nm).
Hence, the best known algorithm to merge two balanced binary search trees to form another balanced binary tree containing n+m elements has a time complexity of O(nm), which is equivalent to O(mn). Therefore, the correct answer is option 'A' - O(mn).
To merge two balanced binary search trees, we need to follow a specific algorithm that ensures the resulting tree is still balanced.
Here is a step-by-step explanation of the algorithm:
1. Convert B1 and B2 to sorted arrays using an inorder traversal. This step takes O(n) and O(m) time, respectively.
2. Merge the two sorted arrays into a single sorted array using the merge algorithm from Merge Sort. This step takes O(n+m) time.
3. Construct a balanced binary search tree from the merged sorted array. This step takes O(n+m) time.
4. The final balanced binary search tree contains n+m elements.
Now, let's analyze the time complexity of the algorithm:
- Converting B1 and B2 to sorted arrays takes O(n) and O(m) time, respectively.
- Merging the two sorted arrays takes O(n+m) time.
- Constructing a balanced binary search tree from the merged sorted array also takes O(n+m) time.
Therefore, the total time complexity of the algorithm is:
O(n) + O(m) + O(n+m) + O(n+m) = O(n+m) + O(n+m) = 2O(n+m) = O(n+m)
Since n and m are the number of elements in B1 and B2 respectively, the time complexity of the algorithm can be written as O(nm).
Hence, the best known algorithm to merge two balanced binary search trees to form another balanced binary tree containing n+m elements has a time complexity of O(nm), which is equivalent to O(mn). Therefore, the correct answer is option 'A' - O(mn).
Which of the following is true- a)The AVL trees are more balanced compared to Red Black Trees, but they may cause more rotations during insertion and deletion.
- b)Heights of AVL and Red-Black trees are generally same, but AVL Trees may cause more rotations during insertion and deletion.
- c)Red Black trees are more balanced compared to AVL Trees, but may cause more rotations during insertion and deletion.
- d)Heights of AVL and Red-Black trees are generally same, but Red Black rees may cause more rotations during insertion and deletion.
Correct answer is option 'A'. Can you explain this answer?
Which of the following is true
a)
The AVL trees are more balanced compared to Red Black Trees, but they may cause more rotations during insertion and deletion.
b)
Heights of AVL and Red-Black trees are generally same, but AVL Trees may cause more rotations during insertion and deletion.
c)
Red Black trees are more balanced compared to AVL Trees, but may cause more rotations during insertion and deletion.
d)
Heights of AVL and Red-Black trees are generally same, but Red Black rees may cause more rotations during insertion and deletion.
|
Shubham Ghoshal answered |
Red Black Tree with n nodes has height <= 2Log2(n+1) AVL Tree with n nodes has height less than Logφ(√5(n+2)) - 2. Therefore, the AVL trees are more balanced compared to Red Black Trees, but they may cause more rotations during insertion and deletion. So if your application involves many frequent insertions and deletions, then Red Black trees should be preferred. And if the insertions and deletions are less frequent and search is more frequent operation, then AVL tree should be preferred over Red Black Tree.
How many real links are required to store a sparse matrix of 10 rows, 10 columns, and 15 non-zero entries, (Pick up the closest answer)- a)15
- b)20
- c)50
- d)100
Correct answer is option 'A'. Can you explain this answer?
How many real links are required to store a sparse matrix of 10 rows, 10 columns, and 15 non-zero entries, (Pick up the closest answer)
a)
15
b)
20
c)
50
d)
100
|
|
Ipsita Dasgupta answered |
Matrix of 10 rows and 10 columns can have m axim um 1 0 x 1 0 = 100 entries. S ince only 15 non-zero entries are present, so number of real link will be 15 only.
Assuming undirected graph.
Assuming undirected graph.
Consider the same recursive C function that takes two arguments
Q. What is the return value of the function foo when it is called as foo(513, 2)?- a)9
- b)8
- c)5
- d)2
Correct answer is option 'D'. Can you explain this answer?
Consider the same recursive C function that takes two arguments
Q. What is the return value of the function foo when it is called as foo(513, 2)?
a)
9
b)
8
c)
5
d)
2
|
Yash Patel answered |
foo(513, 2) will return 1 + foo(256, 2). All subsequent recursive calls (including foo(256, 2)) will return 0 + foo(n/2, 2) except the last call foo(1, 2). The last call foo(1, 2) returns 1. So, the value returned by foo(513, 2) is 1 + 0 + 0…. + 0 + 1. The function foo(n, 2) basically returns sum of bits (or count of set bits) in the number n.
Consider the following statements:
(i) First-in-first out types of computations are efficiently supported by STACKS.
(ii) Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations.
(iii) Implementing QUEUES on a circular array is more efficient than implementing QUEUES, on a linear array with twg indices.
(iv) Last-in-first-out type of computations are efficiency supported by QUEUES.- a)(ii), (iii) are true
- b)(i), (ii) are true
- c)(iii), (iv) are true
- d)(ii), (iv) are true
Correct answer is option 'A'. Can you explain this answer?
Consider the following statements:
(i) First-in-first out types of computations are efficiently supported by STACKS.
(ii) Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations.
(iii) Implementing QUEUES on a circular array is more efficient than implementing QUEUES, on a linear array with twg indices.
(iv) Last-in-first-out type of computations are efficiency supported by QUEUES.
(i) First-in-first out types of computations are efficiently supported by STACKS.
(ii) Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations.
(iii) Implementing QUEUES on a circular array is more efficient than implementing QUEUES, on a linear array with twg indices.
(iv) Last-in-first-out type of computations are efficiency supported by QUEUES.
a)
(ii), (iii) are true
b)
(i), (ii) are true
c)
(iii), (iv) are true
d)
(ii), (iv) are true
|
|
Arpita Mehta answered |
Stack is UFO system so FIFO not supported by stack hence option statement 1 is incorrect and queue is using FIFO so statement 4 is also wrong.
A binary search tree is generated by inserting in order of the following integers: 50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24. The number of nodes in the left subtree and right subtree of the root respectively is- a)(4, 7)
- b)(7,4)
- c)(8,3)
- d)(3,8)
Correct answer is option 'B'. Can you explain this answer?
A binary search tree is generated by inserting in order of the following integers: 50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24. The number of nodes in the left subtree and right subtree of the root respectively is
a)
(4, 7)
b)
(7,4)
c)
(8,3)
d)
(3,8)
|
Saanvi Mishra answered |
Explanation:
To determine the number of nodes in the left subtree and right subtree of the root, we need to construct the binary search tree using the given integers.
Step 1: Insert the first integer, 50, as the root of the tree.
```
50
```
Step 2: Insert the second integer, 15. Since 15 is less than 50, it becomes the left child of 50.
```
50
/
15
```
Step 3: Insert the third integer, 62. Since 62 is greater than 50, it becomes the right child of 50.
```
50
/ \
15 62
```
Step 4: Insert the fourth integer, 5. Since 5 is less than 50 and less than 15, it becomes the left child of 15.
```
50
/ \
15 62
/
5
```
Step 5: Insert the fifth integer, 20. Since 20 is greater than 15 and less than 50, it becomes the right child of 15.
```
50
/ \
15 62
/ \
5 20
```
Step 6: Insert the sixth integer, 58. Since 58 is less than 62 and greater than 50, it becomes the left child of 62.
```
50
/ \
15 62
/ \ /
5 20 58
```
Step 7: Insert the seventh integer, 91. Since 91 is greater than 62, it becomes the right child of 62.
```
50
/ \
15 62
/ \ / \
5 20 58 91
```
Step 8: Insert the eighth integer, 3. Since 3 is less than 50, 15, and 5, it becomes the left child of 5.
```
50
/ \
15 62
/ \ / \
5 20 58 91
/
3
```
Step 9: Insert the ninth integer, 8. Since 8 is greater than 5 and less than 15, it becomes the right child of 5.
```
50
/ \
15 62
/ \ / \
5 20 58 91
/ \
3 8
```
Step 10: Insert the tenth integer, 37. Since 37 is greater than 20 and less than 50, it becomes the right child of 20.
```
50
/ \
15 62
/ \ / \
5 20 58 91
/ \
8 37
```
Step 11: Insert the eleventh integer, 60. Since 60 is greater than 58 and less than 62, it becomes the right child of 58.
To determine the number of nodes in the left subtree and right subtree of the root, we need to construct the binary search tree using the given integers.
Step 1: Insert the first integer, 50, as the root of the tree.
```
50
```
Step 2: Insert the second integer, 15. Since 15 is less than 50, it becomes the left child of 50.
```
50
/
15
```
Step 3: Insert the third integer, 62. Since 62 is greater than 50, it becomes the right child of 50.
```
50
/ \
15 62
```
Step 4: Insert the fourth integer, 5. Since 5 is less than 50 and less than 15, it becomes the left child of 15.
```
50
/ \
15 62
/
5
```
Step 5: Insert the fifth integer, 20. Since 20 is greater than 15 and less than 50, it becomes the right child of 15.
```
50
/ \
15 62
/ \
5 20
```
Step 6: Insert the sixth integer, 58. Since 58 is less than 62 and greater than 50, it becomes the left child of 62.
```
50
/ \
15 62
/ \ /
5 20 58
```
Step 7: Insert the seventh integer, 91. Since 91 is greater than 62, it becomes the right child of 62.
```
50
/ \
15 62
/ \ / \
5 20 58 91
```
Step 8: Insert the eighth integer, 3. Since 3 is less than 50, 15, and 5, it becomes the left child of 5.
```
50
/ \
15 62
/ \ / \
5 20 58 91
/
3
```
Step 9: Insert the ninth integer, 8. Since 8 is greater than 5 and less than 15, it becomes the right child of 5.
```
50
/ \
15 62
/ \ / \
5 20 58 91
/ \
3 8
```
Step 10: Insert the tenth integer, 37. Since 37 is greater than 20 and less than 50, it becomes the right child of 20.
```
50
/ \
15 62
/ \ / \
5 20 58 91
/ \
8 37
```
Step 11: Insert the eleventh integer, 60. Since 60 is greater than 58 and less than 62, it becomes the right child of 58.
Which of the following comments are not true?
1. C provides no input-output features
2. C provides no file access features
3. C borrowed most of its ideas from BCPL
4. C provides no features to manipulate composite objects- a)1 only
- b)1,2 and 3
- c)1,2,3 and 4
- d)None of these
Correct answer is option 'D'. Can you explain this answer?
Which of the following comments are not true?
1. C provides no input-output features
2. C provides no file access features
3. C borrowed most of its ideas from BCPL
4. C provides no features to manipulate composite objects
1. C provides no input-output features
2. C provides no file access features
3. C borrowed most of its ideas from BCPL
4. C provides no features to manipulate composite objects
a)
1 only
b)
1,2 and 3
c)
1,2,3 and 4
d)
None of these
|
|
Gargi Menon answered |
BCPL: Basic Combined Programming Language primary used for system software and called simply B.
A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is- a)log2n
- b)n - 1
- c)n
- d)2n
Correct answer is option 'B'. Can you explain this answer?
A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is
a)
log2n
b)
n - 1
c)
n
d)
2n
|
Rounak Chavan answered |
Because for 2 degree node, every time ‘2’ leafs are added and number of nodes increases is '1'. So number of nodes with degree 2 is always one less than number f leafs present in tree.
Consider the following program of ‘C’
main ( )
{
static int a [ ] = { 1, 2, 3, 4, 5, 6, 7, 8 } ;
int i;
for(i = 2; I < 6; ++i)
a [a [i] ] = a [i];
for (I = 0; I < 8 ; ++i)
printf (“%d”, a[i]);
}
The output of the program is :- a)1 2 3 4 5 6 7 8
- b)1 2 3 3 5 5 7 8
- c)1 2 2 3 3 4 4 8
- d)None of the above
Correct answer is option 'B'. Can you explain this answer?
Consider the following program of ‘C’
main ( )
{
static int a [ ] = { 1, 2, 3, 4, 5, 6, 7, 8 } ;
int i;
for(i = 2; I < 6; ++i)
a [a [i] ] = a [i];
for (I = 0; I < 8 ; ++i)
printf (“%d”, a[i]);
}
The output of the program is :
main ( )
{
static int a [ ] = { 1, 2, 3, 4, 5, 6, 7, 8 } ;
int i;
for(i = 2; I < 6; ++i)
a [a [i] ] = a [i];
for (I = 0; I < 8 ; ++i)
printf (“%d”, a[i]);
}
The output of the program is :
a)
1 2 3 4 5 6 7 8
b)
1 2 3 3 5 5 7 8
c)
1 2 2 3 3 4 4 8
d)
None of the above
|
|
Sudhir Patel answered |
Array a
for(I = 2; I < 6; ++i) // initially i = 2 and 2< 6(true)
a [a [i] ] = a [i];
Iteration 1:
i = 2;
a[a[2]] = a[2]
a[3] = [3]
for(I = 2; I < 6; ++i) // initially i = 2 and 2< 6(true)
a [a [i] ] = a [i];
Iteration 1:
i = 2;
a[a[2]] = a[2]
a[3] = [3]
Iteration 2:
When i = 3, 3 < 6 (true)
a[a[3]] = a[3]
a[3] = 3 // as in iteration 1, a[3] becomes was 3
When i = 3, 3 < 6 (true)
a[a[3]] = a[3]
a[3] = 3 // as in iteration 1, a[3] becomes was 3
Iteration 3:
When i = 4
a[a[4]] = a[4]
a[5] = 5
When i = 4
a[a[4]] = a[4]
a[5] = 5
Iteration 4:
When i = 5, 5 < 6 (true)
a[a[5]] = a[5]
a[5] = 5 // as in iteration 3 a[5] becomes 5.
In next iteration i becomes and condition 6 < 6 false here.
Content of array A are as follows:
Finally, it prints: 1 2 3 3 5 5 7 8
When i = 5, 5 < 6 (true)
a[a[5]] = a[5]
a[5] = 5 // as in iteration 3 a[5] becomes 5.
In next iteration i becomes and condition 6 < 6 false here.
Content of array A are as follows:
Finally, it prints: 1 2 3 3 5 5 7 8
The smallest element of an array’s index is called its- a)Lower bound
- b)Upper bound
- c)Range
- d)Extraction
Correct answer is option 'A'. Can you explain this answer?
The smallest element of an array’s index is called its
a)
Lower bound
b)
Upper bound
c)
Range
d)
Extraction
|
|
Rajesh Malik answered |
Smallest element of an array’s index is called its LOWER BOUND and largest array index is called its UPPER bound.
If p is pointer to an integer and t is a pointer to a character then size of (p) will be- a)Same as that of size of (t)
- b)Greater than that of size of (t)
- c)Less than that of size of (t)
- d)None of the above
Correct answer is option 'A'. Can you explain this answer?
If p is pointer to an integer and t is a pointer to a character then size of (p) will be
a)
Same as that of size of (t)
b)
Greater than that of size of (t)
c)
Less than that of size of (t)
d)
None of the above
|
Shraddha Iyer answered |
Pointer to an integer and pointer to a character are equivalent when the context of size of operator is used.
Which is valid C expression?- a)int my_num = 100,000;
- b)int my_num = 100000;
- c)int my num = 1000;
- d)int $my_num = 10000;
Correct answer is option 'B'. Can you explain this answer?
Which is valid C expression?
a)
int my_num = 100,000;
b)
int my_num = 100000;
c)
int my num = 1000;
d)
int $my_num = 10000;
|
|
Shalini Chopra answered |
Valid C Expression
In C programming language, an expression is a combination of values, variables, operators, and functions that are evaluated to a single value. A valid C expression follows the syntax and rules of the C language.
Out of the given options, only option 'B' is a valid C expression.
Explanation
Let's understand why option 'B' is a valid C expression and why the other options are not valid.
a) int my_num = 100,000;
- This expression contains a comma (,) between 100 and 000, which is not allowed in C.
- In C, the comma operator is used to separate expressions, not to separate digits in a number.
- Therefore, this expression is not valid.
b) int my_num = 100000;
- This expression is valid because it follows the syntax and rules of C.
- It assigns the value 100000 to the variable 'my_num' of integer data type.
c) int my num = 1000;
- This expression contains a space between 'my' and 'num', which is not allowed in C.
- In C, variable names cannot contain spaces or special characters other than underscore (_).
- Therefore, this expression is not valid.
d) int $my_num = 10000;
- This expression starts with a special character '$', which is allowed in C but not recommended.
- In C, variable names should start with a letter or underscore, not a special character.
- Therefore, this expression is valid but not recommended.
Conclusion
Option 'B' is the only valid C expression out of the given options because it follows the syntax and rules of C. Other options contain syntax errors or violate the rules of C. It is important to write valid C expressions to avoid errors and unexpected behavior in the program.
In C programming language, an expression is a combination of values, variables, operators, and functions that are evaluated to a single value. A valid C expression follows the syntax and rules of the C language.
Out of the given options, only option 'B' is a valid C expression.
Explanation
Let's understand why option 'B' is a valid C expression and why the other options are not valid.
a) int my_num = 100,000;
- This expression contains a comma (,) between 100 and 000, which is not allowed in C.
- In C, the comma operator is used to separate expressions, not to separate digits in a number.
- Therefore, this expression is not valid.
b) int my_num = 100000;
- This expression is valid because it follows the syntax and rules of C.
- It assigns the value 100000 to the variable 'my_num' of integer data type.
c) int my num = 1000;
- This expression contains a space between 'my' and 'num', which is not allowed in C.
- In C, variable names cannot contain spaces or special characters other than underscore (_).
- Therefore, this expression is not valid.
d) int $my_num = 10000;
- This expression starts with a special character '$', which is allowed in C but not recommended.
- In C, variable names should start with a letter or underscore, not a special character.
- Therefore, this expression is valid but not recommended.
Conclusion
Option 'B' is the only valid C expression out of the given options because it follows the syntax and rules of C. Other options contain syntax errors or violate the rules of C. It is important to write valid C expressions to avoid errors and unexpected behavior in the program.
A binary search tree contains the numbers 1,2, 3, 4, 5, 6, 7, 8, When the tree is traversed in preorder and the values in each node printed out, the sequence of values obtained is 5, 3,1, 2, 4, 6, 8, 7. If the tree is traversed in postorder, the sequence obtained would be- a)8, 7, 6, 5, 4, 3, 2, 1
- b)1, 2, 3, 4, 8, 7, 6, 5
- c)2, 1, 4, 3, 6, 7, 8, 5
- d)2, 1, 4, 3, 7, 8, 6, 5
Correct answer is option 'D'. Can you explain this answer?
A binary search tree contains the numbers 1,2, 3, 4, 5, 6, 7, 8, When the tree is traversed in preorder and the values in each node printed out, the sequence of values obtained is 5, 3,1, 2, 4, 6, 8, 7. If the tree is traversed in postorder, the sequence obtained would be
a)
8, 7, 6, 5, 4, 3, 2, 1
b)
1, 2, 3, 4, 8, 7, 6, 5
c)
2, 1, 4, 3, 6, 7, 8, 5
d)
2, 1, 4, 3, 7, 8, 6, 5
|
|
Navya Menon answered |
How many distinct binary search trees can be created out of 4 distinct keys?- a)5
- b)14
- c)24
- d)35
Correct answer is option 'B'. Can you explain this answer?
How many distinct binary search trees can be created out of 4 distinct keys?
a)
5
b)
14
c)
24
d)
35
|
Akanksha Chauhan answered |
Total number of distinct binary search tree with n nodes (key)
Which of the following is false?- a)Address is the numeric value associated with a memory location.
- b)Two variables can have the same address.
- c)Address is bound to a variable by the compiler.
- d)Value of a variable can be an address.
Correct answer is option 'C'. Can you explain this answer?
Which of the following is false?
a)
Address is the numeric value associated with a memory location.
b)
Two variables can have the same address.
c)
Address is bound to a variable by the compiler.
d)
Value of a variable can be an address.
|
Kavya Mukherjee answered |
Since address to some of the variable assigned at run time which is assigned by operating system. Two variable can have same address at different instance of time.
Which one of the following is an application of Queue Data Structure?- a)When a resource is shared among multiple consumers.
- b)When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes
- c)Load Balancing
- d)All of the above
Correct answer is option 'D'. Can you explain this answer?
Which one of the following is an application of Queue Data Structure?
a)
When a resource is shared among multiple consumers.
b)
When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes
c)
Load Balancing
d)
All of the above
|
Arshiya Mehta answered |
All of the given options (a, b, c, and d) are applications of the Queue data structure.
A queue is a linear data structure that stores data in a first-in-first-out (FIFO) order. It is a useful data structure for implementing certain algorithms and solving certain problems, such as the following:
When a resource is shared among multiple consumers (option a): A queue can be used to manage access to a shared resource, such as a printer or a network connection. Multiple consumers can add requests to the queue, and the resource can be allocated to the requests in the order they were added to the queue.
When data is transferred asynchronously between two processes (option b): A queue can be used to store data that is transferred between two processes, such as a producer and a consumer. The producer can add data to the queue, and the consumer can retrieve the data from the queue in the order it was added. This allows the two processes to operate independently and at their own pace, without the need for synchronization.
Load balancing (option c): A queue can be used to distribute workload among multiple servers or processors in a load-balancing algorithm. Multiple tasks can be added to the queue, and the servers or processors can take tasks from the queue in the order they were added. This allows the workload to be distributed evenly among the servers or processors, improving the overall performance and scalability of the system.
Therefore, the correct answer is option D, as all of the given options (a, b, c, and d) are applications of the Queue data structure.
In delete operation of BST, we need inorder successor (or predecessor) of a node when the node to be deleted has both left and right child as non-empty. Which of the following is true about inorder successor needed in delete operation?- a)Inorder Successor is always a leaf node
- b)Inorder successor is always either a leaf node or a node with empty left child
- c)Inorder successor may be an ancestor of the node
- d)Inorder successor is always either a leaf node or a node with empty right child
Correct answer is option 'B'. Can you explain this answer?
In delete operation of BST, we need inorder successor (or predecessor) of a node when the node to be deleted has both left and right child as non-empty. Which of the following is true about inorder successor needed in delete operation?
a)
Inorder Successor is always a leaf node
b)
Inorder successor is always either a leaf node or a node with empty left child
c)
Inorder successor may be an ancestor of the node
d)
Inorder successor is always either a leaf node or a node with empty right child
|
Deepika Choudhary answered |
Explanation:
When we delete a node from Binary Search Tree (BST), we need an inorder successor (or predecessor) of a node when the node to be deleted has both left and right child as non-empty. The inorder successor is the next larger node in the BST after the node to be deleted.
The statement "Inorder successor is always either a leaf node or a node with empty left child" is true about inorder successor needed in delete operation. This can be explained as follows:
- Inorder Successor can be a leaf node: If the node to be deleted has no right child, then its inorder successor will be the leftmost leaf node in its right subtree. This is because the leftmost leaf node in the right subtree will be the next larger node in the BST after the node to be deleted.
- Inorder successor can be a node with empty left child: If the node to be deleted has a right child, then its inorder successor will be the smallest node in its right subtree that has an empty left child. This is because the smallest node in the right subtree that has an empty left child will be the next larger node in the BST after the node to be deleted.
Therefore, in both cases, the inorder successor can be either a leaf node or a node with an empty left child. It is not necessary that the inorder successor is always a leaf node, as it can also be an internal node with an empty left child.
Conclusion:
Hence, the correct option is B, which states that "Inorder successor is always either a leaf node or a node with empty left child".
When we delete a node from Binary Search Tree (BST), we need an inorder successor (or predecessor) of a node when the node to be deleted has both left and right child as non-empty. The inorder successor is the next larger node in the BST after the node to be deleted.
The statement "Inorder successor is always either a leaf node or a node with empty left child" is true about inorder successor needed in delete operation. This can be explained as follows:
- Inorder Successor can be a leaf node: If the node to be deleted has no right child, then its inorder successor will be the leftmost leaf node in its right subtree. This is because the leftmost leaf node in the right subtree will be the next larger node in the BST after the node to be deleted.
- Inorder successor can be a node with empty left child: If the node to be deleted has a right child, then its inorder successor will be the smallest node in its right subtree that has an empty left child. This is because the smallest node in the right subtree that has an empty left child will be the next larger node in the BST after the node to be deleted.
Therefore, in both cases, the inorder successor can be either a leaf node or a node with an empty left child. It is not necessary that the inorder successor is always a leaf node, as it can also be an internal node with an empty left child.
Conclusion:
Hence, the correct option is B, which states that "Inorder successor is always either a leaf node or a node with empty left child".
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)6
- b)7
- c)8
- d)9
Correct answer is option 'C'. Can you explain this answer?
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)
6
b)
7
c)
8
d)
9
|
|
Rajesh Malik answered |
here node with integer 1 has to be at root only. Now for maximum depth of the tree the following arrangement can be taken. Take root as level 1. make node 2 at level 2 as a child node of node 1. make node 3 at level 3 as the child node of node 2. .. .. and so on for nodes 4,5,6,7 .. make node 8 at level 8 as the child node of node 7. make node 9 at level 9 as the child node of node 8. Putting other nodes properly, this arrangement of the the complete binary tree will follow the property of min heap. So total levels are 9. node 9 is at level 9 and depth of node 9 is 8 from the root.
What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.- a)2
- b)3
- c)4
- d)5
Correct answer is option 'B'. Can you explain this answer?
What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.
a)
2
b)
3
c)
4
d)
5
|
Bijoy Iyer answered |
AVL trees are binary trees with the following restrictions. 1) the height difference of the children is at most 1. 2) both children are AVL trees Following is the most unbalanced AVL tree that we can get with 7 nodes
What is the time complexity of Build Heap operation. Build Heap is used to build a max(or min) binary heap from a given array. Build Heap is used in Heap Sort as a first step for sorting.- a)O(nLogn)
- b)O(n^2)
- c)O(Logn)
- d)O(n)
Correct answer is option 'D'. Can you explain this answer?
What is the time complexity of Build Heap operation. Build Heap is used to build a max(or min) binary heap from a given array. Build Heap is used in Heap Sort as a first step for sorting.
a)
O(nLogn)
b)
O(n^2)
c)
O(Logn)
d)
O(n)
|
Shubham Das answered |
Following is algorithm for building a Heap of an input array A.
BUILD-HEAP(A)
heapsize := size(A);
for i := floor(heapsize/2) downto 1
do HEAPIFY(A, i);
end for
END
heapsize := size(A);
for i := floor(heapsize/2) downto 1
do HEAPIFY(A, i);
end for
END
Although the worst case complexity looks like O(nLogn), upper bound of time complexity is O(n).
What does the following function do?
int fun(int x, int y)
{
if (y == 0) return 0;
return (x + fun(x, y-1));- a)x + y
- b)x + x*y
- c)x*y
- d)xy
Correct answer is option 'C'. Can you explain this answer?
What does the following function do?
int fun(int x, int y)
{
if (y == 0) return 0;
return (x + fun(x, y-1));
int fun(int x, int y)
{
if (y == 0) return 0;
return (x + fun(x, y-1));
a)
x + y
b)
x + x*y
c)
x*y
d)
xy
|
|
Sanya Agarwal answered |
The function adds x to itself y times which is x*y.
While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is- a)65
- b)67
- c)69
- d)83
Correct answer is option 'B'. Can you explain this answer?
While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is
a)
65
b)
67
c)
69
d)
83
|
Aniket Kulkarni answered |
Here is The Insertion Algorithm For a Binary Search Tree :
Insert(Root,key)
{
if(Root is NULL)
Create a Node with value as key and return
Else if(Root.key <= key) Insert(Root.left,key)
Else
Insert(Root.right,key)
}
{
if(Root is NULL)
Create a Node with value as key and return
Else if(Root.key <= key) Insert(Root.left,key)
Else
Insert(Root.right,key)
}
Creating the BST one by one using the above algorithm in the below given image :
An advantage of chained hash table (external hashing) over the open addressing scheme is- a)Worst case complexity of search operations is less
- b)Space used is less
- c)Deletion is easier
- d)None of the above
Correct answer is option 'C'. Can you explain this answer?
An advantage of chained hash table (external hashing) over the open addressing scheme is
a)
Worst case complexity of search operations is less
b)
Space used is less
c)
Deletion is easier
d)
None of the above
|
Pritam Chatterjee answered |
Deletion is easier, because chained hash table uses linked list
You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2, ..., n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?- a)O(Logn)
- b)O(n)
- c)O(nLogn)
- d)none of the above, as the tree cannot be uniquely determined.
Correct answer is option 'B'. Can you explain this answer?
You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2, ..., n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?
a)
O(Logn)
b)
O(n)
c)
O(nLogn)
d)
none of the above, as the tree cannot be uniquely determined.
|
Sandeep Majumdar answered |
One important thing to note is, it is Binary Search Tree, not Binary Tree. In BST, inorder traversal can always be obtained by sorting all keys.
Consider a hash function that distributes keys uniformly. The hash table size is 20. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed 0.5.- a)5
- b)6
- c)7
- d)10
Correct answer is option 'B'. Can you explain this answer?
Consider a hash function that distributes keys uniformly. The hash table size is 20. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed 0.5.
a)
5
b)
6
c)
7
d)
10
|
Swara Basak answered |
Probability of hashed 1st key = 20/20 = 1
Probability of hashed 2nd key with no collision = 19/20
Probability of hashed 3rd key with no collision = 18/20
Similarly, probability of hashed rth key with no collision
According to question: Probability of hashed (n + 1)th key with collision > 0.5 Probability of hashed (n + 1)th key with collision
P(C) = 1 - P (Till (nth) no collision)
19 x 18 x 17 .... x 20 - n + 1 < 0.5 x (20)n-1
By put n = 5, we get 0.581, for n = 6, we get 0.436, which satisfies the equation.
Probability of hashed 2nd key with no collision = 19/20
Probability of hashed 3rd key with no collision = 18/20
Similarly, probability of hashed rth key with no collision
According to question: Probability of hashed (n + 1)th key with collision > 0.5 Probability of hashed (n + 1)th key with collision
P(C) = 1 - P (Till (nth) no collision)
19 x 18 x 17 .... x 20 - n + 1 < 0.5 x (20)n-1
By put n = 5, we get 0.581, for n = 6, we get 0.436, which satisfies the equation.
Chapter doubts & questions for Programming & Data Structures - Question Bank for GATE Computer Science Engineering 2025 is part of Computer Science Engineering (CSE) exam preparation. The chapters have been prepared according to the Computer Science Engineering (CSE) exam syllabus. The Chapter doubts & questions, notes, tests & MCQs are made for Computer Science Engineering (CSE) 2025 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests here.
Chapter doubts & questions of Programming & Data Structures - Question Bank for GATE Computer Science Engineering in English & Hindi are available as part of Computer Science Engineering (CSE) exam.
Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Question Bank for GATE Computer Science Engineering
63 videos|8 docs|165 tests
|
Signup to see your scores go up within 7 days!
Study with 1000+ FREE Docs, Videos & Tests
10M+ students study on EduRev
|
© EduRev
|
Education Revolution
|
|
Signup to see your scores
go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup