1. Using what formula can a parent node be located in an array?
(i+1)/2
(i-1)/2
i/2
2i/2
2. Which of the following sorting algorithm is in-place
Counting sort
Radix sort
Bucket sort
None
3. Which of the following sorting algorithms is/are stable
Counting sort
Bucket sort
Radix sort
All of the above
4. What is a complete binary tree?
Each node has exactly zero or two children
A binary tree, which is completely filled, with the possible exception of the bottom level, which is
filled from right to left
A binary tree, which is completely filled, with the possible exception of the bottom level, which is
filled from left to right
A tree In which all nodes have degree 2
5. If we represent binary tree as array,then what would be the formula to find out a left child,if the node is
initialized as i?
2i
2i+1
4i
2i+2
6. How many orders of traversal is needed for a binary tree?
2
0
3
4
7. Suppose we have numbers between 1 and 1000 in a binary search tree and want to search for the
number 363. Which of the following sequence could not be the sequence of the node examined?
2, 252, 401, 398, 330, 344, 397, 363
924, 220, 911, 244, 898, 258, 362, 363
925, 202, 911, 240, 912, 245, 258, 363
2, 399, 387, 219, 266, 382, 381, 278, 363
8. Which of the following is incorrect with respect to binary trees?
Let T be a binary tree. For every k ≥ 0, there are no more than 2k nodes in level k
Let T be a binary tree with λ levels. Then T has no more than 2 λ – 1 nodes
Let T be a binary tree with N nodes. Then the number of levels is at least ceil(log (N + 1))
Let T be a binary tree with N nodes. Then the number of levels is at least floor(log (N + 1))
9. A binary tree is a rooted tree but not an ordered tree.Is this statement true or false?
True
Flase
10. A tree sort is also known as ……… sort.
quick
shell
heap
selection
*******************************************************************************
PROGRAMMING
1. Problem statement
You are given two positive integers n and k. Print the k-th positive integer that is not divisible by n.
For example, if n=3, and k=7, then all numbers that are not divisible by 3 are: 1,2,4,5,7,8,10,11,13…. The 7-th
number among them is 10.
Input Format
The first line contains an integer t — the number of test cases in the input. Next, t test cases are given,
one per line.
Each test case is two positive integers n and k (1≤k≤109).
Constraints
(1≤t≤1000)
(2≤n≤10^9)
Output Format
For each test case print the k-th positive integer that is not divisible by n.
SOLUTION :
PYTHON CODE :
for s in[*open(0)][1:]:n,k=map(int,s.split());print(k+(k-1)//(n-1))
2. Problem statement
Given a binary tree, find its level order traversal. Level order traversal of a tree is breadth-first traversal
for the tree.
Input Format
A single line of input contains string s which contains the node of the tree in level order fashion.'N' in
the string represents NULL node.
A string 5 1 1 2 N N 2 reprsents the tree
5
/ \
1 1
/ \
2 2
Similarly a string 1 2 N 3 N represents the tree
1
/
2
/
3
Constraints
1 ≤ Number of nodes ≤ 10^5 1 ≤ Data of a node ≤ 10^5
Output Format
Print the level order traversal of the given Binary Tree.
SOLUTION :
PYTHON CODE :
a=input().split()
for i in a:
if(i != 'N'):
print(i,end=" ")
3. Problem statement
So, the New Year holidays are over. Santa Claus and his colleagues can take a rest and have guests at
last. When two "New Year and Christmas Men" meet, thear assistants cut out of cardboard the letters
from the guest's name and the host's name in honor of this event. Then the hung the letters above the
main entrance. One night, when everyone went to bed, someone took all the letters of our characters'
names. Then he may have shuffled the letters and put them in one pile in front of the door.
Input Format
The input file consists of three lines: the first line contains the guest's name, the second line contains
the name of the residence host and the third line contains letters in a pile that were found at the door
in the morning. All lines are not empty and contain only uppercase Latin letters.
Constraints
The length of each line does not exceed 100.
Output Format
Print "YES" without the quotes, if the letters in the pile could be permuted to make the names of the
"New Year and Christmas Men". Otherwise, print "NO" without the quotes.
SOLUTION :
PYTHON CODE :
s,i=sorted,input;print('YNEOS'[s(i()+i())!=s(i())::2])
********************************************************************
Post a Comment