Java

TOPIC 28 – DATA STRUCTURE QUIZ REVIEW

DETAILS & REVIEW

DETAILS

This short quiz covers the Data Structures unit. All notes. All work.

REVIEW

a) In Java, the method used to add an element to a queue is called ______________. Traditionally, it is often called enqueue.

b) The traditional method used to add an element to a stack is called _______________ (although Java also supports the add method.).

c) In Java, the method used to get and remove an element from a queue is called _______________. Traditionally, it is often called dequeue.

d) The method used to get and remove an element from a stack is called _______________.

e) FIFO refers to ____________ ___________ ____________ ____________. It is the same as LILO.

f) FILO refers to ____________ ___________ ____________ ____________. It is the same as LIFO.

g) _______________ is the type of data structure that is FIFO.

h) _______________ is the type of data structure that is FILO.

i) ____________ is a data structure where all elements are stored together sequentially in memory. This structure cannot be resized.

j) A(n) ____________ is a linear data structure that stores elements in different nodes. Each node is stored in a different location in memory. This structure can be resized efficiently.

k) A(n) ______________ is like a normal array but with the ability of being resized. It could be implemented using an array or a linked list.

l) A data structure that allows you to add and remove elements only at the one end of it is called _____________.

m) A data structure that allows you to add elements at one end and get/remove from the other end is called _______________.

n) A data structure's efficiency is measured by both the ______________ and the _______________ to manipulate the structure.

o) A(n) ____________ is a data structure that stores elements in no specific order and makes sure that there are no duplicates. In Java, both implementations that we looked at do store elements in alphanumeric order.

p) Java _________________ is the framework that contains many different implementations of data structures including lists, sets and maps.

q) With regards to Data Structures, ADT stands for _______________ ________________ ________________.

r) A(n) __________________ is a data structure that stores both a key and value. The key is used to access the value. It is also called an associative array.

s) Java implementations of List ADTs include _______________ and ________________.

t) Java implementations of Map ADTs include ________________ and _______________.

u) Java implementations of Set ADTs include ________________ and ________________.

v) The enhanced for loop can be used with data structures that implement the ____________ interface.

w) A normal array has a _______________ size.

x) A(n) ______________ for loop can be used on any object that implements the Iterable interface.

y) Both the Stack and Queue implementations that we looked at have a __________ method that allows you to see the element that could be popped or polled next but doesn’t actually remove the element from the structure.

first in first out push pop poll (formerly dequeue) array first in last out linked list abstract data type Iterable peek

dynamic array stack queue memory usage time required set collections static stack enhanced

all data transfixed application development tool LinkedList ArrayList HashMap add (formerly enqueue) TreeMap HashSet TreeSet queue

QUESTION 2

You should know the definition of the following terms:

• Array
• Dynamic array
• Linked List
• Stack, Push, Pop, Peek
• Queue, Add, Pool, Peek
• Map, Key, Value
• Set
• Efficiency
• Complexity
• Abstract Data Type
• Length or Size
  
  

QUESTION 3

What will the following code output:

a)
LinkedList<Integer> lili = new LinkedList<Integer>();

lili.add(5);

lili.add(4);

lili.add(0);

System.out.println(lili);

b)

ArrayList<Integer> al = new ArrayList<Integer>();

al.add(5);

al.add(0,4);

al.add(7);

System.out.println(al);

c)

Stack<String> stak = new Stack<String>();

stak.push("Luke");

stak.push("Leia");

stak.push("Han");

stak.push("Yoda");

stak.pop();

System.out.println(stak);

d)

Queue<String> q = new LinkedList<String>();

q.add("Vader");

q.add("Kylo");

q.add("Palpatine");

q.remove();

q.remove();

System.out.println(q);

e)

TreeSet<Integer> s = new TreeSet<Integer>();

s.add(5);

s.add(3);

s.add(2);

s.add(1);

s.add(5);

System.out.println(s.size());

QUESTION 4

Consider the following drawing of a linked list.

a) Alter the drawing to insert a Node at the end containing the value 35.

b) Alter the original drawing to insert a Node at the beginning containing the value 30.

c) Alter the original drawing to insert a Node after the middle node.

d) Alter the original drawing to remove the middle node from the list.

QUESTION 5

Considering Linked Lists and Dynamic Arrays, which is more efficient to

a) Look up the value at any element i

b) Inserting a value at the end of the collection

c) Inserting a value at the start of the collection

d) Removing a value from a location i in the collection

e) Going through the collection one element at the time to calculate the total of all values

QUESTION 6

Explain two different strategies on how to implement a dynamic array. You are essentially being asked to give two strategies on how to deal with inserting/deleting into an array.

Good luck!