Data Structure
Interview Questions in Data structures
USEFUL FOR FYBSC (IT), FYBCA STUDENTS
1.) Convert the expression ((A + B) * C – (D – E) ^ (F + G)) to equivalent Prefix and Postfix notations.
i.) Prefix Notation: – * +ABC ^ – DE + FG
ii.) Postfix Notation: AB + C * DE – FG + ^ –
2.) Sorting is not possible by using which of the following methods? (Insertion, Selection, Exchange, Deletion)
An.) Sorting is not possible in 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.
3.) List out few of the applications that make use of Multilinked Structures?
(i) Sparse matrix,
(ii) Index generation.
4.) In tree construction which is the suitable efficient data structure? (Array, Linked list, Stack, Queue)
An.)Linked list is the suitable efficient data structure
5.) Classify the Hashing Functions based on the various methods by which the key value is found.
 Direct method,
 Subtraction method,
 ModuloDivision method,
 DigitExtraction method,
 MidSquare method,
 Folding method,
 Pseudorandom method
6.) What are the types of Collision Resolution Techniques and the methods used in each of the type?
 Open addressing (closed hashing),the methods used include: Overflow block.
 Closed addressing (open hashing),The methods used include: Linked list, Binary tree
7.) Whether Linked List is linear or Nonlinear data structure?
An.)
According to Access strategies Linked list is a linear one.
According to Storage Linked List is a Nonlinear one
Posted By: Vissicomp Technology Pvt. Ltd.
Website : http://www.vissicomp.com
Hashing technique in Data structures in C
USEFUL FOR FYBSC (IT), FYBCA STUDENTS
1. The memory address of the first element of an array is called
a. floor address
b. foundation address
c. first address
d. base address
2. The memory address of fifth element of an array can be calculated by the formula
a. LOC(Array[5]=Base(Array)+w(5lower bound), where w is the number of words per memory cell for the array
b. LOC(Array[5])=Base(Array[5])+(5lower bound), where w is the number of words per memory cell for the array
c. LOC(Array[5])=Base(Array[4])+(5Upper bound), where w is the number of words per memory cell for the array
d. None of above
3. Which of the following data structures are indexed structures?
a. linear arrays
b. linked lists
c. both of above
d. none of above
4. Which of the following is not the required condition for binary search algorithm?
a. The list must be sorted
b. there should be the direct access to the middle element in any sub list
c. There must be mechanism to delete and/or insert elements in list
d. none of above
5. Which of the following is not a limitation of binary search algorithm?
a. must use a sorted array
b. requirement of sorted array is expensive when a lot of insertion and deletions are needed
c. there must be a mechanism to access middle element directly
d. binary search algorithm is not efficient when the data elements are more than 1000.
6. Two dimensional arrays are also called
a. tables arrays
b. matrix arrays
c. both of above
d. none of above
7. A variable P is called pointer if
a. P contains the address of an element in DATA.
b. P points to the address of first element in DATA
c. P can store only memory addresses
d. P contain the DATA and the address of DATA
Posted By: Vissicomp Technology Pvt. Ltd.
Website : http://www.vissicomp.com
Hashing technique in Data structures in C
USEFUL FOR FYBSC (IT), FYBCA STUDENTS
What is hashing technique? Describe in brief.
 In general, in all searching techniques, search time is dependent on the number of items. Sequential search, binary search and all the search trees are totally dependent on number of items and many key comparisons are involved.
 Hashing is a technique where search time is independent of the number of items or elements. In this technique a hash function is used to generate an address from a key. The hash function takes a key as input and returns the hash value of that key which is used as an address index in the array.
 We can write hash function as follows
h(k)=a;
Where h is hash function, k is the key, a is the hash value of the key.
While choosing a hash function we should consider some important points.
 It should be easy to compute
 It should generate address with minimum collision.
Posted By: Vissicomp Technology Pvt. Ltd.
Website : http://www.vissicomp.com
Data structures in C
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct node
{int data;
struct node *next;
}*start=NULL;
void creat()
{char ch;
do
{ struct node *new_node,*current;
new_node=(struct node *)malloc(sizeof(struct node));
printf(“nEnter the data : “);
scanf(“%d”,&new_node>data);
new_node>next=NULL;
if(start==NULL)
{ start=new_node;
current=new_node; }
else
{ current>next=new_node;
current=new_node; }
printf(“nDo you want to creat another : “);
ch=getche();
}while(ch!=’n’);}
void display()
{struct node *new_node;
printf(“The Linked List : n”);
new_node=start;
while(new_node!=NULL)
{ printf(“%d—>”,new_node>data);
new_node=new_node>next; }
printf(“NULL”);}
void main()
{create();
display();}
Output:
Enter the data : 10
Do you want to creat another : y
Enter the data : 20
Do you want to creat another : y
Enter the data : 30
Do you want to creat another : n
The Linked List :
10—>20—>30—>NULL
Data structures in C
Practical applications of data structures
Hash Table – used for fast data lookup – symbol table for compilers, database indexing, caches, and unique data representation.
Tree – dictionary, such as one found on a mobile telephone for auto completion and spellchecking.
Suffix tree – fast full text searches used in most word processors.
Stack – undo\redo operation in word processors, Expression evaluation and syntax parsing, many virtual machines like JVM are stack oriented.
Queues – Transport and operations research where various entities are stored and held to be processed later i.e. the queue performs the function of a buffer.
Priority queues – process scheduling in the kernel
Trees – Parsers, File system
Radix tree – IP routing table
BSP tree – 3D computer graphics
Graphs – Connections/relations in social networking sites, Routing ,networks of communication, data organization etc.
Heap – Dynamic memory allocation in lisp
Posted By: Vissicomp Technology Pvt. Ltd.
Website : http://www.vissicomp.com
data structures in C Programming
Concept of Data Type
 C language programmer has to tell the system beforehand, the type of numbers or characters used in the program. These are data types. There are many data types in C language.
 A C programmer has to use appropriate data type as per his requirement. C language data types can be broadly classified as:
1) Primary data type
2) Derived data type
3) Userdefined data type
Primary Data Type
 All C Compilers accept the following fundamental data types.
