1.

Data Structures Aptitude

1. What is data structure?
A data structure is a way of organizing data that considers not only the
items stored, but also their relationship to each other. Advance knowledge about the
relationship between data items allows designing of efficient algorithms for the
manipulation of data

2. What is the data structures used to perform recursion?

Stack. Because of its LIFO (Last In First Out) property it remembers its ‘caller’ so
knows whom to return when the function has to return. Recursion makes use of system
stack for storing the return addresses of the function calls.
Every recursive function has its equivalent iterative (non-recursive) function.
Even when such equivalent iterative procedures are written, explicit stack is to be used.

3. What are the notations used in Evaluation of Arithmetic Expressions using prefix
and postfix forms?
Polish and Reverse Polish notations.

4. Convert the expression ((A + B) * C – (D – E) ^ (F + G)) to equivalent Prefix

and Postfix notations.
Prefix Notation:
^ - * +ABC - DE + FG
Postfix Notation:
AB + C * DE - - FG + ^

5. Sorting is not possible by using which of the following methods?

(a) Insertion
(b) Selection
(c) Exchange
(d) Deletion

(d) Deletion.
Using insertion we can perform insertion sort, using selection we can perform
selection sort, using exchange we can perform the bubble sort (and other similar sorting
methods). But no sorting method can be done just using deletion.

6. List out few of the Application of tree data-structure?

 The manipulation of Arithmetic expression,
 Symbol Table construction,
 Syntax analysis.

7. In tree construction which is the suitable efficient data structure?

(a) Array (b) Linked list (c) Stack (d) Queue (e) none
 (b) Linked list

8. Traverse the given tree using Inorder, Preorder and Postorder traversals

Given tree:
A

B C

D E F G

H I J

 Inorder : D H B E A F C I G J
 Preorder: A B D H E C F G I J
 Postorder: H D E B F I J G C A

9. Of the following tree structure, which is, efficient considering space and time
complexities?
(a) Incomplete Binary Tree
(b) Complete Binary Tree
(c) Full Binary Tree

(b) Complete Binary Tree.

By the method of elimination:
Full binary tree loses its nature when operations of insertions and deletions
are done. For incomplete binary trees, extra storage is required and overhead of NULL
node checking takes place. So complete binary tree is the better one since the property of
complete binary tree is maintained even after operations like additions and deletions are
done on it.

10.Draw a binary Tree for the expression :

A * B - (C + D) * (P / Q)
 -

* *

A B + /

C D P Q

11.What are the major data structures used in the following areas : RDBMS, Network
data model & Hierarchical data model.
 RDBMS – Array (i.e. Array of structures)
 Network data model – Graph
 Hierarchical data model – Trees

12. What is a spanning Tree?

A spanning tree is a tree associated with a network. All the nodes of the graph
appear on the tree once. A minimum spanning tree is a spanning tree organized so that
the total edge weight between nodes is minimized.

13.Whether Linked List is linear or Non-linear data structure?

According to Access strategies Linked list is a linear one.
According to Storage Linked List is a Non-linear one.
14.Does the minimum spanning tree of a graph give the shortest distance between any
2 specified nodes?
No.
Minimal spanning tree assures that the total weight of the tree is kept at its
minimum. But it doesn’t mean that the distance between any two nodes involved in the
minimum-spanning tree is minimum.

15.How many different trees are possible with 10 nodes ?

1014
For example, consider a tree with 3 nodes(n=3), it will have the maximum
combination of 5 different (ie, 23 - 3 = 5) trees.

i ii iii iv v

In general:
 If there are n nodes, there exist 2n-n different trees.

2.C Aptitude
1.main()
{
char *p;
int *q;
long *r;
p=q=r=0;
p++;
q++;
r++;
printf("%p...%p...%p",p,q,r);
}
Answer:
0001...0002...0004
Explanation:
++ operator when applied to pointers increments address according to their
corresponding data-types

