NATIONAL OPEN UNIVERSITY OF NIGERIA

UNIVERSITY VILLAGE, PLOT 91, CASDASTRAL ZONE, NNAMDI AZIKIWE EXPRESS WAY, JABI, ABUJA.
FACULTY OF SCIENCES
JANUARY 2021 EXAMINATION

Course Code: CIT341

Course Title: Data Structures

Credit: 3 Units

Time Allowed: 3 Hours

Instruction: Answer Question One and Any Other Four Questions

1. a. Explain what you understand by the following concepts and give an example of each

i. Linear Data Structure (2 marks)

ii. Non-linear data structure (2 marks)

b. Which linear data structure is more suitable to use in implementing each of the following applications:

i. Handling Print jobs on a network printer (1 mark)

ii. Undo function in a word processor (1 mark)

c. Many real world situations correspond to a stack. Think of real-world stack and describe the push and pop operations on it. (3 marks)

d. The following operations are applied to an initially empty queue of integers: enqueue(5); enqueue(3); dequeue(); enqueue(2); enqueue(9); getHead(); enqueue(8); dequeue(); Which element is at the front of the queue and which element is at the rear of the queue after executing these operations? (2 marks)

e. Given an AVL tree with a left subtree of height 5, what is the maximum and the minimum height of its right subtree? (2 marks)

f. Arrange the following complexity classes from best to worst: O(n2 ) , O(n) , O(log(n)) (1 mark)

g. Write down the worst-case and the best case time complexity in Big-O notation for each of the following - Bubble sort (2 marks)

- Quick sort (2 marks)

h. Study the following code segment carefully and explain what it does and give the output. (4 marks) int[] question1 = { 1, 4, 3, 6, 8, 2, 5}; int secret = question1[0], index=0; while (index < question1.length) { if ( question1[index] > secret) secret = question1[index]; index++ ; } System.out.println( secret);

2. a. Explain what you understand by the following concepts and give one example of each

i. Datatype (3 marks)

ii. Abstract datatype (3 marks)

b. Assume a machine which has a single stack and the following five instructions: PUSH A which pushes the value of operand A on the stack ADD which removes the two top elements and places their sum on the stack MULT which removes and multiples the top two elements of the stack and places the result on the stack SUB which removes the top two elements from the stack, subtracts the one which was on top from the other, and places the result on the stack. DIV which removes the top two elements from the stack, divides the one which was on top into the other, and places the result on the stack. Illustrate the execution of the expression (A + B * C) / (D – E) on this stack machine (Remember the order of precedence of arithmetic operators) (6 marks)

3. a. Use the tree below to answer the following questions

i. What is the degree of a node 3 (2 marks)

ii. What is the height of a tree ? (2 marks)

iii. What will be the order in which nodes will be first visited during in-order traversal? (2 marks)

iv. What will be the order in which nodes will be first visited during post-order traversal? (2 marks)

b. Information about a certain binary tree is provided as follows: Post-order traversal: F H E C G D B A In-order traversal: F C H E A D G B Draw the binary tree. (4 marks)

4. a. Write a java program that, and then display the numbers in an array in the reverse order. Assume the array elements are {1,2,3,4,5,6,7,8,9,10} (6 marks)

b. Study the following code fragment program carefully and answer all questions associated with the following programs 1 for(i=0; i<7; i++){ 2 for (j=0;j - perimeter: to compute the perimeter of the Tetragon (perimeter= 2*(length + width)) - area: to compute the area of the Tetragon (area= length * width)

c. declare a class rectangle that implements the interface Tetragon (4 marks)

6. a. Design a class BankAccount having the following specifications:

 an instance variable accountNumber of type int.

 an instance variable customerName of type String.

 an instance variable balance of type double.

 a constructor to initialize all the instance variables.

 a method deposit that takes amount as input and add it to the value of balance

 a method withdraw that takes amount as input and subtract it from the value of balance

 a method getBalance that return the value of balance (8 marks)

b. Create a BankAccount instances named myaccount using the class you defined in part (a) above. The account number should be 1234, the account name=” John Musa” and the initial balance is 20000 (4 marks)