Data Structures - Two Marks Q & A

1.      Limitations of arrays

·         Arrays have a fixed dimension. Once the size of an array is decided it cannot be increased or decreased during execution.

·         Array elements are always stored in contiguous memory locations. So it need contiguous locations otherwise memory will not be allocated to the arrays

·         Operations like insertion of a new element in an array or deletion of an existing element from the array are pretty tedious. This is because during insertion or deletion each element after the specified position has to be shifted one position to the right or one position to the left.

1.      Define 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.      Why do we need data structures?

v  Data structures allow us to achieve an important goal: component reuse

v  Once each data structure has been implemented once, it can be used over and over again in various applications.

3.      Simple Classification of Data Structure.

The data structure can be classified into two types as follows:

a)      Linear Data Structures – All the elements are formed in a sequence or maintain a linear ordering

                                                              i.      Arrays

                                                           ii.      Linked Lists

                                                         iii.      Stacks

                                                         iv.      Queues

b)     Non-Linear Data Structures – All the elements are distributed on a plane i.e. these have no such sequence of elements as in case of linear data structure.

                                                              i.      Trees

                                                           ii.      Graphs

                                                         iii.      Sets

4.      List the operations performed in the Linear Data Structure

a)      Traversal – Processing each element in the list

b)     Search – Finding the location of the element with a given value.

c)      Insertion / Storing – Adding a new element to the list.

d)     Deletion – Removing an element from the list.

e)      Sorting – Arranging the elements in some type of order.

f)       Merging – Combining two lists into a single list.

5.      Explain Linked List

v  A linked list is a list of elements in which the elements of the list can be placed anywhere in memory, and these elements are linked with each other using an explicit link field, that is by storing the address of the next element in the link field of the previous element.

v  A linked list is a self-referential data type because it contains a pointer or link to another data of the same type. This permit insertion and removal of nodes at any point in the list in constant time, but do not allow random access.

6.      What is a node?

Each element structure in a slinked list called node, containing two fields one is data and another is address of next data.

7.      Advantages of Linked List

1. Linked List is dynamic data structure; the size of a list can grow or shrink during the program execution.  So, maximum size need not be known in advance.
2. The Linked List does not waste memory
3. It is not necessary to specify the size of the list, as in the case of arrays.
4. Linked List provides the flexibility in allowing the items to be rearranged.

8.      What are the pitfalls encountered in single linked list?

1. A singly linked list allows traversal of the list in only one direction.
2. Deleting a node from a list requires keeping track of the previous node, that is, the node whose link points to the node to be deleted.
3. If the link in any node gets corrupted, the remaining nodes of the list become unusable.

9.      Define Stack

v  Stack is a linear data structure and is an ordered collection of homogeneous data elements, where the insertion and deletion operations takes place at one end called top of the stack.

v  A stack data structure exhibits the LIFO (Last In First Out) property.

10.  What are operations allowed in a Stack?

1. PUSH : This operation is used to add an item into the top of the stack.
2. POP    : This operation is used to remove an item from the top of the stack.
3. PEEK : This operation is used to display the top item in the stack.

11.  List the notations used to represent the arithmetic expressions.

1.      Infix:                           operator

Ex: A + B

2.      Prefix:                         operator

             (also called as polish notation) Ex: +AB  

3.      Postfix:                       operator

Ex: AB+

12.  Rules for converting an Infix notation to postfix form

1. Assume, the fully parenthesized version of the Infix expression
2. Move all operator, so that they replace their corresponding right part of parenthesis
3. Remove all parenthesis

Example: ((A+((B^C)-D))*(E-(A/C)))          à    ABC^D-+EAC/-*

13.  Define Queue

Queue is an ordered collection of homogeneous data elements, in which the element insertion and deletion takes place at two ends called front and rear. The elements are ordered in linear fashion and inserted at REAR end and deleted FRONT end. This exhibits FIFO (First In First Out) property.

14.  Applications of Queue

Applications of queue as a data structure are more common.

a)      Within a computer system there may be queues of tasks waiting for the line printer, or for access to disk storage, or in a time-sharing system for use of the CPU.

b)     Within a single program, there may be multiple requests to be kept in a queue, or one task may create other tasks, which must be done in turn by keeping them in a queue.

15.  What is the need of Circular Queue?

4  Queue implemented using an array suffers from one limitation i.e. there is a possibility that the queue is reported as full (since rear has reached the end of the array), even though in actuality there might be empty slots at the beginning of the queue. To overcome this limitation circular queue is needed.

4  Now the queue would be reported as full only when all the slots in the array stand occupied.