2. main()
{
int k=1;
printf("%d==1 is ""%s",k,k==1?"TRUE":"FALSE");
}
Answer:
1==1 is TRUE
Explanation:
When two strings are placed together (or separated by white-space) they
are concatenated (this is called as "stringization" operation). So the string
is as if it is given as "%d==1 is %s". The conditional operator( ?: )
evaluates to "TRUE".

3. main()
{
int y;
scanf("%d",&y); // input given is 2000
if( (y%4==0 && y%100 != 0) || y%100 == 0 )
printf("%d is a leap year");
 else
printf("%d is not a leap year");
}
Answer:
2000 is a leap year
Explanation:
An ordinary program to check if leap year or not.

4.int i=10;
main()
{
extern int i;
{
int i=20;
{
const volatile unsigned i=30;
printf("%d",i);
}
printf("%d",i);
}
printf("%d",i);
}
Answer:
30,20,10
Explanation:
'{' introduces new block and thus new scope. In the innermost block i is
declared as,
const volatile unsigned
which is a valid declaration. i is assumed of type int. So printf prints 30. In
the next block, i has value 20 and so printf prints 20. In the outermost
block, i is declared as extern, so no storage space is allocated for it. After
compilation is over the linker resolves it to global variable i (since it is the
only variable visible there). So it prints i's value as 10.

5. main()
{
int *j;
{
int i=10;
j=&i;
}
printf("%d",*j);
}
 Answer:
10
Explanation:
The variable i is a block level variable and the visibility is inside that
block only. But the lifetime of i is lifetime of the function so it lives upto
the exit of main function. Since the i is still allocated space, *j prints the
value stored in i since j points i.

6. #include<stdio.h>
main()
{
register i=5;
char j[]= "hello";
printf("%s %d",j,i);
}
Answer:
hello 5
Explanation:
if you declare i as register compiler will treat it as ordinary integer and it
will take integer value. i value may be stored either in register or in
memory.

7. main()
{
int i=5,j=6,z;
printf("%d",i+++j);
}
Answer:
11
Explanation:
the expression i+++j is treated as (i++ + j)

8. struct point
{
int x;
int y;
};
struct point origin,*pp;
main()
{
pp=&origin;
printf("origin is(%d%d)\n",(*pp).x,(*pp).y);
printf("origin is (%d%d)\n",pp->x,pp->y);
 }

Answer:
origin is(0,0)
origin is(0,0)
Explanation:
pp is a pointer to structure. we can access the elements of the structure
either with arrow mark or with indirection operator.
Note:
Since structure point is globally declared x & y are initialized as zeroes

9. main()
{
int i=_l_abc(10);
printf("%d\n",--i);
}
int _l_abc(int i)
{
return(i++);
}
Answer:
9
Explanation:
return(i++) it will first return i and then increments. i.e. 10 will be
returned.

10.main()
{
char c=' ',x,convert(z);
getc(c);
if((c>='a') && (c<='z'))
x=convert(c);
printf("%c",x);
}
convert(z)
{
return z-32;
}
Answer:
Compiler error
Explanation:
declaration of convert and format of getc() are wrong.
 3.C++ Aptitude and OOPS

1. Name the operators that cannot be overloaded.

Answer:
sizeof . .* .-> :: ?:

2. What is a node class?

Answer:
A node class is a class that,
 relies on the base class for services and implementation,
 provides a wider interface to te users than its base class,
 relies primarily on virtual functions in its public interface
 depends on all its direct and indirect base class
 can be understood only in the context of the base class
 can be used as base for further derivation
 can be used to create objects.
A node class is a class that has added new services or functionality beyond the services
inherited from its base class.

3. What are the conditions that have to be met for a condition to be an invariant of the
class?
Answer:
 The condition should hold at the end of every constructor.
 The condition should hold at the end of every mutator(non-const) operation.

4.What are proxy objects?

