CSCI 106 Data Structures: Final
Exam (Open-book test)
Email me a snapshot of what you are able to finish by
#1~#11
Please answer the 11 questions
in the following two files: list.h and list.cpp.
#12. Look at the code about the linked list implementation:
|
struct ListNode { int Value; ListNode * Next; }; typedef ListNode *
ListNodePointer; class List { public: // ...Code removed ... void Display(); private: ListNodePointer Head; }; // ...Code removed
... void List::Display() { ListNodePointer Temp=Head; while(Temp) { cout<<Temp->Value<<endl; Temp=Temp->Next; } } // ... Code removed
... |
Show how you can add and implement a new member function int Count( ) that will count and the return the number of node currently in the list. (Hint: You can easily modify the code of the Display member function to accomplish this.).
# 13. Look at the code about the binary search tree implementation in chapter 15:
|
struct TreeNode { int Value; TreeNode * Left; TreeNode * Right; }; typedef TreeNode *
TreeNodePointer; class Tree { public: void Display(); // ...Code removed ... private: TreeNodePointer Root; void DisplayTree(TreeNodePointer Root); // ...Code removed ... }; void Tree::Display() { DisplayTree(Root); cout << endl; } void Tree ::
DisplayTree(TreeNodePointer Root) { if (Root != NULL) { DisplayTree(Root->Left); cout<<Root->Value<<' '; DisplayTree(Root->Right); } } |
(i)
Show how you can add and implement a new member function
int
Tree:CountTree(TreeNodePointer RootOFTree) that will recursively
calculate the number of nodes in any subtree rooted at the node pointed to by RootOFTree . (ii) Show how you can then add and
implement a new member function
int
Tree:Count( ) that will appropriately call int
Tree:CountTree(TreeNodePointer RootOFTree)
to calculate the total number of nodes in a binary search tree .
#14~#16
Please answer the questions in
the following two files: Tree.h and Tree.cpp.
17. [Maps] Suppose we have a map defined as follows to store the name-age mappings:
map<string,int>
nameAgeMap;
(i) Show how you can insert the information of “Mary” is 10 (years old), “John” is 20 (years old), “Jane” is 30 (years old), into the map.(ii) (continue from above) Show how you can use the erase member function of maps to erase the age information of “Mary”.(iii) (continue from above) Show how you can use the find member function of maps to find out whether we have the age information of “Mary”.(iv) Show how you can set up a loop to print out all the information of name-age mappings stored in the map.