TCS

QUESTION 1

For the expression (7-(4*5))+(9/3) which of the following is the post order tree traversal?
a) *745-93/+
b) 93/+745*-
c) 745*-93/+
d) 74*+593/-

ANSWER: C
QUESTION 2

For the tree below, write the level-order traversal.

a) 2, 7, 2, 6, 5, 11, 5, 9, 4
b) 2, 7, 5, 2, 11, 9, 6, 5, 4
c) 2, 5, 11, 6, 7, 4, 9, 5, 2
d) 2, 7, 5, 6, 11, 2, 5, 4, 9

ANSWER: B
Question :3

Eesha is developing a word processing software in which she wants to provide undo
feature. The software will maintain all the sequential changes and at any point of time
pressing control z will undo the latest change, what data structure should Eesha use for
this?
A. Stack
B. Queue
C. Linked list
D. Array

Answer: (A)
Question : 4

Eesha wants to implement an image viewer application to view images in a given folder. The
application will be able to display an image and will also know what its next and previous images
are at any given point of time so that the user can so that the user can view next/previous image by
pressing right/left keys on the keyboard. Which data structure is appropriate for Esha to use?
A. Tree
B. Queue
C. Linked list
D. Stack

Answer: C
QUESTION 5

#include <stdio.h>
void main()
{
register int x;
printf("%d", x);
}
a) 0
b) Junk value
c) Compile time error
d) Nothing

ANSWER:B
QUESTION 6

#include <stdio.h>
int main()
{
register int x;
printf("%d", x);
}
a) 0
b) Junk value
c) Compile time error
d) Nothing

ANSWER:A
QUESTION 7

Which of the following statement(s) about stack data structure is/are NOT correct?
a) Stack data structure can be implemented using linked list
b) New node can only be added at the top of the stack
c) Stack is the FIFO data structure
d) The last node at the bottom of the stack has a NULL link

ANSWER: C
QUESTION 8

Consider the following operation performed on a stack of size 5.

Push(1);
Pop();
Push(2);
Push(3);
Pop();
Push(4);
Pop();
Pop();
Push(5);
After the completion of all operation, the no of element present on
stack are
a) 1
b) 2
c) 3
d) 4

ANSWER: A
Question :9

A linear list of elements in which deletion can be done from one end (front) and
insertion can take place only at the other end (rear) is known as a ?

a) Queue
b) Stack
c) Tree
d) Linked list

Answer: A
Question :10

The data structure required for Breadth First Traversal on a graph is?

a) Stack
b) Array
c) Queue
d) Tree

Answer: C
PROGRAMMING

Check if the concatenation of two strings is balanced or not. Given two bracket sequences S1
and S2 consisting of ‘(‘ and ‘)’. The task is to check if the string obtained by concatenating both
the sequences is balanced or not. Concatenation can be done by s1+s2 or s2+s1.
Examples
Input
s1 = “)()(())))”, s2 = “(()(()(”
Output
Balanced
s2 + s1 = “(()(()()()(())))”, which is a balanced paranthesis sequence.
Input
s1 = “(()))(“, s2 = “())())”
Output
Not balanced
s1 + s2 = “(()))(())())” –> Not balanced
s2 + s1 = “())())(()))(” –> Not balanced
QUESTION 11

The pre-order and in-order are traversals of a binary tree are T M L N P O Q and L M N T O P Q.
Which of following is post-order traversal of the tree?
a) L N M O Q P T
b) N M O P O L T
c) L M N O P Q T
d) O P L M N Q T

ANSWER: A
QUESTION 12

Find the postorder traversal of the binary tree shown below.

a) P Q R S T U V W X
b) W R S Q P V T U X
c) S W T Q X U V R P
d) S T W U X V Q R P

ANSWER: C
QUESTION 13

Which among the following is the correct syntax to declare a static variable
register?
a) static register a;
b) register static a;
c) Both static register a; and register static a;
d) We cannot use static and register together

ANSWER:D
QUESTION 14

#include <stdio.h>
void main()
{
register int x = 0;
if (x < 2)
{
x++;
main();
}
}
a) Segmentation fault
b) main is called twice
c) main is called once
d) main is called thrice

ANSWER:A
QUESTION 15

Postfix form of following expression.

D + (E * F)

A. EF * D+
B. DEF * +
C. DEF +*
D. EFD *+

ANSWER: B
QUESTION 16

Stack data structure cannot be used for

A. Implementation of Recursive Function

B. Allocation Resources and Scheduling
C. Reversing string
D. Evaluation of string in postfix form

