ICT209 Data Structures and Abstractions EXAM 1
1. (a)
(b) Write the truth table for a logical ‘and’: &&.
4. (a)
[5 + 5 = 10]
Explain the difference between pointer and reference parameters. Include diagrams of the stack in your explanation.
char is one of the C++ standard types, list six (6) others. (c) Write down the solution to: 11100110 ˆ 11001011.
(d) Given the if statement below: if (num > 10)
write down values for num which should be used to test the statement.
[3 + 2 + 2 + 3 = 10]
2. Write down the whole of the header file for a minimal and complete Date class. The date is to be composed of 3 integers. You do not need to comment the code and you do not need to use in-line methods.
3. (a)
[10]
Draw a UML diagram showing the relationship between a Date class and a DateAr- ray class.
(b) There are at least 25 different rules that need to be applied specifically to C++ object oriented coding. Describe any five (5) of them.
(b) Write C++ code for the body of the method with declaration:
void LinkedList::Delete (Node *nodeBefore)
where nodeBefore is the node in front of the one to be deleted.
[5 + 5 = 10]
Murdoch University
June 2004
ICT209 Data Structures and Abstractions EXAM 2
5. (a)
(b) Write down three (3) methods—other than constructors and destructors—that are
6. (a)
Given the existence of a linked list class called LinkedList, write the private part of the class declaration for:
i. An array of linked lists of size SIZE.
ii. A node whose data is itself a linked list.
What are the relative advantages and disadvantages of using an ADS Linked List as compared to an ADS Array?
required by all simple ADS data structures.
(c) Draw diagrams showing the conceptual difference between an array and an ADS
array, where neither are dynamic.
(b) What is the difference between a max-heap and a min-heap?
(c) Assuming they had been programmed with generic names for adding and deleting data—rather then their more normal method names—draw diagrams showing the contents of
i. a stack, ii. a queue,
iii. a min-heap,
after the following actions have occurred:
Add(21) Add(4) Delete() Add(11) Add(10) Delete() Delete() Add(15) Delete() Add(2)
[5 + 3 + 2 = 10]
[3 + 1 + 6 = 10]
Murdoch University
June 2004
ICT209 Data Structures and Abstractions EXAM 3
7. Write C++ code for the binary search of an ADS array, where the array was defined with:
private:
float m array[SIZE]; int filledElements;
and the method is declared with:
bool Find (float target, int bottomIndex, int topIndex, int &targetIndex);
[10]
8. (a)
(b) Given a table size of 100 what index is given when the key 2255 is hashed using the following algorithms:
What is a hash table and under what conditions is it useful as a data store?
i. Truncation?
ii. Modular arithmetic?
iii. Radix conversion using a base of 3? (c) What is collision resolution?
(d) Name two (2) collision resolution algorithms.
9. The following numbers are added to a data store: 23, 14, 56, 78, 72 and 45. Draw a diagram of the data store that results if it was
(a) An AVL tree. (b) A 3-way B tree.
[2 + 4 + 2 + 2 = 10]
[6 + 4 = 10]
Murdoch University
June 2004
ICT209 Data Structures and Abstractions
EXAM
4
10. Consider the graph below:
0
1
2
7
3
4
5
6
(a) Draw the adjacency list for this graph.
(b) Write down the nodes visited in a search starting from 2 and searching for 7, if it is
i. a breadth first search ii. a depth first search
——– ♦♦♦
[5 + 5 = 10]
END OF PAPER
♦♦♦——–
Murdoch University
June 2004