Linked Lists

Single correct

• ASLLdel is $O(1)$ and DLLdel is $O(n)$
• BBoth SLLdel and DLLdel are $O(\log(n))$
• CBoth SLLdel and DLLdel are $O(1)$
• DSLLdel is $O(n)$ and DLLdel is $O(1)$

Answer key coming soon

Single correct

• AThe best algorithm for the problem takes $\theta(n)$ time in the worst case.
• BThe best algorithm for the problem takes $\theta(n\log n)$ time in the worst case.
• CThe best algorithm for the problem takes $\theta(n^2)$ time in the worst case.
• DIt is not possible to reverse a singly linked list in $O(1)$ space.

Answer key coming soon

Single correct

• A$\Theta(n)$
• B$\Theta(n \log n)$
• C$\Theta(n^2)$
• D$\Theta(1)$

Answer key coming soon

Single correct

• A$\Theta(1), \Theta(1)$
• B$\Theta(1), \Theta(n)$
• C$\Theta(n), \Theta(1)$
• D$\Theta(n), \Theta(n)$

typedef struct node {
  int data;
  node* next;
} node;

void join(node* m, node* n){
  node* p = n;
  while(p->next != NULL) {
    p = p->next;
  }
  p->next = m;
}

Single correct

• Aappend list m to the end of list n for all inputs.
• Beither cause a null pointer dereference or append list m to the end of list n.
• Ccause a null pointer dereference for all inputs.
• Dappend list n to the end of list m for all inputs.

Answer key coming soon

Single correct

• AI only
• BII only
• CBoth I and II
• DNeither I nor II

Answer key coming soon

Single correct

• A$O(\log^2 N)$
• B$O(N)$
• C$O(N^2)$
• D$\Theta(N^2 \log N)$

Answer key coming soon