16.  What is deque?

v  The word deque is a short form of double-ended queue and defines a data structure in which items can be added or deleted at either the front or rear end, but no changes can be made elsewhere in the list.

v  Thus a deque is a generalization of both a stack and a queue.

17.  Types of Linked Lists:

a)      Linear Singly Linked List

b)     Circular Linked List

c)      Two-way or doubly linked lists

d)     Circular doubly linked lists

18.  What are the Applications of linked list?

a)      Implementation of Stack

b)     Implementation of Queue

c)      Implementation of Tree

d)     Implementation of Graph

19.  Applications of Stack

a)      It is very useful to evaluate arithmetic expressions. (Postfix Expressions)

b)     Infix to Postfix Transformation

c)      It is useful during the execution of recursive programs

d)     A Stack is useful for designing the compiler in operating system to store local variables inside a function block.

e)      A stack can be used in function calls including recursion.

f)       Reversing Data

g)     Reverse a List

h)     Convert Decimal to Binary

i)       Parsing – It is a logic that breaks into independent pieces for further processing

j)        Backtracking

Huffman Algorithm - to build a Huffman Tree

/* Huffman Coding in C . This program reads a text file named on the command line, then compresses it using Huffman coding. The file is read twice, once to determine the frequencies of the characters, and again to do the actual compression. */

#include < stdio.h>
#include < stdlib.h>
#include < string.h>
#include < time.h>

/* there are 256 possible characters */

#define NUM_CHARS 256

/* tree node, heap node */

typedef struct _treenode treenode;
struct _treenode {
int freq; /* frequency; is the priority for heap */
unsigned char ch; /* character, if any */
treenode *left, /* left child of Huffman tree (not heap!) */
*right; /* right child of Huffman tree */
};

/* this is a priority queue implemented as a binary heap */
typedef struct _pq {
int heap_size;
treenode *A[NUM_CHARS];
} PQ;

/* create an empty queue */

void create_pq (PQ *p) {
p->heap_size = 0;
}

/* this heap node's parent */

int parent (int i) {
return (i-1) / 2;
}

/* this heap node's left kid */

int left (int i) {
return i * 2 + 1;
}

/* this heap node's right kid */

int right (int i) {
return i * 2 + 2;
}

/* makes the subheap with root i into a heap , assuming left(i) and
* right(i) are heaps
*/
void heapify (PQ *p, int i) {
int l, r, smallest;
treenode *t;

l = left (i);
r = right (i);

/* find the smallest of parent, left, and right */

if (l < p->heap_size && p->A[l]->freq < p->A[i]->freq)
smallest = l;
else
smallest = i;
if (r < p->heap_size && p->A[r]->freq < p->A[smallest]->freq)
smallest = r;

/* swap the parent with the smallest, if needed. */

if (smallest != i) {
t = p->A[i];
p->A[i] = p->A[smallest];
p->A[smallest] = t;
heapify (p, smallest);
}
}

/* insert an element into the priority queue. r->freq is the priority */
void insert_pq (PQ *p, treenode *r) {
int i;

p->heap_size++;
i = p->heap_size - 1;

/* we would like to place r at the end of the array,
* but this might violate the heap property. we'll start
* at the end and work our way up
*/
while ((i > 0) && (p->A[parent(i)]->freq > r->freq)) {
p->A[i] = p->A[parent(i)];
i = parent (i);
}
p->A[i] = r;
}

/* remove the element at head of the queue (i.e., with minimum frequency) */
treenode *extract_min_pq (PQ *p) {
treenode *r;

if (p->heap_size == 0) {
printf ("heap underflow!\n");
exit (1);
}

/* get return value out of the root */

r = p->A[0];

/* take the last and stick it in the root (just like heapsort) */

p->A[0] = p->A[p->heap_size-1];

/* one less thing in queue */

p->heap_size--;

/* left and right are a heap, make the root a heap */

heapify (p, 0);
return r;
}

/* read the file, computing the frequencies for each character
* and placing them in v[]
*/
unsigned int get_frequencies (FILE *f, unsigned int v[]) {
int r, n;

/* n will count characters */

for (n=0;;n++) {

/* fgetc() gets an unsigned char, converts to int */

r = fgetc (f);

/* no more? get out of loop */

if (feof (f)) break;

/* one more of this character */

v[r]++;
}
return n;
}

/* make the huffman tree from frequencies in freq[] (Huffman's Algorithm) */

