Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

0445 Data Structures > Exam 1 > Flashcards

Exam 1 Flashcards

1
Q

Which of the following scenarios describes a principle of Data Hiding? Select all that apply
A) Declare all instance variables private and control access to them through a public method.
B) Use special libraries to encrypt the code of your class so nobody can know what instance variables are declared in it.
C) Do not declare public mutator methods if you do not want the value of your private instance variable to be modified
D) Make sure that you do not store sensitive information (for example passwords) inside your class code.
E) None of the above

A

A, C

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What will be printed if we execute the following code snippet?

public class StatCalls {
public static void main (String​[] args) {
int aSquare = squareNumber(5);
System.out.println(aSquare);
}
int squareNumber(int number) {
int square = number * number;
return square;
}
}

A

The program will not compile

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

You cannot access an instance variable from a static method defined in the same class. (T/F)

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Here is a code for a Dog class:

public class Dog{
String name;
static String owner;
public static void main (String ​[] args) {
Dog ​[] pets = new Dog​[2];
pets​[0] = new Dog();
pets​[0].name = “Lisa”;
pets​[0].owner = “Marge”;
pets​[1] = new Dog();
pets​[1].name = “Bart”;
pets​[1].owner = “Homer”;
for(Dog d : pets)
System.out.println(d.name + “ owned by “ + d.owner);
}
}

WHAT IS PRINTED?

A

Lisa owned by Homer
Bart owned by Homer

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

In the class rectangle we have two instance variables width and height. We write a method getArea() that computes the area of this rectangle. Should we make this method static?

A

No, should be non-static

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Turtle t = new Turtle();

Turtle [ ] turtles = new Turtle [3];

for (int i=0; i<3; i++)

turtles [i] = t;

How many total Turtle objects?

A

1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is printed if we execute the code snipped below?

String s;
s = new String(“Hello”);
String t = s;
String u = new String(s);

System.out.print(t==s + “ “);
System.out.print(u==s + “ “);
System.out.print(t==u);

A

True, False, False

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

The Turtle class has an integer instance variable age with the default value of 0.
Consider the following two static methods inside the Turtle class:

static void addYear(Turtle t){
t = new Turtle();
t.age ++;
}

public static void main (String​[] args){
Turtle myrtle = new Turtle();
myrtle.age = 5;
addYear(myrtle);
System.out.println (“Happy birthday! “+ “You are now “ + myrtle.age + “ years old!”);
}

What is printed after we execute main?

A

Happy Birthday! You are now 5 years old!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is printed after we execute the following code snippet?

ArrayList<Integer> t; // declared a list to store integers
t.add(4); // added 2 integers
t.add(5);
System.out.println(t.size());</Integer>

A

The code will not compile

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

After we execute the code segment below – how many objects need to be garbage-collected because there are no variables that reference them?

String ​[ ] names = new String​[6];
names​[0] = “Alex”;
names​[1] = “Myra”;
names​[2] = “Andrew”;

names​[3] = names​[0];
names​[0] = names​[2];
names​[1] = names​[2];

A

1 abandoned object

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Consider a class Foo with the following instance variables:

private StringBuilder ​[] data;
private int size;
Now consider a copy constructor which does the following:

public Foo(Foo oldFoo) {
data = new StringBuilder​[oldFoo.length];
for (int i = 0; i < oldFoo.size; i++)
data​[i] = oldFoo.data​[i];
size = oldFoo.size;
}

Does this copy constructor produce a deep or a shallow copy, or somewhere in between?

A

Something between deep and shallow

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

The algorithm hasDuplicates answers the question whether the array A has duplicates (at least two identical values).
What is the big O of this algorithm?

algorithm hasDuplicates (array A of size n)

for index from 0 to n − 2

   for rest from index + 1 to n − 1

       if (A​[index] equals A​[rest])

           return true

return false

A

