Brainscape's Knowledge GenomeTM

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


See full index

Data Structure and Algorithms > Quizzes Questions/answer > Flashcards

Quizzes Questions/answer Flashcards

1
Q

Suppose you want to define a data structure that is fast in search, which of the following data structure would you choose?

A

ordered array

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

Rank the following time complexity orders with the slowest one comes first.

A
  1. O(1)
  2. O(logn)
  3. O(n)
  4. O(nlogn)
  5. O(n^2)
  6. O(n^3)
  7. O(2^n)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

O(1) means a process operates in __ time.

A

constant

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

In general, ordered arrays, compared with unordered array, are: (select all that are correct)

A
  1. slower Insertion
  2. Quicker at searching
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

In an unordered array, it is generally faster to find out an item is not in the array than to find out it is. True or False?

A

False

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

Select all the correct statements about the following operation:
Inserting an item into unordered array:

1.takes time proportional to the size of the array
2. requires multiple comparisons
3. requires shifting other items to make room
4. takes the same time no matter how many items there are

A
  1. takes the same time no matter how many items there are
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

The maximum number of elements that must be examined to complete a binary search in an array of 200 elements is:

1.200
2. 8
3. 1
4. 13

A

8

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

What is the output of the following code segments?

int n=9;

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

while (n>0){

  s.push(n%2);

  n=n/2;

}

while (!s.isEmpty()){

  System.out.print(s.pop()+" ");

}

System.out.println();
A

1 0 0 1

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

Suppose that a minus sign in the input indicates pop a stack, and other string indicates push the string into a stack. What will be the content (from top to bottom) of the stack with the following inputs

A C - G H - - F C - - M P

A

PMA

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

Suppose to sort an arbitrary array using selection sort, we need to use 1024ms. How much time do we need to sort it using bubble sort?

A

1024ms

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

Given the array: 0 6 3 2 10 7 9 8.

Show what the array will look like using Bubble Sort to sort it for the first three iterations. (iterations happen based on the rule of the sort, ex bubble 1st iteration finishes after it switches les and right and done.

A

1st) 0 3 6 2 10 7 9 8
2nd). 0 3 2 6 10 7 9 8
3rd) 0 3 2 6 7 10 9 8

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

Given the array: 0 6 3 2 10 7 9 8.

Show what the array will look like using Selection Sort to sort it for the first three iterations.

A

1st) 0 6 3 2 10 7 9 8
2nd). 0 2 3 6 10 7 9 8
3rd) 0 2 3 6 10 7 9 8

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

Given the array: 0 6 3 2 10 7 9 8

Show what the array will look like using Insertion Sort to sort it for the first three iterations.

A

1st) 0 3 6 2 10 7 9 8
2nd). 0 3 2 6 10 7 9 8
3rd). 0 2 3 6 10 7 9 8

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

How many iterations are needed in bubble sort?

A

n-1

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

Given an arbitrary array with N elements, how many iterations do you need to sort it into ascending order using Insertion sort?

A

-N^2
-N-1

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

What is the output of the following code segments?

public static viod main (String[] args)
{
Stack myStack new Stack(5);
Queue myQueue=new Queue(5);
for(int i=1;i<=5;i++)
myStack.push(i);

myStack.display();//

while(!myStack.isEmpty())
myQueue.enqueue(myStack.pop());

while(!myQueue.isEmpty())
myStack.push(myQueue.dequeue());

myStack.display();//
}

A

5 4 3 2 1

1 2 3 4 5

17
Q

Suppose that a minus sign in the input indicates dequeue the queue, and other string indicates enqueue the string into a queue. What will be the content (from front to rear) of the queue with the following inputs:

a f - e c - - g h - - m z - z y k t - -

A

af - a

f +ec a

fec – afe

c +gh afe

cgh – afecg

h +mz afecg

hmz - afecgh

mz +zykt. afecgh

mzykt - - afecghmz

ykt afecghmz

18
Q

You want to keep a list of tasks to be processed. You know the maximum number of tasks possible and you want quick access to each task information.

A

array

19
Q

You have the same list of tasks, but now tasks have different importance levels to you. You want to have quick access to the most important task.

A

priority queue

20
Q

You want to process tasks in order of their arrival, and you want to delete the processed tasks.

A

queue

21
Q

Suppose you want to insert a new node with data of 65 between the nodes referenced by previous and current, what would be

your codes to implement this.

A

public class insertion_between_nodes_linkedlist{
static class Node {
int data;
Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public static void traverseAndPrint(Node head) {
    Node currentNode = head;
    while (currentNode != null) {
        System.out.print(currentNode.data + " -> ");
        currentNode = currentNode.next;
    }
    System.out.println("null");
}

public static Node insertNodeAtPosition(Node head, Node newNode, int position) {
    if (position == 1) {
        newNode.next = head;
        return newNode;
    }

    Node currentNode = head;
    for (int i = 1; i < position - 1 && currentNode != null; i++) {
        currentNode = currentNode.next;
    }

    if (currentNode != null) {
        newNode.next = currentNode.next;
        currentNode.next = newNode;
    }
    return head;
}

public static void main(String[] args) {
    Node node1 = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    Node node4 = new Node(4);
    Node node5 = new Node(5);

    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node5;

    System.out.println("Original list:");
    traverseAndPrint(node1);

    Node newNode = new Node(65);
    node1 = insertNodeAtPosition(node1, newNode, 4);

    System.out.println("\nAfter insertion:");
    traverseAndPrint(node1);
} }
22
Q

Given the following doubly linked list, write the corresponding codes so that you can traverse the entire list backward.

A

public class Transverse_linkedlist_backwards {
static class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
public static void traverseBackward(Node head) {
if (head == null) {
return;
}
if (head.next != null) {
traverseBackward(head.next);
System.out.print(“ -> “);
}
System.out.print(head.data);
}
public static void main(String[] args) {
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
System.out.println(“Original list (backward):”);
traverseBackward(node1);
System.out.println(“null”);
}
}

23
Q

Assume that LL is a DOUBLY linked list with the first node and at least one other internal node M that is not the last node. You may assume that each node has a next pointer and prev pointer, and the reference to node M is already known to you. There is no other existing method for you to call. Note that for each operation, you need to manipulate at least two pointers, next and prev.

1) Swap the first node and the M node ( you are Not allowed to simply swap the data)

