Data Structure
Exam Duration: 45 Mins Total Questions : 30
In a stack, the data item placed on the stack first is
- (a)
the first data item to be removed
- (b)
the last data item to be removed
- (c)
given an index zero
- (d)
not given as index number
Let S be a sorted array of n integers. Let t(n) denotes the time taken for the most efficient algorithm to determine, if there are two elements with sum less than 100 in S. Which of the following statements is true?
- (a)
t(n) is 0(1)
- (b)
\(n\le t(n)\le nlog_{ 2 }n\)
- (c)
\(nlog_{ 2 }n\le t(n)<\left( \frac { n }{ 2 } \right) \)
- (d)
\(t(n)=\left( \frac { n }{ 2 } \right) \)
[(A$B)*C-D]+[(E/F)/(G+)] convert the above infix operation into postfix form.
- (a)
AB$C*D-EF/GH+/+
- (b)
AB$CD*-EF/GH+/+
- (c)
AB$C*D-E/FG+/+/+
- (d)
AB$C*D-/EF+GH/+
Stack is useful for implementing
- (a)
radix sort
- (b)
breadth first search
- (c)
recursion
- (d)
None of these
Choose the equivalent prefix form of the following expression [a+(b-c)]*[(d-e)/(f+g-h))]
- (a)
*+a-bc/-de-+fgh
- (b)
*+a-bc-/de-+fgh
- (c)
*+a-bc/-ed-+fgh
- (d)
*+ab-c/-de-+fgh
Binary tree is a tree in which
- (a)
no node can have more than two children
- (b)
every node must have two children
- (c)
a node can have atleast two children
- (d)
none of the above
Number of comparisons in searching an element in a binary search tree is
- (a)
0(n)
- (b)
0(log n)
- (c)
0(n3)
- (d)
0(n log n)
How many ordered trees are possible with 6 nodes?
- (a)
10
- (b)
12
- (c)
13
- (d)
None of these
Average case complexity of search, Insertion and deletion operation is
- (a)
O(log2n)
- (b)
O(nlog2n)
- (c)
O(n)
- (d)
O(nn)
The postfix expression for the infix expression
- (a)
A+B*(C+D)/F+D*E is
- (b)
ABCD+*F/DE*++
- (c)
A*B+CD/F*DE++
- (d)
A+*BCD/F*DE++
Which one of the following statements is false?
- (a)
Optimal binary search tree construction can be performed efficiently using dynamic programming
- (b)
Breadth-first search can not be used to find converted components of a graph
- (c)
Given the prefix and profix walks over a binary tree, the binary tree cannot be uniquely constructed
- (d)
Depth first search can be used to find connected components of a graph.
What can be said about the array representation of a circular queue when it contains only one element?
- (a)
Front=rear=null
- (b)
Front=rear+1
- (c)
Front=rear-1
- (d)
Front=rear\(\neq \)null
Void function (struct node**q, int num)
{
struct node*temp
temp = malloc (size of (struct node));
temp \(\rightarrow \) data = num;
temp \(\rightarrow \) link=*q;
*q = temp;
}
This is the function for inserting an element in the linked list at
- (a)
beginning
- (b)
end
- (c)
middle
- (d)
None of these
If we want to make the above function as a last node then we want to have
- (a)
temp\(\rightarrow \)data = null
- (b)
temp \(\rightarrow \) link = null
- (c)
*q \(\rightarrow \) link = null
- (d)
None of these
If we want to find the last node of a linked list then the correct coding is
- (a)
if (temp \(\rightarrow \)link ! = null); temp = temp \(\rightarrow \) link
- (b)
if (temp \(\rightarrow \) data = num); temp = temp \(\rightarrow \) link
- (c)
While (temp \(\rightarrow \) link ! = null); temp = temp \(\rightarrow \) link
- (d)
While (temp \(\rightarrow \) link! = data ); temp = temp \(\rightarrow \) link
In queue, an element can be inserted and deleted by using
- (a)
rear and front
- (b)
front and rear
- (c)
top
- (d)
None of these
Queue can be used to implement
- (a)
radix sort
- (b)
quick sort
- (c)
recursion
- (d)
depth first search
The five items U,V,W,X and Y are pushed onto a stack one after the other starting from U.The stack is popped four items and each element is inserted in a queue.Then two elements are delected from the queue and pushed back on the stack and then one item is popped from the stack.Then the popped item is
- (a)
U
- (b)
V
- (c)
W
- (d)
X
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\)
In an empty queue rear and front can be initialized as
- (a)
rear=front=-1
- (b)
rear=front=1
- (c)
rear=0 front=-1
- (d)
rear=-1, front=0
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\)
Consider a sorted array data structure which supports two operations (a) binary search in O (log n) time, (b) insertion of a new element. (Binary search may precede insertion of the element to find position of the insertion). What is the complexity of the insertion operation?
- (a)
O (n)
- (b)
O (log n)
- (c)
O (n log n)
- (d)
None of these
Postorder traversal of a given binary search tree. T produces the following sequences of the key.
10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29
Which one of the following sequences of the keys can be the result of an inorder traversal of the tree T?
- (a)
9,10,15,22,23,25,27,29,40,50,60,95
- (b)
9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29
- (c)
29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95
- (d)
95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29
Select the correct matching pair,
(i) Preorder traversal (A) L-R-W
(ii) Inorder traversal (B) W-L-R
(iii) Postorder traversal (C) R-W-L
(D) W-R-L
(E) R-L-W
(F) L-W-R
Where, L = Left, W= Right, = R = Root
- (a)
(i)-A, (ii)-B, (iii)-F
- (b)
(i)-E, (ii)-A, (iii)-B
- (c)
(i)-E, (ii)-A, (iii)-F
- (d)
(i)-A, (ii)-C, (iii)-D
How many edges are possible in a forest with n vertices and and k trees?
- (a)
n-k+1
- (b)
n-k-1
- (c)
n-k
- (d)
Insufficient data
Which of the following is not true about spanning tree?
- (a)
It is tree associated with a network
- (b)
All the nodes of the graph appear on the tree once
- (c)
Spanning tree doesn't form a cycle
- (d)
Spanning tree cannot be minimum or maximum
Preorder of A*(B+C)/D-G
- (a)
-*A/+BCDG
- (b)
*+AB/C-DG
- (c)
*A+BC/-DG
- (d)
None of these
Which of the following numbers of nodes can have a full binary tree?
- (a)
8
- (b)
15
- (c)
13
- (d)
14
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
There are two sorted lists each of length n. An element is to be searched in both the lists. The lists are mutually exclusive. The maximum numbers of comparisons required using binary search is
- (a)
log22n
- (b)
log2n2
- (c)
1+log2 n
- (d)
Cannot be determined