Data structures

Happy reading...😊

1)What are the real time application of data structures?

1.For representing a city region telephone network.
2.To implement back functionality in the internet web browser.
3.To store dynamically growing data which is accessed very         frequently, based upon a key value.
5.To implement the undo function in a text editor.
6.To store information about the directories and files in a system.

2)List the area of application of data structures.

Compiler Design

Operating System

Database Management System

Statistical analysis package

Numerical Analysis

Graphics

Artificial Intelligence

Simulation

3)Which is the common asymptotic notations that we use?
The upper bound ,O(n) that is used to find the worst case is used most.

4)When can you tell that a Memory Leak will occur?

A memory leak occurs when a program does not free a block of memory allocated dynamically

5)Given the address of first element, how to calculate 

address of any other element?

  Loc (arr [k]) = base (arr) + w * k

   w = number of bytes per storage location 

       of for one element 

   k = index of array whose address we want 

       to calculate

 array : m X n

column major:

Loc(arr[i][j]) = base(arr) + w (m *j + i)

row major:

Loc(arr[i][j]) = base(arr) + w (n*j + i)

6)What are the applications of stack?

Infix to postfix conversion

Function call

Evaluation of postfix expression

Reverse of the string using stack

Checking balanced parentheses in an expression

Tower of Hanoi

7)List some of the applications of queue.
used in printer, disk for waiting list
used in asynchronous data transfer ex: file i/o, socket
buffer in MP3 ,CD player etc.
used to handle interrupts in operating system

8)What is the draw back of linear queue?How can this be corrected?

When any element is inserted in linear queue then rear will be increased by 1. 

Let, assume after insertion operations rear is shifted to last position in queue. It means, now queue is full. Now if a new element is inserted then overflow condition will occur.

Now, if we delete some elements from queue then front will be increased by 1. 

After deletion memory space occupied by those elements will be blank and you want to add some more element. But it cannot possible because rear is still pointing to the last position and it shows overflow. Hence, we cannot able to reuse free memory space present in linear/static queue and memory is not effectively used.

Instead we can use circular linked list,where once the index reaches the last position, it checks if the front is empty or full.

9)What are the scenario in which we can insert an element in circular queue?

• If (rear + 1)%maxsize = front, the queue is full. In that case, overflow occurs and therefore, insertion can not be performed in the queue.
• If rear != max - 1, the rear will be incremented to the mod(maxsize) and the new value will be inserted at the rear end of the queue.
• If front != 0 and rear = max - 1, it means that queue is not full therefore, set the value of rear to 0 and insert the new element there.

10)What kind of pointers should be used in heterogeneous linked list?

The heterogeneous linked list contains different data types, so it is not possible to use ordinary pointers for this. For this purpose, you have to use a generic pointer type like void pointer because the void pointer is capable of storing a pointer to any type.

11)What is the advantage of linked list over array?

(1) The size of the arrays is fixed

(2) Inserting a new element in an array of elements is expensive

because to insert all element has to be shifted

12)Write a c code for creation of node in singly linked list.

struct node   

{  

    int data;   

    struct node *next;  

};  

struct node *head, *ptr;   

ptr = (struct node *)malloc(sizeof(struct node)); 

3)Write the post fix expression of (a+b)*(c-d)

ab+cd-*

4)How is the array different from the linked list?

The size of the arrays is fixed, Linked Lists are Dynamic in size.

Inserting and deleting a new element in an array of elements is

expensive, Whereas both insertion and deletion can easily be done

in Linked Lists.

Random access is not allowed in Linked Listed.

Extra memory space for a pointer is required with each element of

the Linked list.Arrays have better cache locality that can make a

pretty big difference in performance.

5)What are the draw backs of Linked list?

1) Random access is not allowed. We have to access elements

sequentially starting from the first node.

2) Extra memory space for a pointer is required with each

binary search with linked lists.

element of the list. Representation in C: A linked list is 

The first node is called head. If the linked list is empty,

represented by a pointer to the first node of the linked list. 

then value of head is NULL.

3)Unlike array this doesn't have good cache localities

6)Which data structure is used in BFS and DFS of graph?

Queue is used for BFS and stack is used for DFS graph.

7)How to implement Stack using queue?

click here

8)How to implement Queue using stack?

click here

9)What is priority  queue?

A priority queue is a collection in which items can be added at any time, but the only item that can be removed is the one with the highest priority.

Define tree.
The Tree is a recursive data structure containing the set of one or more data nodes where one node is designated as the root of the tree while the remaining nodes are called as the children of the root.

10)What is the minimum number of queues that can be used to implement a priority queue?

Two queues are needed. One queue is used to store the data elements, and another is used for storing priorities.

11)Mention different types of tree.

1.General Tree
2.Forests
3.Binary Tree
4.Binary Search Tree
5.Expression Tree
6.Tournament Tree

12)Write a code to perform in-order traversal of binary tree.

void in-order(struct treenode *tree)  
    {  
        if(tree != NULL)  
        {  
            in-order(tree→ left);  
            printf("%d",tree→ root);  
            in-order(tree→ right);  
        }  
    }

13)What is the maximum number of nodes in a binary tree of height k?

2^k+1-1 where k >= 1

14)How to check if a given Binary Tree is BST or not?

If inorder traversal of a binary tree is sorted, then the binary tree is

BST. The idea is to simply do inorder traversal and while traversing

keep track of previous key value. If the current key value is greater,

then continue, else return false.

15)How can AVL Tree be useful in all the operations as compared to Binary search tree?

AVL tree controls the height of the binary search tree by not letting it be skewed. The time taken for all operations in a binary search tree of height h is O(h). However, it can be extended to O(n) if the BST becomes skewed (i.e. worst case). By limiting this height to log n, AVL tree imposes an upper bound on each operation to be O(log n) where n is the number of nodes.

16)Which technique is used in binary search tree?

divide and conquer

17)Which are the types of tree traversal?
In order
Pre order
Post order
click here to know about binary tree traversal

18)Which data structure can be used for efficiently building a word dictionary and Spell Checker?

Depends on the functionality required in spelling checker and availability of the memory.Hashing is one of the simplest method and few others are trie, ternary search tree.

19)What do you mean by dynamic data structure?
These kind of data structure has the flexible size which can grow and shrink according to situation

20)Write the difference between dynamic and static data structure.

Dynamic data sructure	Static Data Structure
Ability to efficiently add, remove or modify elements	Add, remove or modify elements is not directly possible. If done, it is a resource consuming process.
Flexible size	Fixed size
Effective use of resources – because resources are allocated at the runtime, as required.	Resources allocated at creation of data structure, even if elements are not contain any value.