ANSWER: B
QUESTION 17

Consider the following rooted tree with the vertex P labeled as root

A. SQPTRWUV
B. SQPTURWV
A. SQPTWUVR
A. SQPTRUWV

ANSWER: A
QUESTION 18

Level order traversal of a rooted tree can be done by starting from the root and performing

A. preorder traversal
B. inorder traversal
C. depth first search
D. breadth first search

ANSWER: D
Question : 19

In linked list implementation of a queue, where does a new element be

inserted?

a) At the head of link list

b) At the tail of the link list
c) At the centre position in the link list
d) None

Answer: B
Question : 20

Consider the following operations along with

ENQUEUE and DEQUEUE operations queues,
What is the worst case time
where k is a global parameter. complexity of a sequence of n
queue operations on an initially
empty queue?
Multiqueue(Q)
{ a) θ (n)
b) θ (n + k)
m=k; c) θ (nk)
while(Q is not empty) and (m > 0) d) θ (n2)

{
DEQUEUE(Q)
m=m-1
}
Answer: A
}
PROGRAMMING

Given a string check if it is Pangram or not. A pangram is a

sentence containing every letter in the English Alphabet.
Examples : The quick brown fox jumps over the lazy dog ” is a
Pangram
“The quick brown fox jumps over the dog” is not a Pangram
A pangram is a string that contains all the letters of the English
alphabet. An example of a pangram is "The quick brown fox jumps
over the lazy dog".
A program that checks if a string is pangram or not is given as
follows.
QUESTION 21

The result of the postfix expression 5 3 * 9 + 6 / 8 4 / + is

A. 8
B. 6
C. 10
D. 9

ANSWER:B
QUESTION 22

Convert the following infix expressions into its equivalent postfix

expressions
(A + B ⋀D)/(E - F)+G
a) (A B D ⋀ + E F - / G +)
b) (A B D +⋀ E F - / G +)
c) (A B D ⋀ + E F/- G +)
d) None

ANSWER: A
QUESTION 23

Which data type can be stored in register?

a) int
b) long
c) float
d) all of the mentioned

ANSWER:D
QUESTION 24

Which of the following operation is not possible in a register variable?

a) Reading the value into a register variable
b) Copy the value from a memory variable
c) Global declaration of register variable
d) All of the mentioned

ANSWER:D
QUESTION 25

Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree.
Which of these pairs identify a tree uniquely ?
(i) preorder and postorder
(ii) inorder and postorder
(iii) preorder and inorder
(iv) level order and postorder

A. (i) only
B. (ii), (iii)

C. (iii) only

D. (iv) only

ANSWER: B
QUESTION 26

Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and
preorder traversal, respectively, of a complete binary tree. Which of the following is always
true?
A. LASTIN = LASTPOST
B. LASTIN = LASTPRE
C. LASTPRE = LASTPOST
D. None of the above

ANSWER: D
Question :27

Suppose a circular queue of capacity (n-1) elements is implemented

with an array of n elements. Assume that the insertion and deletion
operations are carried out using REAR and FRONT as array index
variables, respectively. Initially REAR=FRONT=0. The conditions to
detect queue full and queue is empty are?

a) Full: (REAR+1)mod n == FRONT

Empty: REAR==FRONT
b) Full: (REAR+1)mod n == FRONT
Empty: (FRONT+1) mod n == REAR
c) Full: REAR==FRONT
Empty: (REAR+1) mod n==FRONT
d) Full: (FRONT+1)mod n==REAR
Empty: REAR==FRONT

Answer: A
Question :28

An array of size MAX_SIZE is used to implement a circular

queue. Front, Rear, and count are tracked. Suppose front
is 0 and rear is MAX_SIZE -1. How many elements are
present in the queue?

a) Zero
b) One
c) MAX_SIZE-1
d) MAX_SIZE

Answer: D
QUESTION 29

#include<stdio.h>
int main()
{
int i = 10;
register static int* a = &i;
printf("%d", *a);
getchar();
return 0;
}

ANSWER: cannot combine with previous

'register'
declaration specifier
register static int* a = &i;
QUESTION 30

#include <stdio.h>

register int x = 10;

int main()
{
register int i = 10;
printf("%d\n", i);
printf("%d", x);
return 0;
}

ANSWER: illegal storage class on file-scoped

variable
register int x = 10;
^
QUESTION 31

Given a string, find the second most frequent

character in it. Expected time complexity is O(n)
where n is the length of the input string.
Examples:
Input: str = "aabababa";
Output: Second most frequent character is 'b' 
Input: str = "successes";
Output: Second most frequent character is 'c‘
Input: str = "abcd";
Output: No Second most frequent character
QUESTION 31

