QUESTION 1 (General) a. A Java program is to be run on a 32 bit machine, therefore the size of memory addresses is four bytes, and the size of an integer is 4 bytes. A memory reference for an array contains only the first address of location being referenced. Determine the total amount of memory to be allocated by following statements. int i,j=10; float [] a nnew float[i]. [5 marks] b. Using the ASCII table in Appendix A, write down the character representation of the hexadecimal sequence below. 596F7527726520726967687421 [7 marics] c. A C program is used to define a linked list as follows struct Node ( int data; Node * link; struct Node "List, *Prev, "Pos; Figure 1 shows an ordered linked list, with pointer Pos and Prev accessing specific nodes within the list. Figure 1: Representation of an ordered linked list i. A node has been initialized with the value 8 by the following code newnode =new ( Node); newnode > data =8; newnode > link = NULL Diagrammatically represent the steps involved in getting the value 8 inserted into the list [3 marks] ii. Draw the pointer manipulations required if the value 9 was to be removed from the original list depicted in figure 1 [2 mariks] d. Briefly explain why the time to search a linked list is (n) [2 marks] e. Describe two advantages and two disadvantages of representing an unsorted data set in a linked list as opposed to an array. [4 marks] f. Given the following Java code, write down the expected output to the system console. String sentence = new String("A group of related words"); String [] words = sentence. split(" " ); for (int i=0;i iswords.length 0;i++) System.out.printin (i+ ";"+words[i]): [2 marks] g. Given the regular expression / b[aeiou]t/, indicate which of the following strings would match the pattern. [2 marks] bae, bat, boot, bit h. Write a regular expression that can match hexadecimal sequences. [3 marks] QUESTION 2. (Dynamic data structures) a. Show the resulting mimimizing binary heap after the values 21,24,12,27,22, 15,25,30 have been inserted (in the order specified). [4 marks] b. What insertion criteria will cause a binary search tree to exhibit its worst case performance on a search. [2 marks] c. What technique can be used to adjust an unbalanced binary search tree such that the performance of a search improves? [1 mark] d. Show the result of inserting the values 20 and then 26 into the Red-Black tree shown in figure 2. [8 marks] Figure 2. The Red-Black tree for question 2 Question 3 - [TOTAL 15 MARKS] The graph in Figure 1, represents the distances of roads between cities. Figure1: Graph Representing the Distances between Cities in a Country a. Draw the Adjacency matrix for the graph. [4 marks] b. Draw the Adjacency list for the graph. [4 marks] c. Create a table that shows the progression of Dijkstra's Single Source Shortest Path Algorithm through the graph in Figure 1 from city A. d. What is the total time complexity for Radix Sort? [4 marks] e. What is the Space Complexity of the Bubble Sort ? [2 mark] [1 mark]
