首页 >
> 详细

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

Stack

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

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

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Tsp课程作业代写、代做algorithms留学生作业、代做java，C/C 2020-06-23
- Kit107留学生作业代做、C++编程语言作业调试、Data课程作业代写、代 2020-06-23
- Sta302h1f作业代做、代写r课程设计作业、代写r编程语言作业、代做da 2020-06-22
- 代写seng 474作业、代做data Mining作业、Python，Ja 2020-06-22
- Cmpsci 187 Binary Search Trees 2020-06-21
- Comp226 Assignment 2: Strategy 2020-06-21
- Math 504 Homework 12 2020-06-21
- Math4007 Assessed Coursework 2 2020-06-21
- Optimization In Machine Learning Assig... 2020-06-21
- Homework 1 – Math 104B 2020-06-20
- Comp1000 Unix And C Programming 2020-06-20
- General Specifications Use Python In T... 2020-06-20
- Comp-206 Mini Assignment 6 2020-06-20
- Aps 105 Lab 9: Search And Link 2020-06-20
- Aps 105 Lab 9: Search And Link 2020-06-20
- Mech 203 – End-Of-Semester Project 2020-06-20
- Ms980 Business Analytics 2020-06-20
- Cs952 Database And Web Systems Develop... 2020-06-20
- Homework 4 Using Data From The China H... 2020-06-20
- Assignment 1 Build A Shopping Cart 2020-06-20