Data Structures with C

Write a program that create a linked list consisting of nodes of the following struct type and searches the record of a student whose roll_number is given by the user. 

Define RED-BLACK trees. Consider the red-black tree shown below and insert the item 50 into the tree and write the final red-black tree. 

Obtain the optimal binary search tree for the following items and associated probability 

Construct an AVL tree by inserting the elements MAR, MAY, NOV, AUG, APRIL, JAN,DEC, JULY, FEB, JUNE, OCT, SEPT. 

Obtain the shortest(x) and weight(x) for each node in the following binary trees and identify which is height-based leftist tree and which is weight-based leftist tree.

Explain the activities to be performed to delete a node from a binary tree and write C-function to delete an item from the tree. 

Suppose the following list of number is inserted in order into an empty binary search tree(BST) 70 80 60 65 50 45 55, 

i) Construct the binary search tree

ii) Find in order, pre-order and pos-order traversal of BST created

iii) is the BST constructed at AVL tree? State reasons for your claim. Further if your answer is negative balance the tree so that it becomes an AVL tree. 

List various types of threaded binary trees. Explain in-threaded binary tree.

Define max-heap and min-heap. How will you represent a max-heapras an array? Write an algorithm to insert an element to a max-heap. Create a max-heap 100 200-10-30-60 80 90 300.

Write a C-function to insert an item into a binary tree based on direction.

Explain how to reverse and invert a given singly linked list with an example and write its C-function.

List out the difference between singly linked list and doubly linked list. What are the advantages of circular list?

Write a recursive function to print the permutation of a string (ABC) passed to it as an argument.

What is the disadvantage of queue which is implemented using array and how to overcome it? 

Write a program to check whether a given string is palindrome or not using stack.

Differentiate between stack and queue. How are they related to LIFO and FIFO concept?

Write an algorithm to evaluate a postfix expression. Use a stack to evaluate the following postfix arithmetic expression. Show the changing status of the stack in tabular form.

(AB + C-BA+CS-)for given A = 1, B = 2, C = 3. 

With the help of an example, explain sparse matrix. How the sparse matrix is represented in memory. Design the algorithm to transpose a given matrix represented as triplos in a 1-D array 

Design algorithm to add two polynomials using ADT polynomial.

Describe unions used in C. How is it different from structures?

Explain how address calculation is done in row major ordering for a 2- dimensional array,Also generalize for n-dimension

Explain how memory can be dynamically allocated using realloc( ).

Obtain the step count for the C-function to add two matrices of M x N size using counting method and tabular method. 

What is the purpose of using free( )? With an example explain the problem that occur when free() is not used.