O(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the time complexity of the following Java method?

int C(int n) {
int sum = 0;
for (int i=1; i <= n; i++)
for (int j=0; j <= n; j++)
sum += j;
return sum;
}

A

O(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is big O of the following algorithm that computes the sum of the first n integers?

algorithm Sum (n) {
sum: = 0
for i:=1 to n:
sum:= sum + i
return sum

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is the time complexity of the following Java method?

static int F(int n) {
if (n == 1) return 1;
for (int i = 0; i<n; i++){
for(int j= 0; j<n; j++) {
System.out.println(“*”);
break;
}
}
return 0;
}

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Consider the following code snippet:

static void changeName(String name){
name = “Mr. “ + name;
}

public static void main (String​[] args){
String myname = “Smith”;
changeName (myname);
System.out.println (myname);
}

What is printed when I run main?

A

Smith

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Here is a variation of the previous method:

static void changeJunior (StringBuilder name){
name.append(“ Jr.”);
}

public static void main (String​[] args){
StringBuilder myname = new StringBuilder (“Smith”);
changeJunior (myname);
System.out.println (myname);
}

A

Smith Jr.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Consider these two classes:

class Department {
String name;
public Department(String name){
this.name = name;
}
}

class Student {
Department dept;
Student (Department d){
this.dept = d;
}
Student (Student s){
this.dept = s.dept;
}
}

What is printed when we run the following code fragment?

Student s1 = new Student (new Department(“CS”));
Student s2 = new Student (s1);
s2.dept.name = “English”;
System.out.println(s1.dept.name + “ “ + s2.dept.name);

A

English English

19
Q

Which of the following is True?
A) You can’t make an object of an Abstract class but you can of an Interface.
B) You can’t make an object of an Interface but you can of an Abstract class.
C) You must implement all the abstract methods of the Interface but you do not have to implement all the abstract methods of an Abstract class.
D) You can have both abstract and concrete methods in both Interface and Abstract class.
E) You can have static methods in both Interface and Abstract class.
F) None of the above

A

C, E

20
Q

Consider Java classes Foo and SubFoo, where SubFoo is a subclass of Foo.

Which of the following Java statements are LEGAL?
​[Note: You must indicate ALL legal statements to get credit for this problem]

A) Foo F = new Foo();
B) SubFoo S = new SubFoo();
C) Foo F = new SubFoo();
D) SubFoo S = new Foo();

A

A, B, C

21
Q

Consider the following class definitions:

class Polymorphism {
void method1 () {
System.out.println(“Polymorphism”);
}
}

class Concept extends Polymorphism {
void method2 () {
System.out.println(“Concept”);
}
}

class Generics extends Polymorphism {
void method1() {
System.out.println(“Generics”);
}
}

We run the following program in main:

public static void main ( …) {
Polymorphism ​[ ] p = new Polymorphism ​[3];
p​[0] = new Polymorphism();
p​[1] = new Concept();
p​[2] = new Generics();
for (int i =0; i < 3; i++)
p​[i].method1();
}
}
WHAT IS PRINTED?

A

Polymorphism
Polymorphism
Generics

22
Q

Here is an implementation of a generic method that returns the smallest of the two numbers passed as parameters:

public static <T> T min (T x, T y) {
if (x.compareTo(y) < 0)
return x;
else
return y;
}</T>

What will be printed if we run the following code in the main:

String s1 = “A”;
String s2 = “B”;
String smaller = min(s1, s2);
System.out.println(smaller);

A

The program will not compile

23
Q

Which of the following will sort Dogs in reverse order of their height (from the tallest to the shortest)?
A) Collections.sort(dogs, new Comparator<Dog>() {
public int compare(Dog d1, Dog d2) {
return d2.height – d1.height;
}
});
B) Collections.sort(dogs, new Comparator<Dog>() {
public int compare(Dog d1, Dog d2) {
return - d1.compareTo(d2);
}
});
C) Collections.sort(dogs, new Comparator<Dog>() {
public int compare(Dog d1, Dog d2) {
return d2.compareTo(d1);
}
});
D) None of the above
E) All of the above</Dog></Dog></Dog>

A

E

24
Q

Consider the following declarations:

public interface Ability {
public void able();
}
public class Foo implements Ability {
public void fooMethod() { // code not shown }
public void able() { // code not shown }
}
public class SubFoo extends Foo {
public void subFooMethod() { // code not shown }
}
Which of the following code segments are LEGAL? Indicate ALL LEGAL code segments. Assume default constructors exist for classes Foo and SubFoo.
A) SubFoo S = new SubFoo();
S.able();
S.fooMethod();
B) Ability A = new SubFoo();
A.able();
C) Ability A = new Ability();
A.able();
D) Foo F = new SubFoo();
F.able();
E) Ability A = new SubFoo();
A.subFooMethod();

