All past midterm questions · Submit to see grading & explanations
public Node getSecondToLast(SList S) that takes a Singly
Linked List as a parameter and returns a reference to the node before the last node
in the list.public int size() which returns the size of this CircularList.public SList cloneSList(SList S) that creates a
copy of the provided Singly Linked List and returns a reference to the new list.
The original list must not be destroyed.void removeLast() for a singly-linked
list. The method removes the last node. The list maintains size, head, and
tail references.tmp after the node
p in a doubly-linked list. Each node has next and
prev data members.
A ↔ E(p) ↔ F · Insert tmp(D) after
p(E) → result: A ↔ E ↔ D ↔ F
public Node getKthValue(Node H, int k) that takes a
pointer to the Head of a Singly Linked List and an integer k. Return a pointer to the
kth node. Start counting Head as position 1.1 ↔ 2(G) ↔ 3 ↔ 4 ↔ 5 ↔ 6. Node G points to value 2. Write
code to swap nodes containing values 2 and 5. You may create other pointers as
necessary.
class Node { Node prev, next; int value; }
public void remove(int value) in Java within a
Circular Linked List class that searches for a value and removes it from the list.
Each node stores only an integer val and a next pointer.1 → 2 → 4 · B: 1 → 3 → 4 · C:
1 → 1 → 2 → 3 → 4 → 4
PrintDuplicate() extending the
SinglyLinkedList class. This method prints all duplicate values in the list. Also
explain why or why not your code runs in linear time.Scanner to
a text file containing English words (one per line). This method creates an array of 26
Singly Linked Lists, fills them with words from the file based on the word's first
letter (e.g. words starting with 'a' go to A[0], 'b' to A[1], etc.), and returns a reference to this
array.Header ↔ [5] ↔ [10] ↔ [15] ↔ [20] ↔ Trailer, with
temp pointing to node [5]. Trace this code and write/draw the sequence of values from
Head to Tail after execution.
Node A = temp.next; // A → [10] Node B = A.next; // B → [15] // Step 1 A.prev.next = B; B.prev = A.prev; // Step 2 A.next = B.next; if (A.next != null) A.next.prev = A; // Step 3 B.next = A; A.prev = B;
name (String) and
next. Complete the method
RemoveName(SinglyLinkedList L, String N) that searches and removes the
node containing name N. Example: remove "May" from John → Ali → Zaid → May → Rose.
public void RemoveName(SinglyLinkedList L, String N){
if(Head.name == N){
____________________________________________
}
Node S = Head;
Node F = S.next;
while(F != null){
if(F.name == N){
____________________________________________
}
_________________;
_________________;
}
return;
}
public Node Find(SinglyLinkedList L) {
if (L.head == null) return null;
Node slow = L.head;
Node fast = L.head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
| Function f(n) | Big-O Answer |
|---|---|
| (a) f(n) = N²log N² + 2N log 2N | |
| (b) f(n) = (N · (100N + 5 + N²))² | |
| (c) f(n) = N1/2 + log log N | |
| (d) f(n) = 1000 log log N + log N | |
| (e) f(n) = 100n³ − 7n³ + 14n² | |
| (f) f(n) = 100n³ − 100n³ + 7n² | |
| (g) f(n) = log(7n²) | |
| (h) f(n) = 5 log log n + 4 log²(n) | |
| (i) f(n) = 0.001n + 100·2ⁿ | |
| (j) f(n) = n³(1 + 6n + 2014n²) | |
| (k) f(n) = (log n)(n + n²) | |
| (l) f(n) = n²log n + 2n | |
| (m) f(n) = 100n² − 100n² + 14n³ | |
| (n) f(n) = 100 log log n + 100 log²n | |
| (o) f(n) = n³(10 + 20n + 20n²) | |
| (p) f(n) = n²log n + 100n |
count++ executed? What is the Big-O?count = 0;
for(int i = 1; i < 10; i++) {
count++;
}
s = 0;
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
s = s + 1;
// Snippet A
int k = 0;
for (i = 1; i <= n; i++)
for (j = 1; j <= 10; j++)
k = k + i + j;
// Snippet B
int k = 0;
for (i = 1; i <= n; i++)
for (j = i; j <= n; j++)
k = k + i;
// Snippet C
for (i = n; i >= 1; i /= 2)
System.out.println(i);
void f1(int n) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < 10; j++) {
for(int k = 0; k < n; k++) {
for(int m = 0; m < 10; m++) {
System.out.println("!");
}
}
}
}
}
// Snippet 1 — processFixedGrid
public void processFixedGrid(int n) {
int sum = 0;
for (int i = 1; i <= 10; i++)
for (int j = 1; j <= 5; j++)
sum = sum + i + j;
System.out.println("Result " + n + " is " + sum);
}
// Snippet 2 — sqrtSearch (recursive, trace for sqrtSearch(n, 0, n))
public int sqrtSearch(int n, int low, int high) {
if (low > high) return high;
int mid = (low + high) / 2;
long square = (long) mid * mid;
if (square == n) return mid;
if (square < n) return sqrtSearch(n, mid + 1, high);
else return sqrtSearch(n, low, mid - 1);
}
silly(8,0).
Show the trace.public int silly(int n, int m) {
if (n < 1) return m;
else return silly(n/2, m);
}
// Call: silly(8, 0)
recur(32)int recur(int n) {
if (n == 1) return 0;
return 1 + recur(n / 2);
}
// Call: recur(32)
f2(15, 5) and give the Big-O notation.int f2(int n, int m) {
if (n == 0) return 1;
if (n % 2 == 0) return f2(n/2, m);
else return f2((n-1)/2, m-1);
}
// Trace: f2(15, 5)
productDigits(2121) — fill in the table. What is the Big-O? Then
complete the linked-list version productDigitsList(Node head).public static int productDigits(int n) {
if (n == 0) return 1;
return (n % 10) * productDigits(n / 10);
}
// Example: productDigits(234) = 2 × 3 × 4 = 24
fun(n). Show the output when
n=3 and draw the recursion trace.static void fun(int n) {
if (n < 1) return;
else {
System.out.println(n);
fun(n - 1);
System.out.println(n);
return;
}
}
// Call: fun(3)
[ K | R | A | T | E | L | P | U | I ]
[3, -1, -6, 0, -8, 4, 2, 1, -1, -2, 1]
[1, 2, 3, 4, 5, 6, 7] → sum of odds = 16
Scroll up to see detailed feedback under each question.