Consider the usual algorithm for determining whether a sequence of parentheses is balanced.
The maximum number of parentheses that appear on the stack AT ANY ONE TIME when the
algorithm analyzes: (()(())(())) are:
A. 1
B. 2
C. 3
D. 4 or more

ANSWER: C
QUESTION 32

The postfix expression abc+de/*- is equivalent to which of the following infix expression

A. abc+-de*/
B. (a+b)-d/e*c
C. a-(a+b)*(d/e)
D. abc+*-(d/e)

ANSWER: C
Question :33

A circular queue is implemented using an array of size 10.

The array index starts with 0, front is 6, and rear is 9. The
insertion of next element takes place at the array index.

a) 0
b) 7
c) 9
d) 10

Answer: A
Question : 34

Is it possible to implement 2 stack in an array?

Condition: None of the stack should indicate an
overflow until every slot of an array is used.

a. Only 1 stack can be implemented for the given

condition
b. Stacks can not be implemented in array
c.  2 stacks can be implemented for the given
condition.
d.  2 stacks can be implemented if the given
condition is applied only for 1 stack.Answer: C
Question : 35

Is it possible to find the greatest and least value

among the nodes in a given BST without using
any extra variables?

a. No solution exist.  
b. Solution need 2 extra variables  
c. Solution exist without any extra variables  
d Solution need 1 extra variable 

Answer: C
Question : 36

Is it possible to implement a queue using Linked List ?. Enqueue & Dequeue should be O(1).

a. Not possible to implement.  

b Only Enqueue is possible at O(1).   
c. Only Dequeue is possible at O(1).  
d. Both Enqueue and Dequeue is possible at O(1)

Answer: D
QUESTION 37

Which one of the following binary trees has its inorder and preorder traversals as BCAD  and ABCD,
respectively?

A. A
B. B
C. C
D. D

ANSWER: D
QUESTION 38

A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the tree is traversed in pre-
order and the values in each node printed out, the sequence of values obtained is 5, 3, 1, 2, 4, 6, 8,
7. If the tree is traversed in post-order, the sequence obtained would be  
A. 8, 7, 6, 5, 4, 3, 2, 1
B. 1, 2, 3, 4, 8, 7, 6, 5
C. 2, 1, 4, 3, 6, 7, 8, 5
D. 2, 1, 4, 3, 7, 8, 6, 5

ANSWER: D
QUESTION 39

Predict the output?

#include <stdio.h>
int main() {
register char x = 'S';
register int a = 10;
auto int b = 8;
printf("The value of register variable b : %c\n",x);
printf("The sum of auto and register variable :%d",(a+b));
return 0;}

ANSWER: The value of register variable b : S

The sum of auto and register variable : 18
QUESTION 40

#include<stdio.h>
int main()
{
    register int i = 10;
    int* a = &i;
    printf("%d", *a);
    getchar();
    return 0;
}

ANSWER: error: address of register variable

requested
int* a = &i;
^~
QUESTION 41

Consider the postfix expression 4 5 6 a b 7 8 a c, where a, b, c are operators. Operator a has higher
precedence over operators b and c. Operators b and c are right associative. Then, equivalent
infix expression is
A. 4 a 5 6 b 7 8 a c
B. 4 a 5 c 6 b 7 a 8
C. 4 b 5 a 6 c 7 a 8
D. 4 a 5 b 6 c 7 a 8

ANSWER: C
QUESTION 42

Which of the following is valid reverse polish expression?

A. a op b
B. op a b
C. a b op
D. both op a b and a b op

ANSWER: C
Question :43

Which of the following ways can be used to represent a

graph?
a) Adjacency List and Adjacency Matrix
b) Incidence Matrix
c) Adjacency List, Adjacency Matrix as well as Incidence
Matrix
d) No way to represent

Answer: C
Question :44

The concatenation of two lists is to be

performed in O(1) time. Which of the following
implementations of a list could be used ?

A. Singly Linked List

B. Array Implementation of List
C. Doubly Linked List
D. Circular Doubly Linked List

Answer: D
Question :44

What is the output of following function for start pointing to first

node of following linked list? 1->2->3->4->5->6
void fun(struct node* start)
{
  if(start == NULL)
    return;
  printf("%d  ", start->data);
  
  if(start->next != NULL )
    fun(start->next->next);
  printf("%d  ", start->data);
}
A. 146641
B. 135135
C. 1235
D. 135531

Answer: D
THANK YOU