treenode *build_huffman (unsigned int freqs[]) {
int i, n;
treenode *x, *y, *z;
PQ p;

/* make an empty queue */

create_pq (&p);

/* for each character, make a heap/tree node with its value
* and frequency
*/
for (i=0; i< NUM_CHARS; i++) {
x = malloc (sizeof (treenode));

/* its a leaf of the Huffman tree */

x->left = NULL;
x->right = NULL;
x->freq = freqs[i];
x->ch = (char) i;

/* put this node into the heap */

insert_pq (&p, x);
}

/* at this point, the heap is a "forest" of singleton trees */

n = p.heap_size-1; /* heap_size isn't loop invariant! */

/* if we insert two things and remove one each time,
* at the end of heap_size-1 iterations, there will be
* one tree left in the heap
*/
for (i=0; i< n; i++) {

/* make a new node z from the two least frequent
* nodes x and y
*/
z = malloc (sizeof (treenode));
x = extract_min_pq (&p);
y = extract_min_pq (&p);
z->left = x;
z->right = y;

/* z's frequency is the sum of x and y */

z->freq = x->freq + y->freq;

/* put this back in the queue */

insert_pq (&p, z);
}

/* return the only thing left in the queue, the whole Huffman tree */

return extract_min_pq (&p);
}

/* traverse the Huffman tree, building up the codes in codes[] */

void traverse (treenode *r, /* root of this (sub)tree */
int level, /* current level in Huffman tree */
char code_so_far[], /* code string up to this point in tree */
char *codes[]) {/* array of codes */

/* if we're at a leaf node, */

if ((r->left == NULL) && (r->right == NULL)) {

/* put in a null terminator */

code_so_far[level] = 0;

/* make a copy of the code and put it in the array */

codes[r->ch] = strdup (code_so_far);
} else {

/* not at a leaf node. go left with bit 0 */

code_so_far[level] = '0';
traverse (r->left, level+1, code_so_far, codes);

/* go right with bit 1 */

code_so_far[level] = '1';
traverse (r->right, level+1, code_so_far, codes);
}
}

/* global variables, a necessary evil */

int nbits, current_byte, nbytes;

/* output a single bit to an open file */

void bitout (FILE *f, char b) {

/* shift current byte left one */

current_byte < < = 1;

/* put a one on the end of this byte if b is '1' */

if (b == '1') current_byte |= 1;

/* one more bit */

nbits++;

/* enough bits? write out the byte */

if (nbits == 8) {
fputc (current_byte, f);
nbytes++;
nbits = 0;
current_byte = 0;
}
}

/* using the codes in codes[], encode the file in infile, writing
* the result on outfile
*/
void encode_file (FILE *infile, FILE *outfile, char *codes[]) {
unsigned char ch;
char *s;

/* initialize globals for bitout() */

current_byte = 0;
nbits = 0;
nbytes = 0;

/* continue until end of file */

for (;;) {

/* get a char */

ch = fgetc (infile);
if (feof (infile)) break;

/* put the corresponding bitstring on outfile */

for (s=codes[ch]; *s; s++) bitout (outfile, *s);
}

/* finish off the last byte */

while (nbits) bitout (outfile, '0');
}

/* main program */

int main (int argc, char *argv[]) {
FILE *f, *g;
treenode *r; /* root of Huffman tree */
unsigned int n, /* number of bytes in file */
freqs[NUM_CHARS]; /* frequency of each char */
char *codes[NUM_CHARS], /* array of codes, 1 per char */
code[NUM_CHARS], /* a place to hold one code */
fname[100]; /* what to call output file */

/* hassle user */

if (argc != 2) {
fprintf (stderr, "Usage: %s < filename>\n", argv[0]);
exit (1);
}

/* set all frequencies to zero */

memset (freqs, 0, sizeof (freqs));

/* open command line argument file */

f = fopen (argv[1], "r");
if (!f) {
perror (argv[1]);
exit (1);
}

/* compute frequencies from this file */

n = get_frequencies (f, freqs);
fclose (f);

/* make the huffman tree */

r = build_huffman (freqs);

/* traverse the tree, filling codes[] with the codes */

traverse (r, 0, code, codes);

/* name the output file something.huf */

sprintf (fname, "%s.huf", argv[1]);
g = fopen (fname, "w");
if (!g) {
perror (fname);
exit (1);
}

/* write frequencies to file so they can be reproduced */

fwrite (freqs, NUM_CHARS, sizeof (int), g);

/* write number of characters to file as binary int */

fwrite (&n, 1, sizeof (int), g);

/* open input file again */

f = fopen (argv[1], "r");
if (!f) {
perror (argv[1]);
exit (1);
}

/* encode f to g with codes[] */

encode_file (f, g, codes);
fclose (f);
fclose (g);
/* brag */
printf ("%s is %0.2f%% of %s\n",
fname, (float) nbytes / (float) n, argv[1]);
exit (0);
}

