# Recent questions and answers in Programming and DS

60 votes
11 answers
1
Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly $4$ nodes is $O(n^a\log^bn)$. Then the value of $a+10b$ is __________.
55 votes
6 answers
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 _________.
1 vote
1 answer
3
Consider the following C program segment: struct node What is the output of above C program when it runs on a root node of a binary tree? prints nodes at K distance from root node. print nodes of Kth level of binary tree. Both (a) and (b) None of these
1 vote
3 answers
4
Consider 3 dimensional Array A[90] [30] [40] stored in linear array in column major order. If the base address starts at 10. The location of A[20] [20] [30] is __________ . [Assume the first element is stored at A[1][1][1] and each element take 1 B].
2 votes
1 answer
5
Consider 3 dimensional Array A[90] [30] [40] stored in linear array in column major order. If the base address starts at 10, The location of A [20] [20] [30] is ________. (Assume the first element is stored at A[1][1][1] and each element take 1 memory location)
10 votes
5 answers
6
Choose the correct alternatives (More than one may be correct). The total external path length, EPL, of a binary tree with $n$ external nodes is, $EPL= \sum_{w} Iw$, where $I_{w}$ is the path length of external node $w$), $\leq n^{2}$ always. $\geq n \log_{2} n$ always. Equal to $n^{2}$ always. $O(n)$ for some special trees.
15 votes
8 answers
7
In a complete $k$-ary tree, every internal node has exactly $k$ children. The number of leaves in such a tree with $n$ internal node is: $nk$ $(n-1)k + 1$ $n(k-1) +1$ $n(k-1)$
22 votes
3 answers
8
Consider the program where $a, b$ are integers with $b > 0$. x:=a; y:=b; z:=0; while y > 0 do if odd (x) then z:= z + x; y:= y - 1; else y:= y % 2; x:= 2 * x; fi Invariant of the loop is a condition which is true before and after every ... will not terminate for some values of $a, b$ but when it does terminate, the condition $z = a * b$ will hold. The program will terminate with $z=a^{b}$
33 votes
6 answers
9
Consider the following C program segment. # include <stdio.h> int main() { char s1[7] = "1234", *p; p = s1 + 2; *p = '0'; printf("%s", s1); } What will be printed by the program? $12$ $120400$ $1204$ $1034$
30 votes
7 answers
10
Let $T$ be a tree with $10$ vertices. The sum of the degrees of all the vertices in $T$ is ________
5 votes
3 answers
11
1.Linear Probing suffers from both primary and secondary clustering. true or false? 2. Quadratic Probing suffers from both primary and secondary clustering. true or false?
16 votes
4 answers
12
The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height $5$ are $63$ and $6$, respectively $64$ and $5$, respectively $32$ and $6$, respectively $31$ and $5$, respectively
4 votes
4 answers
13
Indicate results of the following program if the language uses i)Static scope rule and ii) Dynamic scope rules (GATE-1989) var x,y:integer; procedure A(var z:integer); var x:integer; begin x:=1; B; z:=x; end; procedure B; begin x:=x+1; end; begin x:=5; A(y); write(y) end;
24 votes
5 answers
14
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; } } Suppose we modify the above function $foo()$ ... modification the time complexity for function $foo()$ is significantly reduced. The space complexity of the modified function would be: $O(1)$ $O(n)$ $O(n^2)$ $n!$
93 votes
11 answers
15
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 _______.
31 votes
5 answers
16
In a binary max heap containing $n$ numbers, the smallest element can be found in time $O(n)$ $O(\log n)$ $O(\log \log n)$ $O(1)$
0 votes
2 answers
17
A complete $n$-ary tree is a tree in which each node has $n$ children or no children. Let $I$ be the number of internal nodes and $L$ be the number of leaves in a complete $n$-ary tree. If $L=41$, and $I=10$, what is the value of $n$? $3$ $4$ $5$ $6$
2 votes
2 answers
18
In a binary max heap containing $n$ numbers, the smallest element can be found in ______ $O(n)$ $O(\log _2 n)$ $O(1)$ $O(\log_2 \log_2 n)$
41 votes
5 answers
19
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 votes
5 answers
20
Consider the following program: int f (int * p, int n) { if (n <= 1) return 0; else return max (f (p+1, n-1), p[0] - p[1]); } int main () { int a[] = {3, 5, 2, 6, 4}; print f(" %d", f(a, 5)); } Note: $max (x, y)$ returns the maximum of $x$ and $y$. The value printed by this program is ________.
74 votes
9 answers
21
Consider the following C program. #include<stdio.h> #include<string.h> void printlength(char *s, char *t) { unsigned int c=0; int len = ((strlen(s) - strlen(t)) > c) ? strlen(s) : strlen(t); printf("%d\n", len); } void main() { char *x = "abc"; ... that $strlen$ is defined in $string.h$ as returning a value of type $size\_t$, which is an unsigned int. The output of the program is __________ .
24 votes
13 answers
22
Consider the following function implemented in C: void printxy(int x, int y) { int *ptr; x=0; ptr=&x; y=*ptr; *ptr=1; printf(“%d, %d”, x, y); } The output of invoking $printxy(1,1)$ is: $0, 0$ $0, 1$ $1, 0$ $1, 1$
14 votes
4 answers
23
Consider the following function definition. void greet(int n) { if(n>0) { printf("hello"); greet(n-1); } printf("world"); } If you run greet(n) for some non-negative integer n, what would it print? n times "hello", followed by n+1 times "world" n times "hello", followed by n times "world" n times "helloworld" n+1 times "helloworld" n times "helloworld", followed by "world"
27 votes
4 answers
24
Let $a$ be an array containing $n$ integers in increasing order. The following algorithm determines whether there are two distinct numbers in the array whose difference is a specified number $S > 0$. i = 0; j = 1; while (j < n ){ if (E) j++; else if (a[j] - a[i] == S) break; else i++; } if (j < n) printf ... expression for E. $a[j] - a[i] > S$ $a[j] - a[i] < S$ $a[i] - a[j] < S$ $a[i] - a[j] > S$
30 votes
10 answers
25
Let $T$ be a full binary tree with $8$ leaves. (A full binary tree has every level full.) Suppose two leaves $a$ and $b$ of $T$ are chosen uniformly and independently at random. The expected value of the distance between $a$ and $b$ in $T$ (ie., the number of edges in the unique path between $a$ and $b$) is (rounded off to $2$ decimal places) _________.
120 votes
11 answers
26
When searching for the key value $60$ in a binary search tree, nodes containing the key values $10, 20, 40, 50, 70, 80, 90$ are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root to the node containing the value $60$? $35$ $64$ $128$ $5040$
1 vote
1 answer
27
The height h of an AVL tree with n nodes lies in the interval: 1. log2(n+1) ≤ h < c log2(n+2)+b 2. log10(n) ≤ h < c log10(n+1)+b 3. log10(n+1) ≤ h < c log10(n+2)+b 4. log2(n) ≤ h < c log2(n+1)+b
2 votes
1 answer
28
Consider an initially empty hash table of length 10. Following set of keys are inserted using open addressing with hash function h(k) = kmod 10 and linear probing. The number of different insertion sequence of the key values using the given hash function and linear probing will result ... to send the packet from source to destination with minimum number of hops. D) both b and c. I think it is B).
14 votes
3 answers
29
A $3-\text{ary}$ tree is a tree in which every internal node has exactly three children. Use induction to prove that the number of leaves in a $3-\text{ary}$ tree with $n$ internal nodes is $2(n-1)$.
21 votes
6 answers
30
The value printed by the following program is _______. void f (int * p, int m) { m = m + 5; *p = *p + m; return; } void main () { int i=5, j=10; f (&i, j); print f ("%d", i+j); }
71 votes
8 answers
31
Consider the C functions foo and bar given below: int foo(int val) { int x=0; while(val > 0) { x = x + foo(val--); } return val; } int bar(int val) { int x = 0; while(val > 0) { x= x + bar(val-1); } ... $6$ and $6$ respectively. Infinite loop and abnormal termination respectively. Abnormal termination and infinite loop respectively. Both terminating abnormally.
21 votes
4 answers
32
Consider the following C code. Assume that unsigned long int type length is $64$ bits. unsigned long int fun(unsigned long int n) { unsigned long int i, j=0, sum = 0; for( i=n; i>1; i=i/2) j++; for( ; j>1; j=j/2) sum++; return sum; } The value returned when we call fun with the input $2^{40}$ is: $4$ $5$ $6$ $40$
31 votes
5 answers
33
#include<stdio.h> void fun1(char* s1, char* s2){ char* temp; temp = s1; s1 = s2; s2 = temp; } void fun2(char** s1, char** s2){ char* temp; temp = *s1; *s1 = *s2; *s2 = temp; } int main(){ char *str1="Hi", *str2 = "Bye"; fun1(str1, str2); printf("%s %s", str1, ... 0; } The output of the program above is: $\text{Hi Bye Bye Hi}$ $\text{Hi Bye Hi Bye}$ $\text{Bye Hi Hi Bye}$ $\text{Bye Hi Bye Hi}$
28 votes
9 answers
34
Consider the following C program: #include<stdio.h> struct Ournode{ char x, y, z; }; int main() { struct Ournode p={'1', '0', 'a'+2}; struct Ournode *q=&p; printf("%c, %c", *((char*)q+1), *((char*)q+2)); return 0; } The output of this program is: 0, c 0, a+2 '0', 'a+2' '0', 'c'
1 vote
1 answer
35
Consider the following pseudo-code fragment, where $a$ and $b$ are integer variables that have been initialized: /* Pre-conditions : $(a > 1 \wedge a < b)$ */ /* Assume that overflow never occurs */ int $x=0$; int $p=1$; while $(p<b) \{$ $p=p*a$; $x=x+1$; $\}$ ... $\lfloor \: \: \rfloor$ means floor */ $\lfloor \log_a^b \rfloor$ /* $\lceil \: \: \rceil$ means ceil */
1 vote
1 answer
36
Suppose you are compiling on a machine with $1$-byte chars, $2$-byte shorts, $4$-byte ints, and $8$-byte doubles, and with alignment rules that require the address of every primitive data element to be an integer multiple of the element's size. Suppose further that the compiler is not ... ; double r; int i; } A[10]; /*10 element array of structs */ $150$ bytes $320$ bytes $240$ bytes $200$ bytes
0 votes
1 answer
37
Which of the following statements are true? Minimax search is breadth-first; it processes all the nodes at a level before moving to a node in next level. The effectiveness of the alpha-beta pruning is highly dependent on the order in which the states are examined The alpha-beta search algorithms computes the same ... and $(c)$ only $(a)$ and $(d)$ only $(b)$ and $(c)$ only $(c)$ and $(d)$ only
0 votes
1 answer
38
Match $\text{List I}$ with $\text{List II}$ Let $R_1=\{(1,1), (2,2), (3,3)\}$ and $R_2=\{(1,1), (1,2), (1,3), (1,4)\}$ ... answer from the options given below: $A-I, B-II, C-IV, D-III$ $A-I, B-IV, C-III, D-II$ $A-I, B-III, C-II, D-IV$ $A-I, B-IV, C-II, D-III$
2 votes
0 answers
39
An external variable is globally accessible by all functions has a declaration “extern” associated with it when declared within a function will be initialized to $0$ if not initialized all of these
0 votes
2 answers
40
A hash table with $10$ buckets with one slot per bucket is depicted. The symbols, $S1$ to $S7$ are initially emerged using a hashing function with linear probing. Maximum number of comparisons needed in searching an item that is not present is $6$ $5$ $4$ $3$
To see more, click for all the questions in this category.