Type and answer the questions provided on the document, doesn't have to be done using a compiler.
ANSWER MUST BE TYPED WITHIN THE QUESTIONS BELOW Linked Lists 1. (a) Declare a class named User that contains the following information: (6 pts.) String name String username String password Include in the class a single constructor that is passed a particular name, username, and password; setters and getters, and a toString method that returns the information in a given User object as follows: "Ashley Smith username: asmith password: aWjPP406!" (b) Declare a class named UserNode that contains a single User object and a link to another UserNode. Include an appropriate constructor and an appropriate set of methods for this class. (4 pts). 2. Create a class named UserAccounts that maintains a list of users (implemented as a linked list of UserNodes), with an appropriate constructor, and the following methods: (15 pts.) isEmpty() – returns true if list is empty, and false otherwise findPassword – returns the password for a given user name changePassword – updates the password for a given user name and password. If they do not match, the password is not updated. addUser – passed a User object to add deleteUser – deletes a user for a given user name and password. If they do not match, the user is not deleted. printUsers – prints a list of all users (including name, username and password) Recursion 3. Determine what the following function calls return for recursive function func below. (4 pts.) public static int func(int n) { if(n == 1) return n; else return 1 + func(n-1); (a) func(1) = _________ (b) func(4) = _________ 4. Does func above perform top down or bottom up computation? _________________ (2 pts.) 5. Determine the general result (in terms of n) of the following recursive function (4 pts.) public static void func2(int n) { if(n == 1) System.out.println(“*”); else { for (int i = 1; i <= n; i++) system.out.print(“*”); system.out.println(); func2(n-1); } } 6. does func2 above perform down or bottom up computation? ___________________ (2 pts.) searching and sorting (chapter 18) (30 pts.) 7. regarding the behavior of algorithms (i.e., rate of growth, big-oh analysis) (6 pts.) (a)the rate of growth of a given algorithm can be determined either analytically (by inspection of the algorithm and use of mathematics), or empirically (by implementing it and executing on various size input). true / false (b)to determine which of two algorithms that solve the same problem has the slowest rate of growth (i.e., that is generally more efficient), it is sufficient to implement and execute each on a sufficiently large problem and compare the run times. true / false (c)for most algorithms, solving a problem that is twice as big takes more than double the amount of time. true / false 8. for the following rates of growth, answer the following (selecting from the rates of growth to the right): (12 pts.) (a) fastest can sort (for general sorting) ______o(2n) (b)fastest can search a sorted list______o(n3) (c) fastest can search an unsorted list ______o(n2 logn) (d)intractable rate of growth ______o(n2) (e) average rate of growth of bubblesort ______o(nlogn) (f)constant time regardless of problem size ______o(n) o(logn) o(1) 9. give the resulting lists after the first two passes of selection sort, insertion sort, bubblesort, and quicksort under the headings below. for quicksort, assume that the first item in each sublist is always chosen as the pivot value (which is not a problem when lists are randomly ordered). (12 pts.) selection sortinsertion sortbubblesort quicksort 20 31 6 19 28 4 9 36 stacks and queues 10. answer the following related to stacks and queues. (a)what are the basic operations of a queue? (2 pts.) (b) complete the following stack class. (12 pts.) public class stack { private int[] elements; private int top; public stack(){ elements = new int[10]; top = -1; } public boolean isempty(){ return ________________; } public boolean isfull(){ ________________; } public void push(int item){ if (____________) system.out.println("* stack full- cannot push *"); else{ ________________; elements[top] = item; } } public int pop(){ if (top == -1) system.out.println("* stack empty - cannot pop *"); else{ string top_item = elements[top]; ________________; return top_item; } } } application of stacks 11.show the series of stack values for evaluating the postfix expression of 2 + (3 * 4) below, (6 pts.) 2 3 4 * + binary trees 12. give the preorder, inorder, and postorder traversals of the following binary tree. (9 pts.) a b e c d f preorder: inorder: postorder: 3. create a binary search tree for the values given below, in which the value 21 is the root of the tree, and that the tree overall is balanced (i.e., approximately the same number of nodes in the left and right subtrees of every node in the tree). (8 pts.) 10, 16, 24, 9, 2, 27, 31, 45, 5, 38, 42, 37, 21, 7, 4 n;="" i++)="" system.out.print(“*”);="" system.out.println();="" func2(n-1);="" }="" }="" 6.="" does="" func2="" above="" perform="" down="" or="" bottom="" up="" computation?="" ___________________="" (2="" pts.)="" searching="" and="" sorting="" (chapter="" 18)="" (30="" pts.)="" 7.="" regarding="" the="" behavior="" of="" algorithms="" (i.e.,="" rate="" of="" growth,="" big-oh="" analysis)="" (6="" pts.)="" (a)="" the="" rate="" of="" growth="" of="" a="" given="" algorithm="" can="" be="" determined="" either="" analytically="" (by="" inspection="" of="" the="" algorithm="" and="" use="" of="" mathematics),="" or="" empirically="" (by="" implementing="" it="" and="" executing="" on="" various="" size="" input).="" true="" false="" (b)="" to="" determine="" which="" of="" two="" algorithms="" that="" solve="" the="" same="" problem="" has="" the="" slowest="" rate="" of="" growth="" (i.e.,="" that="" is="" generally="" more="" efficient),="" it="" is="" sufficient="" to="" implement="" and="" execute="" each="" on="" a="" sufficiently="" large="" problem="" and="" compare="" the="" run="" times.="" true="" false="" (c)="" for="" most="" algorithms,="" solving="" a="" problem="" that="" is="" twice="" as="" big="" takes="" more="" than="" double="" the="" amount="" of="" time.="" true="" false="" 8.="" for="" the="" following="" rates="" of="" growth,="" answer="" the="" following="" (selecting="" from="" the="" rates="" of="" growth="" to="" the="" right):="" (12="" pts.)="" (a)="" fastest="" can="" sort="" (for="" general="" sorting)="" ______="" o(2n)="" (b)="" fastest="" can="" search="" a="" sorted="" list="" ______="" o(n3)="" (c)="" fastest="" can="" search="" an="" unsorted="" list="" ______="" o(n2="" logn)="" (d)="" intractable="" rate="" of="" growth="" ______="" o(n2)="" (e)="" average="" rate="" of="" growth="" of="" bubblesort="" ______="" o(nlogn)="" (f)="" constant="" time="" regardless="" of="" problem="" size="" ______="" o(n)="" o(logn)="" o(1)="" 9.="" give="" the="" resulting="" lists="" after="" the="" first="" two="" passes="" of="" selection="" sort,="" insertion="" sort,="" bubblesort,="" and="" quicksort="" under="" the="" headings="" below.="" for="" quicksort,="" assume="" that="" the="" first="" item="" in="" each="" sublist="" is="" always="" chosen="" as="" the="" pivot="" value="" (which="" is="" not="" a="" problem="" when="" lists="" are="" randomly="" ordered).="" (12="" pts.)="" selection="" sort="" insertion="" sort="" bubblesort="" quicksort="" 20="" 31="" 6="" 19="" 28="" 4="" 9="" 36="" stacks="" and="" queues="" 10.="" answer="" the="" following="" related="" to="" stacks="" and="" queues.="" (a)="" what="" are="" the="" basic="" operations="" of="" a="" queue?="" (2="" pts.)="" (b)="" complete="" the="" following="" stack="" class.="" (12="" pts.)="" public="" class="" stack="" {="" private="" int[]="" elements;="" private="" int="" top;="" public="" stack(){="" elements="new" int[10];="" top="-1;" }="" public="" boolean="" isempty(){="" return="" ________________;="" }="" public="" boolean="" isfull(){="" ________________;="" }="" public="" void="" push(int="" item){="" if="" (____________)="" system.out.println("*="" stack="" full-="" cannot="" push="" *");="" else{="" ________________;="" elements[top]="item;" }="" }="" public="" int="" pop(){="" if="" (top="=" -1)="" system.out.println("*="" stack="" empty="" -="" cannot="" pop="" *");="" else{="" string="" top_item="elements[top];" ________________;="" return="" top_item;="" }="" }="" }="" application="" of="" stacks="" 11.="" show="" the="" series="" of="" stack="" values="" for="" evaluating="" the="" postfix="" expression="" of="" 2="" +="" (3="" *="" 4)="" below,="" (6="" pts.)="" 2="" 3="" 4="" *="" +="" binary="" trees="" 12.="" give="" the="" preorder,="" inorder,="" and="" postorder="" traversals="" of="" the="" following="" binary="" tree.="" (9="" pts.)="" a="" b="" e="" c="" d="" f="" preorder:="" inorder:="" postorder:="" 3.="" create="" a="" binary="" search="" tree="" for="" the="" values="" given="" below,="" in="" which="" the="" value="" 21="" is="" the="" root="" of="" the="" tree,="" and="" that="" the="" tree="" overall="" is="" balanced="" (i.e.,="" approximately="" the="" same="" number="" of="" nodes="" in="" the="" left="" and="" right="" subtrees="" of="" every="" node="" in="" the="" tree).="" (8="" pts.)="" 10,="" 16,="" 24,="" 9,="" 2,="" 27,="" 31,="" 45,="" 5,="" 38,="" 42,="" 37,="" 21,="" 7,="">