Answer:
Objects that stand for other objects are called proxy objects or surrogates
Example:
template<class T>
class Array2D
{
public:
class Array1D
{
 public:
T& operator[] (int index);
const T& operator[] (int index) const;
...
};
Array1D operator[] (int index);
const Array1D operator[] (int index) const;
...
};

The following then becomes legal:

Array2D<float>data(10,20);
........
cout<<data[3][6]; // fine

Here data[3] yields an Array1D object and the operator [] invocation on that
object yields the float in position(3,6) of the original two dimensional array. Clients of
the Array2D class need not be aware of the presence of the Array1D class. Objects of this
latter class stand for one-dimensional array objects that, conceptually, do not exist for
clients of Array2D. Such clients program as if they were using real, live, two-dimensional
arrays. Each Array1D object stands for a one-dimensional array that is absent from a
conceptual model used by the clients of Array2D. In the above example, Array1D is a
proxy class. Its instances stand for one-dimensional arrays that, conceptually, do not
exist.

5. Name some pure object oriented languages.

Answer:
 Smalltalk,
 Java,
 Eiffel,
 Sather.

6. Differentiate between the message and method.

Answer:
Message Method
Objects communicate by sending messages Provides response to a message.
to each other.
A message is sent to invoke a method. It is an implementation of an operation

void main()
{
int a, *pa, &ra;
pa = &a;
ra = a;
cout <<"a="<<a <<"*pa="<<*pa <<"ra"<<ra ;
}
Answer :
Compiler Error: 'ra',reference must be initialized
Explanation :
Pointers are different from references. One of the main
differences is that the pointers can be both initialized and assigned,
whereas references can only be initialized. So this code issues an error.

7.What is a modifier?
Answer:
A modifier, also called a modifying function is a member function that changes the
value of at least one data member. In other words, an operation that modifies the state of
an object. Modifiers are also known as ‘mutators’.

8. What is an accessor?
Answer:
An accessor is a class operation that does not modify the state of an object. The
accessor functions need to be declared as const operations

9. Differentiate between a template class and class template.

Answer:
Template class:
A generic definition or a parameterized class not instantiated until the client
provides the needed information. It’s jargon for plain templates.
Class template:
A class template specifies how individual classes can be constructed much like
the way a class specifies how individual objects can be constructed. It’s jargon for plain
classes.

10. Define namespace.

Answer:
It is a feature in c++ to minimize name collisions in the global name space. This
namespace keyword assigns a distinct name to a library that allows other libraries to use
the same identifier names without creating any name collisions. Furthermore, the
compiler uses the namespace signature for differentiating the definitions.

11. Describe the main characteristics of static functions.

Answer:
The main characteristics of static functions include,
 It is without the a this pointer,
 It can't directly access the non-static members of its class
 It can't be declared const, volatile or virtual.
 It doesn't need to be invoked through an object of its class, although for
convenience, it may.
 4.RDBMS Concepts
1. What is database?
A database is a logically coherent collection of data with some inherent meaning,

representing some aspect of real world and which is designed, built and populated

with data for a specific purpose.

2. What is DBMS?
It is a collection of programs that enables user to create and maintain a database.
In other words it is general-purpose software that provides the users with the processes of
defining, constructing and manipulating the database for various applications.

3. What is a Database system?

The database and DBMS software together is called as Database system.

4. Advantages of DBMS?
 Redundancy is controlled.
 Unauthorised access is restricted.
 Providing multiple user interfaces.
 Enforcing integrity constraints.
 Providing backup and recovery.

5. What is extension and intension?

Extension -
It is the number of tuples present in a table at any instance. This is time
dependent.
Intension -
It is a constant value that gives the name, structure of table and the
constraints laid on it.

6. What is Data Independence?

Data independence means that “the application is independent of the storage
structure and access strategy of data”. In other words, The ability to modify the schema
definition in one level should not affect the schema definition in the next higher level.
 Two types of Data Independence:
 Physical Data Independence: Modification in physical level should
