DATA STRUCTURES
71. What is the need of external sorting?
External sorting is required where the input is too large to fit into memory. So external sorting Is necessary where the program is too large
72. Define two way merge ?
It is a basic external sorting in which there are two inputs and two outputs tapes .
73. Define multi way merge ?
If we have extra tapes then we can expect to reduce the number of passes required to sort our input. We do this by extending two way merge to a k-way merge.
74. Define polyphase merge ?
The k-way merging strategy requires the use of 2 k tapes. This could be prohibitive for some applications . It is possible to get by with only k+1 tapes.
75. What is replacement selection ?
We read as many records as possible and sort them . writing the result to some tapes. This seems like the best approach possible until one realizes that as soon as the first record is written to a output tape the memory it used becomes available for another record . if the next record on the input tape is larger than the record we have just output then it can be included in the item . using this we can give algorithm. This is called replacement selection.
76. What is sorting ?
Sorting is the process of arranging the given items in a logical order.
Sorting is an example where the analysis can be precisely performed.
77. What is mergesort?
The mergesort algorithm is a classic divide&conquer strategy. The problem is divided into two arrays and merged into single array
78. What are the properties involved in heapsort?
1. structure property
2. heap order property
79. Define articulation points.
If a graph is not biconnected,the vertices whose removal would disconnect the graph are known as articulation points.
80. Give some example of NP complete problems.
i. Hamiltonian circuit.
ii. Travelling salesmen problems
iii. Longest path problems
iv. Bin packing
v. Knapsack problem
vi. Graph colouring problem
No comments:
Post a Comment