A

public class Double_Linkedlist{
static class Node {
int data;
Node next;
Node prev;

    public Node(int data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

public static void swapFirstAndM(Node first, Node M) {
    if (first == M) {
        return;
    }

    if (first.prev != null) {
        first.prev.next = M;
    }
    if (M.prev != null) {
        M.prev.next = first;
    }

    if (first.next != null) {
        first.next.prev = M;
    }
    if (M.next != null) {
        M.next.prev = first;
    }

    Node tempNext = first.next;
    first.next = M.next;
    M.next = tempNext;

    Node tempPrev = first.prev;
    first.prev = M.prev;
    M.prev = tempPrev;
}

public static void printList(Node head) {
    Node currentNode = head;
    while (currentNode != null) {
        System.out.print(currentNode.data + " ");
        currentNode = currentNode.next;
    }
    System.out.println();
}

public static void main(String[] args) {
    Node first = new Node(1);
    Node second = new Node(2);
    Node third = new Node(3);
    Node fourth = new Node(4);

    first.next = second;
    second.prev = first;
    second.next = third;
    third.prev = second;
    third.next = fourth;
    fourth.prev = third;

    System.out.println("Original list:");
    printList(first);

    Node M = third;

    swapFirstAndM(first, M);

    System.out.println("List after swapping:");
    printList(M);  
}

}

24
Q

Suppose in the following singly linked list, the prev and next references are already known (they are pointing to two links respectively). Write the statements so that we can add a new link referenced by newLink into between the prev and next.

A

Node newLink = new Node(newData);

prev.next = newLink;

newLink.next = next;
25
Q

In a single-end singly linked list with no cycles, the next data field of the last node in the list is of value null. TRUE OR FALSE

A

true

26
Q

What is the output of by calling foo(17, 3)?

public int foo(int a, int b){

If (a%b==0) return b; 

else return foo(b, a%b);

}

A

Output : 1

explanation:

(17%3) remainder=2 –> (2, 17%3)

(3%2) remainder=1–> (1,3%2)

(2%1) remainder=1–>(1, 2%1)

(1% 0) remainder=0–>returns b which is 1

27
Q

Which of the following statements are true?

  1. Every recursive method must have a base case or a stopping condition.
  2. Every recursive call reduces the original problem, bringing it increasingly closer to a base case until it becomes that case.
  3. Infinite recursion can occur if recursion does not reduce the problem in a manner that allows it to eventually converge into the base case.
  4. Every recursive method must have a return value.
  5. A recursive method is invoked differently from a non-recursive method.

6.A StackOverFlow Exception will occur If there were too many function calls with not enough matching returns. One situation is that there is no base case provided, so the method never ends calling itself.

A

1, 2, 3,6

28
Q

What are the base cases in the following recursive method?

public static void xMethod(int n) {

  if (n > 0) {

    System.out.print(n % 10);

    xMethod(n / 10);

  }

}

A

n <=0

29
Q

Why the following codes fail?

public static int xMethod(int n) {

return n + xMethod(n - 1);

}

A

It would fail because there is no base case.

public static int xMethod(int n) {

    if (n == 1) {

           return 1 ;

     } else {

          return n + xMethod(n - 1);

} }

30
Q

Why does the following recursive method fail?

public long factorial(short n) {

long result = n * factorial(n-1);

    if (n == 1) { return 1; }

    return result;

}

factorial(10);

A

The recursive method for calculating the factorial of a num would fail because it only handles the case when input num is 1 leaving out all the other inputs. It would produce incorrect factorials of numbers other than 1. Instead there should include a base case that will cover all the possible input values like 0 or 1 and then make sure that the recursion will stop for all cases.

31
Q

Which of the following statements about interface are correct?

  1. An interface may contain constructors.
  2. An interface can be instantiated
  3. A class can only implement one interface.
  4. All the methods in an interface are abstract
  5. If a class implements an interface, it should implement all the abstract methods in the interface.
A

4 and 5

32
Q

Why does the following codes fail?

public static int xMethod2(int n) {

if (n == 1) return 1;

else return n + xMethod2(n + 1);

}

int result = xMethod2(2);

A

It doesn’t have a base case to terminate the recursion, which leads to an infinite recursion and a StackOverflowError. As the recursive call xMethod2(n+1) The argument increases by 1, which wont stop as there is no condition to stop the recursion and once it grows too large, it would lead to a StackOverflowError.

33
Q
A

Data Structure and Algorithms (8 decks)

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