The node n contains a reference to an object and references to five children.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Past paper questions

(e) Trees and Recursion (8 marks)

(i) We've been dealing with binary trees in this module, but in this exam, lets deal with 5-ary trees. In a 5-ary tree, each node can have up to five children and a parent (the only node in the tree that has no parent is the root of the tree).

Co

The node n contains a reference to an object and references to five children. Each child has an index C, through C, from left to right. The node n does not contain a reference to the parent. The node has only one constructor that takes in a reference to the object stored in this node and an array of five children (you do not need to check if there are five). If a child does not exist, the reference is wall. It has a method that returns the object stored at this node getElement (). It also has a method getChild (int i) that takes in an index 1 (0 through 4) and returns a reference to Node which is the appropriate child (which can be null).

Write a java generic Node that implements the above-described node.

[5 marks]

(i) In the module, we studied a preorder traversal of a tree. Pretend you have the following class that fully implements a 5-ary tree that uses your Node class.

public class Trees  <

private Node root;

//you should use methods defined in part (1) //assume they work as described above.

public void preorder() {

...//to implement in (1)...

Pretend that there is a 5-ary tree constructed and stored in the root beforehand. Given this tree, implement the method public void preorder() that conducts a preorder traversal of the 5-ary tree inside the Trees class. To visit the node in the tree, simply print out its contents to the screen. Hint: you may need a private helper method. [3 marks]

(b) Linked Lists

Recall that you have a Link class which forms the basis of a linked list. public class Link (

private Object element;

private Link next;

public Link (Object, QueueElement a) (

this element:

this.next;

}

Assume that Link has all get and set methods already implemented. i) Write a LinkedList class. This class should have all necessary at- tributes for a linked list and a constructor that takes no parameters and constructs an empty list. Do not implement any other methods. You will lose marks. [3 marks]

ii) Inside your linked list class, assume that a linked list has already been defined and contained in your attributes. Write a method public void removeMiddle ) that removes the middle element of your linked list. If there is an odd number of elements, the middle is clearly defined. If there is an even number of elements, take the lower of the two. [5 marks)

Reference Diagrams Consider the following class public class Student (

private int studenter

private Student labPartner:

private static int nextStudentusber 100;

public Student () (

}

this studentusber Student.nextStudent Funber Student.nextStudent Number**; this.labPartner sull

public void setLabPartner (Student labPartner) {

this.labPartner⚫ labPartner

(a) Write code that is able to construct an array of 10 student objects and loads them in increasing student number order into that array. The lab part ners of these students should all be set to null

(b) Consider the reference diagram below:

[3 marks]

Write code that constructs the above reference diagram.

(5 marks]

(c) Generics, Linked List, and Stacks/Recursion

(1) A stack could be implemented with a linked list. We also learnt gener ies in this module. Provide the the class definition and the data only for a Link

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of