1  Integer  int 
2  Character  char 
3  Floating point  float 
4  Double precision floating point  double 
5  Void  void

 The size and range of each data type is given in the table below.
Data Type  Range of Values  
1  char  –128 to 127 
2  Int  –32768 to +32767 
3  float  3.4 e–38 to 3.4 e+38 
4  double  1.7 e–308 to 1.7 e+308 
Integer Type
 Integers are whole numbers with a machine dependent range of values. A good programming language as to support the programmer by giving a control on a range of numbers and storage space.
 C has 3 classes of integer storage namely short int, int and long int. All of these data types have signed and unsigned forms.
 A short int requires half the space than normal integer values. Unsigned numbers are always positive and consume all the bits for the magnitude of the number. The long and unsigned integers are used to declare a longer range of values.
Floating Point Types
 Floating point number represents a real number with 6 digits precision. Floating point numbers are denoted by the keyword float.
 When the accuracy of the floating point number is insufficient, we can use the double to define the number. The double is same as float but with longer precision. To extend the precision further we can use long double which consumes 80 bits of memory space.
Posted By: Vissicomp Technology Pvt. Ltd.
Website : http://www.vissicomp.com
Data Structure in C Programming
#include
#include
void main( )
{
int arr[10] = { 11, 2, 9, 13, 57, 25, 17, 1, 90, 3 } ;
int i, num ;
clrscr( ) ;
printf ( “Enter number to search: ” ) ;
scanf ( “%d”, &num ) ;
for ( i = 0 ; i <= 9 ; i++ )
{
if ( arr[i] == num )
break ;
}
if ( i == 10 )
printf ( “Number is not present in the array.” ) ;
else
printf ( “The number is at position %d in the array.”, i ) ;
getch( ) ;}
Posted By: Vissicomp Technology Pvt. Ltd.
Website : http://www.vissicomp.com
Program to convert infix to postfix expression
Data Structure
Infix to postfix
Program to convert infix to postfix expression
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
char inf[40],post[40];
int top=0,st[20];
void postfix();
void push(int);
char pop();
void main()
{
clrscr();
printf(“Enter the infix expression\n\n”);
scanf(“%s”,inf);
postfix();
getch();
}
void postfix()
{
int i,j=0;
for(i=0;inf[i]!=”;i++)
{
switch(inf[i])
{
case ‘+’:while(st[top]>=1)
post[j++]=pop();
push(1);
break;
case ‘‘:while(st[top]>=1)
post[j++]=pop();
push(2);
break;
case ‘*’:while(st[top]>=1)
post[j++]=pop();
push(3);
break;
case ‘/’:while(st[top]>=1)
post[j++]=pop();
push(4);
break;
case ‘^’:while(st[top]>=1)
post[j++]=pop();
push(5);
break;
case ‘(‘:push(0);
break;
case ‘)’:while(st[top]!=0)
post[j++]=pop();
top–;
break;
default:post[j++]=inf[i];
}
}
while(top>0)
post[j++]=pop();
printf(“postfix expression is \n\n %s”,post);
}
void push(int ele)
{
top++;
st[top]=ele;
}
char pop()
{
int el;
char e;
el=st[top];
top–;
switch(el)
{
case 1:e=’+’;
break;
case 2:e=’‘;
break;
case 3:e=’*’;
break;
case 4:e=’/’;
break;
case 5:e=’^’;
break;
}
return e;
}
Output
Posted by Vissicomp Technology Pvt Ltd