Computer Science and Information Technology - Data Structure
Exam Duration: 45 Mins Total Questions : 30
If int s[s] is a one-dimensional array of integers, which of the following refers to the third element in the array?
- (a)
*(s+2)
- (b)
s+3
- (c)
*(s+3)+5
- (d)
*(s+3)+2
maximum number of nodes in a full binary tree of depth (height) 10 is
- (a)
10
- (b)
2047
- (c)
100
- (d)
512
The postfix form of A$B*C-D/E/F(G+H) is=
- (a)
AB$C*D-EF/GH+/+
- (b)
AB$*C-D+EF/GH/+
- (c)
AB$*C+D-EF/GH/*+
- (d)
AB$C-D*EF/GH/++
Evaluate the following postfix notation
A:6,9,2,+*12,3/-
- (a)
62
- (b)
66
- (c)
83
- (d)
None of these
In binary search tree which traversal is used for getting ascending order values
- (a)
Inorder
- (b)
postorder
- (c)
Preorder
- (d)
None of these
In a complete binary tree of n nodes the maximum distance between the nodes is (assume search in the path costs as 1)
- (a)
log2n
- (b)
2log2n
- (c)
log2 n
- (d)
4log2n
In case of the complete binary tree having 10 leaves which one of the following is true?
- (a)
Cannot have more than 19 nodes
- (b)
has exactly 18 nodes
- (c)
Has exactly 17 nodes
- (d)
None of the above
The postfix expression for the infix expression (A+B)*(C+D)/(F+D*E) is
- (a)
(AB+CD+*F)/d+E*
- (b)
(ABCD*+F)/(+DE*+)
- (c)
(A*B+CD)/F*DE++
- (d)
None of the above
The time complexity for evaluating a postfix expression is
- (a)
O(n)
- (b)
O(n log n)
- (c)
O(log n)
- (d)
O(n2)
The correct push function is
- (a)
S\(\rightarrow \)arr [S\(\rightarrow \)top++]=Data
- (b)
S\(\rightarrow \)arr[++S\(\rightarrow \)top]=Data
- (c)
S\(\rightarrow \)arr[++(S\(\rightarrow \)top)]=Data
- (d)
None of the above
Let p be a singly linked list. Let Q be the pointer to an intermediate node X in the list. What is the worst case time complexity of the best known algorithm to delete the node X from the list?
- (a)
O(n)
- (b)
O(log2n)
- (c)
O(log n)
- (d)
O (1)
If we find the prefix polish expression P which is equivalent to E and also find preorder of the tree which is formed from the expression E then which of the following statement is correct?
- (a)
The prefix polish expression P and preorder of E is not equivalent
- (b)
The prefix polish expression P and preorder of E is not equivalent to \(*+2*xy\uparrow -*5a3b\)
- (c)
The prefix polish expression P and preorder to E is not equivalent but its post order is equivalent
- (d)
The prefix polish expression P and preorder of E is equivalent to \(*+2*xy\uparrow -*5ab*3\)
With reference to question 5, find the addition of all the elements from stack and queue.
- (a)
stack=22 , queue=8
- (b)
stack=27 , queue=5
- (c)
stack=22, queue=20
- (d)
None of the above
A linear list in which elements can be added or removed at either end but not in the middle is known as
- (a)
Queue
- (b)
Deque
- (c)
Stack
- (d)
Tree
The most appropriate matching for the following pairs
X, m=malloc(5);m=null 1.using dangling pointers
Y, Free(n);n\(\rightarrow\)value =5 2.using uninitialized pointers
Z, char*P, *P=a 3.lost memory
is
- (a)
X-1 Y-3 Z-3
- (b)
X-2 Y-1 Z-3
- (c)
X-3 Y-2 Z-1
- (d)
X-3 Y-1 Z-2
Among the following which one is not the right operation of deque?
- (a)
Remove the left node from the queue
- (b)
Insert a new node in the left side of queue
- (c)
Insert a new node in the right side of queue
- (d)
Insert a new node in the middle side of queue
The most appropriate matching for the following pairs
X. depth first search 1.Heap
Y. Breadth first search 2.Queue
Z.Soring 3.Stach
- (a)
X-1 Y-2 Z-3
- (b)
X-3 Y-1 Z-2
- (c)
X-3 Y-2 Z-1
- (d)
X-2 Y-3 Z-3
The wrost case complexity for searching an element in binary search tree is
- (a)
(n)
- (b)
O(log n)
- (c)
(n log n)
- (d)
O(n2)
A weight balanced tree is a binary tree in wich for each node, the number of nodes in the left subtree is atlast half and atmost twice the number of nodes in the right sub-tree. The maximum possible height of such a tree on n nodes is best described by which of the following|?
- (a)
log2n
- (b)
\({ log }_{ \frac { 4 }{ 2 } }n\)
- (c)
log3n
- (d)
\({ log }_{ \frac { 3 }{ 2 } }n\)
Let T be a binary search tree with 14 nodes and 60 as the external path length.Then the internal path length is
- (a)
28
- (b)
50
- (c)
32
- (d)
11
Let T be a binary search tree with n nodes can Sa the average number of comparisions required for a successful search and Va be the average number of comparisons required for an unsuccessful search.Then, which of the following relations hold true?
- (a)
\({ S }_{ a }=\frac { \left( { V }_{ a }+n \right) }{ n-1 } \)
- (b)
\(\\ \quad { S }_{ n }=\frac { \left( { V }_{ a }+1 \right) }{ n } { V }_{ a }+1\)
- (c)
\(\\ \quad { S }_{ a }=\frac { \left( n-1 \right) }{ n } { V }_{ a }+1\)
- (d)
\(\\ \quad { S }_{ a }=\frac { \left( n-1 \right) }{ n } { V }_{ a }-1\)
A heap is a
- (a)
complete binary tree
- (b)
full binary tree
- (c)
strictly binary tree
- (d)
B-tree
Consider the following code fragment:
node * fun(node *P)
{
int e = 0;
node *q, t;
f = q = P;
while (q - left)
{
f = q;
q = q \(\rightarrow \) left;
c = ++;
}
f \(\rightarrow \) left = NULl
;
return P;
}
Each of the above codes do when fun (P) is called where P is pointer to BST
- (a)
Deletes the smallest element in the tree
- (b)
Counts the heigh of the tree
- (c)
Deletes the left sub-tree of the root of the tree
- (d)
None of the above
How many rotations are required during the construction of an AVL tree if the following elements are to be added in the order given?
35, 50, 40, 25, 30, 60, 78, 20, 28
- (a)
2 left rotations, 1 right rotations
- (b)
2 left rotations, 2 right rotations
- (c)
3 left rotations, 2 right rotations
- (d)
3 left rotations, 1 right rotations
Linked list are not suitable for
- (a)
Insertion sort
- (b)
binary search
- (c)
radix sort
- (d)
polynomial function
Find the average number of comparisons required for an unsuccessful search of a random binary search tree with N nodes and 50 as external path length.
- (a)
4.2
- (b)
3.3
- (c)
3.9
- (d)
4.9
Preorder of A*(B+C)/D-G
- (a)
-*A/+BCDG
- (b)
*+AB/C-DG
- (c)
*A+BC/-DG
- (d)
None of these
Let Tt be ninary search tree with 15 nodes. If 4.31 is the average number of comparisons required for successful search in a random binary search tree, then what will be the interval path length?
- (a)
30
- (b)
50
- (c)
40
- (d)
60
Let T be binary search tree with n nodes and 56 as its external path length and the average number of comparisons required for an unsucessful search is 4.0. Then, find the value of n.
- (a)
22
- (b)
29
- (c)
13
- (d)
15
When searching for the key value 60 in binary search tree, nodes containing the key value 10, 20, 40, 50, 70, 80, 90 are traversed, not necessarily in the order given. How many different nodes are possible in which these key values can occur on the search path from the root to the node containing the value 60?
- (a)
35
- (b)
64
- (c)
128
- (d)
5040