代写binary tree、代做Python编程语言、代写Java，c/c++代写

日期：2019-12-25 08:40

1. What is the state of the stack after the following sequence of pushes and pops:

Stack<int> s;

s.push( 3 );

s.push( 5 );

s.push( 2 );

s.push( 15 );

s.push( 42 );

s.pop();

s.pop();

s.push( 14 );

s.push( 7 );

s.pop();

s.push( 9 );

s.pop();

s.pop();

s.push( 51 );

s.pop();

s.pop();

2. Suppose the numbers 0, 1, 2, …, 9 were pushed onto a stack in that order, but that pops

occurred at random points between the various pushes. The following is a valid sequence in

which the values in the stack could have been popped:

3, 2, 6, 5, 7, 4, 1, 0, 9, 8

Explain why it is not possible that

3, 2, 6, 4, 7, 5, 1, 0, 9, 8

is a valid sequence in which the values could have been popped off the stack.

3. What is the state of the queue after the following sequence of pushes and pops:

Queue<int> q;

q.push( 3 );

q.push( 5 );

q.push( 2 );

q.push( 15 );

q.push( 42 );

q.pop();

q.pop();

q.push( 14 );

q.push( 7 );

q.pop();

q.push( 9 );

q.pop();

q.pop();

q.push( 51 );

q.pop();

q.pop();

4. Perform depth-first, pre-order depth-first and post-order depth-first traversals on the tree

shown in Figure 1.

5. What is the maximum size of the queue if a queue is used for performing a breadth-first

traversal on the tree in Figure 1?

6. You are given that a tree has pre- and post-order depth first traversals of

A B D E G C F

D G E B F C A

respectively. Can you determine the original tree from this information?

7. You are given that a tree has pre-order depth-first and breadth-first traversals of

A B C D E G F

A B C D E F G

respectively. Can you determine the original tree from this information?

8. Show that the maximum number of nodes in a binary tree of height ? is 2

?+1 ? 1.

9. A full node is a node with two children. Prove that the number of full nodes plus one is

equal to the number of leaves in a nonempty binary tree.

10. Suppose a binary tree has leaves ??1, ??2, . . . , ???? at depths ??1, ??2, . . . , ????,

respectively. Prove that ∑ 2

????? ≤ 1

??

??=1

and determine when the equality is true.

11. The following is an array representation of a complete binary tree. What is the actual tree?

0 1 2 3 4 5 6 7 8 9 10 12 13

84 57 81 42 54 73 60 31 25 14

Without referring to the binary tree, what are the parent and children of the entry containing

42 and 54?

12. Give the prefix, infix, and postfix expressions corresponding to the tree in Figure 2.

Figure 2.

13. a. Show the result of inserting 3, 1, 4, 6, 9, 2, 5, 7 into an initially empty binary search

tree.

b. Show the result of deleting the root.

14. Show the result of inserting 2, 1, 4, 5, 9, 3, 6, 7 into an initially empty AVL tree. What is

the result after erasing 5 from the tree?

15. Perform an in-order traversal of the binary tree shown in Figure 3.

Figure 3

16. What are the number of inversions in the following unsorted list?

6, 7, 3, 1, 2, 4, 5, 8

17. Sort the above sequence using insertion sort.

18. Suppose we exchange elements ??[??] and ??[?? + ??], which were originally out of order.

Prove that at least 1 and at most 2?? ? 1 inversions are removed.

19. Sort 3, 7, 4, 1, 5, 9, 2, 6 using merge sort.

20. Sort 3, 7, 4, 1, 5, 9, 2, 6 using quick sort with median-of-three partitioning.

21. Given the following hash table, remove the following values from the hash table of size

10 using linear probing using the least-significant digit as the hash value:

821, 636, 594, 399

0 1 2 3 4 5 6 7 8 9

219 821 981 388 594 192 636 144 170 399

22. Given input {4371, 1323, 6173, 4199, 4344, 9679, 1989} and a hash function ?(??) =

??(?????? 10), show the resulting

a. separate chaining hash table

b. hash table using linear probing

c. hash table using quadratic probing (?? × ?? + ??)

d. hash table with second hash function ?2

(??) = 7 ? ??(?????? 7)

23. Find the shortest path from A to all other vertices for the graph in Figure 4.

Figure 4

24. Find a minimum spanning tree for the graph in Figure 5 using both Prim’s and Kruskal’s

algorithms.

Figure 5

25. If a graph is bipartite, then all its circuits are of even length.

26. Find a topological ordering for the graph in Figure 6.

Figure 6