DataStructures using C KTU S3

Questions

Cycle - 1 (Pointer Applications)

1. You are given two arrays sorted in ascending order. Write a C Program to merge the elements of the two arrays and to form a single array sorted in ascending order.
2. Given a string s, write a C program to find the length of the longest substring without repeating characters. Also, display the substring.
3. Write a program to find the smallest number in a list of integers using pointers
4. Implement the following string library functions using pointers:
   1. String length
   2. String copy
   3. String comparison
   4. String concatenation
5. Implement bubble sort without using an array (Use pointers instead).

Cycle - 2 (Search Operations)

1. Implement Linear Search.
2. Implement Binary Search.
3. Implement Stack using an array.
4. Write a program in C to check whether a string is palindrome or not, using stack.

Cycle - 3 (Linear DataStructures)

1. Using stack, convert an infix expression to a postfix expression and evaluate the postfix expression.
2. Write a program to convert an infix expression to a prefix expression using stack.
3. Convert an infix expression to a postfix expression without using stack.
4. Implement a Queue using arrays with the operations:
   1. Insert elements into the queue
   2. Delete elements from the queue
   3. Display the contents of the queue after each operation
5. Implement a Circular Queue using arrays with the operations:
   1. Insert elements into the queue
   2. Delete elements from the queue
   3. Display the contents of the queue after each operation
6. Implement a Priority Queue using arrays with the operations:
   1. Insert elements into the queue
   2. Delete elements from the queue
   3. Display the contents of the queue after each operation
7. Implement a Double-Ended Queue using arrays with the operations:
   1. Insert elements into the queue (both front and size)
   2. Delete elements from the queue (both front and size)
   3. Display the contents of the queue after each operation

Cycle - 4 (Sparse Matrix and Polynomials)

1. Write a program to read two polynomials and store them in an array. Calculate the sum of the two polynomials and display the first polynomial, the second polynomial and the resultant polynomial.
2. Write a program to enter two matrices in normal form. Write a function to convert two matrices to a tuple form and display it. Also, find the transpose of the two matrices represented in tuple form and display it. Find the sum of the two matrices in tuple form and display the sum in tuple form.

Cycle - 5 (Linked List)

1. Write a menu-driven program for performing the following operations on a linked list
   1. Display
   2. Insert at beginning
   3. Insert at the end
   4. Insert at a specified position
   5. Delete from the beginning
   6. Delete from the end
   7. Delete from a specified position
2. Create a doubly linked list from a string taking each character from the string. Check if the string is palindrome in an efficient method.
3. Implement a stack using a linked list with the operations:
   1. Push
   2. Pop
   3. Display the contents of the stack
4. Implement a queue using linked lists with the following operations
   1. Enqueue
   2. Dequeue
   3. Display the contents of the queue
5. Write a program to reverse the contents of a queue using stack
6. Write a program to read two polynomials and store them using a linked list. Calculate the sum of the two polynomials and display the first polynomial, the second polynomial and the resultant polynomial.
7. Write a program to read two polynomials and store them using a linked list. Calculate the product of the two polynomials and display the first polynomial, the second polynomial and the resultant polynomial.
8. Write a program for addition of polynomials containing two variables using a linked list. The terms of the polynomials are ordered by the power of the first variable and then the second variable, in the descending order. Eg: 4.x^3.y^1 + 2.x^2.y^3 + 5.x^1.y^2+7.y^2+7.y^1+5
9. The details of students (number, name and total mark) are to be stored in a linked list. Write functions for the following operations:
   1. Insert (at the beginning)
   2. Delete (based on number)
   3. Search (based on name or number)
   4. Sort on the basis of number
   5. Display

Cycle - 6 (Tree)

1. Create a binary tree with the following operations
   1. Insert a new node
   2. Inorder traversal
   3. Preorder traversal
   4. Postorder traversal
   5. Delete a node
2. Write a program to create a binary search tree (data items are integers) with the following operations
   1. Insert a new node
   2. Inorder traversal
   3. Preorder traversal
   4. Postorder traversal
   5. Delete a node
   6. Find the number of leaf nodes
   7. Sort the input numbers

Cycle - 7 (Graph)

1. Represent any given graph and perform depth first search and breadth first search.

Cycle - 8 (Sorting)

1. Implement bubble sort, insertion sort, selection sort, quick sort, merge sort and heap sort.

Cycle - 9 (Hashing)

1. Implement a hash table using the chaining method. Use Linear Probing for collision resolution.