Lets see if you have solutions to the standard problems. Lets define the suitable data structures.

Guess the data structues between the 2 data structures provided (in italics).

Guess the data structues between the 2 data structures provided (in italics).

**Operations are Insert, DeleteMax, and DeleteMin.**

*balanced tree*or*sorted doubly-linked list*

The balanced tree is better since all operations take O(log n) time. The sorted doubly-linked list is O(1) for DeleteMax and DeleteMin, but Insert is O(n); thus, the average time per operation is O(n).**Operations are Insert and FindMedian**.

(The median is the item m such that half the items are less than m and half are greater than m.)

*red-black trees*or*sorted array*

You can use two red-black trees plus an additional variable to hold the median, one red-black tree for items less than the median and one for items greater than the median. When you insert, you can keep track of the median by moving items from one tree to the other. With this scheme, Insert takes O(log n) time and FindMedian take O(1) time. The sorted array takes O(n) time for Insert.**You have a dictionary containing the keywords of the Pascal programming language**.

*ordered array*or*red-black tree*

In this situation the ordered array is best. Both data structures take time O(log n) to find an item. An ordered array takes longer to insert or delete, but we don't expect to be creating or destroying keywords, so there shouldn't be any insertion or deletion. The ordered array is simpler to program and takes less space.**You have a dictionary that can contain anywhere from 100 to 10,000 words.**

*unordered linked-list*or*red-black tree*

The red/black tree is better, since the operations require O(n) time for the linked-list and O(log n) time for the red/black tree. For 10,000 words this could certainly be significant.**You have a large set of integers with operations insert, findMax, and deleteMax.**

*unordered array*or*Hashtable*

Neither data structure is good for this problem. An unordered array is slightly better since it has less overhead and it's easier to program.

## 0 comments:

## Post a Comment