The document provides definitions and explanations of various data structures and algorithms.
1) It begins by defining static and dynamic arrays, and explaining that static arrays have a fixed size set at compile time while dynamic arrays can change in size during runtime.
2) It then explains the stack data structure, describing it as linear structure that follows LIFO principles with push and pop operations.
3) Next, it compares arrays and queues, noting that queues follow FIFO while arrays allow insertion and deletion at any index but have fixed sizes.
4) The document continues by explaining concepts like linked lists, sequential searches, sorting algorithms like radix sort, tree structures like B-Trees, and ways to represent graphs in
The document provides definitions and explanations of various data structures and algorithms.
1) It begins by defining static and dynamic arrays, and explaining that static arrays have a fixed size set at compile time while dynamic arrays can change in size during runtime.
2) It then explains the stack data structure, describing it as linear structure that follows LIFO principles with push and pop operations.
3) Next, it compares arrays and queues, noting that queues follow FIFO while arrays allow insertion and deletion at any index but have fixed sizes.
4) The document continues by explaining concepts like linked lists, sequential searches, sorting algorithms like radix sort, tree structures like B-Trees, and ways to represent graphs in
The document provides definitions and explanations of various data structures and algorithms.
1) It begins by defining static and dynamic arrays, and explaining that static arrays have a fixed size set at compile time while dynamic arrays can change in size during runtime.
2) It then explains the stack data structure, describing it as linear structure that follows LIFO principles with push and pop operations.
3) Next, it compares arrays and queues, noting that queues follow FIFO while arrays allow insertion and deletion at any index but have fixed sizes.
4) The document continues by explaining concepts like linked lists, sequential searches, sorting algorithms like radix sort, tree structures like B-Trees, and ways to represent graphs in
The document provides definitions and explanations of various data structures and algorithms.
1) It begins by defining static and dynamic arrays, and explaining that static arrays have a fixed size set at compile time while dynamic arrays can change in size during runtime.
2) It then explains the stack data structure, describing it as linear structure that follows LIFO principles with push and pop operations.
3) Next, it compares arrays and queues, noting that queues follow FIFO while arrays allow insertion and deletion at any index but have fixed sizes.
4) The document continues by explaining concepts like linked lists, sequential searches, sorting algorithms like radix sort, tree structures like B-Trees, and ways to represent graphs in
PART A [Mohammed Ayyub] 1. Define static and dynamic array in data structure? The Static Data Structure has a fixed memory size, and its size cannot be randomly updated during the run time. The Dynamic Data Structure does not have any fixed memory size, and its size can be randomly updated during the run time. Memory is allocated the data structure during compile time. 2. Explain stack? A Stack is a linear data structure in which elements can be inserted and deleted only from one side of the list, called the top. A stack follows the LIFO (Last In First Out) principle, i.e., the element inserted at the last is the first element to come out. The insertion of an element into the stack is called push operation, and the deletion of an element from the stack is called pop operation.
3. Write difference between array and queue.
Queues: • Operate on FIFO principle. • Insertion and deletion from rear and front. • Can have dynamic or fixed size. Arrays: • Elements accessed by index. • Allow insertion and deletion at any index. • Have a fixed size. 4. Write concept of header linked list in data structure. A header linked list is a type of linked list that has a header node at the beginning of the list. In a header linked list, HEAD points to the header node instead of the first node of the list. The header node does not represent an item in the linked list. This data part of this node is generally used to hold any global information about the entire linked list. The next part of the header node points to the first node in the list. 5.What do you mean by sequential search? Sequential search, also known as linear search, is a simple searching algorithm that finds the position of a target value within a list or array. It sequentially checks each element of the list until a match is found or the entire list has been searched.
6. Define radix sort.
Radix sort is a sorting algorithm that sorts the elements by first grouping the individual digits of the same place value. Then, sort the elements according to their increasing/decreasing order. 7. Explain B-Tree. A B-tree is a self-balancing tree where all the leaf nodes are at the same level which allows for efficient searching, insertion and deletion of records. Because of all the leaf nodes being on the same level, the access time of data is fixed regardless of the size of the data set.
8. Define complete binary tree.
A complete binary tree is a special type of binary tree where all the levels of the tree are filled completely except the lowest level nodes which are filled from as left as possible.
9. How to represent graph in memory? Explain.
Graphs in computer memory are commonly represented using either an adjacency matrix (a 2D array indicating edges between nodes) or an adjacency list (each node has a list of connected nodes).
10. Explain Double Hashing.
Double hashing is a collision resolution technique used in hash tables. Double hashing in hash tables uses two hash functions: one for the initial hash value and another for the step size in the probing sequence. PART B [Ayan Mohammed]
1. Convert following infix expression to postfix
expression. a. A+B/C-D^E-F ABC/+DE^-F b. A/B-(C+D)*E/F^G AB/CD+E*FG^/-
2. Write an algorithm to insert a node in doubly linked
list. 1. Create a new node with the given data. 2. If the list is empty, set the new node as the head. 3. If the new node is to be inserted at the beginning: a. Set the next of the new node as the current head. b. Set the previous of the current head to the new node. c. Update the head to point to the new node. 4. If the new node is to be inserted at the end: a. Traverse the list to reach the last node. b. Set the next of the last node to the new node. c. Set the previous of the new node to the last node. 5. If the new node is to be inserted at a specific position: a. Traverse the list to reach the position. b. Adjust the pointers of the adjacent nodes to include the new node. 6. Return the updated linked list.
3. Explain binary search technique in detail.
Initialization : Start with two pointers, low and high, pointing to the beginning and end of the sorted array. Iterative Process : 1.While low is less than or equal to high, calculate the middle index as (low + high) 2. Compare the middle element with the target value. Updating Pointers :If the middle element is equal to the target, return the index. If the target is less than the middle element, update high to mid - 1 to search in the lower half. If the target is greater than the middle element, update low to mid + 1 to search in the upper half. Termination : Repeat the process until the target is found or low is greater than high. If the target is not found, return a special value (e.g., -1) to indicate absence. [Mohit Tiwari]
4. Discuss the operations performed on a binary tree.
• Insertion: Adding a new node to the tree. To maintain the binary tree property, nodes are typically inserted based on comparisons with existing nodes, placing smaller values to the left and larger values to the right. • Traversal: • Pre-order: Visit the root node, then the left subtree, and finally the right subtree. • In-order: Visit the left subtree, then the root node, and finally the right subtree. This results in elements being visited in sorted order for a binary search tree. • Post-order: Visit the left subtree, then the right subtree, and finally the root node. • Searching: Finding a specific node based on its value. It typically involves traversing the tree according to certain rules (like left for smaller values, right for larger values). • Deletion: Removing a node while maintaining the binary tree properties. It involves different cases like deleting a leaf node, a node with one child, or a node with two children. PART C [Aman Khokar]
1. a. How to perform factorial calculation using
stack? explain.
int fact(int n){
int f = 1; if (n == 0 || n == 1){ return (1); } else{ f = n * fact(n-1); return (f) } } Void main(){ int n; printf(“Enter value of n”); scanf(“%d”, &n); Result = fact(n) }
As we can see from the above example, the recursive calls in the fact function create a stack of function calls, and the values are pushed onto the stack during the recursive calls. As the base case is reached (when n becomes 0 or 1), the stack starts to unwind, and each function call returns its result, popping the corresponding frames off the stack. The PUSH and POP are the basic operations of stack and can be further understood through diagram.
1. b. Write an algorithm to delete an item from
circular Queue. ALGORITHM
◦ STEP 1 START ◦ STEP 2 Store the element to delete. (This step is preparing to return the deleted element if needed.) ◦ STEP 3 If front == -1 then Queue Underflow. (This is a check to ensure that the circular queue is not empty before attempting to delete an element.) ◦ STEP 4 Element deleted from queue is arr[front]. (This step retrieves the element to be deleted from the front of the circular queue.) ◦ STEP 5 if (front==rear) then front= -1; rear= -1; else go to (If the front and rear pointers are equal after deletion, it means there was only one element, and the queue should be reset.) ◦ STEP 6 if (front == MAX - 1) then front= 0 else go to (If the front pointer is at the end of the circular queue, it wraps around to the beginning.) ◦ STEP 7 front = front + 1. (Move the front pointer to the next position in the circular queue.) ◦ STEP 8 STOP. 2. a. Explain circular linked list. Write an algorithm to insert a node into circular linked list. • Circular linked list is a variation of linked list in which the first elements points to the next element and the last element points to the first element.(refer diagram) • Circular linked list can be used to help traverse the same list again and again if needed.
• Each node in a circular linked list has two fields: • Data: The value stored in the node. • Next: A reference to the next node in the sequence. ALGORITHM ◦ STEP 1 IF PTR = NULL, Write OVERFLOW ◦ STEP 2 SET NEW_NODE = PTR ◦ STEP 3 SET PTR = PTR -> NEXT (Move the pointer (PTR) to the next node in the list.) ◦ STEP 4 SET NEW_NODE -> DATA = VAL (Set the data of NEW_NODE to a given value (VAL).) ◦ STEP 5 SET NEW_NODE -> NEXT = HEAD (Make the "NEXT" pointer of NEW_NODE point to the current head of the list.) ◦ STEP 6 SET TEMP = HEAD ◦ STEP 7 Repeat Step 8 while TEMP -> NEXT != HEAD (Loop through list until reaching the last node (where TEMP- >NEXT is head).) ◦ STEP 8 SET TEMP = TEMP -> NEXT [END OF LOOP] ◦ STEP 9 SET TEMP -> NEXT = NEW_NODE (Set the "next" pointer of the last node (TEMP->NEXT) to point to NEW_NODE.) ◦ STEP 10 STOP.
2. b. Discuss insertion sort with suitable example.
Insertion Sort is a straightforward way to sort a list by gradually
building a sorted part. It's good for small lists but not great for big ones. It's adaptive, meaning it's faster if the list is partially sorted. It's better than Selection Sort and Bubble Sort. It uses minimal extra memory and is stable (keeps the order of equal elements). Here's how it works: • Start with the first element; it's considered sorted; save it to to a variable (KEY). • Check from each element, insert it into the sorted part, and repeat until the list is sorted. It can be further understood by following example :
[Anurag Saini] 5 b.Write down the algorithm of Bubble Sort. Sort the following elements using bubble sort. 68, 98, 35, 48, 62, 52, 30. Bubble sort repeatedly swaps adjacent elements until they are in the correct order, resembling the rising movement of air bubbles in water. ALGORITHM ◦ STEP 1 Start with an array arr. ◦ STEP 2 For each element in the array: If arr[i] > arr[i+1], swap the elements. ◦ STEP 3 Repeat Step 2 for each pass through the array until no more swaps are needed. ◦ STEP 4 Return the sorted array. ◦ STEP 5 End Bubble Sort algorithm.
