# Recent questions and answers in Programming and DS 1
For the given nodes: $89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100$ minimum ______ number of interchanges are required to convert it into a max-heap. $3$ $4$ $5$ $6$
2
The number of binary min. heaps that can be formed from a set of 7 distinct integers is _________?
3
A binary tree with $n > 1$ nodes has $n_1$, $n_2$ and $n_3$ nodes of degree one, two and three respec­tively. The degree of a node is defined as the number of its neighbours. Starting with the above tree, while there remains a node $v$ of degree two in the tree, add an edge between the two ... edges will remain at the end of the process? $2 * n_1- 3$ $n_2 + 2 * n_1 - 2$ $n_3 - n_2$ $n_2+ n_1- 2$
4
Consider a binary tree T that has $200$ leaf nodes. Then the number of nodes in T that have exactly two children are ______.
1 vote
5
Define the height of a binary tree or subtree and also define a height-balanced (AVL) tree.
6
Consider the following operation along with Enqueue and Dequeue operations on queues, where $k$ is a global parameter. MultiDequeue(Q){ m = k while (Q is not empty) and (m > 0) { Dequeue(Q) m = m – 1 } } What is the worst case time complexity of a sequence of $n$ queue operations on an initially empty queue? $Θ(n)$ $Θ(n + k)$ $Θ(nk)$ $Θ(n^2)$
7
Write a constant time algorithm to insert a node with data $D$ just before the node with address $p$ of a singly linked list.
1 vote
8
how many of the following statements is incorrect regarding the time complexity of binary search tree,AVL Tree, min heap, binary tree? i assumed non existent elements are those which do not exists in a tree, acc to me only (a) is incorrect! because to find any element in BST, It takes O(n) time
9
Aliasing in the context of programming languages refers to multiple variables having the same memory location multiple variables having the same value multiple variables having the same identifier multiple uses of the same variable
10
Consider the following program fragment: int d = 0; int i,j,k; for(i=1; i<31; ++i) for(j=1; j<31; ++j) for(k=1; k<31; ++k) if(((i+j+k)%3) == 0) d=d+1; printf("%d",d); The number of additions performed by the above program fragment is? a. 27,000 b. 27,000 x 3 c. 27,000 x 3 + 9,000 d. 9,930 + 2,700 x 3
1 vote
11
For n=2 the P is coming as 3,but none of the option is satisfying?
1 vote
12
Consider the following program segment int main ( ) { char ∗ str = “GATECS”; printf (“%d”, madeeasy (str)); return 0; } int madeeasy (int ∗ p1) { int ∗ p2 = p1; while (∗++p1); return (p1 – p2); } The output of the above program will be ______. Assume that the object of data type int occupies 2 bytes
13
Consider the following pseudo code, where $x$ and $y$ are positive integers. begin q := 0 r := x while r ≥ y do begin r := r - y q := q + 1 end end The post condition that needs to be satisfied after the program terminates is $\{ r = qx + y \wedge r < y\}$ $\{ x = qy + r \wedge r < y\}$ $\{ y = qx + r \wedge 0 < r < y\}$ $\{ q + 1 < r - y \wedge y > 0\}$
14
The maximum number of binary trees that can be formed with three unlabeled nodes is: $1$ $5$ $4$ $3$
15
Consider the following New-order strategy for traversing a binary tree: Visit the root; Visit the right subtree using New-order; Visit the left subtree using New-order; The New-order traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 - 2 ^ 6 7 * 1 + - is given by: ... $1 \ 7 \ 6 * + \ 2 \ 5 \ 4 \ 3 \ * \ - \wedge -$
16
The maximum number of comparisons needed to sort 9 items using radix sort is (assume each item is 5 digit octal number): 45 72 360 450
17
A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let $n$ denote the number of nodes in the queue. Let 'enqueue' be implemented by inserting a new node at the head, and 'dequeue' be implemented by deletion of a ... ? $\Theta(1), \Theta(1)$ $\Theta(1), \Theta(n)$ $\Theta(n), \Theta(1)$ $\Theta(n), \Theta(n)$
1 vote
18
What we can do if the unary operator comes in infix notation while converting it into postfix/prefix notations? For example, this $a = -b+c*d/e+f↑g↑h-i*j$
19
1)The number of min heap trees are possible with 15 elements such that every leaf node must be greater than all non-leaf nodes of the tree are ________. -------------------------------------------------------------------------------------------------------------------------- 2)The number of min heap trees are possible with 15 elements_________________
1 vote
20
Let $A$ be a square matrix of size $n\times n$. Consider the following program. What is the expected output? C=100 for i=1 to n do for j=1 to n do { Temp=A[i][j]+C A[i][j]=A[j][i] A[j][i]=Temp-C } for i=1 to n do for j=1 to n ... ]); The matrix $A$ itself. Transpose of matrix $A$. Adding $100$ to the upper diagonal elements and subtracting $100$ from diagonal elements of $A$. None of the option.
21
A priority queue $Q$ is used to implement a stack that stores characters. PUSH (C) is implemented as INSERT $(Q, C, K)$ where $K$ is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN$(Q)$. For a sequence of operations, the keys chosen are in non-increasing order non-decreasing order strictly increasing order strictly decreasing order
22
A program takes as input a balanced binary search tree with $n$ leaf nodes and computes the value of a function $g(x)$ for each node $x$. If the cost of computing $g(x)$ is: $\Large \min \left ( \substack{\text{number of leaf-nodes}\\\text{in left-subtree of$ ... the worst-case time complexity of the program is? $\Theta (n)$ $\Theta (n \log n)$ $\Theta(n^2)$ $\Theta (n^2\log n)$
23
In the following procedure Integer procedure P(X,Y); Integer X,Y; value x; begin K=5; L=8; P=x+y; end $X$ is called by value and $Y$ is called by name. If the procedure were invoked by the following program fragment K=0; L=0; Z=P(K,L); then the value of $Z$ will be set equal to $5$ $8$ $13$ $0$
24
What is difference between $pop\left ( \right )$,$empty Stack\left ( \right )$,$delete Stack\left ( \right )$? Can all be performed in $O\left ( 1 \right )$ time?
25
Runtime stack doesnot contain (A) Local variables (B) Static Variables (C) Parameter Passed (D) Return Address
26
Let $Q$ denote a queue containing sixteen numbers and $S$ be an empty stack. $Head(Q)$ returns the element at the head of the queue $Q$ without removing it from $Q$. Similarly $Top(S)$ returns the element at the top of $S$ without removing it from $S$. Consider ... ); else x:= Pop(S); Enqueue (Q, x); end end The maximum possible number of iterations of the while loop in the algorithm is _______.
1 vote
27
What will be output if you will compile and execute the following C code? void main() { printf("%d",sizeof(5.2)); } $4$ $8$ $2$ $16$
28
Which of the following is the correct order of evaluation for the below expression? $z=x+y^*z/4\%2-1$ $^*/\%+-=$ $=^*/\%+-$ $/^*\%-+=$ $^*\% /-+=$
29
For a given hash table $T$ with $10$ slots that stores $1000$ elements, the load factor $\alpha$ for $T$ is $100$ $0.01$ $200$ $1.05$
30
double foo(int n) { int i; double sum; if(n == 0) { return 1.0; } else { sum = 0.0; for(i = 0; i < n; i++) { sum += foo(i); } return sum; } } The space complexity of the above code is? $O(1)$ $O(n)$ $O(n!)$ $n^n$
31
In a full binary tree number of nodes is $63$ then the height of the tree is : $2$ $4$ $3$ $6$
32
In binary search tree which traversal is used for getting ascending order values ? Inorder Preorder Postorder None of the options
1 vote
33
Narendra is traveling from point A to point B and there are n toll posts along the way. Before starting the journey, Narendra is given, for each post 1 ≤ i < j ≤ n, the feeto travel from post i to post j. The goal is to minimize the travel cost. The most ... . The answer is given to be (C). Is it like this has been solved using Dijkstra using fibonacci heaps? Am I thinking in correct direction?
1 vote
34
The number of min heap trees are possible with 15 elements such that every leaf node must be greater than all non-leaf nodes of the tree are ________.
35
The function f is defined as follows: int f (int n) { if (n <= 1) return 1; else if (n % 2 == 0) return f(n/2); else return f(3n - 1); } Assuming that arbitrarily large integers can be passed as a parameter to the function, consider the following statements. The ... different values of $n \geq 1$. Which one of the following options is true of the above? i and iii i and iv ii and iii ii and iv
36
The minimum number of interchanges needed to convert the array into a max-heap is $89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70$ $0$ $1$ $2$ $3$
37
Statement for Linked Answer Questions 76 & 77: A $3$-ary max heap is like a binary max heap, but instead of $2$ children, nodes have $3$ children. A $3$-ary heap can be represented by an array as follows: The root is stored in the first location, $a$ ... $10, 9, 4, 5, 7, 6, 8, 2, 1, 3$ $10, 8, 6, 9, 7, 2, 3, 4, 1, 5$
Following declaration of an array of struct, assumes size of byte, short, int and long are $1,2,3$ and $4$ respectively. Alignment rule stipulates that $n$ - byte field must be located at an address divisible by $n$, the fields in the struct are not rearranged, padding is used to ensure ... $8$, what is the total size of $C$, in bytes? $150$ $160$ $200$ $240$
Output of following program? #include<stdio.h> int main() { int *ptr; int x; ptr=&x; *ptr=0; printf("x=%d\n",x); printf("*ptr=%d\n",*ptr); *ptr+=5; printf("x=%d\n",x); printf("*ptr=%d\n",*ptr); (*ptr)++; printf( x=%d\n",x); printf("*ptr=%d\n",*ptr); return 0; } $x=0$ $^*ptr=0$ ... $^*ptr=0$ $x=5$ $^*ptr=5$ $x=$garbage value $^*ptr=$garbage value $x=0$ $^*ptr=0$ $x=0$ $^*ptr=0$ $x=0$ $^*ptr=0$