Section - A
1. Answer any Six question.
a. What is Dynamic memory allocation
Dynamic memory allocation is the process of allocating memory during the execution of a program. In data structures, dynamic memory allocation is commonly used to create dynamic data structures such as linked lists, trees, and graphs.
b. What is pointer in C? Give syntax and examples.
In C, a pointer is a variable that stores the memory address of another variable. A pointer provides a way to indirectly access and manipulate the value of a variable by referring to its memory address.
The syntax for declaring a pointer variable in C is as follows:
<datatype> *<pointer variable>;
Example :
int *ptr;
c. What is towers of Honai? Mention constraints.
The Towers of Hanoi is a classic puzzle game that involves moving a stack of discs from one peg to another, using a third peg as an intermediate.
The constraints of the puzzle are:
- The number of pegs must be three.
- The number of discs can be any positive integer, but typically it is between three and eight.
- The discs must be initially placed on one peg in a stack, in increasing order of size from top to bottom.
d. Define sequential search? List its advantages.c. What is towers of Honai? Mention constraints.
Sequential search, also known as linear search, is a searching algorithm used to find the position of a target value within a list or array of values.
- Simplicity
- Versatility
- Efficiency for small data sets
- Space efficiency
e. Convert infix to postfix notation.
a. A*B+C
- A B C * +
b.(A+B)*C-D
- A B * C D – *
f. What is priority queue mention different types of it.
A priority queue is an abstract data type that is similar to a regular queue or stack, but with the added feature that each element has a priority associated with it.
- Max priority queue
- Min priority queue
g. What is singly linked list? How do you declare it?
A singly linked list is a data structure in which each node contains a value and a reference to the next node in the list.
struct Node
{
int data;
struct Node *next;
}
*head = NULL;h. What is strictly binary tree? Give examples.
A strictly binary tree is a binary tree in which each node has either zero or two children. In other words, there are no nodes in the tree with only one child.
Example :
1
/ \
2 3
/ \ / \
4 5 6 7
Section - B
2. Answer any three question of the following
a. What is data structure? Define primitive and non- primitive data structure.
A data structure is a way of organizing and storing data in a computer so that it can be accessed and used efficiently. It provides a way to manage large amounts of data and perform operations on that data in an efficient manner.
Example : array, linked list, graph, pointer, tree, stack and queue.
- Primitive Data Structures:
- These are the basic data structures that are built into a programming language. They are simple and directly operate on the values they contain.
Some examples of primitive data structures include:
- Integer: Used to represent whole numbers.
- Float: Used to represent decimal numbers.
- Character: Used to represent individual characters.
- Boolean: Used to represent true/false values.
2. Non-Primitive Data Structures:
- These are more complex data structures that are built using primitive data types. They are also referred to as composite data structures.
Some examples of non-primitive data structures include:
- Arrays: Used to store a collection of elements of the same data type.
- Linked Lists: Used to store a collection of nodes, where each node contains a value and a reference to the next node.
- Trees: Used to store a hierarchical structure of nodes, where each node has one or more child nodes.
- Graphs: Used to store a collection of nodes and edges that connect those nodes.
b. Write a short note on malloc , calloc and realloc.
1.Malloc()
malloc() is a memory allocation function in the C programming language. It is used to dynamically allocate memory during program execution, which means that memory is allocated on the fly as needed rather than at compile time.
Example :
// Allocate memory for an array of 10 integers
numbers = (int*) malloc(10 * sizeof(int));
2.Calloc()
calloc() is a memory allocation function in the C programming language, similar to malloc(). However, calloc() differs from malloc() in that it initializes the allocated memory to zero before returning a pointer to it.
Example :
// Allocate memory for an array of 10 integers
numbers = (int*) calloc(10, sizeof(int));
3.Realloc()
- realloc() is a memory allocation function in the C programming language that is used to change the size of a previously allocated memory block.
- The realloc() function takes two parameters: a pointer to the original memory block and the new size in bytes of the block
Example :
// Allocate memory for an array of 10 integers
numbers = (int*) malloc(10 * sizeof(int));
c. Write advantages and disadvantages of using pointers
Advantages of using pointers in programming :
- Memory efficiency: Pointers allow you to manipulate data directly in memory, which can be more efficient than using variables or arrays.
- Flexibility: Pointers allow you to access and modify data structures directly, which can be more flexible than using copy or move operations.
- Passing by reference: Pointers can be used to pass variables or data structures to functions by reference, which can be more efficient and allow for in-place modifications.
- Dynamic memory allocation: Pointers allow you to dynamically allocate and deallocate memory, which can be useful for managing memory resources in complex applications.
Disadvantages of using pointers in programming :
- Memory leaks: If pointers are not properly managed, they can cause memory leaks, where memory that is no longer needed is not freed, resulting in wasted memory resources.
- Null pointers: Pointers can be null, meaning they do not point to any valid memory location. Dereferencing a null pointer can result in a program crash or undefined behavior.
- Segmentation faults: Accessing memory through an invalid pointer can result in a segmentation fault, where the program crashes due to an illegal memory access.
- Complex syntax: Pointers can have complex syntax, which can make them difficult to use and understand, especially for beginners.
d. With example write a simple program in C to access address and value of variables using pointers.
/* Simple Print address of Variable Using Pointer in C*/
/* Print Pointer Address Program,C Pointer Examples */
#include <stdio.h>
int main()
{
int a;
int *pt;
printf("Pointer Example Program : Print Pointer Address\n");
a = 10;
pt = &a;
printf("\n[a ]:Value of A = %d", a);
printf("\n[*pt]:Value of A = %d", *pt);
printf("\n[&a ]:Address of A = %p", &a);
printf("\n[pt ]:Address of A = %p", pt);
printf("\n[&pt]:Address of pt = %p", &pt);
printf("\n[pt ]:Value of pt = %p", pt);
return 0;
}Section - C
3. Answer any three question of the following
a. What is recursion? Write comparison between iterative and recursive function.
Recursion is a programming technique where a function calls itself directly or indirectly in order to solve a problem. In other words, a function is said to be recursive if it calls itself during its execution.
b. Write a C program to generate binomial coefficient using recursive function.
/* C Program to calculate Binomial coefficient using Recursion */
#include<stdio.h>
int BC(int n, int k);
int main()
{
int n,k;
printf("Enter n and k : ");
scanf("%d%d",&n,&k);
printf("%\nBinomial coefficient\n",BC(n,k));
printf("%d\n",BC(n,k));
return 0;
}
int BC(int n, int k)
{
if(k==0 || k==n)
return 1;
return BC(n-1,k-1) + BC(n-1,k);
}c. Write an algorithm deleting elements of arrays.
Inputs:
array A of size n in the data structure
index i of element to be deleted, where 0 <= i < n
Outputs:
array A in the data structure with element at index i deleted
- If i is less than 0 or greater than or equal to n, return A.
- Create a new array B of size n-1.
- Copy the elements of A from index 0 to index i-1 to the corresponding positions in B.
- Copy the elements of A from index i+1 to index n-1 to the corresponding positions in B starting at index i.
- Update the size of the array in the data structure to be n-1.
- Free the memory occupied by the old array A.
- Set the pointer to the new array B as the array in the data structure.
Return the updated array A.
d. Compare quick sort and selection sort.
- Time complexity: Quick sort has an average-case time complexity of O(n log n), while selection sort has an average-case time complexity of O(n^2). This means that quick sort is generally faster than selection sort for large arrays.
- Comparison-based sorting: Both algorithms are comparison-based sorting algorithms, meaning they compare elements to each other to determine their relative order. However, quick sort is generally faster than selection sort because it uses a more efficient comparison-based sorting approach.
- Memory usage: Quick sort sorts the array in-place, without requiring additional memory. Selection sort, on the other hand, requires additional memory to store the sorted elements.
- Stability: Quick sort is not a stable sorting algorithm, meaning that the order of equal elements in the original array may not be preserved in the sorted array. Selection sort is also not a stable sorting algorithm.
Section - D
4. Answer any three question of the following
a. Explain Application of stack in function calls.
One of the most common applications of the stack data structure is in managing function calls in computer programs. When a function is called, the computer stores the current state of the program, including the values of variables and the address of the next instruction to be executed, on the stack. This allows the function to execute without interfering with the state of the program outside of the function.
When the function completes execution, the program retrieves the saved state from the stack and resumes execution at the next instruction after the function call. This allows programs to easily call and return from functions without having to manage the state of the program manually.
The stack data structure also allows for nested function calls, where one function calls another function, which in turn calls another function, and so on. Each function call is stored on the stack, so that when the innermost function completes execution, the program can retrieve the state of the outer function and resume execution from the point where it left off.
b. Explain working of circular queue.
Here is how a circular queue works:
Initialize the queue: Create an array of fixed size and initialize the front and rear pointers to point to the first element of the array.
Enqueue an element: To add an element to the circular queue, first check if the queue is full by comparing the (rear+1)%size to the front pointer. If the result is true, the queue is full, and you cannot add any more elements. If the queue is not full, increment the rear pointer by 1 and add the new element at the rear position. If the rear pointer exceeds the size of the array, set it to 0 to create a circular effect.
Dequeue an element: To remove an element from the circular queue, first check if the queue is empty by comparing the front and rear pointers. If they are equal, the queue is empty, and you cannot remove any more elements. If the queue is not empty, remove the element at the front position, increment the front pointer by 1, and return the removed element. If the front pointer exceeds the size of the array, set it to 0 to create a circular effect.
Peek at the front element: To see the element at the front of the queue without removing it, simply return the element at the front position.
Clear the queue: To clear all the elements from the queue, simply set the front and rear pointers to the first position of the array.
c. Write an algorithm evaluation of postfix expression using stack. Algorithm to evaluate postfix expression.
Here is an algorithm to evaluate a postfix expression using a stack:
- Initialize an empty stack.
- Scan the postfix expression from left to right.
- If the current character is an operand, push it onto the stack.
- If the current character is an operator, pop the top two operands from the stack, perform the operation, and push the result back onto the stack.
- Continue scanning the expression until you reach the end.
- When the entire expression has been scanned, the final result will be the only element left on the stack.
- Pop the final result from the stack and return it as the answer.
Here is an example of how to evaluate the postfix expression “2 3 * 4 +”:
- Initialize an empty stack.
- Scan the expression from left to right.
- Push 2 onto the stack.
- Push 3 onto the stack.
- Pop 3 and 2 from the stack, multiply them together, and push the result (6) onto the stack.
- Push 4 onto the stack.
- Pop 4 and 6 from the stack, add them together, and push the result (10) onto the stack.
- The entire expression has been scanned, and the final result is 10.
- Pop 10 from the stack and return it as the answer.
d. What is queue? Write basic concepts.
Queue is defined as a linear data structure that is open at both ends and the operations are performed in First In First Out (FIFO) order.
The basic concepts of a queue include :
- FIFO (First In First Out): The element that is added first to the queue will be the first one to be removed from the queue.
- Enqueue: Adding an element to the rear of the queue.
- Dequeue: Removing an element from the front of the queue.
- Rear: The last element of the queue.
- Front: The first element of the queue.
- Empty queue: A queue with no elements.
- Full queue: A queue with no space for more elements.
- Circular queue: A type of queue where the last element points to the first element.
- Priority queue: A type of queue where elements have a priority associated with them, and the element with the highest priority is removed first.
- Blocking queue: A type of queue where the operations like enqueue and dequeue block when the queue is full or empty, respectively.
Section - E
5. Answer any three question of the following
a. Explain the types of linked lists.
1.Singly Linked Lists
Singly linked lists contain two “buckets” in one node; one bucket holds the data and the other bucket holds the address of the next node of the list. Traversals can be done in one direction only as there is only a single link between two nodes of the same list.
2.Doubly Linked Lists
Doubly Linked Lists contain three “buckets” in one node; one bucket holds the data and the other buckets hold the addresses of the previous and next nodes in the list. The list is traversed twice as the nodes in the list are connected to each other from both sides.
3.Circular Linked Lists
Circular linked lists can exist in both singly linked list and doubly linked list.
Since the last node and the first node of the circular linked list are connected, the traversal in this linked list will go on forever until it is broken.
b. Define the following terms :
1.Node
- A node is a fundamental unit of a tree data structure that contains some data and pointers to its child nodes, if any. In a binary tree, for example, each node can have at most two child nodes.
2.Terminal node
- A terminal node, also called a leaf node, is a node that does not have any child nodes. It is usually at the bottom of the tree and represents a final or intermediate result.
3.Non-terminal node.
- A non-terminal node, also called an internal node or parent node, is a node that has at least one child node. It is usually not at the bottom of the tree and represents an intermediate result or operation.
c. Write an algorithm to display in-order traversal of a binary tree.
An in-order traversal of a binary tree means visiting the nodes in the order of: left subtree, root node, right subtree. Here’s an algorithm to perform an in-order traversal of a binary tree :
- Check if the root node is null. If so, return.
- Traverse the left subtree by recursively calling the in-order traversal function on the left child node.
- Display the value of the root node.
- Traverse the right subtree by recursively calling the in-order traversal function on the right child node.
function inOrderTraversal(node):
if node is null:
return
inOrderTraversal(node.left)
display(node.value)
d. Define the following terms :
Heap tree
Heap tree: A heap tree is a binary tree that satisfies the heap property. The heap property requires that the key of each node in the tree is greater than or equal to (for a max heap) or less than or equal to (for a min heap) the key of its parent node. Heap trees are commonly used in heap data structures, which are often used to implement priority queues.
Binary search tree.
Binary search tree: A binary search tree is a binary tree in which each node has at most two children, and the value of each node is greater than or equal to all the values in its left subtree and less than or equal to all the values in its right subtree. Binary search trees are often used to implement search algorithms because their structure enables efficient searching and sorting operations.
Complete binary tree.
Complete binary tree: A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. Complete binary trees have a number of useful properties, such as being easy to store in an array or list.