not affect the logical level.
 Logical Data Independence: Modification in logical level should
affect the view level.
NOTE: Logical Data Independence is more difficult to achieve

7.What is a view? How it is related to data independence?

A view may be thought of as a virtual table, that is, a table that does not really
exist in its own right but is instead derived from one or more underlying base table. In
other words, there is no stored file that direct represents the view instead a definition of
view is stored in data dictionary.
Growth and restructuring of base tables is not reflected in views. Thus the view
can insulate users from the effects of restructuring and growth in the database. Hence
accounts for logical data independence.

8.What is Data Model?

A collection of conceptual tools for describing data, data relationships data
semantics and constraints.

9.What is E-R model?

This data model is based on real world that consists of basic objects called entities
and of relationship among these objects. Entities are described in a database by a set of
attributes.

10.What is Object Oriented model?

This model is based on collection of objects. An object contains values stored in
instance variables with in the object. An object also contains bodies of code that operate
on the object. These bodies of code are called methods. Objects that contain same types
of values and the same methods are grouped together into classes.

11.What is an Entity?
It is a 'thing' in the real world with an independent existence.

12.What is an Entity type?

It is a collection (set) of entities that have same attributes.

13.What is an Entity set?

It is a collection of all entities of particular entity type in the database.

14.What is an Extension of entity type?

The collections of entities of a particular entity type are grouped together into an
entity set.

15.What is Weak Entity set?

 An entity set may not have sufficient attributes to form a primary key, and its
primary key compromises of its partial key and primary key of its parent entity, then it is
said to be Weak Entity set.

5.Computer Networks
1. What are the two types of transmission technology available?
(i) Broadcast and (ii) point-to-point

2. What is subnet?
A generic term for section of a large networks usually separated by a bridge or
router.

3. Difference between the communication and transmission.

Transmission is a physical movement of information and concern issues like bit
polarity, synchronisation, clock etc.
Communication means the meaning full exchange of information between two
communication media.

4. What are the possible ways of data exchange?

(i) Simplex (ii) Half-duplex (iii) Full-duplex.

5. What is RAID?
A method for providing fault tolerance by using multiple hard disk drives.

6. What is passive topology?

When the computers on the network simply listen and receive the signal, they are
referred to as passive because they don’t amplify the signal in any way. Example for
passive topology - linear bus.

7. What is Brouter?
Hybrid devices that combine the features of both bridges and routers.

8. What is cladding?
A layer of a glass surrounding the center fiber of glass inside a fiber-optic cable.

9. What is point-to-point protocol

A communications protocol used to connect computers to remote networking
services including Internet service providers.

10. How Gateway is different from Routers?

A gateway operates at the upper levels of the OSI model and translates
information between two completely different network architectures or data formats

11. What is MAC address?

The address for a device as it is identified at the Media Access Control (MAC)
layer in the network architecture. MAC address is usually stored in ROM on the network
adapter card and is unique.

12. Difference between bit rate and baud rate.

Bit rate is the number of bits transmitted during one second whereas baud rate
refers to the number of signal units per second that are required to represent those bits.
baud rate = bit rate / N
where N is no-of-bits represented by each signal shift.

13. What is Bandwidth?

Every line has an upper limit and a lower limit on the frequency of signals it can
carry. This limited range is called the bandwidth.

14. What are the types of Transmission media?

Signals are usually transmitted over some transmission media that are broadly
classified in to two categories.
a) Guided Media:
These are those that provide a conduit from one device to another that
include twisted-pair, coaxial cable and fiber-optic cable. A signal traveling along any of
these media is directed and is contained by the physical limits of the medium. Twisted-
pair and coaxial cable use metallic that accept and transport signals in the form of
electrical current. Optical fiber is a glass or plastic cable that accepts and transports
signals in the form of light.
b) Unguided Media:
This is the wireless media that transport electromagnetic waves without using a physical
conductor. Signals are broadcast either through air. This is done through radio
communication, satellite communication

