Java questions #1

From Visual Basic to GNU C, this is the place to talk programming.

Moderators: SecretSquirrel, just brew it!

Java questions #1

Postposted on Sun May 02, 2004 3:54 pm

I'm studying for AB level CompSci, in Java this year, and can't put my finger on the answers to these questions.

"These questions concern the following definition of class List, intended to be used to represent a list of objects (note that the List class uses the standard ListNode class).

Code: Select all
Public class List {
     /*** fields ***/
     private ListNode first;     //pointer to the first node
                                   //in the list
     private ListNode last;      //pointer to the last node
                                   //in the list

     /*** methods ***/
     public List ( )  {first = last = null}  //constructor

     public void addToEnd(Object ob) {
          ListNode tmp = new ListNode (ob, null);
          if (last != null) last.setNext(tmp);
          last = tmp;
     }
}

An empty list is intended to be represented by a List in which first and last are both null. A nonempty list is intended to be represented by a List in which:
  • The first items in the list are stored in a linked list.
  • first points to the first node in the linked list.
  • last points to the last node in the linked list.
However, the List class has not been implemented correctly.


1. What is the problem with the implementation of the List class?
  1. The constructor is not implemented correctly.
  2. The types of first and last fields are wrong.
  3. The addToEnd method will not work correctly when the first value is added to the list.
  4. The addToEnd method will not work correctly when a value other than the first is added to the list.
  5. The addToEnd method will not work correctly when a duplicate value is added to the list.

2. Which of the following best characterizes the running time of the version of addToEnd given above for a list that initially contains n values?
  1. O(1)
  2. O(log n)
  3. O(n)
  4. O(n log n)
  5. O(n^2)"

Any thoughts?
mac_h8r1.postCount++;
Chaos reigns within. Reflect, repent, and reboot. Order shall return.
Slivovitz owns you.
mac_h8r1
Minister of Gerbil Affairs
 
Posts: 2962
Joined: Tue Sep 24, 2002 6:57 pm
Location: Alpha Epsilon Pi for life

Postposted on Sun May 02, 2004 7:47 pm

1. is C

2. is A
Yahoolian
Grand Gerbil Poohbah
 
Posts: 3576
Joined: Sun Feb 16, 2003 3:43 pm
Location: MD

Postposted on Sun May 02, 2004 7:51 pm

ok, but how did you GET to those answers? What is the logic you used?
mac_h8r1.postCount++;
Chaos reigns within. Reflect, repent, and reboot. Order shall return.
Slivovitz owns you.
mac_h8r1
Minister of Gerbil Affairs
 
Posts: 2962
Joined: Tue Sep 24, 2002 6:57 pm
Location: Alpha Epsilon Pi for life

Postposted on Sun May 02, 2004 8:11 pm

Okay, when you call addToEnd with an empty list, it doesn't set the first to equal last, it only sets last correctly.

First is supposed to reference the first ListNode in the list, and when you only have one ListNode in a list, both first and last should reference that ListNode.

For 2, if you analyze the method, addToEnd with a list of 2 elements would take the same number of operations as a list with 4 elements, thus it is O(1), constant time.

Coincidentally, I'm also taking AP CompSci AB and will be taking the exam..
Yahoolian
Grand Gerbil Poohbah
 
Posts: 3576
Joined: Sun Feb 16, 2003 3:43 pm
Location: MD

Postposted on Sun May 02, 2004 8:25 pm

Yahoolian wrote:Coincidentally, I'm also taking AP CompSci AB and will be taking the exam..

Good luck with it. I did "independent study" for the test, and thus have not done very much. 5 on the A level, then didn't touch compsci until 3 days before a competition, where I taught myself beyond the scope of the A test in Java in time for the contest.

Didn't touch it again until 3 days ago. Just finishing up on the syntax of Lists and trees. All is good!

Thx for the help. I may have another to post later in the evening :)
mac_h8r1.postCount++;
Chaos reigns within. Reflect, repent, and reboot. Order shall return.
Slivovitz owns you.
mac_h8r1
Minister of Gerbil Affairs
 
Posts: 2962
Joined: Tue Sep 24, 2002 6:57 pm
Location: Alpha Epsilon Pi for life

Postposted on Sun May 02, 2004 8:40 pm

Best of luck to you too.

Did you look over the marine biology case study yet? That's supposed to be a good chunk of the test.

You're welcome.

Heh, I participated in the 2004 UMD Programming Contest, our team was supposed to place 5th but the judges deleted one of our submissions and couldn't undo it, and we incurred a large point penalty when we resubmitted it towards the end of the contest...
Yahoolian
Grand Gerbil Poohbah
 
Posts: 3576
Joined: Sun Feb 16, 2003 3:43 pm
Location: MD

Postposted on Sun May 02, 2004 8:56 pm

Weeeelll, the Marine Bio Case Study is in my car right now. The WHOLE MB CS. Haven't looked at it yet :\

Our competition was a smaller thing through Cal State, Los Angeles

http://csnetwork.calstatela.edu/progfest/scoreboard.php
We took 4th. All 3 programs were mine, hehe. The other two guys couldn't get it together.
mac_h8r1.postCount++;
Chaos reigns within. Reflect, repent, and reboot. Order shall return.
Slivovitz owns you.
mac_h8r1
Minister of Gerbil Affairs
 
Posts: 2962
Joined: Tue Sep 24, 2002 6:57 pm
Location: Alpha Epsilon Pi for life

Postposted on Sun May 02, 2004 9:04 pm

Gotta love "teamwork."

Remember, there is no I in team, but there is a me. (esp when the rest of your team is incompetent) :wink:
Yahoolian
Grand Gerbil Poohbah
 
Posts: 3576
Joined: Sun Feb 16, 2003 3:43 pm
Location: MD

Postposted on Sun May 02, 2004 9:24 pm

Yahoolian wrote:Gotta love "teamwork."

Remember, there is no I in team, but there is a me. (esp when the rest of your team is incompetent) :wink:

I couldn't agree more. I was on the verge of completing another, but I couldn't figure out an algorithm to make it run fast enough when using larger numbers. Still haven't solved it. Maybe after the APs, I'll post it up. Besides, it wouldn't have affected the score.
mac_h8r1.postCount++;
Chaos reigns within. Reflect, repent, and reboot. Order shall return.
Slivovitz owns you.
mac_h8r1
Minister of Gerbil Affairs
 
Posts: 2962
Joined: Tue Sep 24, 2002 6:57 pm
Location: Alpha Epsilon Pi for life


Return to Developer's Den

Who is online

Users browsing this forum: Exabot [Bot] and 2 guests