Print Full Name:SID (last 6 digits):Email:CMSC 420 Data StructuresWorksheet 1: Linear Relationships Week TwoDr. Michelle McElvany HugueRTfPInstructions:• The Goal: Show what you know.• The Method: For each section, answer what you can.• The Requirement: Explain your answer clearly and with appropriate assumptions.• The Reward: Generous partial credit for correct and clear partial answers.1Problem 1: Lists and Arrays–Counting KeysEssential Definitions: A common set of definitions must be agreed upon before any study ofdata structures can take place. A reference to our course glossary or definitions specific to theproblems of interest will be provided as needed. You may adopt other definitions from othersources as long as they are equivalent to ours and are properly documented.finite graph: consists of a finite set of vertices, V , and a set of edges, E, where G=(V, E) andedge ¡ vi, vj ¿ connects vi to vj, for i = j. Comment: Typically, the edges model somerelationship between either the nodes as stored (merely the shape or syntax or underlyingstructure) or the information (semantics or relationships among keys) they hold.list: a finite set of vertices or a finite connected graph where a vertex can share edges with atmost two other vertices. Unless otherwise stated, the size of list is allowed to grow.array: is a list of n vertices, where n is fixed and individual elements are accessed by an index.binary tree: is a finite graph that is either empty or consists of a single vertex or node and twodisjoint subsets, each of which is a binary tree.k-ary tree: is a finite graph that is either empty or consists of a single vertex or node and k > 1disjoint subsets, each of which is a k-ary tree.k-way search tree: is a k-ary tree in which every non-empty node can hold keys (or data)organized using a the k-way search property.Instructions: Explore these tragically True or frighteningly False statements. fill in the circlecorresponding to the appropriate choice (True or False). For example, if any given statement isTrue, you should fill in the first circle, such that becomes . Othe r wis e, fi l l i n the s ec ondcircle False. Zero points for a blank answer. Two points per c orr e c t action. and no partial credit.If this were a test, you would be invited to give a brief justification of your answer for full credit.However, there is no partial credit on worksheets. So, if you feel the n ee d to just i fy youranswer, then False is probably your best choice.2Statement True False(a) All li st s are ord er ed data st r u ct ures.(b) The nodes in a 4- a ry tree have exactly 4 children.(c) A 4-way search tree has keys in the leaves.(d) The root of a non - em p ty k-ary tr ee i s at level 0.(e) Every linked list has a first key and a last key.(f) Unsuccessful search in a nonempty array is in O(n).(g) Search in a sort ed linked list is in O(log n).(h) Search in a binary search tree is in O(n).(i) The shape of a binary search tree (BST) is independent of the order inwhich keys are inserted.(j) The maximum number of levels i n a 4-way search tree containing nkeys is n.3Code for Problems 2.1–2.4public class Stack {private int size;private Object array[];public Stack() {array = new Object[0];size = 0;}public void push(Object data) {size++;Object temp[] = new Object[size];for (int i = 0; i < size - 1; i++)temp[i] = array[i];temp[size - 1] = data;array = temp;}public void pushAll(Stack other) {for (int i = 0; i < other.size; i++) {push(other.array[i]);}public Object pop() {size--;Object value = array[size];Object temp[] = new Object[size];for (int i = 0; i < size; i++)temp[i] = array[i];array = temp;return value;}public void println() {for (int i = 0; i < size; i++)System.out.println(array[i]);}public String toString() {String result = new String("");for (int i = 0; i < size; i++)result += array[i] + "\n";return (result);}}Code for Problems 2.1–2.4 (Page 11)4Problem 2: Lists, arrays and stacksNote: if you are slow at understanding code, please skip this problem and come back to it only ifyou run out of problems in which you are more confident.Answer the following questions about the code given on page 10 for a simple array-based stackthat is expected to handle large data sets. You are to assume that implementation will be inJAVA.a. Give the asymptotic complexity of running time (O(·) and Ω(·))b. Ide ntify pitfalls in the current implementation or write NONE.““c. Exp l ai n any improvement you would make, and gi ve the asymptotic complexityof your solution. DO NOT WRITE CODE!4.1 push()a.b.c.4.2 pop()a.b.c.4.3 println()a.b.c.4.4 pushAll()a.b.c.54.5