1. Develop an ADT specification for a priority queue. A priority queue is like a FIFO queue except that items are ordered by some priority setting instead of time. In fact, you may think of a FIFO queue as a priority queue in which the time stamp is used to define priority.
2. Write an algorithm to reverse a singly linked list, so that the last element become the first and so on. Do NOT use Deletion – rearrange the pointers.
3. What is the average number of nodes accessed in search for a particular element in an unordered list? In an ordered list? In an unordered array? In an ordered array? Note that a list could be implemented as a linked structure or with an array.
4. Write a routine to interchange the mth and nth elements of a singly-linked list. You must rearrange the pointers, not simply swap the contents.
5. Given the following interface for a list, comment on it from the perspective of an ADT.
public interface ArrayList {
public ArrayList(void) { List = 0 }; //constructor – initializes list to be empty
public Insert(itemtype item, int index); //verifies index & inserts itemat position index in list
public int Search (itemtype item); //searches list & returns position of item. Returns -1 if not found
public int CountItem ( itemtype Item);
private boolean VerifyIndex (int index); //validates that index is position within list
}
Leave a reply