Central Connecticut State University | CS 253 : test2
1. Describe the Binary Tree ADT (give a definition, set of operations,example), and its implementations. Explain and compare linear and linked implementations of binary trees.
2. Describe binary tree traversals (inorder, postorder, preorder and level-order). Give examples of applications of these traversals– describe the application, not just say it.
3. What kind of a binary tree is the heap? Explain different operations of heaps. Compare heaps to binary search trees in term of efficiencies of main operations
4. Explain heap sort (use an example). Compare the efficiency of heap sort to the efficiencies of elementary sorting methods and radix sort.
5. Describe the General Tree ADT (give a definition, set of operations, example). Discuss different ways for implementing general trees, and compare them in terms of the efficiency of search operations.
6. Discuss general tree traversals for both binary tree implementation and ternary tree implementation of a general tree. Give an example to illustrate your answer.
7. Describe the Priority Queue ADT (give a definition, set of operations, example). Discuss different implementations of a priority queue. Show how sorting can be done with a priority queue.
8. Describe the Dictionary ADT (give a definition, set of operations, example). Compare ordered vs unordered dictionaries in terms of the efficiency of main operations, and discuss different implementations of unordered dictionaries (hash tables being one of them).
9. What type of a tree is an AVL tree? Compare it to the binary search tree. Explain how search, insertion and deletion are performed on AVL trees. Discuss possible applications of AVL trees (ordered dictionaries being one of them).
10. Describe 2-3 trees (give a definition and an example). Explain how search, insertion and deletion are performed on 2-3 trees (use an example). How an efficiency of 2-3 trees compares to that of AVL trees? (again, an example will be useful to illustrate your answer).
Practical:
1) trace a data structure
2)define and/or compare efficiencies of program segments.
