7. Indicate how the ADT priority queue can be implemented as
a. an (unsorted) array.
through the array to find its largest element. Deleting the largest element
A[i] can be implemented by exchanging it with the last element and
decreasing the array’s size by 1.
b. We will assume that the array A[0..n ? 1] representing the priority
queue is sorted in ascending order. Inserting a new item of value v can be
done by scanning the sorted array, say, left to right until an element A[j]
≥ v or the end of the array is reached. (A faster algorithm for finding
a place for inserting a new element is binary search discussed in Section
4.3.) In the former case, the new item is inserted before A[j] by first moving
A[n ? 1], ...,A[j] one position to the right; in the latter case, the new
item is simply appended after the last element of the array. Finding the
largest element is done by simply returning the value of the last element
of the sorted array. Deletion of the largest element is done by decreasing
the array’s size by one.
c. Insertion of a new element is done by using the standard algorithm
for inserting a new element in a binary search tree: recursively, the new
key is inserted in the left or right subtree depending on whether it is
smaller or larger than the root’s key. Finding the largest element will
require finding the rightmost element in the binary tree by starting at
the root and following the chain of the right children until a vertex with
no right subtree is reached. The key of that vertex will be the largest
element in question. Deleting it can be done by making the right pointer
of its parent to point to the left child of the vertex being deleted;. if the
rightmost vertex has no left child, this pointer is made “null”. Finally, if
the rightmost vertex has no parent, i.e., if it happens to be the root of the
tree, its left child becomes the new root; if there is no left child, the tree
becomes empty.
8. How would you implement a dictionary of a reasonably small size n if
you knew that all its elements are distinct (e.g., names of 50 states of the
United States)? Specify an implementation of each dictionary operation.
Hit:
Because of insertions and deletions, using an array of the dictionary’s
elements (sorted or unsorted) is not the best implementation possible.
Solution:
Use a bit vector, i.e., an array on n bits in which the ith bit is 1 if
the ith element of the underlying set is currently in the dictionary and
0 otherwise. The search, insertion, and deletion operations will require
checking or changing a single bit of this array.
9. For each of the following applications, indicate the most appropriate data
structure:
a. answering telephone calls in the order of their known priorities.
b. sending backlog orders to customers in the order they have been received.
c. implementing a calculator for computing simple arithmetical expressions.
Hit:
You need to know about the postfix notation in order to answer one of
these questions. (If you are not familiar with it, find the information on
the Internet.)
Solution:
Use: (a) a priority queue; (b) a queue; (c) a stack (and reverse Polish
notation–a clever way of representing arithmetical expressions without
parentheses, which is usually studied in a data structures course).
c.用stack的方式，以一对大括号为匹配对查询，计算其中的math expression,
遇到新的大括号就递归此方法返回value参与上步的计算
10. Anagram checking Design an algorithm for checking whether two given
words are anagrams, i.e., whether one word can be obtained by permuting
the letters of the other. (For example, the words tea and eat are
anagrams.)
1.The most straightforward solution is to search for each successive letter
of the first word in the second one. If the search is successful, delete the
first occurrence of the letter in the second word, stop otherwise.
双重循环，每个字母查找是否存在，找到后，删除target的字母，
直到停止
2.Another solution is to sort the letters of each word and then compare
them in a simple parallel scan.
先排序，然后eaquel
3.We can also generate and compare “letter vectors” of the given words:
Vw[i] = the number of occurrences of the alphabet’s ith letter in the word
w. Such a vector can be generated by initializing all its components to
0 and then scanning the word and incrementing appropriate letter counts
in the vector.
