## Sunday, August 23, 2009

### Classify the Hashing Functions based on the various methods by which the key value is found.

Direct method, Subtraction method, Modulo-Division method, Digit-Extraction method, Mid-Square method, Folding method, Pseudo-random method.

## Saturday, August 22, 2009

### 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.

## Friday, August 21, 2009

### Minimum number of queues needed to implement the priority queue?

Two. One queue is used for actual storing of data and another for storing priorities.

## Wednesday, August 19, 2009

### 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.

## Tuesday, August 18, 2009

### Given a binary search tree and a "target" value, search the tree to see if it contains the target.

static int lookup(struct node* node, int target) { // 1. Base case == empty tree // in that case, the target is not found so return false if (node == NULL) { return(false); } else { // 2. see if found here if (target == node->data) return(true); else { // 3. otherwise recur down the correct subtree if (target <>data) return(lookup(node->left, target)); else return(lookup(node->right, target)); } }}

## Monday, August 17, 2009

### Given a binary search tree and a "target" value, search the tree to see if it contains the target.

static int lookup(struct node* node, int target) { // 1. Base case == empty tree // in that case, the target is not found so return false if (node == NULL) { return(false); } else { // 2. see if found here if (target == node->data) return(true); else { // 3. otherwise recur down the correct subtree if (target <>data) return(lookup(node->left, target)); else return(lookup(node->right, target)); } }}

## Sunday, August 16, 2009

### Generate a Mirror Image of a tree. Change a tree so that the roles of the left and right pointers are swapped at every node

void mirror(struct node* node) {

if (node==NULL) {

return;

}

else {

struct node* temp; // do the subtrees

mirror(node->left); mirror(node->right); // swap the pointers in this node

temp = node->left;

node->left = node->right;

node->right = temp;

}

}

if (node==NULL) {

return;

}

else {

struct node* temp; // do the subtrees

mirror(node->left); mirror(node->right); // swap the pointers in this node

temp = node->left;

node->left = node->right;

node->right = temp;

}

}

## Saturday, August 15, 2009

### finding Nth Node in linked list..

int GetNth(struct node* head, int index) {

struct node* current = head; int count = 0; // the index of the node we're currently looking at while (current != NULL) { if (count == index) return(current->data); count++; current = current->next; } assert(0); // if we get to this line, the caller was asking // for a non-existent element so we assert fail.}

struct node* current = head; int count = 0; // the index of the node we're currently looking at while (current != NULL) { if (count == index) return(current->data); count++; current = current->next; } assert(0); // if we get to this line, the caller was asking // for a non-existent element so we assert fail.}

## Friday, August 14, 2009

### Source code for Binary search method

int binarySearch(int value) {

low = 0; high = N; while (low < mid =" (low" low =" mid" high =" mid-1:">= value, //so high can't be < mid if A[mid] == value high = mid; } // high == low, using high or low depends on taste if (low < N) and (A[low] == value) return low // found else return -1 // not found

}

low = 0; high = N; while (low < mid =" (low" low =" mid" high =" mid-1:">= value, //so high can't be < mid if A[mid] == value high = mid; } // high == low, using high or low depends on taste if (low < N) and (A[low] == value) return low // found else return -1 // not found

}

## Thursday, August 13, 2009

### Deletion of linked list

void DeleteList(struct node** headRef) {

struct node* current = *headRef; // deref headRef to get the real

headstruct node* next;

while (current != NULL) {

next = current->next; // note the next pointer

free(current); // delete the node

current = next; // advance to the next node

}

*headRef = NULL; // Again, deref headRef to affect the real head back// in the caller.

}

struct node* current = *headRef; // deref headRef to get the real

headstruct node* next;

while (current != NULL) {

next = current->next; // note the next pointer

free(current); // delete the node

current = next; // advance to the next node

}

*headRef = NULL; // Again, deref headRef to affect the real head back// in the caller.

}

Subscribe to:
Posts (Atom)