15. What is ICMP?

ICMP is Internet Control Message Protocol, a network layer protocol of the
TCP/IP suite used by hosts and gateways to send notification of datagram problems back
to the sender. It uses the echo test / reply to test whether a destination is reachable and
responding. It also handles both control and error messages.
 Operating Systems
1. Explain Belady's Anomaly.
Also called FIFO anomaly. Usually, on increasing the number of frames allocated
to a process' virtual memory, the process execution is faster, because fewer page faults
occur. Sometimes, the reverse happens, i.e., the execution time increases even when more
frames are allocated to the process. This is Belady's Anomaly. This is true for certain
page reference patterns.
2. What is a binary semaphore? What is its use?
A binary semaphore is one, which takes only 0 and 1 as values. They are used to
implement mutual exclusion and synchronize concurrent processes.

3. What is thrashing?
It is a phenomenon in virtual memory schemes when the processor spends most of
its time swapping pages, rather than executing instructions. This is due to an inordinate
number of page faults.
4. What are short-, long- and medium-term scheduling?
Long term scheduler determines which programs are admitted to the system for
processing. It controls the degree of multiprogramming. Once admitted, a job becomes a
process.
Medium term scheduling is part of the swapping function. This relates to
processes that are in a blocked or suspended state. They are swapped out of real-memory
until they are ready to execute. The swapping-in decision is based on memory-
management criteria.
Short term scheduler, also know as a dispatcher executes most frequently, and
makes the finest-grained decision of which process should execute next. This scheduler is
invoked whenever an event occurs. It may lead to interruption of one process by
preemption.

5. What are turnaround time and response time?

Turnaround time is the interval between the submission of a job and its
completion. Response time is the interval between submission of a request, and the first
response to that request.
6. When is a system in safe state?
The set of dispatchable processes is in a safe state if there exists at least one
temporal order in which all processes can be run to completion without resulting in a
deadlock.

7. What is busy waiting?

The repeated execution of a loop of code while waiting for an event to occur is
called busy-waiting. The CPU is not engaged in any real productive activity during this
period, and the process does not progress toward completion.
8. What are local and global page replacements?
 Local replacement means that an incoming page is brought in only to the relevant
process' address space. Global replacement policy allows any page frame from any
process to be replaced. The latter is applicable to variable partitions model only.

9. What is time-stamping?
It is a technique proposed by Lamport, used to order events in a distributed
system without the use of clocks. This scheme is intended to order events consisting of
the transmission of messages. Each system 'i' in the network maintains a counter Ci.
Every time a system transmits a message, it increments its counter by 1 and attaches the
time-stamp Ti to the message. When a message is received, the receiving system 'j' sets
its counter Cj to 1 more than the maximum of its current value and the incoming time-
stamp Ti. At each site, the ordering of messages is determined by the following rules: For
messages x from site i and y from site j, x precedes y if one of the following conditions
holds....(a) if Ti<Tj or (b) if Ti=Tj and i<j.
10. In the context of memory management, what are placement and replacement
algorithms?
Placement algorithms determine where in available real-memory to load a
program. Common methods are first-fit, next-fit, best-fit. Replacement algorithms are
used when memory is full, and one process (or part of a process) needs to be swapped out
to accommodate a new program. The replacement algorithm determines which are the
partitions to be swapped out.
11. What are demand- and pre-paging?
With demand paging, a page is brought into memory only when a location on that
page is actually referenced during execution. With pre-paging, pages other than the one
demanded by a page fault are brought in. The selection of such pages is done based on
common access patterns, especially for secondary memory devices.

12. What are the key object oriented concepts used by Windows NT?
 Encapsulation
 Object class and instance

13. What are the reasons for process suspension?

 swapping
 interactive user request
 timing
 parent process request

14. What is process migration?

It is the transfer of sufficient amount of the state of process from one machine to
the target machine
15. What is an idle thread?
The special thread a dispatcher will execute when no ready thread is found.