Asian
Define ADT with example.
A useful tools for specifying the logical properties of a data type is called abstract data type. An ADT have both set of values of a given type and the set of operations that can be performed on those values.
Example: Array, List, Queue, etc.
Define max-heap with suitable example.
A max-heap is a complete binary tree in which the value in each internal node is greater than or equal to the values in the children of that node.
Differentiate between linear and circular queue.
| LINEAR QUEUE | CIRCULAR QUEUE |
| Organizes the data elements and instructions in a sequential order one after the other. | Arranges the data in the circular pattern where the last element is connected to the first element. |
| The new element is added from the rear end and removed from the front. | Insertion and deletion can be done at any position. |
How doubly linked list differs from singly linked list ?
In a single linked list, node only points towards next node, and there is no pointer to previous node, which means you can not traverse back on a singly linked list. On the other hand doubly linked list maintains two pointers, towards next and previous node, which allows you to navigate in both direction in any linked list.
What is skip list ?
A skip list is a data structure that is used for storing a sorted list of items with a help of hierarchy of linked lists that connect increasingly sparse subsequences of the items.
Define decision tree with suitable example.
Binary tree can be used to locate item based on comparision, in this situatuation each comparision tells us to visit either left-subtree and right-subtree. A rooted tree where internal vertices corresponding a decision and sub-tree at these vertices of possible outcomes of the decision made is called decision tree.
Define binary search tree .
A binary search tree (BST), also known as an ordered binary tree, is a node-based data structure in which each node has no more than two child nodes. Each child must either be a leaf node or the root of another binary search tree. The left sub-tree contains only nodes with keys less than the parent node; the right sub-tree contains only nodes with keys greater than the parent node.
What is complete binary tree ?
A complete binary tree with n nodes and of depth d is a strectly binary tree, an of whose terminal nodes are at level d.
What is splaying ?
A splaying is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again.
Define tail recursion with example.
The tail recursive functions considered better as the recursive call is at the last statement so there is nothing left to do in the current function. It saves the current function’s stack frame is of no use.
Example: Recursive Function TOH with Tail Recursion
v
|
1 2 3 4 5 6 7 8 9 |
oid TOH(int n,char x,char y,char z) { if(n>0) { TOH(n-1,x,z,y); printf("\n%c-> %c",x,y); TOH(n-1,z,y,x); //tail recursion } } |
IMS
1.Define data structure?
A data structure is a specialized format for organizing, processing, retrieving and storing data. While there are several basic and advanced structure types, any data structure is designed to arrange data to suit a specific purpose so that it can be accessed and worked with in appropriate ways.
2.What is linked list?
A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. In simple words, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.
3.What is sorting?
Sorting refers to the operation or technique of arranging and rearranging sets of data in some specific order. A collection of records called a list where every record has one or more fields.
4.Define cyclic graph.
A cyclic graph is a graph containing at least one graph cycle. Cyclic graphs are not trees.
5.What is hashing?
Hashing is generating a value or values from a string of text using a mathematical function.Hashing is one way to enable security during the process of message transmission when the message is intended for a particular recipient only.
6.Define double linked list.
A Doubly Linked List (DLL) contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.
7.What is queue?
A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO). A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first.
8.Define binary tree.
A binary tree is a tree data structure where each node has up to two child nodes, creating the branches of the tree. The two children are usually called the left and right nodes. Parent nodes are nodes with children, while child nodes may include references to their parents.
9.What is divide and conquer algorithm?
Divide and conquer is an algorithmdesign paradigm based on multi-branched recursion. A divide-and-conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.
10.Define stack.
A stack is a conceptual structure consisting of a set of homogeneous elements and is based on the principle of last in first out (LIFO). It is a commonly used abstract data type with two major operations, namely push and pop.
NCC
- What is asymptotic complexity?
Ans: The limiting behavior of the execution time of an algorithm when the size of the problem goes to infinity is called asymptotic complexity.
- Differentiate between static and dynamic data structure.
Ans: Static structure – It has fixed memory allocation at creation. Eg: Array
Dynamic Structure – Its memory allocation is not fixed at creation. Eg: Linked List.
- List the two approach to delete a node having two children in Binary Search Tree?
Ans: The two approach to delete a node ha having two children in Binary Search Tree are:-
- Deletion by Merging and
- Deletion by copying
- Why doubly linked list is advantageous than singly linked list?
Ans: Because of two way communication in doubly linked list
- From which end insertion of an element is done in a queue?
Ans: From front end insertion of an element is done in a queue.
- Define self-organizing list?
Ans: A self-organizing list is a list that reorders its elements based on self-organizing heuristic to improve average access time.
- What happens when there is excessive recursion?
Ans: When there is excessive recursion the same function is repeatedly called again and again and at worst case scenario the system crashes.
- Define a complete binary tree.
Ans: A complete binary tree is a strict binary tree of same level.
- Differnetiate between searching and traversing.
| Searching | Traversing |
| Searching means to search a particular node | Traversing means to travel to each node exactly once only |
- Why is array implementation of binary tree not good?
Ans: Array implementation of binary tree not good because it consumes lot of time
Orchid International College
- Define Balance Factor.
Ans. The difference between the height of left subtree and the height of right subtree is called Balance Factor.
- What is a min heap ?
Ans. A min heap is a binary tree structure in which the parent node has the value smaller than its children and descendants and the root has the smallest value.
3.Define Big-Omega notation.
Ans. If there exists two functions f(n) and g(n) and two constants c and N such that f(n) >= c*g(n) for all N>n0, then f(n) is said to be big-omega of g(n).
4.What is a strictly binary tree?
Ans. A binary tree with each node having exactly two children or zero child is called a strictly binary tree.
- Differentiate between tail and non-tail recursion.
| Tail Recursion | Non Tail Recursion |
| i. In tail recursion, the recursive call is made only in the last statement. | i. In non-tail recursion, the recursive call can be anywhere inside the function. |
- How is priority queue different from a simple queue ?
| Simple Queue | Priority Queue |
| i. The element at the front of the queue is deleted first. | i. The element having highest priority is deleted first. |
| ii. There is no need of shifting of elements. | ii. If any element is removed from the middle of the queue, the elements after that need to be shifted to front. |
- Define Queue.
Ans. A Queue is a data structure in which elements are inserted from the back end known as rear end and the elements are deleted from the front end.
- When does stack overflow condition occur ?
Ans. Stack overflow condition occurs when the stack is already full and an additional element is tried to be pushed on the stack. In other words, when TOP = stacksize -1, stack overflow occurs.
- Define expression tree.
Ans. An expression tree is a binary tree structure in which operands are placed in the leaf node and the operators are placed in the parent node and the operator with the lowest precedence is placed as root.
- What is the prefix notation of (A+B)*(C-D)/E.
Ans. The prefix notation is: *+AB/-CDE.