Quizzes Questions/answer Flashcards
Suppose you want to define a data structure that is fast in search, which of the following data structure would you choose?
ordered array
Rank the following time complexity orders with the slowest one comes first.
- O(1)
- O(logn)
- O(n)
- O(nlogn)
- O(n^2)
- O(n^3)
- O(2^n)
O(1) means a process operates in __ time.
constant
In general, ordered arrays, compared with unordered array, are: (select all that are correct)
- slower Insertion
- Quicker at searching
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?
False
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
- takes the same time no matter how many items there are
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
8
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();
1 0 0 1
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
PMA
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?
1024ms
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.
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
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.
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
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.
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 many iterations are needed in bubble sort?
n-1
Given an arbitrary array with N elements, how many iterations do you need to sort it into ascending order using Insertion sort?
-N^2
-N-1
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();//
}
5 4 3 2 1
1 2 3 4 5
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 - -
af - a
f +ec a
fec – afe
c +gh afe
cgh – afecg
h +mz afecg
hmz - afecgh
mz +zykt. afecgh
mzykt - - afecghmz
ykt afecghmz
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.
array
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.
priority queue
You want to process tasks in order of their arrival, and you want to delete the processed tasks.
queue
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.
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);
} }
Given the following doubly linked list, write the corresponding codes so that you can traverse the entire list backward.
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”);
}
}
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)
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);
}
}
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.
Node newLink = new Node(newData);
prev.next = newLink; newLink.next = next;
