Love Stuff

ITCS 2214 Exam 2 Study Guide

1. What is a tree data structure?

A Tree is a non-linear structure that is organized into a hierarchy of nodes and edges.

2. What is the root? Is the root at the top or bottom of a tree?

The root is the first most node and is located at the top of the tree.

3. What is a node?

A node is a location on the tree which contains data. They are connected together by edges.

4. What is a leaf? What makes a node a leaf?

A leaf is a node which is near the bottom of the tree with no other nodes (children) below it.

5. What is the level of the root?

A level of the root is the length of the path from the root to the node

6. How do you determine the level of a node?

7. What is a path? What is the height of a tree?

A series of steps along edges from node to node. The height is defined as length of longest path from root to a leaf. (There may be multiple “longest paths”)

8. What is the order of a tree?

9. What is a balanced tree?

10. What is a complete tree?

11. What is a full tree?

12. What specific traits does a binary search tree have?

13. What is a heap?

14. What is the difference between a heap and an ordinary binary tree?

15. What is the difference between a minheap and a maxheap?

16. Describe the process to add an element to a minheap. At what location may an element be added to a minheap? A maxheap?

17. Describe the process of removing an element from a minheap. At what location may an element be removed from a minheap? A maxheap?

18. Describe the use of a heap as a priority queue.

19. Describe the use of a minheap for sorting. Would a minheap be useful for ascending or descending sorting?

20. Relate a hash table to a linear search. To a binary search.

21. What is the relation of a hash table and a hashing function?

22. What is a collision in a hash table?

23. What is a perfect hashing function?

24. Describe and contrast the...