Home | | **Object Oriented Programming and Data Structures** | Important short questions and answers: Sorting and Searching

Object Oriented Programming and Data Structure - Sorting And Searching - Important short questions and answers: Sorting and Searching

**1. What is maxheap? **

If we
want the elements in the more typical increasing sorted order, we can change
the ordering property so that the parent has a larger key than the child. it is
called max heap.

**2. What is divide and conquer strategy?**

In divide
and conquer strategy the given problem is divided into smaller problems and
solved recursively. The conquering phase consists of patching together the
answers. Divide and conquer is a very powerful use of recursion that we will
see many times.

3. **Differentiate between merge sort and quick
sort? **

Mergesort

1.Divide
and conquer strategy 2.Partition by position Quicksort

1. Divide
and conquer strategy

2. Partition
by value

**4. ****Mention some methods for choosing the pivot element
in quicksort?**

1. Choosing
first element

2. Generate
random number

3. Median of
three

**5. ****What are the three cases that arise during the left
to right scan in quicksort?**

I and j
cross each other

I and j do
not cross each other

I and j
points the same position

**6. 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. It is a basic external
sorting in which there are two inputs and two outputs tapes.

**7. Define multi way merge? **

If we
have extra tapes then we can expect to reduce the number of passes required to
sort

**8. 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

**9. 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.

**10. 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.

**11. What is mergesort?**

The
mergesort algorithm is a classic divide and conquer strategy. The problem is
divided into two arrays and merged into single array

**12**.** What are the properties involved in heapsort? **

1.Structure
property 2.Heap order property

**13. Define articulation points.**

If a
graph is not biconnected, the vertices whose removal would disconnect the graph
are known as articulation points. An expression tree is a binary tree in which
the operands are attached as leaf nodes and operators become the internal nodes.

**14. What is an acyclic graph?**

A simple diagram which does not have any cycles is called an
acyclic graph.

**15. Give some example of NP complete
problems.**

·
Hamiltonian circuit.

·
Travelling salesmen problems

**16.
****What are AVL trees?**

An AVL tree is a binary search tree with a balancing
condition.For every node in the tree the heigh of the left and right subtrees
can differ at most by 1.The height of an empty tree is defined to be -1.It
ensures that the depth of the tree is O(log N)

**17. What is topological sort?**

A topological sort is an ordering of vertices in a directed
acyclic graph, such that if there is a path from vi then vj appears after vi in
the ordering.

**18.What is single source shortest
path problem?**

Given as an input a weighted graph, G=(V,E) and a distinguished
vertex,’s’ find the shortest weighted path from ‘s’ to every other vertex in G.

**19.Mention some shortest –path
problems.**

·
Unweighted shortest paths

·
Dijikstra’s algorithm

·
All-pairs shortest paths

**20.
****Define
threaded Binary Tree. **

A binary
tree is threaded by making all right child pointers that would normally be null
point to the inorder successor of the node, and all left child pointers that
would normally be null point to the inorder predecessor of the node.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Object Oriented Programming and Data Structure : Sorting And Searching : Important short questions and answers: Sorting and Searching |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.