A

A, B, D

25
Q

What is the time complexity of the following Java method?

static int D(int n) {
int sum = 0;
for (int i=1; i <= n; i++)
sum += ii;
for (int j=0; j < n; j++)
sum-= j;
for (int k = 0; k < 2n; k++)
sum = sum*k;
return sum;
}

A

O(n)

26
Q

What is the time complexity of the following Java method?

static void E(int n) {
int count = 0;
for (int i=n/2; i<n; i++){
int j = 0;
while (j + n/2 <= n){
int k = 1;
while (k <= n){
count = count + 1;
k = k*2;
}
j = j + 1;
}
}
}

A

O(n2 log n)

27
Q

The following Big-O families are in decreasing order of their complexity:
O(n^10000), O(2^n), O(n log n), O(n), O(1)

If the answer is no, then think how would you rearrange them to be in the decreasing order (in preparation for the exam).

A

False
O(2^n), O(n^10000), O(n log n), O(n), O(1)

28
Q

The following Big-O families are in an increasing order of their complexity:
O(1), O(n log n), O(n), O(n100), O(2n)

If you think this is not true, then think how would you rearrange them to be in an increasing order of complexity (in preparation for the exam).

A

False
O(1), O(n), O(n log n), O(n^100), O(2^n)

29
Q

Algorithm Sorting1 (array A)
i: = 1
while i < length(A)
j: = i
while j > 0 and A​[j-1] > A​[j]
swap A​[j] and A​[j-1]
j: = j - 1
i: = i+ 1

What is the name of the algorithm described in Sorting 1?

A

Insertion Sort

30
Q

Algorithm Sorting2 (array A)
n: = length(A)
do:
swapped: = false
for i from 1 to n-1 :
if A​[i-1] > A​[i]:
swap A​[i-1] and A​[i]
swapped: = true
n: = n - 1
while (swapped)

What is the name of the algorithm described in Sorting 2?

A

Bubble Sort

31
Q

Each Node of a linked list stores a single character.

Which of the following lines correctly adds a new node ‘O’ to the front of the Linked List with the head stored in variable head?

class Node {
char data;
Node next;
}
A) Node onode = new Node(‘O’);
onode.next = head;
B) Node onode= new Node(‘O’);
head.next= onode;
C) head.data= ‘O’;
D) All of the above
E) None of the above

A

E

32
Q

Consider a Java reference A to a (not resizable) array that is currently storing n items.
Which of the actions below MAY require O(n) operations to complete? Indicate all correct answers.
A) Adding a new item at some index i of the array
B) Adding a new item at position n of the array
C) Deleting an item from some index i

A

A,C

33
Q

Consider a Java array reference A which is pointing to an array which is full. We want add more space by doubling the length of A. What is a correct way of doing this?

A

Create a new array B double the size of the old one, then copy the data from A to the new array, and set A=B

34
Q

A Queue is implemented using a singly linked list with a tail pointer. Let n denote the number of nodes in the queue.

Let enqueue() be implemented by inserting a new node at the head, and dequeue() be implemented by deletion of a node from the tail.

With this implementation – which of the following operations will run in time O(1) ?

A

enqueue()

35
Q

When we implement Stack ADT using an Array: why do we use the logical end of the array for both push and pop operations?

A

It is more efficient in most cases to add/remove elements at the end of the Array

36
Q

O(1)

A

Constant time
- random access of element in an array
- inserting at the beginning of linkedList
Bright Green

37
Q

O(log n)

A

Logarithmic Time
- Binary Search
Light green

38
Q

O(n)

A

Linear Time
- looping through elements in an array
- searching through a linkedList
Yellow

39
Q

O(n log n)

A

Quasilinear Time
- Quicksort
- Mergesort
- Heapsort
Light orange

40
Q

O(n^2)

A

Quadratic Time
- Insertion sort
- Selection sort
- Bubble Sort
Orange

41
Q

O(n!)

A

Factorial time
- Traveling Salesmen problem
Red

42
Q

Big O Notation

A

How code slows as data grows

43
Q

Which of the following statements are true? Select all the correct answers.

A) String objects are immutable
B) Mutable objects do not have constructors.
C) Accessors do not change state of mutable objects.
D) We can change the fields of immutable objects without creating a new object

A

A, C

0445 Data Structures (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions