1. What is sorting? What are different logics for sorting?
Sorting is a technique used to arrange the elements of an array in either ascending order or descending order. To implement “sorting”, there are several logics such as “bubble sort”, “selection sort”, “insertion sort”, “quick sort”, “merge sort” and etc.
2. What is Time Complexity?
The amount of time required by a program for its compilation and execution is time complexity.
3. What is Space Complexity?
The amount of memory (space) required by a program for its compilation and execution is Space complexity.
4. Compare time complexity and space complexity for different sorts.
| Sort-type | Worst Case | Best Case | Average Case | Worst case Space Complexity |
| Bubble sort | O(n2) | O(n) | O(n2) | O(1) auxiliary |
| Insertion Sort | O(n2) | O(n) | O(n2) | O(n) total, O(1) auxiliary |
| Selection Sort | O(n2) | O(n2) | O(n2) | O(n) total, O(1) auxiliary |
| Quick Sort | O(n2) | O(nlogn) | O(nlogn) | O(n) |
5. What are Data Structures?
Data structure is a mechanism to organize the data in different ways and to perform possible operations on these structures. It also measures the efficiency of the algorithm in terms of their time-complexity and space complexity of the program.
6. What are the types of Data Structures?
§Linear data structures: Arrays, Linked lists, Stacks, Queues
§Non-Linear data structures: Trees, Graphs, red-black trees
7. What is a linked list?
Linked list is a type of data structure that holds set of nodes linked to each other. Every node consists of information parts and reference parts.
8. What are the advantages and disadvantages of Linked lists?
Advantages:
• In, Linked lists there will not be any memory wastage or shortage.
• To insert an element in the linked list, we need not traverse throughout the list.
• To delete an element in the linked list, we need not traverse throughout the list.
• Predetermining of number of data elements is not necessary.
Disadvantages:
• No direct access to a particular element in the list.
9. What are the types of linked lists?
Linked lists are mainly of 4 types:
1. Single linear linked list
2. Single circular linked list
3. Double linear linked list
4. Double circular linked list
10. What are the applications of linked lists?
· Polynomial addition and multiplication
· Radix sort
· To perform arithmetic operations on large numbers
· Implementation of stacks and queues
· Memory management
11. Compare arrays and linked lists.
| Arrays: | Linked lists: |
| It is a set of values of same type | It is a set of nodes linked together, where node has information and reference parts. |
| Predetermination of the size is a must. | No predetermination of number of nodes, because it uses dynamic memory allocation. |
| Array elements are sequentially stored | Nodes of the list are not stored sequentially. |
| Direct access to any element of the array is possible. | Direct access to any element of the list is not possible. |
| To insert and delete elements we need to traverse throughout the array. | To insert and delete elements we need not traverse throughout the list. |
| Index plays key role. | References play key role. |
| There is a chance for Memory wastage or shortage. | There is no Memory wastage. |
0 comments:
Post a Comment