Cocubes test questions on datastructures and algorithms:
----------------------------------------------------------------------------
1) Average search time for hashing with linear probing will be less if the load factor
a) is far less than one b) equals one c) is far greater than one d) None of the above
2) In a complete k-ary tree every internal node has exactly k children or no child. The number of leaves in such a tree with N internal nodes is
a) Nk b) (N-1)k+1 c) N(k-1)+1 d) N(k-1)
3) The number of leaf nodes in a complete binary tree of depth d is
a) 2^d b) 2^(d-1) + 1 c) 2^(d+1) + 1 d) 2^d + 1
4) Which of the following statements is/are TRUE for an undirected graph?
P: Number of odd degree vertices is even
Q: Sum of degress of all vertices is even
Options : a) P only b) Q only c) Both P and Q d) Neither P nor Q
5) The following numbers are inserted into an empty binary search tree in the given order : 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree?
(the height of a tree is the maximum distance of a leaf node from the root) ?
Options : a) 2 b)3 c)4 d)6
6) The complexity of multiplying two matrices of order m*n and n*p is of the order
a) m*n*p b) m*p c)m*n d)n*p
7) Let P be a Quicksort Program to sort numbers in ascending order using the first element as pivot. Let t1 and t2 be the number of comparisions made by P for the inputs {1,2,3,4,5} and {4,1,5,3,2} respectively. Which one of the following holds true?
a) t1=5 b) t1 < t2 c) t1>t2 d)t1=t2
8) A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue an deQueue can be performed in constant time ?
Front -----> Node1 ------> Node2 ------------> Rear
^ |
|_________________________________________________|
Options : a) rear node b) front node c)not possible with a single pointer d)node next to front
9) Restriction while using the binary search is
Options : a) List should be similar in number
b) List should be larger in number
c) List should be in sorted order
d) None of these
10) Which of the following sorting methods would the most suitable for sorting list which is almost sorted
Option : a) Bubble sort b)Insertion sort c) Selection sort d) Quick sort
Programming test (4 programming problems to be solved in 75 minutes) from glider.ai
----------------------------------------------------------------------------------------------------------------
1) Find the sum of upper pyramid of a matrix of size (M x N) with M rows and N columns. The matrix is stored in a 1D array
The below is representational purpose of matrix(in 2D) and the elements that contribute to sum. These elements are stored in a 1D array
1 2 3 4 5 elements considered for sum in this row (1,2,3,4,5)
6 7 8 9 10 elements considered for sum in this row (7,8,9)
11 12 13 14 15 elements considered for sum in this row (13)
16 17 18 19 20 elements not considered for sum in this row
2)Find if the given two strings is a permutation of the other
3) Find students with maximum average score of 3 subjects
4) Suppress negative integers in an array without disturbing the sequence of order of occurance.
input : 5, -4, 3, -2, 6, -11, 12, -8, 9
output: 5, 3, 6, 12, 9, -4, -2, -11, -8 (negative numbers moved to end)