Tamil dictionary. English to Tamil dictionary. Tamil to English dictionary. Tamil dictionary with pronunciation.

Tamil dictionary. English to Tamil dictionary. Tamil to English dictionary. Tamil dictionary with pronunciation.

Excellent site for every one.

It has Tamil Stories, Devotional songs (Lyrics), Kids Tamil learning etc., are available

This site is very useful for Every Individual.

Program for Finding Transitive Closure - Warshall Algorithm

#include
#include
#define MAX 20

display(int matrix[MAX][MAX],int n)
{

int i,j;
for(i=0;i{

for(j=0;j
printf("%3d",matrix[i][j]);

printf("\n");

}

}

int main()
{

int i,j,k,n;
int w_adj[MAX][MAX],adj[MAX][MAX],path[MAX][MAX];

printf("Enter number of vertices : ");
scanf("%d",&n);

printf("Enter weighted adjacency matrix :\n");
for(i=0;i
for(j=0;j
scanf("%d",&w_adj[i][j]);

printf("The weighted adjacency matrix is :\n");
display(w_adj,n);

/* Make weighted adjacency matrix into boolean adjacency matrix*/

for(i=0;i
for(j=0;j
if(w_adj[i][j]==0)

adj[i][j]=0;

else

adj[i][j]=1;

printf("The adjacency matrix is :\n");
display(adj,n);

for(i=0;i
for(j=0;j
path[i][j]=adj[i][j];

for(k=0;k{

printf("P%d is :\n",k);
display(path,n);
for(i=0;i
for(j=0;j
path[i][j]=( path[i][j] || ( path[i][k] && path[k][j] ) );

}

printf("Path matrix P%d of the given graph is :\n",k);
display(path,n);

}/*End of main() */

Program for Depth First Search for an un-directed Graph using C

#include

#define MAX 10
int n;
int adj[MAX][MAX];
int visited[MAX];

void readmatrix()
{
    int i,j;
    printf("\nEnter the number of Vertices in the Graph : ");
    scanf("%d",&n);
    printf("\nEnter the Adjacency Matrix\n\n");
    for (i = 1; i <= n; i++)
        for (j = 1; j<= n; j++)
            scanf("%d",&adj[i][j]);
    for (i = 1; i <= n; i++)
        visited[i] = 0;
}


int dfs(int start)
{
    int stack[MAX];
    int top=-1,i;
    printf("%d - ",start);
    visited[start]=1;
    stack[++top]=start;
    while(top!=-1)
    {
      start=stack[top];
      for(i=1;i<=MAX;i++)
      {
         if(adj[start][i]&&visited[i]==0)
          {
             stack[++top]=i;
             printf("%d-",i);
             visited[i]=1;
             break;
           }
       }

     if(i==MAX)
             top--;
    }
    return 0;
}

int main()
{

    int source;
    printf("\n Program for Depth First Search for an un-directed Graph");
    readmatrix();
    printf("\nEnter the Source : ");
    scanf("%d",&source);
    printf("\nThe nodes visited in the DFS order is : ");
    dfs(source);
    printf("\n");
    return 0;
}

Program for Breadth First Search in a graph using C

#include

#define MAX 10

int n;
int adj[MAX][MAX
];
int visited[MAX];
void readmatrix()
{
    int i,j;
    printf("\nEnter the number of Vertices in the Graph : ");
    scanf("%d",&n);
    printf("\nEnter the Adjacency Matrix\n\n");
    for (i = 1; i <= n; i++)
        for (j = 1; j<= n; j++)
            scanf("%d",&adj[i][j]);
    for (i = 1; i <= n; i++)
        visited[i] = 0;
}

void bfs(int source)
{
    int queue[MAX];
    int i, front, rear, root;
    front = rear = 0;
    visited[source] = 1;
    queue[rear++] = source;
    printf("%d   ",source);
    while (front != rear)
    {
        root = queue[front];
        for (i = 1; i <= n; i++)
            if (adj[root][i] && !visited[i])
            {
                visited[i] = 1;
                queue[rear++] = i;
                printf("%d   ",i);
            }
        front++;
    }
}

int main()
{
    int source;
    printf("\n Program for Breadth First Search for a un-directed Graph");
    readmatrix();
    printf("\nEnter the Source : ");
    scanf("%d",&source);
    printf("\nThe nodes visited in the BFS order is : ");
    bfs(source);
    return 0;
}