Q.1 What is a Data Structure?
Q.2 What are the various operations that can be performed on different Data Structures?
Answer:
Q.4 What is Stack and where it can be used?
Q.6 What is a Linked List?
Q.7 What is a Linked List types?
Answer:
Answer: A data structure is a way of organizing the data so that the data can be used efficiently. Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. For example, B-trees are particularly well-suited for implementation of databases, while compiler implementations usually use hash tables to look up identifiers. (Source: Wiki Page)
Q.2 What are the various operations that can be performed on different Data Structures?
Answer:
- Insertion? Add a new data item in the given collection of data items.
- Deletion? Delete an existing data item from the given collection of data items.
- Traversal? Access each data item exactly once so that it can be processed.
- Searching? Find out the location of the data item if it exists in the given collection of data items.
- Sorting? Arranging the data items in some order i.e. in ascending or descending order in case of numerical data and in dictionary order in case of alphanumeric data.
Q.3 What are linear and non linear data Structures?
Answer:
- Linear: A data structure is said to be linear if its elements form a sequence or a linear list. Examples: Array. Linked List, Stacks and Queues
- Non-Linear: A data structure is said to be non-linear if traversal of nodes is nonlinear in nature. Example: Graph and Trees.
Q.4 What is Stack and where it can be used?
Answer: Stack is a linear data structure which the order LIFO(Last In First Out) or FILO(First In Last Out) for accessing elements. Basic operations of stack are : Push, Pop , Peek
Q.5 What are Infix, prefix, Postfix notations?
Answer:
Answer:
- Infix notation: X + Y – Operators are written in-between their operands. This is the usual way we write expressions. An expression such as
A * ( B + C ) / D
- Postfix notation (also known as “Reverse Polish notation”): X Y + Operators are written after their operands. The infix expression given above is equivalent to
A B C + * D/
- Prefix notation (also known as “Polish notation”): + X Y Operators are written before their operands. The expressions given above are equivalent to
/ * A + B C D
Q.6 What is a Linked List?
Answer: A linked list is a linear data structure (like arrays) where each element is a separate object. Each element (that is node) of a list is comprising of two items – the data and a reference to the next node.Types of Linked List.
Answer:
- Singly Linked List: In this type of linked list, every node stores address or reference of next node in list and the last node has next address or reference as NULL. For example 1->2->3->4->NULL
- Doubly Linked List: Here, here are two references associated with each node, One of the reference points to the next node and one to the previous node. Eg. NULL<-1<->2<->3->NULL
- Circular Linked List: Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list. Eg. 1->2->3->1 [The next pointer of last node is pointing to the first]
Q.8 How to check if a given Binary Tree is BST or not?
Answer: 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 current key value is greater, then continue, else return false. See A program to check if a binary tree is BST or not for more details.
Q.9 Which Data Structure Should be used for implementiong LRU cache?
Answer:
- Queue which is implemented using a doubly linked list. The maximum size of the queue will be equal to the total number of frames available (cache size).The most recently used pages will be near rear end and least recently pages will be near front end.
- A Hash with page number as key and address of the corresponding queue node as value. See How to implement LRU caching scheme? What data structures should be used?
