1.) Draw an arithmetic expression tree that has four external nodes, storing the
ID: 3759080 • Letter: 1
Question
1.) Draw an arithmetic expression tree that has four external nodes, storing the numbers 1, 5, 6, and 7 (with each number stored in a distinct external node, but not necessarily in this order), and has three internal nodes, each storing an operator from the set { +,?,?, / }, so that the value of the root is 21. The operators may return and act on fractions, and an operator may be used more than once.
2.) Show how to implement the stack ADT using only a priority queue and one additional integer instance variable. (pseudo-code)
3.) Given a heap H and a key k, give an algorithm to compute all the entries in H having a key less than or equal to k. For example, given the heap of Figure 9.12a and query k =7, the algorithm should report the entries with keys 2, 4, 5, 6, and 7 (but not necessarily in this order). Your algorithm should run in time proportional to the number of entries returned, and should not modify the heap. (pseudo-code) The algorithm should print the elements smaller or equal than k.
4.) Draw the 11-entry hash table that results from using the hash function, h(i) =(3i+5) mod 11, to hash the keys 12, 44, 13, 88, 23, 94, 11, 39, 20, 16, and 5, assuming collisions are handled by chaining.
5.) What is the result of the previous exercise, assuming collisions are handled by linear probing?
cB GA) (4.0 (15,K) 15.K (GA) 1650) t (2.U3 (O (uz) (015) ( (,w (20B) ((10L) alExplanation / Answer
2)
Maintain a minKey variable initialized to 0.
On a push operation for element e, call insertItem (minKey; e) and decrement minKey.
On a pop operation, call removeMinElement and increment minKey.
4)
chaining
0
1
2
3
4
5
6
7
8
9
10
Keys
20
16
44
94
12
13
5
88
39
23
11
5)
linear probing
0
1
2
3
4
5
6
7
8
9
10
Keys
11
39
20
5
16
44
88
12
23
13
94
0
1
2
3
4
5
6
7
8
9
10
Keys
20
16
44
94
12
13
5
88
39
23
11
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.